信息论 基础理论与应用第三版(傅祖芸)-第9章-讲义

1、第第9 9章章 信道的纠错编码信道的纠错编码 差错控制的基本形式差错控制的基本形式 纠错码分类及其基本概念纠错码分类及其基本概念 线性分组码线性分组码 * *循环码循环码 * *卷积码卷积码 香农第二定理指出，只要信息传输率小于信道容量，通香农第二定理指出，只要信息传输率小于信道容量，通 过适当的编译码方法，就能以任意小的错误概率传输信息。过适当的编译码方法，就能以任意小的错误概率传输信息。 但从实际工程看，并没有指出具体的编译码方法。但从实际工程看，并没有指出具体的编译码方法。 这正是这正是信道纠错编码信道纠错编码要解决的问题。要解决的问题。 香农第二定理指出，在信道中以信息传输率香农第二定

2、理指出，在信道中以信息传输率R R小于信道容量小于信道容量 条件下，使差错概率尽可能小的条件下，使差错概率尽可能小的信道编译码原则信道编译码原则是：是： 编码原则编码原则： 在在n n次扩展信道输入符号序列中选取次扩展信道输入符号序列中选取MM个作为码字构成一组个作为码字构成一组 码码C C，并尽量使选取的，并尽量使选取的MM个码字中两两不相同码字的汉明距离尽个码字中两两不相同码字的汉明距离尽 可能地大；可能地大； 译码原则译码原则： 当收到符号序列后，翻译成与之汉明距离最近的码字（最大当收到符号序列后，翻译成与之汉明距离最近的码字（最大 似然准则）。似然准则）。 几十年来，基于香农编码定理和

3、以上编译码原则，科技工作几十年来，基于香农编码定理和以上编译码原则，科技工作 者们开发了很多具有者们开发了很多具有纠错能力的信道编码纠错能力的信道编码，如线性分组码、循环，如线性分组码、循环 码、码、BCHBCH码、卷积码、码、卷积码、TCMTCM码、码、TuoboTuobo码等，在通信系统中得到码等，在通信系统中得到 了广泛应用。了广泛应用。 9.1 9.1 差错控制的基本形式差错控制的基本形式 现代数字通信系统中，利用检错和纠错的编码技术，现代数字通信系统中，利用检错和纠错的编码技术， 使得信道编译码具备一定的差错控制能力。主要方式有：使得信道编译码具备一定的差错控制能力。主要方式有： 1

4、 1、前向纠错、前向纠错(FEC)(FEC)方式方式： 发送端信道编码器将信息码组编成具有一定发送端信道编码器将信息码组编成具有一定纠错能力纠错能力的码。的码。 接收端信道译码器对接收码字译码，若传输中产生的差错接收端信道译码器对接收码字译码，若传输中产生的差错 数目在码的纠错能力之内，译码器对差错进行数目在码的纠错能力之内，译码器对差错进行定位定位并加以并加以纠正纠正。 发送端发送端 接收接收端端 可检错纠错的码可检错纠错的码 FECFEC 检错、纠错检错、纠错 nFEC FEC 特点特点 单向控制，不需要反馈信道；时延小，实时性好。单向控制，不需要反馈信道；时延小，实时性好。 为适应较差信

5、道，冗余码元多，编码效率低，译码设备复杂。为适应较差信道，冗余码元多，编码效率低，译码设备复杂。 有一定的纠错范围限制。有一定的纠错范围限制。 适用于容错能力强的语音、图像传输；不适合容错能力弱的适用于容错能力强的语音、图像传输；不适合容错能力弱的 数据通信网。数据通信网。 2 2、反馈重发、反馈重发(ARQ)(ARQ)方式（检错重发方式）：方式（检错重发方式）： 发送端发送端发送的是能够发送的是能够发现（检测）发现（检测）错误的码；错误的码； 接收端接收端收到信道传输来的码后，译码器依据该码编码规则，收到信道传输来的码后，译码器依据该码编码规则， 判决出当前码字传输是否出错，并把判决出当前码

6、字传输是否出错，并把判决结果判决结果（应答信号）反（应答信号）反 馈至发送端。发送端把接收端认为有错的信息馈至发送端。发送端把接收端认为有错的信息重新发出重新发出，直到，直到 接收端认为正确为止。接收端认为正确为止。 发送端发送端 接收端接收端 可检错的码可检错的码 ARQARQ 应答信号应答信号 检错、不纠错检错、不纠错 nARQARQ特点特点 需要双向控制和反馈信道。需要双向控制和反馈信道。 系统的控制设备和存储设备复杂，但编译码设备较简单。系统的控制设备和存储设备复杂，但编译码设备较简单。 接收端检错能力、系统纠错能力强，可大大降低系统误码率。接收端检错能力、系统纠错能力强，可大大降低系

7、统误码率。 具有自适应性。但若重发频繁，将使效率降低，甚至系统阻塞，具有自适应性。但若重发频繁，将使效率降低，甚至系统阻塞， 使得连续性和实时性变差。使得连续性和实时性变差。 在短波、有线干扰情况复杂的信道，在计算机网络、分组在短波、有线干扰情况复杂的信道，在计算机网络、分组 交换网、卫星通信、移动通信中广泛应用。交换网、卫星通信、移动通信中广泛应用。 3 3、混合纠错、混合纠错(HEC)(HEC)方式：方式： n 前向纠错前向纠错FEC+FEC+反馈重发反馈重发ARQARQ 发送端发送的是兼有发送端发送的是兼有检错和纠错能力检错和纠错能力的码；接收端收到码的码；接收端收到码 字后，首先检测错

8、误情况。当差错在码的纠错能力范围内，就字后，首先检测错误情况。当差错在码的纠错能力范围内，就 自动纠错；当差错很多已经超出了纠错能力，但能够检测到错自动纠错；当差错很多已经超出了纠错能力，但能够检测到错 误，接收端就通过反馈信道，请求重发。误，接收端就通过反馈信道，请求重发。 发送端发送端 接收端接收端 可检错和纠错的码可检错和纠错的码 HECHEC 应答信号应答信号 检错、纠错检错、纠错 nHECHEC的特点的特点 总体性能介于总体性能介于FECFEC和和ARQARQ之间，误码率低，但需要反馈信道。之间，误码率低，但需要反馈信道。 实时性和连续性好。实时性和连续性好。 设备不太复杂，应用广泛

9、。设备不太复杂，应用广泛。 4 4、信息反馈、信息反馈(IRQ)(IRQ)方式方式( (回程校验方式回程校验方式) ): : 接收端接收端收到信道传输来的码后，全部由反馈信道发回发送端；收到信道传输来的码后，全部由反馈信道发回发送端； 发送端发送端将发送的码与反馈回的码进行比较，发现错误后，把出将发送的码与反馈回的码进行比较，发现错误后，把出 错的码再次重发，直到接收端认为正确为止。错的码再次重发，直到接收端认为正确为止。 发送端发送端 接收端接收端 消息（不编码）消息（不编码） IRQIRQ 消息消息 不检错、纠错不检错、纠错 nIRQIRQ特点：特点： 需要双向控制，需要反馈信道。需要双向

10、控制，需要反馈信道。 系统的控制设备和存储设备相对复杂。系统的控制设备和存储设备相对复杂。 无需编译码设备，接收端不具备检、纠错能力强，整体系统纠无需编译码设备，接收端不具备检、纠错能力强，整体系统纠 错能力强，可大大降低整个系统误码率。错能力强，可大大降低整个系统误码率。 具有自适应性，但若重发频繁，将使传输效率降低，甚至系统具有自适应性，但若重发频繁，将使传输效率降低，甚至系统 阻塞，使得连续性和实时性变差。阻塞，使得连续性和实时性变差。 5 5、检错删除：、检错删除： 接收端接收端发现错码后，立即将其删除。发现错码后，立即将其删除。 适用在发送码元中有大量多余度，删除部分接收码元不影响应

11、适用在发送码元中有大量多余度，删除部分接收码元不影响应 用之处。用之处。 6 6、差错隐藏：、差错隐藏： 在某些应用领域，如音乐、语音、图像、视频等领域，在某些应用领域，如音乐、语音、图像、视频等领域， 有差错或损失的部分数据对人的主观感受影响不大，此时，可有差错或损失的部分数据对人的主观感受影响不大，此时，可 根据已接收的数据采用内插或外推的技术，得到满足应用的输根据已接收的数据采用内插或外推的技术，得到满足应用的输 出数据。出数据。 9.2 9.2 纠错码分类纠错码分类 1 1、纠错码的分类：、纠错码的分类： n按纠正错误的类型分类：按纠正错误的类型分类： 纠随机差错码：纠随机差错码：无记

12、忆信道中，噪声随机独立地影响每个无记忆信道中，噪声随机独立地影响每个 码元，造成了随机差错；码元，造成了随机差错； 纠突发差错码：纠突发差错码：有记忆信道中，突发噪声可造成突发性的有记忆信道中，突发噪声可造成突发性的 成群差错（如太阳黑子、雷电等引起）成群差错（如太阳黑子、雷电等引起）。 纠混合差错码纠混合差错码 n按应用目的分类：按应用目的分类： 检错码检错码只能检测错误是否存在。只能检测错误是否存在。 纠错码纠错码能够检测错误，并能够自动纠正错误。能够检测错误，并能够自动纠正错误。 纠删码纠删码能够纠正删除（丢失）了的信息。能够纠正删除（丢失）了的信息。 n按码元取值分类：按码元取值分类：

13、 二元纠错码二元纠错码目前最常用模式目前最常用模式 多元纠错码多元纠错码 n按码的结构中对信息序列的处理方式分类：按码的结构中对信息序列的处理方式分类： 分组码（分组码（n,kn,k）将信息序列每将信息序列每k k位分组，再增加入位分组，再增加入r=n-r=n- k k 个冗余码元（校验元），校验元只由本组个冗余码元（校验元），校验元只由本组k k个信息元按个信息元按 照一定规律产生，与其他信息组无关。照一定规律产生，与其他信息组无关。 卷积码（卷积码（n,kn,k0 0,L ,L）将信息序列每将信息序列每 k k0 0 位分组，编码器输位分组，编码器输 出该段的出该段的r=n-kr=n-k0

14、 0个与本组和前个与本组和前L L组信息元相关的校验元，组信息元相关的校验元， 得到得到n n长的码字。长的码字。 n按码的数学结构中校验元与信息元关系分类：按码的数学结构中校验元与信息元关系分类： 线性码线性码线性关系，如线性方程组线性关系，如线性方程组 非线性码非线性码非线性关系非线性关系 n按码的是否具有循环性分类：按码的是否具有循环性分类： 循环码循环码分组码中任一码字的码元经过循环移位后，分组码中任一码字的码元经过循环移位后， 仍是本码中的码字。仍是本码中的码字。 非循环码非循环码至少有一个码字经循环移位后，不再是本至少有一个码字经循环移位后，不再是本 码中的码字。码中的码字。 n按

15、构造码的数学理论分类：按构造码的数学理论分类： 代数码代数码近世代数，比较完善，如线性分组码。近世代数，比较完善，如线性分组码。 几何码几何码投影几何学投影几何学 算术码算术码数论，高等算术数论，高等算术 组合码组合码排列组合，数论排列组合，数论 实际的码可能同时分别具备以上某些特征，比如：某一纠错码实际的码可能同时分别具备以上某些特征，比如：某一纠错码 可以同时是线性码、分组码、循环码、纠随机差错码、二元码、代可以同时是线性码、分组码、循环码、纠随机差错码、二元码、代 数码等。数码等。 9.3 9.3 纠错码的概念及其纠错能力纠错码的概念及其纠错能力 信息序列信息序列码字序列码字序列 接收序

16、列接收序列 译码后信息序列译码后信息序列 噪声源噪声源 E E 错误图样错误图样 对编码器的输入信息序列，每对编码器的输入信息序列，每k k个信息符号分成个信息符号分成信息组信息组： m m= =（m mk-1k-1, ,m mk-2k-2,m m0 0），），m mi i为为信息元信息元（i=0,1,k-1i=0,1,k-1）。）。 （在（在q q元数字通信系统中，共有元数字通信系统中，共有 种信息组。）种信息组。） 码字码字： 为了纠错，编码器按一定规则增加产生为了纠错，编码器按一定规则增加产生r r个多余符个多余符 号，形成长度为号，形成长度为 n=k+r n=k+r 的序列的序列： C

17、=(cC=(cn-1n-1,c ,cn-2n-2,c,c0 0), ), c ci i为为码元码元（i=0,1,n-1i=0,1,n-1） 校验元校验元：增加的增加的 r=n-k r=n-k 位码元位码元。 n n：码长；：码长；k k：信息组长度；：信息组长度； r r：校验元的位长。：校验元的位长。 k q n1 1、信息元、校验元、码字：、信息元、校验元、码字： n码码C C中的码字个数（中的码字个数（k k为信息位数）：为信息位数）： n（n,kn,k）分组码：）分组码：编码器输出为编码器输出为 个码字组成的序列；个码字组成的序列； 许用码字许用码字： 种码符号序列中，取出种码符号序列

18、中，取出 个作为分组码个作为分组码 的码字。的码字。 禁用码字禁用码字：其余：其余 种码符号序列。种码符号序列。 n卷积码（卷积码（n,kn,k0 0,L ,L）: :编码器输出的校验元不仅由本组信息元有关，编码器输出的校验元不仅由本组信息元有关， 也与其前面若干段的信息组所确定。也与其前面若干段的信息组所确定。 k q k q n q k q kn qq k k个信息位个信息位r r个监督位个监督位 a an n-1 -1a an n-2 -2. .a ar ra ar r-1 -1a an n-2 -2. .a a0 0 t t 码长码长 n n = = k k + + r r 分组码的结

19、构分组码的结构 n2 2、码字的汉明重量：、码字的汉明重量： 汉明距离汉明距离D(CD(C1 1,C,C2 2) )：对应位置上不同码元的个数。：对应位置上不同码元的个数。 码的最小距离码的最小距离：d dminmin, d(C), d(C) 汉明重量（汉明势）汉明重量（汉明势）：码字中非零码元的个数：码字中非零码元的个数 W(C)W(C)。 对对2 2元码，汉明重量为码字中的元码，汉明重量为码字中的“1”1”的个数。因此，二的个数。因此，二 元码字的汉明重量和汉明距离为：元码字的汉明重量和汉明距离为： 1 , 0)( 1 0 i n i i ccCW )(),( jiji CCWCCD 模模

20、2 2加，若对应位不同加，若对应位不同 则为则为1 1；相同则为；相同则为0 0。 其重量即为不相同的其重量即为不相同的 总位数，也就是两个总位数，也就是两个 码字的汉明距离。码字的汉明距离。 n3 3、错误图样：、错误图样： 码字序列通过信道传输送入译码器之前，由于信道的码字序列通过信道传输送入译码器之前，由于信道的 噪声干扰，使得接收序列中某些码元发生差错，可用噪声干扰，使得接收序列中某些码元发生差错，可用错误错误 图样图样（差错图样差错图样）定量描述：）定量描述： E=(eE=(en-1n-1e en-2n-2ee1 1e e0 0)=C)=CR R 二元数字通信系统中，码元传输错误图样

21、：二元数字通信系统中，码元传输错误图样： E=(eE=(en-1n-1e en-2n-2ee1 1e e0 0), e), ei i =0,1 ,i=0,1,n-1=0,1 ,i=0,1,n-1 若若 e ei i =0 =0 ， 第第i i位码元无差错；位码元无差错； 若若 e ei i =1 =1 ， 第第i i位码元发生差错；位码元发生差错； 差错关系差错关系： 接收序列接收序列 = = 许用码字许用码字 + + 错误图样错误图样 R=(rR=(rn-1n-1r rn-2n-2rr1 1r r0 0), r), ri i =0,1 ,i=0,1,n-1=0,1 ,i=0,1,n-1 接收

22、序列长度接收序列长度 = = 码字长度码字长度 = = 错误图样长度错误图样长度 = n= n 差错类型：差错类型： n随机差错随机差错是相互独立的、不相关，存在这种差错是相互独立的、不相关，存在这种差错 的信道是无记忆信道或随机信道；的信道是无记忆信道或随机信道； n突发差错突发差错指成串出现的错误指成串出现的错误, ,错误与错误间有相关错误与错误间有相关 性性, ,一个差错往往要影响到后面一串码元。一个差错往往要影响到后面一串码元。 RCE ERC ECR , 例例 发送码字发送码字 C= 010110111, C= 010110111, 接收序列接收序列 R= 001110011,R=

23、001110011, 错误图样错误图样 E=C+R= 011000100E=C+R= 011000100 若为若为随机差错随机差错，错误码元为：，错误码元为： 2 2，3 3，7 7，错误数量，错误数量 =W(E)=3=W(E)=3； 若为若为突发差错突发差错，错误码元串长度为：，错误码元串长度为：6 6； 出错范围：从错误图样出错范围：从错误图样E E中的第一个中的第一个1 1到最后一个到最后一个1 1， 其其 错误串中的错误串中的0 0表示该位码元未发生错误。表示该位码元未发生错误。 nBSCBSC（二元无记忆对称信道）的错误图样的出现概率（二元无记忆对称信道）的错误图样的出现概率 设设p

24、 p为错误概率为错误概率(1),(1),则则n n次无记忆扩展信道中，次无记忆扩展信道中，随机差错随机差错 的某错误图样的某错误图样E E的出现概率为：的出现概率为： )( )( )( EW EWn ppEP 0 0位差错（全对）：位差错（全对）： W(EW(E0 0)=0)=0， 1 1位随机差错：位随机差错： W(EW(E1 1)=1, )=1, 2 2位随机差错：位随机差错： W(EW(E2 2)=2,)=2, e e位随机差错：位随机差错： W(EW(Ee e)=e,)=e, n n位差错（全错）位差错（全错） W(EW(En n)=n,)=n, 0 n C 1 n C 2 n C e

25、 n C n n C ppEP n 1 1) ( n pEP)( 0 2 2 2) (ppEP n e en e ppEP )( n n pEP)( 差错图样数差错图样数概率概率 错误图样的错误图样的总数总数： nn nnnnn CCCCC2. e210 n nnn pppppp . 2 21 )(.)(.)()()( 210ne EPEPEPEPEP 发生发生多位错误的概率多位错误的概率小于小于较少位数较少位数随机错误的概率。随机错误的概率。 因此，因此，无记忆信道无记忆信道中，一般优先纠正较少位数的随机错中，一般优先纠正较少位数的随机错 误，如误，如1-21-2位，此时的误码率就可下降几个

26、数量级。位，此时的误码率就可下降几个数量级。 错误图样出现的错误图样出现的概率关系概率关系（p1p1）：）： n4 4、分组码的纠错能力与码最小距离的关系、分组码的纠错能力与码最小距离的关系 一般地，分组码的码间最小距离一般地，分组码的码间最小距离 dmin dmin 越大，意味着任越大，意味着任 意码字间的差别越大，则码的检、纠错能力越强。意码字间的差别越大，则码的检、纠错能力越强。 检错能力检错能力： 如果一个分组码能检出如果一个分组码能检出总位数总位数e e 个码元个码元的任何错误的任何错误 图样，称码的图样，称码的检错能力为检错能力为 e e。 纠错能力纠错能力： 如果分组码能纠正如果

27、分组码能纠正总位数总位数t t 个码元个码元的任意错误图样，的任意错误图样， 称码的称码的纠错能力为纠错能力为 t t。 例例 重复码（重复码（3 3，1 1）为：（）为：（000000，111111），最小码间距为），最小码间距为3 3。 两个码字在传输后发生两个码字在传输后发生1 1位错误的接收序列形成两个互不相交位错误的接收序列形成两个互不相交 的子集，按照的子集，按照最小距离译码准则最小距离译码准则，就能纠正，就能纠正1 1位随机错误。若发位随机错误。若发 生生2-32-3位错误，则接收序列进入另一个子集内，无法纠正。位错误，则接收序列进入另一个子集内，无法纠正。 (0,0,0) (0

28、,0,1)(1,0,1) (1,0,0) (1,1,0) (0,1,0) (0,1,1) (1,1,1) a2 a0 a1 n定理定理：对于一个（：对于一个（n,kn,k）分组码）分组码C C，最小距离为，最小距离为d dmin min，则： ，则： 若能检测（发现）若能检测（发现）e e个随机错误，则要求个随机错误，则要求 d dminmin e+1e+1 ; ; 或：可检测出任意小于等于或：可检测出任意小于等于 e = d e = dmin min 1 1个随机差错；个随机差错； 若能纠正若能纠正 t t 个随机错误，则要求个随机错误，则要求 d dminmin 2t+12t+1 ; ;

29、或：可纠正任意小于等于或：可纠正任意小于等于 t= INT (d t= INT (dminmin-1) / 2-1) / 2个随机差错；个随机差错； 若能纠正若能纠正 t t 个随机错误，同时能检测个随机错误，同时能检测e t e t 个随机错误，则个随机错误，则 要求：要求： d dminmin t+e+1t+e+1 。 设设V,UV,U为距离最小的两个许用码字。若某码字传输发生错误，按为距离最小的两个许用码字。若某码字传输发生错误，按 最小距离准则译码，为了检测最小距离准则译码，为了检测 R=U+ER=U+E： 须须d dminmin e+1 e+1，否则，会发生码字译码混淆，如，否则，会

30、发生码字译码混淆，如 R+E =V R+E =V 。 e VU dmin dmin=4,码距和检错能力关系示意图 t t VU d min 图 dmin=5,码距和纠错能力关系示意图 设设V,UV,U为距离最小的两个许用码字。若某码字传输发生错误，按为距离最小的两个许用码字。若某码字传输发生错误，按 最小距离准则译码最小距离准则译码. . 若若 R=V+ER=V+E，WW（E E）= t= t，则若，则若 dmin 2t+1 , dmin 2t+1 , 则可能译码为则可能译码为 U U。 错误！错误！ 当当 dmin 2t+1dmin 2t+1，D D（R R，V V） D k k) ) 码字

31、，其中码字，其中 ( (n nk k) ) 个附加码元是由信息码个附加码元是由信息码 元的元的线性运算线性运算产生的。产生的。 n对于二元码，信息码组长对于二元码，信息码组长 k k 位，有位，有 2 2k k 个不同的信息码组，则有个不同的信息码组，则有 2 2k k 个个 码字与它们一一对应。码字与它们一一对应。 2 2、 一致监督（校验）方程一致监督（校验）方程 n编码方法：已知信息码组编码方法：已知信息码组k k位信息位，按预定规则生成位信息位，按预定规则生成 r r 个监督个监督 （校验）码元，与信息位一起构成码字。（校验）码元，与信息位一起构成码字。 n要求：每个监督元是其中某些信

32、息元的运算结果。要求：每个监督元是其中某些信息元的运算结果。 （以下仅讨论二元码）（以下仅讨论二元码） 例例：k k=3, =3, r r=4=4，构成，构成 (7,3) (7,3) 线性分组码线性分组码。设码字为。设码字为 ( (C C6 6, ,C C5 5, ,C C4 4, ,C C3 3, ,C C2 2, ,C C1 1, ,C C0 0) ) 其中，其中，C C6 6, ,C C5 5, ,C C4 4为信息元，为信息元，C C3 3, ,C C2 2, ,C C1 1, ,C C0 0为监督元，码元取为监督元，码元取0 0或或1 1。 监督元可按下面方程组计算监督元可按下面方程

33、组计算 364 2654 165 054 (6.2.1) CCC CCCC CCC CCC n一致监督（校验）方程一致监督（校验）方程 由确定信息元得到监督元规则的一组方程。由于所有码字都按由确定信息元得到监督元规则的一组方程。由于所有码字都按 同一规则同一规则确定，又称为一致监督（校验）方程。确定，又称为一致监督（校验）方程。 n线性分组码线性分组码 若一致监督方程是若一致监督方程是线性线性的，监督元和信息元之间是线性运算关的，监督元和信息元之间是线性运算关 系，所以由监督方程所确定的分组码是系，所以由监督方程所确定的分组码是线性分组码线性分组码。 364 2654 165 054 CCC

34、CCCC CCC CCC 信息组信息组对应码字对应码字 0 0 00 0 00 0 0 0 0 0 00 0 0 0 0 0 0 0 0 10 0 10 0 1 1 1 0 10 0 1 1 1 0 1 0 1 00 1 00 1 0 0 1 1 10 1 0 0 1 1 1 0 1 10 1 10 1 1 1 0 1 00 1 1 1 0 1 0 1 0 01 0 01 0 0 1 1 1 01 0 0 1 1 1 0 1 0 11 0 11 0 1 0 0 1 11 0 1 0 0 1 1 1 1 01 1 01 1 0 1 0 0 11 1 0 1 0 0 1 1 1 11 1 11 1

35、 1 0 1 0 01 1 1 0 1 0 0 00000 00000 0000 00000 045 156 2456 346 CCC CCC CCCC CCC 前例前例 3 3、 一致监督（校验）矩阵一致监督（校验）矩阵 为了运算方便，为了运算方便，可可将监督方程写将监督方程写 成矩阵形式。成矩阵形式。 前例前例： 6 5 4 3 2 1 0 6543210 10110000 11101000 11000100 01100010 C 00000 1011000 1110100 H 1100010 0110001 C C C C C C C CCCCCCC 令 0 0 T TT CH HC o

36、r 00000 00000 0000 00000 045 156 2456 346 CCC CCC CCCC CCC 推广：推广：一般情况，对一般情况，对 ( (n n, ,k k) ) 线性分组码，每个码字中的线性分组码，每个码字中的 r r( (r r= =n nk k) ) 个个 监督元与信息元之间的关系可由如下监督元与信息元之间的关系可由如下r r * * n n 阶阶线性方程组确定：线性方程组确定： ) 6 . 2 . 6( 0 0 0 02211 02222121 01212111 ChChCh ChChCh ChChCh rnnrnr nnn nnn rnrr n n hhh h

37、hh hhh H . . . . 21 22121 11211 则：则： 00 TTT CHorHC 0 2 1 . c c c C n n T 令：令： . 0121 hhhhH nn n若用若用h hi i (i=n-1,n-2,1,0) (i=n-1,n-2,1,0) 表示表示H H矩阵中的矩阵中的列矢量列矢量，则，则H H可写为：可写为： 0. 00111111 hchchchc nnnn nH H矩阵的矩阵的每一行元素每一行元素是线性方程组中一个方程的系数，由它来是线性方程组中一个方程的系数，由它来 唯一确定每一个校验元。因此，唯一确定每一个校验元。因此，H H中中每一行必须是线性无

38、关每一行必须是线性无关的，的， 且必定有：且必定有：r =nr =nk k 行。行。 0 T CH 4 4、 生成矩阵生成矩阵 根据（根据（n,kn,k）线性分组码的一致监督方程出发，将）线性分组码的一致监督方程出发，将信息组信信息组信 息位息位与与生成的码字生成的码字之间的生成关系用矩阵来表示，就可得到之间的生成关系用矩阵来表示，就可得到生生 成矩阵。成矩阵。 例例 前例中，前例中， 364 2654 165 054 (6.2.1) CCC CCCC CCC CCC 041526 ,mcmcmc 010 121 0122 023 04 15 26 mmc mmc mmmc mmc mc mc

39、 mc 0 1 2 0 1 2 3 4 5 6 110 011 111 101 100 010 001 m m m c c c c c c c 1011100 1110010 0111001 0120123456 mmmccccccc 生成矩阵生成矩阵G G1 1 其各行为码字，互不相关。其各行为码字，互不相关。 其他码字为此三个码字的线性其他码字为此三个码字的线性 组合方式生成。组合方式生成。 信息组信息组对应码字对应码字 0 0 00 0 00 0 0 0 0 0 00 0 0 0 0 0 0 0 0 10 0 10 0 1 1 1 0 10 0 1 1 1 0 1 0 1 00 1 00

40、 1 0 0 1 1 10 1 0 0 1 1 1 0 1 10 1 10 1 1 1 0 1 00 1 1 1 0 1 0 1 0 01 0 01 0 0 1 1 1 01 0 0 1 1 1 0 1 0 11 0 11 0 1 0 0 1 11 0 1 0 0 1 1 1 1 01 1 01 1 0 1 0 0 11 1 0 1 0 0 1 1 1 11 1 11 1 1 0 1 0 01 1 1 0 1 0 0 n推广推广：对一般：对一般 ( (n n, ,k k) ) 线性分组码，设有一组线性分组码，设有一组k k个个线性独立的码字，线性独立的码字， 由此一组线性独立的码字以行向量构成

41、的矩阵，称为线性分组由此一组线性独立的码字以行向量构成的矩阵，称为线性分组 码的码的生成矩阵生成矩阵G G（k k* *n n阶）：阶）： kkkknknk nn nn gggggC gggggC gggggC ).( . ).( ).( 0121 2202122122 1101121111 0121 20212212 10112111 2 1 . . . . . kkknkn nn nn k gggg gggg gggg g g g G 满足：满足： )2,.,2 , 1 (,),( k iii iknCGmC码 nG G中每一行及其线性组合都是中每一行及其线性组合都是许用码字许用码字，故有

42、：，故有： 阶零矩阵。阶零矩阵。为为)(, 0 ,0 knkGH or HG T TT 0 线性分组码的所有码字都可由其生成矩阵或一致校验矩阵求线性分组码的所有码字都可由其生成矩阵或一致校验矩阵求 得。当已知得。当已知G G、H H中的一个，就可求另一个。中的一个，就可求另一个。 n系统码：系统码： 信息元以不变形式出现在码字的任意信息元以不变形式出现在码字的任意k k位上。位上。 n标准生成矩阵：标准生成矩阵： 生成矩阵能把信息元保留在各码字的生成矩阵能把信息元保留在各码字的最左边最左边k k位位上。上。 | )(knkk PIG | )(kn T knk IPH 0 T GH 因此，因此，

43、标准系统生成矩阵标准系统生成矩阵G G应满足如下形式：应满足如下形式： 其与其与H H矩阵之间的转换关系：矩阵之间的转换关系： 若非标准系统码，则若非标准系统码，则G G与与H H之间元素需要由方程组确定。之间元素需要由方程组确定。 ( (略略) )生成矩阵之间的关系生成矩阵之间的关系 对于二元（对于二元（n,kn,k）分组码，在）分组码，在2 2k k个码字中，个码字中，k k个个独立码字组独立码字组不不 止一个。对于同一码，选择不同的独立码字组构成生成矩阵止一个。对于同一码，选择不同的独立码字组构成生成矩阵G G也也 不相同。但经过若干次不相同。但经过若干次初等变换初等变换，可变成等价的，

44、可变成等价的标准生成矩阵标准生成矩阵。 例例 一个二元（一个二元（7 7，3 3）码）码, ,生成矩阵为：生成矩阵为： 0010111 1100101 0111001 2 G 信信 息息 组组 000001010011100101110111 码码 字字 00000001110100101001101001111001110011101000111011101001 生成的码字为：生成的码字为： 信信 息息 组组 000000001001010010011011100100101101110110111111 码码 字字 000000000000001111110100010010110100

45、1100110100100111011110010011101110011011101010100010011101110111011010011001 码字集合完全相同。码字集合完全相同。 但生成矩阵但生成矩阵G1G1、G2G2 选取了不同的独立码字构成。选取了不同的独立码字构成。 生成矩阵生成矩阵可以经过初等行变换可以经过初等行变换得到其得到其标准标准 生成矩阵生成矩阵。 比较：生成矩阵比较：生成矩阵G G2 2产生的码（非系统码）产生的码（非系统码） 比较：生成矩阵比较：生成矩阵G G1 1产生的码（系统码）产生的码（系统码） 1011100 1110010 0111001 1 G 00

46、10111 1100101 0111001 2 G 2 2行行+3+3行行=2 2行行 1 1行行+2+2行行=3 3行行 14332 | 1011100 1110010 0111001 GPIG 标准生成矩阵标准生成矩阵 5 5、线性分组码性质与纠错能力、线性分组码性质与纠错能力 1 1）（）（n,kn,k）线性分组码由生成矩阵）线性分组码由生成矩阵G G或校验矩阵或校验矩阵H H确定。确定。 它们满足：它们满足： 阶矩阵。阶矩阵。为为或或)(0,0knkGHHG TTT 0 ; 2 2）封闭性。（）封闭性。（n,kn,k）码中任意两个码字之和仍为许用码字，）码中任意两个码字之和仍为许用码字

47、， 即：即： ),(,),(,knCCCknCC kjiji 则若 字。）线性分组码的许用码为（即knCHC HCHCHCHCC HCHC T T j T i T k T ji T j T i ,0 0)( , 0, 0 kk 3 3）含有零码字。）含有零码字。 n n位长的零矢量为（位长的零矢量为（n,kn,k）线性分组码的许用码字。）线性分组码的许用码字。 （因为满足（因为满足 ） 00 TT HCH 4 4）所有许用码字可由其中）所有许用码字可由其中k k个独立码字（基底）线性组合而成。个独立码字（基底）线性组合而成。 在在 个许用码字中，个许用码字中，k k个独立许用码字不止一组。它们

48、可个独立许用码字不止一组。它们可 构成生成矩阵构成生成矩阵G G。 k 2 5 5）码的最小距离等于非零码字的最小重量。即：）码的最小距离等于非零码字的最小重量。即： 0),(, )(min min iii CknCCWd 因为：因为： ),(, 0)(min ),(, )(min ),(, ),(min min knCCCW knCCCCCCW knCCCCCCDd kkk jijiji jijiji ， 封闭性 定理定理 设（设（n,kn,k）线性分组码）线性分组码C C的校验矩阵为的校验矩阵为H H，则码的最小距离为，则码的最小距离为d d 的的充要条件充要条件为：为：H H中任意中任意

49、d-1d-1个列向量线性无关，且有个列向量线性无关，且有d d个列向量个列向量 线性相关。线性相关。（提供了构造最小距离为（提供了构造最小距离为d d的线性分组码的思路。）的线性分组码的思路。） 1000110 0100011 0010111 0001101 H n任何任何3 3列相加均非列相加均非0 0， n而最少的相关列数为而最少的相关列数为4 4： 如：从右向左第如：从右向左第0 0，1 1，2 2，5 5之和为之和为0 0， 相关。相关。 故，码最小距离为：故，码最小距离为：4 4 由此可知：由此可知： u当所有当所有列向量相同列向量相同，而排列位置不同的，而排列位置不同的H H 矩阵

50、所对应的分组码，矩阵所对应的分组码， 具有相同的具有相同的最小距离最小距离，则它们在纠错能力和码率上等价。，则它们在纠错能力和码率上等价。 u对于分组码来说，由于可以进行对于分组码来说，由于可以进行初等变换初等变换进行等价变换，进行等价变换，系统码系统码 和和非系统码非系统码的纠错能力是相同的，而系统码的编译码比非系统码简的纠错能力是相同的，而系统码的编译码比非系统码简 单，且单，且G G、H H矩阵可方便互求，因此，一般只需讨论系统码。矩阵可方便互求，因此，一般只需讨论系统码。 例例 6 6、线性分组码的纠错与伴随式、线性分组码的纠错与伴随式： 接收到一个序列接收到一个序列 R R 后，校验

51、后，校验 H H R RT T=0=0T T 是否成立：是否成立： n若关系成立，则认为若关系成立，则认为 R R 是一个码字；是一个码字； n否则判为码字在传输中发生了错误；否则判为码字在传输中发生了错误； 伴随式（伴随式（/ /监督子监督子/ /校验子）校验子）： S=RS=R H HT T 或 或 S ST T=H=H R RT T 如何纠错？如何纠错？ n设发送码矢设发送码矢 C=(cC=(cn n 1 1,c ,cn n2 2,c ,c0 0) ) n信道错误图样为信道错误图样为 E=(eE=(en n 1 1,e ,en n2 2,e ,e0 0) ) ， 其中其中e ei i=0

52、=0，表示第，表示第i i位无错；位无错；e ei i=1=1，表示第，表示第i i 位有错。位有错。 i=ni=n1,n1,n2,02,0。 接收序列接收序列 R R ： R R=(=(r rn n 1 1, ,r rn n2 2, ,r r0 0)=)=C C + +E E =( =(c cn n 1 1+e +en n 1 1, ,c cn n2 2+ +e en n2 2, ,c c0 0 + +e e0 0) ) 接收序列的伴随式（接收字用监督矩阵进行检验）接收序列的伴随式（接收字用监督矩阵进行检验） S ST T=H=H R RT T=H=H (C+E)(C+E)T T=H=H C

53、 CT T+H+H E ET T 由于由于H H C CT T=0=0T T，所以，所以 S ST T=H=H E ET T 或或 S=E S=E H HT T 即：即： 分析分析： 0 0 1 1 2 2 1 1 0 1 2 1 0121.eheheheh e e e e hhhhHES n n n n n n nn TT n对于对于2 2元码，元码， e ei i=0=0，1 1，伴随式是，伴随式是H H矩阵中对应矩阵中对应若干列向量之和若干列向量之和。 （1 1位错，多位错）位错，多位错） 例例：已知：已知 (7,3)(7,3)码的一致校验矩阵。码的一致校验矩阵。 1000110 010

54、0011 0010111 0001101 H 设发送码矢设发送码矢C C=1010011=1010011。若传输时没有差错，若传输时没有差错，E E0 0 = =（00000000000000），）， 则接收码字则接收码字 R R1010011=C1010011=C，R R 与与C C 相同：相同： S S0 0 = =E E0 0 H HT T = = （ （00000000） 没有错误；没有错误； 若传输时差错图样为若传输时差错图样为 E E00 00 = C = 1010011= C = 1010011， 则则 R R00000000000000， S S00 00 = =E E0000

55、 H HT T = = （ （00000000），无法发现此错误；），无法发现此错误； 若若发送码矢发送码矢C C1 1=0100111=0100111，C C2 2=1101001=1101001， 错误图样错误图样 E E1 1= =（10000001000000），）， 接收码字接收码字 R R1 111001111100111， R R2 20101001 0101001 ； 伴随式伴随式 S S1 1 = R= R1 1 H HT T = E = E1 1 H HT T = = （11101110），）， S S2 2= R= R2 2 H HT T = E = E2 2 H HT

56、T = = （11101110），）， 可见：可见： S S1 1 = S= S2 2 0 0 ；不为；不为0 0，译码器判断有错误；，译码器判断有错误； 第第1 1位错误，刚好对应于位错误，刚好对应于H H矩阵的第矩阵的第1 1列向量；列向量； 伴随式与发送码字无关，只与错误图样有关。伴随式与发送码字无关，只与错误图样有关。 0 1 1 1 0 0 0 0 0 0 1 1000110 0100011 0010111 0001101 11 TT HES 0 0 1 1 2 2 1 1.eheheheh HES n n n n TT 当当错误图样错误图样 E E3 3 = =（001000000

57、10000），），可得：可得： S S3 3= E= E3 3 H HT T = =（11011101），）， 刚好为刚好为H H矩阵的第矩阵的第3 3列向量。列向量。 依此类推：依此类推：当发生当发生1 1位错误时，当位错误时，当i i位错误发生在第位错误发生在第i i位，其伴随式位，其伴随式 正好是正好是H H矩阵中的第矩阵中的第i i列向量。列向量。 若传送时发送若传送时发送2 2位码元错误，设位码元错误，设 E E= =（10100001010000）= = E E1 1 + + E E3 3 ， 伴随式伴随式 S S = E= E H HT T= = （ E E1 + 1 + E E

58、3 3） H HT T = = E E1 1 H HT T +E +E3 3 H HT T = = （00110011），）， 可见：可见： S S不同于不同于H H中的任何一列，说明发生了不止一位错误；中的任何一列，说明发生了不止一位错误； 可能是第可能是第1 1、第、第3 3位错误；位错误； 但若错误图样但若错误图样 E E= =（01001000100100）或（）或（00000110000011），）， 其伴随式仍为（其伴随式仍为（00110011），译码器无法判断错误的位置，故无法纠），译码器无法判断错误的位置，故无法纠 正正2 2位的随机差错。位的随机差错。 若若错误图样错误图样

59、E E= =（01101000110100），可得：），可得： S= ES= E H HT T = =（11101110）= S= S1 1 ，刚好，刚好 为为H H矩阵的第矩阵的第1 1列向量。列向量。 由此：由此：此（此（7 7，3 3）码可发现）码可发现3 3位随机错误，但当发生位随机错误，但当发生1 1位错误时，无法纠位错误时，无法纠 正；或者相反。正；或者相反。 0 1 1 1 0 0 1 0 1 1 0 1000110 0100011 0010111 0001101 TT HES H H矩阵：任意小于等于矩阵：任意小于等于3 3列线性无关，而最少列线性无关，而最少4 4列就线性相关

60、，故其列就线性相关，故其最小最小 码距码距d dminmin=4, =4, 故可纠正故可纠正1 1位错误的同时检测出位错误的同时检测出2 2位错误，或检测位错误，或检测3 3位错误。位错误。 本章习题 9-1 9-3 9-4 7、 标准阵列译码标准阵列译码 u传输中错误图样传输中错误图样E不同时，有可能对应相同的伴随式。不同时，有可能对应相同的伴随式。 当信道译码器接收到接收序列当信道译码器接收到接收序列R后，由下式求解后，由下式求解E： S = R HT = E HT 但是，此式中对应的错误图样可以有但是，此式中对应的错误图样可以有2k个解。个解。 u一般采用一般采用最大似然准则译码最大似然