通信原理_CH8编码.

1、南京理工大学南京理工大学通信工程系通信工程系 Nanjing University of Science and Technology Department of Communication Engineering1 通信原理通信原理 第八章第八章 差错控制编码差错控制编码 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.042 差错控制编码差错控制编码 n 数字通信系统数字通信系统 数字 信源 数字 调制 噪声源 解调终端信道

2、编 码 器 译 码 器 同步 信源编码 信道编码 p数字通信系统的主要指标是数字通信系统的主要指标是有效性和可靠性有效性和可靠性 p提高可靠性的措施提高可靠性的措施 针对加性干扰针对加性干扰 n调制解调方式、增大发射功率、加强天线方向性、提高接收机灵敏度等调制解调方式、增大发射功率、加强天线方向性、提高接收机灵敏度等 n信道编码（差错控制编码）信道编码（差错控制编码） p信道编码信道编码 n用适合信道传输的码进行传输，或对源码进行重编码，使不带规律性用适合信道传输的码进行传输，或对源码进行重编码，使不带规律性(或或 规律性不强规律性不强)的数字信号变成的数字信号变成带上规律性带上规律性(或加强

3、规律性或加强规律性)的数字信号的数字信号 n信道译码器则利用这些规律性来鉴别是否发生错误，或进而纠错信道译码器则利用这些规律性来鉴别是否发生错误，或进而纠错 n信道编码与信道的统计特性有关信道编码与信道的统计特性有关 在信息序列中在信息序列中 加入加入监督码元监督码元 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.043 差错控制编码差错控制编码 n 信道根据加性干扰引起错码的分布规律进行分类信道根据加性干扰引起错码的分布规律进

4、行分类 p随机信道随机信道 n信道中错码是随机的信道中错码是随机的, 且统计独立；且统计独立；（如高斯白噪声引起错码）（如高斯白噪声引起错码） p突发信道突发信道 n信道中错码成串集中出现；信道中错码成串集中出现；（如脉冲干扰引起错码）（如脉冲干扰引起错码） p混合信道混合信道 n信道中同时存在随机错误和突发错码，且都不能忽略不计信道中同时存在随机错误和突发错码，且都不能忽略不计 n 常用的差错控制技术常用的差错控制技术 p检错重发检错重发 p前向纠错前向纠错 p反馈校验法反馈校验法 不同类型的不同类型的 信道应该采信道应该采 用不同的差用不同的差 错控制技术错控制技术 检错码 判决信号 发收

5、 纠错码 发收 信息信号 信息信号 收发 （典型为（典型为ARQ） p检错删除检错删除 检错码 发收 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.044 本章的主要内容本章的主要内容 n 8.1 纠错编码的基本原理纠错编码的基本原理 n 8.2 常用的简单编码常用的简单编码 n 8.3 线性分组码线性分组码 n 8.4 循环码循环码 n 8.5 卷积码卷积码 Communication Principles Communica

6、tion Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.045 本章的主要内容本章的主要内容 n 8.1 纠错编码的基本原理纠错编码的基本原理 n 8.2 常用的简单编码常用的简单编码 n 8.3 线性分组码线性分组码 n 8.4 循环码循环码 n 8.5 卷积码卷积码 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.046 8.1 纠错编码

7、的基本原理纠错编码的基本原理 雹 雾 霜 雪 雨 阴 云 晴 111 011 101 001 110 010 100 000 种许使用 种中只准 4 8 码组许用码组，其它为禁用 雨 阴 云 晴 011 101 110 000 许用码组中，只要错一位许用码组中，只要错一位(不管哪位错不管哪位错) ，就是禁用码组，故这种编码能发现，就是禁用码组，故这种编码能发现 任何一位出错，但不能发现的二位出任何一位出错，但不能发现的二位出 错，二位出错后又产生许用码。错，二位出错后又产生许用码。 其中的任一码组在传输中其中的任一码组在传输中 若发生一个或多个错码，若发生一个或多个错码， 就会变成另一信息码，

8、接就会变成另一信息码，接 收端无法发现错误。收端无法发现错误。 这样的码组也不能这样的码组也不能纠正错纠正错 误，因为误，因为“晴晴”“”“雨雨”“”“ 阴阴”错一位，都可能变成错一位，都可能变成 “100” 1 1 1 0 0 0 雨 晴 若把若把8种组合（种组合（3位编位编 码）中，只取码）中，只取2种为种为 许用码，其它许用码，其它6种为种为 禁用码，则可纠错禁用码，则可纠错 例：收到禁用码组例：收到禁用码组“100”时，如认时，如认 为只有一位错，则可判断此错码为只有一位错，则可判断此错码 发生在第发生在第1位，从而纠正为位，从而纠正为“000”( 晴晴)，因为，因为“111”(雨雨)

9、发生任何一个发生任何一个 错误都不会变成错误都不会变成“100”。 信息位信息位 监督位监督位 p这种将信息码分组，为每组信码附加若干监督码的编码集合，称为这种将信息码分组，为每组信码附加若干监督码的编码集合，称为分分 组码组码。 信息位信息位 监督位监督位 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.047 8.1 纠错编码的基本原理纠错编码的基本原理 n 几个重要的参数几个重要的参数 p分组码一般用符号分组码一般用符号 (

10、n,k) 表示，表示， nk是每个码组二进制信息码元的数目，是每个码组二进制信息码元的数目， nn是编码组的总位数，又称为码组长度（是编码组的总位数，又称为码组长度（码长码长）。）。 nn-k=r为每码组中的监督码元数目，称监督位数目。为每码组中的监督码元数目，称监督位数目。 p码重码重：在分组码中，在分组码中， “1”的数目称为码组的重量，简称码重。的数目称为码组的重量，简称码重。 n例如，码组（例如，码组（1 1 0 1 0），码长），码长 n =5，码重为，码重为3。 p码距码距：把两个码组对应位不同的数目称为这两个码组的距离，简称：把两个码组对应位不同的数目称为这两个码组的距离，简称

11、码距，又称码距，又称汉明（汉明（ Hamming ）距离）距离。 n例如，码组（例如，码组（1 1 0 0 0）与（）与（1 0 0 1 1）的距离为）的距离为 3。 10011 11000 p最小码距最小码距：码组集合中，：码组集合中， 全体全体码组之间的距离的最码组之间的距离的最 小值称为最小码距小值称为最小码距(d0)。 011 101 110 000 雨 阴 云 晴 1 1 1 0 0 0 雨 晴 3 0 d2 0 d Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin

12、 2012.04RUI Yibin 2012.048 n圆上离圆上离 B 距离最近的码组是距离最近的码组是A 。 AB 0 d 8.1 纠错编码的基本原理纠错编码的基本原理 n 分组码的检错、纠错能力与最小码距的关系分组码的检错、纠错能力与最小码距的关系 p分组码能检测分组码能检测 e 个错码，所要求的最小码距个错码，所要求的最小码距 d0 ？ e n设有两个许用码设有两个许用码A、B，它们的码距为，它们的码距为d0 。 n若若 A 发生发生 e 个错误，则得到的码组与个错误，则得到的码组与A的的 距离为距离为e，即该码组落在以，即该码组落在以A为圆心，半径为圆心，半径 为为 e 的圆上。的圆

13、上。 n若要译码器不将若要译码器不将A 错判成错判成B，必须有：，必须有： 1, B Ad 1, 0 eBAdd即： 为检测为检测 e 个错码，要求最小码距个错码，要求最小码距 d0 应不小于应不小于 e+1 A Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.049 8.1 纠错编码的基本原理纠错编码的基本原理 p分组码能纠正分组码能纠正 t 个错码，所要求最小码距个错码，所要求最小码距 d0 ？ t n设有两个许用码设有两个许

14、用码A、B，它们的码距为，它们的码距为d0。 n若若 A 发生发生 t 个错误，则得到的码组与个错误，则得到的码组与A的的 距离为距离为t，即该码组落在以，即该码组落在以A为圆心，半径为圆心，半径 为为 t 的圆上。的圆上。 n这时，离这时，离 B 距离最近的码组是距离最近的码组是A 。 n根据根据最大似然的译码准则最大似然的译码准则，要想使译码器，要想使译码器 将将A正确译成正确译成A，必须，必须A 离离A比离比离B近。近。 BAdAAd, BAdAAdd, 0 即： 为纠正为纠正 t 个错码，要求最小码距个错码，要求最小码距 d0 应不小于应不小于 2t+1 t 0 d AB A t1 t

15、 1tt12 t n 分组码的检错、纠错能力与最小码距的关系分组码的检错、纠错能力与最小码距的关系 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0410 8.1 纠错编码的基本原理纠错编码的基本原理 p分组码能纠正分组码能纠正 t 个错码，同时检个错码，同时检 e 个错码，所要求的最小码距个错码，所要求的最小码距 d0？ e n设有两个许用码设有两个许用码A、B，它们的码距为，它们的码距为d0。 n若若 A 发生发生 e 个错

16、误，则得到码组落在以个错误，则得到码组落在以A为为 圆心，半径为圆心，半径为 e 的圆上。这时，离的圆上。这时，离 B 距离距离 最近的码组是最近的码组是A 。 nA离离B的距离必须至少为的距离必须至少为t+1，否则，否则， A将将 进入进入B的纠错能力范围内，而被错纠为的纠错能力范围内，而被错纠为B。 BAdAAdd, 0 即： 为纠正为纠正 t 个错码，同时检测个错码，同时检测 e 个错码，最小码距个错码，最小码距 d0 应不小于应不小于 e+t+1 t 0 d AB A 1te n 分组码的检错、纠错能力与最小码距的关系分组码的检错、纠错能力与最小码距的关系 在某些情况下，要求对于出现较

17、频繁但错码数很少的码组，按前向纠错方式工作，以在某些情况下，要求对于出现较频繁但错码数很少的码组，按前向纠错方式工作，以 节省反馈重发的时间。同时又希望对一些错码数较多的码组，在超过该码的纠错能力节省反馈重发的时间。同时又希望对一些错码数较多的码组，在超过该码的纠错能力 后，能检测出来，再按检错重发方式工作。这种工作方式称为后，能检测出来，再按检错重发方式工作。这种工作方式称为纠检结合纠检结合。 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibi

18、n 2012.0411 8.1 纠错编码的基本原理纠错编码的基本原理 n 结论结论：分组码纠错、检错能力决定于最小码距：分组码纠错、检错能力决定于最小码距d0 p检错能力：检错能力： p纠错能力：纠错能力： 1 0 de 2 1 int 0 d t 011 101 110 000 雨 阴 云 晴 1 1 1 0 0 0 雨 晴 3 0 d 2 0 d11 0 de 能检一位错码能检一位错码 21 0 de 1 2 1 int 0 d t 能检能检 2 位错码位错码 能纠能纠 1 位错码位错码 Communication Principles Communication Principles C

19、hapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0412 8.1 纠错编码的基本原理纠错编码的基本原理 n 纠错编码的效用纠错编码的效用 p设随机信道中发送设随机信道中发送“0”、“1”时的错误概率均为时的错误概率均为 p (p1)，则在码长，则在码长 为为 n 的码组中有的码组中有r 位发生错码的概率为：位发生错码的概率为： rnrr nn ppCrP 1 时，当 3 107 pn r p rnr n ! ! 3 7 10771 pP 52 7 101 . 2212 pP 83 7 105 . 3353 pP p可见，采用纠错编

20、码，即使仅能纠正（或检测）码组中可见，采用纠错编码，即使仅能纠正（或检测）码组中 12 个错误，个错误， 也可以使误码率下降几个数量级。也可以使误码率下降几个数量级。 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0413 本章的主要内容本章的主要内容 n 8.1 纠错编码的基本原理纠错编码的基本原理 n 8.2 常用的简单编码常用的简单编码 n 8.3 线性分组码线性分组码 n 8.4 循环码循环码 n 8.5 卷积码卷积码

21、Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0414 8.2 常用的简单编码常用的简单编码 n 奇偶校验码奇偶校验码 p奇偶校验码分为奇偶校验码分为奇校验码奇校验码、偶校验码偶校验码两种两种 p编码规则编码规则 无论信息位有多少，只有无论信息位有多少，只有一位监督位一位监督位，且对，且对an-1 an-2 a1 a0的码组，有的码组，有 如下监督关系：如下监督关系： 0 021 aaa nn 偶校验： 1 021 aaa nn

22、 奇校验： n如：对信息码组如：对信息码组 11001 进行偶校验编码进行偶校验编码 校验位校验位 信息位信息位 1 1 0 0 1 0 p检错能力检错能力 n能检测奇数位错误能检测奇数位错误。 1 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0415 8.2 常用的简单编码常用的简单编码 n 二维奇偶校验码二维奇偶校验码 行监督位行监督位 列监督位列监督位 0110011 0100010 p检纠错能力检纠错能力 n能检测奇数

23、位错误及部分偶数位错误（如：能检测奇数位错误及部分偶数位错误（如：4位错码构成矩形位错码构成矩形不能不能检测）检测） n当码组中仅在当码组中仅在一行一行有奇数个错误时，能够确定错码的位置，从而实现纠有奇数个错误时，能够确定错码的位置，从而实现纠 错错 n适于检测适于检测突发错误突发错误 0 0 1 1 p又称方阵码，将奇偶校验码按行组成矩阵，然后在列方向增加第二维又称方阵码，将奇偶校验码按行组成矩阵，然后在列方向增加第二维 奇偶校验位。奇偶校验位。 001111 100001 110011 111001 010111 110011 Communication Principles Commun

24、ication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0416 8.2 常用的简单编码常用的简单编码 n 恒比码恒比码 p每个码组均含有相同数目的每个码组均含有相同数目的“1”和和“0”。由于。由于“1”的数目与的数目与“0”的数的数 目之比保持恒定，所以称为恒比码。目之比保持恒定，所以称为恒比码。 n例如，我国电传机传输阿拉伯数字时，用例如，我国电传机传输阿拉伯数字时，用5位代码表示，每个码组的长位代码表示，每个码组的长 度为度为5，其中恒有，其中恒有3个个“1”，称为，称为 “5中取中取3”

25、恒比码。恒比码。 阿拉伯数字阿拉伯数字保护电码保护电码阿拉伯数字阿拉伯数字保护电码保护电码 1 2 3 4 5 01011 11001 10110 11010 00111 6 7 8 9 0 10101 11100 01110 10011 01101 p主要优点主要优点 简单，适于用来传输电传机或其它键盘设备产生的字母和符号。简单，适于用来传输电传机或其它键盘设备产生的字母和符号。 p检错能力检错能力 能检测所有奇数个错误和部分偶数个错误（除去能检测所有奇数个错误和部分偶数个错误（除去“0”、“1”对换外对换外 的偶数个错误都可检测）。的偶数个错误都可检测）。 Communication Pr

26、inciples Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0417 8.2 常用的简单编码常用的简单编码 n 正反码正反码 p正反码的监督位与信息位数目相同。监督码元与信息码元相同或相正反码的监督位与信息位数目相同。监督码元与信息码元相同或相 反，由信息码中反，由信息码中“1”的个数决定。的个数决定。 p正反码是一种简单的能纠错的编码，长度为正反码是一种简单的能纠错的编码，长度为10的正反码具有纠正的正反码具有纠正1位错位错 码的能力，并能检测全部两位以下的错码和大部分两

27、位以上的错码。码的能力，并能检测全部两位以下的错码和大部分两位以上的错码。 p电报通信中的正反码电报通信中的正反码 n信息位段有信息位段有奇数奇数个个1 1 1 0 0 1 1 1 0 0 1 （监督位与信息位（监督位与信息位重复重复） n信息位段有信息位段有偶数偶数个个1 1 0 0 0 1 0 1 1 1 0 （监督位是信息位（监督位是信息位反码反码） Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0418 本章的主要内容本

28、章的主要内容 n 8.1 纠错编码的基本原理纠错编码的基本原理 n 8.2 常用的简单编码常用的简单编码 n 8.3 线性分组码线性分组码 n 8.4 循环码循环码 n 8.5 卷积码卷积码 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0419 8.3 线性分组码线性分组码 n 基本概念基本概念 0 021 aaa nn 偶校验： p代数码和线性分组码代数码和线性分组码 n建立在代数关系基础上的编码称代数码建立在代数关系基础上

29、的编码称代数码 n可用线性方程组（代数关系）表述码的规律性的分组码称为线性分组码可用线性方程组（代数关系）表述码的规律性的分组码称为线性分组码 p编码与监督编码与监督 n偶校验码在接收端实际上计算代数关系式偶校验码在接收端实际上计算代数关系式 S = an-1 an-2 a0 n如果监督位增加到二位，就能增加一个类似于偶校验码的如果监督位增加到二位，就能增加一个类似于偶校验码的新新的监督式的监督式 n两个监督式的两个校正子有两个监督式的两个校正子有4种可能的组合：种可能的组合：00, 01, 10, 11。若用。若用1种组种组 合表示无错，其余合表示无错，其余3种组合就可以用来表示一位错码的种

30、组合就可以用来表示一位错码的3种不同位置。种不同位置。 n同理，同理，r个监督式能指示一位错码的个监督式能指示一位错码的2r-1个可能位置。个可能位置。 n对于线性分组码对于线性分组码(n,k)，监督位数，监督位数r=n-k，如果希望用，如果希望用r个监督关系式指示个监督关系式指示 一位错码一位错码的的n种可能的位置，则要求种可能的位置，则要求 监督关系式监督关系式 校正子校正子 n r 1212rk r 有错， 无错 1 , 0 只能发现错误，不只能发现错误，不 能指示错误位置能指示错误位置 汉明码的诞生汉明码的诞生 Communication Principles Communicatio

31、n Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0420 8.3.1 汉明码汉明码 n 基本概念基本概念 p线性分组码线性分组码(n,k)，监督位，监督位r=n-k，若满足，若满足n=2r-1，则称其为，则称其为汉明码汉明码 p汉明码是能够汉明码是能够纠正一位错码纠正一位错码且编码效率最高的一种线性分组码。且编码效率最高的一种线性分组码。 n 监督关系式的构造监督关系式的构造 p以以(n,k)=(7,4)的汉明码的汉明码(r=3)为例，现规定为例，现规定3个校正子的组合个校正子的组合 S1,S2,S3错

32、码位置错码位置S1,S2,S3错码位置错码位置 0 0 1a01 0 1a4 0 1 0a11 1 0a5 1 0 0a21 1 1a6 0 1 1a30 0 0无无 错错 03463 13562 24561 aaaaS aaaaS aaaaS 监督位的取值应使：监督位的取值应使： S1S2S3=000，所以监督关系式为所以监督关系式为 0 0 0 0346 1356 2456 aaaa aaaa aaaa 3460 3561 4562 aaaa aaaa aaaa 用码率用码率R衡量，衡量，Rk/n Communication Principles Communication Princip

33、les Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0421 8.3.1 汉明码汉明码 n 编码原理编码原理 信息位信息位 a6a5a4a3 监督位监督位 a2a1a0 信息位信息位 a6a5a4a3 监督位监督位 a2a1a0 00000001000111 00010111001100 00101011010010 00111101011001 01001101100001 01011011101010 01100111110100 01110001111111 3460 3561 4562 aaaa aaaa aaaa

34、p给定信息位后，根据监督给定信息位后，根据监督 关系可以算出监督位。关系可以算出监督位。 p接收端收到码组后，先计算接收端收到码组后，先计算 出校正子出校正子S1S2S3，再按规定，再按规定 判断有无错码或错码位置，判断有无错码或错码位置， 最后纠正错码。最后纠正错码。 0000011 接收码组： S1,S2,S3错码位置错码位置S1,S2,S3错码位置错码位置 0 0 1a01 0 1a4 0 1 0a11 1 0a5 1 0 0a21 1 1a6 0 1 1a30 0 0无无 错错 03463 13562 24561 aaaaS aaaaS aaaaS 011 321 ：SSS 00010

35、11 纠正后码组： a3出错出错 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0422 8.3.1 汉明码汉明码 n (7,4)汉明码汉明码 信息位信息位 a6a5a4a3 监督位监督位 a2a1a0 信息位信息位 a6a5a4a3 监督位监督位 a2a1a0 00000001000111 00010111001100 00101011010010 00111101011001 01001101100001 010110111

36、01010 01100111110100 01110001111111 p最小码距最小码距 d0=3 p检错能力检错能力 e=d01=2 p纠错能力纠错能力 t=int(d01)/2=1 p编码效率编码效率 12 12 r r r n k R 12 1 r r 。接近很大时，1Rn Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0423 8.3.2 线性分组码的一般原理线性分组码的一般原理 n 监督矩阵和生成矩阵监督矩阵和生成矩

37、阵线性分组码的编码线性分组码的编码 p将上述汉明码将上述汉明码(7, 4)的监督关系式改写的监督关系式改写 01001101 00101011 00010111 0123456 0123456 0123456 aaaaaaa aaaaaaa aaaaaaa “+”均为均为 模模2加加 ）（模2 0 0 0 1001101 0101011 0010111 0 1 2 3 4 5 6 a a a a a a a TT AHO 0 T HA或 1001101 0101011 0010111 H nr 3456 aaaa 012 aaa r k 阶矩阵阶矩阵P r r 阶单位方阵阶单位方阵Ir r P

38、I 具有具有PIr形式的形式的H 矩阵矩阵 称为称为典型监督矩阵典型监督矩阵 H AT p监督矩阵监督矩阵 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0424 8.3.2 线性分组码的一般原理线性分组码的一般原理 n 监督矩阵和生成矩阵监督矩阵和生成矩阵 p把监督关系式改写为：把监督关系式改写为： 3460 3561 4562 33 44 55 66 aaaa aaaa aaaa aa aa aa aa 3 4 5 6 0

39、1 2 3 4 5 6 1101 1011 0111 1000 0100 0010 0001 a a a a a a a a a a a 3 4 5 6 a a a a GA TT GaaaaA 3456 1101000 1010100 0110010 1110001 G k r 阶矩阵阶矩阵Q Q=PT k k 阶单阶单 位方阵位方阵Ik QIk 具有具有IkQ形式的形式的G 矩阵矩阵 称为典型生成矩阵称为典型生成矩阵 GT p生成矩阵生成矩阵 这种前这种前k位是信息码元，后位是信息码元，后r 位是监督码元位是监督码元(附加于信息码附加于信息码 元之后元之后)的码称为的码称为系统码系统码。

40、T k r PIG IPH 1001101 0101011 0010111 H Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0425 8.3.2 线性分组码的一般原理线性分组码的一般原理 n 校正子校正子S（伴随式）（伴随式） 线性分组码的译码线性分组码的译码 p设发送码组为：设发送码组为：A=an-1,an-2,a1,a0 接收码组为：接收码组为：B=bn-1,bn-2,b1,b0 p发送码组与接收码组之差发送码组与接收码组

41、之差(称称错误图样错误图样)为：为：E = A B = en-1,en-2,e1,e0 模模2操作操作 bi=ai 时时, ei=0, 正确正确 bi ai 时时, ei=1, 错码错码 EAB p令令S=B H T，S为校正子，也称为校正子，也称伴随式伴随式 T HBS T EH T HEA)( TT EHAH 0 由此可见由此可见，校正子，校正子S与错误图样与错误图样E 间有确定间有确定 的线性变换关系，若的线性变换关系，若S和和E之间一一对应，则之间一一对应，则 S将能代表错码的位置。将能代表错码的位置。 p接收端译码器的任务接收端译码器的任务 n根据接收码组根据接收码组 B 计算校正子

42、计算校正子 S=BHT； n从校正子从校正子S 确定错误图样；确定错误图样； n从接收到的码字中减去错误图样从接收到的码字中减去错误图样E。 n 线性分组码具有封闭性线性分组码具有封闭性 错误错误 码位码位 错误图样错误图样校正子校正子 en-1,en-2,e1,e0S2,S1,S0 0 0 0 0 0 0 00 0 0 b0 0 0 0 0 0 0 10 0 1 b1 0 0 0 0 0 1 00 1 0 b2 0 0 0 0 1 0 01 0 0 b3 0 0 0 1 0 0 00 1 1 b4 0 0 1 0 0 0 01 0 1 b5 0 1 0 0 0 0 01 1 0 b6 1 0

43、 0 0 0 0 01 1 1 码集中任两个码字模码集中任两个码字模 二加后仍在码集中二加后仍在码集中 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0426 本章的主要内容本章的主要内容 n 8.1 纠错编码的基本原理纠错编码的基本原理 n 8.2 常用的简单编码常用的简单编码 n 8.3 线性分组码线性分组码 n 8.4 循环码循环码 n 8.5 卷积码卷积码 Communication Principles Communi

44、cation Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0427 8.4 循环码循环码 n 循环码的特点循环码的特点 p循环码是一种分组的线性系统码循环码是一种分组的线性系统码 p循环码除了有线性分组码的封闭性外，还有循环性循环码除了有线性分组码的封闭性外，还有循环性 码集中任一码循环移码集中任一码循环移 位后仍在码集中位后仍在码集中 ),(, 0121 knaaaaA nn 码集若 12101 ,aaaaA n 循环右移一位：),(kn码集 10322 , nnn aaaaA循环左移一位：),(kn

45、码集 p是一类重要的线性分组码，比较方便用移位寄存器实现编码和译码是一类重要的线性分组码，比较方便用移位寄存器实现编码和译码 信息位信息位 a6a5a4 监督位监督位 a3a2a1a0 信息位信息位 a6a5a4 监督位监督位 a3a2a1a0 00000001001011 00101111011100 01011101100101 01110011110010 n (7, 3)循环码的码集循环码的码集 n 通常为了研究方便，我们用通常为了研究方便，我们用 代数多项式代数多项式来表示码字。来表示码字。 右移右移1位位 Communication Principles Communication

46、 Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0428 8.4.1 码多项式码多项式 n 码多项式的基本概念码多项式的基本概念 p用以表示码字的一个用以表示码字的一个代数多项式代数多项式称为码多项式。称为码多项式。 0121 ,),(aaaaAkn nn 循环码的一个码字为： 01 2 2 1 1 axaxaxaxA n n n n 对应的码多项式为： 多项式的系多项式的系 数数ai对应于对应于 码元的值。码元的值。 p码左移一位，对应于码多项式乘以码左移一位，对应于码多项式乘以 x 1 , 0 , 1

47、 , 1 , 1 , 0 , 0 1 A 0 , 1 , 0 , 1 , 1 , 1 , 0 3 A 1 234 1 xxxxA xxxxxA 345 3 xxAxA 13 n 码多项式的按模运算码多项式的按模运算 p若一任意多项式若一任意多项式F(x)被一个被一个n 次多项式次多项式N(x)除，得到商式除，得到商式Q(x)和一个和一个 次数小于次数小于n的余式的余式R(x)，即，即 xRxQxNxF 则称则称R(x)为为F(x) 关于关于N(x)按模运算的结果，按模运算的结果， xNxRxF模 p例例 1 24 xx 1 3 x x xx 4 1 2 xx 1 11 3224 xxxxx模

48、最高次幂最高次幂 为为x n-1 左移一位左移一位 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0429 8.4.2 生成多项式与生成矩阵生成多项式与生成矩阵 n 生成多项式生成多项式 p在在(n,k)循环码码集所对应的码多项式中，循环码码集所对应的码多项式中，唯一唯一的一个的一个常数项不为常数项不为0的的 (n-k)次次多项式多项式g(x) 称为该循环码的生成多项式称为该循环码的生成多项式 信息位信息位 a6a5a4 监督位

49、监督位 a3a2a1a0 信息位信息位 a6a5a4 监督位监督位 a3a2a1a0 00000001001011 00101111011100 01011101100101 01110011110010 例：例：(7,3)循环码的生成多项式循环码的生成多项式 1 24 xxxxg xg xxg xgx xgx xG k k 2 1 p循环码的码多项式循环码的码多项式都是都是生成多生成多 项式的项式的倍式倍式 xQxgxAi n 生成矩阵生成矩阵G p将生成多项式将生成多项式逐次移位逐次移位，得到，得到k个线性无关个线性无关的码多项式，将它们构成矩的码多项式，将它们构成矩 阵，称为生成多项式矩

50、阵阵，称为生成多项式矩阵G(x)，其系数就是生成矩阵，其系数就是生成矩阵G。 例：例：(7,3)循环码的循环码的生成多项式矩阵和生成矩阵生成多项式矩阵和生成矩阵 xg xxg xgx xG 2 1 24 235 2346 xxx xxxx xxxx 0010111 0101110 1011100 G Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0430 8.4.3 如何寻找如何寻找(n,k)循环码的生成多项式循环码的生成多项式

51、 n 对于对于(n,k)循环码，将循环码，将xn+1因式分解因式分解(系数模二运算系数模二运算)，其中最高，其中最高 幂次数为幂次数为r=n-k，且常数项为，且常数项为1的因子多项式，就是的因子多项式，就是(n,k)循环码循环码 的生成多项式。的生成多项式。 p例：例：x7+1因式分解因式分解 1111 3237 xxxxxx 为了求为了求(7,3)循环码的生成多项式，就要在上式中找一个最高幂次数为循环码的生成多项式，就要在上式中找一个最高幂次数为 r=n-k=4，且常数项为，且常数项为1的因子。这样的因子有两个：的因子。这样的因子有两个： 111 2343 xxxxxx 111 2423 x

52、xxxxx 这两个多项式这两个多项式都可以都可以作为生成多项式用，作为生成多项式用，但但不同生成多项式所产生的不同生成多项式所产生的 循环码码组也不同循环码码组也不同。 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0431 8.4.4 系统循环码的编码电路系统循环码的编码电路 p若若k位信息码为：位信息码为： M=mk-1,mk-2,m1,m0，则，则信息码多项式信息码多项式为：为： 01 2 2 1 1 mxmxmxmxm

53、k k k k xrxmxxA kn 系统码： 码多项式码多项式 xgxmxA p系统码（系统码（前前k 位是信息码元，后位是信息码元，后r 位是监督码元位是监督码元）的生成矩阵是典型生成）的生成矩阵是典型生成 矩阵，具有矩阵，具有IkQ的形式。的形式。由生成多项式矩阵直接得到的生成矩阵不具由生成多项式矩阵直接得到的生成矩阵不具 有这样的形式，不是系统码有这样的形式，不是系统码。 xrxmxxA kn xgxrxgxmxxA kn mod mod r(x)的最高次是的最高次是r 1， g(x)的最高次是的最高次是r，所以，所以 ，r(x) mod g(x)=r(x) xgxmxxAxr kn

54、mod xgxmxA 循环码： xgxmxxgxm kn mod xgxmx kn mod xgxmxxmxxA knkn mod 系统循环码： r(x)是监督码多项式是监督码多项式 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0432 8.4.4 系统循环码的编码电路系统循环码的编码电路 n 编码电路原理编码电路原理 xgxmxxmxxA knkn mod p以以(7,3)循环码为例循环码为例 1 24 xxxxg 1 0

55、g 1 1 g1 2 g0 3 g 1 4 g 移位寄存器移位寄存器 除法电路，完成除法电路，完成 mod g(x)操作操作 输入输入 m 移存器移存器 abcd 反馈反馈 e 输出输出 f 0000000 1 1 0 1110 1001 1010 1 1 1 1 1 f=m 0 0 0 0 0 0101 0010 0001 0000 0 1 0 1 0 1 0 f=e 1 p工作步骤工作步骤 所有移存器清零；所有移存器清零； 开关开关S 倒向下，输入信码一方面送入倒向下，输入信码一方面送入 除法电路进行运算，一方面直接输出。除法电路进行运算，一方面直接输出。 在信息位全部进入除法器后，开关转

56、在信息位全部进入除法器后，开关转 向上，切断反馈线，除法电路停止，同向上，切断反馈线，除法电路停止，同 时输出端接到移存器，将除法电路计算时输出端接到移存器，将除法电路计算 得到的监督位依次输出。得到的监督位依次输出。 1 1 mod 2 2424 x xxxxxx abcd 输入 m S e f 输出 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0433 8.4.5 系统循环码的译码电路系统循环码的译码电路 n 伴随多项式伴

57、随多项式 xgxRxS mod xgxExA mod xgxE mod p以以(7,3)循环码为例循环码为例 1 24 xxxxg 输入输入 m 移存器移存器 abcd 与门与门 输出输出 000000 1 0 0 0 1 0 1 1110 0111 1101 1000 1010 0101 0010 0 0 0 0 0 0 0 0 0 0001 0000 1 0 p工作步骤：工作步骤： 所有移存器清零；所有移存器清零； 假定接收码组为假定接收码组为“1000101”，此码组进入除法电路后，此码组进入除法电路后 ，移位寄存器各级的状态变化过程如左表。当此码组的，移位寄存器各级的状态变化过程如左表

58、。当此码组的7 个码元全部进入除法电路后，除法结果个码元全部进入除法电路后，除法结果（自右向左自右向左）为为 “0100”，表明接收码组的第二位是错码。表明接收码组的第二位是错码。 保持输入恒为保持输入恒为“0”，将缓冲寄存器中暂存的信码逐位，将缓冲寄存器中暂存的信码逐位 移出。在信码的第移出。在信码的第2位移出时，反馈移位寄存器的状态为位移出时，反馈移位寄存器的状态为 “1000”，与门输出，与门输出“1”，纠正错码，并对寄存器清零。，纠正错码，并对寄存器清零。 abcd 输入 m f 输出 与门与门 缓冲移位寄存器缓冲移位寄存器 a b c d 一般情况下，码组不是孤立的一般情况下，码组不

59、是孤立的 ，因此需要两套除法电路。，因此需要两套除法电路。 Communication Principles Communication Principles Chapter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0434 本章的主要内容本章的主要内容 n 8.1 纠错编码的基本原理纠错编码的基本原理 n 8.2 常用的简单编码常用的简单编码 n 8.3 线性分组码线性分组码 n 8.4 循环码循环码 n 8.5 卷积码卷积码 Communication Principles Communication Principles Chap

60、ter 8 Channel Coding RUI Yibin 2012.04RUI Yibin 2012.0435 8.5 卷积码卷积码 n 卷积码的概念卷积码的概念 p又称连环码，其监督位由当前码组及其前又称连环码，其监督位由当前码组及其前 N 1 个码组的信息位决定，个码组的信息位决定， 即由即由 N 个码组的信息位决定个码组的信息位决定 p卷积码记作卷积码记作(n,k,N) nn码组的码元数，即码字的字长；码组的码元数，即码字的字长； nk一个码组中的信息位的个数；一个码组中的信息位的个数； nN卷积码的编码约束度（卷积码的编码约束度（nN称为编码约束长度），即确定一个监督称为编码约束长