§8.2纠错编码的基本原理 纠错编码的基本原理
简单例子： 简单例子： 3位二进制码组（c1 c2 c3）,其中 位二进制码组（ ） 其中ci=0或1。此码组 或 。 位二进制码组 其中 种不同的组合： 有8种不同的组合： 种不同的组合 000 001 010 011 100 101 110 111
可分别代表不同的信息含义。若将 种码组都作为有用 可分别代表不同的信息含义。若将8种码组都作为有用 码组来使用，比如代表8种天气情况 种天气情况： 码组来使用，比如代表 种天气情况： 000（晴），001（雷），010（雹），011（阴）， （ ）， （ ）， （ ）， （ 100（风）， （ ），101（云）， （ ），110（雨）， （ ），111（雪） （
4
二、纠错编码的分类
按功能分： 按功能分：检错码和纠错码 按监督码元与信息码元之间是否存在线性关系分： 按监督码元与信息码元之间是否存在线性关系分： 线性码与非线性码 按信息码元与监督码元之间的约束关系不同分： 按信息码元与监督码元之间的约束关系不同分：分 组码与非分组码如卷积码 按信息码元在编码后是否保持原来的信号形式分： 按信息码元在编码后是否保持原来的信号形式分： 系统码与非系统码 按纠正差错的类型分： 按纠正差错的类型分：纠正随机错误的码与纠正突 发错误的码 按码元的取值分： 按码元的取值分：二进制码与多进制码
13
000（晴） （
111（阴） （
其他均为禁用码组， 其他均为禁用码组，则它可检测两个错码或能纠正一 个错码。 个错码。 如：接收端接收到禁用码组100，若认为只有一个错码， 接收端接收到禁用码组 ，若认为只有一个错码， 可纠正，若错码数不超过2个 可纠正，若错码数不超过 个，只能检测错误 4种信息完全可以由 位二进制数字来表示，即前两位。 种信息完全可以由2位二进制数字来表示 即前两位。 种信息完全可以由 位二进制数字来表示， 可见，第三位完全是多余的， 可见，第三位完全是多余的，这第三位就作为附加的 监督码
6
四、差错控制方法
（1）前向纠错（FEC） ）前向纠错（FEC）
7
优点：无需反向信道、译码总延迟恒定， 优点：无需反向信道、译码总延迟恒定，具有恒定的信息 传输速率 缺点：当纠错能力强时，要增加冗余位； 缺点：当纠错能力强时，要增加冗余位；接收可靠性对信 道传输条件的恶化很敏感 （2）自动要求重发（ARQ） ）自动要求重发（ARQ）
P≤e
− nE ( R )
E（R）称为误差指数，n编码长度，R信息发送速率 （ ）称为误差指数， 编码长度 编码长度， 信息发送速率
16
三、编码距离与纠错检测的关系
几个基本概念 码重：二进编码序列 中 包含1的个数为该码组的重 码重：二进编码序列V中，包含 的个数为该码组的重 ），W(v) 量（权）， 码距：两个等长码组V1,V2中对应码位上不同二进制码 码距：两个等长码组 中对应码位上不同二进制码 元的个数，也叫汉明距离， 元的个数，也叫汉明距离，d(V1,V2) 两码组间的汉明距离也等于两码组对应位模二加后所得 码组的重量
11
这种编码方法就不具有任何抗干扰能力： 这种编码方法就不具有任何抗干扰能力： 任一码组在传输中若发生一个或多个错码， 任一码组在传输中若发生一个或多个错码，则将变成 另一信息码组 但如果在8种码组中，规定只准使用其中 种来传输信息 种来传输信息， 但如果在 种码组中，规定只准使用其中4种来传输信息， 种码组中 比如，许用码组为： 比如，许用码组为： 000（晴）， 011（阴）， 101（云）， 110（雨） （ （ （ （ 这种编码接收端有可能检测码组中出现的一位或 这种编码接收端有可能检测码组中出现的一位或 三位错误， 三位错误，但不能发现两位错码的情况 接收端收到禁用码组时， 接收端收到禁用码组时，就认为发现了错误
η
k k = = n k + r
19
编码效率是衡量码性能的一个重要参量， 编码效率是衡量码性能的一个重要参量，编码效率与 抗干扰能力这两个参数是相互矛盾的 编码的主要任务就是如何找到一种编码， 编码的主要任务就是如何找到一种编码，在满足一定 误码率要求的前提下，尽量提高编码效率。 误码率要求的前提下，尽量提高编码效率。
15
二、纠错编码的理论基础
理论依据：Shannon信道编码定理 理论依据：Shannon信道编码定理 定理指出： 定理指出： 对于一给定的有干扰信道，若其信道容量为C 对于一给定的有干扰信道，若其信道容量为C， 只要发送端以低于 的速率R发送信息， 低于C 只要发送端以低于C的速率R发送信息，则一定存在 一种编码方法，使编码错误概率P随着码长n的增加， 一种编码方法，使编码错误概率P随着码长n的增加， 按指数下降到任意小的值。 按指数下降到任意小的值。
9
发端发出同时具有检错和纠错能力的码，收端收到后， 发端发出同时具有检错和纠错能力的码，收端收到后， 检查错误情况：如果错误在纠错能力之内，则自动纠正； 检查错误情况：如果错误在纠错能力之内，则自动纠正； 若超出纠错能力，但在检错能力之内， 若超出纠错能力，但在检错能力之内，则经反向信道要 求重发。 求重发。
d (V 1,V 2) = W (V 1 ⊕ V 2)
例：V1＝{11001100}和V2={10010111} ＝ 和 重量分别为W1＝4，W2＝5；它们的距离为 重量分别为 ＝ ， ＝ ； d(V1,V2)=5。 。
17
最小码距：对于某种编码， 最小码距：对于某种编码，所含的全部码组之间的最小距 成为该码的最小码距， 离，成为该码的最小码距，用dmin表示 最小码距的大小直接关系着这种编码的检错和纠错能力， 最小码距的大小直接关系着这种编码的检错和纠错能力， 直接关系着这种编码的检错和纠错能力 它是衡量各种码抗干扰能力大小的标准。 它是衡量各种码抗干扰能力大小的标准。码组的最小距离 越大，说明码字间的最小差别越大，抗干扰能力越强。 越大，说明码字间的最小差别越大，抗干扰能力越强。 最小码距与检错和纠错能力的关系 1) 如果 一个码能检错不多于 个错，则要求 一个码能检错不多于e个错 个错， 2) 如果 一个码能纠正不多于 个错，则要求 一个码能纠正不多于t个错 个错，
14
一、纠错编码的基本思想
发送端按照某种规则在信息序列上附加监督码元， 发送端按照某种规则在信息序列上附加监督码元， 附加监督码元 接收端则按照同一规则检查两者间关系 码的检错和纠错能力是用信息量的冗余来换取的。 码的检错和纠错能力是用信息量的冗余来换取的。 冗余来换取的 添加的冗余越多，码的检错、纠错能力越强， 添加的冗余越多，码的检错、纠错能力越强，但信道 的传输效率下降也越多。 的传输效率下降也越多。 以牺牲通信的有效性（信息传输速率）来提高可靠性 牺牲通信的有效性（信息传输速率）来提高可靠性
第八章 差错控制编码
1
● —— 主要内容
§8.1 §8.2 §8.3 §8.4 §8.5
引言 纠错编码的基本原理 线性分组码 循环码 小结
2
§8.1 引言
一、基本概念
在数字信号传输中，由于噪声的存在及信道特性 在数字信号传输中，由于噪声的存在及信道特性 不理想，都可使信号波形失真， 不理想，都可使信号波形失真，从而在接收端就不可 避免的产生错误判决。 避免的产生错误判决。 引起误码原因: 引起误码原因: (1)信道特性不理想 乘性干扰 引起码间串扰， (1)信道特性不理想(乘性干扰 引起码间串扰，通常 信道特性不理想 乘性干扰): 可采用均衡的办法纠正。 可采用均衡的办法纠正。 噪声影响(加性干扰 加性干扰) (2) 噪声影响 加性干扰 : 需借助各种差错控制编码 技术来克服。 技术来克服。
线性码 码组中监督码元和信息码元之间满足线性变换关系， 码组中监督码元和信息码元之间满足线性变换关系，由一 组线性方程（监督方程）构成。线性码是一种代数码。 组线性方程（监督方程）构成。线性码是一种代数码。奇 偶监督码是最简单的线性码。 偶监督码是最简单的线性码。
注意：不同的纠错编码方法，有不同的检错或纠错能力， 注意：不同的纠错编码方法，有不同的检错或纠错能力， 一般说来，增加监督码元越多，检错或纠错的能力就越强， 一般说来，增加监督码元越多，检错或纠错的能力就越强， 提高传输可靠性是以降低传输有效性为代价的。 提高传输可靠性是以降低传输有效性为代编码) 差错控制编码又称为信道编码(纠错编码)，要求在 又称为信道编码 满足有效性前提下， 满足有效性前提下，尽可能提高数字通信的可靠性 有效性前提下 纠错编码： 纠错编码：在要传送的数字信息序列中按一定规则加 上一些冗余码元（监督位), ),使序列按满足一定数学规律 上一些冗余码元（监督位),使序列按满足一定数学规律 的码字传输(编码过程); 的码字传输(编码过程); 译码:在接收端, 译码:在接收端,利用这种规律性来鉴别传输过程是否 发生错误或纠正错误，恢复原始信息序列。 发生错误或纠正错误，恢复原始信息序列。
5
三、误码的类型 随机误码
•错码出现是随机的、错码之间统计独立。 错码出现是随机的、错码之间统计独立。 错码出现是随机的 统计独立 •由随机噪声引起 由随机噪声引起 •存在随机误码的信道称为随机信道 存在随机误码的信道称为随机信道
突发误码
•错码成串集中出现，在很短的时间出现大量错码，而 错码成串集中出现，在很短的时间出现大量错码， 错码成串集中出现 过后又存在较大的无错码位，且差错之间是相关的 过后又存在较大的无错码位， •例如：脉冲噪声，信道中衰落 例如： 例如 脉冲噪声， •存在这种差错的信道称为突发信道 存在这种差错的信道称为突发信道
五、编码增益
描述编码系统对非编码系统性能的改善程度， 描述编码系统对非编码系统性能的改善程度，定义为 在给定误码率要求下， 在给定误码率要求下，非编码系统与编码系统之间所 需信噪比的差。 需信噪比的差。 编码增益越大越好
20
§8.3线性分组码 线性分组码
一、基本概念