第九章 差错控制编码_sxq

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

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

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

4、： 为为提高信号传输的有效性提高信号传输的有效性而采取的措施。而采取的措施。 为为提高信号传输的可靠性提高信号传输的可靠性而采取的措施而采取的措施, ,亦称亦称 差错控制编码。差错控制编码。 在发送端利用信道编码器在数据信息中增在发送端利用信道编码器在数据信息中增 加一些监督信息，使不带规律性或规律性不加一些监督信息，使不带规律性或规律性不 强的原始数字信号变为带规律性或加强了规强的原始数字信号变为带规律性或加强了规 律性的数字信号，律性的数字信号，信道译码器信道译码器则利用这些规则利用这些规 律性来鉴别是否发生错误，或进行错误纠正。律性来鉴别是否发生错误，或进行错误纠正。 差错控制差错控制

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

6、纠检错编译系统。方法和设备简单，无需纠检错编译系统。 但需要但需要双向信道双向信道，传输效率传输效率、实时性差、实时性差 。 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组8 (3)检错重发法检错重发法ARQ 所发码具有检错能力，收端接收后判决是否出错，通所发码具有检错能力，收端接收后判决是否出错，通 过反向信道发送判决结果，发端据此决定是否重发。过反向信道发送判决结果，发端据此决定是否重发。 译码设备简单，对突发错误有效，要求有反馈信道。译码设备简单，对突发错误有效，要求有反馈信道。 信源信源编码器编码器正向信道正向信道译码器译码器信宿信宿 缓存器缓存器

7、 重发控制器重发控制器反向信道反向信道重发判决器重发判决器 工作过程：发送工作过程：发送检测检测回复回复重发或发送新的数据重发或发送新的数据 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组9 停止等待方式停止等待方式 3221 221 发送端发送端 接收端接收端 ARQARQ的三种实现方式：的三种实现方式： 特点：半双工工作，简单，要求的缓存量小，但等待时间较长，特点：半双工工作，简单，要求的缓存量小，但等待时间较长， 传输效率传输效率 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组10 连续重发方式 65432543

8、210 65432543210 退退N N步方式：从出错帧开始重发步方式：从出错帧开始重发 优缺点：传输效率优缺点：传输效率，但重发的，但重发的N N帧中，大部分帧中，大部分 为正确，所以仍有浪费。发端缓存必须可存为正确，所以仍有浪费。发端缓存必须可存N N帧。帧。 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组11 29876543210 29876543210 只对出错信息重发，因此传输效率大大提只对出错信息重发，因此传输效率大大提 高高 。但收发两端都要有足够的存储空间。但收发两端都要有足够的存储空间。 选择重发方式 copyright 信息科学与技

9、术学院通信原理教研组信息科学与技术学院通信原理教研组12 反馈信道反馈信道 ARQ FEC 编码器编码器 正向信道正向信道 FEC 译码器译码器 ARQ 编码既有纠错能力也有检错能力，收端收到编码既有纠错能力也有检错能力，收端收到 信息码组后在收端进行检测。在纠错范围内：信息码组后在收端进行检测。在纠错范围内： 纠正；超出范围：通过纠正；超出范围：通过ARQARQ方式进行重发。方式进行重发。 (4) 混合方式 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组13 （1） 根据各码组信息码和监督码的关系分：根据各码组信息码和监督码的关系分： 线性码，非线性码线

10、性码，非线性码 根据监督码元是否仅与本组信息元有关根据监督码元是否仅与本组信息元有关 分组码，卷积码分组码，卷积码 （2） 根据纠错码组中信息元是否隐蔽分：根据纠错码组中信息元是否隐蔽分： 系统码，非系统码系统码，非系统码 （3） 纠错码的分类纠错码的分类 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组14 根据码的用途分：根据码的用途分： 检错码检错码 ，纠错码，纠错码 （4） 根据根据码元的取值码元的取值： 二进制码，多进制码二进制码，多进制码 （5） 根据根据构造编码的数学方法构造编码的数学方法： 代数码，几何码，算术码代数码，几何码，算术码 （6）

11、 本课程主要讨论纠随机错误的二进制线性分组码。本课程主要讨论纠随机错误的二进制线性分组码。 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组15 纠错码的发展概况纠错码的发展概况 n 通信的数学理论，通信的数学理论，Shannon(1948)Shannon(1948) n 汉明码，汉明码，Hamming (1950)Hamming (1950) n 级连码，级连码，Forney(1966)Forney(1966) n 卷积码及有效译码，卷积码及有效译码，(60(60年代年代) ) n RS RS码及有效译码，码及有效译码，(60(60年代年代) ) n TC

12、M TCM，Ungerboeck(1982),Forney(1984)Ungerboeck(1982),Forney(1984) n Turbo Turbo码，码，Berrou(1993) Berrou(1993) n LDPC LDPC 码，码，Gallager(1963),Macky(1996)Gallager(1963),Macky(1996) n 空时编码空时编码,Tarokh(2000),Tarokh(2000) copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组16 9.2 纠错编码的基本原理纠错编码的基本原理 1、 几个术语几个术语 码长：码长：

13、码组中码元的数目，常用码组中码元的数目，常用n n表示；表示； 码距：码距：两等长码字两等长码字C C1 1、C C2 2对应位上取值不同的对应位上取值不同的 数目，又称为汉明数目，又称为汉明(Hamming)(Hamming)距离，记为距离，记为 d(cd(c1 1,c,c2 2) )。 码重码重：码组中非零码元的数目，记为：码组中非零码元的数目，记为W W； copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组17 n=3时，码距的几何说明：时，码距的几何说明： （ a2 a1 a0 ） a2 a1 a0 （ 110） （ 011 ） d=2 110 011

14、 （ 111） （ 000 ） d=3 000 111 最小码距最小码距：在分组码：在分组码(n,k)(n,k)中，任意两个码字之中，任意两个码字之 间汉明距离的最小值，记为间汉明距离的最小值，记为d dmin min。 最小码距的大小关系到编码的检最小码距的大小关系到编码的检纠纠错能力错能力。 010 101 100 001 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组18 发送序列发送序列C: (1111011000) 接收序列接收序列R: (0110010110) 比较比较C和和R，可写出另一个序列，可写出另一个序列E：1001001110 R =

15、 C + E 序列序列E定义为错误图样定义为错误图样(Error Pattern) 错误图样：错误图样： copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组19 A A、B B两消息，可用一位二进制数表示，两消息，可用一位二进制数表示，A=1A=1、B=0B=0出错时出错时 无法判定无法判定 增加一个监督位，取增加一个监督位，取11A11A、00B00B 再增加一个监督位，取再增加一个监督位，取111A111A、000B000B 许用码组：许用码组：00，11 禁用码组：禁用码组：01，10 若收到若收到0101或或1010时，时，可知发生了错误，但不能纠正错

16、误可知发生了错误，但不能纠正错误。 许用码组：000，111 禁用码组：001, 010, 100, 011, 101, 110 如一位错如一位错能够纠正错误能够纠正错误；若两位错，；若两位错，则只能发现不能纠错则只能发现不能纠错 2、纠错或检错的原理、纠错或检错的原理 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组20 因此因此 这种（这种（3,13,1）码，能纠正一个错，发现两个错。）码，能纠正一个错，发现两个错。 但是但是 (3,1)(3,1)码中，数据位仅为码中，数据位仅为1 1位，监督位为位，监督位为 两位，传输效率两位，传输效率 可以看出：差错

17、控制是以可以看出：差错控制是以牺牲传输效率牺牲传输效率为代价而为代价而 换取了传输质量的提高的。纠检错能力与加入的监督换取了传输质量的提高的。纠检错能力与加入的监督 元方式和数目有关。元方式和数目有关。 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组21 分组码的三个参数分组码的三个参数 码长码长 n，信息位，信息位 k，最小距离，最小距离 d0 ， 用符号用符号 (n,k,d0) 表示表示 k个信息元个信息元 an-1 an-2 ar ar-1 a0 r个监督元个监督元 码长：码长：n = k+r R=k/n为为编码效率编码效率，d0一定一定(纠错能力一

18、定纠错能力一定)时，时，k/n大，效率高。大，效率高。 对被传输的信息序列分组，每组为对被传输的信息序列分组，每组为k k个信息元，对个信息元，对 每组按某种关系附加每组按某种关系附加(n-k) (n-k) 个监督码元个监督码元 ( (校验校验) )，形成，形成 为为n n位的码字。这种方法构成的码组称为位的码字。这种方法构成的码组称为分组码分组码。 3、分组码、分组码 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组22 4、分组码的纠分组码的纠( (检检) )错能力与最小码距错能力与最小码距d d0 0的关系的关系 任一任一（n n，k k）分组码，若要

19、在码字内能：分组码，若要在码字内能： 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 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组23 1 A1 d0 e A2 （a） A1 A2 d0 et （c） A1 d0 t A2 （b） A2 t 1 1 copyrig

20、ht 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组24 例例9-1一个码集，只有两个许用码：一个码集，只有两个许用码：00000000、11111111， 试求其纠、检错能力和编码效率。试求其纠、检错能力和编码效率。 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组25 解：解：根据码距的定义，则该码集根据码距的定义，则该码集d0 = 4， 1/ 用于检错，用于检错，e d d0 0 1=3，即可检，即可检3个错误；个错误； 2/ 用于纠错，用于纠错，t (d d0 01)/2=3/2，取整，即可纠，取整，即可纠1个错误；个错误； 3/

21、同时用于纠、检错，同时用于纠、检错， d d0 0 e+t+1 e+t+1 （e et t） 取：取：e=2，t=1，则可满足上式，即可检，则可满足上式，即可检2个错误个错误 同时纠一个错；同时纠一个错； R=k/n=1/4 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组26 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组27 5. 差错控制编码的效用差错控制编码的效用 假设在随机信道中，发送假设在随机信道中，发送“0”0”和和“1”1”的的 错误概率相等，都等于错误概率相等，都等于p p，且，且p p1 1，在码长，

22、在码长 为为n n的码组中，发生的码组中，发生r r个错误的概率为：个错误的概率为： ! ( )(1) !()! rrn rr nn n P rC ppp r nr copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组28 ! ( )(1) !()! rrn rr nn n P rC ppp r nr 例如：当例如：当n=7，p=10-时，则有：时，则有： 3 7 1077) 1 ( pP 522 7 101 . 221 )!27( ! 2 ! 7 )2( ppP 833 7 105 . 335 )!37( ! 3 ! 7 ) 3( ppP 由此可见，即使仅能纠

23、正由此可见，即使仅能纠正1-21-2个错误，也可使误码个错误，也可使误码 率下降几个数量级。所以差错控制编码具有较大的实率下降几个数量级。所以差错控制编码具有较大的实 际应用价值。际应用价值。 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组29 6. 6. 有扰信道编码定理（有扰信道编码定理（ShannonShannon第二定理）第二定理） 对于给定的有扰信道，若信道容量为对于给定的有扰信道，若信道容量为C C，只，只 要发送端以低于要发送端以低于C C的信息速率的信息速率R Rb b发送信息，则发送信息，则 一定存在一种编码方法一定存在一种编码方法，使得

24、译码错误概率，使得译码错误概率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随指数下降。随指数下降。 其中其中 C=Blog2(1+S/N)（bit/s） 2.在在C和和Rb一定

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

26、-1 编码后 Pe A B 信噪比 (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为为编码增益编码增益。 上面两种情况

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

28、速率后由C C 点升到点升到E E点。但加用纠点。但加用纠 错编码后，仍可将误码错编码后，仍可将误码 率降到率降到D D点。这时付出点。这时付出 的代价仍是带宽增大。的代价仍是带宽增大。 10-6 10-5 10-4 10-3 10-2 10-1 编码后 Pe C D E 信噪比 (dB) copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组34 9-3 9-3 常用的简单编码常用的简单编码 1 1、奇偶监督码：、奇偶监督码： k=n-1,r=1k=n-1,r=1的线性码。的线性码。 特点：特点： 码组中的码组中的1 1个数是奇数（奇监督码）个数是奇数（奇监督码

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

30、 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 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 偶监督码编码器 a4 a3 a2 a1 + 信息组信息组a0 a1 a2 a3 a4 码字码字

31、 12340 aaaaa copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组37 01234 bbbbbs b3b0b1b2b4 + 接收码组 B S 检错信号 有错 无错 1 0 偶监督码的检错偶监督码的检错 电路电路 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组38 例例9-29-2：一数据序列：一数据序列： 1110011100 1011110111 0110101101 1000110001 1010110101 试对其进行（试对其进行（6 6，5 5）偶校验编码，写出码序列）偶校验编码，写出码序列 并分析其抗干

32、扰能力并分析其抗干扰能力 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组39 一数据序列一数据序列： 1110011100 1011110111 0110101101 1000110001 1010110101 试对其进行（试对其进行（6 6，5 5）偶校验编码，写出码序列）偶校验编码，写出码序列 并分析其抗干扰能力并分析其抗干扰能力 解：解： （6 6，5 5）, ,将数据序列每将数据序列每5 5码元分组，码元分组， 123450 aaaaaa并作：并作： 的运算的运算 可得出编码数据序列：可得出编码数据序列： 111001110011101111011

33、10001101011011110001100010010101101011 1 只能检测出奇数个错误，不能发现偶数个错误，只能检测出奇数个错误，不能发现偶数个错误， 也不能纠错。也不能纠错。 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组40 2 2、水平垂直奇偶校验、水平垂直奇偶校验码：码： 又称行列监督码或二维奇偶监督码。又称行列监督码或二维奇偶监督码。 特点：特点： 对水平方向和垂直方向的码元同时实施奇偶监督。对水平方向和垂直方向的码元同时实施奇偶监督。 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1

34、 1 1 1 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 1 1 0 0 行行 列列 监监 督督 码码 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组41 适于监测突发错误： q逐行传输时，能检测长度b M+1的突发错误; q逐列传输时,能检测长度bL+1的突发错误； q还能纠正一些仅在一行中的单个错误。 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 1 1 1 0

35、 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 1 1 0 0 L5，M10的行列监督码的行列监督码 其中其中M为列数，为列数，L为行数为行数 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组42 3 3、恒比码：、恒比码： 又称等重码或定又称等重码或定1 1码。码。 特点：特点： 码组中码组中0 0，1 1的个数保持不变。的个数保持不变。 若码长为若码长为n n，码重为，码重为w w，则此码的码字个数，则此码的码字个数 为：为：C Cn nw w，禁用码字个数为：，禁用码字个数为：2 2n n - C - Cn n

36、w w 码字的个数码字的个数C C5 53 3 =10 =10 检错能力较强，可检出检错能力较强，可检出所有奇数所有奇数和和部分偶数部分偶数错误。错误。 检错能力较强，可检出所有奇数和部分偶数错误。检错能力较强，可检出所有奇数和部分偶数错误。 适用于传输电报或其他键盘设备产生的字母或符适用于传输电报或其他键盘设备产生的字母或符 号，但不适合信源发出的是二进制随机数字序列号，但不适合信源发出的是二进制随机数字序列 的场合。的场合。 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组43 数字数字码码 字字 0 0 1 1 2 2 3 3 4 4 5 5 6 6

37、7 7 8 8 9 9 0110101101 0101101011 1100111001 1011010110 1101011010 0011100111 1010110101 1110011100 0111001110 1001110011 3:2 恒比码恒比码 如：我国的电报，每如：我国的电报，每 个汉字用四个个汉字用四个1010进制进制 数表示，每位数表示，每位1010进制进制 数就采用数就采用 3 3：2 2 恒比恒比 码构成的码构成的5 5位码组来表位码组来表 示。示。 码字的个数码字的个数C C5 53 3 =10 =10 copyright 信息科学与技术学院通信原理教研组信息科

38、学与技术学院通信原理教研组44 作业： 4 4、正反码：、正反码： 简单的可纠错编码，信元数等于监督元数简单的可纠错编码，信元数等于监督元数 特点：特点： 信息位中，有奇数个信息位中，有奇数个1 1时，监督位重复信息位；时，监督位重复信息位； 信息位中，有偶数个信息位中，有偶数个1 1时，监督位取信息位的反码；时，监督位取信息位的反码； 可纠一位、检测所有两位错和部分两位以上的错误。可纠一位、检测所有两位错和部分两位以上的错误。 例：例： 11001 1100111001 110011100111001 10001 1000110001 100010111001110 (n,k) (n,k)

39、其中其中k=n/2 k=n/2 编码效率：编码效率： R=k/n=1/2R=k/n=1/2 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组45 9.4 线性分组码 9.4.1 9.4.1 基本概念基本概念 可用可用线性方程组线性方程组表述码的规律性的分表述码的规律性的分 组码称为线性分组码。线性码建立在代数组码称为线性分组码。线性码建立在代数 学群论基础上，线性码各许用码的集合构学群论基础上，线性码各许用码的集合构 成代数学中的群，因此，又称为群码。成代数学中的群，因此，又称为群码。 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通

40、信原理教研组46 1. 1. 含有全零码字。含有全零码字。 2.2.任意两个许用码字之和仍是一个许用码字。任意两个许用码字之和仍是一个许用码字。 （封闭性封闭性） 3.3.最小码距最小码距d d0 0等于非零码字的最小重量即等于非零码字的最小重量即d d0 0=W=Wmin min （由此性质可以方便的确定出线性分组码的最（由此性质可以方便的确定出线性分组码的最 小码距，进而明确其纠错能力。）小码距，进而明确其纠错能力。） 在群中只有一种运算，就是模在群中只有一种运算，就是模2 2 和。和。 线性分组码的性质线性分组码的性质： copyright 信息科学与技术学院通信原理教研组信息科学与技术

41、学院通信原理教研组47 奇偶监督码是一种最简单的线性码，我们曾经作了奇偶监督码是一种最简单的线性码，我们曾经作了 偶校验的例子。偶校验的例子。 0 021 aaa nn 称为称为监督监督方程方程。 接收时，为了检测传输时是否有错，还要做同样的计接收时，为了检测传输时是否有错，还要做同样的计 算：算： 01234 bbbbbs 有错 无错 1 0 s 这里这里S S称为称为校正子，校正子，上式也称上式也称伴随式伴随式。 奇偶监督码中只有一位监督码，因此只能表示有否错误。奇偶监督码中只有一位监督码，因此只能表示有否错误。 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原

42、理教研组48 当监督位增加，则监督方程增加，校正子增加。当监督位增加，则监督方程增加，校正子增加。 r r位监督码除了用全位监督码除了用全“0”0”表示无错外，可表示表示无错外，可表示 r 21 种错误图样。种错误图样。(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种状态，但只

43、取种状态，但只取2k 种为许种为许 用状态，其他为禁用，用状态，其他为禁用， (n,k)码可检测的错误图样数为码可检测的错误图样数为 2n-2k 2n-k -1=2r-1 不可检测的错误图样数为不可检测的错误图样数为2k-1 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组49 1 n c 2 n c t n c t i i n c 1 2 n-k-1 + + = 对于能纠正对于能纠正 t 个错误的线性分组码个错误的线性分组码(n,k)应满足：应满足： i n c 是错是错 i 位的个数。位的个数。 如果满足如果满足 ，则有可能构造出纠正一位或一位，则有可能

44、构造出纠正一位或一位 以上的线性码以上的线性码。 i=1时，时， 1 n n c 即对于码组长度为即对于码组长度为n n，信息码元，信息码元k k位，监督元位，监督元r r， n r 12 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组50 思考：思考： 例例9-39-3设设(n(n，k)k)中，中，k=4k=4，要求能纠一位错，取，要求能纠一位错，取r=r=？ copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组51 解：解： (n(n，k)k)线性分组码，线性分组码，k=4k=4，要求能纠一位错，要求能纠一位错， 现取现

45、取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 3 21 r n 恰好满足恰好满足 , ,故可纠一位错。故可纠一位错。 copyright 信息科学与技术学院通信原理教研组信

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

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

48、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 0 0 1 0 0 0 1 0 1 1 1

49、 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 0 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组54 9.4.2 监督矩阵 0 0 0 1001101 0101011 0010111 0 1 2 3

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

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

52、与技术学院通信原理教研组信息科学与技术学院通信原理教研组57 设监督方程设监督方程A A1 1、A A2 2均为线性码集合中的许用码均为线性码集合中的许用码 组，因此有组，因此有 令两许用码组相加令两许用码组相加 A A1 1+A+A2 2带入监督方程，有：带入监督方程，有： 0 2 T HA0 1 T HA 因此，因此， A A1 1+A+A2 2亦为许用码组。亦为许用码组。 0)( 2121 TTT HAHAHAA copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组58 9.4.3 生成矩阵 当给出信息组后，如何方便迅速地求出整个当给出信息组后，如何方便迅

53、速地求出整个 编码码组，即如何生成编码矢量编码码组，即如何生成编码矢量？ C C2 2=C=C6 6+C+C5 5+C+C4 4 C C1 1=C=C6 6+C+C5 5+C+C3 3 C C0 0=C=C6 6+C+C4 4+C+C3 3 由监督元与信息元之间的关系：由监督元与信息元之间的关系： 3 4 5 6 0 1 2 1101 1011 0111 C C C C C C C T PCCCCCCC 3456012 或者可以写成：或者可以写成： copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组59 QCCCCCCC 3456012 令令 QP T 则有：

54、则有： 给给Q Q的左边，加一个的左边，加一个k kk k阶的单位矩阵，则构成：阶的单位矩阵，则构成： G=IG=Ik k Q Q称为称为生成矩阵生成矩阵，且为典型形式。典型，且为典型形式。典型 G G矩阵矩阵 行数行数- - 信息元的个数信息元的个数k k 列数列数- - 码组长度码组长度 n n 每行本身就是一个许用码组每行本身就是一个许用码组 TT HG00 T GH于是有：于是有： 矩阵和非典型矩阵之间可以转换。矩阵和非典型矩阵之间可以转换。 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组60 码字的前面码字的前面 k k 位为信息位，后面位为信息

55、位，后面 位为位为监督位监督位 一般情况，定义线性分组码的码字有如下形式：一般情况，定义线性分组码的码字有如下形式： 信息码元信息码元 监督位监督位信息信息位位 编码编码 码字码字 k kn k n 系统形式的线性分组码系统形式的线性分组码 1210 () nnn kn k Cccccc 120 () kk Mmmm 02121 mmmccc kkknnn kn 0 M G编码编码 k kn copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组61 设信息组 1000111 0100110 0010101 0001011 G 生成矩阵生成矩阵 编码码组编码码组

56、CM G 6543 Mcccc copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组62 . )2阶矩阵，各行线性无关为nkG 1）由G和信息组即可产生全部码字. 111 110 101 011 T QP 通过典型生成矩阵产生的一定是系统码。通过典型生成矩阵产生的一定是系统码。 k 1000 0100 I 0010 0001 G称为典型生成矩阵。 3) k GI Q copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组63 011010 101001 110100 G （1）试确定试确定(n,k)(n,k)，并求，并求H H ；

57、(2) (2) 写出监督元与信息元的关系式及写出监督元与信息元的关系式及 该（该（n,kn,k）码的全部码字；）码的全部码字； (3) (3) 确定最小码距及检错能力。确定最小码距及检错能力。 例9-4设已知设已知 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组64 110100 011010 101001 解：求H，需确定P， QP T 应将已知的那个G转换成典型形式，求出Q， 再利用 求出G。 011010 101001 110100 G 011010 110100 101001 H=P Ir= 100101 010110 001011 r T IQ

58、copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组65 (2) 0 T HC5 4 3 2 1 0 110100 0110100 101001 c c c c c c 设C= 012345 cccccc 于是有： 110100 011010 101001 345 cccGMC 监督元与信息元的关系式监督元与信息元的关系式 copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组66 用三位二进制数的所有用三位二进制数的所有8种状态带入，可得到所有码字如右表种状态带入，可得到所有码字如右表。 序号 码 字 0 0 0 0 0 0 0

59、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等于非零码等于非零码 字的最小重量即字的最小重量即 d0 0=wmin min copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组67 9.4.4 校正子S 发送端经过编

60、码后给出：发送端经过编码后给出： 0121 ccccc nn 接收端收到的码组为：接收端收到的码组为： 0121 rrrrR nn 两者的差记为：两者的差记为： 0121 eeeeCRE nn ii ii i cr cr e 1 0 表示第表示第 i 位无错位无错 表示第表示第 i 位有错位有错 E称为错误图样。共有称为错误图样。共有2n个错误图样。个错误图样。 当当 E为全零错误图样时，为全零错误图样时，R=C 没有传输错误没有传输错误; copyright 信息科学与技术学院通信原理教研组信息科学与技术学院通信原理教研组68 TT HR0 可利用可利用E检出或纠正错误；检出或纠正错误； T