第九章差错控制编码_sxq

1、第第9 9章章差错控制编码差错控制编码南京航空航天大学信息科学与技术学院南京航空航天大学信息科学与技术学院 通信原理教研组通信原理教研组copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组2引言引言1纠错编码的基本原理纠错编码的基本原理2常用的简单编码常用的简单编码3线性分组码线性分组码4循环码循环码5第第9章章 差错控制编码差错控制编码67卷积码卷积码网格编码调制网格编码调制copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组39.1 引言引言信道信道解调解调信源信源编码编码加密加密调制调制解密解密译码译码信宿信宿噪声噪声同步系

2、统同步系统信源编码信源编码 信道编码信道编码 差错控制差错控制ASKFSKPSKDPSK数字通信的组成数字通信的组成A/DA/D数据压缩数据压缩copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组4采用信道编码采用信道编码 在通信过程中，会受到各种外来干扰，如脉冲干扰，随在通信过程中，会受到各种外来干扰，如脉冲干扰，随机噪声干扰，人为干扰及通信线路传输性能的限制都将使信机噪声干扰，人为干扰及通信线路传输性能的限制都将使信号失真。由于以上原因，引起数据信息序列产生错误，称之号失真。由于以上原因，引起数据信息序列产生错误，称之为为差错差错。 随机性错误：前后出错位之

3、间无一定关系，随机、离散出现。随机性错误：前后出错位之间无一定关系，随机、离散出现。突发性错误：差错成串出现，且有一定相关性。突发性错误：差错成串出现，且有一定相关性。差错的两大类型：差错的两大类型： 合理的设计基带信号合理的设计基带信号时域时域/频域均衡频域均衡 都能有效的提高传输可靠性。都能有效的提高传输可靠性。发射功率的提高发射功率的提高copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组5数字通信中的编码数字通信中的编码信道编码：信道编码：信源编码：信源编码： 为为提高信号传输的有效性提高信号传输的有效性而采取的措施。而采取的措施。为为提高信号传输的可靠

4、性提高信号传输的可靠性而采取的措施而采取的措施, ,亦称亦称差错控制编码。差错控制编码。 在发送端利用信道编码器在数据信息中增在发送端利用信道编码器在数据信息中增加一些监督信息，使不带规律性或规律性不加一些监督信息，使不带规律性或规律性不强的原始数字信号变为带规律性或加强了规强的原始数字信号变为带规律性或加强了规律性的数字信号，律性的数字信号，信道译码器信道译码器则利用这些规则利用这些规律性来鉴别是否发生错误，或进行错误纠正。律性来鉴别是否发生错误，或进行错误纠正。差错控制差错控制copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组6 1、差错控制方法、差错控制

5、方法（1）前向纠错法）前向纠错法FEC 所发码具有纠错能力，收端接收后自动纠所发码具有纠错能力，收端接收后自动纠错，无需反向信道。实时性好，但译码设备错，无需反向信道。实时性好，但译码设备复杂，复杂，传输效率传输效率 。信源信源FEC编码编码信道信道FEC译码译码信宿信宿copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组7（2）信息反馈法）信息反馈法IF信息信号信息信号信息信号信息信号发端收端收端 方法和设备简单，无需纠检错编译系统。方法和设备简单，无需纠检错编译系统。但需要但需要双向信道双向信道，传输效率传输效率、实时性差、实时性差 。copyright 信

6、息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组8(3)检错重发法检错重发法ARQ 所发码具有检错能力，收端接收后判决是否出错，通所发码具有检错能力，收端接收后判决是否出错，通过反向信道发送判决结果，发端据此决定是否重发。过反向信道发送判决结果，发端据此决定是否重发。 译码设备简单，对突发错误有效，要求有反馈信道。译码设备简单，对突发错误有效，要求有反馈信道。信源信源编码器编码器正向信道正向信道译码器译码器信宿信宿缓存器缓存器重发控制器重发控制器反向信道反向信道重发判决器重发判决器工作过程：发送工作过程：发送检测检测回复回复重发或发送新的数据重发或发送新的数据copyright

7、信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组9停止等待方式停止等待方式 3221221发送端发送端接收端接收端 ARQARQ的三种实现方式：的三种实现方式： 特点：半双工工作，简单，要求的缓存量小，但等待时间较长，特点：半双工工作，简单，要求的缓存量小，但等待时间较长，传输效率传输效率 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组10 连续重发方式 6543254321065432543210退退N N步方式：从出错帧开始重发步方式：从出错帧开始重发优缺点：传输效率优缺点：传输效率，但重发的，但重发的N N帧中，大部分帧中，大部分为正

8、确，所以仍有浪费。发端缓存必须可存为正确，所以仍有浪费。发端缓存必须可存N N帧。帧。 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组112987654321029876543210 只对出错信息重发，因此传输效率大大提只对出错信息重发，因此传输效率大大提高高 。但收发两端都要有足够的存储空间。但收发两端都要有足够的存储空间。 选择重发方式 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组12反馈信道反馈信道ARQFEC编码器编码器正向信道正向信道FEC译码器译码器ARQ 编码既有纠错能力也有检错能力，收端收到编码既有纠

9、错能力也有检错能力，收端收到信息码组后在收端进行检测。在纠错范围内：信息码组后在收端进行检测。在纠错范围内：纠正；超出范围：通过纠正；超出范围：通过ARQARQ方式进行重发。方式进行重发。 (4) 混合方式copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组13（1）根据各码组信息码和监督码的关系分：根据各码组信息码和监督码的关系分： 线性码，非线性码线性码，非线性码根据监督码元是否仅与本组信息元有关根据监督码元是否仅与本组信息元有关 分组码，卷积码分组码，卷积码（2）根据纠错码组中信息元是否隐蔽分：根据纠错码组中信息元是否隐蔽分： 系统码，非系统码系统码，非系

10、统码（3）纠错码的分类纠错码的分类copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组14根据码的用途分：根据码的用途分： 检错码检错码 ，纠错码，纠错码（4）根据根据码元的取值码元的取值： 二进制码，多进制码二进制码，多进制码（5）根据根据构造编码的数学方法构造编码的数学方法： 代数码，几何码，算术码代数码，几何码，算术码（6）本课程主要讨论纠随机错误的二进制线性分组码。本课程主要讨论纠随机错误的二进制线性分组码。copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组15纠错码的发展概况纠错码的发展概况n 通信的数学理论，通信的数

11、学理论，Shannon(1948)Shannon(1948)n 汉明码，汉明码，Hamming (1950)Hamming (1950)n 级连码，级连码，Forney(1966)Forney(1966)n 卷积码及有效译码，卷积码及有效译码，(60(60年代年代) )n RS RS码及有效译码，码及有效译码，(60(60年代年代) )n TCM TCM，Ungerboeck(1982),Forney(1984)Ungerboeck(1982),Forney(1984)n Turbo Turbo码，码，Berrou(1993) Berrou(1993) n LDPC LDPC 码，码，Gall

12、ager(1963),Macky(1996)Gallager(1963),Macky(1996)n 空时编码空时编码,Tarokh(2000),Tarokh(2000)copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组169.2 纠错编码的基本原理纠错编码的基本原理1、 几个术语几个术语码长：码长：码组中码元的数目，常用码组中码元的数目，常用n n表示；表示；码距：码距：两等长码字两等长码字C C1 1、C C2 2对应位上取值不同的对应位上取值不同的数目，又称为汉明数目，又称为汉明(Hamming)(Hamming)距离，记为距离，记为d(cd(c1 1,c

13、,c2 2) )。码重码重：码组中非零码元的数目，记为：码组中非零码元的数目，记为W W；copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组17n=3时，码距的几何说明：时，码距的几何说明：（ a2 a1 a0 ）a2a1a0（ 110） （ 011 ）d=2110011（ 111） （ 000 ）d=3000111最小码距最小码距：在分组码：在分组码(n,k)(n,k)中，任意两个码字之中，任意两个码字之间汉明距离的最小值，记为间汉明距离的最小值，记为d dminmin。最小码距的大小关系到编码的检最小码距的大小关系到编码的检纠纠错能力错能力。0101011

14、00001copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组18发送序列发送序列C: (1111011000)接收序列接收序列R: (0110010110)比较比较C和和R，可写出另一个序列，可写出另一个序列E：1001001110R = C + E 序列序列E定义为错误图样定义为错误图样(Error Pattern)错误图样：错误图样：copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组19A A、B B两消息，可用一位二进制数表示，两消息，可用一位二进制数表示，A=1A=1、B=0B=0出错时出错时无法判定无法判定 增加一个

15、监督位，取增加一个监督位，取11A11A、00B00B 再增加一个监督位，取再增加一个监督位，取111A111A、000B000B许用码组：许用码组：00，11禁用码组：禁用码组：01，10若收到若收到0101或或1010时，时，可知发生了错误，但不能纠正错误可知发生了错误，但不能纠正错误。许用码组：000，111禁用码组：001, 010, 100, 011, 101, 110如一位错如一位错能够纠正错误能够纠正错误；若两位错，；若两位错，则只能发现不能纠错则只能发现不能纠错2、纠错或检错的原理、纠错或检错的原理copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教

16、研组20因此因此这种（这种（3,13,1）码，能纠正一个错，发现两个错。）码，能纠正一个错，发现两个错。 但是但是 (3,1)(3,1)码中，数据位仅为码中，数据位仅为1 1位，监督位为位，监督位为两位，传输效率两位，传输效率 可以看出：差错控制是以可以看出：差错控制是以牺牲传输效率牺牲传输效率为代价而为代价而换取了传输质量的提高的。纠检错能力与加入的监督换取了传输质量的提高的。纠检错能力与加入的监督元方式和数目有关。元方式和数目有关。copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组21分组码的三个参数分组码的三个参数码长码长 n，信息位，信息位 k，最小距

17、离，最小距离 d0 ， 用符号用符号 (n,k,d0) 表示表示k个信息元个信息元an-1 an-2 ar ar-1 a0 r个监督元个监督元码长：码长：n = k+rR=k/n为为编码效率编码效率，d0一定一定(纠错能力一定纠错能力一定)时，时，k/n大，效率高。大，效率高。 对被传输的信息序列分组，每组为对被传输的信息序列分组，每组为k k个信息元，对个信息元，对每组按某种关系附加每组按某种关系附加(n-k) (n-k) 个监督码元个监督码元 ( (校验校验) )，形成，形成为为n n位的码字。这种方法构成的码组称为位的码字。这种方法构成的码组称为分组码分组码。3、分组码、分组码copyr

18、ight 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组224、分组码的纠分组码的纠( (检检) )错能力与最小码距错能力与最小码距d d0 0的关系的关系 任一任一（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)个随机错误，个随机错误，则要求：则要求： d d0 0 e+t+1 e+t+1 cop

19、yright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组231 A1 d0eA2（a）A1 A2 d0et（c） A1 d0tA2（b） A2t11copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组24例例9-1一个码集，只有两个许用码：一个码集，只有两个许用码：00000000、11111111，试求其纠、检错能力和编码效率。试求其纠、检错能力和编码效率。copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组25解：解：根据码距的定义，则该码集根据码距的定义，则该码集d0 = 4， 1/ 用于检错，用于检错

20、，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/4copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组26copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组275. 差错控制编码的效用差错控

21、制编码的效用 假设在随机信道中，发送假设在随机信道中，发送“0”0”和和“1”1”的的错误概率相等，都等于错误概率相等，都等于p p，且，且p p1 1，在码长，在码长为为n n的码组中，发生的码组中，发生r r个错误的概率为：个错误的概率为：!( )(1)!()!rrn rrnnnP rC pppr nrcopyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组28!( )(1)!()!rrn rrnnnP rC pppr nr例如：当例如：当n=7，p=10-时，则有：时，则有：371077) 1 ( pP5227101 . 221)!27( ! 2! 7)2(p

22、pP8337105 . 335)!37( ! 3! 7) 3(ppP 由此可见，即使仅能纠正由此可见，即使仅能纠正1-21-2个错误，也可使误码个错误，也可使误码率下降几个数量级。所以差错控制编码具有较大的实率下降几个数量级。所以差错控制编码具有较大的实际应用价值。际应用价值。copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组296. 6. 有扰信道编码定理（有扰信道编码定理（ShannonShannon第二定理）第二定理） 对于给定的有扰信道，若信道容量为对于给定的有扰信道，若信道容量为C C，只，只要发送端以低于要发送端以低于C C的信息速率的信息速率R

23、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+S/N) （bit/s）copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组30 1.码长码长n和信息速率和信息速率Rb一定时，随一定时，随C误差指数误差指数E(Rb) P随指数下降。随指数下降。 其中其中

24、C=Blog2(1+S/N)（bit/s） 2.在在C和和Rb一定时一定时(Rb C)，随码长，随码长n P 随指数下降随指数下降(P0)。 数字传输系统中，无误码传输的最高信息速率数字传输系统中，无误码传输的最高信息速率 Rbmax=C=Blog2(1+S/N) （bit/s） 两个结论：两个结论：copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组31编码性能举例 未采用纠错编码时，若接收信噪比等于7dB，编码前误码率约为810-4，图中A点，在采用纠错编码后，误码率降至约410-5，图中B点。这样，增大发送功率,就能降低误码率约一个半数量级。10-610-

25、510-410-310-210-1编码后PeAB信噪比 (dB)copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组32 由图还可以看出，若保持由图还可以看出，若保持误码率在误码率在1010-5-5，图中，图中C C点，点，未采用编码时，约需要信未采用编码时，约需要信噪比噪比E Eb b / n / n0 0 = 9.5 dB = 9.5 dB。在采用这种编码时，约需在采用这种编码时，约需要信噪比要信噪比7.5 dB7.5 dB，图中，图中D D点。可以节省功率点。可以节省功率2 dB2 dB。通常称这通常称这2 dB2 dB为为编码增益编码增益。 上面两种情况

26、付出的代上面两种情况付出的代价是带宽增大。价是带宽增大。10-610-510-410-310-210-1PeCD信噪比 (dB)编码后copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组33 传输速率和传输速率和E Eb b/n/n0 0的关系的关系对于给定的传输系统式对于给定的传输系统式中，中，R RB B为码元速率。为码元速率。若希望提高传输速率，若希望提高传输速率，由上式看出势必使信噪由上式看出势必使信噪比下降，误码率增大。比下降，误码率增大。假设系统原来工作在图假设系统原来工作在图中中C C点，提高速率后由点，提高速率后由C C点升到点升到E E点。但加

27、用纠点。但加用纠错编码后，仍可将误码错编码后，仍可将误码率降到率降到D D点。这时付出点。这时付出的代价仍是带宽增大。的代价仍是带宽增大。10-610-510-410-310-210-1编码后PeCDE信噪比 (dB)copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组349-3 9-3 常用的简单编码常用的简单编码1 1、奇偶监督码：、奇偶监督码： k=n-1,r=1k=n-1,r=1的线性码。的线性码。特点：特点： 码组中的码组中的1 1个数是奇数（奇监督码）个数是奇数（奇监督码） 或偶数（偶监督码）。或偶数（偶监督码）。0021aaann偶监督时，要满足：

28、偶监督时，要满足：1021aaann奇监督时，要满足：奇监督时，要满足：两者的校验能力相同，均只能检测出奇数个错误。两者的校验能力相同，均只能检测出奇数个错误。R=k/n=n-1/n=1-1/n编码效率：编码效率：copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组35 码长码长5 5的偶监督码的偶监督码序序 码码 字字 序序 码码 字字号号 信息码元信息码元 监督元监督元 号号 信息码元信息码元 监督元监督元 a4 a3 a2 a1 a0 a4 a3 a2 a1 a0 0 0 0 0 0 0 8 1 0 0 0 1 1 0 0 0 1 1 9 1 0 0 1

29、0 2 0 0 1 0 1 10 1 0 1 0 0 3 0 0 1 1 0 11 1 0 1 1 1 4 0 1 0 0 1 12 1 1 0 0 0 5 0 1 0 1 0 13 1 1 0 1 1 6 0 1 1 0 0 14 1 1 1 0 1 7 0 1 1 1 1 15 1 1 1 1 0 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组36 偶监督码编码器a4a3a2a1+信息组信息组a0a1a2a3a4码字码字12340aaaaacopyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组3701234bbbbbsb3

30、b0b1b2b4+接收码组BS检错信号有错无错10偶监督码的检错偶监督码的检错电路电路copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组38 例例9-29-2：一数据序列：一数据序列： 1110011100 1011110111 0110101101 1000110001 1010110101 试对其进行（试对其进行（6 6，5 5）偶校验编码，写出码序列）偶校验编码，写出码序列并分析其抗干扰能力并分析其抗干扰能力 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组39一数据序列一数据序列： 1110011100 101111

31、0111 0110101101 1000110001 1010110101 试对其进行（试对其进行（6 6，5 5）偶校验编码，写出码序列）偶校验编码，写出码序列并分析其抗干扰能力并分析其抗干扰能力解：解： （6 6，5 5）, ,将数据序列每将数据序列每5 5码元分组，码元分组，123450aaaaaa并作：并作：的运算的运算可得出编码数据序列：可得出编码数据序列：11100111001110111101110001101011011110001100010010101101011 1 只能检测出奇数个错误，不能发现偶数个错误，只能检测出奇数个错误，不能发现偶数个错误，也不能纠错。也不能纠错

32、。 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组402 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行行列列监监督督码码copyright

33、 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组41适于监测突发错误：q逐行传输时，能检测长度b M+1的突发错误;q逐列传输时,能检测长度bL+1的突发错误；q还能纠正一些仅在一行中的单个错误。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 0L5，M10的行列监督码的行列监督码其中其中M为列数，为列数，L为行数为行数copyright 信息科学与技术学院通信原理教研组信息科

34、学与技术学院通信原理教研组423 3、恒比码：、恒比码： 又称等重码或定又称等重码或定1 1码。码。特点：特点： 码组中码组中0 0，1 1的个数保持不变。的个数保持不变。 若码长为若码长为n n，码重为，码重为w w，则此码的码字个数，则此码的码字个数 为：为：C Cn nw w，禁用码字个数为：，禁用码字个数为：2 2n n - C- Cn nw w码字的个数码字的个数C C5 53 3 =10=10检错能力较强，可检出检错能力较强，可检出所有奇数所有奇数和和部分偶数部分偶数错误。错误。检错能力较强，可检出所有奇数和部分偶数错误。检错能力较强，可检出所有奇数和部分偶数错误。适用于传输电报或

35、其他键盘设备产生的字母或符适用于传输电报或其他键盘设备产生的字母或符号，但不适合信源发出的是二进制随机数字序列号，但不适合信源发出的是二进制随机数字序列的场合。的场合。copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组43数字数字码码 字字0 01 12 23 34 45 56 67 78 89 901101011010101101011110011100110110101101101011010001110011110101101011110011100011100111010011100113:2 恒比码恒比码如：我国的电报，每如：我国的电报，每个汉字用四

36、个个汉字用四个1010进制进制数表示，每位数表示，每位1010进制进制数就采用数就采用 3 3：2 2 恒比恒比码构成的码构成的5 5位码组来表位码组来表示。示。码字的个数码字的个数C C5 53 3 =10=10copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组44作业：4 4、正反码：、正反码： 简单的可纠错编码，信元数等于监督元数简单的可纠错编码，信元数等于监督元数特点：特点： 信息位中，有奇数个信息位中，有奇数个1 1时，监督位重复信息位；时，监督位重复信息位； 信息位中，有偶数个信息位中，有偶数个1 1时，监督位取信息位的反码；时，监督位取信息位的反

37、码；可纠一位、检测所有两位错和部分两位以上的错误。可纠一位、检测所有两位错和部分两位以上的错误。例：例：11001 1100111001 11001110011100110001 1000110001 100010111001110(n,k) (n,k) 其中其中k=n/2 k=n/2 编码效率：编码效率： R=k/n=1/2R=k/n=1/2copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组459.4 线性分组码9.4.1 9.4.1 基本概念基本概念 可用可用线性方程组线性方程组表述码的规律性的分表述码的规律性的分组码称为线性分组码。线性码建立在代数组码称

38、为线性分组码。线性码建立在代数学群论基础上，线性码各许用码的集合构学群论基础上，线性码各许用码的集合构成代数学中的群，因此，又称为群码。成代数学中的群，因此，又称为群码。copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组46 1. 1. 含有全零码字。含有全零码字。 2.2.任意两个许用码字之和仍是一个许用码字。任意两个许用码字之和仍是一个许用码字。（封闭性封闭性） 3.3.最小码距最小码距d d0 0等于非零码字的最小重量即等于非零码字的最小重量即d d0 0=W=Wminmin （由此性质可以方便的确定出线性分组码的最（由此性质可以方便的确定出线性分组码的

39、最小码距，进而明确其纠错能力。）小码距，进而明确其纠错能力。） 在群中只有一种运算，就是模在群中只有一种运算，就是模2 2 和。和。线性分组码的性质线性分组码的性质：copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组47 奇偶监督码是一种最简单的线性码，我们曾经作了奇偶监督码是一种最简单的线性码，我们曾经作了偶校验的例子。偶校验的例子。0021aaann称为称为监督监督方程方程。接收时，为了检测传输时是否有错，还要做同样的计接收时，为了检测传输时是否有错，还要做同样的计算：算：01234bbbbbs有错无错10s这里这里S S称为称为校正子，校正子，上式也称上

40、式也称伴随式伴随式。奇偶监督码中只有一位监督码，因此只能表示有否错误。奇偶监督码中只有一位监督码，因此只能表示有否错误。copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组48当监督位增加，则监督方程增加，校正子增加。当监督位增加，则监督方程增加，校正子增加。r r位监督码除了用全位监督码除了用全“0”0”表示无错外，可表示表示无错外，可表示r21种错误图样。种错误图样。(n,k)码可纠错的错误图样数为：码可纠错的错误图样数为： 我们把接收码组我们把接收码组R R与发射码组与发射码组C C的差称为的差称为错误图样错误图样，用用E E表示：表示：E=C-RE=C-

41、R，或者，或者 C=R+EC=R+E (n,k)中，信息码为中，信息码为k位，可传输位，可传输M=2k种信息，当种信息，当增加增加r位的监督位后，有位的监督位后，有2n种状态，但只取种状态，但只取2k 种为许种为许用状态，其他为禁用，用状态，其他为禁用，(n,k)码可检测的错误图样数为码可检测的错误图样数为 2n-2k2n-k -1=2r-1不可检测的错误图样数为不可检测的错误图样数为2k-1copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组491nc2nctnctiinc12 n-k-1 + + =对于能纠正对于能纠正 t 个错误的线性分组码个错误的线性分组

42、码(n,k)应满足：应满足：inc是错是错 i 位的个数。位的个数。如果满足如果满足 ，则有可能构造出纠正一位或一位，则有可能构造出纠正一位或一位以上的线性码以上的线性码。i=1时，时，1nnc 即对于码组长度为即对于码组长度为n n，信息码元，信息码元k k位，监督元位，监督元r r，nr12copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组50 思考：思考： 例例9-39-3设设(n(n，k)k)中，中，k=4k=4，要求能纠一位错，取，要求能纠一位错，取r=r=？copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组51 解

43、：解： (n(n，k)k)线性分组码，线性分组码，k=4k=4，要求能纠一位错，要求能纠一位错，现取现取r=3r=3，可指示，可指示2 23 3-1=7-1=7种错误，种错误， 码长码长n=4+3=7n=4+3=7，表示为：表示为： C=CC=C6 6C C5 5C C4 4C C3 3C C2 2C C1 1C C0 0 其中其中C C6 6C C5 5C C4 4C C3 3为信息码元，为信息码元，C C2 2C C1 1C C0 0为监督元为监督元由由r=3r=3，可有三个监督方程和校正子，设为，可有三个监督方程和校正子，设为s s1 1s s2 2s s3 321rn 恰好满足恰好满足

44、 , ,故可纠一位错。故可纠一位错。copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组52设设s1s2s3三位校正子与误三位校正子与误码位置的对应关系为：码位置的对应关系为：0 0 00 0 00 0 10 0 10 1 00 1 01 0 01 0 00 1 10 1 11 0 11 0 11 1 01 1 01 1 11 1 1误码位置误码位置无错无错 C C0 0 C C1 1 C C2 2 C C3 3 C C4 4 C C5 5 C C6 6S S1 1 S S2 2 S S3 3 于是监督码元于是监督码元C C2 2C C1 1C C0 0应应由以

45、下由以下监督方程监督方程决定。决定。C C2 2=C=C6 6+C+C5 5+C+C4 4C C1 1=C=C6 6+C+C5 5+C+C3 3C C0 0=C=C6 6+C+C4 4+C+C3 3监督元与信息元之间的线性方程组监督元与信息元之间的线性方程组s1=C2+C6+C5+C4=0s2=C1+C6+C5+C3=0s3=C0+C6+C4+C3=0copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组53于是得到于是得到(7(7，4)4)线性分组码如下：线性分组码如下： 序序 码码 字字 号号 信息元信息元 监督元监督元 8 1 0 0 0 1 1 18 1

46、0 0 0 1 1 1 9 1 0 0 1 1 0 0 9 1 0 0 1 1 0 0 10 1 0 1 0 0 1 0 10 1 0 1 0 0 1 0 11 1 0 1 1 0 0 1 11 1 0 1 1 0 0 1 12 1 1 0 0 0 0 1 12 1 1 0 0 0 0 1 13 1 1 0 1 0 1 0 13 1 1 0 1 0 1 0 14 1 1 1 0 1 0 0 14 1 1 1 0 1 0 0 15 1 1 1 1 1 1 1 15 1 1 1 1 1 1 1 序序 码码 字字 号号 信息元信息元 监督元监督元 0 0 0 0 0 0 0 00 0 0 0 0 0

47、 0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 2 0 0 1 0 1 0 1 2 0 0 1 0 1 0 1 3 0 0 1 1 1 1 0 3 0 0 1 1 1 1 0 4 0 1 0 0 1 1 0 4 0 1 0 0 1 1 0 5 0 1 0 1 1 0 1 5 0 1 0 1 1 0 1 6 0 1 1 0 0 1 1 6 0 1 1 0 0 1 1 7 0 1 1 1 0 0 0 7 0 1 1 1 0 0 0copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组549.4.2 监督矩阵000100110101010110

48、0101110123456CCCCCCC 将前面的监督方程改写成矩阵的形式，将前面的监督方程改写成矩阵的形式， C=CC=C6 6C C5 5C C4 4C C3 3C C2 2C C1 1C C0 0 可看成为编码矢量，于是有：可看成为编码矢量，于是有：记做：记做：TTHC00TCH监督方程监督方程copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组55H - H - 监督矩阵监督矩阵110110110111P 不满足以上关系的为非典型矩阵，典型矩阵和不满足以上关系的为非典型矩阵，典型矩阵和非典型矩阵之间可以转换。非典型矩阵之间可以转换。2/ 2/ H H矩阵

49、各行是线性无关的。矩阵各行是线性无关的。行数行数-监督元的个数监督元的个数r r列数列数-码组长度码组长度 n nI Ir r为为r r阶单位阵阶单位阵1/ 1/ 当有当有H=P IrH=P Ir时称为典型矩阵，时称为典型矩阵，100I010001copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组56利用监督方程，我们可以对线性码的利用监督方程，我们可以对线性码的封闭性加以证明封闭性加以证明 即H阵与编码码字的转置乘积为0，可用来作为判断接收码组是否错的依据。,/3TTOCHcopyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组5

50、7 设监督方程设监督方程A A1 1、A A2 2均为线性码集合中的许用码均为线性码集合中的许用码组，因此有组，因此有 令两许用码组相加令两许用码组相加 A A1 1+A+A2 2带入监督方程，有：带入监督方程，有：02THA01THA因此，因此， A A1 1+A+A2 2亦为许用码组。亦为许用码组。0)(2121TTTHAHAHAAcopyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组589.4.3 生成矩阵 当给出信息组后，如何方便迅速地求出整个当给出信息组后，如何方便迅速地求出整个编码码组，即如何生成编码矢量编码码组，即如何生成编码矢量？C C2 2=C=

51、C6 6+C+C5 5+C+C4 4C C1 1=C=C6 6+C+C5 5+C+C3 3C C0 0=C=C6 6+C+C4 4+C+C3 3由监督元与信息元之间的关系：由监督元与信息元之间的关系：3456012110110110111CCCCCCCTPCCCCCCC3456012或者可以写成：或者可以写成：copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组59QCCCCCCC3456012令令QPT则有：则有：给给Q Q的左边，加一个的左边，加一个k kk k阶的单位矩阵，则构成：阶的单位矩阵，则构成：G=IG=Ik k Q Q称为称为生成矩阵生成矩阵，且

52、为典型形式。典型，且为典型形式。典型G G矩阵矩阵行数行数- - 信息元的个数信息元的个数k k列数列数- - 码组长度码组长度 n n每行本身就是一个许用码组每行本身就是一个许用码组TTHG00TGH于是有：于是有：矩阵和非典型矩阵之间可以转换。矩阵和非典型矩阵之间可以转换。copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组60码字的前面码字的前面 k k 位为信息位，后面位为信息位，后面 位为位为监督位监督位一般情况，定义线性分组码的码字有如下形式：一般情况，定义线性分组码的码字有如下形式：信息码元信息码元监督位监督位信息信息位位编码编码 码字码字kkn

53、kn系统形式的线性分组码系统形式的线性分组码1210()nnn kn kCccccc 120()kkMmmm02121mmmccckkknnnkn 0M G编码编码 kkn copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组61设信息组1000111010011000101010001011G生成矩阵生成矩阵编码码组编码码组CM G6543Mcccccopyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组62. )2阶矩阵，各行线性无关为nkG1）由G和信息组即可产生全部码字.111110 101011TQP通过典型生成矩阵产生的一

54、定是系统码。通过典型生成矩阵产生的一定是系统码。k10000100I00100001G称为典型生成矩阵。3) kGI Qcopyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组63011010101001110100G （1）试确定试确定(n,k)(n,k)，并求，并求H H ； (2) (2) 写出监督元与信息元的关系式及写出监督元与信息元的关系式及 该（该（n,kn,k）码的全部码字；）码的全部码字； (3) (3) 确定最小码距及检错能力。确定最小码距及检错能力。例9-4设已知设已知copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理

55、教研组64110100011010101001解：求H，需确定P，QPT应将已知的那个G转换成典型形式，求出Q，再利用 求出G。011010101001110100G011010110100101001H=P Ir=100101010110001011rTIQcopyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组65 (2) 0THC5432101101000110100101001cccccc设C= 012345cccccc于是有：110100011010101001345cccGMC监督元与信息元的关系式监督元与信息元的关系式copyright 信息科学与技术

56、学院通信原理教研组信息科学与技术学院通信原理教研组66用三位二进制数的所有用三位二进制数的所有8种状态带入，可得到所有码字如右表种状态带入，可得到所有码字如右表。 序号 码 字 0 0 0 0 0 0 0 1 0 0 1 0 1 1 2 0 1 0 1 1 0 3 0 1 1 1 0 1 4 1 0 0 1 0 1 5 1 0 1 1 1 0 6 1 1 0 0 1 1 7 1 1 1 0 0 0(3) 确定最小码距及确定最小码距及 检错能力检错能力所以有：所以有：d d0 0=3=3可用于检两位错或可用于检两位错或纠一位错。纠一位错。利用性质知：最小利用性质知：最小码距码距d0 0等于非零码

57、等于非零码字的最小重量即字的最小重量即d0 0=wminmincopyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组679.4.4 校正子S 发送端经过编码后给出：发送端经过编码后给出：0121cccccnn接收端收到的码组为：接收端收到的码组为：0121rrrrRnn两者的差记为：两者的差记为：0121eeeeCREnniiiiicrcre10表示第表示第 i 位无错位无错表示第表示第 i 位有错位有错E称为错误图样。共有称为错误图样。共有2n个错误图样。个错误图样。当当 E为全零错误图样时，为全零错误图样时，R=C 没有传输错误没有传输错误;copyright

58、 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组68TTHR0可利用可利用E检出或纠正错误；检出或纠正错误；TTHR0传输中的错误超出了可纠错的范围。传输中的错误超出了可纠错的范围。可能有可能有两种两种情况：情况：(n,k)可检测的错误图样数为可检测的错误图样数为 2n - 2k(n,k)可纠错的错误图样数为可纠错的错误图样数为 2n-k - 1这时的错误图样称为不可检测的错误图样这时的错误图样称为不可检测的错误图样一般来讲，一般来讲，E=0， 则则R=C，可满足监督方程，可满足监督方程E0，则，则RC，不满足监督方程，不满足监督方程检错：当检错：当S=0时，认为时，认为E=

59、0，当，当S 0时，认为时，认为E 0,校正子校正子 S 的计算的计算TTTTTEHEHCHHECRHS)(即校正子只与错误图样即校正子只与错误图样E有关。有关。copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组69标准阵列表标准阵列表kknknknknkkkkCECECEECECECEECECECEECCCCDDDD2232222233323322322222321232101E排列方法排列方法第一个元素。排在零码字个码字排在第一行，全码的）（02),(11Cknk陪陪集集陪陪集集首首copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信

60、原理教研组70kknknknknkkkkCECECEECECECEECECECEECCCCDDDD2232222233323322322222321232101E陪陪集集陪陪集集首首下面构成第二行。放在下面，并将放在重作为错误图样重中选择重量较小的个剩下的）（iiknCCECEnn212222且希望重量尽可能小。重是前面未出现过的，每行第一个重。有继续以上过程，用完所）（nn3copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组71构造标准阵列的一般方法如下：构造标准阵列的一般方法如下：1）用概率译码确定各伴随式）用概率译码确定各伴随式S对应的差错图案对应的差错