《CH差错控制编码》PPT课件.ppt

《《CH差错控制编码》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《CH差错控制编码》PPT课件.ppt（128页珍藏版）》请在装配图网上搜索。

1、2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 1 第 11章 差错控制编码 又称信道编码 ， 是提高数字传输可靠 性的一种技术 。 其 基本思想 是通过对信息序列作某种 变换 ， 使原来彼此独立 、 相关性极小的信 息码元产生某种相关性 ， 在接收端就可以 利用这种规律性来检查并纠正信息码元在 信 到 传输中所造成的差错 。 比如 ， 考试填空题 ， 改错题 概述 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 2 概述 纠错编码的基本原理 纠错编码的性能 简单的实用编码 线性分组码 循环码 卷积码 网格编码调制 TCM 其它编码 第 11章 差错

2、控制编码 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 3 11.1 概述 1.误码的主要形式 （ 1） 随机错误： 误码的位置随机 （ 误码间无关 联 ） ， 随机误码主要由白噪声引起 。 （ 2） 突发错误 ： 误码成串出现 ， 主要由强脉冲 及雷电等突发的强干扰引起 。 （ 3） 混合错误 ： 以上两种误码及产生原因的组 合 。 11.1 差错控制编码的基本概念 差错控制的主要方式 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 4 （ 1） 前向纠错 （ FEC） ； （ 2） 检错重发 （ ARQ） :停发等候重发 ， 返回重发 ， 选择

3、重发 ； （ 3） 反馈校验 （ IRQ） ； （ 4） 混合纠错 （ HEC） ； （ 5） 检错删除 。 能够发现错误的码 反馈信号 发 收 检错重发 （ ARQ） 可以纠正错误的码 发 收 前向纠错 （ FEC） 数据信息 发 收 信息反馈 数据信息 可以纠正和发现错误的码 发 收 混合 纠错检错 （ HEC） 反馈信号 发送端将信息序列编码成能够纠正错误的码 ， 接收端 根据编码规则进行检查 ， 如果有错自动纠正； 不需要反馈信道 ， 特别适合只能提供单向信道场合； 自动纠错 ， 不要求检错重发 ， 延时小 ， 实时性好； 纠错码必须与信道的错误特性密切配合； 若纠错较多 ， 则编 、

4、 译码设备复杂 ， 传输效率低； 收端把收到的数据序列全部经反向信道送回发端 ， 发端比较 发出和送回的数据序列 ， 从而发现有否错误 ， 并把有错误的 数据序列再次传送 ， 直到发端没有发现错误； 不需要纠错 、 检错的编 、 译码器 ， 设备简单； 需要和正向信道相同的反向信道 ， 实时性差； 发端需要一定容量的存储器以存储发送码组； 仅适应于传输速率较低 ， 信道差错率较低 ， 具有双向传输线 路及控制简单的系统 。 FEC与 ARQ的结合； 发端发出同时具有检错和纠错能力的码 ， 收端收到 后 ， 检查错误情况：如果错误在纠错能力之内 ， 则 自动纠正；若超出纠错能力 ， 但在检错能力

5、之内 ， 则经反向信道要求重发； 在实时性和译码复杂性方面是 FEC和 ARQ的折衷 。 11.1 差错控制编码的基本概念 2.差错控制的主要方式 几个概念 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 5 监督码元： 在接收端识别有无错码 ， 所以在发送端需要 在信息码元序列中增加一些除了信息码元之外的差错控 制码元 ， 它们称为监督码元 。 编码效率 (简称码率 ) ：设编码序列中信息码元数量为 k， 总码元数量为 n， 则比值 k/n 就是码率 。 例如 ， 若编码序 列中平均每两个信息码元就添加一个监督码元 ， 则这种 编码的码率为 1/3。 冗余度： 监督码元

6、数 (n-k) 和信息码元数 k 之比 。 不同的编码方法 ， 有不同的检错或纠错能力 。 理论上 ， 差错控制以降低信息传输速率为代价换取提高传输可靠 性 。 纠错编码又称为差错控制编码 差错控制编码的分类 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 6 3.差错控制编码的分类 （ 1） 线性码 ： 信息码与监督码之间的关系为线性关系 （ 信息位 与监督位之间是由一些线性方程联系的 ） ； 非线性码 ： 信息码与监督码之间的关系为非线性关系 。 （ 2） 分组码 ： 信息码与监督码以组为单位建立关系 （ 将信息码 分组 ， 为每组信码附加若干监督码的编码 ） ； 卷

7、积码 ： 监督码与本组和前面码组中的信息码有关 。 （ 3） 系统码 ： 编码后码组中信息码保持原图样顺序 (形式 )不变 ; 非系统码 ： 编码后码组中原信息码原图样发生变化 。 （ 4） 数学方法 ： 代数码 :建立在代数学基础上的编码 几何码 ； 算术码 。 分组码结构 11.2 差错控制编码的基本原理 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 7 分组码的结构 将信息码分组 ， 为每组信息码附加若干监督 码的编码称为 分组码 。 分组码中 ， 监督码元仅监督本码组中的信息 码元 。 分组码的一般结构 分组码的符号： (n, k) N 码组的总位数 ， 又称为

8、码组的长度 （ 码长 ） ， k 码组中信息码元的数目 ， nk r, 码组中的监督码元数目 ， 或称监督位数目 。 纠错编码基本原理 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 8 11.2 纠错编码的基本原理 1. 纠错编码的基本原理 理论依据 ： Shannon信道编码定理 。 定理指出 ： 对于一给定的有扰信道 ， 若其信道容量为 C， 只要发送端以低于 C的速率 R发送信息 ， 则一定存在一 种编码方法 ， 使编码错误概率 P随着码长 n的增加 ， 按 指数下降到任意小的值 。 2. 纠错编码的基本思想 ： 发送端按照某种规则在信息序列上附加监督码元 ， 接

9、 收端则按照同一规则检查两者间关系 以牺牲通信的有效性 （ 信息传输速率 ） 来提高可靠性 码的检错和纠错能力是用信息量的冗余来换取的 。 一 般说来 ， 添加的冗余越多 ， 码的检错 、 纠错能力越强 ， 但信道的传输效率下降也越多 。 检错与纠错 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 9 3. 检错与纠错的基本概念 11.2 差错控制编码的基本原理 例 1， 用 1位二进制码的 2种编码组合 ， 分别表示 “ 月有 阴晴圆缺 ” 中 “ 月 ” 的四种状态 。 0-圆 ， 1-缺 。 a. 若任一位或一位以上的错误都会变成另一码组 ， 所 以无法检错和纠错

10、。 例如 ， 发送 “ 0” ， 错误收到 “ 1” b. 若用 2位二进制 （ 有 4个码组 ） ， 表示 “ 圆 、 缺 ” 两 种信息 。 0 0 -圆 ， 1 1 -缺 用到的： 0 0， 1 1 称为 “ 许用码组 ” ： 其余不用的 ， 称为 “ 禁用码组 ” ： 1 0， 0 1 因任一位误码 ， 都会变成禁用码组 ， 所以可检出 1位 误码 。 续 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 10 可见 纠错编码之所以具有检错和纠错能力 ， 是因为 在信息码元外添加了冗余码元 （ 监督码元 ） ； 直观地 ， 冗余度越大 ， 许 （ 准 ） 用码组间的

11、区 别越大 ， 检错和纠错能力越强 。 几个术语 c. 若用 3位二进制 （ 有 8个码组 ） ， 表示 “ 圆 、 缺 ” 两种信息 。 0 00 -圆 ， 1 11 -缺 。 其余为禁用码 。 则可发现两位及以下的误码 ， 并纠正 1位误码 。 11.2 差错控制编码的基本原理 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 11 a. 码重 W： 码组中非零码元的数目 。 如 “ 011” 码字的码重为 2； b. 码距 d： 两码组中对应码元位置上取值 不同的个数 。 如码字 “ 011”与 “ 110”间码距 为 2； c. 最小码距 d0（ Hamming距

12、） ： 准用码组 中任两码组间的最小码距 。 几个术语 分组码码距和纠检错能力之间的关系 11.2 差错控制编码的基本原理 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 12 【 证 】 设一种编码的最小码距为 3。 任一个码组 A位于 O点 ， 码组 A发生两位以下错码时 ， 不可能变成另一个准用码组 ， 因而能检测错码的位数等于 2。 0 1 2 3 B A 汉明距离 e d0 即 ， 若一种编码 的最小码距为 d0， 则将能检测 (d0-1)个 错码 。 反之 ， 若要 求检测 e个错码 ， 则 最小码距 d0至少应 不小于 (e +1)。 分组码的码距和检纠错能

13、力的关系 1） 一种编码的最小码距 d0的大小直接关系着这种编码 的检错和纠错能力为检测 e个错码 ， 要求最小码距 d0e+1 续 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 13 【 证 】 图中画出码组 A和 B的距离为 5。 码组 A或 B若发 生不多于两位错码 ， 则其位置均不会超出半径为 2以原位 置为圆心的圆 。 这两个圆是不重叠的 。 判决规则为 ：若接收码组落于以 A为圆心的圆上就判 决收到的是码组 A， 若落于以 B为圆心的圆上就判决为码 组 B。 从而 ， 就能够纠正两位错码 。 B t A 汉明距离 0 1 2 3 4 5 t d0 2）为了纠

14、正 t个错码，要求最小码距 d0 2t + 1 续 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 14 图中码组 A和 B之间距离为 5。 按照检错能力公式 ， 最多 能检测 4个错码 ， 即 e = d0 1 = 5 1 = 4， 按照纠错能力公式 纠错时 ， 能纠正 2个错码 。 但是 ， 不能同时做到两者 ， 因为当错码位数超过纠错能 力时 ， 该码组立即进入另一码组的圆内而被错误地 “ 纠正 ” 了 。 例如 ， 码组 A若错了 3位 (超过 2位 )， 就会被误认为码组 B 错了 2位造成的结果 ， 从而被错 “ 纠 ” 为 B。 这就是说 ， 检 错和纠错公

15、式不能同时成立或同时运用 。 )(10 teted B t A 汉明距离 0 1 2 3 4 5 t d0 3）为纠正 t个错码，同时检测 e个错码，要求最小码距 续 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 15 这种纠错和检错结合的工作方式简称 纠检结合 。 A B e 1 t t 汉明距离 )(10 teted 所以 ， 为了在可以纠正 t个错码的同时 ， 能够检测 e个 错码 ， 就需要像下图所示那样 ， 使某一码组 （ 譬如码组 A） 发生 e个错误之后所处的位臵 ， 与其他码组 （ 譬如码组 B） 的纠错圆圈至少距离等于 1， 不然将落在该纠错圆上从而

16、发生错误地 “ 纠正 ” 。 因此 ， 由此图可以直观看出 ， 要 求最小码距 续 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 16 这种工作方式是自动在纠错和检错之间转换的 。 当错码数量少时 ， 系统按前向纠错方式工作 ， 以 节省重发时间 ， 提高传输效率；当错码数量多时 ， 系 统按反馈重发方式纠错 ， 以降低系统的总误码率 。 所以 ， 它适用于大多数时间中错码数量很少 ， 少 数时间中错码数量多的情况 。 纠检结合 纠错编码性能 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 17 由上节所述的纠错编码原理可知 ， 为了减少接收错 误

17、码元数量 ， 需要在发送信息码元序列中加入监督码元 。 这样作的结果使发送序列增长 ， 冗余度增大 。 若仍须保 持发送信息码元速率不变 ， 则传输速率必须增大 ， 因而 增大了系统带宽 。 系统带宽的增大将引起系统中噪声功率增大 ， 使信 噪比下降 。 信噪比的下降反而又使系统接收码元序列中 的错码增多 。 一般说来 ， 采用纠错编码后 ， 误码率总是能够得到 很大改善的 。 改善的程度和所用的编码有关 。 11.3 纠错编码的性能 系统带宽和信噪比的矛盾： 传输速率和信噪比关系 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 18 若希望提高传输 速率 ， 可看出势必

18、导 致信噪比下降 ， 误码 率增大 。 假设系统原来工 作在图中 C点 ， 提高 速率后由 C点升到 E点 。 但加用纠错编码后 ， 仍可将误码率降到 D 点 。 这时付出的代价 仍是带宽增大 。 B sssb Rn P Tn P n TP n E 0000 )/1( 10-6 10-5 10-4 10-3 10-2 10-1 编码后 Pe C D E A B 信噪比 (dB) 传输速率和 Eb/n0的关系对于给定的传输系统 式中， RB为码元速率。 几种简单的常用编码 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 19 11.4.1 奇偶效验码 在信息码组 an-1,

19、an-2,a 1中加入 监督位 a0， 使编码后码 组中 “ 1”的个数为奇数（ 奇效验 ）或偶数（ 偶效验 ）。 偶效验 ：取校验码（监督码元） a0， 使下式成立 an-1an-2 a1 a0 0 即， a0 = an-1an-2 a1 奇效验 ：取 校验码（监督码元） a0， 使下式成立 an-1an-2 a1 a0 1 即， a0 = an-1an-2 a1 1 奇偶效验码码组间最小距离 d0 2， 至少可检出一位误码 。 实际 ， 可检测所有奇数个误码 。 (用于计算机通信 ） 水平奇偶校验码 11.4 几种简单的常用编码 2020年 11月 16日 2时 45分 信电学院信息工程系

20、 李世银 20 a1 n -1 a1 n-2 a 11 a10 a2 n-1 a2 n-2 a 21 a20 am n-1 am n-2 a m1 am0 m个码组分别以各自码组为单位作奇效验或偶效验 ， 然后以各码组的最高位 、 次高位 ， 依次发送： 11.4.2 水平奇偶效验码 水平奇偶校验码特点 分组进行奇偶校验 发 送 次 序 当突发的错误数小于 m个时 ， 每个码组中的误码个数 最多为 1个 ， 通过奇偶效验可以检出 。 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 21 水平奇偶效验码特点： 在上面的分析中 ， 整个方阵作为一个 “ 码组 ” ， 长度为原

21、来的 m倍； 可检出不大于 m个的突发错误； 在未增加监督位的条件下 ， 检错能力 为原来的 m倍 ， 这是 香农信道编码定 理 应用的一个例子 。 该编解码所付的 代价 ：缓存空间和延 时增大 。 水平垂直奇偶校验码 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 22 11.4.3 水平垂直二维奇偶效验码 （ 方阵码 ） 8.1 差错控制编码的基本概念 a1 n-1 a1 n-2 a 11 a10 a2 n-1 a2 n-2 a 21 a20 an n-1 an n-2 a n1 an0 在水平奇偶监督码的基础上增加列的奇偶效验 可检出任一行和任一列的所有奇数个错误

22、， 及长度 不大于行数 （ 按列发 ） 或不大于列数 （ 按行发 ） 的突发 错误 。 其他校验码 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 23 11.4.4 恒比码 每个码组中含 “ 1”和 “ 0”的个数的比例恒定 ， 又称 等重码 能检测出所有奇数个错误 ， 并能部分检测出偶数个 错误 （ 成对交换错则检测不出 ） 简单 ， 适应于对字母或符号进行编码 11.4.5 群计数码 码组中的监督码元是信息序列中 “ 1”码个数的二进 制表示； 假设待编码信息序列为 1011101， 则编码后码组为 1011101101； 较强的检错能力 ， 能检测出几乎所有形式的

23、差错 （ 除同时发生 “ 0”变 “ 1”和 “ 1”变 “ 0”的成对错误 外 ） 正反码 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 24 例如 ， 码长 n = 10， 信息位 k = 5， 监督位 r = 5。 其 编码规则为： 若信息位为 11001， 则码组为 11001 11001； 若信息位为 10001， 则码组为 10001 01110。 11.4.6 正反码 正反码的编码： 它是一种简单的能够纠正错码的编码 。 其中的监督 位数目与信息位数目相同 ， 监督码元与信息码元相同或 者相反则由信息码中 “ 1”的个数而定 : 信息位中有奇数个 “ 1”

24、时 ， 监督位是信息位的重复； 当信息位有偶数个 “ 1”时 ， 监督位是信息位的反码 。 正反码解码 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 25 先将接收码组中信息位和监督位按模 2 相加 ， 得到一个合成码组 。 然 后 ， 由此合成码组产生一个校验码组： 若接收码组的信息位中有奇数个 “ 1”， 则合成码组就是校验码组； 若接收码组的信息位中有偶数个 “ 1”， 则取合成码组的反码作为校验码组 。 最后 ， 观察校验码组中 “ 1”的个数 ， 按下表进行判决及纠正可能发现 的错码 。 正反码的解码： 校验码组的组成 错码情况 1 全为 “ 0” 无错码 2

25、 有 4个 “ 1”和 1个 “ 0” 信息码中有 1位错码，其位置对应校验码 组中 “ 0”的位置 3 有 4个 “ 0”和 1个 “ 1” 监督码中有 1位错码，其位置对应校验码 组中 “ 1”的位置 4 其他组成 错码多于 1个 例 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 26 例 ， 发送 11001 11001， 无错接收 ， 则合成码组应为 1100111001=00000。 由于接收码组信息位中有奇数个 “ 1”， 所以校验码组就是 00000。 按上表判决 ， 结论是无错码 。 若传输中产生了差错： 接收码组错成 10001 11001， 则合成码

26、组 1000111001 01000。 由于接收码组中信息位有偶数个 “ 1”， 所以校验码组应取合成码 组的反码 ， 即 10111。 按上表判断信息位中左边第 2位为错码 。 若接收码组错成 11001 01001， 则合成码组 1100101001 10000。 由于接收码组中信息位有奇数个 “ 1”， 故校验码组就是 10000， 按上表判断 ， 监督位中第 1位为错码 。 若接收码组为 10011 11001， 则合成码组 1001111001 01010， 校验码组与其相同 ， 按上表判断 ， 这时错码多于 1个 。 上述长度为 10的正反码具有纠正 1位错码的能力 ， 并能检测

27、全部 2位以下的错码和大部分 2位以上的错码 。 线性分组码 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 27 11.5 线性分组码 11.5.1. 基本概念 线性分组码的 特点 ： (1)两许用码组之和 （ 逐位模 2和 ） 仍为一许用 码组 （ 封闭性 ） ； (2)码组间的最小距离等于非零码的最小码重 。 如何编码？校正子 线性分组码： 码组中的信息位和监督位之间的 关系由线性方程确定 。 表示方法： （ n， k） ,其中 n码组总位数； k信息位数 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 28 在偶数监督码中 ， 由于使用了一位

28、监督位 a0， 它和信 息位 an-1 a1一起构成一个代数式： 0021 aaa nn 021 aaaS nn 在接收端解码时 ， 实际上就是在计算 若 S = 0， 就认为无错码；若 S = 1， 就认为有错码 。 现将上式称为 监督关系式 ， S称为 校正子 。 由于校正子 S 只有两种取值 ， 故它只能代表有错和无错这两种信息 ， 而 不能指出错码的位置 。 11.5.2 校正子 校正子 续 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 29 例： 具有纠正 一位 误码的分组码 （ 7， 4） a6a5a4a3 a2a1a0 n = 7, k = 4, 信息位

29、监督位 r = n k 3 11.5 线性分组码 定义一组确定误码位置的参量： S1S2S3(校正子 ) 由上表可得： 如何确定 a2a1a0 ? 监督位确定 当出现一 位误码时 ， 校 正子能够确定 误码的位置 。 S1 S2 S3 错码位置 S1 S2 S3 错码位置 001 a0 101 a4 010 a1 110 a5 100 a2 111 a6 011 a3 000 无错码 03463 13562 24561 aaaaS aaaaS aaaaS 11.5.2 校正子（续） 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 30 由此 ,编码时监督位的产生 ： 给出

30、一组信息码 a6a5a4a3 ， 可计算出监督位 a2a1a0。 例 3460 3561 4562 aaaa aaaa aaaa 11.5 线性分组码 11.5.3 监督方程 当 无误码 时，应有 上述方程亦称为 监督方程 。 0 0 0 03463 13562 24561 aaaaS aaaaS aaaaS 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 31 例： 设信息码组 a6a5a4a3 0101 则监督位为： 若接收时有一位 (a5)码出错： a6a5a4a3 a2a1a0 0001101 则有： S1 a6a5a4a2 0001=1 S2 a6a5a3a1

31、0010=1 S3 a6a4a3a0 0011=0 根据校正子 S1 S2 S3 110， 可判断误码发生在 a5，并恢复。 3460 3561 4562 aaaa aaaa aaaa 100 110 010 1 0 1 则 发送码组： a6a5a4a3 a2a1a0 0101101 11.5 线性分组码 监督矩阵 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 32 0 0 0 03463 13562 24561 aaaaS aaaaS aaaaS 11.5.4 监督矩阵 11.5 线性分组码 监督矩阵 01001101 00101011 00010111 012345

32、63 01234562 01234561 aaaaaaaS aaaaaaaS aaaaaaaS 该监督方程可用矩阵形式表示 可用表示为 前述的 监督方程 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 33 前述的监督方程可用矩阵形式表示 0 0 0 1001101 0101011 0010111 0123456 Taaaaaaa 11.5 线性分组码 矩阵 H称为 监督矩阵 。 监督矩阵一般式及性质 0 0 0 . 0 1 5 6 a a a a H 这里 1001101 0101011 0010111 3PI H 11.5.4 监督矩阵 2020年 11月 16日 2

33、时 45分 信电学院信息工程系 李世银 34 一般地 ， 对于任意的监督方程都可用矩阵形式表示 11.5 线性分组码 矩阵 H称为 监督矩阵 。 0 . 0 0 . 0 1 2 1 a a a a H n n 监督矩阵的性质 ： （ 1） H由码元间的监督关系 S唯一确定； （ 2） H的行向量相互独立，当采用系统码结构时，具有形式 H=PIr 其中 Ir是 r r单位阵。并称之为 典型监督矩阵 。 （ 3）若发 A， 收到 B， HBT0则有误码。 11.5.4 监督矩阵 生成矩阵 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 35 11.5.5 生成矩阵 3 4 5

34、 6 0 1 2 1101 1011 0111 a a a a a a a 346 356 456 0 1 2 aaaa aaaa aaaa 在上例中 ， 根据监督方程 ， 监督位的产生可表示为 可用矩阵表示为 3 4 5 6 a a a a P 一般式 1101 1011 0111 P 3456 3456 3456 1101 1011 0111 0 1 2 aaaaa aaaaa aaaaa即 其中， 11.5 线性分组码 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 36 110 101 011 111 TPQ Qaaaaaaa 3456012 其转置形式： 式中

35、例 定义 为 生成矩阵 。 其中 Ik是 k k的单位阵 ， k为信息位数 。 QIPIG kTk Ga.aaa.aa rnnnn 21021 发送码组可按下式产生： 直接得到整个码组，而不 是只有监督位！ 11.5 线性分组码 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 37 如 ， 在上例中 可得 生成矩阵 1101 1011 0111 P 110 101 011 111 TPQ 346 356 456 0 1 2 aaaa aaaa aaaa Q,IP,IG kTk 110 101 011 111 1000 0100 0010 0001 发送码组可按下式产生：

36、Gaaaaaaaaaaa 34560123456 11.5 线性分组码 三个关系 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 38 11.5.6 校正 S与 H及误码码组 E的关系 表示接收码元错误 表示接收码元正确 ,ab, ,ab, e ii ii i 1 0 11.5 线性分组码 设发送码组为 A， 接收码组为 B 误码码组为： E=B-A=en-1en-2e 1e0 在接收端计算校正子为 矩阵 E常称为错误样图 。 （ 实际中只知道 B而并不知道 A和 E） S=BHT=A+EHT AHT+EHT = 0 + EHT =EHT 可见 ， S仅与 E和 HT有关

37、 ， S与 E之间存在确定关 系 ， 所以只需计算 S， 就可得到 E， 从而实现检错纠错 。 H与 G关系 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 39 QIG k 110 101 011 111 1000 0100 0010 0001 rPIH 1001101 0101011 0010111 1101 1011 0111 P 110 101 011 111 TPQ 可见 ， 监督矩阵和生成矩阵存在对应关系 ， 线性码 既可以由 G确定 ， 也可以直接由 H生成 。 使用场合 11.5.7 H和 G矩阵对应关系 2020年 11月 16日 2时 45分 信电学院

38、信息工程系 李世银 40 Gaaa aaa rnn nn . . 21 021 通常 ， 编码时使用生成矩阵 ， 译码时使用 监 督矩阵 。 S=BHT=EHT 例 E、 S、 监督方程 、 P、 H、 G六者之间 是相互关联 ， 一一对应的 。 一个改变必然导 致其它 5者的相应变化 。 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 41 【 例 1】 给定一个 （ 7， 4） 线性分组码的生成矩阵 1011000 1110100 1100010 0110001 G 若信息码为 d=1101， 求该信息码的线性分组编码 。 解： Ga.aaa.aa rnnnn 210

39、21 采用生成矩阵进行编码 11.5.8 应用举例 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 42 1011000 1110100 1100010 0110001 1011056 a.aa 000110101000111000110 0001011 例 2 所以，该信息码的线性分组编码为： 1101000 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 43 【 例 2】 已知线性 （ 6， 3） 码的生成矩阵为 1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 G 求线性分组码 、 各码组的码重 、 最小码距和 该码的差

40、错控制能力 。 解： 因为 k=3，所以信息码码组组成的矩阵为 （ 3 8阶）矩阵 D： 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 44 续 111 011 101 001 110 010 100 000 D 则由 Gaaa aaa rnn nn . . 21 021 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 45 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1

41、 0 0 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 0 0 0 C 可得出分组码码组矩阵为 码重 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 46 可见非零码组的最小码重为 3， 则分组码的最小码 距 dmin=3； 因此 ， 该分组码能够检 2位错；或同时纠 1位错 ， 检 1位错 。 例三 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 47 【 例 3】 已知一线性 (7， 4)码的生成矩阵为 求当接收端收到码组 R= 1010110 时 ， 所对应的信息码组 D。 10

42、11000 1110100 1100010 0110001 G 分析： 首先， 需要由 G推导出 H ； 然后， 通过 H计算 S； 再， 判断纠错。 解 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 48 解：根据前面 H与 G的关系 可得 将接收码组 R= 1010110 代入 ， 可得 S 100 010 001 101 111 110 011 T H 1001110 0100111 0011101 H 101 111 110 011 TP 1110 0111 1101 P 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 49 TRHS 0

43、1 01 0 01 1 11 1 0 S 111 第 7位出错 。 所以 ， 接收端收到码组 R=1010110 时 ， 所对应的 信息码组 D= 0010。 100 010 001 101 111 110 011 1010110 汉明码 ？ E、 S、 监督方程 、 P、 H、 G六者之间是相互关联 ，一一对应的 。 一个改变必然导致其它 5者相应变化 。 本题 S=111对应的是 a4出错 。 所以信息码应为 1000。 请大家验证一下 ！ 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 50 S1 S2 S3 错码位置 S1 S2 S3 错码位置 001 a0 11

44、1 a4 010 a1 011 a5 100 a2 110 a6 101 a3 000 无错码 03453 14562 23461 aaaaS aaaaS aaaaS 1001110 0100111 0011101 H 监督 矩阵 错误 图样 监督 方程 本题 S=111对应的是 a4出错 。 所以信息码应为 1000。 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 51 11.5.9 汉明码 12112 12 rr r rr n k n 11.5 线性分组码 第四讲 具有下列特点的线性分组码称之为 汉明码 ： 码长： n 2r 1， 信息位 k 2r-r-1， 监督位

45、： r n-k 记为：（ n， k）（ 2r 1， 2r 1 r ） 最小码距 dmin 3， 纠错能力 t 1 汉明码的 编码效率 ： 监督矩阵 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 52 汉明码的监督矩阵有 n列 r行 ， 它的 n列是除全零以 外的 r位码组构成 ， 且每一码组只在某列中出现一次 。 以 r=3为例 ， 可构造如下监督矩阵 3 1001011 0101110 0010111 I,PH 1101000 0110100 1110010 1010001 4 TP,IG 其编译码可直接根据 H、 G使用数字电路实现 。 其中 ， 译码方法采用计算校

46、正子 ， 然后确定错误图样 并加以纠正 。 编码器 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 53 0a 6a 4a 3a 2a 1a 5a 6a 4a 3a 5a编 码 器 译码器 Gaaaaaa rnnnn . 21021 356 345 456 0 1 2 aaaa aaaa aaaa 1011 1110 0111 P 编码器 方法 1： 方法 2： 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 54 03563 13452 24561 aaaaS aaaaS aaaaS S=BHT=EHT 译码器 扩展汉明码 译码器 方法 1： 方法

47、 2： H 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 55 *11.5.10 扩展汉明码 111 0 0 0 0 . e HH 11.5 线性分组码 1001011 0101110 0010111 H 11111111 0 0 0 1001011 0101110 0010111 eH 在汉明码中增加一位校验码 （ n， k） （ n 1， k） ， 对所有的位作偶监督 。 例：设原汉明码 （ 7， 4） ： a7a6a5a4 a3a2a1 a7a6a5a4 a3 a2a1 a0 信息位 监督位 信息位 原监督位 偶校验位 监督矩阵： H He 特点 2020年 11

48、月 16日 2时 45分 信电学院信息工程系 李世银 56 扩展汉明码特点： 0110 aa.aaS nn 11.5 线性分组码 校正子 S的确定方法与原汉明码校正子 S的确定 方法基本相同 。 只是新增了一个校正子 40 d 最小码距： 在纠正 1位误码的同时可以检测两为误码 。 在某些情况下也可以将 ， 汉明码的码长和信 息位缩短 ， 得到缩短汉明码 。 如 （ 5， 2） 交织码 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 57 *11.5.11 交织码 目的 ：减小信道中错误的相关性 ， 将长突发错误 离散成短突发错误或随机错误 。 措施 ：将 m个 （ n,

49、k） 分组码码组按 行排列成一个 m n的码阵 ， 从而得到一个 （ mn， mk） 交织码 ， 并规定以列的顺序 自左至右传送 。 mnmm n n aaa aaa aaa 21 22212 11211 mnm a,a,a,a,a,a 221212111 性能 ：如果 （ n,k） 可纠正 t个误码 ， 则 （ mn,mk） 可纠 正不大于 mt的单个突发错误 ， 或纠正 t个长度不 大于 m的突发错误 。 循环码 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 58 11.6.1 循环码的基本概念 （ 1） 定义 对线性分组码 T， 如对任意 Ti T， Ti 循环左

50、移或 循环右移任意位后得到的码组 Ti 仍然有 Ti T ， 则称 T 为循环码 。 （ 2） 码多项式 为用代数理论研究循环码 ， 可将码组用多项式表示 ， 该多项 式称为码多项式 。 一般地 ， 长为 n的码组 an-1an-2 a1a0， 对应码多项式 T(x) 11.6 循环码 012211 .)( axaxaxaxT nnnn 式中 ， xi 的系数对应码字中 ai的取值 。 例： （ 7,3）的一个码字： 1001110 对应 x6 x3 x2 x 码多项式的按模运算 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 59 所有 ， 在模运算下 ， 一整数 m按

51、模 n运 算等于其被 n除所得之数余数 。 npnpQnm npm m o d则记为： （ 3） 码多项式的按模运算 在整数除法中 ， 可进行按 n运算 ， 若 （ Q为整数 ， p n） （ 模 n） 码多项式的除法 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 60 类似地 ， 可以定义关于多项式 N(x)的除法运算 ， 若 )( )()( )( )( xN xRxQ xN xF )()()()( xRxNxQxF )(m o d)()( xNxRxF 1m o d1 nn xx 1n n x x 式中 Q(x)为整式 ， 余式 R(x)的幂 N(x)的幂 。 上式

52、可写成： 记为： 此时 ， 码多项式系数仍按模 2运算 ， 即只取 0和 1值 。 例：有 例 2 1111 11 nn n xx x 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 61 再如 1m o d11 3224 xxxxx 11 324 xm o d?xx 由于在模 2运算中，用加法代替了减法， 故余项 11 22 xx,xx 而是不是 定理 1 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 62 证明： 设 ， (1) i 1时 ， 有 定理 1 若 T(x)是长度为 n的循环码中的一个码多项 式 ， 则 xiT(x)按模 xn 1运

53、算的余式 T(x)必为 循环码中的另一码多项式 。 P343 0112211 .)( axaxaxaxT nnnn 1 . 1 )( 021121 n n n n n n x xaxaxaxa x xxT 102112 . nnn axaxaxaxT余式 可见余式是由码组 an-1an-2 a1a0左循环一位之后 的得到的码组： an-2 a1a0an-1 1 1 1021121 n n n n n n x axaxa.xaxa 1 10 2 1 1 2 1 n n n n n x axaxa.xaa 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 63 （ 接 定理 1

54、证明 ） ， 若 i 2 1 . 1 . 1 .1 1 )( 1 )( 21 2 0 3 1 1 3 21 1 2 0 3 12 1 10 2 1 1 21 2 n nn n n nn n n n n n n n n n n n nn x axaxaxaxa axa x xaxaxaxa xa x axaxaxaxax x xxTx x xTx 1 .)( 1 )( 2211011 n in i n i n in in n i x axaxaxaxaxQ x xTx 显然 ， 余式为 对应码组 an-1an-2 a1a0左循环两位之后的得 到的码组 。 一般地 ， 对任意 i有： 余式 an-

55、i-1an-i-2 a1a0an-1an-2 an-i+1an-i 对应 an-1an-2 a1a0左循环 i位之后的得到的码组 。 证毕 循环码生成多项式 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 64 11.6.2 循环码的生成多项式 g(x)及生成矩阵 定理 2 循环码中 ， n k 次码多项式 g(x)有且只有一个 。 g(x)称为循环码 码生成多项式 。 P343 证明 ： （ 1） 在含 K个信息位的循环码中 ， 除全 0码外 ， 其它码组最多 只有 k-1个连 0。 否则 ， 经循环移位后前面 k个信息码元全 为 0， 而监督码元不全为 0的码组 ，

56、这在线性分组码中是不 可能的 。 （ 2） n k次的码多项式 g(x)的常数项不能为 0， 否则该多项式 右移一位就会出现 k个连 0的情况 。 (因该码组前 k-1位为 0) （ 3） n k次的码多项式 g(x)只可能有一个 ， 若有两个 ， 两多项 式相加后由线性分组码的封闭性仍为码多项式 ， 但由于 n k次项和常数项相消 ， 会产生 k 1连 0的情况 ， 由 （ 1） 分析 ， 这是不可能的 。 综上 （ 1） 、 （ 2） 和 （ 3） ， 证毕 。 循环码生成矩阵 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 65 )x(g )x(xg . . . .

57、 . )x(gx )x(gx xG k k 2 1 循环码生成矩阵 G(x) 例 任一码多项式都可由其信息码元和生成矩阵 Gx确定 ： )( )( . )( )( .)( 2 1 2121 xg xxg xgx xgx aaaxGaaaxT k k knnnknnn )(.)()( 2211 xgaxgxaxgxa knknkn 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 66 例如表 11-5的 (7,3)循环码 ， n=7, k=3, r=4,唯一的一个 (n k) = 4次码多项式代表的码组是第二码组 0010111， 与它相对应的码多项式 ， 即生成多项式 定

58、理 3 1)( 24 xxxxg 其生成矩阵分别为 )( )( )( )( 2 xg xxg xgx xG 0010111 0101110 1011100 )( xG 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 67 11.6.2 循环码的生成多项式 g(x)及生成矩阵 (续 ) .)( 21 xGaaaxT knnn g(x)为码多项式 A(x)的一个因式 ， 所以 T(x)可被 g(x)整除 。 证毕 )(.)()( 2211 xgaxgxaxgxa knknkn )()()(.2211 xgxIxgaxaxa knknkn 循环码生成多项式（续）定理 4 推论

59、： 次数不大于 k 1次的任何多项式与 g(x)的乘 积都是码多项式 。 定理 3 在循环码中 ， 所有的码多项式 T(x)都能够被 g(x)整 除 。 P344 式 11.6-18 证明 ： 因为任一码多项式都可由其信息码元和生成矩阵 Gx确定 ： 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 68 11.6.2 循环码的生成多项式 g(x)及生成矩阵 (续 ) 定理 4 循环码 （ n， k） 的生成多项式 g(x)是 xn 1的一 个因式 。 1 )(1 1 )( nn k x xR x xgx )()(1)(1)( xgxhxxRxxgx nnk )()()()

60、()(1 xgxhxxgxhxgxx kkn 其中 R(x)的幂小于 n。 由定理 1， R(x)是码多项式 ， 又由定理 3， 有 R(x)=h(x)g(x)， 即有 移项整理得： 即 g(x)是 xn 1的一个因式 。 证毕 总结 证明 ：因为 g(x)幂为 n k， 因而可得 定理 1 若 T(x)是长度为 n的循环码中的一个码多项 式 ， 则 xiT(x)按模 xn 1运算的余式 T(i)(x)必 为循环码中的另一码多项式 。 定理 3 在循环码中 ， 所有的码多项式 T(x)都能够被 g(x)整除 。 2020年 11月 16日 2时 45分 信电学院信息工程系 李世银 69 11.6.2 循环码的生成多项式 g(x)及生成矩阵 (续 ) 总结： 监督多项式 定理 1 若 T(x)是长度为