1、通信原理第十二章 差错控制编码严谨 严格 求实 求是第一章 绪论本章内容结构 12.1 引言 12.2 常用的简单编码 12.3 线性分组码 12.4 循环码 12.5 卷积码严谨 严格 求实 求是第一章 绪论12.1 12.1 引言引言一一.差错控制方法差错控制方法(3)混合纠错（HEC）(1)检错重发（ARQ）(2)前向纠错（FEC）严谨 严格 求实 求是第一章 绪论 1.将信息码分组，为每组信息码附加若干监督码的编将信息码分组，为每组信息码附加若干监督码的编码，称为分组码。（系统码）码，称为分组码。（系统码）码组码组=信息位信息位+监督位监督位二二.基本概念基本概念严谨 严格 求实 求是
2、第一章 绪论2.分组码的表示：符号（分组码的表示：符号（n，k）n 码组的总位数码组的总位数k 码组中信息码元的数目码组中信息码元的数目r =n-k 监督码元的数目监督码元的数目3.编码效率编码效率nrnkR/1/R R越大，信息位比重大，有效性越高。越大，信息位比重大，有效性越高。严谨 严格 求实 求是第一章 绪论4.分类：分类：（1 1）根据已编码组中信息码元与监督码元之间的函数）根据已编码组中信息码元与监督码元之间的函数关系，可分为线性码和非线性码。若信息码元与监督码关系，可分为线性码和非线性码。若信息码元与监督码元之间的关系呈线性，即满足一组线性方程式，则称为元之间的关系呈线性，即满足
3、一组线性方程式，则称为线性码。线性码。（2 2）根据信息码元与监督码元之间的约束方式不同，）根据信息码元与监督码元之间的约束方式不同，可分为分组码和卷积码。分组码的监督码元仅与本码组可分为分组码和卷积码。分组码的监督码元仅与本码组的信息码元有关，卷积码的监督码元不仅与本码组的信的信息码元有关，卷积码的监督码元不仅与本码组的信息码元有关，而且与前面码组的信息码元有约束关系。息码元有关，而且与前面码组的信息码元有约束关系。（3 3）根据编码后信息码元是否保持原来的形式，可分）根据编码后信息码元是否保持原来的形式，可分为系统码和非系统码。在系统码中，编码后的信息码元为系统码和非系统码。在系统码中，编
4、码后的信息码元保持原样，而非系统码中的信息码元则改变了原来的信保持原样，而非系统码中的信息码元则改变了原来的信号形式。号形式。严谨 严格 求实 求是第一章 绪论（4 4）根据编码的不同功能，可分为检错码和纠错码。）根据编码的不同功能，可分为检错码和纠错码。（5 5）根据纠、检错误类型的不同，可分为纠、检随机）根据纠、检错误类型的不同，可分为纠、检随机性错误的码和纠、检突发性错误的码。性错误的码和纠、检突发性错误的码。（6 6）根据码元取值的不同、可分为二进制码和多进制）根据码元取值的不同、可分为二进制码和多进制码。码。本章只介绍二进制纠、检错编码。本章只介绍二进制纠、检错编码。严谨 严格 求实
5、 求是第一章 绪论 误码率一定时，非编码系统需要的输入信噪误码率一定时，非编码系统需要的输入信噪比与采用了纠错编码系统所需的输入信噪比之间的比与采用了纠错编码系统所需的输入信噪比之间的差值。（用差值。（用dB表示）表示）采用不同的编码会得到不同采用不同的编码会得到不同的编码增益，但编码增益的提高要以增加系统带宽的编码增益，但编码增益的提高要以增加系统带宽或复杂度来换取。或复杂度来换取。（1）码组中）码组中“1”的个数称为码组的重量。（的个数称为码组的重量。（w）5.编码增益编码增益6.码重、码距码重、码距严谨 严格 求实 求是第一章 绪论（3）某种编码中各个码组之间的距离的最小值称为最某种编码
6、中各个码组之间的距离的最小值称为最小码距（小码距（）0d 例：例：10011 w=3 01101（2 2）两个等长码组之间的对应位不同的位数，称）两个等长码组之间的对应位不同的位数，称为码距。又称为汉明距离。（为码距。又称为汉明距离。（d d）d=4例：例：10011 01101 01010d1=4 d0=3 d2=3d3=3严谨 严格 求实 求是第一章 绪论天津工业大学 信息学院 通信原理10ed（1）时能检出时能检出e e个或个或e e个以下错码。个以下错码。（2）（3）120 td时能纠正时能纠正t t个或个或t t个以下错码。个以下错码。时能检出时能检出t t个或个或e e个以下错码。
7、个以下错码。)(10teted7.e检错能力 t纠错能力严谨 严格 求实 求是第一章 绪论例例12-1 12-1 已知已知8 8个码组为：（个码组为：（O00000O00000），（），（001110001110），），（010101010101），（），（011011011011），（），（100011100011），），（1O11011O1101），），（110110110110），（），（111000111000），），（1 1）求以上码组的最小码距；（）求以上码组的最小码距；（2 2）若此）若此8 8个码组用于检错，个码组用于检错，可检出几位错？（可检出几位错？（3 3）若用于纠错码，
8、能纠几位？（）若用于纠错码，能纠几位？（4 4）若同时用于纠错和检错，纠错、检错性能如何？若同时用于纠错和检错，纠错、检错性能如何？30d10 ed13 e2e120 td123 t1t10ted （1）（2）（3）（4）严谨 严格 求实 求是第一章 绪论例例12-2 12-2 已知两码组（已知两码组（00000000）和（）和（11111111），若该码组），若该码组用于检错，能检出几位错码？若用于纠错，能纠用于检错，能检出几位错码？若用于纠错，能纠正几位错码？若同时用于纠错和检错，问各能纠、正几位错码？若同时用于纠错和检错，问各能纠、检几位错码？检几位错码？40d14 e3e124 t1t
9、14te1t2e （1）（2）（3）严谨 严格 求实 求是第一章 绪论一一.奇偶监督码奇偶监督码在信息位后加一位校验位在信息位后加一位校验位12.2 12.2 常用的简单编码常用的简单编码00121aaaann 奇监督码奇监督码偶监督码偶监督码特点：只能检测出奇数个错码，不能检测出偶数个错码10121aaaann严谨 严格 求实 求是第一章 绪论二二.二维奇偶监督码二维奇偶监督码012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn 行监督位行监督位列监督位列监督位严谨 严格 求实 求是第一章 绪论特点：特点：（1）能检测出每一行（列）中的奇数
10、个或偶数个错码，）能检测出每一行（列）中的奇数个或偶数个错码，但不能检测出行列同时成偶数个出现的错码。但不能检测出行列同时成偶数个出现的错码。（2）能检测突发性错误（成串错码）。）能检测突发性错误（成串错码）。（3）能纠正错码。）能纠正错码。三三.恒比码：恒比码：码组中均含有相同数目的码组中均含有相同数目的“1 1”或或“0 0”特点：能检测出组码中奇数个及部分偶数个码元得错特点：能检测出组码中奇数个及部分偶数个码元得错误。（误。（“1 1”错成错成“0 0”和和“0 0”错成错成“1 1”不能检测）。不能检测）。数字数字0123456789码字码字0110101011110011011011
11、0100011110101111000111010011严谨 严格 求实 求是第一章 绪论 四四.正反码正反码例：信息位：例：信息位：11001 11001 监督位：监督位：1100111001 信息位：信息位：10001 10001 监督位：监督位：01110011101.1.编码规则：编码规则：（1 1）当信息位中有奇数个）当信息位中有奇数个1 1时，监督位是信息位时，监督位是信息位的简单重复。的简单重复。（2）当信息位中有偶数个1时，监督位是信息位的反码。严谨 严格 求实 求是第一章 绪论例：例：11001 11001=0000011001 11001=00000 10001 01110
12、=11111 10001 01110=111112.2.译码方法译码方法（1 1）将码组中的信息码与监督码进行模）将码组中的信息码与监督码进行模2 2加得合加得合成码组。成码组。（2 2）若信息码中有奇数个）若信息码中有奇数个1 1，则合成码组即为检验，则合成码组即为检验码组。码组。若信息码中有偶数个若信息码中有偶数个1 1，则合成码组的反码即，则合成码组的反码即为检验码组。为检验码组。（3 3）观察检验码组中）观察检验码组中1 1的个数，按的个数，按p278p278进行检错进行检错和纠错。和纠错。严谨 严格 求实 求是第一章 绪论12.3 线性分组码线性分组码 一一.以（以（7 7，4 4）
13、分组码为例）分组码为例码字：码字：A=A=（）3456aaaa012aaa其中信息位：监督位：3456aaaa012aaa若分组码可用下列线性方程组表示：若分组码可用下列线性方程组表示：346035614562aaaaaaaaaaaa（“+”为模为模2加加 ）则：该分组码为（则：该分组码为（7 7，4 4）线性分组码（共有）线性分组码（共有1616个个码字）码字）严谨 严格 求实 求是第一章 绪论性质：性质：（1 1）封闭性：任意）封闭性：任意2 2个许用码组之和（模个许用码组之和（模2 2加）仍加）仍为一个许用码组。为一个许用码组。（2 2）有零元：）有零元：（3 3）有负元：）有负元：（4
14、 4）结合律成立：）结合律成立：iioAAAoiiAAA)()(432432AAAAAA（任一码字即为本身的负元）严谨 严格 求实 求是第一章 绪论二二.监督矩阵监督矩阵H H将上例中的式子改写为：将上例中的式子改写为：000034613562456aaaaaaaaaaaa0001011001110101011101000123456aaaaaaa用矩阵表示为：用矩阵表示为：并记为：并记为：OHAOAHTTT或严谨 严格 求实 求是第一章 绪论H阵可表示为：阵可表示为：rPIH100110101010110010111PkrrIrr（阶）（阶单位阵）矩阵矩阵H H称为（称为（7 7，4 4）线
15、性分组码得监督矩阵。上式）线性分组码得监督矩阵。上式也称为典型监督矩阵。若不是典型监督矩阵要用也称为典型监督矩阵。若不是典型监督矩阵要用初等变换化成典型矩阵。初等变换化成典型矩阵。严谨 严格 求实 求是第一章 绪论三三.生成矩阵生成矩阵G G 若信息码元已知，通过监督矩阵可以求出监若信息码元已知，通过监督矩阵可以求出监督码元。督码元。346035614562aaaaaaaaaaaa345603456134562110110110111aaaaaaaaaaaaaaa34563456012110110110111aaaaaaaaPaaa用矩阵表示：用矩阵表示：1101010111113456345
16、6012aaaaPaaaaaaaT或或严谨 严格 求实 求是第一章 绪论 将上式扩展可以由已知信息码元求得整个码将上式扩展可以由已知信息码元求得整个码组。组。110100010101000110010111000134560123456aaaaaaaaaaaTPIG41101000101010001100101110001令：令：G称为生成矩阵严谨 严格 求实 求是第一章 绪论典型监督矩阵和典型生成矩阵存在以下关系式：典型监督矩阵和典型生成矩阵存在以下关系式：rTrIQIPHTkkPIQIG),(knknr例：（例：（7，4）rIPH100110101010110010111TkPIG1101
17、000101010001100101110001严谨 严格 求实 求是第一章 绪论 34560123456aaaaaaaaaaa1101000101010001100101110001全部码字为：全部码字为：000111011001101011010011001001111001010100110100000000001111111001011101010111000011100110101001010011001111000130d10 ed2e120 td1t严谨 严格 求实 求是第一章 绪论四四.伴随式（校正子）伴随式（校正子）S S 设发送码字为设发送码字为 ，接收码字，接收码字为为
18、，由于干扰，噪声可能引入，由于干扰，噪声可能引入误差，使接收码组与发送码组不同，因此误差，使接收码组与发送码组不同，因此有有 ，其中，其中 是传输中产是传输中产生的错误行矩阵。对于二进制码元有生的错误行矩阵。对于二进制码元有:E矩阵中哪一位码元为矩阵中哪一位码元为1就表示接收码字中就表示接收码字中对应位有错。对应位有错。E称为错误图样。称为错误图样。021aaaAnn0121bbbbBnnEAB021eeeEnnABABE模模2严谨 严格 求实 求是第一章 绪论 在接收端用在接收端用H来检测接收来检测接收B中的错码。中的错码。令：令：THBS伴随式或校正子：伴随式或校正子：如果如果B与与A相同
19、，则：相同，则：0TTHAHBS否则：否则：0THBS又又EABTTTTTHEHEHAHEAHBS)(表示校正子表示校正子S仅与信道的错误图样仅与信道的错误图样E有关，而与有关，而与发送的码字发送的码字A无关。无关。严谨 严格 求实 求是第一章 绪论五五.如何利用如何利用S S完成纠错完成纠错对（对（7，4）线性分组码）线性分组码100110101010110010111H设设B中最高位有错，错误图样中最高位有错，错误图样0000001E1110000001TTHHES它的转置它的转置111TS恰好是典型恰好是典型H阵的第一列。阵的第一列。严谨 严格 求实 求是第一章 绪论同理可求出：同理可求
20、出：若次高位有错若次高位有错011S，即，即 恰好是恰好是H的第二列。的第二列。TS 因此，在接收码组中只错一位码元情况下，因此，在接收码组中只错一位码元情况下，计算出的校正子计算出的校正子S总是和典型监督矩阵总是和典型监督矩阵 中的中的某一行相同。某一行相同。TH例：例：1010000B1011010000HBHSTT与第三列相同与第三列相同严谨 严格 求实 求是第一章 绪论0000100E正确码组为：正确码组为：101010000001001010000EBA六六.汉明码汉明码 汉明码是一种可以纠正单个随机错误的线性汉明码是一种可以纠正单个随机错误的线性分组码。它的最小码距分组码。它的最小
21、码距 ，监督元位数，监督元位数 ，码长，码长 ，信息元位，信息元位数数 ，编码效率，编码效率当当r很大时，很大时，因此是一种高效码。，因此是一种高效码。30d)2(rknr12 rnrkr121211212rrrrrnkR1R严谨 严格 求实 求是第一章 绪论 上例中的（上例中的（7，4）线性分组码就是汉明码，）线性分组码就是汉明码，并且任意调换并且任意调换H矩阵中各列的结果不会影响纠，矩阵中各列的结果不会影响纠，检错能力。检错能力。严谨 严格 求实 求是第一章 绪论12.4 循环码循环码 一一.概念概念1.循环码：循环码：线性分组码线性分组码 （1）封闭性）封闭性 ),(kn（2）循环性：循
22、环码中任一许用码组经过循环）循环性：循环码中任一许用码组经过循环移位之后，所得到的码组仍为一许用码组。移位之后，所得到的码组仍为一许用码组。2.码多项式码多项式循环码的一许用码组循环码的一许用码组可表示为：可表示为：),(0121aaaaAnn012211)(axaxaxaxAnnnn其中：其中：x为码元位置标记，不考虑其取值。为码元位置标记，不考虑其取值。码元码元 只取只取“1”或或“0”。)1,1,0(niai严谨 严格 求实 求是第一章 绪论例例:(7，3）循环码中第二个码组）循环码中第二个码组 1110100)(1234562xxxxxxxA)0010111(2A124xxx如何实现移
23、位：乘一个如何实现移位：乘一个x相当于码左移一位。相当于码左移一位。xxxxxxA2352)()0101110(A3.按模运算按模运算若若)()()()()(xNxRxQxNxM（的次数小于的次数小于 ）则：则：)()()(xNxRxM模)(xR)(xN称为称为 按模按模 运算后运算后的余式。的余式。)(xM)(xN严谨 严格 求实 求是第一章 绪论例：例：1 133xx模 1 113224xxxxx模4.规律规律（1）循环码中，将许用码组）循环码中，将许用码组 左移左移一位得到的码字记为：一位得到的码字记为：。其。其码多项式为：码多项式为：可以证明：可以证明：),(0121aaaaAnn),
24、(1032)1(nnnaaaaA102312)1()(nnnnnaxaxaxaxA 1)()()1(nxxAxxA模 1)()()(niixxAxAx模严谨 严格 求实 求是第一章 绪论（2）根据循环码的定义，）根据循环码的定义，均为均为许用码字。许用码字。因此下列结论：若因此下列结论：若 是许用码字，则是许用码字，则 在按模在按模 运算下，也是许用码字。运算下，也是许用码字。)()3()2()1(,iAAAA)(xA)(xAxi1nx即：若即：若 1)()()(niixxAxAx模则则 也是许用码字。也是许用码字。)()(xAi例例:(7，3）循环码）循环码)0101110(3A则：则：1)
25、(125xxxxA7n那么那么 1)(734534583xxxxxxxxxxAx模其码字为其码字为 。4A严谨 严格 求实 求是第一章 绪论二二.生成多项式与生成矩阵生成多项式与生成矩阵G G1.(n，k)循环码码组集合中（全循环码码组集合中（全“0”除外）最除外）最高阶数最小的多项式高阶数最小的多项式（n-k）阶）阶称为生成多项称为生成多项式，记为式，记为g(x)。2.集合中其它码多项式都是集合中其它码多项式都是 运算运算下的余式。下的余式。即可以由生成多项式即可以由生成多项式g(x)产生循环码的全部码产生循环码的全部码字。字。)1()(nixngx模严谨 严格 求实 求是第一章 绪论3.生
26、成矩阵生成矩阵G循环码的生成矩阵多项式可以写成循环码的生成矩阵多项式可以写成_)()()()()(21xgxxgxgxxgxxGkk以（以（7，3）循环码为例）循环码为例1)(24xxxxg)()()()(2xgxxgxgxxG111010001110100011101G经线性变换，将经线性变换，将G整理成典型生成矩阵。整理成典型生成矩阵。严谨 严格 求实 求是第一章 绪论TkPIG111010001110100011101整个码组可表示为：整个码组可表示为：)()()()()(2456456xgxxgxgxaaaxGaaaxA任意一个码多项式都能被任意一个码多项式都能被g(x)整除。整除。)
27、()()(4526xgaxxgaxgxa)()(4526xgaxaxa严谨 严格 求实 求是第一章 绪论三三.监督多项式、监督矩阵监督多项式、监督矩阵1.对于对于(n，k)循环码，循环码，可分解成可分解成g(x)和其和其它因式的乘积。它因式的乘积。)()(1xhxgxn1nx记为：记为：称称h(x)为监督多项式，其矩阵形式为：为监督多项式，其矩阵形式为：kIPH 以（以（7，3）循环码为例）循环码为例111001111101TP1000101010011100101100001011H严谨 严格 求实 求是第一章 绪论)1)(1)(1(13237xxxxxx2.对于（对于（7，3）循环码，）循
28、环码，g(x)的最高次为的最高次为4所以，有两种方案所以，有两种方案)1()1(123347xxxxxx)1()1(324xxxxx第一种方案：第一种方案：1)(234xxxxg101110011100100111001101110001011100010111G1)(23xxxh严谨 严格 求实 求是第一章 绪论码字：码字：01011101110010101110000000000010111100101111001010111001第二种方案：第二种方案：1)(3xxxh1)(24xxxxg111010001110101101001111010001110100011101G码字：码字：1
29、0011100111010111010000000000100111101001100111011101001严谨 严格 求实 求是第一章 绪论例例:已知已知(7，4）循环码的生成多项式为）循环码的生成多项式为（1）求典型生成矩阵和典型监督矩阵；）求典型生成矩阵和典型监督矩阵；（2）输入信息码为）输入信息码为11001011，求编码后的系统码；，求编码后的系统码；（3）全部码组；）全部码组；（4）纠、检错能力）纠、检错能力 123 xx解：解：1)(23xxxg)()()()()(23xgxxgxgxxgxxGTkPIG1011000111010011000100110001101100001
30、0110000101100001011严谨 严格 求实 求是第一章 绪论四四.编码电路编码电路1.对于对于(n，k)循环码中，可用多项式表示为：循环码中，可用多项式表示为：)()()(xrxxmxAkn其中：其中：m(x)为不大于（为不大于（k-1）次的多项式，代表信息码）次的多项式，代表信息码元。元。r(x)为不大于为不大于(r-1)次的多项式，代表监督码元。次的多项式，代表监督码元。)()()(xhxgxA)()()()(xgxhxrxxmkn)()()()(xrxgxhxxmkn或：或：严谨 严格 求实 求是第一章 绪论)()()()()(xgxrxhxgxmxkn)()()(xgxrx
31、mxkn模该式提供了循环码编码的数学依据。该式提供了循环码编码的数学依据。2.步骤：步骤：（1）信息多项式）信息多项式m(x)左移左移n-k位。（相当于位。（相当于 ）（2）求其模）求其模g(x)的余式的余式r(x)（3）余式的系数作监督码元，附加在信息码元之后形）余式的系数作监督码元，附加在信息码元之后形成循环码。成循环码。knxxm)(严谨 严格 求实 求是第一章 绪论例例:已知已知(7，3）循环码的生成多项式为）循环码的生成多项式为求信息位为求信息位为101时的码字。时的码字。1)(24xxxxg严谨 严格 求实 求是第一章 绪论3.编码电路编码电路1D2D3D4D门1门2输入信息码元输
32、出码组 首先，四级移位寄存器清零，三位信息码元到来时，门1断开，门2接通，直接输出信息元。第3次移位脉冲来时将除法电路运算所得的余数存入四级移位寄存器，第47次移位时，门2断开，门1接通，输出监督码元（即余数）。当一个码字输出完毕后就将移位寄存器清零，等待下一组信息码元输入后重新编码。1)(234xxxxg严谨 严格 求实 求是第一章 绪论4.解码解码（1）只检错）只检错设发送码组为设发送码组为A，接收码组为，接收码组为B。)()()(xgxmxAB不出错时，有不出错时，有B(x)=A(x)则：则：能整除。能整除。余数不为余数不为0时，时，B有错。有错。)()()(xmxgxB严谨 严格 求实
33、 求是第一章 绪论框图：框图：（2）纠错）纠错用用B(x)除以除以g(x)得到余式得到余式按余式按余式 用查表的方法或通过某种运算得用查表的方法或通过某种运算得到到E(x)。)(xr)(xr严谨 严格 求实 求是第一章 绪论例：例：12-6 12-6 令令 为为(7(7，4)4)循环码的生成多项循环码的生成多项式。式。(1)(1)求出该循环码的生成矩阵和监督矩阵；求出该循环码的生成矩阵和监督矩阵；(2)(2)若两个信息码组分别为若两个信息码组分别为(1001)(1001)和和(0110),(0110),求出这两求出这两个循环码组；个循环码组；(3)(3)画出其编码器原理框图。画出其编码器原理框图。1)(3xxxg1101000011010000110100001101G解：（解：（1）1101000011010011100101010001100101101011100010111H严谨 严格 求实 求是第一章 绪论（2）（3）严谨 严格 求实 求是第一章 绪论（4）0101110100011000110101110010101110001101001101000000000011111110010111100101101000110001101110010101110011010001
