《第7章 差错控制编码.ppt》由会员分享，可在线阅读，更多相关《第7章 差错控制编码.ppt（39页珍藏版）》请在第壹文秘上搜索。
1、第第7 7章章 差错控制编码差错控制编码 7.1 7.1 引言引言 7.2 7.2 常用简单分组码常用简单分组码 7.3 7.3 线性分组码线性分组码 7.4 7.4 循环码循环码 7.5 7.5 卷积码卷积码 7.6 m 7.6 m 序列序列7.1 7.1 引言引言7.1.1 7.1.1 信源编码与信道编码的基本概念信源编码与信道编码的基本概念 在数字通信系统中，为了提高数字信号传输的有效性而采在数字通信系统中，为了提高数字信号传输的有效性而采取的编码称为信源编码；为了提高数字通信的可靠性而采取取的编码称为信源编码；为了提高数字通信的可靠性而采取的编码称为信道编码。的编码称为信道编码。2 2
2、、信道编码（差错控制编码）、信道编码（差错控制编码）差错控制编码是在信息序列上附加上一些监督码元，利用差错控制编码是在信息序列上附加上一些监督码元，利用这些冗余的码元，使原来不规律的或规律性不强的原始数字这些冗余的码元，使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号；差错控制译码则利用这些规律信号变为有规律的数字信号；差错控制译码则利用这些规律性来鉴别传输过程是否发生错误，或进而纠正错误。性来鉴别传输过程是否发生错误，或进而纠正错误。7.1.2 7.1.2 纠错编码的分类纠错编码的分类 （1）按照信道编码的不同功能，可以分为）按照信道编码的不同功能，可以分为检错码检错码和和纠错码
3、纠错码。（2）按照信息码元和监督码元之间的检验关系，可以将它分按照信息码元和监督码元之间的检验关系，可以将它分为为线性线性码码和和非线性码非线性码。（3）按照信息码元和监督码元之间的约束方式不同，可以将按照信息码元和监督码元之间的约束方式不同，可以将它分为它分为分组码分组码和和卷积码卷积码。（4）按照信息码元在编码后是否保持原来的形式，可以将它按照信息码元在编码后是否保持原来的形式，可以将它分为分为系统码系统码和和非系统码非系统码。（5）按照纠正错误的类型不同，可以将它分为）按照纠正错误的类型不同，可以将它分为纠正随机错误纠正随机错误码码和和纠正突发错误码纠正突发错误码。（6）按照信道编码所采
4、用的数学方法不同，可以将它分为）按照信道编码所采用的数学方法不同，可以将它分为代代数码数码、几何码几何码和和算术码算术码。随着数字通信系统的发展，可以将信道编码器和调制器统一随着数字通信系统的发展，可以将信道编码器和调制器统一起来综合设计，这就是所谓的起来综合设计，这就是所谓的网格编码调制网格编码调制。7.1.2 7.1.2 差错控制方式差错控制方式检错重发（检错重发（ARQ）的）的优点优点主要表现在：主要表现在：（1）只需要少量的冗余码，就可以得到极低的输出误码率；）只需要少量的冗余码，就可以得到极低的输出误码率；（2）有一定的自适应能力；有一定的自适应能力；某些某些不足不足主要表现在：主要
5、表现在：（1）需要反向信道，故不能用于单向传输系统，并且实现重）需要反向信道，故不能用于单向传输系统，并且实现重发控制比较复杂；发控制比较复杂；（2）通信效率低，不适合严格实时传输系统。）通信效率低，不适合严格实时传输系统。混合纠错方式是前向纠错方式和检错重发方式的结合。混合纠错方式是前向纠错方式和检错重发方式的结合。检错重发方式：检错重发方式：7.1.2 7.1.2 纠错编码的基本原理纠错编码的基本原理 信道编码的基本概念：信道编码的基本概念：码长：码长：码字中码元的数目；码字中码元的数目；码重：码重：码字中非码字中非0数字的数目；数字的数目；码距：码距：两个等长码字之间对应位不同的数目，有
6、时也称两个等长码字之间对应位不同的数目，有时也称作这两个码字的汉明距离；作这两个码字的汉明距离；最小码距：最小码距：在码字集合中全体码字之间距离的最小数值。在码字集合中全体码字之间距离的最小数值。码率：码率：信息位信息位k k 与码长与码长n之比；之比；编码效率：编码效率：在给定误码率要求下，非编码系统与编码系在给定误码率要求下，非编码系统与编码系 统的性噪比之比。统的性噪比之比。纠错码的抗干扰能力完全取决于许用码字之间的距离，码纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。就越
7、强。分组码的最小汉明距离分组码的最小汉明距离d0与检错和纠错能力之间满足下列关系：与检错和纠错能力之间满足下列关系：（1）当码字用于检测错误时，如果要）当码字用于检测错误时，如果要检测检测e个错误个错误，则，则 d0 e+1 （2）当码字用于纠正错误时，如果要当码字用于纠正错误时，如果要纠正纠正t个错误个错误，则，则 d0 2t+1 （3）若码字用于）若码字用于纠纠t个错误个错误，同时检同时检e个错误个错误时（时（et），则），则 d0 t+e+1 编码效率编码效率Rc可以用下式表示：可以用下式表示：nrnrnnkRc17.2 7.2 常用简单分组码常用简单分组码 7.2.1 7.2.1 奇偶
8、监督码奇偶监督码 可以表示成为（可以表示成为（n，n-1）。如果是）。如果是奇监督码奇监督码，在附加，在附加上一个监督元以后，码长为上一个监督元以后，码长为n的码字中的码字中“1”的个数为奇的个数为奇数个；如果是数个；如果是偶监督码偶监督码，在附加上一个监督元以后，码，在附加上一个监督元以后，码长为长为n的码字中的码字中“1”的个数为偶数个。的个数为偶数个。an-1+an-2+a1+a0=0 奇奇偶偶监督码的编码可以用软件实现，也可用硬件电路实现。监督码的编码可以用软件实现，也可用硬件电路实现。如果码组如果码组B无错，无错，BA，则，则M0；如果码组；如果码组B有单个（或奇数有单个（或奇数个）
9、错误，则个）错误，则M1。7.2.2 7.2.2 行列监督码行列监督码 行列监督码又称行列监督码又称水平垂直一致监督码水平垂直一致监督码或或二维奇偶监督码二维奇偶监督码，有，有时还被称为时还被称为矩阵码矩阵码。1 1 0 0 1 0 1 0 0 00 1 0 0 0 0 1 1 0 10 1 1 1 1 0 0 0 0 11 0 0 1 1 1 0 0 0 01 0 1 0 1 0 1 0 1 0001011 1 0 0 0 1 1 1 1 00二维奇偶监督码适于检测突发错码。二维奇偶监督码不仅可二维奇偶监督码适于检测突发错码。二维奇偶监督码不仅可用来检错，还可用来纠正一些错码。用来检错，还可
10、用来纠正一些错码。7.2.3 7.2.3 恒比码恒比码 恒比码又称等重码，该码的码字中恒比码又称等重码，该码的码字中1和和0的位数保持恒定的的位数保持恒定的比例。具体情况见表比例。具体情况见表8-3。目前我国电传通信中普遍采用目前我国电传通信中普遍采用3：2码，国际上通用的码，国际上通用的ARQ电报通信系统中，采用电报通信系统中，采用3：4码即码即7中取中取3码。码。7.3 7.3 线性分组码线性分组码 7.3.1 7.3.1 基本概念基本概念 分组码是一组固定长度的码组，可表示为（分组码是一组固定长度的码组，可表示为（n,k），通常），通常它用于前向纠错。在编码时，它用于前向纠错。在编码时，
11、k个信息位被编为个信息位被编为n位码组长度，位码组长度，而而n-k个监督位的作用就是实现检错与纠错。个监督位的作用就是实现检错与纠错。这样，一个这样，一个k比特信息的线性分组码可以映射到一个长度为比特信息的线性分组码可以映射到一个长度为n码组上。码组上。线性分组码的线性分组码的主要性质主要性质如下：如下：（1）任意两许用码之和仍为一许用码，也就是说，线性分）任意两许用码之和仍为一许用码，也就是说，线性分组码具有封闭性；组码具有封闭性；（2）码组间的最小码距等于非零码的最小码重。码组间的最小码距等于非零码的最小码重。对偶校验时的监督关系。在对偶校验时的监督关系。在接收端解码接收端解码时，实际上就
12、是在时，实际上就是在计算：计算：S=bn-1+bn-2+b1+b0 若若S0，则无错；若，则无错；若S1就认为有错。就认为有错。例如例如r 3，若取，若取r=3，则，则n=k+r=7。假设。假设S3、S2、S1三位三位校正字码组与误码位置的关系如表校正字码组与误码位置的关系如表8-4。根据表。根据表8-4，可以构，可以构成如下关系式：成如下关系式：1212rknrr或 当当r个监督方程式计算得到的校正子有个监督方程式计算得到的校正子有r位，可以用来指示位，可以用来指示2r-1种误码图样。种误码图样。如果希望用如果希望用r个监督位构造出个监督位构造出r个监督关系式来指示一位错个监督关系式来指示一
13、位错码的码的n种可能，则要求：种可能，则要求：S1=a6+a5+a4+a2 ,S2=a6+a5+a4+a2 ,S3=a6+a4+a3+a0 进而得到进而得到下面的方程组形式：下面的方程组形式：000034613562456aaaaaaaaaaaaaaaaaaaaaaaa034613562456接收端收到每个码组后，计算出接收端收到每个码组后，计算出S3、S2和和S1，如不全为，如不全为0，则可，则可按表按表8-4确定误码的位置，然后予以纠正。不难看出，上述（确定误码的位置，然后予以纠正。不难看出，上述（7，4）码的最小码距）码的最小码距dmin3。上式可以记作：上式可以记作：HAT=0T或或A
14、HT=0，其中，其中010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa0001001101010101100101110123456Taaaaaaa7.3.2 监督矩阵监督矩阵H和生成矩阵和生成矩阵G 将（将（7，4）码的三个监督方程式可以重新改写为如下形式：）码的三个监督方程式可以重新改写为如下形式：rIPH1001101010101100101110000aaaaaaa0123456A这时这时Q=PT，如果在，如果在Q矩阵的左边在加上一个矩阵的左边在加上一个kk的单位矩阵，的单位矩阵，就形成了一个新矩阵就形成
15、了一个新矩阵G：3456012110110110111aaaaaaa Q34563456012110101011111aaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa也可以用矩阵形式来表示：也可以用矩阵形式来表示：或表示成为：或表示成为：1101000101010001100101110001QIGk这里这里G称为生成矩阵，利用它可以产生整个码组：称为生成矩阵，利用它可以产生整个码组：GGMA3456aaaa则接收端利用接收到的码组则接收端利用接收到的码组B计算校正子：计算校正子：S=BH
16、T=(A+E)HT=AHT+EHT=EHT 因此，校正子仅与因此，校正子仅与E有关，即错误图样与校正子之间有确定有关，即错误图样与校正子之间有确定的关系。的关系。120120120nnnnnnbbbaaaeeeBAEiiiiiababe107.3.3 校验子校验子S 设发送组码设发送组码A，在传输过程中有可能出现误码，这时接收，在传输过程中有可能出现误码，这时接收到的码组为到的码组为B。则收发码组之差为：。则收发码组之差为：其中：其中：7.3.4 7.3.4 汉明码汉明码 汉明码是一种能够纠正单个错误的线性分组码。它有以下汉明码是一种能够纠正单个错误的线性分组码。它有以下特点：特点：（1）最小码距）最小码距dmin3，可纠正一位错误；，可纠正一位错误；（2）码长码长n与监督元个数与监督元个数r之间满足关系式：之间满足关系式：。通常二进制汉明码可以表示为：通常二进制汉明码可以表示为：12 rn()2121rrnkr，（，）（7 7，4 4）系统汉明码的编码器和译码器电路：）系统汉明码的编码器和译码器电路：7.4 循环码循环码 循环码是线性分组码的一个重要子集，循环码是线性分组码的一个重要
