第第 九九 章章差错控制编码差错控制编码信信源源信信源源编编码码信信道道编编码码调调制制发发转转换换器器媒媒质质收收转转换换器器解解调调信信道道译译码码信信源源译译码码信信宿宿9.0 引言引言目的：目的：提高通信系统的可靠性提高通信系统的可靠性 降低误码率，减少发射功率，提高接收机的灵敏度等等。降低误码率，减少发射功率，提高接收机的灵敏度等等。1. 随机性差错：随机性差错：差错是随机的且相互之间是独立出现。通常差错是随机的且相互之间是独立出现。通常由由高斯白噪声引起；高斯白噪声引起；12位错误。位错误。2. 突发性差错：突发性差错：由脉冲性干扰引起由脉冲性干扰引起, ,在短暂的时间内出现连续在短暂的时间内出现连续的差错，而这些短暂时间之后却又存在较长的无误码区间。的差错，而这些短暂时间之后却又存在较长的无误码区间。一、差错类型一、差错类型9.1 纠错编码的基本概念纠错编码的基本概念混合性差错：混合性差错：既存在随机差错又有突发性差错。既存在随机差错又有突发性差错。以上两种错误性质不同，可采取不同措施处理以上两种错误性质不同，可采取不同措施处理 ！ 可以用来检测一位错误可以用来检测一位错误 可纠正一位错误或检测两位错误可纠正一位错误或检测两位错误AB 许用码组许用码组 禁用码组禁用码组 00 01 11 10 采用采用2 2位二进制码位二进制码许用码组许用码组 禁用码组禁用码组 000 001 010 100 111 101 110 011采用采用3 3位二进制码位二进制码采用采用1 1位二进制码位二进制码01二、差错控制的基本方法二、差错控制的基本方法 在信息序列之后附加一些监督码元在信息序列之后附加一些监督码元，这些多余的码元与信，这些多余的码元与信息码元之间以某种确定的规则相互关联，接收端按照既定的规息码元之间以某种确定的规则相互关联，接收端按照既定的规则检验出关联关系，如这种规则受到破坏，将会发现错误，乃则检验出关联关系，如这种规则受到破坏，将会发现错误，乃至纠正错误。至纠正错误。例：例：三、检错与纠错能力三、检错与纠错能力与最小码距与最小码距 d0 的关系的关系结论：结论：最小码距决最小码距决定检错和纠错能力定检错和纠错能力(c) 为了同时检测为了同时检测e个错误，纠正个错误，纠正t个错误个错误d0 et1(b) 为了纠正为了纠正t个错误个错误 d0 2t1(a) 为了检测为了检测e个错误，个错误， d0 e1码距：码距：两个码组对应位上不同的数目。两个码组对应位上不同的数目。 码重：码重：码组中码组中“1”的数目。的数目。AB0 1 2 3d0e(a)AB0 1 2 3 4 5d0tt(b)ABd0et tt1(c)四、差错控制编码的效用四、差错控制编码的效用 假设在随机信道中发假设在随机信道中发“0”“0”和发和发“1”“1”的概率相同，在码长为的概率相同，在码长为n的码组中恰好发生的码组中恰好发生 r 个错误的概率为：个错误的概率为：( p为误码率为误码率 )当码长当码长 n7 ，误码率误码率 时时 ，则有：则有：结论：采用差错控制编码，即使仅能纠正（或检测）结论：采用差错控制编码，即使仅能纠正（或检测）12个错误，就能使误码率下降几个数量级。个错误，就能使误码率下降几个数量级。 五、纠错码的五、纠错码的分类分类分类分类1. 分组码与卷积码分组码与卷积码：分组码：分组码：将信息码分组，为每组信息码后面附加若干位监督码元，且将信息码分组，为每组信息码后面附加若干位监督码元，且 监督码元仅监督本码组中的信息位监督码元仅监督本码组中的信息位。 K个信息位个信息位r个监督位个监督位码长码长 nkr卷积码：卷积码：卷积码也是先将信息序列分组，后面附加监督位，但是监卷积码也是先将信息序列分组，后面附加监督位，但是监督位不但与本码组的信息位有关，还与前面码组的信息位有关，或督位不但与本码组的信息位有关，还与前面码组的信息位有关，或者说监督位不仅监督本码组的信息位还监督其它码组的信息位者说监督位不仅监督本码组的信息位还监督其它码组的信息位。2. 系统码与非系统码系统码与非系统码系统码：系统码： 就是信息位在前，监督位在后的码字。就是信息位在前，监督位在后的码字。非系统码非系统码: : 信息位与监督位之间无特定的位置关系。信息位与监督位之间无特定的位置关系。9.2 差错控制方式差错控制方式2. 前向纠错前向纠错（FEC） 可以纠正错误可以纠正错误 发发 收收3. 混和纠错混和纠错（HEC） 可以发现和纠正错误可以发现和纠正错误 发发 收收 应答信号应答信号 比较：比较：译码复杂性、实时性和占用传输链路译码复杂性、实时性和占用传输链路(单向还是双向单向还是双向)1. 检错重发（检错重发（ARQ） （包括停发等候重发、返回重发和选择重发）（包括停发等候重发、返回重发和选择重发） 能够发现错误能够发现错误 发发 收收 应答信号应答信号ARQ：自动重复请求发送：自动重复请求发送1233123ACKNAKACK等待时间等待时间发送端发送端接收端接收端1 2 3 4 5 6 2 3 4 5 6 7 8 9 10 111 2 3 4 5 6 2 3 4 5 6 7 8 9 10 11从码组从码组2 2开始重发开始重发NAKACK发现错误发现错误 停发等候重发停发等候重发 返回重发返回重发1 2 3 4 5 6 2 7 8 9 10 1 12 1 2 3 4 5 6 2 7 8 9 10 1112重发重发码组码组2 2NAKACK发现错误发现错误选择重发选择重发比较反返回重发和选择重发：比较反返回重发和选择重发： 看起来只重传特定的帧比同时将未损坏的帧一起传显得更有效，看起来只重传特定的帧比同时将未损坏的帧一起传显得更有效，但是由于接收方进行的排序和存储所需的复杂度，以及发送方选择重但是由于接收方进行的排序和存储所需的复杂度，以及发送方选择重传所需的额外逻辑，选择重发传所需的额外逻辑，选择重发ARQARQ的开销更大，所以并不常用。的开销更大，所以并不常用。（1）帧损坏：）帧损坏：接收方发现错误，就返回一个否认帧给发送方，发送方重发最后一帧。接收方发现错误，就返回一个否认帧给发送方，发送方重发最后一帧。发送方发送方接收方接收方数据帧数据帧0ACK1数据帧数据帧1ACK0数据帧数据帧0NAK时间时间时间时间等待时间等待时间等待时间等待时间等待时间等待时间停等停等ARQ，损坏帧损坏帧数据帧数据帧0ACK1。正确正确有错误有错误停等停等ARQ：（ 2） 帧丢失帧丢失（a）丢失数据帧：丢失数据帧： 发送设备等待发送设备等待ACK或或NAK帧直到定时器超时帧直到定时器超时；（b）确认帧丢失确认帧丢失: 接收方检查到达的新数据帧编号。接收方检查到达的新数据帧编号。如果丢失的是如果丢失的是NAK帧，接收方将接收新的数据帧拷贝并返回一个帧，接收方将接收新的数据帧拷贝并返回一个ACK帧；帧；如果丢失的是如果丢失的是ACK帧，则接收方将新的数据帧拷贝视为重复帧，对它的接帧，则接收方将新的数据帧拷贝视为重复帧，对它的接收进行确认并等待下一帧的到来收进行确认并等待下一帧的到来发送方发送方接收方接收方数据帧数据帧0ACK1数据帧数据帧0ACK1时间时间时间时间超时超时等待时间等待时间停等停等ARQ，确认帧丢失，确认帧丢失。丢失丢失9.3 常用的简单纠错码常用的简单纠错码1. 奇偶校验奇偶校验设信息位每组长度为设信息位每组长度为n-1n-1位，增加一位监督位，位，增加一位监督位，n n位编码构成以下位编码构成以下约束关系约束关系接收端计算校正子接收端计算校正子奇偶校验可以用来检测单个或奇数个错误奇偶校验可以用来检测单个或奇数个错误2. . 纵向奇偶校验（纵向奇偶校验（LRC）用于检测突发错误）用于检测突发错误11100111 11011101 00111001 1010100111100111110111010011100110101001纵向排列纵向排列原是数据原是数据11100111 11011101 00111001 10101001 10101010突发错误突发错误接收方检验是否满足接收方检验是否满足LRCLRC 10101010监督码元监督码元交织编码：交织编码： 针对突发性错误针对突发性错误 信信 息息 码码 元元 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 监督码元监督码元 0 0 1 1 1 0 0 0 0 1 0监督码元监督码元 1 0 0 1 0 1 13. 水平垂直奇偶校验水平垂直奇偶校验它能发现某一行或某一列上所有奇数个错误以它能发现某一行或某一列上所有奇数个错误以及长度不大于行数（或列数）的突发错误及长度不大于行数（或列数）的突发错误5. 群计数码群计数码111001 100信息位信息位监督位监督位发现所有奇数个错误，以及一些偶数个错误，除发现所有奇数个错误，以及一些偶数个错误，除“0”变变“1”，和和“1”变变“0”成对出现。成对出现。4. 等重码（恒比码）等重码（恒比码）数字数字 电电 码码 数字数字 电电 码码 0 0 1 1 0 1 5 0 0 1 1 1 1 0 1 0 1 1 6 1 0 1 0 1 2 1 1 0 0 1 7 1 1 1 0 0 3 1 0 1 1 0 8 0 1 1 1 0 4 1 1 0 1 0 9 1 0 0 1 15中取中取3，或，或7中取中取4作业：作业：9-3，9-59.4 线性分组码线性分组码定义：定义：信息位和监督位之间的关系是由线性方程组约束的编码称信息位和监督位之间的关系是由线性方程组约束的编码称作线性分组码，即监督码元是由信息码元的线性组合而产生。作线性分组码，即监督码元是由信息码元的线性组合而产生。奇偶校验码就是一种效率很高的线性分组码奇偶校验码就是一种效率很高的线性分组码。这里这里S称为校正子，若称为校正子，若S0，表示无错，表示无错，S1表示有错误，由表示有错误，由于只用了一位监督位于只用了一位监督位a 0 ，因此只能表示有错与无错。，因此只能表示有错与无错。若监督位增加到若监督位增加到2位，就可增加一个监督方程式，接收时就可位，就可增加一个监督方程式，接收时就可计算计算2个校正子个校正子S1和和 S2 ，共有四种可能，除了，共有四种可能，除了00表示无错以表示无错以外，其余外，其余3种就可以表示一位错码的的具体位置了种就可以表示一位错码的的具体位置了。对于二进制编码，知道了错误的位置，就可以实现纠错了对于二进制编码，知道了错误的位置，就可以实现纠错了一般说来对于，对一般说来对于，对 r r个监督位，可以计算个监督位，可以计算r 个校正子，它可以指个校正子，它可以指出出 种错误图样，即种错误图样，即 个错误位置，因此对于个错误位置，因此对于（n，k）码。要想指出一位错码的所有可能位置，则要求：码。要想指出一位错码的所有可能位置，则要求：2 1r2 1r 设分组码中设分组码中（n，k）中中k4，为了纠正一位错误，则为了纠正一位错误，则 ，取，取r3，则，则n7，用用 表示，用表示，用 表示由表示由3 3个监督方程式计算得到的校正子，并假设这个监督方程式计算得到的校正子，并假设这3 3个校正子与误码对应的关系如下表所示：个校正子与误码对应的关系如下表所示：对于对于纠正纠正t 个错误个错误一、线性分组码的构成：一、线性分组码的构成：纠正纠正1 1个错误个错误校正子表校正子表 S1S2S3 误码位置误码位置 S1S2S3 误码位置误码位置 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 0 无错无错因此接收端计算下面因此接收端计算下面3个校验关系，可确定误码的位置个校验关系，可确定误码的位置发送端构成偶校验关系发送端构成偶校验关系由此监督位可以由信息位的线性组合得到：由此监督位可以由信息位的线性组合得到：许用码组许用码组信息位信息位 监督位监督位 信息位信息位 监督位监督位 0 0 0 0 0 0 0 1 0 0 0 111 0 0 0 1 0 1 1 1 0 0 1 100 0 0 1 0 1 0 1 1 0 1 0 010 0 0 1 1 1 1 0 1 0 1 1 001 0 1 0 0 1 1 0 1 1 0 0 001 0 1 0 1 1 0 1 1 1 0 1 010 0 1 1 0 0 1 1 1 1 1 0 100 0 1 1 1 0 0 0 1 1 1 1 111二、二、二、二、线性分组码的生成和监督矩阵线性分组码的生成和监督矩阵1. 1. 监督矩阵监督矩阵即即其中：其中：2. 2. 生成矩阵生成矩阵生成矩阵生成矩阵对于所有的编码与信息位的关系：对于所有的编码与信息位的关系：P为为 阶矩阵，阶矩阵， 为为 阶单位阵阶单位阵，具有具有 形式称为典型形式的监督矩阵；形式称为典型形式的监督矩阵；线性代数理论告诉我们，典型形式的监督矩阵各行一定是线性无关的，线性代数理论告诉我们，典型形式的监督矩阵各行一定是线性无关的，非典型形式的监督矩阵可以通过矩阵的初等变换化为典型形式。非典型形式的监督矩阵可以通过矩阵的初等变换化为典型形式。其中其中则则全部码字由信息位与生成矩阵全部码字由信息位与生成矩阵G相乘得到相乘得到Q为为K r 阶矩阵阶矩阵。I k为为k 阶单位阵阶单位阵具有典型化形式具有典型化形式 的生成矩阵称为典型生成矩阵的生成矩阵称为典型生成矩阵 它与典型化形式它与典型化形式 的关系为：的关系为： 结论：结论： 1). 由典型化的生成矩阵产生的是系统码组；由典型化的生成矩阵产生的是系统码组；k 2). 典型化的生成矩阵的各行也必定是线性无关的，每一行都是典型化的生成矩阵的各行也必定是线性无关的，每一行都是一个许用码组，一个许用码组，k行许用码组进过运算可以生成行许用码组进过运算可以生成 2 个不同的码组，个不同的码组， 非典型形式的生成矩阵经过运算也一定可化为典型形式。非典型形式的生成矩阵经过运算也一定可化为典型形式。例：若线性分组码的生成矩阵为例：若线性分组码的生成矩阵为：典型阵为典型阵为：监督矩阵监督矩阵三、线性分组码的特性：三、线性分组码的特性：1) 任意两个许用码组之和仍为许用码组封闭性任意两个许用码组之和仍为许用码组封闭性2) 码的最小距离等于非零码的最小重量码的最小距离等于非零码的最小重量。四、四、线性分组码的伴随式译码线性分组码的伴随式译码设发送的码组为设发送的码组为A，接收的码组为接收的码组为R，设设E为传输错误图样为传输错误图样，则则：RAE计算校正子计算校正子或者或者对于前面（对于前面（7，4）码的例子，一位错误图样为：）码的例子，一位错误图样为： (1000000) , (0100000)， (0010000)，(0001000)， (0000100)，(0000001), (0000001).例：若接收的码组为例：若接收的码组为1001101计算伴随式计算伴随式 ：最后一位有错，译码得：最后一位有错，译码得：1001100校正子校正子S只与只与E有关，若接收码字有关，若接收码字R中第中第I 位有错，那么导出的伴位有错，那么导出的伴随式随式 恰好是矩阵恰好是矩阵H的第的第i 列相同的位置。利用伴随式不列相同的位置。利用伴随式不仅可以判决接收码字中是否有错，而且可以指出差错的位置。仅可以判决接收码字中是否有错，而且可以指出差错的位置。作业：作业：9-79.5 循环码循环码一、特点：一、特点：循环码是一种具有循环移位特性的线性分组码，这循环码是一种具有循环移位特性的线性分组码，这类码除了具有线性分组码的一般性质外，还具有循环性质带来类码除了具有线性分组码的一般性质外，还具有循环性质带来的其它性能和特征，并可以用不太长的码长来实现，循环码本的其它性能和特征，并可以用不太长的码长来实现，循环码本身的特性使编译设备比较容易实现。身的特性使编译设备比较容易实现。1. 码多项式码多项式：若若 是一个码字是一个码字则则C的每次的每次循环移位都是一个码字循环移位都是一个码字序号序号 信息码信息码 (7.3)循环码循环码 移位次数移位次数 码多项式码多项式0 000 0000000 1 001 0011101 02 011 0111010 133 111 1110100 24 110 1101001 35 101 1010011 46 010 0100111 577 100 1001110 6例例 ：(7，3)循环码循环码按模运算规则：模按模运算规则：模n运算下，一整数运算下，一整数m等于其被等于其被n除得到的余数除得到的余数模运算中，模运算中，一般的讲，若一整数一般的讲，若一整数m可表示为可表示为：则：则： （模（模n）对于多项式对于多项式对于多项式对于多项式: :2. 按模运算按模运算结论：结论：可以证明在循环码中可以证明在循环码中, , 若若 是一个码长为是一个码长为n的许用码的许用码组多项式，则组多项式，则 在模在模 运算下亦是许用码组，运算下亦是许用码组，即若有：即若有：则则 也是一个许用码组。也是一个许用码组。前面的（前面的（7，3）1110100码多项式码多项式为为为为左移一位的多项式左移一位的多项式 1110100左移一位的码组左移一位的码组1101001对应的多项式对应的多项式显然显然多项式除法多项式除法： 二、循环码的生成多项式二、循环码的生成多项式 对于线性分组码来说只要找到它的生成矩阵就可确定所有的对于线性分组码来说只要找到它的生成矩阵就可确定所有的编码码字，而它的生成矩阵的每一行都是一个许用码组，循环编码码字，而它的生成矩阵的每一行都是一个许用码组，循环码的某一个码字循环移位可得到它的码字。只要找到这个码字码的某一个码字循环移位可得到它的码字。只要找到这个码字就可以得到生成矩阵。这个码字称为生成多项式（码字）。就可以得到生成矩阵。这个码字称为生成多项式（码字）。生成矩阵可写为：生成矩阵可写为：对于线性分组码，其生成矩阵由对于线性分组码，其生成矩阵由K 行线性无关的码字组成行线性无关的码字组成2. (n，k)循环码的生成多项式循环码的生成多项式g g (x)(x)是是 的因式的因式；定理：定理：1. 在一个在一个(n，k)循环码中，存在一个唯一的最低次码多循环码中，存在一个唯一的最低次码多项项式，式， 其次数为其次数为 r = n - k，且常数项必须为且常数项必须为，即生成多项式即生成多项式：3. 若是一个若是一个(nk)次多项式，且是次多项式，且是 的因式，则的因式，则 一定能生成一个一定能生成一个(n，k)循环码循环码。4. 所有码多项式必定能被整除，所有码多项式必定能被整除，即即 就是说阶数小于就是说阶数小于(n-1)(n-1)能被能被 整除的每个多项式都是循环码整除的每个多项式都是循环码的许用码组，或必是的倍式的许用码组，或必是的倍式 (7.k) 循环码循环码(n . k) d g( x) h( x ) (7.6) 2(7.4) 3(7.3) 4(7.1) 6结论：结论：(1) 一个一个( (n，k) )循环码的每一个码多项式也必然是按循环码的每一个码多项式也必然是按模模 运算后某个余式，即一个运算后某个余式，即一个(n，k)循环码的所有码字都循环码的所有码字都可以通过可以通过k 个许用码多项式循环移位得到。个许用码多项式循环移位得到。(2)(2) 循环码完全由其码组长度循环码完全由其码组长度n及生成多项式及生成多项式 g (x)决定决定. .例：一个例：一个(7，4) 循环码，则由生成多项式循环码，则由生成多项式构成的生成矩阵为构成的生成矩阵为：典型阵为典型阵为：监督矩阵监督矩阵三、循环码的系统码的编码实现三、循环码的系统码的编码实现系统码组中的最左边的系统码组中的最左边的k k位是信息码元，随后是位是信息码元，随后是n nk k位的监位的监督码元，即码多项式为：督码元，即码多项式为：因此因此：有：有：m (x) x 除法求余得到除法求余得到r ( x)n - k例例：已知已知 (7，4) 循环码的生成多项式为循环码的生成多项式为若信息码为若信息码为1001 ，求编码码字，求编码码字因此：因此：解：解：即编码码组为：即编码码组为： 1001011 S0 S1输入输入m。 S2。K1K2输出输出ef输入输入 移移 存存 器器 反馈反馈 输出输出 m S0 S1 S2 e f 0 0 0 0 0 00 0 0 0 0 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 反馈反馈 e=S21+m0作业作业：9-1，9-6，9-7，9-8，9-13，9-14 (n ,k) 循环码编码器循环码编码器Sn-k-1输出输出。K1K2f输入输入S0S0四、循环码的译码四、循环码的译码 校正子计算电路校正子计算电路 错误图样识别错误图样识别 n 级级 缓缓 存存 器器输入输入纠错后输出纠错后输出1 2 . (n -k)监督矩阵监督矩阵对于最高位错误，校正子为对于最高位错误，校正子为: : a b c 七七 级级 缓缓 存存 器器纠错后输出纠错后输出门门节拍节拍 输入输入 a b c 与门与门 缓存缓存 译码译码 1 0 0 0 0 输出输出 输出输出 输出输出 2 0 0 0 0 3 0 0 0 0 4 1 1 0 0 5 0 0 1 0 6 1 1 0 1 7 1 0 1 1 8 0 0 0 0 1 0 1节拍节拍 输入输入 a b c 与门与门 缓存缓存 译码译码 1 1 1 0 0 输出输出 输出输出 输出输出 2 1 1 1 0 3 0 0 1 1 4 1 0 0 0 5 0 0 0 0 6 1 1 0 0 7 1 1 1 0 8 0 0 1 1 0 1 1 9 0 0 0 0 1 1 0结论：结论： 可以看出译码器仅需识别最高位的错误图样即可可以看出译码器仅需识别最高位的错误图样即可用以上除法电路作为校正子计算电路时，用了一个重要的性质用以上除法电路作为校正子计算电路时，用了一个重要的性质：某码组循环移位某码组循环移位 i 次次的校正子等于原码组校正子在除法电路中循环的校正子等于原码组校正子在除法电路中循环移位移位 i 次所得的结果。即次所得的结果。即：上述性质可以使得译码器需要识别得错误图样数目大为减少，上述性质可以使得译码器需要识别得错误图样数目大为减少，因为某个可纠正错误图样因为某个可纠正错误图样E( x)得得 i 循环移位循环移位x E( x)也必定是可也必定是可以纠正的以纠正的.i(7.4)循环码完整译码器循环码完整译码器输出输出门门5 四四 级级 缓缓 存存 器器 a b c门门1 a b c门门2门门3门门4输入输入作业：作业：9-8，9-13，9-14，9-15