第7章 差错控制编码.ppt

第第7 7章章 差错控制编码差错控制编码 Ø7.17.1 引言引言 Ø7.27.2 常用简单分组码常用简单分组码 Ø7.37.3 线性分组码线性分组码 Ø7.47.4 循环码循环码 Ø7.57.5 卷积码卷积码 Ø7.7.6 6 m m 序列序列8/8/20247.17.1 引言引言7.1.1 7.1.1 信源编码与信道编码的基本概念信源编码与信道编码的基本概念 在数字通信系统中，为了提高数字信号传输的有效性而采在数字通信系统中，为了提高数字信号传输的有效性而采取的编码称为信源编码；为了提高数字通信的可靠性而采取取的编码称为信源编码；为了提高数字通信的可靠性而采取的编码称为信道编码的编码称为信道编码8/8/20242 2、信道编码（差错控制编码）、信道编码（差错控制编码） 差错控制编码是在信息序列上附加上一些监督码元，利用差错控制编码是在信息序列上附加上一些监督码元，利用这些冗余的码元，使原来不规律的或规律性不强的原始数字这些冗余的码元，使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号；差错控制译码则利用这些规律信号变为有规律的数字信号；差错控制译码则利用这些规律性来鉴别传输过程是否发生错误，或进而纠正错误。

性来鉴别传输过程是否发生错误，或进而纠正错误 8/8/20247.1.2 7.1.2 纠错编码的分类纠错编码的分类 （（1）按照信道编码的不同功能，可以分为）按照信道编码的不同功能，可以分为检错码检错码和和纠错码纠错码 （（2））按照信息码元和监督码元之间的检验关系，可以将它分按照信息码元和监督码元之间的检验关系，可以将它分为为线性线性码码和和非线性码非线性码 （（3））按照信息码元和监督码元之间的约束方式不同，可以将按照信息码元和监督码元之间的约束方式不同，可以将它分为它分为分组码分组码和和卷积码卷积码 （（4））按照信息码元在编码后是否保持原来的形式，可以将它按照信息码元在编码后是否保持原来的形式，可以将它分为分为系统码系统码和和非系统码非系统码 （（5）按照纠正错误的类型不同，可以将它分为）按照纠正错误的类型不同，可以将它分为纠正随机错误纠正随机错误码码和和纠正突发错误码纠正突发错误码 （（6）按照信道编码所采用的数学方法不同，可以将它分为）按照信道编码所采用的数学方法不同，可以将它分为代代数码数码、、几何码几何码和和算术码算术码 随着数字通信系统的发展，可以将信道编码器和调制器统一随着数字通信系统的发展，可以将信道编码器和调制器统一起来综合设计，这就是所谓的起来综合设计，这就是所谓的网格编码调制网格编码调制。

8/8/20247.1.2 7.1.2 差错控制方式差错控制方式8/8/2024检错重发（检错重发（ARQ））的的优点优点主要表现在：主要表现在： （（1）只需要少量的冗余码，就可以得到极低的输出误码率；）只需要少量的冗余码，就可以得到极低的输出误码率； （（2））有一定的自适应能力；有一定的自适应能力；某些某些不足不足主要表现在：主要表现在： （（1）需要反向信道，故不能用于单向传输系统，并且实现重发）需要反向信道，故不能用于单向传输系统，并且实现重发控制比较复杂；控制比较复杂； （（2）通信效率低，不适合严格实时传输系统通信效率低，不适合严格实时传输系统 混合纠错方式是前向纠错方式和检错重发方式的结合混合纠错方式是前向纠错方式和检错重发方式的结合 检错重发方式：检错重发方式：8/8/20247.1.2 7.1.2 纠错编码的基本原理纠错编码的基本原理 信道编码的基本概念：信道编码的基本概念： 码长：码长：码字中码元的数目；码字中码元的数目； 码重：码重：码字中非码字中非0数字的数目；数字的数目； 码码距距：：两两个个等等长长码码字字之之间间对对应应位位不不同同的的数数目目，，有有时时也也称称作这两个码字的汉明距离；作这两个码字的汉明距离； 最小码距：最小码距：在码字集合中全体码字之间距离的最小数值。

在码字集合中全体码字之间距离的最小数值 码率：码率：信息位信息位k k 与码长与码长n之比；之比； 编编码码效效率率：：在在给给定定误误码码率率要要求求下下，，非非编编码码系系统统与与编编码码系系 统的性噪比之比统的性噪比之比 纠错码的抗干扰能力完全取决于许用码字之间的距离，码纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强8/8/2024分组码的最小汉明距离分组码的最小汉明距离d0与检错和纠错能力之间满足下列关系：与检错和纠错能力之间满足下列关系： （（1）当码字用于检测错误时，如果要）当码字用于检测错误时，如果要检测检测e个错误个错误，则，则 d0 ≥ e+1 （（2））当码字用于纠正错误时，如果要当码字用于纠正错误时，如果要纠正纠正t个错误个错误，则，则 d0 ≥ 2t+1 （（3））若码字用于若码字用于纠纠t个错误个错误，，同时检同时检e个错误个错误时（时（e>t），），则则 d0≥ t+e+1 编码效率编码效率Rc可以用下式表示：可以用下式表示：8/8/20247.27.2 常用简单分组码常用简单分组码 7.2.1 7.2.1 奇偶监督码奇偶监督码 可以表示成为（可以表示成为（n，，n-1）。

如果是如果是奇监督码奇监督码，在附加，在附加上一个监督元以后，码长为上一个监督元以后，码长为n的码字中的码字中““1””的个数为奇的个数为奇数个；如果是数个；如果是偶监督码偶监督码，在附加上一个监督元以后，码，在附加上一个监督元以后，码长为长为n的码字中的码字中““1””的个数为偶数个的个数为偶数个 an-1+an-2+…+…+a1+a0 = 0 8/8/2024奇奇偶偶监督码的编码可以用软件实现，也可用硬件电路实现监督码的编码可以用软件实现，也可用硬件电路实现如果码组如果码组B无错，无错，B＝＝A，则，则M＝＝0；；如果码组如果码组B有单个（或奇数有单个（或奇数个）错误，则个）错误，则M＝＝1 8/8/2024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二维奇偶监督码适于检测突发错码。

二维奇偶监督码不仅可二维奇偶监督码适于检测突发错码二维奇偶监督码不仅可用来检错，还可用来纠正一些错码用来检错，还可用来纠正一些错码8/8/20247.2.3 7.2.3 恒比码恒比码 恒比码又称等重码，该码的码字中恒比码又称等重码，该码的码字中1和和0的位数保持恒定的的位数保持恒定的比例具体情况见表比例具体情况见表8-3 目前我国电传通信中普遍采用目前我国电传通信中普遍采用3：：2码，国际上通用的码，国际上通用的ARQ电报通信系统中，采用电报通信系统中，采用3：：4码即码即7中取中取3码8/8/20247.37.3 线性分组码线性分组码 7.3.1 7.3.1 基本概念基本概念 分组码是一组固定长度的码组，可表示为（分组码是一组固定长度的码组，可表示为（n , k），），通常通常它用于前向纠错在编码时，它用于前向纠错在编码时，k个信息位被编为个信息位被编为n位码组长度，位码组长度，而而n-k个监督位的作用就是实现检错与纠错个监督位的作用就是实现检错与纠错 这样，一个这样，一个k比特信息的线性分组码可以映射到一个长度为比特信息的线性分组码可以映射到一个长度为n码组上。

码组上8/8/2024线性分组码的线性分组码的主要性质主要性质如下：如下： （（1）任意两许用码之和仍为一许用码，也就是说，线性分）任意两许用码之和仍为一许用码，也就是说，线性分组码具有封闭性；组码具有封闭性； （（2））码组间的最小码距等于非零码的最小码重码组间的最小码距等于非零码的最小码重 对对偶偶校校验验时时的的监监督督关关系系在在接接收收端端解解码码时时，，实实际际上上就就是是在在计算：计算： S = bn-1+bn-2+…+…+b1+b0 若若S＝＝0，，则无错；若则无错；若S＝＝1就认为有错就认为有错 8/8/2024例如例如r ≥ 3，，若取若取r = 3，则，则n = k+r = 7假设假设S3、、S2、、S1三位三位校正字码组与误码位置的关系如表校正字码组与误码位置的关系如表8-4根据表8-4，可以构，可以构成如下关系式：成如下关系式： 当当r个监督方程式计算得到的校正子有个监督方程式计算得到的校正子有r位，可以用来指示位，可以用来指示2r-1种误码图样种误码图样 如果希望用如果希望用r个监督位构造出个监督位构造出r个监督关系式来指示一位错码个监督关系式来指示一位错码的的n种可能，则要求：种可能，则要求：8/8/2024S1= a6+a5+a4+a2 , S2= a6+a5+a4+a2 , S3= a6+a4+a3+a0 进而得到进而得到下面的方程组形式：下面的方程组形式： 接收端收到每个码组后，计算出接收端收到每个码组后，计算出S3、、S2和和S1，，如不全为如不全为0，则可，则可按表按表8-4确定误码的位置，然后予以纠正。

不难看出，上述（确定误码的位置，然后予以纠正不难看出，上述（7，，4）码的最小码距）码的最小码距dmin＝＝38/8/2024上式可以记作：上式可以记作：HAT=0T或或AHT=0 ，，其中其中7.3.2 监督矩阵监督矩阵H和生成矩阵和生成矩阵G 将（将（7，，4）码的三个监督方程式可以重新改写为如下形式：）码的三个监督方程式可以重新改写为如下形式：8/8/2024这这时时Q = PT，，如如果果在在Q矩矩阵阵的的左左边边在在加加上上一一个个k××k的的单单位位矩矩阵阵，，就形成了一个新矩阵就形成了一个新矩阵G：： 也可以用矩阵形式来表示：也可以用矩阵形式来表示：或表示成为：或表示成为：8/8/2024这里这里G称为生成矩阵，利用它可以产生整个码组：称为生成矩阵，利用它可以产生整个码组：8/8/2024则接收端利用接收到的码组则接收端利用接收到的码组B计算校正子：计算校正子： S=BHT=(A+E)HT= AHT + EHT = EHT 因此，校正子仅与因此，校正子仅与E有关，即错误图样与校正子之间有确定有关，即错误图样与校正子之间有确定的关系 7.3.3 校验子校验子S 设发送组码设发送组码A，，在传输过程中有可能出现误码，这时接收在传输过程中有可能出现误码，这时接收到的码组为到的码组为B。

则收发码组之差为：则收发码组之差为：其中：其中：8/8/20247.3.4 7.3.4 汉明码汉明码 汉明码是一种能够纠正单个错误的线性分组码它有以下汉明码是一种能够纠正单个错误的线性分组码它有以下特点：特点： （（1）最小码距）最小码距dmin＝＝3，，可纠正一位错误；可纠正一位错误； （（2））码长码长n与监督元个数与监督元个数r之间满足关系式：之间满足关系式： 通常二进制汉明码可以表示为：通常二进制汉明码可以表示为： 8/8/2024（（7 7，，4 4）系统汉明码的编码器和译码器电路：）系统汉明码的编码器和译码器电路：8/8/20248/8/20247.4 循环码循环码 循环码是线性分组码的一个重要子集，循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码，它有许多是目前研究得最成熟的一类码，它有许多特殊的代数性质特殊的代数性质 7.4.1 循环码的特点循环码的特点 循环特性是指：循环码中任一许用码循环特性是指：循环码中任一许用码组经过循环移位后，所得到的码组仍然是组经过循环移位后，所得到的码组仍然是许用码组。

许用码组8/8/2024 为了利用代数理论研究循环码，可以将为了利用代数理论研究循环码，可以将码组用代数多项是来表示，这个多项式被称码组用代数多项是来表示，这个多项式被称为码多项式，为码多项式，对于于许用循用循环码A=(an-1 an-2 … a1 a0)，，可以将它的可以将它的码多多项式表示式表示为：： 若一个整数若一个整数m可以表示为可以表示为: : 则则在在模模n运运算算下下，，有有m≡≡p（（模模n）），，同同样样对对于多项式而言：于多项式而言：8/8/2024 则可以写为：则可以写为：F(x)≡≡R(x) （模（模N(x)） 在循环码中，若在循环码中，若A(x)是一个长为是一个长为n的许用的许用码组，则在按模码组，则在按模 运算运算下，亦是一个许用下，亦是一个许用码组例如，码组例如， 其对应的码组为其对应的码组为0101110，它正是表，它正是表8-7中第中第3码字8/8/20247.4.2 循环码的生成多项式和生成矩阵循环码的生成多项式和生成矩阵 循环码中次数最低的码多项式称为生成循环码中次数最低的码多项式称为生成多项式，用多项式，用g(x)表示。

可以证明生成多项式表示可以证明生成多项式g(x)具有以下特性：具有以下特性： （（1）） g(x)是一个常数项为是一个常数项为1的的 次次多项式；多项式； （（2）） g(x)是是 的一个因式；的一个因式； （（3））该循环码中其它码多项式都是该循环码中其它码多项式都是g(x)的倍式 8/8/2024 为了保证构成的生成矩阵为了保证构成的生成矩阵G的各行线性的各行线性不相关，通常用不相关，通常用g(x)来构造生成矩阵，来构造生成矩阵， 显然，上式不符合显然，上式不符合 形式，所以形式，所以此生成矩阵不是典型形式此生成矩阵不是典型形式 因此，一旦生成多项因此，一旦生成多项式式g(x)确定以后，该循环确定以后，该循环码的生成矩阵就可以确定码的生成矩阵就可以确定 8/8/2024 利用循环码的特点来确定监督矩阵利用循环码的特点来确定监督矩阵H：： 由于（由于（n,k））循环码中循环码中g(x)是是xn +1的因式，的因式，因此可令：因此可令： 监督矩阵表示为：监督矩阵表示为：8/8/2024 7.4.3 循环码的编、译码方法循环码的编、译码方法 1、编码过程、编码过程 首先需要根据给定循环码的参数确定生首先需要根据给定循环码的参数确定生成多项式成多项式g(x) ，，然后，利用循环码的编码特然后，利用循环码的编码特点，即所有循环码多项式点，即所有循环码多项式A(x)都可以被都可以被g(x)整整除，来定义生成多项式除，来定义生成多项式A(x)。

下面就将以上下面就将以上各步处理加以解释：各步处理加以解释： （（1））用用xn-k乘乘m(x)这一运算实际上是这一运算实际上是把信息码后附加上（把信息码后附加上（n-k））个个““0”” 8/8/2024 （（2））求求r(x)由于循环码多项式由于循环码多项式A(x)都可都可以被以被g(x)整除，也就是：整除，也就是：上式也等效于：上式也等效于：这样我们就得到了这样我们就得到了r(x) （（3））编码输出系统循环码多项式编码输出系统循环码多项式A(x)为：为： 8/8/2024 上述三步编码过程，在硬件实现时，可上述三步编码过程，在硬件实现时，可以利用除法电路来实现以利用除法电路来实现 2、译码过程、译码过程 循环码的译码可以分三步进行：循环码的译码可以分三步进行： （（1）由接收到的码多项式）由接收到的码多项式B(x)计算校正计算校正子（伴随式）多项式子（伴随式）多项式S(x)；； 8/8/2024 （（2））由校正子由校正子S(x)确定错误图样确定错误图样E(x)；； （（3））将错误图样将错误图样E(x)与与B(x)相加，纠正相加，纠正错误。

错误8/8/20247.5 卷积码卷积码 卷积码中编码后的卷积码中编码后的n个码元不仅与当前个码元不仅与当前段的段的k个信息有关，而且也与前面（个信息有关，而且也与前面（N-1））段的信息有关，编码过程中相互关联的码段的信息有关，编码过程中相互关联的码元为元为nN个因此，这个因此，这N段时间内的码元数段时间内的码元数目目nN通常被称为这种码的约束长度通常被称为这种码的约束长度 由于与前面由于与前面m段规定时间内的信息位段规定时间内的信息位有关，这里的有关，这里的m＝＝N-1通常用（通常用（n，，k，，m））表示卷积码表示卷积码 8/8/2024 例如：例如：卷积码的卷积码的n = 2，，k = 1，，m = 2，，因因此，它的约束长度此，它的约束长度nN = n×(×(m+1) ) = 2××3 = 6 8/8/2024 假如输入的信息为假如输入的信息为D = [11010]，，为了使信为了使信息息D全部通过移位寄存器，还必须在信息位后全部通过移位寄存器，还必须在信息位后面加面加3个零表8-9列出了对信息列出了对信息D进行卷积编进行卷积编码时的状态。

码时的状态 描述卷积码的方法：图解表示和解析表示描述卷积码的方法：图解表示和解析表示 卷积码的译码方法可分为代数译码和概率卷积码的译码方法可分为代数译码和概率译码两大类译码两大类 8/8/20248/8/20247.6 m序列序列确定序列：确定序列： 可以预定确定并且可以重复实现的序列可以预定确定并且可以重复实现的序列随机序列：随机序列： 既不能预定确定又不能重复实现的序列既不能预定确定又不能重复实现的序列8/8/2024平衡特性：平衡特性： 序列的每个周期内序列的每个周期内““0”0”和和““1”1”的个数至多差的个数至多差一个一个游程特分特性：游程特分特性： 序列中取值相同的相连的元素称为一个游程序列中取值相同的相连的元素称为一个游程相关特性：相关特性： 将伪随机序列的一个周期与其任意次的循环移将伪随机序列的一个周期与其任意次的循环移位的序列逐位比较，相同的位数与不同的为数至位的序列逐位比较，相同的位数与不同的为数至多相差多相差1(1(说明序列不相关说明序列不相关) )8/8/2024。