1、信道编码和差错控制信道编码和差错控制纠错编码纠错编码线性分组码线性分组码循环码循环码22022-2-28基本要求基本要求了解信道编码的目的和要求了解信道编码的目的和要求掌握纠错编码的基本原理和纠错编码系统的性掌握纠错编码的基本原理和纠错编码系统的性能分析能分析熟悉常用的简单编码熟悉常用的简单编码掌握线性分组码、循环码的编码和解码方法掌握线性分组码、循环码的编码和解码方法32022-2-28基本内容基本内容信道编码信道编码概念概念，指数字信号为了适应信道的传指数字信号为了适应信道的传输特性，达到高效可靠的传输而进行的相应的输特性，达到高效可靠的传输而进行的相应的信号处理过程。信号处理过程。信道编
2、码的信道编码的目的目的：降低误码率，降低误码率，提高信号传输提高信号传输的可靠性。的可靠性。信道编码的信道编码的基本原理基本原理是在信号码元序列中增加是在信号码元序列中增加监督码元，并利用监督码元去发现或纠正传输监督码元，并利用监督码元去发现或纠正传输中发生的错误。中发生的错误。42022-2-28基本内容基本内容在信道编码只有发现错码能力而无纠正错在信道编码只有发现错码能力而无纠正错码能力时，必须结合其他措施来纠正错码，码能力时，必须结合其他措施来纠正错码，否则只能将发现为错码的码元删除。这些否则只能将发现为错码的码元删除。这些手段统称为手段统称为差错控制差错控制。差错控制编码是一种信道编码
3、。差错控制编码是一种信道编码。52022-2-28基本内容基本内容 信道的分类信道的分类v 随机信道随机信道v 突发信道突发信道v 混合信道混合信道62022-2-28基本内容基本内容常用的差错控制方式主要有常用的差错控制方式主要有v检错重发（简称检错重发（简称ARQ）v前向纠错（简称前向纠错（简称FECFEC）v混合纠错（简称混合纠错（简称HECHEC）目的：目的：克服线路传输中出现的数据差错，实现克服线路传输中出现的数据差错，实现 调制解调器至终端调制解调器的无差错数调制解调器至终端调制解调器的无差错数 据传送。据传送。72022-2-28基本内容基本内容差错控制编码方法差错控制编码方法/
4、 /纠错编码方法：纠错编码方法： 为了在接收端能够发现或纠正错码，为了在接收端能够发现或纠正错码，在发送码元序列中加入一些差错控制码在发送码元序列中加入一些差错控制码元（监督码元元（监督码元/监督位）。监督位）。 加入的监督码元越多，纠加入的监督码元越多，纠/检错的能检错的能力越强，传输效率越低，从而可以用降力越强，传输效率越低，从而可以用降低传输效率换取传输可靠性的提高。低传输效率换取传输可靠性的提高。82022-2-28基本内容基本内容差错控制编码分类：差错控制编码分类： 按照差错控制编码的不同功能分为按照差错控制编码的不同功能分为检错码、纠错码和纠删码；检错码、纠错码和纠删码； 按照信息
5、码元和附加的监督码元之间的检验关系分为按照信息码元和附加的监督码元之间的检验关系分为线性码和非线性码；线性码和非线性码； 按照信息码元和监督码元之间的约束方式不同分为按照信息码元和监督码元之间的约束方式不同分为分组码和卷积码；分组码和卷积码；92022-2-28基本内容基本内容差错控制编码分类：差错控制编码分类： 按照信息码元在编码后是否保持原来的形式不变分为按照信息码元在编码后是否保持原来的形式不变分为系统码和非系统码；系统码和非系统码； 按照纠正错误的类型不同分为按照纠正错误的类型不同分为纠正随机错误的码和纠正突发错误的码；纠正随机错误的码和纠正突发错误的码； 按照构造差错控制编码的数学方
6、法分为按照构造差错控制编码的数学方法分为代数码、几何码和算术码；代数码、几何码和算术码；按照每个码元取值不同分为按照每个码元取值不同分为 二进制和多进制码。二进制和多进制码。102022-2-28基本内容基本内容码率：码率：编码序列中信息码元数量编码序列中信息码元数量k k和总码元数量和总码元数量n n之比：之比：k/nk/n冗余度：冗余度： 监督码元数（监督码元数（n-kn-k）和）和总总码元数量码元数量n n之比之比: : ( (n-k)/nn-k)/n112022-2-28纠错编码纠错编码纠错编码中的基本概念纠错编码中的基本概念v纠错编码：具有检错能力或纠错能力的编码。纠错编码：具有检错
7、能力或纠错能力的编码。 v纠错编码分为纠错编码分为分组码分组码和和卷积码卷积码两大类。两大类。v分组码分组码：将若干监督码元附加在一组信息位上：将若干监督码元附加在一组信息位上构成一个具有纠错能力的独立码组，并且监督构成一个具有纠错能力的独立码组，并且监督位仅监督本组中的信息码元。位仅监督本组中的信息码元。v分组码用符号（分组码用符号（n,k）表示，其中）表示，其中n是码组长度，是码组长度，k为信息码元数目，为信息码元数目，r=n-k为监督码元数目。为监督码元数目。122022-2-28纠错编码纠错编码纠错编码中的基本概念纠错编码中的基本概念v由代数关系确定监督位的分组码称为由代数关系确定监督
8、位的分组码称为代数码代数码。v在代数码中，若监督位和信息位的关系是由在代数码中，若监督位和信息位的关系是由线性方程式决定的，则称这种编码为线性方程式决定的，则称这种编码为线性分线性分组码组码。例如：奇偶监督码、汉明码、循环码。例如：奇偶监督码、汉明码、循环码。132022-2-28纠错编码纠错编码纠错编码中的基本概念纠错编码中的基本概念v汉明码汉明码：能够纠正：能够纠正1位错码的效率较高的线性位错码的效率较高的线性 分组码。分组码。v循环码循环码：就有循环性的线性分组码。：就有循环性的线性分组码。vBCH码码：能够纠正多个随机错码的循环码。：能够纠正多个随机错码的循环码。vRS码码：具有很强纠
9、错能力的多进制：具有很强纠错能力的多进制BCH码。码。142022-2-28纠错编码纠错编码纠错编码中的基本概念纠错编码中的基本概念v码长：一个码组中码元的数目。码长：一个码组中码元的数目。v码重：一个码组中码重：一个码组中“1”的个数。的个数。v码距码距d：两个等长码组之间对应位不同的个数。：两个等长码组之间对应位不同的个数。v最小码距最小码距 ：码组集合中所有码距的最小值。：码组集合中所有码距的最小值。0d152022-2-28纠错编码纠错编码纠错编码纠错编码纠检错能力与最小码距纠检错能力与最小码距 的关系的关系：0dv一个码组内检测一个码组内检测e个误码：个误码：v一个码组内纠正一个码组
10、内纠正t t个误码：个误码：v一个码组内纠正一个码组内纠正t t个误码同时检测个误码同时检测 e e（etet）个误码：个误码： 10 ed120 td)(10teted162022-2-28纠错编码纠错编码码距与检错和纠错能力的关系：码距与检错和纠错能力的关系： 0d0dBAABett0123012345(a)(b)ABett1(c)172022-2-28纠错编码纠错编码纠错编码系统的性能：纠错编码系统的性能：v误码率性能和带宽的关系：误码率性能和带宽的关系：采用编码降低采用编码降低误码率所付出的代价是带宽的增大。误码率所付出的代价是带宽的增大。v功率和带宽的关系：功率和带宽的关系：采用编码
11、以节省功率，采用编码以节省功率，并保持误码率不变，付出的代价也是带宽并保持误码率不变，付出的代价也是带宽的增大。的增大。182022-2-28纠错编码纠错编码纠错编码系统的性能：纠错编码系统的性能：v传输速率和带宽的关系：传输速率和带宽的关系：对于给定的传输系对于给定的传输系统，其传输速率和信噪比统，其传输速率和信噪比 的关系为的关系为0/bEn0000(1/)bsssBEPTPPnnnTn R 提高传输速率，采用编码以保持误码提高传输速率，采用编码以保持误码率不变，代价是带宽增大。率不变，代价是带宽增大。192022-2-28纠错编码纠错编码纠错编码系统的性能：纠错编码系统的性能：v编码增益
12、：编码增益：在保持误码率恒定的条件下，采在保持误码率恒定的条件下，采用纠错编码所节省的信噪比用纠错编码所节省的信噪比0/bEn00(/)(/)dBbubcGEnEndB 未编码时的信噪比未编码时的信噪比编码后所需的信噪比编码后所需的信噪比202022-2-28奇偶监督码奇偶监督码 监督位只有监督位只有1位，码率为位，码率为 k/(k+1) 奇偶监督码能够检测奇数个错码奇偶监督码能够检测奇数个错码 分为奇数监督码和偶数监督码分为奇数监督码和偶数监督码 在奇数监督码中，监督位使码组中在奇数监督码中，监督位使码组中“1”的个的个数数 为奇数为奇数212022-2-28奇偶监督码奇偶监督码在偶数监督码
13、中，监督位使码组中在偶数监督码中，监督位使码组中“1”的个数的个数为偶数。在接收端检测时，将接收码组按照式为偶数。在接收端检测时，将接收码组按照式求求“模模2和和”，若计算结果为，若计算结果为“1”就说明有错码，就说明有错码，为为“0”就认为无错码。（就认为无错码。（a0为监督位，其余位为监督位，其余位为信息位）为信息位）1200nnaaa222022-2-28二维奇偶监督码二维奇偶监督码 方阵码或矩形码方阵码或矩形码 构造方法构造方法：先将若干奇偶监督码按行排列成：先将若干奇偶监督码按行排列成矩阵，再按列增加第二维监督位矩阵，再按列增加第二维监督位 码率为：码率为： 有可能检测出偶数个错码有
14、可能检测出偶数个错码 适合检测突发错码，能够纠正部分错码适合检测突发错码，能够纠正部分错码(1)(1)km nnmn232022-2-28线性分组码线性分组码代数码代数码是利用代数关系式产生监督位的编码。是利用代数关系式产生监督位的编码。线性分组码线性分组码是代数码的一种，其监督位和信息是代数码的一种，其监督位和信息位的关系由线性方程决定。位的关系由线性方程决定。汉明码汉明码是能够纠正一个错误的效率较高的线性是能够纠正一个错误的效率较高的线性分组码。分组码。242022-2-28线性分组码线性分组码校正子校正子S（监督关系式）（监督关系式） 纠错就是通过计算纠错就是通过计算S，实际中，实际中S
15、只有两种只有两种取值，故只能表示有错和无错，而不能进一取值，故只能表示有错和无错，而不能进一步指明错码的位置。步指明错码的位置。120nnSaaa 252022-2-28线性分组码线性分组码若有若有r个监督关系式，则个监督关系式，则r个校正子可以指明一个个校正子可以指明一个错码的（错码的（2r-1）个不同位置。）个不同位置。当校正子可以指明的错码位置数目等于或大于当校正子可以指明的错码位置数目等于或大于码组长度码组长度n时，才能纠正码组中任何一个位置上时，才能纠正码组中任何一个位置上的错码，即要求的错码，即要求2121rrnkr 或 262022-2-28线性分组码线性分组码汉明码汉明码要求设
16、计一个能够纠正要求设计一个能够纠正1个错误的分组码个错误的分组码(n,k)，给定的码组中有给定的码组中有4个信息位，个信息位，k=4，则监督位数，则监督位数r3。若取。若取r=3，则，则n=k+r=7。现在用现在用a6a5a4a3a2a1a0表示这表示这7个码元，用个码元，用S1S2S3表示校正子，则这表示校正子，则这3个校正子恰好能够指个校正子恰好能够指明明7个错码的位置。个错码的位置。272022-2-28线性分组码线性分组码S1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码165422653136430SaaaaSa
17、aaaSaaaa汉明码汉明码282022-2-28线性分组码线性分组码265416530643aaaaaaaaaaaa汉明码汉明码 信息位的值决定于输入信号，是随机的。信息位的值决定于输入信号，是随机的。监督位是按监督关系确定的，应保证校正子监督位是按监督关系确定的，应保证校正子S等于等于0，既有：，既有：654265316430000aaaaaaaaaaaa292022-2-28汉明码汉明码（7,4）码，若）码，若 代表代表4个信息个信息 位，这位，这 代表代表3个监督码元。个监督码元。线性分组码线性分组码3456aaaa、012aaa、（信息位）3456aaaa（监督位）012aaa（信息
18、位）3456aaaa（监督位）012aaa0000000100100011010001010110011100001110111011010101100010001001101010111100110111101111111100010001001010100111302022-2-28线性分组码线性分组码汉明码汉明码接收端解码方法：接收端解码方法： 根据接收码组，先计算出校正子根据接收码组，先计算出校正子S1S2S3 ，然后查表判断错码位置。然后查表判断错码位置。165422653136430SaaaaSaaaaSaaaa312022-2-28线性分组码线性分组码汉明码汉明码码率：码率：21
19、21rrkrn 322022-2-28线性分组码线性分组码用矩阵形式表示用矩阵形式表示）模 2(0001011001110101011101000123456aaaaaaaTTTH AOA HO或332022-2-28线性分组码线性分组码监督矩阵监督矩阵H矩阵可以分成两部分矩阵可以分成两部分rPIH001101101011011001110典型形式监督矩阵典型形式监督矩阵具有具有 形式的形式的H矩阵矩阵rPI各行必须是线各行必须是线性无关的性无关的rn342022-2-28线性分组码线性分组码0001011001010101001101000111QIGr生成矩阵生成矩阵TPQ 转置矩阵转置矩
20、阵65432106543Aa a a a a a aa a a a GG的各行必须是的各行必须是线性无关的线性无关的knkrrk352022-2-28线性分组码线性分组码解码过程解码过程 发送码组发送码组A，接收到的码组，接收到的码组B，收发码，收发码 组之差记为组之差记为E（错误图样错误图样）ABE021eeenn()SB HAE HE HTTT校正子校正子若若S和和E之间有一一对应，则能代表错码的位置。之间有一一对应，则能代表错码的位置。362022-2-28线性分组码线性分组码00000010a00100004a0000010010000000001002a10000006a000100
21、03a0000000无错0011010101101001110110001a5aSSEE错码位置错码位置错码位置错码位置372022-2-28线性分组码线性分组码线性码的封闭性线性码的封闭性若若M1和和M2是一种线性分组码中的两个码组，是一种线性分组码中的两个码组，则则( M1 + M2 )仍是其中一个码组。仍是其中一个码组。码的最小距离就是码的最小重量码的最小距离就是码的最小重量382022-2-28循环码循环码具有循环性。即循环码中任一码组循环一位具有循环性。即循环码中任一码组循环一位（将最右端的码元移至左端，或反之）以后，（将最右端的码元移至左端，或反之）以后，仍为该码中的一个码组。仍为
22、该码中的一个码组。为便于计算，把这样的码组中个码元当作是一为便于计算，把这样的码组中个码元当作是一个多项式的系数，即把一个长为个多项式的系数，即把一个长为n的码组表示成的码组表示成 为信息码多项式为信息码多项式121210( )nnnnT xaxaxa xax仅是码元位置的标记，我们并不关心仅是码元位置的标记，我们并不关心x的取的取值，这种多项式称为值，这种多项式称为码多项式码多项式。( )m x392022-2-28循环码循环码)()()()()(21xgxxgxgxxgxxGkk循环码的循环码的生成多项式生成多项式 是常数项不是常数项不为为”0” 的的 的一个（的一个（n-k）次因式）次因
23、式)(xg) 1(nx循环码的生成矩阵循环码的生成矩阵402022-2-28循环码循环码循环码的编码方法循环码的编码方法根据给定的根据给定的(n,k)值选定生成多项式值选定生成多项式)(xg( )g x即从即从 的因子中选一的因子中选一(n-k)次多项次多项式作为式作为) 1(nx412022-2-28循环码循环码循环码的编码方法循环码的编码方法 将信息码多项式将信息码多项式 升升(n-k)次幂后除以生成多次幂后除以生成多 项式项式得到的系统循环码多项式得到的系统循环码多项式)(xm)(xg)()()()()(xgxrxQxgxmxkn)()()(xrxmxxTkn422022-2-28循环码
24、循环码例：例：求求(7,3)循环码中，信息码循环码中，信息码110所对应的码组所对应的码组 解：解：v求v v v T(x)=1100000+101=1100101( )g x2( )m xxx7 32224242( )()1(1)( )11n kxm xxxxxxxg xxxxxxx422652( )( )( )()11n kT xxm xr xxxxxxxx432022-2-28循环码循环码循环码的编码方法循环码的编码方法 可用除法电路来可用除法电路来主要是用带反馈的线主要是用带反馈的线性移位寄存器来实现性移位寄存器来实现 abcd+Kfem输入输出（7，3）码编码器码编码器 442022
25、-2-28循环码循环码循环码的解码循环码的解码检错解码器检错解码器缓冲移存器除法电路反相与门接收信息码重发指令接收码组”时输出“余式”时输出“余式0010452022-2-28循环码循环码循环码的解码循环码的解码)()()()()(xgxrxQxgxR 在接收端用生成多项式在接收端用生成多项式 去除接去除接收码组收码组 ，而后通过判断余项，而后通过判断余项 是否为零来判别是否为零来判别)(xr)(xg)(xR462022-2-28循环码循环码循环码的纠错循环码的纠错 先计算接收多项式先计算接收多项式 的校正式的校正式 ，然后根据校正式然后根据校正式 用查表的方法或通过某用查表的方法或通过某种运算得到错误图样种运算得到错误图样 ，再从，再从 减去减去 即可得到已纠正错误的发送码组即可得到已纠正错误的发送码组 。)(xR)(xS)(xS)(xE)(xR)(xE)(xT472022-2-28循环码循环码循环码的纠错循环码的纠错纠错解码器纠错解码器abc门7级缓存器+与门输出输入
