第五章差错控制与信道编码数据通信原理课件.ppt

1、第五章 差错控制与信道编码 结束放映学习目录学习要求内容简介主讲教师：刘兴顺内容简介差错控制就是通过某种方法，发现并纠正数据传输中出现的错误。差错控制技术是提高数据传输可靠性的重要手段之一，现代数据通信中使用的差错控制方式大都是基于信道编码技术来实现的，本章对差错控制的基本概念以及常用的信道编码方案作了比较详细的理论述。返回结束学习要求1.理解差错控制的基本概念及其原理等；2.掌握信道编码的基本原理；3.了解常用检错码的特性；4.掌握线性分组码的一般特性；5.掌握汉明码以及循环码的编译码及其实现原理；6.了解卷积码的基本概念。返回结束学习目录返回5.1 概述5.2 常用的简单信道编码5.3 线

2、性分组码5.4 卷积码结束5.1 概 述下一页上一页差错控制是数据通信系统中提高传输可靠性，降低系统传输误码率的有效措施。本节将介绍差错控制和信道编码的基本原理、差错控制的实现方式等内容。5.1.1 差错控制 5.1.2 信道编码 5.1.3 基于信道编码的差错控制方式 本节内容提要：5.1.1 差错控制下一页上一页 差错控制通过某种方法，发现并纠正传输中出现的错误。香农信道编码定理在具有确定信道容量的有扰信道中，若以低于信道容量的速率传输数据，则存在某种编码方案，可以使传输的误码率足够小。基于信道编码的差错控制在发送端根据一定的规则，在数据序列中按照一定的规则附加一些监督信息，接收端根据监督

3、信息进行检错或者纠错。5.1.1 差错控制下一页上一页 随机错误 主要由起伏噪声引起，错误码元分布比较分散且彼此统计独立；突发错误主要由脉冲噪声引起，错误码元分布集中且彼此具有某种相关性。错误图样 差错分析 BAEE中，“0”表示正确，“1”表示错误下一页上一页 随机错误错误图样5.1.1 差错控制 突发错误错误图样5.1.2 信道编码下一页上一页在不采用信道编码的时候，进入信道的数据码元相互独立，一旦发生错误，将无法发现。例如气象台向电视台传输气象信息。不可靠数据传输系统 5.1.2 信道编码下一页上一页将信息序列按照k位码元的长度分成若干个信息码组M，再将信息码组输入到信道编码器，信道编码

4、器按照一定的算法，产生一个新的n位码字A输出，nk；收端根据A中的相关性判断接收是否正确，并将其恢复成M。编码效率为k/n，即所谓编码效率是指信道编码后码字中信息码元的数目与码字总码元数目之比。信道编码的基本思想5.1.2 信道编码下一页上一页 信道编码的冗余 信息码组M由k个二进制码元（即比特）组成，所以就有2k个M；A长度为n，n位长度的码字共有2n个，信道编码实质是通过一定 的规则，从2n个长度为n的码字中选择了其中的2k个，每个被选 中的码字称为许用码字；未被选中的2n-2k个n长的码字称为禁用码字，反映冗余大小。5.1.2 信道编码下一页上一页 对本节开始时的例子采用(2，1)重复码

5、:11”-晴,“00”-雨 许用码组为:“11”和“00”,禁用码组为：“01”和“10”此时接收端可以发现单个错误，但不能纠正错误 也不能发现2位错误，如下图所示：实例分析 I5.1.2 信道编码下一页上一页 对本节开始时的例子采用(3，1)重复码:111”-晴,“000”-雨 许用码组为:111和000 禁用码组为：001、010、011、100、101、110 将这种编码用来检错时，可以发现两位以内的错误 将这种编码用来纠错，可以纠正一位错误，如下图所示：实例分析 II5.1.2 信道编码下一页上一页 如此译码的原因是信道中错一位的概率远远大于错多位的概率 例如要把该（3，1）重复码在有

6、一条误码率为10-5的信道传输，则：错一位的概率为：P1=C31 Pe(1Pe)2=310-5 错二位的概率为：P2=C32 Pe2(1Pe)=310-10 错三位的概率为：P3=Pe3=10-15 这种译码方法称为极大似然译码法,其基本原理为:构造一个极大似 然函数L,从2k个许用码组中找到一个码字Ci，当R=Ci时,函数L可以 取得最大值,则认为C=Ci。5.1.2 信道编码下一页上一页 线性码和非线性码 若f()是线性函数称为线性码若f()是非线性函数则称为非线性编码 信道编码的分类)(MfA信道编码器函数关系式为：分组码和卷积码 分组码：每个信息码组M通过运算产生对应的A，记作(n，k

7、)12,2,1,0)(kiiiMfA卷积码：每个A是由m(mt)(n，k)分组码总共有2k个码字，记作Ai（i=0,1,2k-1）,则这些码字两两之间都有一个码距，定义该(n，k)分组码的最小码距为：5.1.3 基于信道编码的差错控制方式下一页上一页 反馈纠错（ARQ）方式 原理采用检错码，接收端发现错误后，给发送端一个反馈信号，要求重新发送，直到正确为止。特点编码效率比较高，对信道的适应能力强重发导致信道的有效利用率较低，通信的实时性较差 应用数据通信系统5.1.3 基于信道编码的差错控制方式下一页上一页 前向纠错（FEC）方式 原理采用纠错码,收端发现错误后自动纠正。特点无需重发，实时性好

8、编码效率较低，译码设备比较复杂若错误超出纠错码纠错能力,只好将其抛弃 应用移动通信系统 5.1.3 基于信道编码的差错控制方式下一页上一页 混合纠错（HEC）方式 原理采用纠检错码，是ARQ和FEC方式的折衷方案 特点集合了ARQ和FEC的优点，在保证系统较高的有效性的同时,大幅度提高了整个系统的可靠性 应用移动通信系统，数据传输系统下一页上一页5.2 常用的简单信道编码本节内容提要：检错码在ARQ系统中使用，其生成方式简单，易于实现，检错效果较好，因此得到广泛的应用，本节将介绍奇偶校验码、行列监督码、恒比码、正反码的编译码规则、特性以及应用情况。5.2.1 奇偶监督码 5.2.2 行列监督码

9、 5.2.3 恒比码 5.2.4 重复码 5.2.5 正反码下一页上一页5.2.1 奇偶监督码 奇偶监督码码重为奇数或偶数的(n,n-1)系统分组码)(0)(11010模二偶监督模二奇监督niiniiaa：ITU-T建议同步数据传输使用偶监督异步数据传输使用奇监督 监督关系假设将（n，n-1）的奇偶监督码的码字记作：an-1,an-2,a1,a0，其中a0为监督码元，其余为信息码元，则各码元满足：下一页上一页5.2.2 行列监督码 行列监督码对水平方向(共L行)和垂直方向(共M列),同时进行奇偶监督的码，记作（LM+L+M+1,LM）。(66，50)行列监督码的一个码字 该码具有很强的纠检错能

10、力，常用于短波散射信道等信道干扰比 较严重的通信中。下一页上一页5.2.3 恒比码 恒比码该码的特点是码字中1，0数目恒定，亦即1，0数目之比恒定。目前我国电传通信中普遍采用3：2码，又称5中取3码，如下所示 国际上通用的ARQ电报通信系统中，采用7中取3码。下一页上一页5.2.4 重复码(3，1)重复码两个码字为000和111，其最小码距为3；(n，1)重复码也只有全0码和全1码两个码字，其最小码距为n，却有2n-2个禁用码组，随着码长的增大，其冗余也变得很大；该码随码长增加，具有很强的纠检错能力，但其编码效率的急剧下降；重复码并不是一种优秀的编码方案，仅用于速率很低的数据通信系统中。重复码

11、重复码只有一位信息码元，监督码元是信息码元的重复，所以仅有两个码字；下一页上一页5.2.5 正反码 正反码该码型多用于10单位码的前向纠错设备中，可以纠正一位错误，发现全部两个以下的错误，以及大部分两个以上的错误，其本质 就是五单位码的重复；编码规则信息码组中1的数目为奇数时，监督码是信息码的重复即正码；信息码组中1的数目为偶数时，监督码是信息码的反码。译码方法首先将收到的码字重的信息位和监督位按对应位作模2运算，得到一个5位码组，若该码字中有奇数个1，则将其作为校验码 组，若有偶数个1，则取其反码作为校验码组。然后，按照下表 进行纠检错译码下一页上一页5.2.5 正反码 正反码错误判决表 校

12、验码组的形式错误情况判断1全“0”传输正确24个“1”，1个“0”信息元有1位出错，在校验码组中“0”对应的位置34个“0”，1个“1”监督元有1位出错，在校验码组中“1”对应的位置4其它形式传输出错，且错误位数大于1下一页上一页5.3 线性分组码本节内容提要：本节将对线性分组码的特点、编译码规则以及应用情况作介绍，主要包括以下四方面内容。5.3.1 基本概念 5.3.2 线性分组码编码 5.3.3 汉明码 5.3.4 循环码下一页上一页5.3.1 基本概念1有限域定义了加法“+”和乘法“”两种运算的有限集合；q个元素的有限域又称为伽罗瓦域，记作GF(q)；对域的逆元操作又演绎出了减法“”和除

13、法运算“”，域具有封闭特性)GF()GF()GF()GF(qqqq，则 域中总包含惟一的加法恒等元“0”和乘法恒等元“1”10)GF(，则q下一页上一页5.3.1 基本概念 域中任意元素存在惟一的加法逆元 域中任意非零元都存在惟一的乘法逆元 于是减法和除法运算可定义为：0),GF(,)()GF(,)(1qq 域中元素满足交换律、结合律和分配律运算规则：)()()()()()GF(,q下一页上一页5.3.1 基本概念 GF(q)中定义的是模q的加法和乘法，例如GF(2)的运算表如表所示：+0100111001000101 加法运算表 乘法运算表下一页上一页5.3.1 基本概念2矢量空间 所有n维

14、矢量组成的集合就构成了n维矢量空间Vn；矢量对矢量的加法构成一个加法交换群，即满足封闭性、结合律和交换律，有恒等元和逆元。满足分配律 满足结合律对于相乘恒等元 F1有 uu 1 Vu 矢量空间的性质8PSK调制时给出的信号点矢量图，就是定义在GF(2)上的3维矢量空间V3 V3=000，001，010，011，100，101，110，111 下一页上一页5.3.1 基本概念 集合S中存在全零矢量（0,0,0），即零元；集合S中任何两个矢量和仍在该集合中，即满足封闭性。子空间如果n维矢量空间Vn的一个子集S，满足以下条件，则称其为Vn的一个子空间：矢量与码字的关系 一个码长为n的码字可以看成是一

15、个有n个元素的矢量；所有2n个n长码字就构成了定义在GF(2)上的n维矢量空间Vn；对于一个(n，k)线性分组码，其编码过程是从GF(2)上的n维矢 量空间Vn中，寻找其中遵循某种编码规则的一个子空间，而这 个字空间中的所有码字正好构成了一个加法交换群，所以线性 分组码又称为群码。下一页上一页5.3.1 基本概念3线性分组码性质 封闭性),(),(),(knAAAknAknAkjiji 具有零元 即具有全零码，记作A0 。具有负元若Ai+Aj=A0则称其互为码元，（n,k）中Ai是它本身的负元。满足结合率和交换率 1221321321321)()(AAAAAAAAAAAAA下一页上一页5.3.

16、2 线性分组码编码1生成距阵 矢量的线性无关 若Vn中k个矢量A1,A2,Ak，当且仅当 ，i=1,2,k时下式成立 0i02211 kkAAA 空间的基 在任意一个矢量空间或者子空间中，至少存在一组线性无关的矢量，可以张成这个空间,这一组矢量称为该空间的基，基中矢量的数目称为空间的维数。下一页上一页5.3.2 线性分组码编码 实例分析v1=(1000)，v2=(0100)，v3=(0010)，v4=(0001)线性无关的，作为基，张成一个4维矢量空间V4：44332211vvvvu)1000()0010()0100()1000(432110000100001000014321G4321下一页

17、上一页5.3.2 线性分组码编码 生成矩阵矩阵G的每行矢量是基中的矢量，故称之为生成矩阵；有其可以得到矢量空间中的全部矢量；上例中选取的基得到的生成矩阵恰好是4阶单位矩阵，实际上线性无关的行矢量都可以作为生成矩阵的行矢量。2编码原理 线性分组码标记（n，k）线性分组码，其码字通常记作：A=an-1 an-2 a0 1n信息码组M记作：M=mk-1 mk-2 m1 m0 1k 下一页上一页5.3.2 线性分组码编码 生成矩阵G记作：编码过程 nknkkknnkgggggggggG1,10,10,11,110101,00100110ggg1,10,10,11,110101,00100021nkkk

18、nnkkgggggggggmmmMGA下一页上一页5.3.2 线性分组码编码 实例 假设一个(6，3)分组生成矩阵为：101100110010101011G编码过程为：1011001100101010110121020122012mmmmmmmmmmmmmMGA下一页上一页5.3.2 线性分组码编码 该(6，3)码是非系统码，信息元m2、m0、m1分别出现在码字A的第 1、3、5位，而2、4、6位是编码器产生的监督码元其码表为：信息码组M m2 m1 m0码字A a5 a4 a3 a2 a1 a0信息码组M m2 m1 m0码字A a5 a4 a3 a2 a1 a00 0 00 0 10 1

19、00 1 10 0 0 0 0 00 0 1 1 0 10 1 0 0 1 10 1 1 1 1 01 0 01 0 11 1 01 1 11 1 0 1 0 11 1 1 0 0 01 0 0 1 1 01 0 1 0 1 1下一页上一页5.3.2 线性分组码编码 生成矩阵典型化 实例分析3系统码编码原理 101100110010101011G101100110010011001G101100110010011001011202012012mmmmmmmmmmmmMGA 编码过程下一页上一页5.3.2 线性分组码编码 (6，3)系统分组码表 监督元与信息元之间的一般关系 信息码组M m2 m

20、1 m0码字A a5 a4 a3 a2 a1 a0信息码组M m2 m1 m0码字A a5 a4 a3 a2 a1 a00 0 00 0 10 1 00 1 10 0 0 0 0 00 0 1 1 0 10 1 0 0 1 10 1 1 1 1 01 0 01 0 11 1 01 1 11 0 0 1 1 01 0 1 0 1 11 1 0 1 0 11 1 1 0 0 0011202012012345mmmmmmmmmaaaaaaA下一页上一页5.3.2 线性分组码编码 注意到系统码中前k位即信息元，将其写成线性方程组的形式034145235aaaaaaaaa监督关系 00003414523

21、5aaaaaaaaa0100110010011001101012345aaaaaa下一页上一页5.3.2 线性分组码编码 监督矩阵 监督关系一般表达 100110010011001101H0THA0TAH或 生成矩阵典型阵一般形式nkrkknkrkkkrrQIqqqqqqqqqG1,11,10,11,111101,00100100000100001下一页上一页5.3.2 线性分组码编码(n，k)分组码码字可表示为：(n，k)码的一般编码过程A=an-1 an-2 an-k ar-1 a1 a0 =mk-1 mk-2 m0 ar-1 a1 a0 对上式两边同时进行矩阵转置得：QIMMGAkTTk

22、TTTMQIMGA下一页上一页5.3.2 线性分组码编码 也即此时的系数矩阵，即监督矩阵为 01000001000010211,11,11,01,111010,11000aaaqqqqqqqqqnnrkrrkk1000001000011,11,11,01,111010,11000rkrrkkqqqqqqqqqH下一页上一页5.3.2 线性分组码编码 生成矩阵和监督距阵的关系(n，k)码的一般编码过程0rkrkrrkrkkrkTrTkTQQIQQIIQQIIQQIGH0TGH0THG或 即 根据需要选定一监督关系确定H阵；求由H距阵和阵的关系确定G阵；由A=MG生成所有码字。下一页上一页5.3.

23、2 线性分组码编码 伴随式S和错误图样E的关系 伴随式 二者并不是一一对应的关系，因为错误图样有2n种表现形 式，而伴随式仅有2r种表现形式，（注意r=n-kn），且其中 S=0说明传输无错，这在该(n，k)分组码用于检错时已足够。但发生了错误却不能检出是完全有可能的，例如封闭性 错误。4伴随式与检错原理 错码的码字，判决传输出不是该错码的码字，判决传输无是该)(0)(0knBknBBHST，TTTTTEHEHAHHEABHS)(下一页上一页5.3.2 线性分组码编码 (6，3)分组码的监督矩阵为：实例分析 伴随式 100110010011001101H03414523501234501210

24、0110010011001101bbbbbbbbbbbbbbbHBsssSTT下一页上一页5.3.2 线性分组码编码(6，3)分组码伴随式计算电路 下一页上一页5.3.3 汉明码 将监督矩阵记成列矢量的形式，H=h0 h1 hn-2 hn-1，则 汉明码定义 伴随式和错误图样的关系 0111,11,11,01,111010,110000121100000100001eeeeqqqqqqqqqHEssssSrknnrkrrkkTrrT10211201nnnnTeeeeShhhh单个错误时的伴随式恰好与H的一个列矢量对应，只要H的各个 列矢量不为0矢量，且各不相同，则可以纠正单个错误。下一页上一页

25、5.3.3 汉明码 汉明码的另一种描述方式：对于任何的整数，必存在一个(n，k)汉明码，码长n和监督元数目r=n-k满足 n=2r-1 汉明码特点 可以纠正一位传输错误，且d0=3，码长和监督员的关系：n=2r-1 实例分析(7，4)汉明码 首先其监督矩阵，此时监督矩阵为H37，3位二进制码元的组合有8种：000、001、010、011、100、101、110、111 其中不全为零的7个正好可用作监督矩阵的列,可得到监督矩阵：下一页上一页5.3.3 汉明码 任意调换监督矩阵各列位置并不影响码的纠错能力，将其转化成典型阵的形式，并由其可以得到生成矩阵G 101010111001101111000

26、H100110101010110010111H1101000101010001100101110001G由A=MG得到其所有的码字，如下表所示：下一页上一页5.3.3 汉明码 假设发送端的码字是A15=1111111，传输过程中第4位a3出现了错误，即接收的码字是B=1110111 此时对应的伴随式为：信息码组Mm3 m2 m1 m0码字Aa6 a5 a4 a3 a2 a1 a0信息码组Mm3 m2 m1 m0码字Aa6 a5 a4 a3 a2 a1 a00 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 10 0 0 0 0 0 00

27、 0 0 1 0 1 10 0 1 0 1 0 10 0 1 1 1 1 00 1 0 0 1 1 00 1 0 1 1 0 10 1 1 0 0 1 10 1 1 1 0 0 01 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 11 0 0 0 1 1 11 0 0 1 1 0 01 0 1 0 0 1 01 0 1 1 0 0 11 1 0 0 0 0 11 1 0 1 0 1 01 1 1 0 1 0 01 1 1 1 1 1 1下一页上一页5.3.3 汉明码 下表给出了该（7，4）汉明码单个错误的错误图样与其对应的伴 随式，可

28、以发现伴随式正是监督矩阵的每一列，且该列的位置恰 好是码元出错的位置。由于S不时全零，可判断传输出错，而ST=0 1 1T，是监督矩阵H的第4列,这正是错误码元发生的位置,因此可以得到错误图样为E=0001000，进而按B+E即可纠错。1101110111100110101010110010111TTHBS下一页上一页5.3.3 汉明码 完备性定义 汉明码完备码 性错误位置错误图样Ee6 e5 e4 e3 e2 e1 e0伴随式Ss2 s1 s0无错0 0 0 0 0 0 00 0 0b00 0 0 0 0 0 10 0 1b10 0 0 0 0 1 00 1 0b20 0 0 0 1 0 0

29、1 0 0b30 0 0 1 0 0 00 1 1b40 0 1 0 0 0 01 0 1b50 1 0 0 0 0 01 1 0b61 0 0 0 0 0 01 1 1tnnnknrCCC1022下一页上一页5.3.4 循环码一个(7，3)系统循环码 码表如下所示：1基本概念一类具有循环移位特性的线性分组码，即其中的一个码字经过循环移位后仍然是该分组码的码字 定义信息码组Mm2 m1 m0码字Aa6 a5 a4 a3 a2 a1 a0信息码组Mm2 m1 m0码字Aa6 a5 a4 a3 a2 a1 a00 0 00 0 10 1 00 1 10 0 0 0 0 0 00 0 1 0 1 1

30、 10 1 0 1 1 1 00 1 1 1 0 0 11 0 01 0 11 1 01 1 11 0 0 1 0 1 11 0 1 1 1 0 01 1 0 0 1 0 11 1 1 0 0 1 0下一页上一页5.3.4 循环码例如A4=0111001，对应的码多项式为：码多项式(n，k)循环码中，为了便于描述与计算，经常使用n-1次码多项式 来表示码字，码字A=an-1 an-2 a1 a0，它对应的码多项式为：01222211)(axaxaxaxaxAnnnn11001110)(345234564xxxxxxxxxxAA4向左循环移1位得A7=1110010，这相当于将A4(x)乘以x，

31、即 xxxxxxAxA45647)()(下一页上一页5.3.4 循环码对于(7，3)循环码的码多项式，其最高次数不能超过6，解决该 问题的办法是对上式作模x7+1运算：A7向左循环移1位得A6=1100101，但若将A7(x)乘以x得到多项式为 其计算过程如下：25677)(xxxxxxA)()1(1)(672567xAxxxxxxA模1111256725677xxxxxxxxx下一页上一页5.3.4 循环码2生成多项式和生成矩阵(n，k)循环码中的r=n-k次码多项式，其次数最低（0元除外）；其它所有的码多项式都能被g(x)整除；并且g(x)是xn+1的一个因式。生成多项式 g(x)例如本节

32、前面给出的(7，3)循环码，其生成多项式为：1)(24xxxxg)1)(1()1)(1()1)(1)(1(1232343243237xxxxxxxxxxxxxxxx下一页上一页5.3.4 循环码若g(x)含有(x+1)因式，对应的(n，k)系统循环码，能够检出所有奇数个错误；(n，k)系统循环码检错能力与g(x)的关系 若g(x)含有常数项1因式，且不能整除xe+1，则对应的(n，k)系统循环码，能够检出所有的两位错误；10ne若g(x)含有常数项1因式，对应的(n，k)系统循环码，能够检出所有突发长度r的突发错误，并且对突发长度等于r+1的突发错误的漏检率为2-(r-1)，对突发长度大于r+

33、1的突发错误的漏检率为2-r。下一页上一页5.3.4 循环码CRC-12：标准生成多项式 CRC-16：CRC-CCITT：CRC-32：1)(231112xxxxxxg1)(21516xxxxg1)(51216xxxxg1)(245781011121622232632xxxxxxxxxxxxxxxg下一页上一页5.3.4 循环码g(x)、x g(x)、x2 g(x)、xk-1 g(x)是(n，k)循环码的k个线性无 关的码字，所以可得其上乘距阵G，用码多项式表示G的各行：生成矩阵G 若信息码组M=mk-1 mk-2 m0，则：)()()()()(21xgxxgxgxxgxxGkk)()()(

34、)()()(012211xgmxxgmxgxmxgxmxMGxAkkkk)()()(012211xgxMxgmxmxmxmkkkk下一页上一页5.3.4 循环码上式同时提供了循环码的一种编码方法，但由其得到的循环码 是非系统码，因为此时生成矩阵不是典型阵。例如本节前面给出的(7，3)循环码，1)(24xxxxg将该矩阵典型化之后，再按照A=MG编码才能得到表本节前面 给出的系统(7，3)循环码；实际应用中，系统循环码的编译码通常是由g(x)经过简单的代数 运算来实现。1110100011101000111011)()()()(2423523462xxxxxxxxxxxxgxxgxgxxG下一页

35、上一页5.3.4 循环码系统(n，k)循环码码字：编码原理用码多项式来表示为：3编码A=an-1 an-2 an-k ar-1 a1 a0 =mk-1 mk-2 m0 ar-1 a1 a0 01112211)(axaxaxaxaxaxArrknknnnnn011102211)(axaxaxmxmxmrrknkkkk)()(xrxxMkn下一页上一页5.3.4 循环码式中M(x)是信息码组码多项式，所以只需要确定r(x)已知循环码的所有码字都能够被g(x)整除，r(x)可由下式确定：(n，k)循环码的生成多项式为：)x(g)()(模knxxMxr 编码器1)(12211 xgxgxgxxgrrr

36、其中r=n-k，则该(n，k)系统循环码的编码电路如下图所示：下一页上一页5.3.4 循环码r级线性移位寄存器的初始状态为全零，所有开关均向下连通；在寄存器时钟的控制下进行k次移位，输出M(x)的系数(即信息 码组)，同时实现除法电路的功能；编码器工作过程下一页上一页5.3.4 循环码所有开关向下连通，输入下一组信息重复上述过程。实例分析所有开关均倒向上方连通，在寄存器时钟的控制下再经过r=n-k 次移位，将监督元输出到信道；本节前面给出的(7，3)循环码生成多项式：g(x)=x4+x2+x+1 由其可得编码电路如下图所示：下一页上一页5.3.4 循环码假设M=110，编码器工作过程如下表所示

37、 输入移位寄存器状态反馈输出R1R2R3R4f0000000m2m1m0110111100101010111110a6a5a4信息元0000000010000100001001010101a3a2a1a0监督元下一页上一页5.3.4 循环码现在检验上表编码结果，因为M=110，所以 即所得的码字为A=1100101。xxxM2)(5624)()(xxxxxxMxkn)(111)()(222456xgxxxxxxxxxgxMxkn1)(2xxr1)()()(256xxxxrxMxxAkn下一页上一页5.3.4 循环码系统循环码的每一个码字都能够被生成多项式g(x)整除：检错译码原理发送端发送的码

38、字为3译码01222211)(axaxaxaxaxAnnnn01222211)(bxbxbxbxbxBnnnn01222211)(exexexexexEnnnn01222211)(sxsxsxsxsxSrrrr接收的码字为错误图样伴随式下一页上一页5.3.4 循环码可以证明：若S等于0判定传输无错，否则判定传输出错。)()()()()(xgxExgxBxS模模检错译码原理图：下一页上一页5.3.4 循环码寄存器置零，开关S向下连通；在寄存器时钟的控制下经n次移位后将接收码字B输入，此时寄存器中存储的即伴随式(n，k)循环码伴随式计算电路 其工作过程如下：),.,(011ssssSrr将开关向上

39、打开，经r=n-k次移位读出伴随式。下一页上一页5.3.4 循环码 纠错译码原理确定循环码的纠错能力;根据 模g(x)计算伴随式，若S(x)则判定传输出错。)()(xBxS根据 模g(x)找到伴随式对应的错误图样)()(xExS由A(x)=B(x)+E(x)纠错。5.4 卷积码下一页上一页本节内容提要：卷积码是一类非线性有记忆编码，本节将简要介绍卷积码的编 译码原理。5.4.1 卷积编码器 5.4.2 卷积码的解析描述 5.4.3 卷积码的图解描述 5.4.4 维特比译码原理 下一页上一页5.4.1 卷积编码器卷积码通常记作(n，k，m)，其中k为一次移入编码器的比特数目，n为对应于k比特输入

40、的编码输出，m为约束长度。卷积码定义卷积码的编码效率为k/n，可以将其理解为同一时刻，编码器有k位比特信息输入，有n位编码比特输出 卷积码有记忆的特性：卷积编码器的输出不仅和当前输入的k比特信息有关，而且还依赖于之前输入的m-1组k比特信息。下一页上一页5.4.1 卷积编码器(n，k，m)卷积编码器结构 下一页上一页5.4.1 卷积编码器可以发现上图中mk级寄存器中第一级是多余的，事实上只需要 m(k-1)级即可，所以可以得到卷积码编码器的另一种形式下一页上一页5.4.1 卷积编码器(3，1，3)卷积码的两种等效编码器 实例分析 3级编码器 2级编码器 321331211ssscsscsc下一

41、页上一页5.4.2 卷积码的解析描述仍然以上图中的(3，1，3)卷积码为例，由其单位冲击响应可构造生成矩阵为：生成矩阵法 其中未写出的元素为0。和分组码不同，卷积码并不以块的形式出现，即其码字可能无限长，故5-68式所示的矩阵称为半无限矩阵 011001111011001111011001111011001111321321321321VVVVVVVVVVVVg下一页上一页此时卷积码可由C=MG得到，例如M=11101时11010000101111110101001100111101100111101100111101100111101100111111101C5.4.2 卷积码的解析描述下一

42、页上一页卷积编码器也可以用n个生成多项式来描述，分别对应n个输出支路。生成多项式法 (3，1，3)卷积码编码器 上图所示的卷积编码器可以用以下所示的3个生成多项式描述 232211)(1)(1)(xxxgxxgxg5.4.2 卷积码的解析描述下一页上一页则对应的码多项式为所以对应的码字是：C=111 110 101 010 100 001 011输入信息为M=11101，对应的多项式为 则各支路码多项式分别为：421)(xxxxM652336322432111)()()(1)()()(1)()()(xxxxgxMxcxxxxgxMxcxxxxxgxMxc65432321110100001010101011111)()()()(xxxxxxxcxcxcxC5.4.2 卷积码的解析描述下一页上一页5.4.3 卷积码的图解描述 实例分析以下图所示的(2，1，3)卷积码器假设初始状态为a，输入序列为M=110100，则有状态图很容易得到编码序列为C=100100011111。状态图法 下一页上一页5.4.3 卷积码的图解描述 树图法 输入为110100时，编码输出为100100011111，如图中虚线所示 下一页上一页5.4.3 卷积码的图解描述 网格图法 下一页上一页5.4.4 维特比译码原理返回结束