1、第 3 章 差错控制&3.1 3.1 差错控制的基本概念及原理差错控制的基本概念及原理q3.1.1 3.1.1 差错控制的基本概念差错控制的基本概念q3.1.2 3.1.2 差错控制的基本原理差错控制的基本原理&3.2 3.2 简单的差错控制编码简单的差错控制编码 q3.2.1 3.2.1 奇偶监督码奇偶监督码 q3.2.2 3.2.2 水平奇偶监督码水平奇偶监督码q3.2.3 3.2.3 二维奇偶监督码二维奇偶监督码&3.3 3.3 汉明码及线性分组码汉明码及线性分组码q3.3.1 3.3.1 汉明码汉明码q3.3.2 3.3.2 线性分组码线性分组码第 3 章 差错控制&3.4 3.4 循
2、环码循环码q3.4.1 3.4.1 循环码的循环特性循环码的循环特性q3.4.2 3.4.2 循环码的生成多项式和生成矩阵循环码的生成多项式和生成矩阵q3.4.3 3.4.3 循环码的解码方法循环码的解码方法q3.4.4 3.4.4 循环码的解码方法循环码的解码方法&3.5 3.5 卷积码卷积码q3.5.1 3.5.1 卷积码的基本概念卷积码的基本概念q3.5.2 3.5.2 卷积码的图解表示卷积码的图解表示q3.5.3 3.5.3 卷积码的概率解码卷积码的概率解码3.1 差错控制的基本概念及原理 数据信号在传输过程中不可避免地会发生差错，即数据信号在传输过程中不可避免地会发生差错，即出现出现
3、误码误码。造成误码的主要原因可以归结为两个方面：。造成误码的主要原因可以归结为两个方面：r信道不理想造成的符号间干扰 由于信道不理想使得接收波形发生畸变，在接收由于信道不理想使得接收波形发生畸变，在接收端抽样判决时会造成码间干扰，若此干扰严重时则导端抽样判决时会造成码间干扰，若此干扰严重时则导致误码。这种原因造成的误码可以通过致误码。这种原因造成的误码可以通过均衡方法均衡方法予以予以改善以至消除。改善以至消除。r噪声对信号的干扰 信道等噪声叠加在接收波形上，对接收端信号的信道等噪声叠加在接收波形上，对接收端信号的判决造成影响，如果噪声干扰严重时也会导致误码。判决造成影响，如果噪声干扰严重时也会
4、导致误码。消除噪声干扰产生误码的方法就是进行消除噪声干扰产生误码的方法就是进行差错控制差错控制。3.1.1 差错控制的基本概念1.差错分类 数据信号在信道中传输会受到噪声干扰，噪声大体数据信号在信道中传输会受到噪声干扰，噪声大体分为两类：分为两类：随机噪声和脉冲噪声随机噪声和脉冲噪声。l随机差错随机差错又称独立差错，指那些独立地、稀疏地和互不相关地又称独立差错，指那些独立地、稀疏地和互不相关地发生的差错。存在这种差错的信道称为无记忆信道或随机信道。发生的差错。存在这种差错的信道称为无记忆信道或随机信道。l突发差错突发差错是指一串串，甚至是成片出现的差错，差错之间有相是指一串串，甚至是成片出现的
5、差错，差错之间有相关性，差错出现是密集的。产生突发错误的信道称为有记忆信道关性，差错出现是密集的。产生突发错误的信道称为有记忆信道或突发信道。或突发信道。实际信道是复杂的，所出现的错误也不是单一的，而是随实际信道是复杂的，所出现的错误也不是单一的，而是随机和突发错误并存的，这两类错误形式并存的信道称为机和突发错误并存的，这两类错误形式并存的信道称为组合组合信道或复合信道信道或复合信道。2.差错控制的基本思路 差错控制的核心是抗干扰编码，或差错控制编码，简称纠错编码，也叫信道编码q发送端发送端：将被传送的信息码（无规律）按照一定的：将被传送的信息码（无规律）按照一定的规则加入监督码元后进行传输，
6、加入的监督码元与规则加入监督码元后进行传输，加入的监督码元与信息码元存在某种确定的约束关系。信息码元存在某种确定的约束关系。q接收端接收端：检验信息码元与监督码元之间的既定的约：检验信息码元与监督码元之间的既定的约束关系，如关系被破坏，则传输中有错。束关系，如关系被破坏，则传输中有错。信息码(k)+监督码(r)=码组(n)3.差错控制方式差错控制方式（1）检错重发（ARQ）优缺点所需的监督码位数少，编码效率比较高；译码设备较简单；接收端检测到差错后，要通过反向信道发回NAK，要求发端重发，所以需要反向信道，实时性差ARQARQ有有3 3种种重重发发方式，即方式，即停停发发等候重等候重发发，返回
7、重，返回重发发和和选择选择重重发发。差错控制方式（2）前向纠错（FEC）优缺点 不需要反向信道，自动纠错，不要求重发，因而实时性好；缺点是所选择的纠错码必须与信道的错码特性密切配合，否则 很难达到降低错码率的要求；要纠正较多的错码，译码设备复杂，且要求附加的监督码较多，编码效率低。差错控制方式（3）混合纠错检错（HEC）是ARQ和FEC方式的折衷方案 优缺点 集合了ARQ和FEC的优点，在保证系统较高的有效性的同时,大幅度提高了整个系统的可靠性，但需要反向信道。差错控制方式（4）信息反馈（IRQ）数据信息 数据信息 （d）信息反馈 优缺点 优点是不需要纠错、检错，设备简单；缺点是需要和前向信道
8、相同的反向信道，实时性差，且发送端需要一定容量的存储器。3.1.2 差错控制的基本原理1.差错控制的原理3.1.2 差错控制的基本原理1.差错控制的原理（续）要想具有检错和纠错能力，必须有禁用码组。禁用码组的获得方法：加监督位。结论 若要传送若要传送A A和和B B两个消息：若用两个消息：若用1 1位码表示，则没有检位码表示，则没有检错和纠错能力；若用错和纠错能力；若用2 2位码表示（加位码表示（加1 1位监督码），可以位监督码），可以检错检错1 1位；若用位；若用3 3位码表示（加位码表示（加2 2位监督码），最多可以检位监督码），最多可以检出出2 2位或纠错码位或纠错码1 1位。位。在纠错
9、编码中将信息传输效率也称为编码效率，定在纠错编码中将信息传输效率也称为编码效率，定义为义为 显然，显然，R R越大编码效率越高，它是衡量码性能的一个越大编码效率越高，它是衡量码性能的一个重要参数。对于一个好的编码方案，不但希望它检错纠重要参数。对于一个好的编码方案，不但希望它检错纠错能力强，而且还希望它的编码效率高，但两方面的要错能力强，而且还希望它的编码效率高，但两方面的要求是矛盾的，在设计中要全面考虑。求是矛盾的，在设计中要全面考虑。差错控制的基本原理nkR 2.汉明距离与检错和纠错能力的关系码长：码组或码字中编码的总位数为码组的长度。（1）几个概念码重：码组中非零码元的数目为码组的重量。
10、例如“11010”的码长为5，码重为3。码距：两个等长码组中对应码位上具有不同二进制码的数目 称为码距。例如：码组1 11010 码组2 01101(000)(001)(101)(100)(110)(010)(011)(111)a2a0a1在一种编码中，任意两个许用码组间距离的最小值。汉明距离（最小码距）：（2）汉明距离和检错和纠错能力的关系a)a)为为了了检测检测e e位位错码错码，要求最小，要求最小码码距距 min1de b)b)为为了了纠纠正正t t位位错码错码，要求最小，要求最小码码距距 min21dt c)c)为为了了纠纠正正t t位位错码错码，同，同时检测时检测e(et)e(et)
11、位位错码错码，要求最小，要求最小码码距距 min1det 3.纠错编码的分类(1)按码组的功能分，有检错码和纠错码两类。(2)按码组中监督码元与信息码元之间的关系分，有线性码和 非线性码两类。(3)按照信息码元与监督码元的约束关系，可分为分组码和 卷积码。(4)按照信息码元在编码前后是否保持原来的形式不变，可分为系统码和非系统码。(5)按纠正差错的类型可分为纠正随机错误的码和纠正突发 错误的码。(6)按照每个码元取值来分，可分为二进制码与多进制码。3.2 简单的差错控制编码1.奇偶监督码特点：只有一个监督位。偶监督：码组中“1”的个数为偶数。1210,nnaaa a 12100nnaaaa 信
12、息位监督位奇监督：码组中“1”的个数为奇数。12101nnaaaa 只能检出奇数位错码。2.水平奇偶监督码 思想方法：将信息码序列按行排成方阵，每行后面加一个奇或偶监督码，即每行为一个奇（偶）监督码组，但发送时则按列的顺序传输：11101110011000010101，接收端仍将码元排成与发送端一样的方阵形式，然后按行进行奇偶校验。信信 息息 码码 元元 监督码元监督码元 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1水平偶
13、监督码可以检出奇数位错误和长度不大于方阵中行数的突发错误。3.二维奇偶监督码（水平垂直奇偶监督码）思想方法：在水平监督基础上对方阵中的每一列再进行奇偶校验。发送时按行或按列的顺序传输，接收端重新将码元排成与发送时的方阵形式，然后每行、每列都进行奇偶校验。二维偶监督码 信信 息息 码码 元元 监督码元监督码元 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1监督码元监督码元 0 1 1 0 1 1 0 0 0 1 1可以纠1位错
14、码；可以检出某行或某列上的奇数位错码和长度不大于方阵中行数(列数)的突发错码；可以检出一部分偶数位错码；不能检出错码恰好分布在矩阵4个顶点上的偶数位错码。3.3 汉明码及线性分组码汉明码特点 可以纠正一位错码，且d0=33.3.1 汉明码 1.码长和监督位的关系：1021nnaSaaa 若使用偶监督：只有一位监督位 0a接收端译码时，实际上就是计算：0S 1S 若 无错；有错。1位监督位，有1个校正子。只能表示有错和无错，不能指示错码位置。21rn 7,44,3,kr如汉明码，只能纠一位错码 码长和监督位的关系2位监督位，就有2个监督关系式，也有2个校正子。12S S1200 01 10 11
15、S S ，无错 指示错码位置（n,k）汉明码，监督位 r=n-k，可构造出r个监督关系式 来指示一位错码的n种可能位置，要求 346035614562aaaaaaaaaaaa1.1.（7 7,4 4）汉汉明明码码a6 a5 a4 a3：信息码元；a2 a1 a0：监督码元信息码元与监督码元的关系：1）（）（7,4）汉明码汉明码16542Saaaa s1 s2 s3 错码位置错码位置 0 0 0 无错 0 0 1 a0 0 1 0 a1 1 0 0 a2 0 1 1 a3 1 0 1 a4 1 1 0 a5 1 1 1 a6 校正子与错码位置的关系26531Saaaa 36430Saaaa 3r
16、 有3个校正子123,SSS例例3-13-1：接收端收到某（7,4）汉明码为1001010，问：此（7,4）汉明码是否有错？错码位置如何？计算校正子1654210001Saaaa 2653110111Saaaa 3643010100Saaaa 得校正子 为110，123S S S码组有错。5a正确码组：1101010 346035614562aaaaaaaaaaaa654265316430000aaaaaaaaaaaa 2）（7,4）汉明码的产生由监督关系式：移项，解出监督位：解决问题：由信息位计算监督位解决问题：由信息位计算监督位（7,4）汉明码的许用码组假设发送端的码字是A15=11111
17、11，传输过程中第4位a3出现了错误，即接收的码字是B=1110111 不是许用码组。信息码a6 a5 a4 a3码组Aa6 a5 a4 a3 a2 a1 a0信息码a6 a5 a4 a3码组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 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
18、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例例3-23-2：已知信息码为1101，求所对应的（7,4）汉明码。计算监督位26541100aaaa 16531111aaaa 06431010aaaa 汉明码码组：11010103）编码效率编码效率（7,4）汉明码的编码效率：457%7kRn 3.3.2 线性分组码线性码：监督码元与信息码元之间满足一组线性方程。分组码：
19、监督码元仅对本码组中的码元起监督作用。1.监督矩阵以（7,4）汉明码为例654265316430000aaaaaaaaaaaa 654321065432106543210111010001101010010110010aaaaaaaaaaaaaaaaaaaaa 简写为+线性分组码：既是线性码又是分组码。65432101110100011010100210110010aaaaaaa 模111010011010101011001H写成矩阵形式00TTTHAAH 简写为r=P I265416530643aaaaaaaaaaaa 6251403111011011011aaaaaaa 210654311
20、1110101011a a aa a a a 6543a a a aQ TQP 其中：监督位 信息位 监督位与信息位的关系（矩阵表示）2.生成矩阵用途：由信息位和生成矩阵可得出整个码组。生成矩阵：kGI Q 以（7,4）汉明码为例 120nnAaaaG 信信息息位位典典型型的的111110101011Q kGI Q 1000111010011000101010001011 如（7,4）汉明码表中的第3个码组信息码a6 a5 a4 a3码组Aa6 a5 a4 a3 a2 a1 a0信息码a6 a5 a4 a3码组Aa6 a5 a4 a3 a2 a1 a00 0 0 00 0 0 10 0 1 0
21、0 0 1 10 1 0 00 1 0 10 1 1 00 1 1 10 0 0 0 0 0 00 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 16
22、6432106643Aa a a a a a aa a a aG 求整个码组 10001110100110001000101010001011 0010101 注意：生成矩阵G各行本身就是一个码组。加例题！二元域上只有两种运算：加和乘。运算规则如下：加乘0000 111 011 10 0 000 101 001 11 3.监督矩阵和生成矩阵的关系 ,TrkH=PIQPGI Q 例例3-33-3：某（7,4）线性分组码，监督方程如下，求监督矩阵H和典型的生成矩阵G。如信息码为0010，求整个码组。265316430543aaaaaaaaaaaa 6543210654321065432101101
23、10001011010001110010aaaaaaaaaaaaaaaaaaaaa 监督方程改写为得监督矩阵：110110010110100111001rHP I 110101011111TQP 典型生成矩阵：1000110010010100100110001111 kGI Q 如信息码为0010，则整个码组为 0010AG 10001100100101001000100110001111 0010011 4.线性分组码的主要性质 (1)(1)封封闭闭性性 是指一是指一种线种线性分性分组码组码中的任意中的任意两个码组两个码组之逐位模之逐位模2 2和仍和仍为这种为这种 码码中的另一中的另一个许个
24、许用用码组码组。(2)(2)码码的最小距离等于非零的最小距离等于非零码码的最小重量。的最小重量。3.4 循环码循环码是一种线性分组码。3.4.1 循环码的循环特性表表3-13-1（7,37,3）循）循环码环码的一的一种码组种码组 码组编号码组编号信息位信息位监督位监督位码组编号码组编号信息位信息位监督位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010 循环码的循环特性是指在循环码中任一许用码组经过循环移位后所得到的码组仍为它的一个许用码组。第2码组右移1
25、位得到第5码组；第5码组右移1位得到第7码组。12101210()nnnnA xaxaxa xa x1210(,)nnAaaa a2.码多项式的表示及运算规则 6431A xxxxx 1011011A 例如，码组为 则码多项式为：码多项式的运算：加、减、乘、除运算1 1）码码多多项项式的加法式的加法运运算：同算：同幂幂次相加，系次相加，系数进数进行行异异或或运运算算kkkkkkkkkkkcbabaxcxbxa 2 2）码码多多项项式的式的减减法法运运算：同加法算：同加法运运算算kkkkxaxa-码组为码组为则码则码多多项项式式为为：A B C0000111011103 3）异异或或运运算（算（
26、逻辑逻辑加和加和逻辑减逻辑减）的）的真值真值表表CBABABA4 4）码码多多项项式的乘法式的乘法运运算：服算：服从从一般的代一般的代数规数规律律123xxx)1()1(2xxx)1)(1(2xx5 5）码码多多项项式的除法式的除法运运算：服算：服从从一般的代一般的代数规数规律律11112223xxxxxx6 6）码码多多项项式的除法式的除法运运算算简简化表示化表示)1(1223xxxx模余式（模除式）被除式 例如例如上式上式还还可表示可表示为为3.4.2 循环码的生成多项式和生成矩阵 1.生成多项式 g(x)生成多项式的寻找方法：（n,k）循环码的 个码组中，有一个码组前k-1位码元均为0，
27、第k位码元为1，最后一位为1，此码组对应的多项式为生成多项式。2k 对于线性分组码，有了典型的生成矩阵G，就可以由k个信息码得出整个码组。如果知道监督方程，便可得到监督矩阵H，而由监督矩阵和生成矩阵G之间的关系则可以求出生成矩阵G。这里介绍求生成矩阵G的另一种方法，即根据循环码的基本性质来找出它的生成矩阵。由于G的各行本身就是一个码组，如果能找到k个线性无关的码组，就能构成生成矩阵G。其最高幂次为即为生成多项式，此码组对应的多项式位（最后一位）码元为，第为位码元，第位码元均为前个码组中，有一个码组循环码的称为生成多项式。，组便可构成生成矩阵个许用码个许用码组。这对应的码组共构成的一个许用码组，
28、连同循环码所对应的码组都是根据循环码的特性knkkknknknknxxgnkkknxgGkkxgknxgxxgxxxgxgxgxxgkggg ),(11012),()()(),()(),(),(,100)(1)101000(12111121例例3-4:3-4:求表3-1所示的（7,3）循环码的生成多项式。码组编号码组编号信息位信息位监督位监督位码组编号码组编号信息位信息位监督位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010 421g xxxx 2.生成
29、矩阵G 12kkxg xxg xG xxg xg x 典型的生成矩阵kGI Q 通过线性变换可将非典型的生成矩阵转换为典型的生成矩阵单位方阵例例3-53-5：求例3-4所示的（7,3）循环码的典型生成矩阵G。421g xxxx 生成矩阵多项式 2x g xG xxg xg x 6432532421xxxxxxxxxxx 生成矩阵101110001011100010111G 100101101011100010111 311 行行行行取取代代第第 行行 3.生成多项式的另一种求法 （n,k）循环码的生成多项式是 的一个（n-k）次因式。1nx 例例3-63-6：求（7,3）循环码的生成多项式。7
30、3231111xxxxxx 生成多项式有两个：3242111g xxxxxxx 3432111g xxxxxxx 生成多项式不同，产生出的循环码码组也不同。3.4.3 循环码的编码方法 1211210nnn kn kkkm xmxmxm xm x 信息位对应的码多项式：循环码的码多项式 1n kxm x 求求 2n kxm xr xq xg xg x 3n kA xxm xr x 下一页上一页循环码的编码当M=110，所以 即所得的码字为A=1100101。xxxM2)(5624)()(xxxxxxMxkn)(111)()(222456xgxxxxxxxxxgxMxkn1)(2xxr1)()(
31、)(256xxxxrxMxxAkn3.4.4 循环码的解码方法1.检错的实现无差错 A x，发送码组 R x，接收码组 若码组无错 A xR x，R xrxQxg xg x A xR x 若码组有错，则 接收码组 若码组无错 0rx 0rx 检测到差错解码器的核心：除法器121132121CRCxxxxx 国际通信中常用的是循环冗余校验（CRC）生成多项式为：16152161CRCxxx 161251CRCITUxxx 1245781011121622232632xxxxxxxxxxxxxxCRC-32CRC IS-95 CDMA126781112131520212930 xxxxxxxxxx
32、xxx 3.5.1 卷积码的基本概念卷积码又称连环码，是非分组码。没有严格的代数结构 卷积码的监督位不仅取决于这段时间的k个信息位，还取决于前N-1段规定时间内的信息位。1.卷积码的概念编码效率：即卷即卷积码积码的的监监督位不督位不仅对仅对本本码组码组起起监监督作用，督作用，对对前前N-1N-1个码个码组组也起也起监监督作用。督作用。这这N N段段时间内时间内的的码码元元数数目目nNnN称为约称为约束束长长度。度。卷积码的表示方式：(n,k,N)(n,k,N)kRn 卷积编码器(n，k，N)卷积编码器结构 编码输出每次输入k比特1k1k1k1k 1 k2k3kNk 12nNk级移存器n个模2加
33、法器每输入k比特旋转1周卷积码的编码(3，1，3)卷积码等效编码器 实例分析 3级编码器 n=3,k=1:每输入一个信息比特，产生3个输出比特；S1、S2、S3：移存器321331211ssscsscsc3.5.2 卷积码的图解表示 根据卷积码的特点，它还可以用树状根据卷积码的特点，它还可以用树状图、网格图和状态图来表示，它与卷积图、网格图和状态图来表示，它与卷积码的编码过程和解码方法有密切关系。码的编码过程和解码方法有密切关系。1.树状图 输出移位寄存器用转换开关代替，输出移位寄存器用转换开关代替，转换开关每输入一个比特转换一次，这转换开关每输入一个比特转换一次，这样，每输入一个比特，经编码
34、器产生两样，每输入一个比特，经编码器产生两个比特。图中个比特。图中m1,m2,m3m1,m2,m3为移位寄存器，为移位寄存器，假设移位寄存器的起始状态全为假设移位寄存器的起始状态全为0 0，即，即m1m1,m2,m3,m2,m3为为000000。c1c1与与c2c2表示为表示为 c1=m1+m2+m3 c1=m1+m2+m3 c2=m1+m3 c2=m1+m3 m1m1表示当前的输入比特，而移位寄存表示当前的输入比特，而移位寄存器存储以前的信息，表示编码器状态。器存储以前的信息，表示编码器状态。m m1 11 11 10 01 10 00 00 00 0m3m20001111001100000
35、c1c21101010010110000状态abdcbcaa（2,1,32,1,3）卷积码编码器的状态变化过程）卷积码编码器的状态变化过程编码器中移位过程可能产生的各种序列用树状图表示 2.网格图3.状态图 从树状图的第三级各节点状态从树状图的第三级各节点状态a,b,ca,b,c和和d d与第四级各节点与第四级各节点a,b,ca,b,c和和d d之间的关系，或者取出已达到稳定状态的一节网格之间的关系，或者取出已达到稳定状态的一节网格(网格图中第三级网格图中第三级到第四级节点间的一节网格到第四级节点间的一节网格)，我们就可将当前状态与下一个状态之，我们就可将当前状态与下一个状态之间的关系用状态图来表示。间的关系用状态图来表示。
