版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
1、2008.81第第 九九 章章差错控制编码差错控制编码2008.82引言引言1纠错编码的基本原理纠错编码的基本原理2常用的简单编码常用的简单编码3线章章 差错控制编码差错控制编码67卷积码卷积码网格编码调制网格编码调制2008.839.1 引言信道信道解调解调信源信源编码编码加密加密调制调制解密解密译码译码信宿信宿噪声噪声同步系统同步系统信源编码信源编码 信道编码信道编码 差错控制差错控制ASKFSKPSKDPSK数字通信的组成数字通信的组成A/DA/D数据压缩数据压缩2008.84数字通信中的编码分为数字通信中的编码分为：信道编码：信道编码：信源编码：
2、信源编码：为提高信号传输的为提高信号传输的有效性有效性而而采取的措施。采取的措施。为提高信号传输的为提高信号传输的可靠性可靠性而而采取的措施。亦称差错控制采取的措施。亦称差错控制编码。编码。2008.85 在通信过程中，会受到各种外来在通信过程中，会受到各种外来干干扰，如脉冲干扰，随机噪声干扰扰，如脉冲干扰，随机噪声干扰，人，人为干扰及通信线路传输性能的限制都为干扰及通信线路传输性能的限制都将使信号失真。由于以上原因，引起将使信号失真。由于以上原因，引起数据信息序列产生错误，称之为数据信息序列产生错误，称之为差错。差错。 2008.86差错的两大类型：差错的两大类型： 随机性错误随机性错误：前
3、后出错位之间无一定关：前后出错位之间无一定关系，随机、离散出现。系，随机、离散出现。 突发性错误突发性错误：差错成串出现，且有一定：差错成串出现，且有一定相关性。相关性。 实际信道中，上述两种错误常同时存实际信道中，上述两种错误常同时存在。在。 2008.87v合理的设计基带信号合理的设计基带信号v时域时域/ /频域均衡频域均衡 v发射功率的提高发射功率的提高v采用信道编码采用信道编码都能有效的提高传输可靠性。2008.88差错控制 在发送端利用信道编码器在数据信息中在发送端利用信道编码器在数据信息中增加一些监督信息，使不带规律性或规律性增加一些监督信息，使不带规律性或规律性不强的原始数字信号
4、变为带规律性或加强了不强的原始数字信号变为带规律性或加强了规律性的数字信号，规律性的数字信号，信道译码器信道译码器则利用这些则利用这些规律性来鉴别是否发生错误，或进行错误纠规律性来鉴别是否发生错误，或进行错误纠正正。2008.89 1、差错控制方法（1）前向纠错法）前向纠错法FEC 所发码具有纠错能力，收端接收后自动纠所发码具有纠错能力，收端接收后自动纠错，无需反向信道。实时性好，但译码设备错，无需反向信道。实时性好，但译码设备复杂，复杂，传输效率传输效率 。信源信源FEC编码编码信道信道FEC译码译码信宿信宿（2）信息反馈法）信息反馈法IF信息信号信息信号信息信号信息信号发端收端收端 方法和
5、设备简单，无需纠检错编译系统。方法和设备简单，无需纠检错编译系统。但需要双向信道，但需要双向信道，传输效率传输效率、实时性差、实时性差 。2008.810 (3)检错重发法ARQ 所发码具有检错能力，收端接收后判决是所发码具有检错能力，收端接收后判决是否出错，通过反向信道发送判决结果，发端否出错，通过反向信道发送判决结果，发端据此决定是否重发。据此决定是否重发。 译码设备简单，对突发错误有效，要求有反馈信道。译码设备简单，对突发错误有效，要求有反馈信道。信源信源编码器编码器正向信道正向信道译码器译码器信宿信宿缓存器缓存器重发控制器重发控制器反向信道反向信道重发判决器重发判决器工作过程：发送工作
6、过程：发送检测检测回复回复重发或发送新的数据重发或发送新的数据2008.811停止等待方式停止等待方式 3221221发送端发送端接收端接收端 ARQ的三种实现方式： 特点：半双工工作，简单，要求的缓存量小，但等待时间较长，特点：半双工工作，简单，要求的缓存量小，但等待时间较长，传输效率传输效率 2008.812 连续重发方式 2543210退退N N步方式：从出错帧开始重发步方式：从出错帧开始重发优缺点：传输效率优缺点：传输效率，但重发的，但重发的N N帧中，大部分帧中，大部分为正确，所以仍有浪费。发端缓存必须可存为正确，所以仍有浪费。发端缓存必须可存N N帧。
7、帧。 2008.9876543210 只对出错信息重发，因此传输效率大大提只对出错信息重发，因此传输效率大大提高高 。但收发两端都要有足够的存储空间。但收发两端都要有足够的存储空间。 选择重发方式 2008.814反馈信道反馈信道ARQFEC编码器编码器正向信道正向信道FEC译码器译码器ARQ 编码既有纠错能力也有检错能力，收端收到编码既有纠错能力也有检错能力，收端收到信息码组后在收端进行检测。在纠错范围内：信息码组后在收端进行检测。在纠错范围内：纠正；超出范围：通过纠正；超出范围：通过ARQARQ方式进行重发。方式进行重发。 (4) 混合方式 2008.815（
8、1）根据各码组信息码和监督码的关系分：根据各码组信息码和监督码的关系分： 线性码，非线性码线性码，非线性码根据监督码元是否仅与本组信息元有关根据监督码元是否仅与本组信息元有关 分组码，卷积码分组码，卷积码（2）根据纠错码组中信息元是否隐蔽分：根据纠错码组中信息元是否隐蔽分： 系统码，非系统码系统码，非系统码（3）纠错码的分类2008.816根据码的用途分：根据码的用途分： 检错码检错码 ，纠错码，纠错码（4）根据根据码元的取值码元的取值： 二进制码，多进制码二进制码，多进制码（5）根据根据构造编码的数学方法构造编码的数学方法： 代数码，几何码，算术码代数码，几何码，算术码（6）本课程主要讨论纠
9、随机错误的二进制线性分组码。本课程主要讨论纠随机错误的二进制线、 几个术语几个术语码长：码长：码组中码元的数目，常用码组中码元的数目，常用n n 表示；表示；码距：码距：两等长码字两等长码字C C1 1、C C2 2对应位上取值不同的对应位上取值不同的数目，又称为汉明数目，又称为汉明(Hamming)(Hamming)距离，记为距离，记为d(cd(c1 1,c,c2 2) )。码重码重：码组中非零码元的数目，记为：码组中非零码元的数目，记为W W；最小码距最小码距：在分组码：在分组码(n,k)(n,k)中，任意两个码字之中，任意两个码字之间
10、汉明距离的最小值，记为间汉明距离的最小值，记为d dminmin。码距的大小关系到编码的检码距的大小关系到编码的检纠纠错能力错能力。2008.818n=3时，码距的几何说明：时，码距的几何说明：（ a2 a1 a0 ）a2a1a0（ 110） （ 011 ）d=2110011（ 111） （ 000 ）d=.819A A、B B两消息，可用一位二进制数表示，两消息，可用一位二进制数表示，A=1A=1、B=0B=0出错时无法判定出错时无法判定 。例例 增加一个监督位，取增加一个监督位，取11A11A、00B,00B,若收到若收到0101或或1010时，时， 可知发生了错误，
11、但不能纠正错误。可知发生了错误，但不能纠正错误。 再增加一个监督位，取再增加一个监督位，取111A111A、000B,000B,如一位错：如一位错： B001 A110B001 A110；若两位错若两位错011,110011,110则只能发现不能纠错则只能发现不能纠错 因此因此这种（这种（3.13.1）码，能纠正一个错，发现两个错。）码，能纠正一个错，发现两个错。 但是但是 (3.1)(3.1)码中，数据位仅为码中，数据位仅为1 1位，监督位为两位，位，监督位为两位，传输效率传输效率 可以看出：差错控制是以牺牲传输效率为代价而可以看出：差错控制是以牺牲传输效率为代价而换取了传输质量的提高的。纠
12、检错能力与加入的监督换取了传输质量的提高的。纠检错能力与加入的监督元数目成正比。元数目成正比。 2、 纠错或检错的原理2008.820分组码的三个参数分组码的三个参数码长码长 n，信息位信息位 k，最小距离最小距离 d0 ， 用符号用符号 (n,k,d0) 表示表示k个信息元个信息元an-1 an-2 ar ar-1 a0 r个监督元个监督元码长：码长：n = k+rR=k/n为为编码效率编码效率，d0一定一定(纠错能力一定纠错能力一定)时，时，k/n大，效率高。大，效率高。 对被传输的信息序列分组，每组为对被传输的信息序列分组，每组为k k个信息元，对个信息元，对每组按某种关系附加每组按某种
13、关系附加(n-k) (n-k) 个监督码元个监督码元 ( (校验校验) )，形成，形成为为n n位的码字。这种方法构成的码组称为位的码字。这种方法构成的码组称为分组码分组码。2008.821 3、分组码的纠(检)错能力与最小码距d0的关系 任一任一（ n n，k k）分组码，若要在码字内能：分组码，若要在码字内能： 1/ 1/ 检测检测e e个随机错误，则要求：个随机错误，则要求： d d0 e+1e+1 2/ 2/ 纠正纠正t t个随机错误，则要求：个随机错误，则要求： d d0 0 2 2t+1t+1 3/ 3/ 纠正纠正t t个同时检测个同时检测e e(et)(et)个随机错误，个随机错
14、误，则要求：则要求： d d0 0 e+t+1 e+t+1 2008.822 A1 d 0eA2（a）A1 A2 d 0et（c） A1 d 0tA2（b）A2t2008.823例：例：一个码集，只有两个许用码：一个码集，只有两个许用码：00000000、11111111，试求其纠、检错能力，试求其纠、检错能力和编码效率。和编码效率。2008.8244、对纠错编码的要求对纠错编码的要求例：例：一个码集，只有两个许用码：一个码集，只有两个许用码：0000、1111，试求其纠检错能力和编码效率。试求其纠检错能力和编码效率。解：解：根据码距的定义，则该码集根据码距的定义，则该码集d 0 = 4， 1
15、/ 用于检错，用于检错，e d d0 0 1=3，即可检即可检3个错误；个错误；2/ 用于纠错，用于纠错，t (d d0 01)/2=3/2，取整，即可纠取整，即可纠1个错误；个错误；3/ 同时用于纠、检错，同时用于纠、检错， d d0 0 e+t+1 e+t+1 （e et t） 取：取：e=2，t=1，则可满足上式，即可检则可满足上式，即可检2个错误个错误 同时纠一个错；同时纠一个错；R=k/n=1/42008.8255. 差错控制编码的效用 假设在随机信道中，发送假设在随机信道中，发送“0”0”和和“1”1”的错误概的错误概率相等，都等于率相等，都等于p p，且，且p p1 1，在码长为
17、的实际应用价值。具有较大的实际应用价值。2008.8276. 有扰信道编码定理（Shannon第二定理） 对于给定的有扰信道，若信道容量为对于给定的有扰信道，若信道容量为C C，只要发送端以低于只要发送端以低于C C的信息速率的信息速率R Rb b发送信息，发送信息，则则一定存在一种编码方法一定存在一种编码方法，使得译码错误概，使得译码错误概率率P P随着码长随着码长n n的增加，按指数下降至任意小的增加，按指数下降至任意小的值，表示为的值，表示为 P P e e-nE(Rb-nE(Rb) )E(RE(Rb b) )为误差指数，为误差指数，R Rb bC0)0。 Rbmax=C=Blog2(1
18、+S/N) （bit/s）2008.828 系统带宽和信噪比的矛盾：系统带宽和信噪比的矛盾： 由上节所述的纠错编码原理可知，为了减少接收错误由上节所述的纠错编码原理可知，为了减少接收错误码元数量，需要在发送信息码元序列中加入监督码元。码元数量，需要在发送信息码元序列中加入监督码元。这样作的结果使发送序列增长，冗余度增大。若仍须这样作的结果使发送序列增长，冗余度增大。若仍须保持发送信息码元速率不变，则传输速率必须增大，保持发送信息码元速率不变，则传输速率必须增大，因而增大了系统带宽。系统带宽的增大将引起系统中因而增大了系统带宽。系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比的下降反
19、而又噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。一般说来，采用使系统接收码元序列中的错码增多。一般说来，采用纠错编码后，误码率总是能够得到很大改善的。改善纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。的程度和所用的编码有关。2008.829 编码性能举例编码性能举例 未采用纠错编码时，未采用纠错编码时，若接收信噪比等于若接收信噪比等于7dB，编码前误码率，编码前误码率约为约为8 10-4，图中，图中A点，在采用纠错编码点，在采用纠错编码后，误码率降至约后，误码率降至约4 10-5，图中，图中B点。这样，点。这样，不增大发送功率不增大发送
20、功率就能就能降低误码率约一个半降低误码率约一个半数量级。数量级。10--310-210-1编码后PeCDEAB信噪比 (dB)2008.830 由图还可以看出，若由图还可以看出，若保持误码率在保持误码率在10-5，图中图中C点，未采用编点，未采用编码时，约需要信噪比码时，约需要信噪比Eb / n0 = 10.5 dB。在。在采用这种编码时，约采用这种编码时，约需要信噪比需要信噪比7.5 dB，图，图中中D点。可以节省功率点。可以节省功率2 dB。通常称这。通常称这2 dB为为编码增益编码增益。 上面两种情况付出的代上面两种情况付出的代价是带宽增大。价是带宽增大。10-61
21、0--210-1编码后PeCDEAB信噪比 (dB)2008.831 传输速率和传输速率和Eb/n0的关系的关系对于给定的传输系统对于给定的传输系统式中，式中，RB为码元速率。为码元速率。若希望提高传输速率，若希望提高传输速率，由上式看出势必使信由上式看出势必使信噪比下降，误码率增噪比下降，误码率增大。假设系统原来工作大。假设系统原来工作在图中在图中C点，提高速率后点，提高速率后由由C点升到点升到E点。但加用点。但加用纠错编码后，仍可将误码纠错编码后，仍可将误码率降到率降到D点。这时付出的点。这时付出的代价仍是带宽增大。代价仍是带宽增大。BsssbRnPTnPnTPnE0
22、000)/ 1 (10--310-210-1编码后PeCDEAB信噪比 (dB)2008.8329-3 常用的简单编码1 1、奇偶监督码：、奇偶监督码： k=n-1,r=1k=n-1,r=1的线性码。的线性码。特点：特点： 码组中的码组中的1 1个数是奇数（奇监督码）个数是奇数（奇监督码） 或偶数（偶监督码）。或偶数（偶监督码）。0021aaann偶监督时，要满足：偶监督时，要满足：1021aaann奇监督时，要满足：奇监督时，要满足：两者的校验能力相同，均只能检测出奇数个错误。两者的校验能力相同，均只能检测出奇数个错误。R=k/n=n-1/n=1-1/n编码效率：编码效
25、11100 1011110111 0110101101 1000110001 1010110101 试对其进行（试对其进行（6 6，5 5）偶校验编码，写出码序列）偶校验编码，写出码序列并分析其抗干扰能力并分析其抗干扰能力解：解： （6 6，5 5）, ,将数据序列每将数据序列每5 5码元分组，码元分组，123450aaaaaa并作：并作：的运算的运算可得出编码数据序列：可得出编码数据序列：011 1 只能检测出奇数个错误，不能发现偶数个错误，只能检测出奇数个错误，不能发现偶数个错误
26、，也不能纠错。也不能纠错。 2008.8382 2、水平垂直奇偶校验、水平垂直奇偶校验码：码： 又称行列监督码或二维奇偶监督码。又称行列监督码或二维奇偶监督码。特点：特点：对水平方向和垂直方向的码元同时实施奇偶监督。对水平方向和垂直方向的码元同时实施奇偶监督。 1 1 0 0 1 0 1 0 0 0 00 1 0 0 0 0 1 1 0 1 00 1 1 1 1 0 0 0 0 1 11 0 0 1 1 1 0 0 0 0 01 0 1 0 1 0 1 0 1 0 11 1 0 0 0 1 1 1 1 0 0行行列列监监督督码码2008.839适于监测突发错误：适于监测突发错误：q逐行传输时，
27、能检测长度逐行传输时，能检测长度b b m+ m+1 1的突发错误的突发错误; ;q逐列传输时逐列传输时, ,能检测长度能检测长度b b L+L+1 1的突发错误；的突发错误；q还能纠正一些仅在一行中的单个错误。还能纠正一些仅在一行中的单个错误。其中其中m为行数，为行数，L为列数为列数2008.8403 3、恒比码：、恒比码： 又称等重码或定又称等重码或定1 1码。码。特点：特点： 码组中码组中0 0，1 1的个数保持不变。的个数保持不变。 若码长为若码长为n n，码重为码重为w w，则此码的码字个数则此码的码字个数 为：为：C Cn nw w，禁用码字个数为：禁用码字个数为：2 2n n -
28、 - C Cn nw w例如：我国的电报，每个汉字用四个例如：我国的电报，每个汉字用四个1010进制数表进制数表 示，每位示，每位1010进制数就采用进制数就采用 3 3：2 2 恒比码构恒比码构 成的成的5 5位码组来表示。位码组来表示。码字的个数码字的个数C C5 53 3 =10=10检错能力较强，可检出检错能力较强，可检出所有奇数所有奇数和和部分偶数部分偶数错误。错误。2008.841数字数字码码 字字0 01 12 23 34 45 56 67 78 89 1101
29、3:2 恒比码恒比码如：我国的电报，每如：我国的电报，每个汉字用四个个汉字用四个1010进制进制数表示，每位数表示，每位1010进制进制数就采用数就采用 3 3：2 2 恒比恒比码构成的码构成的5 5位码组来表位码组来表示。示。码字的个数码字的个数C C5 53 3 =10=102008.8424 4、正反码：、正反码： 简单的可纠错编码，信元数等于监督元数简单的可纠错编码，信元数等于监督元数特点：特点： 信息位中，有奇数个信息位中，有奇数个1 1时，监督位重复信息位；时，监督位重复信息位； 信息位中，有偶数个信息位中，
30、有偶数个1 1时，监督位取信息位的反码；时，监督位取信息位的反码；可纠一位、检测所有两位错和部分两位以上的错误。可纠一位、检测所有两位错和部分两位以上的错误。例：例：11001 1100111001 10001 1000110001 (n,k) (n,k) 其中其中k=n/2 k=n/2 编码效率：编码效率： R=k/n=1/2R=k/n=1/22008.8439.4 线 基本概念基本概念 可用线性方程组表述码的规律性的分可用线性方程组表述码的规律性的分组码称为线性分组码。线性码建立在代组码称为线、。线性码建立在代数学群论基础上，线性码各许用码的集数学群论基础上，线性码各许用码的集合构成代数学中的群，因此，又称为群合构成代数学中的群，因此，又称为群码。码。2008.844 1. 1. 含有全零码字。含有全零码字。 2.2.任意两个许用码字之和仍是一个许用码字。任意两个许用码字之和仍是一个许用码字。（封闭性封闭性） 3.3.最小码距最小码距d d0 0等于非零码字的最小重量即等于非零码字的最小重量即d d0 0= =w wminmin （由此性质可以方便的确定出线性分组码的最（由此性质可以方便的确定出线性分组码的最小码距，进而明确其纠错能力。）小码距，进而明确其纠错能力。） 在群中只有一种
32、运算，就是模在群中只有一种运算，就是模2 2 和。和。线 奇偶监督码是一种最简单的线性码，我们曾经作了奇偶监督码是一种最简单的线性码，我们曾经作了偶校验的例子。偶校验的例子。0021aaann称为监督称为监督方程方程。接收时，为了检测传输时是否有错，还要做同样的计接收时，为了检测传输时是否有错，还要做同样的计算：算：01234bbbbbs有错无错10s这里这里S S称为称为校正子，校正子，上式也称上式也称伴随式伴随式。奇偶监督码中只有一位监督码，因此只能表示有否错误。奇偶监督码中只有一位监督码，因此只能表示有否错误。2008.846当监督位增加，
33、则监督方程增加，校正子增加。当监督位增加，则监督方程增加，校正子增加。r r位监督码除了用全位监督码除了用全“0”0”表示无错外，可表示表示无错外，可表示r21种错误图样。种错误图样。(n,k)码可纠错的错误图样数为：码可纠错的错误图样数为： 我们把接收码组我们把接收码组R R与发射码组与发射码组C C的差称为的差称为错误图样错误图样，用用E E表示：表示：E=C-RE=C-R，或者，或者 C=R+EC=R+E (n,k)中，信息码为中，信息码为k位，可传输位，可传输M=2k种信息，当种信息，当增加增加r位的监督位后，有位的监督位后，有2n种状态，但只取种状态，但只取2k 种为许种为许用状态，
34、其他为禁用，用状态，其他为禁用，(n,k)码可检测的错误图样数为码可检测的错误图样数为 2n-2k2 n-k -1=2 r-1不可检测的错误图样数为不可检测的错误图样数为2k-12008.8471nc2nctnctiinc12 n-k-1 + + =对于能纠正对于能纠正 t 个错误的线性分组码个错误的线性分组码(n,k)应满足：应满足：inc是错是错 i 位的个数。位的个数。如果满足如果满足 ，则有可能构造出纠正一位或一，则有可能构造出纠正一位或一位以上的线性码位以上的线nnc 即对于码组长度为即对于码组长度为n n，信息码元信息码元k k位，监督元位，监督元r r，nr
40、0 0 1 1 7 0 1 1 1 0 0 0 7 0 1 1 1 0 0 02008.8529.4.2 监督矩阵 将前面的监督方程改写成矩阵的形式，将前面的监督方程改写成矩阵的形式， C=CC=C6 6C C5 5C C4 4C C3 3C C2 2C C1 1C C0 0 可看成为编码矢量，于是有：可看成为编码矢量，于是有：记做：记做：TTHC00TCH监督方程监督方程2008.853H - H - 监督矩阵监督矩阵 不满足以上关系的为非典型矩阵，典型矩阵和不满足以上关系的为非典型矩阵，典型矩阵和非典型矩阵之间可以转换。非典型矩阵之间可以转换。2/ 2/ H H矩阵各行是线、行是线性无关的。行数行数-监督元的个数监督元的个数r r列数列数-码组长度码组长度 n nI Ir r为为r r阶单位阵阶单位阵1/ 1/ 当有当有H=P H=P IrIr 时称为典型矩阵，时称为典型矩阵，2008.854利用监督方程，我们可以对线性码的利用监督方程，我们可以对线性码的封闭性加以证明封闭性加以证明 即H阵与编码码字的转置乘积为0，可用来作为判断接收码组是否错的依据。,/3TTOCH2008.855 设监督方程设监督方程A A1 1、A A2 2均为均为线性码集合中的许用码线性码集合中的许用码组，因此有组，因此有 令两许用码组相加令两许用码组相加 A A1 1+A+A2 2带入监
43、：2008.857QCCCCCCC3456012令令QPT则有：则有：给给Q Q的左边，加一个的左边，加一个k kk k阶的单位矩阵，则构成：阶的单位矩阵，则构成：G=G=I Ik k Q Q称为称为生成矩阵生成矩阵，且为典型形式。典型，且为典型形式。典型G G矩阵矩阵行数行数- - 信息元的个数信息元的个数k k列数列数- - 码组长度码组长度 n n每行本身就是一个许用码组每行本身就是一个许用码组TTHG00TGH于是有：于是有：矩阵和非典型矩阵之间可以转换。矩阵和非典型矩阵之间可以转换。2008.858码字的前面码字的前面 k k 位为信息位，后面位为信息位，后面 位为位为监督位监督位一
44、般情况，定义线性分组码的码字有如下形式：一般情况，定义线性分组码的码字有如下形式：信息码元信息码元监督位监督位信息信息位位编码编码 码字码字kkn kn系统形式的线性分组码系统形式的线()nnn kn kCccccc 120()kkMmmm02121mmmccckkknnnkn 0M G编码编码 kkn 2008.859设信息组生成矩阵生成矩阵编码码组编码码组CM G6543Mcccc2008.860. )2阶矩阵，各行线）由G和信息组即可产生全部码字.通过典型生成矩阵产生的一定是系统码。通过典型生成矩阵产生的一定是系统码。G称为典型生成矩阵。3) kGI Q2
45、008.110100G （1）试确定试确定(n,k)，并求，并求H ； (2) 写出监督元与信息元的关系式及写出监督元与信息元的关系式及 该（该（n,k）码的全部码字；码的全部码字； (3) 确定最小码距及检错能力。确定最小码距及检错能力。例：设已知设已知2008.101001解：求H，需确定P，TQPQPT应将已知的那个G转换成典型形式，求出Q，再利用 求出G。100G001H=P Ir=011rTIQ2008.863 (2) 0THC0000
47、：d d0 0=3=3可用于检两位错或纠一位错。利用性质知：最小利用性质知：最小码距码距d0 0等于非零码等于非零码字的最小重量即字的最小重量即d0 0=wminmin2008.8659.4.4 校正子S 发送端经过编码后给出：发送端经过编码后给出：0121cccccnn接收端收到的码组为：接收端收到的码组为：0121rrrrRnn两者的差记为：两者的差记为：0121eeeeCREnniiiiicrcre10表示第表示第 i 位无错位无错表示第表示第 i 位有错位有错E称为错误图样。共有称为错误图样。共有2n个错误图样。个错误图样。当当 E为全零错误图样时，为全零错误图样时，R=C 没有传输错
48、误没有传输错误;2008.866TTHR0可可利用利用E检出或纠正错误；检出或纠正错误；TTHR0传输中的错误超出了可纠错的范围。传输中的错误超出了可纠错的范围。但可能有但可能有两种两种情况：情况：(n,k)可检测的错误图样数为可检测的错误图样数为 2n - 2k(n,k)可纠错的错误图样数为可纠错的错误图样数为 2n-k - 1这时的错误图样称为不可检测的错误图样这时的错误图样称为不可检测的错误图样一般来讲，一般来讲，E=0， 则则R=C，可满足监督方程可满足监督方程E0，则，则RC，不满足监督方程不满足监督方程检错：当检错：当S=0时，认为时，认为E=0，当，当S 0时，认为时，认为E 0
49、,校正子校正子 S 的计算的计算TTTTTEHEHCHHECRHS)(即校正子只与错误图样即校正子只与错误图样E有关。有关。2008.867构造标准阵列的一般方法如下：构造标准阵列的一般方法如下：1）用概率译码确定各伴随式）用概率译码确定各伴随式S对应的差错图案对应的差错图案E，共，共 对对；2）表格为）表格为 列，列， 行，先确定第一行和第一列，第一行为行，先确定第一行和第一列，第一行为 个个码字码字 ，第一列为，第一列为 ；3）各列对应的元素为第一列的）各列对应的元素为第一列的 和该列的和该列的 之和；之和；2n2k2n k2kiEjciEjC0C1C21kC00SE000EC011ECC
52、 0 0 0 由于由于 ，当只发生一位错码时，矩阵，当只发生一位错码时，矩阵E E中中只有一个非零元素，与只有一个非零元素，与H H的转置相乘的结果是选的转置相乘的结果是选出其中的一列，即校正子与出其中的一列，即校正子与H H矩阵的哪一列相同，矩阵的哪一列相同，则该列即为码元发生错误的位置。则该列即为码元发生错误的位置。 TEHS = 0 0 0 1 0 1 1 2008.872(n，k)线性分组码编、译码过程小结： 编码过程：编码过程： 设线性分组码为设线性分组码为(n，k)，0121mmmmMkk信息码为：信息码为：1) 根据生成矩阵或监督矩阵，根据生成矩阵或监督矩阵，2) 由由C=MG0
53、 求出所有码字，且为系统码。求出所有码字，且为系统码。H0=P IrG0=Ik QQPT求出典型生成矩阵；求出典型生成矩阵；2008.873译码过程：译码过程：1） 由收到的码组由收到的码组R计算校正子计算校正子S；TRHS TTHRS或2） 由由S判决是否有错并通过判决是否有错并通过 找出错误图样；找出错误图样；TEHS 3） 按照按照 R+E=C 计算并还原计算并还原 C；4）将码组）将码组C还原成原信息组还原成原信息组M。2008.8749.4.5 汉明码汉明码是用于纠一位错误的线性分组码。汉明码是用于纠一位错误的线性分组码。特点：特点：12 rn最小码距：最小码距： 30d纠错能力：纠
54、错能力：1t编码效率编码效率 ：R1knrrnnn Rn当 很大时，2008.875例n=15的汉明码，其监督位为多少？编码的汉明码，其监督位为多少？编码效率为多少？效率为多少？2008.876解：解：4161212rnnrr，可知：由于是其信息位有于是其信息位有 15-4=11 位位此汉明码为（此汉明码为（15，11）码）码编码效率：编码效率：R/11/1573%k n其监督位有其监督位有 15-11=4 位位2008.877 汉明码是线性分组码，因此其监督矩阵同样汉明码是线性分组码，因此其监督矩阵同样有有n n列、列、r r行，当监督位数给定后，即可构造出行，当监督位数给定后，即可构造出汉
55、明码。汉明码。例，例，r=3 H H矩阵的矩阵的n n列由除了全零以外的列由除了全零以外的 个个r r位码位码构成，每码组出现一次且全部出现。（构成，每码组出现一次且全部出现。（H H不唯一）不唯一）21r11G110100H构造构造2008.878得到的汉明码如下所示：得到的汉明码如下所示：信息位监督位信息位监督位a6a5a4a111a2a1a0101011000a6a5a4a10110011
56、0111101111a2a1a008.879（7，4）汉明码编码器）汉明码编码器a6a5a4a3信息组信息组a0a1a2a3a4码字码字+a5a6+2008.880完备码 纠正单个错误的汉明码中，纠正单个错误的汉明码中，r r 位校正子码组与位校正子码组与误码图样一一对应，最充分地利用了监督位所能误码图样一一对应，最充分地利用了监督位所能提供的信息。提供的信息。 在一般情况下，对于能纠正在一般情况下，对于能纠正t t个错误的线性分个错误的线性分组码组码(n(n，k)k)，应满足以下不等式：应满足以下不等式： 因此，汉明码也是纠一位错的线、码中，因此，汉明码也是纠一位错的线性分组码中，编码效率最高的编码效率最高的。tiintnnnknrCCCC.881tiintnnnknrCCCC1211212 上式取等号时，校正子与误码不超过上式取等号时，校正子与误码不超过t t个的所个的所有图样一一对应，监督码元得到最充分的利用，有图样一一对应，监督码元得到最充分的利用，这种线性分组码即完备码。这种线性分组码即完备码。 除汉明码外，迄今为止，找到的唯一能纠除汉明码外，迄今为止，找到的唯一能纠正多个错误的完备码为正多个错误的完备码为(23(23，12)12)戈雷码。戈雷码。 t=3t=3汉明码就是一种完备码。汉明码就是一
58、种完备码。 该式亦称为汉明界，它给出已知该式亦称为汉明界，它给出已知k k和和t t时，时，所需要的监督位数。所需要的监督位数。2008.882列阵的个来构成时，可任选其中nHnrn12 但此时构成的则非汉明码。但此时构成的则非汉明码。 通常选择码重最小的矢量优先。通常选择码重最小的矢量优先。例试构造一个试构造一个k=5的可纠一个错的线性分组码的可纠一个错的线/ 计算最短的码长；计算最短的码长；2/ 构造构造H；3/ 求生成矩阵求生成矩阵G；4/ 求信息组为求信息组为(10101)的编码码字的编码码字C。2008.883解：解： 1/ 因为因为t 等于等于1, 且要求且要求k=5,
59、可用试探法确定可用试探法确定n设：设：n-k=3，则则 不满足纠错要求；不满足纠错要求； 853712123nkn设：设：n-k=4，则则 满足纠错要求；满足纠错要求； 9541512124nkn于是取于是取n=9，此时此时r = n-k = 4，(9, 5)线，四位码共有四位码共有 种状态，除全零外种状态，除全零外 都可用于构造都可用于构造H矩阵。矩阵。1624 为了构造典型矩阵，选为了构造典型矩阵，选1000，0100，0010，0001四码组，然后从其余的四码组，然后从其余的11个码组中，再选出个码组中，再选出5个，通常个，通常按照码重从小到
60、大选择。按照码重从小到大选择。100111HPIr实际只需实际只需9个个2008.001 QIGk4/ M=1 0 1 0 1C=MG=1 0 1 0 1 0 1 1 0Q3/ 求生成矩阵求生成矩阵 已知已知 TPQ Ik于是有：于是有：2008.8869.5 循环码9.5.1 9.5.1 循环码原理循环码原理 循环码是线性分组码的一个重要子类，也是循环码是线性分组码的一个重要子类，也是目前研究最成熟的一类码。它不仅有封闭性，且还目前研究最成熟的
61、一类码。它不仅有封闭性，且还有循环性。有循环性。(n(n，k)k)码组码组0121CCCCCnna则将则将所有码元向左循环一位，得到的：所有码元向左循环一位，得到的：10132nnnbCCCCCC也是许用码组也是许用码组是许用码组是许用码组。即即10111iiniCC CC CCC2008.887 若线性分组码的若线性分组码的任一码组循环移位所任一码组循环移位所得码组仍在该码组集得码组仍在该码组集中，则此码为循环码。中，则此码为循环码。（7，3）循环码序号 码 字 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 2 0 1 0 0 1 1 1 3 0 1 1 1 0 1 0 4
63、较简单；由于具有循环性，编译码设备较简单； 可以用代数的方法分析和设计编码。可以用代数的方法分析和设计编码。10-5-2 循环码的多项式表示已知码组：已知码组：0121CCCCCnn设设x为一个任意的实变量，其幂次代表移位的次数，为一个任意的实变量，其幂次代表移位的次数，以以Ci 作为多项式的系数，则可以得到码多项式：作为多项式的系数，则可以得到码多项式： )(012211CxCxCxCxCnnnn循环码的特点循环码的特点2008.890)(012211CxCxCxCxCnnnn每循环一位，相当于码多项式乘以每循环一位，相当于码多项式乘以x，仍为许用码组仍为许用码组)(10212312) 1
65、信息码组为：其对应多项式为：其对应多项式为：012211)(mxmxmxmxmkkkk2008.892)()()()(210121xgxgxxgxxgxmmmmkknn)(012211xgmxmxmxmkkkk)()(xgxm则编码码组为：则编码码组为：)()(xMGxC由上式可看出：用由上式可看出：用G(x)G(x)生成的码字，都是生成的码字，都是g(x)g(x)的倍式，的倍式， 都可以被都可以被g(x)g(x)整除。整除。2008.893如何寻找生成多项式？已知编码码组为：已知编码码组为：)()()(xgxmxC生成多项式是一个生成多项式是一个n-k次的多项式，且本身也是次的多项式，且本身
1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
2026届浙江省杭州市江南实验学校高三化学第一学期期末达标测试试题含解析
2025贵州航空产业城集团股份有限公司旗下子公司贵州安立航空材料有限公司招聘61人笔试历年参考题库附带答案详解
2025年公招教师特岗教师招聘考试教育公共基础知识线年贵州省中考英语真题含答案
