CH11差错控制编码课件

差错控制编码通信工程学院

陈爱萍8171-1@163.com1差错控制编码通信工程学院陈爱萍8171-1@163.c基本要求数字通信纠错和检错编码的基本原理与分类；几种常用简单编码的编码规则及特点；线性分组码的编码规则及特点。2基本要求数字通信纠错和检错编码的基本原理与分类；2引言减小接收端发生码元错误的措施采用无ISI传输系统选择合适的调制、解调方法增加信号的发送功率采用差错控制编码差错控制编码的概念：又称为信道编码目的：克服信息传输过程中由于信道噪声、干扰（加性干扰）引起的误码，提高可靠性（信源编码：提高有效性;）方法：在信息码元中加入冗余的监督码元来提高抗干扰能力实质：有效性换可靠性3引言减小接收端发生码元错误的措施差错控制编码的概念：又称为错误种类信道中常见的错误有以下三种：随机错误：错误的出现是随机的，即各个码元是否发生错误是互相独立的，通常不是成片地出现错误。由信道的加性随机噪声引起，故把具有此特性的信道称为随机信道

突发错误：错误是一连串出现的。通常在一个突发错误持续时间内，开头和末尾的码元总是错的，中间的某些码元可能错也可能对，但错误的码元相对较多。如移动通信中信号在某一段时间内发生衰落，造成一串差错；汽车发动时电火花干扰造成的错误；光盘上的一条划痕等。这样的信道称为突发信道。混合错误：既有突发错误又有随机错误的情况。这种信道称为混合信道4错误种类信道中常见的错误有以下三种：随机错误：错误的出现是随差错控制方式自动重发请求（ARQ）：发端发送能检错的码；收端对收到的码作判决，若有错则通知发端请求重发，直到正确接收为止。

特点：可具有不同的重发机制,需要反馈信道.可达到良好的性能，但实时性很差前向纠错（FEC）：发端发送能纠正错误的编码,收端对收到的码作判决，若有错则纠之。特点：不需反馈信道,实时性好；译码设备复杂应用：大量使用在数字通信和存储系统中，原因是：采用专用大规模集成电路的编译码器，体积、成本小；显著改善误码率混合方式(HEC)：结合FEC和ARQ方式,在纠错能力范围内,自行纠错,否则请求重传.5差错控制方式自动重发请求（ARQ）：发端发送能检错的码；收端差错控制方式图示6差错控制方式图示6差错控制编码的分类按信息码与监督码间关系分：线性码与非线性码（函数关系为现性与非线性）按组内各码元与信息码之间关系的涉及范围：分组码（组内各码元只与本组信息码元有关）卷积码（组内各码元不仅与本组信息码元有关，而且与前面若干组信息码元有关）按码编前后信息码元是否保持原样：系统码（保持原样）与非系统码（不保持原样）按码的功能分：检错码（只能检错）与纠错码（能检错和纠错）按纠（检）错码的类型：纠正随机错误码与纠正突发错误码

随着数字通信系统的发展，可以将信道编码器和调制器统一起来综合设计，这就是所谓的网格编码调制。7差错控制编码的分类按信息码与监督码间关系分：线性码与非线性码GSM系统的话音和信道编码组成帧长20ms速率22.8kb/s8GSM系统的话音和信道编码组成帧长20ms8几个相关的名词码长：一个码组（码字、码矢）中码元的数目码重：一个码组（码字、码矢）中非零位的个数码距：两个等长码组之间对应位不同的个数。最小码距d0是码组集合中，所有码距的最小值9几个相关的名词码长：一个码组（码字、码矢）中码元的数目9抗干扰能力与最小码距d0的关系纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。要检测e

个错误，则d0≥e+1；要纠正

t

个错误，则d0≥2t+1；要纠正t个错误，同时检测e个错误（e>t），则d0≥t+e+110抗干扰能力与最小码距d0的关系纠错码的抗干扰能力完全取决例1：已知8个码组为000000，001110，010101，011011100011，101101，110110，1110001）求该码组的最小距离；2）若用于检错，能检出几位错误？3）若用于纠错，能纠正几位错误？3）若同时用于检错和纠错，问纠错、检错的性能如何？解：1）最小码距为所有码距中的最小值2）检错时，d0e+1，ed0–1=2，能检出2位错误；d0=3；3）纠错时，d02t+1，t(d0–1)/2=1，能纠1位错误；4）检错和纠错：d0e+t+1，且e<t，故不能同时用于检错和纠错11例1：已知8个码组为解：1）最小码距为所有码距中的最小值2几种简单的纠错码奇偶监督码：只有一位监督码，它使码组中“1”的数目为偶数或奇数，编码效率高。a0为监督位，其他为信息位偶数监督码：奇数监督码：特点：只能发现单个或奇数个错误，“检奇不检偶”。最小码距为2；适合检测随机错误，对突发错误无能为力；编码效率:R=(n-1)/n12几种简单的纠错码奇偶监督码：只有一位监督码，它使码组中“1”二维奇偶监督码：又称为方阵码，在行编码的基础上，再作列编码。特点：可以发现某一行或某一列上的所有奇数个错误及长度不大于行数(或列数)的突发错误（交织）几种简单的纠错码---二维奇偶监督码对构成矩形四角的错码无法检出13二维奇偶监督码：又称为方阵码，在行编码的基础上，再作列编码。恒比码：恒比码又称等重码，码组中1和0的位数保持恒定的比例。数目不对则错误我国电传通信中普遍采用3:2码，国际上通用的ARQ电报通信系统中，采用3:4码，即7中取3码。正反码：监督位数目和信息位数目相同，监督码元与信息码元相同或者相反（信息码的重复或信息码的反码）几种简单的纠错码---恒比码和正反码14恒比码：恒比码又称等重码，码组中1和0的位数保持恒定的比例。线性分组码

概念：信息码元和监督码元用线性方程联系起来。是一组固定长度的码组，可表示为（n,k），用于前向纠错。编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错与纠错。编码效率：R=k/n性质：任意两许用码组之和（逐位模2加）仍为一许用码组，即线性码有封闭性；最小码距等于非零码的最小码重例1：000000，001110，010101，011011100011，101101，110110，11100015线性分组码概念：信息码元和监督码元用线性方程联系起来。是一例：奇偶监督码是一种简单的线性码。一位监督码（an-1an-2…a2

a1

a0

）发送时：0=an-1an-2…a1

a0

（偶校验）接收时：S=an-1an-2…a1

a0

S=0，表示无错；

S=1，表示有错，但无法指示错码的位置。S称为校正子,又称伴随式一般来说，r(r=n-k)个监督方程计算得到r个较正子S，对一位错码来说，可以表示出(2r-1)个可能的错码位置；如r=2，S的可能值有：00,01,10,11,若用其中一种组合表示无措，则其余3种组合可以指示一个错码的3种位置；因此对于(n,k)分组码，若满足:2r

-1≥n,

则有可能构造出指示一位错码的n种可能位置。

16例：奇偶监督码是一种简单的线性码。一位监督码（an-1a错码位置S1S2S3a6111a5110a4101a3011a2100a1010a0001无错000错码图样（并非唯一）a6a5

a4

a2

=S1a6a5

a3

a1

=S2a6a4

a3

a0=S3（偶数监督关系）举例：(7,4)分组码，又称汉明码，n=7,k=4,r=3,最小码距（汉明距）：d0=3(t=1,e=2)可纠正一个错误或检测2个错误设码组为：a6a5a4a3

a2a1a0定义校正子S与错码的关系如表：编码效率最高的线性分组码。例如：(7,4)、(15,11)码。17错码位置S1S2S3a6111a5110a4101a3011a2

=

a6a5

a4a1

=

a6a5

a3a0

=a6a4

a3经移位后可得到监督位：

全部16种许用码组如表a6a5

a4

a2=0a6a5

a3

a1=0a6a4

a3

a0

=0由：发端编码a6a5a4a3

a2a1a0：信息位是随机的，如何确定a2a1a0？18a2=a6a5a4经移位后可得到监督例：若接收码组为：0000011S1=a6a5

a4

a2=0S2=a6a5

a3

a1=1S3=a6a4

a3

a0=1S1S2S3=011，故错码在a3位！收端考察S1S2S3是否为零可纠错1位错码位置S1S2S3a6111a5110a4101a3011a2100a1010a0001无错000错码图样19例：若接收码组为：0000011S1=a6监督矩阵H据：线性码是信息位和监督位满足一线性方程的码1·a6+1·a5+1·

a4+0·

a3+

1·

a2+0·

a1

+0·

a0

=01·a6+1·a5+0·

a4

+1·

a3+0·

a2+1·

a1

+0·

a0

=01·a6+0·a5

+1·

a4+1·

a3+0·

a2

+0·

a1

+1·

a0

=0（注：这里“+”=

）a6a5

a4

a2=0a6a5

a3

a1=0a6a4

a3

a0

=0由：20监督矩阵H据：线性码是信息位和监督位满足一线性方程的码1·aH为监督矩阵，rn阶，具有H=PIr的形式，又称为典型监督矩阵；P为rk阶矩阵；Ir为rr阶方阵A为编码码组；O为行向量H的转置矩阵21H为监督矩阵，rn阶，具有H=PIr的形式，又称为典型监督Q为kr阶矩阵，它为P的转置，即：生成矩阵G22Q为kr阶矩阵，它为P的转置，即：生成矩阵G22定义生成矩阵G：由此可产生整个码组G为kn阶;生成矩阵的每一行都是一个许用码组，并有：GHT=O；具有G=IkQ的形式，又称为典型监督矩阵；A中，信息位不变，监督位附加在后又称为系统码23定义生成矩阵G：由此可产生整个码组G为kn阶;23例224例224校验子S设发送组码A，在传输过程中有可能出现误码，这时接收到的码组为B。则收发码组之差为：

则接收端利用接收到的码组B计算校正子：

S=BHT=(A+E)HT=AHT+EHT=EHT

故校正子仅与E有关，即错误图样与校正子之间有确定的关系。其中：25校验子S设发送组码A，在传输过程中有可能出现误码，这时接收到例3错码位置S1S2S3a6111a5110a4101a3011a2100a1010a0001无错00026例3错码位置S1S2S3a6111a5110a4101a3重要概念差错控制编码的目的：提高信息传输的可靠性实质：有效性换可靠性码长：一个码组中码元的数目码重：一个码组中非零位的个数码距：两个等长码组之间对应位不同的个数。最小码距dmin是码组集合中，所有码距的最小值分组码表示符号(n,k)：n是码组总位数，k是信息码位数，监督位的位数：r=n-k编码效率：R=k/n汉明码：可纠正1位错码，编码效率最高的线性分组码。(7,4)、(15,11)码。码长：n=2r

-1

信息位：k=n–r=2r

–r-1

监督位：r3最小码距（汉明距）：dmin=3(t=1或e=2)27重要概念差错控制编码的目的：提高信息传输的可靠性27

如果码组B无错，B＝A，则M＝0；如果码组B有单个（或奇数个）错误，则M＝1。奇偶监督码的编码可以用软件实现，也可用硬件电路实现。奇偶监督码的编码的实现28如果码组B无错，B＝A，则M＝0；如果码组B有单个（或差错控制编码通信工程学院

陈爱萍8171-1@163.com29差错控制编码通信工程学院陈爱萍8171-1@163.c基本要求数字通信纠错和检错编码的基本原理与分类；几种常用简单编码的编码规则及特点；线性分组码的编码规则及特点。30基本要求数字通信纠错和检错编码的基本原理与分类；2引言减小接收端发生码元错误的措施采用无ISI传输系统选择合适的调制、解调方法增加信号的发送功率采用差错控制编码差错控制编码的概念：又称为信道编码目的：克服信息传输过程中由于信道噪声、干扰（加性干扰）引起的误码，提高可靠性（信源编码：提高有效性;）方法：在信息码元中加入冗余的监督码元来提高抗干扰能力实质：有效性换可靠性31引言减小接收端发生码元错误的措施差错控制编码的概念：又称为错误种类信道中常见的错误有以下三种：随机错误：错误的出现是随机的，即各个码元是否发生错误是互相独立的，通常不是成片地出现错误。由信道的加性随机噪声引起，故把具有此特性的信道称为随机信道

突发错误：错误是一连串出现的。通常在一个突发错误持续时间内，开头和末尾的码元总是错的，中间的某些码元可能错也可能对，但错误的码元相对较多。如移动通信中信号在某一段时间内发生衰落，造成一串差错；汽车发动时电火花干扰造成的错误；光盘上的一条划痕等。这样的信道称为突发信道。混合错误：既有突发错误又有随机错误的情况。这种信道称为混合信道32错误种类信道中常见的错误有以下三种：随机错误：错误的出现是随差错控制方式自动重发请求（ARQ）：发端发送能检错的码；收端对收到的码作判决，若有错则通知发端请求重发，直到正确接收为止。

特点：可具有不同的重发机制,需要反馈信道.可达到良好的性能，但实时性很差前向纠错（FEC）：发端发送能纠正错误的编码,收端对收到的码作判决，若有错则纠之。特点：不需反馈信道,实时性好；译码设备复杂应用：大量使用在数字通信和存储系统中，原因是：采用专用大规模集成电路的编译码器，体积、成本小；显著改善误码率混合方式(HEC)：结合FEC和ARQ方式,在纠错能力范围内,自行纠错,否则请求重传.33差错控制方式自动重发请求（ARQ）：发端发送能检错的码；收端差错控制方式图示34差错控制方式图示6差错控制编码的分类按信息码与监督码间关系分：线性码与非线性码（函数关系为现性与非线性）按组内各码元与信息码之间关系的涉及范围：分组码（组内各码元只与本组信息码元有关）卷积码（组内各码元不仅与本组信息码元有关，而且与前面若干组信息码元有关）按码编前后信息码元是否保持原样：系统码（保持原样）与非系统码（不保持原样）按码的功能分：检错码（只能检错）与纠错码（能检错和纠错）按纠（检）错码的类型：纠正随机错误码与纠正突发错误码

随着数字通信系统的发展，可以将信道编码器和调制器统一起来综合设计，这就是所谓的网格编码调制。35差错控制编码的分类按信息码与监督码间关系分：线性码与非线性码GSM系统的话音和信道编码组成帧长20ms速率22.8kb/s36GSM系统的话音和信道编码组成帧长20ms8几个相关的名词码长：一个码组（码字、码矢）中码元的数目码重：一个码组（码字、码矢）中非零位的个数码距：两个等长码组之间对应位不同的个数。最小码距d0是码组集合中，所有码距的最小值37几个相关的名词码长：一个码组（码字、码矢）中码元的数目9抗干扰能力与最小码距d0的关系纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。要检测e

个错误，则d0≥e+1；要纠正

t

个错误，则d0≥2t+1；要纠正t个错误，同时检测e个错误（e>t），则d0≥t+e+138抗干扰能力与最小码距d0的关系纠错码的抗干扰能力完全取决例1：已知8个码组为000000，001110，010101，011011100011，101101，110110，1110001）求该码组的最小距离；2）若用于检错，能检出几位错误？3）若用于纠错，能纠正几位错误？3）若同时用于检错和纠错，问纠错、检错的性能如何？解：1）最小码距为所有码距中的最小值2）检错时，d0e+1，ed0–1=2，能检出2位错误；d0=3；3）纠错时，d02t+1，t(d0–1)/2=1，能纠1位错误；4）检错和纠错：d0e+t+1，且e<t，故不能同时用于检错和纠错39例1：已知8个码组为解：1）最小码距为所有码距中的最小值2几种简单的纠错码奇偶监督码：只有一位监督码，它使码组中“1”的数目为偶数或奇数，编码效率高。a0为监督位，其他为信息位偶数监督码：奇数监督码：特点：只能发现单个或奇数个错误，“检奇不检偶”。最小码距为2；适合检测随机错误，对突发错误无能为力；编码效率:R=(n-1)/n40几种简单的纠错码奇偶监督码：只有一位监督码，它使码组中“1”二维奇偶监督码：又称为方阵码，在行编码的基础上，再作列编码。特点：可以发现某一行或某一列上的所有奇数个错误及长度不大于行数(或列数)的突发错误（交织）几种简单的纠错码---二维奇偶监督码对构成矩形四角的错码无法检出41二维奇偶监督码：又称为方阵码，在行编码的基础上，再作列编码。恒比码：恒比码又称等重码，码组中1和0的位数保持恒定的比例。数目不对则错误我国电传通信中普遍采用3:2码，国际上通用的ARQ电报通信系统中，采用3:4码，即7中取3码。正反码：监督位数目和信息位数目相同，监督码元与信息码元相同或者相反（信息码的重复或信息码的反码）几种简单的纠错码---恒比码和正反码42恒比码：恒比码又称等重码，码组中1和0的位数保持恒定的比例。线性分组码

概念：信息码元和监督码元用线性方程联系起来。是一组固定长度的码组，可表示为（n,k），用于前向纠错。编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错与纠错。编码效率：R=k/n性质：任意两许用码组之和（逐位模2加）仍为一许用码组，即线性码有封闭性；最小码距等于非零码的最小码重例1：000000，001110，010101，011011100011，101101，110110，11100043线性分组码概念：信息码元和监督码元用线性方程联系起来。是一例：奇偶监督码是一种简单的线性码。一位监督码（an-1an-2…a2

a1

a0

）发送时：0=an-1an-2…a1

a0

（偶校验）接收时：S=an-1an-2…a1

a0

S=0，表示无错；

S=1，表示有错，但无法指示错码的位置。S称为校正子,又称伴随式一般来说，r(r=n-k)个监督方程计算得到r个较正子S，对一位错码来说，可以表示出(2r-1)个可能的错码位置；如r=2，S的可能值有：00,01,10,11,若用其中一种组合表示无措，则其余3种组合可以指示一个错码的3种位置；因此对于(n,k)分组码，若满足:2r

-1≥n,

则有可能构造出指示一位错码的n种可能位置。

44例：奇偶监督码是一种简单的线性码。一位监督码（an-1a错码位置S1S2S3a6111a5110a4101a3011a2100a1010a0001无错000错码图样（并非唯一）a6a5

a4

a2

=S1a6a5

a3

a1

=S2a6a4

a3

a0=S3（偶数监督关系）举例：(7,4)分组码，又称汉明码，n=7,k=4,r=3,最小码距（汉明距）：d0=3(t=1,e=2)可纠正一个错误或检测2个错误设码组为：a6a5a4a3

a2a1a0定义校正子S与错码的关系如表：编码效率最高的线性分组码。例如：(7,4)、(15,11)码。45错码位置S1S2S3a6111a5110a4101a3011a2

=

a6a5

a4a1

=

a6a5

a3a0

=a6a4

a3经移位后可得到监督位：

全部16种许用码组如表a6a5

a4

a2=0a6a5

a3

a1=0a6a4

a3

a0

=0由：发端编码a6a5a4a3

a2a1a0：信息位是随机的，如何确定a2a1a0？46a2=a6a5a4经移位后可得到监督例：若接收码组为：0000011S1=a6a5

a4

a2=0S2=a6a5

a3

a1=1S3=a6a4

a3

a0=1S1S2S3=011，故错码在a3位！收端考察S1S2S3是否为零可纠错1位错码位置S1S2S3a6111a5110a4101a3011a2100a1010a0001无错000错码图样47例：若接收码组为：0000011S1=a6监督矩阵H据：线性码是信息位和监督位满足一线性方程的码1·a6+1·a5+1·

a4+0·

a3+

1·

a2+0·

a1

+0·

a0

=01·a6+1·a5+0·

a4

+1·

a3+0·

a2+1·

a1

+0·

a0

=01·a6+0·a5

+1·

a4+1·

a3+0·

a2

+0·

a1

+1·

a0

=0（注：这里“+”=

）a6a5

a4

a2=0a6a5

a3

a1=0a6