通信原理 Ch12 差错控制编码（2014年版）课件.pptx

《通信原理 Ch12 差错控制编码（2014年版）课件.pptx》由会员分享，可在线阅读，更多相关《通信原理 Ch12 差错控制编码（2014年版）课件.pptx（108页珍藏版）》请在三一办公上搜索。

1、第 12 章差错控制编码,本章主要内容,12.1 引言12.2 纠错编码的原理几个基本概念最小码距与检错或纠错能力的关系12.3 常用的简单编码12.4 汉明码12.5 循环码,12.1 引言,一、为什么引入差错控制编码？数字信号在传输过程中由于信道特性不理想以及加性噪声和人为干扰的影响，使接收端产生错误判决，即误码。降低误码率的方法：1. 降低数字信道本身引起的误码。例如，可以加大发射功率，降低接收设备本身的噪声，以及合理选择抗干扰能力强的调制和解调方法等。2. 采用差错控制编码，也就是信道编码。,二、差错控制编码的基本原理： 通过对信息序列作某种变换，使原来彼此独立、相关性极小的信息码元产

2、生某种相关性，在接收端可以利用这种规律性来检查并纠正信息码元在信息传输中所造成的差错。 实质上，加入冗余信息，起“监督”作用例如：,重复码,三、差错控制的常见方式：1. 检错重发(ARQ，Automatic Repeat reQuest),判决规则：有误码就重发,例子：,2. 前向纠错(FEC，Forward Error Correction),判决规则：根据“0”和“1”个数判决，“1”的个数多就判决为“1”，反之亦然。,例子：,3. 混合差错控制(HEC，Hybrid Error Correction),判决规则：根据“0”和“1”个数判决，“1”的个数多就判决为“1”，反之亦然。如果“0

3、”和“1”个数相等，重发,例子：,ARQ与HEC比较,12.2 纠错编码的原理,一、几个基本概念1. 分组码：将若干监督位附加在一组信息位上构成一个具有纠错功能的独立码组，并且监督位仅监督本组中的信息码元。分组码一般用（n,k）表示例如：汉明码(7,4)；0011110中，0011 是信息位，110 是监督位,2. 系统码和非系统码系统码：编码后的信息码元保持原样。 非系统码：编码后的信息码元改变了原来的信号形式。3. 线性码和非线性码线性码：信息码元与监督码元之间为线性关系。非线性码：信息码元与监督码元之间为非线性关系。,4. 许用码组和禁用码组许用码组：发送端有可能输出的码组。禁用码组：发

4、送端不可能输出的码组。例如：则：许用码组是“000”和“111” ； 禁用码组是“001”、“010”、“100”、 “110”、“101”、“011”。 如果在接收端接收到禁用码组，则可以知道发生了误码。,5. 编码效率对于分组码( n , k )，定义6. 码重：二进制码组中“1”的个数，用W表示例如：码组 “10001”的码重是2。7. 码距：两个等长码组之间对应位不同的个数，用 d 表示。,8. 最小码距：码组集合中各码组之间的码距的最小值，用d0表示。,9.两个等长码组的码距等于这两个码组对应位进行模2加（“”）所得的码组的码重。 二进制数的模2加（“”）运算规则： 00=0；11=

5、0; 01=1; 10=1 规律：两个一样的二进制数进行模2加，得0 两个不一样的二进制数进行模2加，得1 即：模2加运算等价于数字逻辑中的异或运算 （不同为1，相同为0）,二、最小码距与检错或纠错能力的关系1. 为检测 e 个错误，最小码距应满足,1011,1111,1101,1001,1110,0110,0100,1100,0010,1000,0000,判决规则：有误码就重发,2. 为纠正 t 个错误，最小码距应满足,11111,11110,10000,00000,11100,11000,判决规则：根据“0”和“1”个数判决，“1”的个数多就判决为“1”， 反之亦然。,3.为纠正 t 个错

6、误，同时又能够检测 e 个错误， e t,最小码距应满足,1011,1111,1101,1001,1110,0110,1100,1000,0000,判决规则：根据“0”和“1”个数判决，“1”的个数多就判决为“1”，反之亦然。如果“0”和“1”个数相等，重发。,小结：1.为检测 e 个错误，最小码距应满足2.为纠正 t 个错误，最小码距应满足3.为纠正 t 个错误，同时又能够检测 e 个错误（et），最小码距应满足,作业：题12.1已知8个码组为：（O00000），（001110），（010101），（011011），（100011）， （1O1101），（110110），（111000），（

7、1）求以上码组的最小码距 d0；（2）若此8个码组用于检错，可检出几位错？（3）若用于纠错码，能纠几位？（4）若同时用于纠错和检错，e 能不能大于 t ？,12.3 常用的简单编码,一、奇偶校验码奇偶校验码分为奇数检验码和偶数校验码。无论信息位有多少，监督位只有1位。 偶数校验码：它使码组中“1”的数目为偶数。“ ”表示模2加。,信息位,监督位,，模2加 运算： 多个二进制数（“0”或“1”）连续进行模2加 运算，如果有偶数个“1”则结果为“0”；如果有奇数个“1”则结果为“1”。奇偶校验码只能发现奇数个错误，不能发现偶数个错误，不能纠错。,二、二维奇偶校验码以二维偶校验码为例，101 110

8、 001,可以检测在某一行出现偶数个错误；,可以纠正1位错误。,三、恒比码每个码组均含有相同数目的“1”和“0”。下表是 5中取3恒比码。在接收端检测时，只需计算接收码组中“1”的数目是否正确，就可以知道有无错误。不属于分组码。,附加知识点,线性分组码：监督位与信息位呈线性关系，即任何一位监督位可以由若干信息位进行线性代数运算得到。包括：奇偶校验码，重复码，汉明码， 循环码，戈雷码等,12.4 汉明码,一、定义： 一种能够纠正1位错码并且效率较高的线性分组码。 最小码距d0=3。 下面以（7,4）汉明码为例讲解,二、监督方程的概念,个数为 监督位的数目，r =3,线性不相关，即不能由两个方程推

9、导出另外一个方程,信息码,信道编码器,系统码,（7,4）汉明码编码表,三、校正子 S 先把监督方程整理成“=”的右边全为“0”，再把“0”分别用 代替。,（1）在发送端， 全为“0” （2）在接收端， 不一定全为“0”在接收端， 若 全为“0”，认为正确接收； 若 不全为“0”，则肯定有误码。观察 除全为“0”外，还有情况，可以指示 种仅错1位情况。 所以，纠正1位错码，要求 ，为了使编码效率最大，选取 。,接收端：在无错和仅错一位的情况下，校正子与错码位置的关系,在仅错一位的情况下，如何找到错码位置？第一步：根据监督方程计算校正子第二步： 方法一：根据校正子的值查验监督方程的对应码位 例题：

10、判断码字是否正确，如有错误，指出错码位置,在仅错一位的情况下，如何找到错码位置？第一步：根据监督方程计算校正子第二步： 方法二：根据 S1 S2 S3T与监督方程对应列的关系例题：判断码字是否正确，如有错误，指出错码位置,试求：判断码字 是否正确，如有错误，指出错码位置。解：,四、监督矩阵H ( r行 x n列 )在发送端，有,典型监督矩阵,发送端,接收端,发送端,接收端,在仅错一位的情况下，如何找到错码位置？解题步骤：第一步：根据监督方程计算校正子S第二步：根据校正子的值查H矩阵，对应列即为错码位置例题：判断码字是否正确，如有错误，指出错码位置,第一步：计算校正子,五、生成矩阵G ( k行

11、x n列 )若存在一个矩阵G，使得信息矩阵xG=系统码矩阵则称矩阵G为生成矩阵。例如：,典型生成矩阵,行与行之间线性无关,观察典型监督矩阵H和典型生成矩阵G,六、生成矩阵G 的每一行都是许用码组,六、典型生成矩阵G 的每一行都是许用码组,七、错误图样E ( 1行 x n列 )发送码组：接收码组：错误图样E：,八、线性分组码的性质（1）全零码组必定是线性分组码中的一个码字,（2）封闭性 一种线性分组码中任意两个许用码组之和（模2加）仍为这种码中的一个许用码组。 设 和 是一种线性码中的两个许用码组，则 仍为其中的一个许用码组。,（3）码的最小距离即是码的最小重量。 因为线性码具有封闭性，因而两个

12、码组之间的距离必是另一个码组的重量（除全0码组外）。 其中：汉明码的最小距离为3。,（4）生成矩阵G每行都是许用码组。,已知，典型生成矩阵G 的每一行都是许用码组；,又因为，线性分组码的封闭性，即任意两个许用码组之和（模2加）仍为这种码中的一个许用码组；,由典型生成矩阵经过初等变换可以获得非典型生成矩阵,所以，无论是典型生成矩阵还是非典型生成矩阵，生成矩阵的每一行都是许用码组；,非典型生成矩阵,（5）生成矩阵G中，行与行之间线性无关。（6）在线性分组码（n, k）中，任意找到k个线性无关的许用码组，就可以构造生成矩阵。 （如果所构造的生成矩阵是非典型生成矩阵，则可以通过初等变换得到典型生成矩阵

13、。）,例题1：（重点考试题型）,已知（7,4）汉明码监督方程如下：求：(1)监督矩阵和生成矩阵。 (2)分别求出信息“1010”时的系统码。 (3) 若收到“1100101”，试判断是否有错码？如果有1位错码，指出哪位错？ (4)求错误图样。,非典型监督矩阵,解：（1）,将非典型监督矩阵转换为典型监督矩阵,利用线性代数的初等变换， ,(2)求信息“1 0 1 0”的系统码方法1：由监督方程计算监督位 可得信息“1010”的系统码为“1010011”,方法2：信息与典型生成矩阵G计算得到系统码,方法3：典型生成矩阵G的某些行进行模2加运算（适合信息位中“1”的个数不多的场合）“1010”,(3)

14、若收到“1 1 0 0 1 0 1”，试判断是否有错码？如果有1位错码，指出哪位错？解：第一步：根据监督方程计算校正子S,(4)求错误图样。解：已知 错，可得错误图样为 0100000作业：12.5,例题2：已知（7,4）汉明码的生成矩阵为：,求：(1)监督矩阵和监督方程。 (2)当输入序列为 “110101101010” 时，求编码器的输出序列。 (3)若收到“0010101”，试判断是否有错码？如果有1位错码，指出哪位错？ (4)求错误图样。,解：因为,是典型生成矩阵,(1)求监督矩阵和监督方程。,由监督矩阵可得监督方程,即，监督方程为,(2)当输入序列为 “1 1 0 1 0 1 1 0

15、 1 0 1 0” 时，求编码器的输出序列。,方法1：由监督方程计算监督位,方法2：信息与典型生成矩阵G计算得到系统码,方法3：典型生成矩阵G的某些行进行模2加运算,(3)若收到“ ”，试判断是否有错码？如果有1位错码，指出哪位错？,解：第一步：由监督方程可得在接收端计算校正子的公式,解：已知 错，可得错误图样为 0001000,(4)求错误图样。,12.5 循环码,一、定义 循环码中任意一个许用码组经过循环移位之后，所得的码组仍为一个许用码组。 下表给出了（7,3） 循环码的全部码组。,二、码多项式及模运算 1. 码多项式把码组中的各码元当作一个多项式的系数上式称为码多项式，x只是作为码元位

16、置的标记。例如： 0 1 0 0 1 1 1 ,2. 码多项式运算（1）“”，“” 就是码多项式的系数按“模2加”运算。 例如：,（2）“”，“” 过程中的 “”和“”是“模2加，” 例如：,例如：,（3）模运算 一个码多项式A(x)被B(x)除，得到的余式C(x)，称C(x)为A(x)进行模B(x)的运算结果。 记为： A(x) C(x) （模B(x)） 例如：,3. 若多项式T(x)是一个码长为n的许用码组，则 在模 运算下也是一个许用码组例：（1）在表中取出第5号码组 1 0 0 1 1 1 0 对应的码多项式为 （2）把它乘以 ，设m=3，即 （3）进行模（ ）运算，n为系统码的长度，

17、本例为n=7，即,三、码的生成多项式和生成矩阵 1. 码的生成多项式 定义：前（k-1）位皆为“0”而前面第k位为“1”的码组所对应的码多项式，并记为g(x)。 在（7,3） 循环码中的第二号码组0011101所对应的码多项式即为码的生成多项式，并记为g(x)。 g(x)必须是一个且仅有一个、同时常数项不为“0”的（n-k）次多项式，即r次多项式。,2. 生成矩阵 G,对于（n, k）线性分组码，有了生成矩阵G，就可以由k个信息码元得到相应的系统码。,已知，生成矩阵G的每一行都是一个许用码组，因此若能找到k个线性无关的许用码组，就能构成生成矩阵。,非典型生成矩阵,k行线性无关,生成矩阵,生成矩

18、阵G也可以写为,利用初等变换，将非典型生成矩阵G变换为典型生成矩阵G,利用初等变换,典型生成矩阵,由生成矩阵获得信息码110的循环码,利用非典型生成矩阵G,利用典型生成矩阵G,不是系统码,是系统码,3. 监督矩阵 H,由典型生成矩阵,可得典型监督矩阵,4. 监督方程和校正子,由监督矩阵,可得监督方程,在接收端，校正子S,四、循环码的编码器,例题1：（重点考试题型）,已知（7,4）循环码生成多项式：求：(1)监督矩阵和生成矩阵。 (2)若信息为“1100”，求系统码。 (3) 若接收端收到“1011101”，试判断有没有误码？如果有误码，指出是哪一位错了？（假设传输时最多只有一个误码） (4)画

19、出构成该循环码的编码器电路。,解：（1）,重写,重写,重写,解：（2）若信息为“1 1 0 0”，求系统码,方法一： 由监督矩阵,写出监督方程,计算监督位,方法二：信息与典型生成矩阵G计算得到系统码,若信息为“1 1 0 0”，求系统码,方法三： 通过典型生成矩阵G的某些行进行模2加运算,若信息为“1 1 0 0”，求系统码,(3) 若接收端收到“1 0 1 1 1 0 1”，试判断有没有误码？如果有误码，指出是哪一位错了？,由监督方程写出在接收端校正子的计算公式,计算校正子,对照典型监督矩阵H的列，,解：,(4)画出构成该循环码的编码器电路。,例题2：,已知（7,3）循环码的一个码字为 10

20、01011求：(1)写出生成多项式g(x). (2)写出生成矩阵和监督矩阵。 (3)若信息为“110”，求系统码。 (4) 若接收端收到“1010111”，试判断有没有误码？如果有误码，指出是哪一位错了？（假设传输时最多只有一个误码） (5)画出构成该循环码的编码器电路。,解：（1）已知（7,3）循环码的一个码字为 1001011,由生成多项式g(x)的定义，即前（k-1）位皆为“0”而前面第k位为“1”的码组所对应的码多项式,通过左循环移位，可得,解：（2）写出生成矩阵和监督矩阵。,重写,解：（3）若信息为“1 1 0”，求系统码,方法一：,写出监督方程,计算监督位,由典型监督矩阵,方法二：

21、信息与典型生成矩阵G计算得到系统码,若信息为“1 1 0 ”，求系统码,方法三： 通过典型生成矩阵G的某些行进行模2加运算,若信息为“1 1 0”，求系统码,方法四：,若信息为“1 1 0”，求系统码,由题干中所给的循环码组，可以得到,由生成多项式g(x)所对应的循环码组，可以得到,(4) 若接收端收到“ 1 0 1 0 1 1 1”，试判断有没有误码？如果有误码，指出是哪一位错了？,由监督方程写出在接收端校正子的计算公式,计算校正子,对照典型监督矩阵H的列，,解：,(5)画出构成该循环码的编码器电路。,作业：（重点考试题型）,已知（7,3）循环码生成多项式：求：(1)监督矩阵和生成矩阵。 (2)若信息为“101”，求系统码。 (3) 若接收端收到“1011101”，试判断有没有误码？如果有误码，指出是哪一位错了？（假设传输时最多只有一个误码） (4)画出构成该循环码的编码器电路。,