1第九章第九章 差错控制编码差错控制编码主要内容：主要内容：纠错编码的原理纠错编码的原理线性分组码线性分组码循环码循环码卷积码卷积码（数字通信特有）（数字通信特有）29.1 9.1 引引 言言 信号在信道中受到干扰信号在信道中受到干扰干扰种类：乘性干扰种类：乘性码间干扰；克服方法：均衡器码间干扰；克服方法：均衡器 加性干扰的类型：加性干扰的类型：突发突发型型错码错码：错码成串集中出现；：错码成串集中出现； 原因：脉冲干扰，衰落原因：脉冲干扰，衰落混合型错码混合型错码：加性加性错码；克服方法：差错控制编码错码；克服方法：差错控制编码随机型错码随机型错码：错码是随机出现的，相互间统计独立：错码是随机出现的，相互间统计独立 原因：白噪声。原因：白噪声。提高信号抗加性干扰的能力提高信号抗加性干扰的能力3速率速率( b/s )线路类别线路类别误码率标准误码率标准300电话交换线电话交换线专用线专用线10- - 45510- - 5600电话交换线电话交换线专用线专用线10- - 35510- - 51200电话交换线电话交换线专用线专用线10- - 55510- - 52400专用线专用线10- - 5CCITT 建议的误码率标准建议的误码率标准检错重发、检错重发、前向纠错、反馈校验、检错删除前向纠错、反馈校验、检错删除 差错控制的方法差错控制的方法4检错重发：如接收端检测出错码，通知发端重发，直到检错重发：如接收端检测出错码，通知发端重发，直到 (ARQ) 接收正确为止。此方法只能判断是否有错码，接收正确为止。此方法只能判断是否有错码， 不能判断具体的错码位置。所以，只能检错不不能判断具体的错码位置。所以，只能检错不 能纠错，且需要能纠错，且需要双向双向通道。通道。前向纠错：前向纠错：收端能检测出错码，并可以确定错码的位收端能检测出错码，并可以确定错码的位 (FEC) 置，并予纠正。此方法只需要置，并予纠正。此方法只需要单向单向通道。实通道。实 时性好，但设备复杂。时性好，但设备复杂。反反馈馈校校验验：接接收收端端将将收收到到的的信信号号原原封封不不动动的的发发回回发发端端，由由发发端端将将其其与与原原发发信信号号相相比比较较，如如果果有有错错则则重重发发。这种方法需这种方法需双向双向通道，效率低，设备简单通道，效率低，设备简单检错删除：如：重复发送的的遥测信号。检错删除：如：重复发送的的遥测信号。5自动请求重发系统自动请求重发系统（ARQ） 工作过程：工作过程：2 2）重重发发控控制制器器收收到到重重发发命命令令时时，控控制制输输入入缓缓冲冲储储存存器器重发一次当前码组，否则发送后一码组。重发一次当前码组，否则发送后一码组。1 1）收收端端解解码码器器检检测测出出错错码码时时由由指指令令发发生生器器产产生生重重发发命命令令传传给给发发端端，同同时时发发出出删删除除命命令令，删删除除输输出出缓缓冲冲器器内容。内容。重发控制重发控制信信源源双双向向通通道道指令发生器指令发生器解码器解码器输出缓存器输出缓存器收收信信者者错误时删除错误时删除编码编码输入缓存器输入缓存器6优点：优点：1 1）监督码少）监督码少; ; 2 2）对各种信道有一定的适应能力；）对各种信道有一定的适应能力； 3 3）成本及复杂性低。）成本及复杂性低。缺点：缺点：1 1）需要双向通道；）需要双向通道； 2 2）干干扰扰大大时时系系统统可可能能处处于于重重发发循循环中，效率降低；环中，效率降低； 3 3）实时性差。）实时性差。7在在信信息息码码序序列列中中加加监监督督码码元元，监监督督码码和和信信息息码码之之间间存存在在一一种种逻逻辑辑关关系系。因因此此，收收端端可可以以利利用用这这种种逻逻辑辑关系发现或纠正存在的错码。关系发现或纠正存在的错码。一一般般来来说说，监监督督码码元元越越多多，检检、纠纠错错能能力力越越强强。用降低传输速率换取传输可靠性的提高。用降低传输速率换取传输可靠性的提高。不同的编码方法，有不同的检错或纠错能力。不同的编码方法，有不同的检错或纠错能力。目标：监督码元要少，目标：监督码元要少，检、纠错能力要强。检、纠错能力要强。9.2 9.2 纠错编码的基本原理纠错编码的基本原理8例：例：表示天气表示天气信源信源发送信息码发送信息码晴晴0 0云云0 1阴阴1 0雨雨1 1接收信息码接收信息码 判别判别(错误错误)0 1云云11 雨雨0 0晴晴1 0阴阴结论：结论：虽然接收码组有错，但接收端无法识别。虽然接收码组有错，但接收端无法识别。错错 1 位位9信源信源发送信息码发送信息码监督码监督码晴晴0 00云云0 11阴阴1 01雨雨1 10接收码组接收码组判别判别001、010、100010、001、111100、111、001111、100、010增加一位监督码增加一位监督码错错 1 位位接收码组接收码组判别判别(错误错误)011、110、101 云、雨、阴云、雨、阴000、101、110 晴、阴、雨晴、阴、雨110、000、011 雨、晴、云雨、晴、云101、000、011 阴、晴、云阴、晴、云错错 2 位位结论：可以检测出结论：可以检测出 1 位错码，但不能纠错。位错码，但不能纠错。禁用码组：非禁用码组：非信息信息码组码组许用码组：有效许用码组：有效信息信息码组码组码距码距10结论：结论：能纠正能纠正 1 位错码位错码，或，或检测出检测出 2 位错码位错码。信源信源 发送信息码发送信息码 监督码监督码晴晴0 0000云云0 1011阴阴1 0101雨雨1 1110接收码组接收码组判别判别00001,00010,00100,01000,10000晴晴01010,01001,01111,00011,11011云云10100,10111,10001,11101,00101阴阴11111,11100,11010,10110,01110雨雨错错 1 位位接收码组接收码组判别判别11000,10100,10010,10001,01100,01010,01001,00110,00101,0001110011,11111,11001,11010,00111,00001,00010,01101,01110,0101001101,00001,00111,00110,11001,11110,11101,10011,10000,1010000110,01010,01100,01111,10010,10100,10111,11000,11011,11111错错 2 位位增加三位监督码增加三位监督码码距关系码距关系11特特征征：分分组组码码中中的的监监督督码码元元仅仅监监督督本本码码组组中的信息码元。中的信息码元。分分组组码码定定义义：将将信信息息码码分分组组，为为每每组组信信息息码码后附加若干监督码元形成的码集合。后附加若干监督码元形成的码集合。 分组码分组码 k ： 码组中码组中信息码元信息码元的数目。的数目。 n ： 码组的总位数，又称为码组的总位数，又称为码组长度码组长度。 r = n - - k ：码组中：码组中监督码元监督码元的数目。的数目。编码效率：编码效率：k/n；冗余度：；冗余度：(n-k)/k符号：符号：( n , k )12结构结构 码长码长 n = k + r k 个信息位个信息位 r 个监督位个监督位码组重量码组重量：码组中：码组中 “1 ” 的数目。的数目。an-1an-2arar-1a0码距码距 d ：两个码组对应位上不同的码元个数，：两个码组对应位上不同的码元个数，称为称为汉明距离汉明距离。最小码距最小码距 d0 ：码集合中任意两两码组间距离：码集合中任意两两码组间距离的最小值。的最小值。天气编码举例天气编码举例13 检测检测 e 个错码，要求最小码距个错码，要求最小码距 纠正纠正 t 个错码，要求最小码距个错码，要求最小码距 纠正纠正 t 个错码、同时检测个错码、同时检测 e 个错码，要求最小码距个错码，要求最小码距 码距与码集合检、纠错能力的关系码距与码集合检、纠错能力的关系AB例：例： A = ( 00000 ) 、B = ( 11111 )， d0 = 5 结论：结论：e = 4 或或 t = 2 或或 t = 1 、 e = 3d = 1d = 2d = 3天气编码举例天气编码举例14 奇数监督码奇数监督码: :使码组中使码组中“1” 的个数为奇数的个数为奇数 偶数监督码偶数监督码: :使码组中使码组中“1” 的个数为偶数的个数为偶数码距为码距为2 2，能检，能检测奇数个错码测奇数个错码二维奇偶监督码（矩阵码）二维奇偶监督码（矩阵码）生成规则：生成规则： 许用码组写成一行（包括信息码和许用码组写成一行（包括信息码和1 位监位监督码），设共有督码），设共有m 行。第行。第 m+1 行为按列增加的行为按列增加的监督码。（构成监督码行）监督码。（构成监督码行） 1 1、奇偶监督码奇偶监督码一维奇偶监督码：一维奇偶监督码： 1 位监督码；位监督码；9.3 9.3 常用的简单编码常用的简单编码常用常用an-1 an-2 a0=1an-1 an-2 a0=0161）设）设 和和 发生错码，按行无法检测出有错，而发生错码，按行无法检测出有错，而按列可检测。按列可检测。a2 a1 a00 0 00 1 11 0 11 1 00 0 0例例 二维偶数监督码二维偶数监督码通式通式突发性错码突发性错码2 2）能检测突发性错码；适用于突发信道。）能检测突发性错码；适用于突发信道。173）若仅一行有奇数个错码时，可通过列确定错码位置若仅一行有奇数个错码时，可通过列确定错码位置并纠正。并纠正。4）当当 同时出错，则按行按列均不能检测同时出错，则按行按列均不能检测 出有错。出有错。5）方阵码除了在行列上的错码都为偶数时，无法检测）方阵码除了在行列上的错码都为偶数时，无法检测外，其余均能检测。外，其余均能检测。上页上页182 2恒比码恒比码在在恒恒比比码码中中，每每个个码码组组均均含含有有相相同同数数目目的的“1 1”( (和和“0 0”) )。这这种种码码在在检检测测时时，只只要要判判断断接接收收码码组组中中“1 1”的数目是否正确，就能判断有无错误。的数目是否正确，就能判断有无错误。P286P286表表9-29-2中中的的保保护护电电码码，每每个个码码组组的的长长度度为为5 5，其其中中恒恒有有3 3个个“1 1”，称称为为5/35/3恒恒比比码码。用用于于我我国国的的汉汉字字电电传编码。传编码。从从5 5中中取取3 3的的组组合合数数C C3 35 5=5!/(3! =5!/(3! 2!)=102!)=10。这这1010种种许许用用码码组组恰恰好好可可用用来来表表示示1010个个阿阿拉拉伯伯数数字字。用用4 4位位阿阿拉拉伯伯数数字表示一个汉字。字表示一个汉字。在在无无线线电电报报通通信信中中，广广泛泛采采用用的的是是 7/37/3恒恒比比码码，这这种种码码组组中中总总是是有有3 3个个“1 1”。共共有有7!/(37!/(3！4!)=354!)=35种种许许用用码组，它们可用来代表码组，它们可用来代表2626个英文字母及其他控制符号个英文字母及其他控制符号。 19特征：特征：具有纠正具有纠正 1 位错码、检测位错码、检测 2 位和大部分位和大部分 2 位以上错码位以上错码的能力的能力定义：定义：信息码位数与监督码位数信息码位数与监督码位数相同相同 编码编码规则：规则： 1）当信息位中有）当信息位中有奇奇数个数个“1”时，监督位是信息位的重复时，监督位是信息位的重复2）当信息位中有）当信息位中有偶偶数个数个“1”时，监督位是信息位的反码时，监督位是信息位的反码1 0 0 0 1 例：例：若信息码为若信息码为 1 1 0 0 1 3 3、 正反码正反码 则正反码为则正反码为 1 1 0 0 1 1 1 0 0 11 0 0 0 1 0 1 1 1 01）将接收码组中信息码和监督码对应按位模将接收码组中信息码和监督码对应按位模2 加，得加，得合成码组合成码组2）根据接收码组中信息码含）根据接收码组中信息码含 “1” 的奇偶情况，的奇偶情况，由合成码组生成由合成码组生成校验码组校验码组 3）根据校验码组的组成，依表判断错码情况，并予检错与纠错）根据校验码组的组成，依表判断错码情况，并予检错与纠错译码译码规则：规则：“1”为奇为奇 校验校验 = 合成合成“1”为偶为偶 校验校验 =20例：发例：发 1 1 0 0 1 1 1 0 0 1 1）收无错）收无错 信息码中含奇数个信息码中含奇数个“1”2）收有错、为）收有错、为 1 0 0 0 1 1 1 0 0 1合成码组合成码组= 1 1 0 0 1 1 1 0 0 10 0 0 0 0译码判决：译码判决：校验码组校验码组错码情况错码情况 1 全全 “0” 无错码无错码 24 个个“1”1 个个“0” 信息码中有一位错码，信息码中有一位错码，对应校验码组中的对应校验码组中的“0” 的位置的位置 34 个个“0”1 个个“1” 监督码中有一位错码，监督码中有一位错码，对应校验码组中的对应校验码组中的“1” 的位置的位置 4 其他组成其他组成 错码多于错码多于 1 个个 校验码组校验码组 = 合成码组合成码组 = 00000判断接收无错码判断接收无错码合成码组合成码组= 1 0 0 0 1 1 1 0 0 10 1 0 0 0 信息码中含偶数个信息码中含偶数个“1”查表知信息码第二位错查表知信息码第二位错特征：特征：编码效率低编码效率低219.4 9.4 线性分组码线性分组码汉明码的编码原理汉明码的编码原理一般线性分组码的编码原理一般线性分组码的编码原理（可以纠错）（可以纠错）线性码：监督码和信息码之间的关系是线性关系线性码：监督码和信息码之间的关系是线性关系22分析偶数监督码，寻找逻辑组合分析偶数监督码，寻找逻辑组合 监督方程监督方程 所以解码就是要计算所以解码就是要计算0 无错无错1 有错有错s =只能表示出错只能表示出错不能描述错码位置不能描述错码位置一位监督码对一位监督码对应一个监督方应一个监督方程程，即，即对应一对应一个校正子个校正子结论：若增加监督码元，建立多个监督方程，多个结论：若增加监督码元，建立多个监督方程，多个校正子就能形成逻辑组合描述错码位置。校正子就能形成逻辑组合描述错码位置。r位监督码对应位监督码对应r个校正子，就有个校正子，就有2r 种组合，用其中种组合，用其中一种组合表示无错，其余一种组合表示无错，其余2r-1种组合表示错码的位置。种组合表示错码的位置。9.4.1 9.4.1 汉明码汉明码s=an-1 an-2 a0an-1 an-2 a0=0校正子校正子 23确定监督关系表确定监督关系表建立监督方程建立监督方程建立编码方程建立编码方程如果只错一位，分组码如果只错一位，分组码(n,k)中的错码有中的错码有n个可能的位个可能的位置置 ，要用要用r 位监督码表示这位监督码表示这n 个错码的位置，个错码的位置， 为提高编码效率，为提高编码效率， r 取最小值取最小值例：例：已知已知( 7 , 4 )码，码，r = 3 共有共有3个监督方程，个监督方程， 构成构成 3个校正子个校正子 S1 S2 S3S1 S2 S30 0 0无错无错0 0 1a0 错错0 1 0a1 错错1 0 0a2 错错1 1 0a3 错错0 1 1a4 错错1 1 1a5 错错1 0 1a6 错错只纠正一位错码只纠正一位错码监督码出错只与监督码出错只与一个校正子有关一个校正子有关24求码组集合求码组集合 k = 4，信息码组有信息码组有 16 个个a6 a5 a4 a3a2 a1 a00 0 0 00 0 00 0 0 11 1 00 0 1 00 1 10 0 1 11 0 1.1 1 0 00 1 01 1 0 11 0 01 1 1 00 0 11 1 1 11 1 1能能纠纠正正一一位位错错码码，且且2r-1=n的的线线性分组码，称为性分组码，称为汉明码汉明码。其编码效率为其编码效率为k/n=(2r-1-r)/(2r-1)=1-r/(2r-1)=1-r/n当当n很很大大时时，则则编编码码效效率率接接近近1。可可见见，汉汉明明码码是是一种高效码。一种高效码。25 汉明码的监督方程为汉明码的监督方程为用用矩阵表示矩阵表示9.4.2 9.4.2 一般线性分组码的编码原理一般线性分组码的编码原理记为：记为：监督矩阵监督矩阵码组向量码组向量当当 称称 H 为典型监督矩阵为典型监督矩阵（含单位阵）（含单位阵）错误图样错误图样26根据监督方程确定了根据监督方程确定了编码方程编码方程两边同取转置两边同取转置构造构造生成矩阵生成矩阵G 为典型生成矩阵为典型生成矩阵 编码矩阵方程编码矩阵方程特点：信息位不变，监督位附加于其后。特点：信息位不变，监督位附加于其后。由典型生成矩阵得出的码组由典型生成矩阵得出的码组 A是是系统码系统码27生成矩阵生成矩阵G 中中每行均为一个码组，且线性无关每行均为一个码组，且线性无关若能找到若能找到k个线性无关的已知码组，就能构成矩阵个线性无关的已知码组，就能构成矩阵G。 循环码生成矩阵循环码生成矩阵28译码运算，当译码运算，当S 为校正子。说明为校正子。说明 S 与与E 有确定的线性关系有确定的线性关系若若 E 的数目有限的数目有限，能与能与 S 一一对应，一一对应，则则 说明说明 S 能描述错码的位置，具有纠错能力。能描述错码的位置，具有纠错能力。令令 发码组为发码组为 A、收码组为、收码组为 B 错码图样错码图样 E = B- - A错误图样错误图样收发码组的关系收发码组的关系0 无错无错1 有错有错 令令 B =E + + A29发码组发码组 A = 1 1 0 0 0 1 0收码组收码组 B = 1 0 0 0 0 1 0 译码运算译码运算例：例： ( 7 , 4 )汉明码汉明码, S1 S2 S30 0 0无错无错0 0 1a0 错错0 1 0a1 错错1 0 0a2 错错1 1 0a3 错错0 1 1a4 错错1 1 1a5 错错1 0 1a6 错错 a5 错错含义：含义：错码图样错码图样 E =（0 1 0 0 0 0 0） 只有一位错码只有一位错码30线性码中任意线性码中任意两个码组之和两个码组之和仍为这种码中的一个码组仍为这种码中的一个码组证：证： 设设 A1 、 A2 为线性码中两个许用码组为线性码中两个许用码组两式相加两式相加是许用码组是许用码组推广：推广： 1）两个码组间的）两个码组间的距离距离必是另一码组的必是另一码组的重量重量2）除）除 全全0 码组之外，编码的码组之外，编码的最小码重最小码重是码集是码集合的合的最小码距最小码距。线性分组码的性质：线性分组码的性质：封闭性封闭性3)线性分组码中必有全线性分组码中必有全0码；码；（信息码全（信息码全0，监督码全，监督码全0）319.5 9.5 循环码循环码 9.5.1 9.5.1 码多项式码多项式9.5.2 9.5.2 循环码的特性循环码的特性9.5.3 9.5.3 循环码的编码方法循环码的编码方法 循循环环码码是是线线性性分分组组码码中中一一种种重重要要的的编编码码。它它是是在在严严密密的的代代数数理理论论基基础础上上建建立立起起来来的的。其其编编码码和和解解码码不不太太复复杂杂，但但检检(纠纠)错错的的能能力力较较强强。循循环环码码除除了了具具有有线线性性码的一般性质外，还具有循环性，见表码的一般性质外，还具有循环性，见表11-5。32码多项式的模运算：码多项式的模运算：9.5.1 9.5.1 码多项式码多项式码多项式码多项式以码组中各码元为系数的多项式以码组中各码元为系数的多项式T( x ) = an-1 x n-1 + an-2 x n-2 + . + a1 x + a0设设 多项式多项式 F(x)、除式为、除式为 N(x)注：注：多多项式按模项式按模 N(x) 运算过程中，其系数均为运算过程中，其系数均为模模2 运算。运算。x 仅为码元位置的标记仅为码元位置的标记模模 N( x )； R( x )：余式：余式例：例：( 110 0101 ) T( x ) = x 6 + x 5 + x 2 + 133例：例：解：解：记为：记为：余式余式系数为二进制，只能取系数为二进制，只能取0或或1，二进制的加减都是一样的，二进制的加减都是一样的34 用用码码多多项项式式的的运运算算来来表表示示：若若T(x)对对应应一一个个码码长长为为 n 的的许许用用码码组组，则则x i T(x)按按模模x n+1运运算算后后余余式式T(x)仍仍为为许用码组许用码组。证：证： 令令 T(x)的系数是的系数是T(x)中系数向左循环移位中系数向左循环移位 i 次的结果次的结果9.5.2 9.5.2 循环码的特性循环码的特性 编码中任意一个码组，左移或右移一位得到的新码编码中任意一个码组，左移或右移一位得到的新码组必是该码集合中另一码组。组必是该码集合中另一码组。生成多项式生成多项式 T( x ) = an-1 x n-1 + an-2 x n-2 + . + a1 x + a0 x iT( x ) = an-1 x n-1+i + . + an-1-i x n-1+ . + a0 xix iT(x) an-1-i x n-1 +. + a0 x i + an-1 x i-1 + . +an-i35例：例： ( 7 , 3 )循环码循环码, 码组为码组为( 110 0101 )，验证验证 x 3 T( x ) 按模按模 x 7 +1 运算后余式仍是一个许用码组运算后余式仍是一个许用码组 。 解：解： T( x ) = an-1 x n-1 + an-2 x n-2 + . + a1 x + a0 T( x ) = x 6 + x 5 + x 2 + 1 x 3 T( x ) = x 9 + x 8 + x 5 + x 3 余式余式T(x) 对应码组为对应码组为(0101110) 是是T(x)码组循环左移三位的结果码组循环左移三位的结果369.5.3 9.5.3 循环码的编码方法循环码的编码方法思路：思路：由码的循环性，由码的循环性，可知找到一个码多项式，可知找到一个码多项式，就能就能得到其他的码多项式得到其他的码多项式一一个个(n,k)码码有有2k个个不不同同码码组组。用用g(x)表表示示其其中中前前(k-1)位位皆皆为为“0”的的码码组组。则则g(x)，xg(x)，x2g(x)，xk-1g(x)都都是是该该循循环环码码的的码码组组，而而且且这这k个个码码组组是是线线性性无无关关的，用它们可以构成此循环码的的，用它们可以构成此循环码的生成矩阵生成矩阵G。循环码的生成矩阵循环码的生成矩阵 Gk是是一一个个码码组组中中信信息息码的长度码的长度37对对g(x)的说明：的说明： 是该循环码中是该循环码中阶数最低阶数最低的码多项式。的码多项式。 在在循循环环码码中中除除全全“0”码码组组外外，即即连连“0”的的长长度度最最多多只只能能有有(k-1)位位。否否则则在在经经过过若若干干次次循循环环移移位位后后将将得得到到一一个个k个个信信息息位位全全为为“0”，但但监监督督位位不不全全为为“0”的的码码组。这显然是不可能的。组。这显然是不可能的。 g(x)必须是必须是一个常数项不为一个常数项不为“0”的的(n-k)次多项式次多项式。 而而且且还还是是唯唯一一的的。因因为为如如果果有有两两个个，则则由由码码的的封封闭闭性性，把把这这两两个个相相加加也也应应该该是是一一个个码码组组，且且此此码码组组多多项项式式的的次次数数将将小小于于(n-k)，即即连连续续“0”的的个个数数多多于于(n-k)，这这是不可能的。是不可能的。 我我们们称称这这唯唯一一的的(n-k)次次多多项项式式g(x)为为码码的的生生成成多多项项式式。一旦确定一旦确定g(x)，则整个，则整个(n-k)循环码就被确定了。循环码就被确定了。38(7,3)循循环码的的码组:T(x)=a6a5a4G(x) =a6a5a4 =(a6 x2+a5 x+a4)g(x) 这表明，所有表明，所有码多多项式式T(x)都是都是g(x)倍式倍式，而且任一，而且任一次数不大于次数不大于(k-1)的多的多项式乘式乘g(x)都是都是码多多项式。式。在表在表11-5中找出生成多中找出生成多项式式所有的信息码组合所有的信息码组合39码生成多项式码生成多项式 g( x ) 的求解的求解定理：定理：循环码循环码( n , k ) 的的 g( x ) 是是 xn +1 的一个的一个( n- - k ) 次次 因子。因子。证：证： 任意一个码多项式任意一个码多项式 T( x ) 都是都是 g( x ) 倍式倍式令令 T( x ) = h( x ) g( x ) 而而 x k g( x ) = x n + 1 + T( x ) x n +1 = x k g( x ) + T( x ) = x k g( x ) + h( x ) g( x ) = x k + h( x ) g( x ) g(x)为为一一(n-k)次次多多项项式式，故故xkg(x)为一为一n次多项式。次多项式。余余式式T(x) 也也是是一一个个许许用用码组。码组。按模运算按模运算40例：已知例：已知 (7,3) 循环码，求码组集合循环码，求码组集合 、监督矩阵、监督矩阵 H 。解：解： n = 7 x7 + 1 = ( x +1 )( x 6 + x 5+ x 4 + x 3 + x 2+ x + 1 ) = ( x +1 )( x 3 + x 2+ 1 )( x 3 + x + 1 ) g1( x ) = ( x +1 )( x 3 + x 2+ 1 ) = x 4 + x 2+ x + 1 g2( x ) = ( x +1 )( x 3 + x + 1 ) = x 4 + x 3+ x 2 + 1 取取 g( x ) = g1( x ) = x 4 + x 2+ x + 1 互逆互逆(生成多项式的逆多项式也是生成多项式生成多项式的逆多项式也是生成多项式)表表11-5（2）41 A = ( a6 a5 a4 a3 a2 a1 a0 ) a6 a5 a4 a6 a5 a4 a3 a2 a1 a0 0 0 0 0 0 0 0 0 0 00 0 1 1） 0 0 1 0 1 1 10 1 0 2） 0 1 0 1 1 1 00 1 1 3） 0 1 1 1 0 0 11 0 0 5） 1 0 1 1 1 0 01 0 1 4） 1 0 0 1 0 1 11 1 0 7） 1 1 1 0 0 1 01 1 1 6） 1 1 0 0 1 0 1监督方程：监督方程： d0 = 3 , t = 1 非典型非典型非系统非系统429.5.4 循环码的编、解电路循环码的编、解电路1、循环码的编码电路、循环码的编码电路设设m(x)为信息码多项式，其次数小于为信息码多项式，其次数小于k。 (1)用用xn-k乘乘m(x)。得到的得到的xn-km(x)的次数必小于的次数必小于n。也。也就是把信息码后附加上就是把信息码后附加上(n-k)个个“0”，这是监督位的，这是监督位的位置。位置。 (2)用用g(x)除除xn-km(x): xn-km(x)/ /g(x)=Q(x)r(x)得到得到余式余式r(x) 。 (3) T(x)=xn-km(x)+r(x)由于由于xn-km(x)+r(x)=Q(x)g(x)，能被，能被g(x)整除，因此整除，因此T(x)必为一码多项式必为一码多项式。 余式余式r(x) 就是就是监督码多项式监督码多项式。43上述三步运算，可由除法电路来实现。上述三步运算，可由除法电路来实现。 ( (移存器的反馈抽头取决于生成多项式移存器的反馈抽头取决于生成多项式) ) 44452循环码的解码电路循环码的解码电路 接收端解码的要求有两个：检错和纠错。接收端解码的要求有两个：检错和纠错。 用于检错的解码电路比较简单。用于检错的解码电路比较简单。 把接收码组把接收码组R(x)除以除以生成多项式生成多项式g(x)。 当当传传输输中中未未发发生生错错误误时时，接接收收码码组组与与发发送送码码组组相相同同，即即R(x)=T(x)，故接收码组，故接收码组R(x)必定必定能被能被g(x)整除整除 若若码码组组在在传传输输中中发发生生错错误误，则则R(x)T(x)，R(x)被被g(x)除时可能除时可能除不尽除不尽而有余项，即有而有余项，即有 R(x)/ /g(x)=Q(x)+r(x)/ /g(x) 当当错错码码数数超超过过了了这这种种编编码码的的检检错错能能力力时时，有有错错码码的的接接收收码码组组也也可可能能被被g(x)整整除除，这这时时的的错错码码就就不不能能检检出出了。这种错误称为了。这种错误称为不可检错误不可检错误。4647 用用于于纠纠错错的的解解码码方方法法比比较较复复杂杂。要要求求每每个个可可纠纠正正的的错错误误图图样样必必须须与与一一个个特特定定余余式式有有一一一一对对应应关关系系。可可按按下下述步骤进行：述步骤进行： (1)用用生生成成多多项项式式g(x)除除接接收收码码组组R(x)=T(x)+E(x)，得得出出余式余式r(x)； (2)按按余余式式r(x)用用查查表表的的方方法法或或通通过过某某种种运运算算得得到到错错误误图样图样E(x)。 (3)从从R(x)中中减减去去E(x)，便便得得到到已已纠纠正正错错误误的的原原发发送送码码组组T(x)； 上上述述运运算算第第(2)步步较较复复杂杂，并并且且在在计计算算余余式式和和决决定定E(x)的时候需要把整个接收码组的时候需要把整个接收码组R(x)暂时存储起来。暂时存储起来。 对对于于纠纠正正突突发发错错误误或或单单个个错错误误的的编编码码还还算算简简单单，而而对于纠正多个随机错误的编码却是十分复杂的。对于纠正多个随机错误的编码却是十分复杂的。 48 这这种种解解码码方方法法称称为为捕捕错错解解码码法法。一一种种编编码码可可以以有有几几种种不不同同的的纠纠错错解解码码法法。对对于于循循环环码码来来说说，可可用用捕捕错错解解码码、大数逻辑解码等大数逻辑解码等 现在主要用现在主要用软件软件来做编解码来做编解码499.5.5 缩短循环码缩短循环码v并并不不是是在在所所有有码码长长(n,k)码码中中，都都能能找找到到相相应应的的满满足足某某纠纠错错能能力力的的循循环环码码。但但在在系系统统设设计计中中，码码长长n、信信息位数息位数k和和纠错能力纠错能力常常是预先确定的。常常是预先确定的。v这时可采用缩短循环码来满足要求。这时可采用缩短循环码来满足要求。v把把一一个个(n+i，k+i)循循环环码码的的信信息息位位减减少少到到k位位。就就得得到到一一位位新新的的(n,k)的的线线性性码码，我我们们称称这这种种码码为为缩缩短短循循环环码码。由由于于监监督督码码没没有有变变化化，缩缩短短循循环环码码与与原原循循环环码码至至少少具具有有相相同同的的纠纠错错能能力力；缩缩短短循循环环码码的的编编码码和和译译码可用码可用原循环码使用的电路原循环码使用的电路完成。完成。v在在实实际际中中，为为了了增增加加检检错错性性能能，在在原原循循环环码码上上增增加加一一个个偶偶校校验验位位，得得到到(n+1,k+1) 码码扩扩展展码码。扩扩展展码已不再具有循环性。码已不再具有循环性。509.5.4 BCH码码 v在已提出的许多纠正随机错误的码中，在已提出的许多纠正随机错误的码中，BCH码是至码是至今用得今用得最广泛和很有效最广泛和很有效的一种码，的一种码，BCH码是以发明码是以发明这种码的三个人的名字来命名的。这种码的三个人的名字来命名的。BCH码是一类码是一类纠纠正多个随机错误正多个随机错误的循环码。的循环码。vBCH码分两类，即码分两类，即本原本原BCH和非本原和非本原BCH码。本原码。本原BCH码的码长为码的码长为n=2m-1，(m是是3的任意正整数的任意正整数)，它的生成多项式它的生成多项式g(x)中中含有含有最高次数为最高次数为m次的次的本原多本原多项式；项式；v非本原非本原BCH码的码长码的码长n是是2m-1的一个因子，它的生成的一个因子，它的生成多项式多项式g(x)中中不含有不含有最高次数为最高次数为m的的本原多项式本原多项式。v能能纠纠正正tm/2错错码码的的BCH码码，其其码码长长为为n=2m-1，监监督位督位n-kmt。v若若码码长长n=(2m-1)/ii1，且且除除得得尽尽(2m-1)，则则为为非非本本原码。原码。v具具有有循循环环性性的的汉汉明明码码就就是是能能纠纠正正单单个个错错码码的的本本原原BCH码码v表表11-7中中的的( (23,12) )码码称称为为戈戈莱莱( (Golay) )码码，它它是是一一个个纠纠正正三三个个随随机机错错误误的的码码，且且容容易易解解码码，实实际际中中使使用的比较多。用的比较多。529.6 卷积码卷积码树状图树状图监监督督码码不不仅仅与与本本组组信信息息码码有有关关，还还与与前前面面N-1组组信信息息码码有有关关，符号符号（n,k,N）。）。N:约束度；约束度；nN:约束长度。约束长度。码码长长较较短短(2or3)，实实时时性性好好，更适用于前向纠错。更适用于前向纠错。53OUTIN010M2M1输入输入1移位移位 输入输入0移位移位 0a状态状态复位复位a状态状态b状态状态54OUTIN110M2M1输入输入1移位移位b状态状态0输入输入0复位复位c状态状态d状态状态55网格图网格图56非系统码非系统码57卷积码译码卷积码译码大数逻辑译码（门限译码）大数逻辑译码（门限译码）概率译码：分为维特比译码和序列译码概率译码：分为维特比译码和序列译码 网格编码网格编码卷积码和多相卷积码和多相PSK的结合的结合58第第9章作业章作业 思考题 习题 学号 1 9 8 16 1 9 17 25 33 2 10 7 15 2 10 18 26 34 3 11 6 14 3 11 19 27 35 4 12 5 13 4 12 20 28 36 5 13 4 12 5 13 21 29 37 6 14 3 11 6 14 22 30 38 7 15 2 10 7 15 23 31 39 8 16 1 9 8 16 24 32 40