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

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

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

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

4、(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之间，误码率低，但需要反馈信道。之间，误码率低，但需要反馈信道。实时性和连续性好。实时性和连续性好。设备不太复杂，应用广泛。设备不太复杂，应用广泛。4 4、信息反馈、信息反馈(IRQ)(IRQ)方式方式( (回程校验方式回程校验方式) ):

9、: 接收端接收端收到信道传输来的码后，全部由反馈信道发回发送端；收到信道传输来的码后，全部由反馈信道发回发送端；发送端发送端将发送的码与反馈回的码进行比较，发现错误后，把出将发送的码与反馈回的码进行比较，发现错误后，把出错的码再次重发，直到接收端认为正确为止。错的码再次重发，直到接收端认为正确为止。发送端发送端接收端接收端消息（不编码）消息（不编码）IRQIRQ消息消息不检错、纠错不检错、纠错nIRQIRQ特点：特点：需要双向控制，需要反馈信道。需要双向控制，需要反馈信道。系统的控制设备和存储设备相对复杂。系统的控制设备和存储设备相对复杂。无需编译码设备，接收端不具备检、纠错能力强，整体系统纠

10、无需编译码设备，接收端不具备检、纠错能力强，整体系统纠错能力强，可大大降低整个系统误码率。错能力强，可大大降低整个系统误码率。具有自适应性，但若重发频繁，将使传输效率降低，甚至系统具有自适应性，但若重发频繁，将使传输效率降低，甚至系统阻塞，使得连续性和实时性变差。阻塞，使得连续性和实时性变差。5 5、检错删除：、检错删除： 接收端接收端发现错码后，立即将其删除。发现错码后，立即将其删除。 适用在发送码元中有大量多余度，删除部分接收码元不影响应适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处。用之处。 6 6、差错隐藏：、差错隐藏： 在某些应用领域，如音乐、语音、图像、视频等领域，在

11、某些应用领域，如音乐、语音、图像、视频等领域，有差错或损失的部分数据对人的主观感受影响不大，此时，可有差错或损失的部分数据对人的主观感受影响不大，此时，可根据已接收的数据采用内插或外推的技术，得到满足应用的输根据已接收的数据采用内插或外推的技术，得到满足应用的输出数据。出数据。9 9.2 .2 纠错码分类纠错码分类1 1、纠错码的分类：、纠错码的分类：n按纠正错误的类型分类：按纠正错误的类型分类：纠随机差错码：纠随机差错码：无记忆信道中，噪声随机独立地影响每个无记忆信道中，噪声随机独立地影响每个码元，造成了随机差错；码元，造成了随机差错；纠突发差错码：纠突发差错码：有记忆信道中，突发噪声可造成

12、突发性的有记忆信道中，突发噪声可造成突发性的成群差错（如太阳黑子、雷电等引起）成群差错（如太阳黑子、雷电等引起）。纠混合差错码纠混合差错码n按应用目的分类：按应用目的分类：检错码检错码只能检测错误是否存在。只能检测错误是否存在。纠错码纠错码能够检测错误，并能够自动纠正错误。能够检测错误，并能够自动纠正错误。纠删码纠删码能够纠正删除（丢失）了的信息。能够纠正删除（丢失）了的信息。n按码元取值分类：按码元取值分类：二元纠错码二元纠错码目前最常用模式目前最常用模式多元纠错码多元纠错码n按码的结构中对信息序列的处理方式分类：按码的结构中对信息序列的处理方式分类：分组码（分组码（n,kn,k）将信息序列

13、每将信息序列每k k位分组，再增加入位分组，再增加入r=n-r=n-k k 个冗余码元（校验元），校验元只由本组个冗余码元（校验元），校验元只由本组k k个信息元按个信息元按照一定规律产生，与其他信息组无关。照一定规律产生，与其他信息组无关。卷积码（卷积码（n,kn,k0 0,L ,L）将信息序列每将信息序列每 k k0 0 位分组，编码器输位分组，编码器输出该段的出该段的r=n-kr=n-k0 0个与本组和前个与本组和前L L组信息元相关的校验元，组信息元相关的校验元，得到得到n n长的码字。长的码字。n按码的数学结构中校验元与信息元关系分类：按码的数学结构中校验元与信息元关系分类：线性码线

14、性码线性关系，如线性方程组线性关系，如线性方程组非线性码非线性码非线性关系非线性关系n按码的是否具有循环性分类：按码的是否具有循环性分类：循环码循环码分组码中任一码字的码元经过循环移位后，分组码中任一码字的码元经过循环移位后，仍是本码中的码字。仍是本码中的码字。非循环码非循环码至少有一个码字经循环移位后，不再是本至少有一个码字经循环移位后，不再是本码中的码字。码中的码字。n按构造码的数学理论分类：按构造码的数学理论分类：代数码代数码近世代数，比较完善，如线性分组码。近世代数，比较完善，如线性分组码。几何码几何码投影几何学投影几何学算术码算术码数论，高等算术数论，高等算术组合码组合码排列组合，数

15、论排列组合，数论 实际的码可能同时分别具备以上某些特征，比如：某一纠错码实际的码可能同时分别具备以上某些特征，比如：某一纠错码可以同时是线性码、分组码、循环码、纠随机差错码、二元码、代可以同时是线性码、分组码、循环码、纠随机差错码、二元码、代数码等。数码等。9 9.3 .3 纠错码的概念及其纠错能力纠错码的概念及其纠错能力信息序列信息序列码字序列码字序列接收序列接收序列译码后信息序列译码后信息序列噪声源噪声源E E 错误图样错误图样 对编码器的输入信息序列，每对编码器的输入信息序列，每k k个信息符号分成个信息符号分成信息组信息组： m m= =（m mk-1k-1, ,m mk-2k-2,m

16、 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=(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：信息组长度；

17、：信息组长度； r r：校验元的位长。：校验元的位长。kqn1 1、信息元、校验元、码字：、信息元、校验元、码字：n码码C C中的码字个数（中的码字个数（k k为信息位数）：为信息位数）：n（n,kn,k）分组码：）分组码：编码器输出为编码器输出为 个码字组成的序列；个码字组成的序列；许用码字许用码字： 种码符号序列中，取出种码符号序列中，取出 个作为分组码个作为分组码的码字。的码字。禁用码字禁用码字：其余：其余 种码符号序列。种码符号序列。n卷积码（卷积码（n,kn,k0 0,L ,L）: :编码器输出的校验元不仅由本组信息元有关，编码器输出的校验元不仅由本组信息元有关，也与其前面若干段的信

18、息组所确定。也与其前面若干段的信息组所确定。kqkqnqkqknqq 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 0t t码长码长 n n = = k k + + r r分组码的结构分组码的结构n2 2、码字的汉明重量：、码字的汉明重量：汉明距离汉明距离D(CD(C1 1,C,C2 2) )：对应位置上不同码元的个数。：对应位置上不同码元的个数。码的最小距离码的最小距离：d dminmin, d(C), d(C)汉明重量（汉明势）汉明重量（汉明势）：码字中非零码元的个数：码

19、字中非零码元的个数 W(C)W(C)。 对对2 2元码，汉明重量为码字中的元码，汉明重量为码字中的“1”1”的个数。因此，二的个数。因此，二元码字的汉明重量和汉明距离为：元码字的汉明重量和汉明距离为： 1 , 0)(10iniiccCW)(),(jijiCCWCCD模模2 2加，若对应位不同加，若对应位不同则为则为1 1；相同则为；相同则为0 0。其重量即为不相同的其重量即为不相同的总位数，也就是两个总位数，也就是两个码字的汉明距离。码字的汉明距离。n3 3、错误图样：、错误图样： 码字序列通过信道传输送入译码器之前，由于信道的码字序列通过信道传输送入译码器之前，由于信道的 噪声干扰，使得接收

20、序列中某些码元发生差错，可用噪声干扰，使得接收序列中某些码元发生差错，可用错误错误图样图样（差错图样差错图样）定量描述：）定量描述： E=(eE=(en-1n-1e en-2n-2ee1 1e e0 0)=C)=CR R 二元数字通信系统中，码元传输错误图样：二元数字通信系统中，码元传输错误图样： 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位码元发生差错；位码元发

21、生差错； 差错关系差错关系： 接收序列接收序列 = = 许用码字许用码字 + + 错误图样错误图样 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 接收序列长度接收序列长度 = = 码字长度码字长度 = = 错误图样长度错误图样长度 = n= n差错类型：差错类型：n随机差错随机差错是相互独立的、不相关，存在这种差错是相互独立的、不相关，存在这种差错的信道是无记忆信道或随机信道；的信道是无记忆信道或随机信道；n突发差错突发差错指成串出现的错误指成串出现的错误, ,错误与错误间有相关错误与错

22、误间有相关性性, ,一个差错往往要影响到后面一串码元。一个差错往往要影响到后面一串码元。RCEERCECR,例例 发送码字发送码字 C= 010110111, C= 010110111, 接收序列接收序列 R= 001110011,R= 001110011,错误图样错误图样 E=C+R= 011000100E=C+R= 011000100 若为若为随机差错随机差错，错误码元为：，错误码元为： 2 2，3 3，7 7，错误数量，错误数量=W(E)=3=W(E)=3； 若为若为突发差错突发差错，错误码元串长度为：，错误码元串长度为：6 6； 出错范围：从错误图样出错范围：从错误图样E E中的第一个

23、中的第一个1 1到最后一个到最后一个1 1， 其其错误串中的错误串中的0 0表示该位码元未发生错误。表示该位码元未发生错误。 nBSCBSC（二元无记忆对称信道）的错误图样的出现概率（二元无记忆对称信道）的错误图样的出现概率 设设p p为错误概率为错误概率(1),(1),则则n n次无记忆扩展信道中，次无记忆扩展信道中，随机差错随机差错的某错误图样的某错误图样E E的出现概率为：的出现概率为： )()()(EWEWnppEP0 0位差错（全对）：位差错（全对）： W(EW(E0 0)=0)=0，1 1位随机差错：位随机差错： W(EW(E1 1)=1, )=1, 2 2位随机差错：位随机差错：

24、 W(EW(E2 2)=2,)=2,e e位随机差错：位随机差错： W(EW(Ee e)=e,)=e,n n位差错（全错）位差错（全错） W(EW(En n)=n,)=n,0nC1nC2nCenCnnCppEPn 11)(npEP)(0222)(ppEPneeneppEP)(nnpEP)(差错图样数差错图样数概率概率错误图样的错误图样的总数总数：nnnnnnnCCCCC2.e210nnnnpppppp.221)(.)(.)()()(210neEPEPEPEPEP 发生发生多位错误的概率多位错误的概率小于小于较少位数较少位数随机错误的概率。随机错误的概率。因此，因此，无记忆信道无记忆信道中，一般

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

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

27、个子集内，无法纠正。位错误，则接收序列进入另一个子集内，无法纠正。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1n定理定理：对于一个（：对于一个（n,kn,k）分组码）分组码C C，最小距离为，最小距离为d dminmin，则：，则：若能检测（发现）若能检测（发现）e e个随机错误，则要求个随机错误，则要求 d dminmin e+1e+1 ; ; 或：可检测出任意小于等于或：可检测出任意小于等于 e = d e = dminmin1 1个随机差错；个随机差错； 若能纠正若能纠正 t t 个随机错误，则要求个随机错误

28、，则要求 d dminmin 2t+12t+1 ; ; 或：可纠正任意小于等于或：可纠正任意小于等于 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

29、+1 e+1，否则，会发生码字译码混淆，如，否则，会发生码字译码混淆，如 R+E =V R+E =V 。eVUdmin dmin=4,码距和检错能力关系示意图t tVUdmin图 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，

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

31、监督元是其中某些信息元的运算结果。要求：每个监督元是其中某些信息元的运算结果。 （以下仅讨论二元码）（以下仅讨论二元码）例例：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。监督元可按下面方程组计算监督元可

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

33、0000000000000000451562456346CCCCCCCCCCCCC前例前例3 3、 一致监督（校验）矩阵一致监督（校验）矩阵 为了运算方便，为了运算方便，可可将监督方程写将监督方程写成矩阵形式。成矩阵形式。前例前例：6543210654321010110000111010001100010001100010C0000010110001110100H11000100110001CCCCCCCCCCCCCC 令00TTTCHHCor00000000000000000000451562456346CCCCCCCCCCCCC推广：推广：一般情况，对一般情况，对 ( (n n, ,k k

34、) ) 线性分组码，每个码字中的线性分组码，每个码字中的 r r( (r r= =n nk k) ) 个个监督元与信息元之间的关系可由如下监督元与信息元之间的关系可由如下r r * * n n 阶阶线性方程组确定：线性方程组确定：) 6 . 2 . 6(000022110222212101212111ChChChChChChChChChrnnrnrnnnnnnrnrrnnhhhhhhhhhH.212212111211则：则：00TTTCHorHC021.cccCnnT令：令：.0121hhhhHnnn若用若用h hi i (i=n-1,n-2,1,0) (i=n-1,n-2,1,0) 表示表示

35、H H矩阵中的矩阵中的列矢量列矢量，则，则H H可写为：可写为：0.00111111hchchchcnnnnnH H矩阵的矩阵的每一行元素每一行元素是线性方程组中一个方程的系数，由它来是线性方程组中一个方程的系数，由它来唯一确定每一个校验元。因此，唯一确定每一个校验元。因此，H H中中每一行必须是线性无关每一行必须是线性无关的，的，且必定有：且必定有：r =nr =nk k 行。行。0TCH4 4、 生成矩阵生成矩阵 根据（根据（n,kn,k）线性分组码的一致监督方程出发，将）线性分组码的一致监督方程出发，将信息组信信息组信息位息位与与生成的码字生成的码字之间的生成关系用矩阵来表示，就可得到之

36、间的生成关系用矩阵来表示，就可得到生生成矩阵。成矩阵。例例 前例中，前例中，3642654165054(6.2.1)CCCCCCCCCCCCC041526,mcmcmc0101210122023041526mmcmmcmmmcmmcmcmcmc0120123456110011111101100010001mmmccccccc1011100111001001110010120123456mmmccccccc生成矩阵生成矩阵G G1 1其各行为码字，互不相关。其各行为码字，互不相关。其他码字为此三个码字的线性其他码字为此三个码字的线性组合方式生成。组合方式生成。n推广推广：对一般：对一般 ( (n

37、 n, ,k k) ) 线性分组码，设有一组线性分组码，设有一组k k个个线性独立的码字，线性独立的码字，由此一组线性独立的码字以行向量构成的矩阵，称为线性分组由此一组线性独立的码字以行向量构成的矩阵，称为线性分组码的码的生成矩阵生成矩阵G G（k k* *n n阶）：阶）：kkkknknknnnngggggCgggggCgggggC).(.).().(0121220212212211011211110121202122121011211121.kkknknnnnnkgggggggggggggggG满足：满足：)2,.,2 , 1 (,),(kiiiiknCGmC码nG G中每一行及其线性组合

38、都是中每一行及其线性组合都是许用码字许用码字，故有：，故有：阶阶零零矩矩阵阵。为为)(, 0,0knkGHorHGTTT0 线性分组码的所有码字都可由其生成矩阵或一致校验矩阵求线性分组码的所有码字都可由其生成矩阵或一致校验矩阵求得。当已知得。当已知G G、H H中的一个，就可求另一个。中的一个，就可求另一个。n系统码：系统码： 信息元以不变形式出现在码字的任意信息元以不变形式出现在码字的任意k k位上。位上。n标准生成矩阵：标准生成矩阵： 生成矩阵能把信息元保留在各码字的生成矩阵能把信息元保留在各码字的最左边最左边k k位位上。上。|)(knkkPIG|)(knTknkIPH0TGH 因此，因

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

40、等价的标准生成矩阵标准生成矩阵。例例 一个二元（一个二元（7 7，3 3）码）码, ,生成矩阵为：生成矩阵为：0010111110010101110012G生成的码字为：生成的码字为：码字集合完全相同。码字集合完全相同。 但生成矩阵但生成矩阵G1G1、G2G2选取了不同的独立码字构成。选取了不同的独立码字构成。生成矩阵生成矩阵可以经过初等行变换可以经过初等行变换得到其得到其标准标准生成矩阵生成矩阵。比较：生成矩阵比较：生成矩阵G G2 2产生的码（非系统码）产生的码（非系统码）比较：生成矩阵比较：生成矩阵G G1 1产生的码（系统码）产生的码（系统码）101110011100100111001

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

42、nCCCknCCkjiji则若字。）线性分组码的许用码为（即knCHCHCHCHCHCCHCHCTTjTiTkTjiTjTi,00)(, 0, 0kk3 3）含有零码字。）含有零码字。 n n位长的零矢量为（位长的零矢量为（n,kn,k）线性分组码的许用码字。）线性分组码的许用码字。（因为满足（因为满足 ）00TTHCH4 4）所有许用码字可由其中）所有许用码字可由其中k k个独立码字（基底）线性组合而成。个独立码字（基底）线性组合而成。 在在 个许用码字中，个许用码字中，k k个独立许用码字不止一组。它们可个独立许用码字不止一组。它们可构成生成矩阵构成生成矩阵G G。k25 5）码的最小距离

43、等于非零码字的最小重量。即：）码的最小距离等于非零码字的最小重量。即：0),(, )(minminiiiCknCCWd因为：因为：),(, 0)(min),(, )(min),(, ),(minminknCCCWknCCCCCCWknCCCCCCDdkkkjijijijijiji，封闭性定理定理 设（设（n,kn,k）线性分组码）线性分组码C C的校验矩阵为的校验矩阵为H H，则码的最小距离为，则码的最小距离为d d的的充要条件充要条件为：为：H H中任意中任意d-1d-1个列向量线性无关，且有个列向量线性无关，且有d d个列向量个列向量线性相关。线性相关。（提供了构造最小距离为（提供了构造最

44、小距离为d d的线性分组码的思路。）的线性分组码的思路。）1000110010001100101110001101Hn任何任何3 3列相加均非列相加均非0 0，n而最少的相关列数为而最少的相关列数为4 4：如：从右向左第如：从右向左第0 0，1 1，2 2，5 5之和为之和为0 0，相关。相关。故，码最小距离为：故，码最小距离为：4 4由此可知：由此可知：u当所有当所有列向量相同列向量相同，而排列位置不同的，而排列位置不同的H H 矩阵所对应的分组码，矩阵所对应的分组码，具有相同的具有相同的最小距离最小距离，则它们在纠错能力和码率上等价。，则它们在纠错能力和码率上等价。u对于分组码来说，由于可

45、以进行对于分组码来说，由于可以进行初等变换初等变换进行等价变换，进行等价变换，系统码系统码和和非系统码非系统码的纠错能力是相同的，而系统码的编译码比非系统码简的纠错能力是相同的，而系统码的编译码比非系统码简单，且单，且G G、H H矩阵可方便互求，因此，一般只需讨论系统码。矩阵可方便互求，因此，一般只需讨论系统码。例例6 6、线性分组码的纠错与伴随式、线性分组码的纠错与伴随式：接收到一个序列接收到一个序列 R R 后，校验后，校验 H H R RT T=0=0T T 是否成立：是否成立：n若关系成立，则认为若关系成立，则认为 R R 是一个码字；是一个码字；n否则判为码字在传输中发生了错误；否

46、则判为码字在传输中发生了错误； 伴随式（伴随式（/ /监督子监督子/ /校验子）校验子）： S=RS=R H HT T 或或 S ST T=H=H R RT T 如何纠错？如何纠错？n设发送码矢设发送码矢 C=(cC=(cn n1 1,c ,cn n2 2,c,c0 0) )n信道错误图样为信道错误图样为 E=(eE=(en n1 1,e ,en n2 2,e,e0 0) ) ，其中其中e ei i=0=0，表示第，表示第i i位无错；位无错；e ei i=1=1，表示第，表示第i i 位有错。位有错。 i=ni=n1,n1,n2,02,0。接收序列接收序列 R R ：R R=(=(r rn

47、n1 1, ,r rn n2 2,r r0 0)=)=C C + +E E =( =(c cn n1 1+e+en n1 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 CT T+H+H E ET T 由于由于H H C CT T=0=0T T，所以，所以 S ST T=H=H E ET T 或或 S=ES=E H HT T 即：即：分析分析：0011221101210121.eh

48、eheheheeeehhhhHESnnnnnnnnTTn对于对于2 2元码，元码， e ei i=0=0，1 1，伴随式是，伴随式是H H矩阵中对应矩阵中对应若干列向量之和若干列向量之和。（1 1位错，多位错）位错，多位错）例例：已知：已知 (7,3)(7,3)码的一致校验矩阵。码的一致校验矩阵。1000110010001100101110001101H 设发送码矢设发送码矢C C=1010011=1010011。若传输时没有差错，若传输时没有差错，E E0 0 = =（00000000000000），）， 则接收码字则接收码字 R R1010011=C1010011=C，R R 与与C C

49、相同：相同： S S0 0 = =E E0 0 H HT T = = （00000000） 没有错误；没有错误； 若传输时差错图样为若传输时差错图样为 E E00 00 = C = 1010011= C = 1010011， 则则 R R00000000000000， S S00 00 = =E E0000 H HT T = = （00000000），无法发现此错误；），无法发现此错误； 若若发送码矢发送码矢C C1 1=0100111=0100111，C C2 2=1101001=1101001， 错误图样错误图样 E E1 1= =（10000001000000），）， 接收码字接收码字

50、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 T = = （11101110），）， 可见：可见： S S1 1 = S= S2 2 0 0 ；不为；不为0 0，译码器判断有错误；，译码器判断有错误； 第第1 1位错误，刚好对应于位错误，刚好对应于H H矩阵的第矩阵的第1 1列向量；列向量； 伴随式与发送码字无关，只与错误图样有关。伴随式与

51、发送码字无关，只与错误图样有关。 01110000001100011001000110010111000110111TTHES00112211.ehehehehHESnnnnTT 当当错误图样错误图样 E E3 3 = =（00100000010000），），可得：可得： S S3 3= E= E3 3 H HT T = =（11011101），），刚好为刚好为H H矩阵的第矩阵的第3 3列向量。列向量。 依此类推：依此类推：当发生当发生1 1位错误时，当位错误时，当i i位错误发生在第位错误发生在第i i位，其伴随式位，其伴随式正好是正好是H H矩阵中的第矩阵中的第i i列向量。列向量。若传

52、送时发送若传送时发送2 2位码元错误，设位码元错误，设 E E= =（10100001010000）= = E E1 1 + + E E3 3 ， 伴随式伴随式 S S = E= E H HT T= = （ E E1 + 1 + E E3 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= =（0100100010010

53、0）或（）或（00000110000011），）， 其伴随式仍为（其伴随式仍为（00110011），译码器无法判断错误的位置，故无法纠），译码器无法判断错误的位置，故无法纠正正2 2位的随机差错。位的随机差错。 若若错误图样错误图样 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位错误时，无法纠位错误时，无法纠正；或者相反。正；或者相反

54、。011100101101000110010001100101110001101TTHESH H矩阵：任意小于等于矩阵：任意小于等于3 3列线性无关，而最少列线性无关，而最少4 4列就线性相关，故其列就线性相关，故其最小最小码距码距d dminmin=4, =4, 故可纠正故可纠正1 1位错误的同时检测出位错误的同时检测出2 2位错误，或检测位错误，或检测3 3位错误。位错误。本章习题 9-1 9-3 9-47、 标准阵列译码标准阵列译码u传输中错误图样传输中错误图样E不同时，有可能对应相同的伴随式。不同时，有可能对应相同的伴随式。 当信道译码器接收到接收序列当信道译码器接收到接收序列R后，由

55、下式求解后，由下式求解E： S = R HT = E HT 但是，此式中对应的错误图样可以有但是，此式中对应的错误图样可以有2k个解。个解。u一般采用一般采用最大似然准则译码最大似然准则译码（输入码元等概分布），其译码错误概率（输入码元等概分布），其译码错误概率最小，正确译码概率最大。最小，正确译码概率最大。 在在BSC信道中，重量最小的信道中，重量最小的E*，其发生的概率最大，则：，其发生的概率最大，则：P(C+ E*|C)=P(E*) P(C+ E|C), EE* 因此，用伴随式译码时就采用最大似然准则（最小距离译码准因此，用伴随式译码时就采用最大似然准则（最小距离译码准则），选取重量最轻

56、的则），选取重量最轻的E作为译码的错误图样。作为译码的错误图样。 实际译码中，根据实际译码中，根据 R HT = S = E HT找出重量最轻的找出重量最轻的E的译码的译码方法及其繁琐。一般采用标准阵列译码方法。方法及其繁琐。一般采用标准阵列译码方法。u标准阵列译码方法：标准阵列译码方法：n发送码字：取自由发送码字：取自由 2k 个码字构成的集合个码字构成的集合C ；n接收序列：可以是接收序列：可以是 2n 个个 n 长序列中任一个矢量；长序列中任一个矢量；n把把 2n 个个 n 长序列划分为长序列划分为 2k 个互不相交的子集个互不相交的子集 ，并，并按照最大似然译码准则，使得在每个子集对应

57、一个许用码字；按照最大似然译码准则，使得在每个子集对应一个许用码字；n根据码字和子集间一一对应关系，若接收矢量根据码字和子集间一一对应关系，若接收矢量 R落在子集落在子集 Dl中，中，就把就把 Rl 译为子集译为子集 Dl 对应的码字对应的码字 Cl 。因此因此 当接收序列当接收序列 R 与实际发送码字在同一子集中时，译码就是正确与实际发送码字在同一子集中时，译码就是正确的。的。k221,DDDu标准阵列表的构造：标准阵列表的构造：n先将先将 2k 个许用码字排成一行，作为个许用码字排成一行，作为标准阵列标准阵列的第一行，并将全的第一行，并将全0码矢码矢C0=(000)放在最左面的位置上；放在

58、最左面的位置上；n然后在剩下的然后在剩下的 (2n2k) 个个 n 长序列中选取一个重量最轻的重长序列中选取一个重量最轻的重 E1 放在全放在全0码矢码矢 C 0下面，即第下面，即第2行首位；再将行首位；再将 E1 分别和所有许用分别和所有许用码字相加：码字相加：Ci + E1，放在对应码字下构成阵列第二行；，放在对应码字下构成阵列第二行；n在第二次剩下的在第二次剩下的 n长序列中，选取重量最轻的长序列中，选取重量最轻的 n 重重 E2，放在，放在 E1 下面，并将下面，并将 E2 分别加到第一行各许用码字上分别加到第一行各许用码字上Ci + E2 ，得到第三，得到第三行；行；n，继续这样做下

59、去，直到全部，继续这样做下去，直到全部 n 重用完为止。得到重用完为止。得到 (n,k) 线性线性码的标准阵列。码的标准阵列。k221,DDDk2C22ECk32ECkknk22ECkni2ECkn22ECkn2E标准阵列表结构标准阵列表结构伴随式伴随式陪集首（表中每一行称为陪集）陪集首（表中每一行称为陪集）u标准阵列表的特点：标准阵列表的特点：n表中每一行称为表中每一行称为陪集陪集，该行的首位元素，该行的首位元素Ei 在为在为陪集首陪集首，各行元，各行元素都不同；素都不同；n如果把如果把错误图样错误图样作为陪集首，则同一个陪集中所有的元素都队作为陪集首，则同一个陪集中所有的元素都队应相同的伴

60、随式；应相同的伴随式；n表中表中各列各列以同一组许用码字为基础，将以同一组许用码字为基础，将2n个接收序列划分成不个接收序列划分成不相交的子集合相交的子集合D0, D1, D2, D2k-1. 每个子集合每个子集合Dj对应同一个许用对应同一个许用码字码字Cj ，它是每列子集的，它是每列子集的子集首子集首。u标准阵列的译码：标准阵列的译码：n列子集列子集Dj各元素是同一许用码字各元素是同一许用码字Cj在信道中发生若干错误得到。在信道中发生若干错误得到。同列中各元素对应的是不同的错误图样。同列中各元素对应的是不同的错误图样。n而列子集而列子集Dj各元素是与许用码字各元素是与许用码字Cj距离最近的，