第7章-物联网通信技术(曾宪武)LXX2014.7

1、第7章差错控制技术1 1第7章差错控制技术7.1差错控制技术概述差错控制技术概述7.2差错控制方法差错控制方法7.3常用检错码常用检错码7.4循环码循环码7.5卷积码卷积码本章小结本章小结第7章差错控制技术2 27.1 差错控制技术概述差错控制技术概述7.1.1 差错控制的基本原理差错控制的基本原理在二进制编码中， 1位二进制编码可表示2种不同的状态， 2位二进制编码可表示4种不同的状态， n位二进制编码可以表示2n种不同的状态。 在n位二进制编码的2n种不同的状态中， 能表示有用信息的码组称为许用码组， 不能表示有用信息的码组称为禁用码组。 第7章差错控制技术3 3现以3位二进制编码构成的码

2、组集合000, 001, 010, 011, 100, 101,110, 111为例， 分三种情况讨论。 （1） 情况1。 若8个状态都表示有用信息， 即均是许用码组， 则其中任一码字出错都将变成另一个码字， 于是， 接收端无法识别哪个出错。 第7章差错控制技术4 4（2） 情况2。若只取4个状态， 则取000、 011、 101、 110表示许用码组， 001、 100、 010、 111表示禁用码组。如果000中错1位， 那么可能变为001、 100、 010中的任一个， 而这三个均是禁用码组， 可知传输出错。 当000出现三个错误时， 将变为111， 也是禁用码； 当000出现两个错误时

3、， 将变为011、 110、 101， 它们均是许用码， 可见在接收端无法发现错误。 从上述分析可以看出， 采用这种方法可以发现部分差错， 但不能纠错。 又如， 在接收端收到100， 尽管可以知道是一个错码， 但000、 101和110在发生一位错码的情况下均可以是100。 第7章差错控制技术5 5（3）情况3。 若要纠正错码， 就需增加冗余。 如果仅取000和111表示许用码组， 其他为禁用码组， 那么可以检验出2个错码， 并能纠正1个错码。 例如， 收到100时， 若只有一个错码， 则可以判断错码在第一位， 并纠正为000， 因为111的任何一位误码均不会为100， 而可能为011、101

4、或110； 但若假设误码数不超过2位， 则存在两种可能， 即000错1位和111错2位， 均可能变为100， 因此只能检测出错误， 而无法纠错。 第7章差错控制技术6 67.1.2 差错控制编码的特性与能力差错控制编码的特性与能力差错控制编码的能力与差错控制编码的特性有关。 编码的特性主要包括码字的汉明重量、 码间距离和最小码距。 我们用C表示由许多码元Ci(0in1)构成的码字， 码字中码元的个数用n表示。 以下先介绍汉明重量、 码间距离和最小码距的概念。第7章差错控制技术7 71. 码字的汉明重量(Hamming Weight)码字C=Cn1Cn2C0的汉明重量是指码字中非零码元的个数，

5、用HW(C)表示。 例如， 1101的汉明重量为3（可写成HW(1101)=3）， HW(110101)=4。 第7章差错控制技术8 82. 码间距离(d)码间距离又称为海明距离， 是指一码组集合中任意两个码字之间的对应位上码元不同的个数，用d表示， 可表示为式中， Ci、Cj分别表示码组集合中的任意两个码组（码字）， Ci=Cin1Cin2Ci0。 例如， 对于两个码字1101和0111， =1+0+1+0=2d(10101, 11010)=4。 第7章差错控制技术9 93. 最小码距在一个码组集合(C1，C2， ， CN）中， 各码字之间的距离可能是不相同的， 就称该码组集合中最小的码距为

6、最小码距， 用d0表示。 例如， 对于码组集合(0111100, 1011011, 1101001)， d(0111100, 1011011)=5， d(0111100, 1101001)=4， d(1011011, 1101001)=3，于是最小码距d0=3。第7章差错控制技术10 10在分析一组码字（码组）的检错纠错能力时， 总用最小码距d0来衡量， 这是一种最不利的情况。 在3位二进制码中， 把8个码字的许用码变为4个码字许用码就具有了纠错能力， 这是因为这8个码字的d0=1， 而在000， 001,101,110中， 它们的d0=2， 在000,111中它们的d0=3。 由此可见， 码

7、组集合中的最小码距d0不同， 纠错检错的能力不同， 码组集合中的最小码距越大， 其纠错检错的能力也就越强。 第7章差错控制技术11 114. 编码纠错检错能力与最小码距d0的关系差错控制编码的抗干扰能力与码的结构有关， 一种编码的结构是与它们的码距有关的， 码距的长度可以反映出该种编码方式抗干扰的能力， 码距与纠错检错能力之间的关系可用如下定理表述。 第7章差错控制技术12 12定理7.1.1 若一种码的最小码距为d0， 则它能检查传输差错个数（或称为检错能力）e应满足d0e+1。 由定理7.1.1可知， 对于3位二进制编码， 8个码字均是许用码时， d0=1， 于是e=0，这说明该码没有差错

8、能力； 当使用4个码字时， d0=2， 则e=1， 说明能查出1个差错；若取2个码字时， d0=3， 则e=2， 说明能查出2个差错。 因此， 要想使传输的码字具有检错能力， 该码组集合的最小码距必须大于或等于2。第7章差错控制技术13 13定理 7.1.2 若一种码的最小距离为d0， 则它能纠正传输差错的个数（又称为纠错能力）t应满足d02t+1。 定理7.1.3 若一种码的最小距离为d0， 则它能检查e个差错， 同时又能纠正t个以下差错的条件为d0t+e+1。 定理7.1.3说明， 当传输差错等于或小于t时， 该码可以自动纠正这些差错， 但当差错大于t而又小于e时， 该码只能检测出错来。

9、第7章差错控制技术14 14例7.1.1 求码组集合000,011,101,110和000,111的纠错检错能力。 解 码组集合000,001,101,110的最小距离d0=2， e=d01=1， 由定理7.1.1可知， 能检查出一个错。 对于000,111， d0=3， e=d01=2， 可以查出2个错。 由定理7.1.2可知，t=1， 能纠正一个错。第7章差错控制技术15 155. 编码效率控制差错编码需要加入一定的监督码才能进行差错控制， 该编码方式属于分组编码的一种。在编码时， 加入的监督码位数越多， 其纠错的能力也越强， 但同时降低了编码效率。 若码长用n表示， 其中的信息码的长度为

10、k， 监督码的长度为r， 则有n=k+r， 于是， 编码效率为第7章差错控制技术16 167.2 差错控制方法差错控制方法7.2.1 自动请求重发自动请求重发(ARQ)方式方式由于采用检错编码时， 系统仅能发现传输错误， 而不知道错误发生的确切位置， 因此需要采用自动请求重发工作方式。 接收端根据校验序列的编码规则判断所接收的数据是否发生传输错误， 并把判断结果通过反馈信道传送给发送端。 接收端判断的结果有三种可能： 第7章差错控制技术17 17第一种是肯定确认， 即接收端对收到的校验帧校验后未发现错误， 会向发送端发送一个肯定确认信号， 用ACK表示， 发送端收到ACK信号后即可知道该帧发送

11、成功。 第二种是否定确认。 接收端收到一个帧后， 经校验发现有错误， 则回送一个否定确认信号，用NAK表示， 发送端收到NAK信号后必须重发该帧。 第7章差错控制技术18 18第三种是超时重发。 发送端在发出一个帧后开始计时， 如果在规定的时间内没有收到该帧的确认信号（ACK或NAK）， 则认为发生帧的丢失或确认信号丢失， 必须重发该帧。 在传送数据时， 发送需经过发送、 等待、 确认这三个阶段， 即所谓的“停等ARQ”。 在数据帧的发送中， 发送端每次仅发送缓冲区中的一个数据帧， 并在发送后立即启动定时器， 等待接收端回送的确认帧。 第7章差错控制技术19 19定时器启动后， 如在规定的时间

12、内没有收到确认信息帧， 则认为发生帧的丢失或确认信号丢失， 需要重新发送。 假如在规定的时间没有收到确认信息， 系统就会自动重发， 重发会造成重复帧的现象， 即可能发生没有出错的数据帧重复发送到接收端的情况。 为了解决重复帧的问题， 可在每个数据帧的帧头增加一个发送序号， 当收到重复帧时， 根据序号可将重复的帧丢弃掉。第7章差错控制技术2020为了提高传输效率， 人们提出了连续重发请求(Continuous ARQ )技术， 该技术的特点是不等待前一帧的确认， 而直接发送下一帧。 这样可能会出现发送端未发现出错之前， 就有很多帧到达接收端， 而接收端会将这些帧丢弃。 为解决连续重发请求中出现的

13、问题， 人们提出了返回N帧ARQ及选择性重发ARQ技术。 第7章差错控制技术21 21ARQ方式具有以下特点： （1） 只需要少量的冗余码元就可获得较高的传输可靠性。（2） 与前向纠错相比， 复杂性和成本较低。（3） ARQ方式要求有反馈信道， 因此不能用于单向传输和同步传输。 （4） 控制规程及控制过程较复杂， 系统重复传帧的现象较严重， 通信效率低， 不适合实时性要求高的场合。 第7章差错控制技术22227.2.2 前向纠错前向纠错(FEC)方式方式FEC是利用纠错编码使接收端的译码器发现错误并准确地判断出出错的位置， 从而能自动纠正的差错控制方式。 FEC方式具有如下特点： （1） 实时

14、性高， 无限反馈信道， 特别适合于单向多点同时传送， 控制规则简单， 但译码设备较复杂。（2） 纠错码的冗余度较高， 传输效率较低， 并且纠错码与信道特性要相配合， 对信道的要求较高。 第7章差错控制技术23237.2.3 混合纠错混合纠错(HEC)方式方式混合纠错方式是由FEC和ARQ两者结合而成的差错控制方式。 它不仅能检测出错误， 而且还能在一定程度上纠正错误。 HFC方式具有如下特点： （1） 可以降低FEC的复杂度， 改善ARQ的连贯性。（2） 通信效率较低， 通信的可靠性较高， 在卫星通信中应用广泛。 第7章差错控制技术24247.2.4 信息反馈信息反馈(IRQ)方式方式信息反馈

15、方式也称为回程校验方式， 它是在发送端检测错误的。 其工作过程为， 发送端不对信息进行差错编码， 而是直接将信息发送给接收端， 接收端收到后， 将其存储起来， 再将其通过反馈信道回送给发送端， 由接收端比较并发现是否出错。 第7章差错控制技术2525IRQ方式具有以下特点： （1） 设备及控制规程简单。（2） 需要反馈信道， 收发两端均需要大容量的存储设备来存储传输信息。（3） 传输效率低。 第7章差错控制技术2626 7.3 常用检错码常用检错码7.3.1 奇偶校验码奇偶校验码1. 编码方法奇偶校验编码只需在信息码后加1位校验位（或称为监督位）， 使码组中“1”的个数为奇数或偶数。 两者的监

16、督方程分别为式中，Cn，Cn1， ， C1为信息码元，C0为监督码元。 第7章差错控制技术27272. 奇偶校验编码的特点奇偶校验编码的优点是操作简单， 冗余度低， 编码效率高； 缺点是奇校验只能发现奇数个错误， 不能发现偶数个错误。 第7章差错控制技术28287.3.2 恒比码恒比码恒比码是指码字中所含“1”的个数相同的码。 由于码长一定， 则码字中“1”和“0”的个数之比是恒定的， 所以称该种编码方式为恒比码。 码字中“1”的个数称为码重。 1. 编码方法在恒比码中， 只需保持码字中“1”和“0”的比例恒定即可。 在接收端， 只要判断“1”的个数是否正确便可判断传输是否正确。 第7章差错控

17、制技术2929我国的电传机传输汉字时是采用“保护电码”来进行的， 该码为5中取3的恒定码， 码的长度为5， 码中“1”的个数为3， “0”的个数为2。 5位码组成的码组集合的码字共有25=32个， 而5中取3的恒定码共有C35=5!/(53)!3!=10, 恰好可以表示10个状态， 即可表示09共10个阿拉伯数字， 并用它拼成汉字。 我国的“保护电码”比国际电码的抗干扰能力强。 第7章差错控制技术3030一般情况下， 从“n中取m（nm）”恒比码的码字数目为可见， 恒比码实际上是用n比特传送了lbCmn比特信息量， 如用“5中取3”的恒比码来传送数据， 每个码字的信息量为lb10=3.3(bi

18、t)， 而5位二进制码的每个码字的信息量为lb25=5(bit)， 也就是说用53.3=1.7的信息量作为检验码而“浪费”的。 第7章差错控制技术31 31恒比码的编码效率为“5中取3”的恒比码编码效率为=3.35=0.66。 在国际无线电报中， 采用7位编码， 码字中有3个1， 共有C37=35个， 可表示26个英文字母和其他一些符号。第7章差错控制技术32322. 特点恒比码所具有的优点是编码简单， 纠错能力比奇偶校验码要强， 适用于电传机或其他键盘设备； 缺点是不适用随机二进制序列的编码。 恒比码必能发现错误的类型只有一种情况， 即“1”错为“0”的数目恰好是“0”错为“1”的数目。 第

19、7章差错控制技术33337.3.3 矩阵校验码矩阵校验码1. 编码方法将若干个所要传送的数字序列编排成一个矩阵， 矩阵中的每一行为一个码字， 在每一行的最后加上一个监督码元， 进行奇偶校验， 矩阵中的每一列则由不同码字相同位置的码元组成， 在每列的最后也加上一个监督码元， 进行奇偶校验, 如图7.3.1所示。 第7章差错控制技术3434图7.3.1 矩阵码组成第7章差错控制技术3535图7.3.1中， a10, , am0为m行奇偶监督码中的m个监督位， cn1， ， c0为按列进行监督的n列奇偶校验的n个监督位。 这种码有可能检测出偶数个错误。 因为每行的监督位a10, ， am0虽然不能用

20、于检测本行中的偶数个错误， 但按列有可能由cn1, ， c0监督出来。 有一些偶数个错误不可能检测出来， 譬如a1n2, a11, a2n2, a21所构成的4个错码。 第7章差错控制技术3636如数字序列11010101 00101011 00110011 10101010， 现将8位作为一个码字， 编成一个矩阵， 每个码字采用奇校验， 则编码结果如图7.3.2所示。 图7.3.2 编矩阵码结果第7章差错控制技术37372. 特点这种二维奇偶监督码适于检测突发错码。 因为这种突发错码常常成串出现， 随后有较长一段无错区间， 所以在某一行出现多个奇偶错码的机会较多， 而这种矩阵码正适合于检测这

21、类突发错误。 由于矩阵码只对构成的四角误码无法检测， 所以它的检测能力较强， 一些试验表明， 这种码可以使误码率降低至原误码率的百万分之一到万分之一。 第7章差错控制技术38387.3.4 正反码正反码正反码是一种简单的能纠错的码， 该种码的监督位与信息位相同， 且监督码与信息码相同或相反， 主要用于单位电码的前向自动纠错设备， 能纠正1位错误， 发现大部分2位以上的错误。 第7章差错控制技术39391. 编码方法每一个正反码字由10个码元组成， 其中5位信息码， 5位监督码。 当信息码中“1”的个数为偶数时， 监督码元是信息码的反码。 例如： 信息码为10101， 监督码为10101， 因为

22、信息码中“1”为奇数， 所以监督码与信息码相同；构成的码字为10101 10101。 信息码为10010， 监督码为01101， 因为信息码中“1”为偶数， 所以监督码与信息码相反； 构成的码字为10010 01101。 第7章差错控制技术40402. 译码在接收端， 先将所接收码字中的信息位和监督位， 按对应的位进行模2加， 得到一个5位的合成码, 然后用合成码产生一个校验码。 若接收码字中信息码中“1”的个数为奇数， 则合成码作为校验码； 如果信息码中“1”的个数为偶数， 则校验码为合成码的反码。 最后观察校验码字中“1”的个数， 并根据表7.3.1中的判决规则进行判决。 第7章差错控制技

23、术41 41例如， 发送码字为10101 10101， 接收码字为10101 10101，合成码为1010110101=00000， 由于接收码字中信息码“1”的个数为奇数个， 因此校验码为00000， 对应表7.3.1 可看到无错误传输。 又例如， 发送码字为10101 10101， 接收码字为11101 10101，合成码为1110110101=01000， 由于接收码字中信息码“1”的个数为偶数个， 因此校验码为10111， 对应表7.3.1 可知信息码有1位错， 位置在校验码“0”所对应的位置， 故可自动纠正为10101。第7章差错控制技术4242第7章差错控制技术43437.3.5

24、线性分组码线性分组码线性分组码(Linear Block Codes)是信道编码中最基本的一类编码， 在线性分组码中，监督码仅与所在码组中的信息码元有关， 且两者之间是通过预设的线性关系联系的。 线性分组码的构成是将信息序列划分为等长为k位的序列段后， 在每段之后附加r位监督码元(Parity Check bits)， 所构成的长度为n=k+r的码组记为(n, k)分组码。 第7章差错控制技术4444n位长度二进制码可编成2n个码字， 但由于信息码的长度仅为k， 即信息码字的个数为2k个（称其为许用码）， 所以其他2n2k个码字不能表示信息， 这些不能表示信息的码称为禁用码。 在(n, k)分

25、组码中， 码的长度为n， 其中表示信息的码长为k， 共有2k个不同的长度为n的码来对应所表示的信息， 这些码构成的码组集合可用数学中的“群”来表示， 并具有以下性质。第7章差错控制技术4545性质1: 封闭性, 即任意两个码字之模2和仍为一个码字。 性质2: 码的最小距离等于非零码的最小重量。 线性分组编码就是对长度为k的信息码按照一定规则加入长度为nk的监督码的过程，并且所增加的监督码与信息码的码元之间构成某种线性关系。 以下以(7, 4)线性分组码的编码为例来说明其整个编码过程。 第7章差错控制技术4646(7,4)码中， 信息码的长度为4， 可用C6C5C4C3来表示， 监督码可用C2C

26、1C0来表示， 编码后所形成的线性分组编码可用C6C5C4C3C2C1C0来表示， 监督码元C2、 C1、 C0与信息码元C6、 C5、 C4及C3构成了如下的线性关系：利用式(7.3.5)可得到(7, 4)线性分组码， 其结果如表7.3.2所示。第7章差错控制技术4747第7章差错控制技术48487.4 循循 环环 码码7.4.1 循环码的基本概念循环码的基本概念在数据通信中， 尤其是在计算机通信中， 应用非常广泛的一种差错控制编码是循环冗余校验码(CRC)。 CRC编码实际上是一种线性分组码， 具有很强的纠错能力。第7章差错控制技术49491. 循环冗余校验码(CRC)的定义若线性分组码各

27、码字中的码元循环左移位（或右移位）所形成的码字仍然是码组集合中的一个码字（除全零码外）， 则这种码就称为循环码。 如n长度循环码中的一个码为C=Cn1Cn2C1C0, 依次循环位移后得到的码为各码字均是循环码中的码组。 第7章差错控制技术50502. 码多项式一个由二进制码元序列组成的码组都可以和一个只含有“0”和“1”两个系数的多项式建立起一一对应的关系， 这个多项式就称为码多项式。 一个n位长的二进制序列， 它是码多项式Xn1到X0的n1次多项式的系数。 如二进制码元序列110110所对应的码多项式为第7章差错控制技术51 51把码组中的码元当作多项式系数（取0或1）， 把n长度的码字写成

28、最高次方n1次的多项式：（7.4.1）一个码字（码组）与码多项式是一一对应的， 如码组1001101所对应的码多项式为T(X)=X6+X3+X2+1； 而码多项式X5+X4+X2+X对应的码组为110110。 二进制码多项式间可进行加减运算， 即进行逻辑上的异或运算。如两个二进制码多项式A1(X)、A2(X)间的加减运算为第7章差错控制技术52523. 码多项式的同余若用X7+1去除X7+X6+X5+X3所得的余式和用X7+1去除X6+X5+X3+1所得的余式相同， 即则称两个多项式X7+X6+X5+X3和X6+X5+X3+1同余， 并记为第7章差错控制技术5353利用同余的概念可以将循环码通

29、过对应的码多项式进行分析处理。 在循环码中， 所有的非零码都具有循环特性， 即一个码字可以由另一码字向左（或向右）循环位移而得到， 对应于这种循环码多项式也具有循环特性， 即每个码多项式都可以由一个次数低的码多项式得到。该码循环一次的码多项式是原码多项式C(x)乘以x， 除以xn+1的余式， 记为C1(x)=xC（x） （mod xn+1）第7章差错控制技术5454推广下去， C（x）的i次循环位移Ci（x）是C（x）乘以xi， 除以xn+1的余式， 即Ci（x）=xiC（x） （mod xn+1） （7.4.2） 循环码是线性分组码的一种， 因此可以应用线性分组码的编译码方法。 在(n, k

30、)循环码集合中， 取前k1位都为零的码字g(x)， 根据循环码的循环特性， 将g(x)进行k1循环移位， 可得到k个码字g(x), xg(x), ， xk1g(x)。第7章差错控制技术5555这k个码多项式线性无关， 因此可利用这k个多项式相对应的码字作为各行构成码生成矩阵， 于是得到(n, k)循环码的生成矩阵第7章差错控制技术5656码生成矩阵一旦确定， 码也就确定了。 式(7.4.3）说明(n, k)循环码可以由它的一个(n, k)次码多项式g(x)来确定， 称g(x)为码生成多项式。 (n, k)次码生成多项式g(x)具有下列性质： 性质1: g(x) 是唯一的(n, k)次码多项式，

31、 并且它的次数最低。性质2: g(x) 是xn+1的因式， 即xn+1=h(x)g(x)， h(x)称为监督多项式。 第7章差错控制技术57577.4.2 循环码的编码和译码循环码的编码和译码1. 编码方法循环码是由信息码元和监督码元构成的。 首先把信息序列分为等长为k的若干个序列段，每信息段附加r位长度的监督码元， 从而构成长度为n=k+r的循环码。 循环码用(n, k)表示， 它也可以用一个n1次多项式来表示。 循环码的格式如图7.4.1所示。 第7章差错控制技术5858图7.4.1 循环码的格式第7章差错控制技术5959一个n位循环码由k位信息码加上r位校验码组成， 其中r=nk。 表征

32、循环码(CRC)的多项式称为生成多项式G(X)。k位二进制码元加上r位CRC校验位后， 信息位要向左移， 这相当于A(X)乘上X。 XA(X)除以生成多项式G(X)， 得到整数多项式Q(X)加上余数多项式R(X)， 即从而有第7章差错控制技术6060利用多项式加减法的性质， 有这说明信息多项式A(X)和余数多项式R(X)可以合并为一个新的多项式C(X)， 称为循环多项式， 该多项式是生成多项式G(X)的整数Q(X)倍。第7章差错控制技术61 612. 循环码的性质在循环码中， nk次码多项式有一个且仅有一个生成多项式G(X)。 在循环码中， 所有码多项式能被生成多项式G(X)整除。 循环码的输

33、出多项式G(X)是Xn+1的一个因式。第7章差错控制技术62623. CRC校验码的生成和校验根据信息序列的分组长度和检错能力的要求， 每个k位信息段附加r位监督码元构成n=k+r位循环码， 其生成步骤如下： (1) 在k位信息码组的后面加上r个0。 r是监督码元的位数， 比生成多项式G(X)的位数r+1少1位。 第7章差错控制技术6363(2) 采用二进制除法将新的加长的长度为n的码组用G(X)来除， 所产生的余数就是CRC校验码。 (3) 用r个码元的CRC校验码元替代信息段后面附加的r个0， 如果余数的位数小于r， 则在最左端用0补足r位； 如果除法运算没有产生余数（信息码组是可以被整除

34、的）， 则用r位0作为校验码。第7章差错控制技术6464在接收端进行校验时， 可按以下步骤进行： 第一步， 将接收到的数据分为若干个长度为n的数据段， 用G(X)来除。 第二步， 如果n位数据段能被G(X)整除， 则说明该数据段在传送的过程中未发生差错， 否则， 说明传送过程中出现了差错。 以下以两个例子来说明循环码的编码过程。 第7章差错控制技术6565例如， 信息码组为1101， 生成多项式为G(X)=X3+X+1， 编(7, 4)循环码。 编码步骤如下： (1) A(X)=1101为4位二进制码， 需附加r=74=3位监督码， 在1101后附加000， 变为1101000。 (2) 用G

35、(X)=X3+X+1（对应的码组为1011）去除1101000， 即将1101000作为被除数， 1011作为除数， 进行除法运算, 得到的余数为1， 于是CRC校验码为001。 第7章差错控制技术6666(3) 用001替代第一步中的000， 最后的编码为1101001。 注意， 在进行除法运算时， 需要进行减法运算， 该减法运算实际上是一个异或运算， 如1001， 则结果为11。 又例如， 信息码组为101， 编一个(7, 3)的循环码。 编码的步骤如下： （1） 确定监督码的码长， 监督位的码长为r=nk=73=4。 （2） 确定生成多项式G（X）。 根据循环码的性质， 循环码的生成多项

36、式G（X）Xn+1的一个因式， 所以生成多项式G（X）是X7+1的一个因式， 而G（X）是nk=4次因式。 第7章差错控制技术6767对X7+1可分解因式为X7+1=（X+1）（X3+X2+1）（X3+X2+1） 从X7+1的因式分解中任意选择4次因式， 我们选择G(X)=(X+1)(X3+X2+1)， 需要注意的是上述的因式分解与严格意义上的初等数学的因式分解不同， 这里执行的运算是异或运算， 如X+X=0， 因此G(X)=(X+1)(X3+X2+1)=X4+X3+X2+1所对应的码为11101。 第7章差错控制技术6868(3) 在信息码组后附加4位0， 变为1010000。 (4) 除法

37、运算， 并求余。 (5) 用余数0011替代0000， 得到最后的编码为1010011。 第7章差错控制技术69694. 循环码的应用及特点在串行通信中， 常常采用CRC-16、 CRC-CCITT及CRC-32这3种常用的生成多项式来产生校验码。 CRC-16的生成多项式为G(X)=X16+X15+X2+1; CRC-CCITT的生成多项式为G(X)=X16+X12+X5+1; CRC-32的生成多项式为G(X)=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1。 第7章差错控制技术70707.5 卷卷 积积 码码7.5.1 基本原理基本原

38、理卷积码是一种非分组码， 它的校验位不仅和本组码有关， 而且还与前组及前若干组码有关， 具有连环监督作用， 因此卷积码也称为连环码。 卷积码的整个编码过程是环环相扣连锁进行的。 编码时， 信息序列分为k0个码元段， 每段在经过编码后变为n0(n0k0)个码元的码组， 通常n0和k0都是较小的整数。第7章差错控制技术71 71编码器的每个单位时间内所输出的n0个码元不仅与此时输入的k0个信息码元有关， 而且还与之前较长一段时间内输入的信息码元有关。 图7.5.1所示为一个简单的n0=3， k0=1 的卷积编码器。 第7章差错控制技术7272图7.5.1 n0=3, k0=1的卷积编码器第7章差错

39、控制技术7373在每一个单位时间内， 当一个新的信息码元mj进入编码器， 存储在存储器中的码组向右依次移动一位， 此时新的信息码元一方面直接进入信道， 同时前面两个单位时间内输入的信息码元mj1、 mj2按一定方式进行模2加的运算， 得到两个监督码元Pj1、 Pj2后依次随mj送入信道。 由图7.5.1可知：（7.5.1）第7章差错控制技术7474若下一个单位时间内输入的信息码元为mj+1， 则它的两个监督码元为（7.5.2）若输入的信息码元为mj、 mj+1， 则输出的编码为mj Pj1Pj2 mj+1 P（j+1）1 P（j+1）2。 若mjmj+1=11， 则输出为111101。第7章差

40、错控制技术75757.5.2 编码和译码编码和译码1. 简单卷积编码器简单卷积编码器如图7.5.2所示。 它由两个移位寄存器R1和R2及一个模2加法器构成。图7.5.2 简单卷积编码器原理图第7章差错控制技术7676移位寄存器按信息码率的速度进行工作， 当输入1位信息码元时， 电子开关倒换一次，即前半拍接通a端， 后半拍接通b端。 因此， 若输入信息为a0a1a2a3， 第一拍， 从寄存器R1中移出的为a0， 所以a端输出的是a0； 寄存器R2移出的是0（初始值为0）， 所以b端输出的为b0=a0 + 0=a0。第7章差错控制技术77772. 解码器与图7.5.2所对应的解码器如图7.5.3所示。 解码器的输入端是一个电子开关， 它按节拍把信息码元与监督码元分别接到a端和b端， 3个移位寄存器R1、 R2和R3的节拍为码元序列节拍的一半。 R1、 R2在信息码元到达时移位，监督码元到达期间保持原状态。 寄存器R3在监督码元到达时移位， 在信息码元到达时保持原状态。第7章差错控制技术7878R1、 R2及加法器1构成与发送端一样的编码器， 它从接收到的信息码元序列中计算出监督码序