1、第 12 章差错控制编码本章主要内容n12.1 引言n12.2 纠错编码的原理几个基本概念最小码距与检错或纠错能力的关系n12.3 常用的简单编码n12.4 汉明码n12.5 循环码12.1 引言n一、为什么引入差错控制编码？数字信号在传输过程中由于信道特性不理想以及加性噪声和人为干扰的影响，使接收端产生错误判决，即误码。降低误码率的方法：1.降低数字信道本身引起的误码。例如，可以加大发射功率，降低接收设备本身的噪声，以及合理选择抗干扰能力强的调制和解调方法等。2.采用差错控制编码，也就是信道编码。n二、差错控制编码的基本原理：通过对信息序列作某种变换，使原来彼此独立、相关性极小的信息码元产生
2、某种相关性，在接收端可以利用这种规律性来检查并纠正信息码元在信息传输中所造成的差错。实质上，加入冗余信息，起“监督”作用例如：001011“”“”发发送送端端“”“”“发送端1接收端”“0：和信源只有两个消息BA无法检错可以检错”“；”“1 0BA重复码重复码10“”接接收收端端01“”接接收收端端信道n三、差错控制的常见方式：1.检错重发(ARQ，Automatic Repeat reQuest)”“”“”“”“发送端111000正确接收检错重发1能能够够检检错错 位位。”“发送端112不能检错 位10“”接收端01“”接收端11“”接收端11000如果发“”，收“”，则误判为“”，判决规则
3、：有误码就重发判决规则：有误码就重发例子：发送端发送端接收端接收端检错码检错码判决信息判决信息2.前向纠错(FEC，Forward Error Correction)”“”“”“”“发送端11110000接收端”“110111100如果发“”，收“”“发送端111”，即“接收端判决为“11111能够纠错 位。2不能检错或纠错 位。0000则误判为“”，即“”。或010“”011“”接收端101“”接收端或001“”111“”接收端正确接收判决规则：根据判决规则：根据“0”和和“1”个数判决，个数判决，“1”的个数多就判决为的个数多就判决为“1”，反之亦然。，反之亦然。例子：发送端发送端接收端接
4、收端纠错码纠错码3.混合差错控制(HEC，Hybrid Error Correction)”“”“”“”“发送端11111000000111“”接收端”“发送端1111”，即“接收端判决为“111110101“”接收端检错重发接收端”“11101101“”接收端1011“”接收端1111“”接收端正确接收1100“”接收端0110“”接收端11“00”接收端1010“”接收端01“10”接收端1 能够纠错 位2 能够检错 位判决规则：根据判决规则：根据“0”和和“1”个数判决，个数判决，“1”的个数多就判决为的个数多就判决为“1”，反之亦然。，反之亦然。如果如果“0”和和“1”个数相等，重发个
5、数相等，重发例子：发送端发送端接收端接收端检错和纠错码检错和纠错码判决信息判决信息1111如果发“”，1 2 结果：能够纠错 位，并能够检错 位。3不能检错 位。1000收“”，00000则误判为“”，即“”。或或0100“”,或或0010“”,或或0001“”,nARQ与HEC比较”“”“”“”“发送端1111100000”“发送端1111:ARQ检错重发1000“”接收端3能能够够检检错错 位位，没没有有纠纠错错能能力力”“发送端1111:HEC检错重发接收端”“110021能能够够检检错错 位位，并并能能够够纠纠错错 位位。接收端”“111011111纠正为“”，纠错 位1000“”接收
6、端0000误判为“”接收端”“1110检错重发接收端”“1100检错重发12.2 纠错编码的原理n一、几个基本概念1.分组码：将若干监督位附加在一组信息位上构成一个具有纠错功能的独立码组，并且监督位仅监督本组中的信息码元。分组码一般用（n,k）表示例如：汉明码(7,4)；0011110中，0011 是信息位，110 是监督位7;n 4;k 743rnk1na2nara1ra0ak个个信信息息位位r个个监监督督位位nkr码码长长2.系统码和非系统码系统码：编码后的信息码元保持原样。非系统码：编码后的信息码元改变了原来的信号形式。3.线性码和非线性码线性码：信息码元与监督码元之间为线性关系。非线性
7、码：信息码元与监督码元之间为非线性关系。4.许用码组和禁用码组许用码组：发送端有可能输出的码组。禁用码组：发送端不可能输出的码组。例如：则：许用码组是“000”和“111”；禁用码组是“001”、“010”、“100”、“110”、“101”、“011”。如果在接收端接收到禁用码组，则可以知道发生了误码。”“”“”“”“发送端111100005.编码效率对于分组码(n,k)，定义6.码重：二进制码组中“1”的个数，用W表示例如：码组“10001”的码重是2。7.码距：两个等长码组之间对应位不同的个数，用 d 表示。nkR 100010101 1001003d 这这两两个个码码组组的的码码距距是
8、是 4d这这两两个个码码组组的的码码距距是是8.最小码距：码组集合中各码组之间的码距的最小值，用d0表示。1000110110110113d3d2d02d 这这三三个个码码组组组组成成的的集集合合的的最最小小码码距距 9.两个等长码组的码距等于这两个码组对应位进行模2加（“”）所得的码组的码重。二进制数的模2加（“”）运算规则：0 0=0；1 1=0;0 1=1;1 0=1 规律：两个一样的二进制数进行模2加，得0 两个不一样的二进制数进行模2加，得1 即：模2加运算等价于数字逻辑中的异或运算 （不同为1，相同为0）100010101 13d 这这两两个个码码组组的的码码距距是是 1 1 0
9、1 0W这个码组的码重=3n二、最小码距与检错或纠错能力的关系1.为检测 e 个错误，最小码距应满足1011111111011001111001100100110000101000000004d01maxed01de01edmaxe01de1ABOAAA判决规则：判决规则：有误码就重发有误码就重发2.为纠正 t 个错误，最小码距应满足1111111110100000000005d 021 maxtd021dtmaxtmaxt021 td021dt1AOAA1110011000BOBB判决规则：判决规则：根据根据“0”和和“1”个数判决，个数判决，“1”的个数多就判决为的个数多就判决为“1”，反
10、之亦然。反之亦然。3.为纠正 t 个错误，同时又能够检测 e 个错误，e t,最小码距应满足 1011111111011001111001101100100004d01maxetd 01 detmaxett01 etd01 det1ABOA0000OAB判决规则：判决规则：根据根据“0”和和“1”个数判决，个数判决，“1”的个数多就判决为的个数多就判决为“1”，反之亦然。反之亦然。如果如果“0”和和“1”个数相等，重发。个数相等，重发。小结：1.为检测 e 个错误，最小码距应满足2.为纠正 t 个错误，最小码距应满足3.为纠正 t 个错误，同时又能够检测 e 个错误（et），最小码距应满足01
11、 det01de021dtn作业：题12.1n已知8个码组为：（O00000），（001110），（010101），（011011），（100011），（1O1101），（110110），（111000），（1）求以上码组的最小码距 d0；（2）若此8个码组用于检错，可检出几位错？（3）若用于纠错码，能纠几位？（4）若同时用于纠错和检错，e 能不能大于 t？12.3 常用的简单编码n一、奇偶校验码奇偶校验码分为奇数检验码和偶数校验码。无论信息位有多少，监督位只有1位。偶数校验码：它使码组中“1”的数目为偶数。“”表示模2加。00121aaaann信息位信息位监督位监督位1nRn1210.nna
12、aaan ，模2加 运算：多个二进制数（“0”或“1”）连续进行模2加 运算，如果有偶数个“1”则结果为“0”；如果有奇数个“1”则结果为“1”。n奇偶校验码只能发现奇数个错误，不能发现偶数个错误，不能纠错。偶校验规则：201 aaa000001010101011 11 1012100aaa101101=0 101111=1 21aa210aaan二、二维奇偶校验码以二维偶校验码为例，101 110 001 10101 100001 101011010100000110101发送端接收端321aaa0a321aaa0a3210 aaaa32100aaaa10101 10010010101可以检
13、测在某一行出现偶数个错误；可以检测在某一行出现偶数个错误；可以纠正可以纠正1位错误。位错误。n三、恒比码每个码组均含有相同数目的“1”和“0”。下表是 5中取3恒比码。在接收端检测时，只需计算接收码组中“1”的数目是否正确，就可以知道有无错误。不属于分组码。数字0123456789码字01101 01011 11001 10110 11010 00111 10101 11100 01110 10011附加知识点n线性分组码：监督位与信息位呈线性关系，即任何一位监督位可以由若干信息位进行线性代数运算得到。n包括：奇偶校验码，重复码，汉明码，循环码，戈雷码等12.4 汉明码n一、定义：一种能够纠正
14、1位错码并且效率较高的线性分组码。最小码距d0=3。下面以（7,4）汉明码为例讲解6543210aaaaaaa4k 3r 7nkr信信息息位位监监督督位位系系统统码码n二、监督方程的概念 6543654653621021430=aaaaaaaaaaaaaaaaaaa6543210aaaaaaa6524aaaa6513aaaa6403aaaa个数为 监督位的数目，r=3线性不相关，即不能由两个方程推导出另外一个方程6543210aaaaaaa0011110信息码信道编码器系统码6543 a a a a6543210 a aaaaaa监督方程6543654653621021430=aaaaaaaa
15、aaaaaaaaaaa信息位监督位信息位监督位a6 a5 a4 a3a2 a1 a0a6 a5 a4 a3a2 a1 a00000000100100011010001010110011100001110111011010101100010001001101010111100110111101111111100010001001010100111（7,4）汉明码编码表）汉明码编码表n三、校正子 S 先把监督方程整理成“=”的右边全为“0”，再把“0”分别用 代替。6524aaaa6513aaaa6403aaaa12,.,rS SS65421aaSaa65310aaaa64300aaaa65420
16、aaaa65312aaSaa64303aaSaa发发发发发发收收收n（1）在发送端，全为“0”（2）在接收端，不一定全为“0”n在接收端，若 全为“0”，认为正确接收；若 不全为“0”，则肯定有误码。n观察 除全为“0”外，还有情况，可以指示 种仅错1位情况。n 所以，纠正1位错码，要求 ，为了使编码效率最大，选取 。12,.,rS SS12,.,rS SS12,.,rS SS(21)r(21)r21rn 21rn 12,.,rS SS12,.,rS SS 接收端：在无错和仅错一位的情况下，校正子与错码位置的关系0a 错6543654165326423310210aaaaaaaSaaaaaaa
17、SaSaaaa10S 20S 31S 1a 错10S 21S 30S 2a 错11S 20S 30S 3a 错10S 21S 31S 4a 错11S 20S 31S 5a 错11S 21S 30S 6a 错11S 21S 31S 无错10S 20S 30S 123 TS S S注意列向量的值与监督方程对应列的关系在仅错一位的情况下，如何找到错码位置？第一步：根据监督方程计算校正子第二步：方法一：根据校正子的值查验监督方程的对应码位 例题：判断码字是否正确，如有错误，指出错码位置 6543654165326423310210aaaaaaaSaaaaaaaSaSaaaa001011010S 21S
18、 31S 3a 错第第一一步步：第第二二步步：查验监督方程在仅错一位的情况下，如何找到错码位置？第一步：根据监督方程计算校正子第二步：方法二：根据 S1 S2 S3T与监督方程对应列的关系例题：判断码字是否正确，如有错误，指出错码位置 6543654165326423310210aaaaaaaSaaaaaaaSaSaaaa001011010S 21S 31S 3a 错查看监督方程的对应列第第一一步步：第第二二步步：n试求：判断码字 是否正确，如有错误，指出错码位置。n解：6543654165326423310210aaaaaaaSaaaaaaaSaSaaaa11S 21S 30S 5a 错00
19、011001010101第第一一步步方法一：查验监督方程方法二：查看监督方程的对应列第第二二步步n四、监督矩阵H (r行 x n列)在发送端，有 2102165436546536304000aaaaaaaaaaaaaaaaaaaH 001011011101111000011rnr krPI与典型监督矩阵典型监督矩阵1S2S3SH矩阵中数值相同的一列对应错码位置H0010110111011110000116a5a4a3a2a1a0a000TA6310524Aaaaaaaa设系统码 0TH A记为 0TA H或1S2S3S发送端发送端接收端接收端发送端发送端接收端接收端 TTSH A123SSSS
20、校正子在仅错一位的情况下，如何找到错码位置？解题步骤：第一步：根据监督方程计算校正子S第二步：根据校正子的值查H矩阵，对应列即为错码位置例题：判断码字是否正确，如有错误，指出错码位置0010 111TSH第二步：与矩阵中数值相同的一列 对应错码位置6543654165326423310210aaaaaaaSaaaaaaaSaSaaaaH 001011011101111000011rn11110001 1S 20S 3 1S 第一步：第一步：计算计算校正子校正子4a 错n五、生成矩阵G (k行 x n列)若存在一个矩阵G，使得信息矩阵xG=系统码矩阵则称矩阵G为生成矩阵。例如：654365320
21、41 G a a a aa aaaaaaG 0010110111011110011kn000000001kk rIQ6543654653621021430=aaaaaaaaaaaaaaaaaaa典型生成矩阵典型生成矩阵2a1a0a行行与行之间与行之间线性无关线性无关n观察典型监督矩阵H和典型生成矩阵GH 001011011101111000011rnG 0010110111011110011kn000000001r krPIkk rIQTPQ有TrrHP IQITkkGIQIPn六、生成矩阵G 的每一行都是许用码组 1 0 0 000101101110111100110000000011 0
22、0 0 1 1 10 1 0 000101101110111100110000000010 1 0 0 1 1 0n六、典型生成矩阵G 的每一行都是许用码组 0 0 1 000101101110111100110000000010 0 1 0 1 0 10 0 0 100101101110111100110000000010 0 0 1 0 1 1n七、错误图样E (1行 x n列)发送码组：接收码组：错误图样E：2165430B b b b b b b b2165430A a a a a a a a6543210EAB e e e e e e e0,1,iiiiibaeba当式中当 1 1
23、0 0 0 0 1发送端：1 1 1 0 0 0 1接收端：0 0 1 0 0 0 0错误图样：n八、线性分组码的性质（1）全零码组必定是线性分组码中的一个码字 0 0 0 000101101110111100110000000010 0 0 0 0 0 0（2）封闭性 一种线性分组码中任意两个许用码组之和（模2加）仍为这种码中的一个许用码组。设 和 是一种线性码中的两个许用码组，则 仍为其中的一个许用码组。1A2A12()AA12 0,0TTA HAH因为1212 =0TTTA HAHAAH所以（）证明：（3）码的最小距离即是码的最小重量。因为线性码具有封闭性，因而两个码组之间的距离必是另一
24、个码组的重量（除全0码组外）。其中：汉明码的最小距离为3。（4）生成矩阵G每行都是许用码组。已知，典型生成矩阵G 的每一行都是许用码组；又因为，线性分组码的封闭性，即任意两个许用码组之和（模2加）仍为这种码中的一个许用码组；由典型生成矩阵经过初等变换可以获得非典型生成矩阵 所以，无论是典型生成矩阵还是非典型生成矩阵，生成矩阵的生成矩阵的每一行都是许用每一行都是许用码组；码组；00101110111111000110000100000010110111011110011000000001非典型生成矩阵（5）生成矩阵G中，行与行之间线性无关。（6）在线性分组码（n,k）中，任意找到k个线性无关的许
25、用码组，就可以构造生成矩阵。（如果所构造的生成矩阵是非典型生成矩阵，则可以通过初等变换得到典型生成矩阵。）例题1：（重点考试题型）已知（7,4）汉明码监督方程如下：求：(1)监督矩阵和生成矩阵。(2)分别求出信息“1010”时的系统码。(3)若收到“1100101”，试判断是否有错码？如果有1位错码，指出哪位错？(4)求错误图样。26510aaaa54310aaaa65300aaaa2102116543655435306000aaaaaaaaaaaaaaaaaaaH 100011011010111100011非典型监督矩阵非典型监督矩阵解：（1）4k 3r 信信息息位位监监督督位位与1S2S3
26、SH矩阵中数值相同的一列对应错码位置H 100011011010111100011将非典型监督矩阵转换为典型监督矩阵H 110011010110111000011利用线性代数的初等变换，典典型型非非典典型型r k rPI Tkk rkr kGIQIP典型生成矩阵H 110011010110111000011典典型型r k rPIG 0000101100010010111101000111(2)求信息“1 0 1 0”的系统码方法1：由监督方程计算监督位 可得信息“1010”的系统码为“1010011”26510aaaa54310aaaa65300aaaa6053aaaa5143aaaa6215
27、aaaa6a5a4a3a=100=1=010=1=101=0方法2：信息与典型生成矩阵G计算得到系统码10101000101010001100101100001111111 0 1 0 0方法3：典型生成矩阵G的某些行进行模2加运算（适合信息位中“1”的个数不多的场合）“1010”1000101010001100101100001111G典典型型生生成成矩矩阵阵 111 0 1 0 0(3)若收到“1 1 0 0 1 0 1”，试判断是否有错码？如果有1位错码，指出哪位错？解：第一步：根据监督方程计算校正子S26115aaaSa54312aaaSa65303aaaSa计算可得11S21S31S
28、监督方第二步程直接：方法1：对得到的照由监督矩阵H 100011011010111100011非非典典型型5a结果为错6a5a4a3a2a1a0aTSH与矩阵中数值相同的一列对应错码位置2102116543655435306000aaaaaaaaaaaaaaaaaaa方法2：对照监督方程11S21S31S1（）2（）5a 错方法一：查验监督方程方法二：查看监督方程的对应列(4)求错误图样。解：已知 错，可得错误图样为 0100000作业：12.55a例题2：已知（7,4）汉明码的生成矩阵为：求：(1)监督矩阵和监督方程。(2)当输入序列为“110101101010”时，求编码器的输出序列。(3
29、)若收到“0010101”，试判断是否有错码？如果有1位错码，指出哪位错？(4)求错误图样。1000101010011100101100001011G解：因为1000101010011100101100001011Gkk rIQ是典型生成矩阵100111111011H001000011 Tr krk rkHPIQI典型监督矩阵(1)求监督矩阵和监督方程。H100011011110111000011由监督矩阵可得监督方程由监督矩阵可得监督方程2102165436545436305000aaaaaaaaaaaaaaaaaaa4k 3r 信信息息位位监监督督位位即，监督方程为即，监督方程为6524a
30、aaa5431aaaa6530aaaa(2)当输入序列为“1 1 0 1 0 1 1 0 1 0 1 0”时，求编码器的输出序列。1237434110101101010nkrAAA解解：，故故将将输输入入序序列列每每 个个码码元元分分一一段段，依依次次记记为为，方法1：由监督方程计算监督位5264aaaa4153aaaa5063aaaa110=0 101=0 111=1 11101A 对对于于6a5a4a3a10011101A 编编码码后后的的系系统统码码为为方法2：信息与典型生成矩阵G计算得到系统码11101A 对对于于100010101001111 1010010110000101111
31、10100=1A G方法3：典型生成矩阵G的某些行进行模2加运算1000101010011100101100001011G11101A 对对于于101 1 0 1 0 10011101A 编编码码后后的的系系统统码码为为23=01100110=1010010110 0101AA利利用用类类似似的的方方法法，编编码码后后的的系系统统码码为为编编码码后后的的系系统统码码为为 110101101010 001001011101011010110所所以以，当当输输入入序序列列为为时时，编编码码器器的的输输出出序序列列为为(3)若收到“”，试判断是否有错码？如果有1位错码，指出哪位错？解：第一步：由监督
32、方程可得在接收端计算校正子的公式6524aaaa5431aaaa6530aaaa65421aaaaS54312aaaaS65303aaaaS计算可得10S21S31S00101016a5a4a3a2a1a0aTSH方法1：与矩阵中数值相同的一列对应错码位置H1000110111101110000116a5a4a3a2a1a0a10S21S31S3a结果为错第二步：方法2：对照监督方程2102165436545436305000aaaaaaaaaaaaaaaaaaa123=TSSSS校正子列向量与监督方程的对应列即为错码位置。10S21S31S3a结果为错解：已知 错，可得错误图样为 00010
33、003a(4)求错误图样。12.5 循环码n一、定义 循环码中任意一个许用码组经过循环移位之后，所得的码组仍为一个许用码组。下表给出了（7,3）循环码的全部码组。码组编号12345678码组0000000 0011101 0100111 0111010 1001110 1010011 1101001 11101000 0 11 110第2号码组第4号码组第8号码组第7号码组第6号码组第3号码组第5号码组n二、码多项式及模运算 1.码多项式把码组中的各码元当作一个多项式的系数上式称为码多项式，x只是作为码元位置的标记。例如：0 1 0 0 1 1 1 121210nnnnaxaxa xa6543
34、20100111xxxxxx 521xxx2.码多项式运算（1）“”，“”就是码多项式的系数按“模2加”运算。例如：52(1)xxx632(1)xxx521xxx6321xxx6x5x3xx653xxxx（2）“”，“”过程中的“”和“”是“模2加，”例如：2(1)x 32(1)xx2x15x3x2x4x13x5x4x5431xxx对应位2x13x2x1 例如：2(1)x 2x2(1)x 15x3x2x4x13x4x5431xxx（）对应位543+1xxx2x112x对应位0321xx对应位（3）模运算 一个码多项式A(x)被B(x)除，得到的余式C(x)，称C(x)为A(x)进行模B(x)的
35、运算结果。记为：A(x)C(x)（模B(x)）例如：x3(1)x 12x4x x对应位42+1xxx42+1xx3(1)x（模12xx12xx3.若多项式T(x)是一个码长为n的许用码组，则 在模 运算下也是一个许用码组例：（1）在表中取出第5号码组 1 0 0 1 1 1 0 对应的码多项式为 （2）把它乘以 ，设m=3，即 （3）进行模（）运算，n为系统码的长度，本例为n=7，即 632xxxx1nx 3xmx71x 63239654()xxxxxxxxx()mxT x(1)nx 7(1)x 9654xxxx2x9x2x6x5x4x2x965465427 (1)xxxxxxxxx模6542
36、 1 1 1 0 1 0 0 8xxxx对应的码组为即第 号码组1)mnxx 结论：把一个许用码组乘以再进行(模运算，m结果仍然为一个许用码组，即左循环移位 次。5第 号码组1 1 10001n三、码的生成多项式和生成矩阵 1.码的生成多项式 定义：前（k-1）位皆为“0”而前面第k位为“1”的码组所对应的码多项式，并记为g(x)。在（7,3）循环码中的第二号码组0011101所对应的码多项式即为码的生成多项式，并记为g(x)。g(x)必须是一个且仅有一个、同时常数项不为“0”的（n-k）次多项式，即r次多项式。432()1g xxxx2.生成矩阵 G 对于（对于（n,k）线性分组码，有了生成
37、矩阵）线性分组码，有了生成矩阵G，就可以，就可以由由k个信息码元得到相应的系统码。个信息码元得到相应的系统码。已知，生成矩阵已知，生成矩阵G的每一行都是一个许用码组，因的每一行都是一个许用码组，因此若能找到此若能找到k个线性无关的许用码组，就能构成生成个线性无关的许用码组，就能构成生成矩阵。矩阵。21(),(),(),()kg xx g xxg xxg x 都都是是许许用用码码组组k而而且且这这 个个码码组组都都是是线线性性无无关关的的。G循循环环码码的的生生成成矩矩阵阵12()()()()()kkxg xxg xG xx g xg x 0011101()g x1左循环移位 次0111010
38、x相当于乘以()x g x11101002()xg x1左循环移位 次x相当于乘以G kn0110101001101110110102()()()()xg xG xx g xg x非典型生成矩阵非典型生成矩阵k行行线性线性无关无关生成生成矩阵矩阵生成矩阵生成矩阵G也可以写为也可以写为1()()()()kxg xG xx g xg x3k 本本例例中中,利用初等变换，将非典型生成矩阵G变换为典型生成矩阵GG 011010100110111011010 011010100110111010101G 011010101111001010101G 利用初等变换 kk rIQ典型典型生成矩阵生成矩阵由生
39、成矩阵获得信息码由生成矩阵获得信息码110的循环码的循环码011010100110111011010利用非利用非典型典型生成矩阵生成矩阵G 110 1 01101 0011010101111001010101利用典型生成矩阵利用典型生成矩阵G 110 1011010不是系统码不是系统码是系统码是系统码3.监督矩阵 H 100101011100101000011kk rIQ由典型生成矩阵可得典型监督矩阵Tr krk rrHPIQIG 01101010111100101010111001004.监督方程和校正子 由监督矩阵H 1001010111001010000111100100可得监督方程63
40、4aaa6254aaaa615aaa504aaa6a5a4a3a2a1a0a在接收端，校正子S1634aaSa26542Saaaa3615aaSa4504aaSaTSH与矩阵中数值相同的一列对应错码位置n四、循环码的编码器 4327 3()1g xxxx在（，）循环码中，若选定 D0D1D2D3 门1门2 输入信息码元输出码组先断后开先开后断01234D D D D 是 级移位寄存器()0g x反馈线的连接与的非 系数相对应4327 3()1g xxxx在（，）循环码中，若选定门2 D0D1D2D3 门1 输入信息码元输出码组110设信息位为 则系统码元为 110 1001输入信息码元 110
41、 00000000断开111111110100开断0 0 0 00 10移移位位次次序序输入输入移位寄存器移位寄存器输输出出0123DDDD134567211000001011100101010100001000010000110100100000/例题1：（重点考试题型）已知（7,4）循环码生成多项式：求：(1)监督矩阵和生成矩阵。(2)若信息为“1100”，求系统码。(3)若接收端收到“1011101”，试判断有没有误码？如果有误码，指出是哪一位错了？（假设传输时最多只有一个误码）(4)画出构成该循环码的编码器电路。32()1g xxx解：（1）32()1g xxx0 0 0 1 1 0
42、1G=0010101010100111100001000011 G=0010101011110011100001000011非典型生成矩阵0 01 0 101G=0010101011110011100001000011 G=1001100001010101111001000011重写G=0010101011110010011001000011重写 G=0010101011110010011000011010典型生成矩阵kk rIQ Tr krk rrHPIQI可可得得典典型型监监督督矩矩阵阵典型生成矩阵G=0010101011110010011000011010kk rIQ重写=1101110
43、01010100011101解：（2）若信息为“1 1 0 0”，求系统码方法一：由监督矩阵H=110010111010100110011写出监督方程6243aaaa6154aaaa5043aaaa计算监督位2100=1a 1110=0a 0100=1a 6a5a4a3a1100101系统码为“”方法二：信息与典型生成矩阵G计算得到系统码101 1 0 0 1若信息为“1 1 0 0”，求系统码00101010111100100110000110101 1 0 0方法三：通过典型生成矩阵G的某些行进行模2加运算G=0010101011110010011000011010若信息为“1 1 0 0
44、”，求系统码 系统码为0111001(3)若接收端收到“1 0 1 1 1 0 1”，试判断有没有误码？如果有误码，指出是哪一位错了？由监督方程写出在接收端校正子的计算公式64321aaaSa65412aaaSa54303aaaSa计算校正子10S 20S 31S 对照典型监督矩阵H的列，H=1100111101010011001100a 错解：6a5a4a3a2a1a0a6a5a4a3a2a1a0a=1111=0 =1010=0=0111=1 (4)画出构成该循环码的编码器电路。D0D1D2 门1门2 输入信息码元输出码组32 ()1 g xxx由可以直接画出编码器例题2：已知（7,3）循环
45、码的一个码字为 1001011求：(1)写出生成多项式g(x).(2)写出生成矩阵和监督矩阵。(3)若信息为“110”，求系统码。(4)若接收端收到“1010111”，试判断有没有误码？如果有误码，指出是哪一位错了？（假设传输时最多只有一个误码）(5)画出构成该循环码的编码器电路。解：（1）已知（7,3）循环码的一个码字为 100101142()1g xxxx0001111由生成多项式g(x)的定义，即前（k-1）位皆为“0”而前面第k位为“1”的码组所对应的码多项式通过左循环移位，可得解：（2）写出生成矩阵和监督矩阵。G=011110010110010001111非典型生成矩阵0 11 1
46、100G=011110010110010110011 典型生成矩阵kk rIQ=0010101000000001G=Tr krk rrHPIQI可可得得典典型型监监督督矩矩阵阵典型生成矩阵重写011110010110010001111kk rIQ011111101101解：（3）若信息为“1 1 0”，求系统码方法一：写出监督方程524aaa6154aaaa604aaa计算监督位210=1a 1110=0a 010=1a 6a5a4a1100101系统码为“”H=0010101000000001011111101101635aaa由典型监督矩阵311=0a 6a5a4a3a2a1a0a方法二：
47、信息与典型生成矩阵G计算得到系统码11 0 101 1 0 0 1若信息为“1 1 0”，求系统码011110010110010001111方法三：通过典型生成矩阵G的某些行进行模2加运算若信息为“1 1 0”，求系统码 系统码为0111001G=011110010110010001111方法四：若信息为“1 1 0”，求系统码21 kn对对于于 的的循循环环码码，可可以以使使用用任任何何一一个个码码组组通通过过循循环环移移位位得得到到另另一一个个码码组组。0001111由题干中所给的循环码组，可以得到由题干中所给的循环码组，可以得到由由生成多项式生成多项式g(x)所对应的循环码组，可以得到所
48、对应的循环码组，可以得到0001111(4)若接收端收到“1 0 1 0 1 1 1”，试判断有没有误码？如果有误码，指出是哪一位错了？由监督方程写出在接收端校正子的计算公式6513aaSa5422aaSa65413aaaSa计算校正子11S 20S 31S 对照典型监督矩阵H的列，6a 错解：6a5a4a3a2a1a0a6a5a4a3a2a1a0a=100=1=011=0=1011=1 6440aaSa=111=1 41S H=0010101000000001011111101101(5)画出构成该循环码的编码器电路。42 ()1 g xxxx由可以直接画出编码器 D0D1D2D3 门1门2 输入信息码元输出码组作业：（重点考试题型）已知（7,3）循环码生成多项式：求：(1)监督矩阵和生成矩阵。(2)若信息为“101”，求系统码。(3)若接收端收到“1011101”，试判断有没有误码？如果有误码，指出是哪一位错了？（假设传输时最多只有一个误码）(4)画出构成该循环码的编码器电路。42()1g xxxx
