1、信息论基础理论与应用第三版傅祖芸第9章讲义 香农第二定理指出，在信道中以信息传输率香农第二定理指出，在信道中以信息传输率R R小于信道容量小于信道容量条件下，使差错概率尽可能小的条件下，使差错概率尽可能小的信道编译码原则信道编译码原则是：是：编码原则编码原则：在在n n次扩展信道输入符号序列中选取次扩展信道输入符号序列中选取MM个作为码字构成一组个作为码字构成一组码码C C，并尽量使选取的，并尽量使选取的MM个码字中两两不相同码字的汉明距离尽个码字中两两不相同码字的汉明距离尽可能地大；可能地大；译码原则译码原则：当收到符号序列后，翻译成与之汉明距离最近的码字（最大当收到符号序列后，翻译成与之汉
2、明距离最近的码字（最大似然准则）。似然准则）。几十年来，基于香农编码定理和以上编译码原则，科技工作几十年来，基于香农编码定理和以上编译码原则，科技工作者们开发了很多具有者们开发了很多具有纠错能力的信道编码纠错能力的信道编码，如线性分组码、循环，如线性分组码、循环码、码、BCHBCH码、卷积码、码、卷积码、TCMTCM码、码、TuoboTuobo码等，在通信系统中得到码等，在通信系统中得到了广泛应用。了广泛应用。9.1 9.1 差错控制的基本形式差错控制的基本形式 现代数字通信系统中，利用检错和纠错的编码技术，现代数字通信系统中，利用检错和纠错的编码技术，使得信道编译码具备一定的差错控制能力。主
3、要方式有：使得信道编译码具备一定的差错控制能力。主要方式有：1 1、前向纠错、前向纠错(FEC)(FEC)方式方式：发送端信道编码器将信息码组编成具有一定发送端信道编码器将信息码组编成具有一定纠错能力纠错能力的码。的码。接收端信道译码器对接收码字译码，若传输中产生的差错接收端信道译码器对接收码字译码，若传输中产生的差错数目在码的纠错能力之内，译码器对差错进行数目在码的纠错能力之内，译码器对差错进行定位定位并加以并加以纠正纠正。发送端发送端接收接收端端可检错纠错的码可检错纠错的码FECFEC检错、纠错检错、纠错nFEC FEC 特点特点单向控制，不需要反馈信道；时延小，实时性好。单向控制，不需要
4、反馈信道；时延小，实时性好。为适应较差信道，冗余码元多，编码效率低，译码设备复杂。为适应较差信道，冗余码元多，编码效率低，译码设备复杂。有一定的纠错范围限制。有一定的纠错范围限制。适用于容错能力强的语音、图像传输；不适合容错能力弱的适用于容错能力强的语音、图像传输；不适合容错能力弱的数据通信网。数据通信网。2 2、反馈重发、反馈重发(ARQ)(ARQ)方式（检错重发方式）：方式（检错重发方式）：发送端发送端发送的是能够发送的是能够发现（检测）发现（检测）错误的码；错误的码；接收端接收端收到信道传输来的码后，译码器依据该码编码规则，收到信道传输来的码后，译码器依据该码编码规则，判决出当前码字传输
5、是否出错，并把判决出当前码字传输是否出错，并把判决结果判决结果（应答信号）反（应答信号）反馈至发送端。发送端把接收端认为有错的信息馈至发送端。发送端把接收端认为有错的信息重新发出重新发出，直到，直到接收端认为正确为止。接收端认为正确为止。发送端发送端接收端接收端可检错的码可检错的码ARQARQ应答信号应答信号检错、不纠错检错、不纠错nARQARQ特点特点需要双向控制和反馈信道。需要双向控制和反馈信道。系统的控制设备和存储设备复杂，但编译码设备较简单。系统的控制设备和存储设备复杂，但编译码设备较简单。接收端检错能力、系统纠错能力强，可大大降低系统误码率。接收端检错能力、系统纠错能力强，可大大降低
6、系统误码率。具有自适应性。但若重发频繁，将使效率降低，甚至系统阻塞，具有自适应性。但若重发频繁，将使效率降低，甚至系统阻塞，使得连续性和实时性变差。使得连续性和实时性变差。在短波、有线干扰情况复杂的信道，在计算机网络、分组在短波、有线干扰情况复杂的信道，在计算机网络、分组交换网、卫星通信、移动通信中广泛应用。交换网、卫星通信、移动通信中广泛应用。3 3、混合纠错、混合纠错(HEC)(HEC)方式：方式：n 前向纠错前向纠错FEC+FEC+反馈重发反馈重发ARQARQ 发送端发送的是兼有发送端发送的是兼有检错和纠错能力检错和纠错能力的码；接收端收到码的码；接收端收到码字后，首先检测错误情况。当差
7、错在码的纠错能力范围内，就字后，首先检测错误情况。当差错在码的纠错能力范围内，就自动纠错；当差错很多已经超出了纠错能力，但能够检测到错自动纠错；当差错很多已经超出了纠错能力，但能够检测到错误，接收端就通过反馈信道，请求重发。误，接收端就通过反馈信道，请求重发。发送端发送端接收端接收端可检错和纠错的码可检错和纠错的码HECHEC应答信号应答信号检错、纠错检错、纠错nHECHEC的特点的特点总体性能介于总体性能介于FECFEC和和ARQARQ之间，误码率低，但需要反馈信道。之间，误码率低，但需要反馈信道。实时性和连续性好。实时性和连续性好。设备不太复杂，应用广泛。设备不太复杂，应用广泛。4 4、信
8、息反馈、信息反馈(IRQ)(IRQ)方式方式(回程校验方式回程校验方式):接收端接收端收到信道传输来的码后，全部由反馈信道发回发送端；收到信道传输来的码后，全部由反馈信道发回发送端；发送端发送端将发送的码与反馈回的码进行比较，发现错误后，把出将发送的码与反馈回的码进行比较，发现错误后，把出错的码再次重发，直到接收端认为正确为止。错的码再次重发，直到接收端认为正确为止。发送端发送端接收端接收端消息（不编码）消息（不编码）IRQIRQ消息消息不检错、纠错不检错、纠错nIRQIRQ特点：特点：需要双向控制，需要反馈信道。需要双向控制，需要反馈信道。系统的控制设备和存储设备相对复杂。系统的控制设备和存
9、储设备相对复杂。无需编译码设备，接收端不具备检、纠错能力强，整体系统纠无需编译码设备，接收端不具备检、纠错能力强，整体系统纠错能力强，可大大降低整个系统误码率。错能力强，可大大降低整个系统误码率。具有自适应性，但若重发频繁，将使传输效率降低，甚至系统具有自适应性，但若重发频繁，将使传输效率降低，甚至系统阻塞，使得连续性和实时性变差。阻塞，使得连续性和实时性变差。5 5、检错删除：、检错删除：接收端接收端发现错码后，立即将其删除。发现错码后，立即将其删除。适用在发送码元中有大量多余度，删除部分接收码元不影响应适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处。用之处。6 6、差错隐藏：
10、、差错隐藏：在某些应用领域，如音乐、语音、图像、视频等领域，在某些应用领域，如音乐、语音、图像、视频等领域，有差错或损失的部分数据对人的主观感受影响不大，此时，可有差错或损失的部分数据对人的主观感受影响不大，此时，可根据已接收的数据采用内插或外推的技术，得到满足应用的输根据已接收的数据采用内插或外推的技术，得到满足应用的输出数据。出数据。9.2 9.2 纠错码分类纠错码分类1 1、纠错码的分类：、纠错码的分类：n按纠正错误的类型分类：按纠正错误的类型分类：纠随机差错码：纠随机差错码：无记忆信道中，噪声随机独立地影响每个无记忆信道中，噪声随机独立地影响每个码元，造成了随机差错；码元，造成了随机差
11、错；纠突发差错码：纠突发差错码：有记忆信道中，突发噪声可造成突发性的有记忆信道中，突发噪声可造成突发性的成群差错（如太阳黑子、雷电等引起）成群差错（如太阳黑子、雷电等引起）。纠混合差错码纠混合差错码n按应用目的分类：按应用目的分类：检错码检错码只能检测错误是否存在。只能检测错误是否存在。纠错码纠错码能够检测错误，并能够自动纠正错误。能够检测错误，并能够自动纠正错误。纠删码纠删码能够纠正删除（丢失）了的信息。能够纠正删除（丢失）了的信息。n按码元取值分类：按码元取值分类：二元纠错码二元纠错码目前最常用模式目前最常用模式多元纠错码多元纠错码n按码的结构中对信息序列的处理方式分类：按码的结构中对信息
12、序列的处理方式分类：分组码（分组码（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 0个与本组和前个与本组和前L L组信息元相关的校验元，组信息元相关的校验元，得到得到n n长的码字。长的码字。n按码的数学结构中校验元与信息元
13、关系分类：按码的数学结构中校验元与信息元关系分类：线性码线性码线性关系，如线性方程组线性关系，如线性方程组非线性码非线性码非线性关系非线性关系n按码的是否具有循环性分类：按码的是否具有循环性分类：循环码循环码分组码中任一码字的码元经过循环移位后，分组码中任一码字的码元经过循环移位后，仍是本码中的码字。仍是本码中的码字。非循环码非循环码至少有一个码字经循环移位后，不再是本至少有一个码字经循环移位后，不再是本码中的码字。码中的码字。n按构造码的数学理论分类：按构造码的数学理论分类：代数码代数码近世代数，比较完善，如线性分组码。近世代数，比较完善，如线性分组码。几何码几何码投影几何学投影几何学算术码
14、算术码数论，高等算术数论，高等算术组合码组合码排列组合，数论排列组合，数论 实际的码可能同时分别具备以上某些特征，比如：某一纠错码实际的码可能同时分别具备以上某些特征，比如：某一纠错码可以同时是线性码、分组码、循环码、纠随机差错码、二元码、代可以同时是线性码、分组码、循环码、纠随机差错码、二元码、代数码等。数码等。9.3 9.3 纠错码的概念及其纠错能力纠错码的概念及其纠错能力信息序列信息序列码字序列码字序列接收序列接收序列译码后信息序列译码后信息序列噪声源噪声源E E 错误图样错误图样 对编码器的输入信息序列，每对编码器的输入信息序列，每k k个信息符号分成个信息符号分成信息组信息组：m m
15、=（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=(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：码
16、长；：码长；k k：信息组长度；：信息组长度；r r：校验元的位长。：校验元的位长。kqn1 1、信息元、校验元、码字：、信息元、校验元、码字：n码码C C中的码字个数（中的码字个数（k k为信息位数）：为信息位数）：n（n,kn,k）分组码：）分组码：编码器输出为编码器输出为 个码字组成的序列；个码字组成的序列；许用码字许用码字：种码符号序列中，取出种码符号序列中，取出 个作为分组码个作为分组码的码字。的码字。禁用码字禁用码字：其余：其余 种码符号序列。种码符号序列。n卷积码（卷积码（n,kn,k0 0,L,L）:编码器输出的校验元不仅由本组信息元有关，编码器输出的校验元不仅由本组信息元有关
17、，也与其前面若干段的信息组所确定。也与其前面若干段的信息组所确定。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)汉明重量（汉明势）汉明重量（汉明势）：码字中非零码元的个数：码字中非零码元的个数
18、 W(C)W(C)。对对2 2元码，汉明重量为码字中的元码，汉明重量为码字中的“1”1”的个数。因此，二的个数。因此，二元码字的汉明重量和汉明距离为：元码字的汉明重量和汉明距离为：1,0)(10iniiccCW)(),(jijiCCWCCD模模2 2加，若对应位不同加，若对应位不同则为则为1 1；相同则为；相同则为0 0。其重量即为不相同的其重量即为不相同的总位数，也就是两个总位数，也就是两个码字的汉明距离。码字的汉明距离。n3 3、错误图样：、错误图样：码字序列通过信道传输送入译码器之前，由于信道的码字序列通过信道传输送入译码器之前，由于信道的 噪声干扰，使得接收序列中某些码元发生差错，可用
19、噪声干扰，使得接收序列中某些码元发生差错，可用错误错误图样图样（差错图样差错图样）定量描述：）定量描述：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位码元发生差错；位码元发生差错；差错关系差错关系：接收序列接收序列 =许用码字许
20、用码字 +错误图样错误图样 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突发差错突发差错指成串出现的错误指成串出现的错误,错误与错误间有相关错误与错误间有相关性性,一个差错往往要影响到后面一串码元。一个差错往往要影响到后面一串码元。RCEERCECR
21、,例例 发送码字发送码字 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中的第一个中的第一个1 1到最后一个到最后一个1 1，其其错误串中的错误串中的0 0表示该位码元未发生错误。表示该位码元未发生错误。nBS
22、CBSC（二元无记忆对称信道）的错误图样的出现概率（二元无记忆对称信道）的错误图样的出现概率 设设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位随机差错：位随机差错：W(EW(E2 2)=2,)=2,e e位随机差错：位随机差错：W(EW(Ee e)=e,)=e,n n位差错（全错）位差错（全错）W(EW(
23、En n)=n,)=n,0nC1nC2nCenCnnCppEPn 11)(npEP)(0222)(ppEPneeneppEP)(nnpEP)(差错图样数差错图样数概率概率错误图样的错误图样的总数总数：nnnnnnnCCCCC2.e210nnnnpppppp.221)(.)(.)()()(210neEPEPEPEPEP 发生发生多位错误的概率多位错误的概率小于小于较少位数较少位数随机错误的概率。随机错误的概率。因此，因此，无记忆信道无记忆信道中，一般优先纠正较少位数的随机错中，一般优先纠正较少位数的随机错误，如误，如1-21-2位，此时的误码率就可下降几个数量级。位，此时的误码率就可下降几个数量
24、级。错误图样出现的错误图样出现的概率关系概率关系（p1p1）：）：n4 4、分组码的纠错能力与码最小距离的关系、分组码的纠错能力与码最小距离的关系 一般地，分组码的码间最小距离一般地，分组码的码间最小距离 dmin dmin 越大，意味着任越大，意味着任意码字间的差别越大，则码的检、纠错能力越强。意码字间的差别越大，则码的检、纠错能力越强。检错能力检错能力：如果一个分组码能检出如果一个分组码能检出总位数总位数e e 个码元个码元的任何错误的任何错误图样，称码的图样，称码的检错能力为检错能力为 e e。纠错能力纠错能力：如果分组码能纠正如果分组码能纠正总位数总位数t t 个码元个码元的任意错误图
25、样，的任意错误图样，称码的称码的纠错能力为纠错能力为 t t。例例 重复码（重复码（3 3，1 1）为：（）为：（000000，111111），最小码间距为），最小码间距为3 3。两个码字在传输后发生两个码字在传输后发生1 1位错误的接收序列形成两个互不相交位错误的接收序列形成两个互不相交的子集，按照的子集，按照最小距离译码准则最小距离译码准则，就能纠正，就能纠正1 1位随机错误。若发位随机错误。若发生生2-32-3位错误，则接收序列进入另一个子集内，无法纠正。位错误，则接收序列进入另一个子集内，无法纠正。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0
26、,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 个随机错误，则要求个随机错误，则要求 d dminmin 2t+12t+1;或：可纠正任意小于等于或：可纠正任意小于等于 t=INT(d t=INT(dminmin-1)/2-1)/2个随机差错；个随
27、机差错；若能纠正若能纠正 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，否则，会发生码字译码混淆，如，否则，会发生码字译码混淆，如 R+E=V R+E=V。eVUdmin dmin=4,码距和检错能力关系示意图t tVUdmin图 dmin=5,码距和纠错能力关
28、系示意图 设设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)码字，其中码字，其中 (n nk k)个附加码元是由信息码个附加码元是由信息码元的元的线性运算线性运算产生的。产生的。n对于二元码，信息码组长对于二元码，信息码组长 k k 位，有位，有 2 2k k 个不同的
29、信息码组，则有个不同的信息码组，则有 2 2k k 个个码字与它们一一对应。码字与它们一一对应。2 2、一致监督（校验）方程一致监督（校验）方程n编码方法：已知信息码组编码方法：已知信息码组k k位信息位，按预定规则生成位信息位，按预定规则生成 r r 个监督个监督（校验）码元，与信息位一起构成码字。（校验）码元，与信息位一起构成码字。n要求：每个监督元是其中某些信息元的运算结果。要求：每个监督元是其中某些信息元的运算结果。（以下仅讨论二元码）（以下仅讨论二元码）例例：k k=3,=3,r r=4=4，构成，构成 (7,3)(7,3)线性分组码线性分组码。设码字为。设码字为(C C6 6,C
30、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。监督元可按下面方程组计算监督元可按下面方程组计算3642654165054(6.2.1)CCCCCCCCCCCCCn一致监督（校验）方程一致监督（校验）方程 由确定信息元得到监督元规则的一组方程。由于所有码字都按由确定信息元得到监督元规则的一组方程。由于所有码字都按同一规则同一规则确定，又称为一致监督（校验）方程。确定，又称为一致监督（校验）
31、方程。n线性分组码线性分组码 若一致监督方程是若一致监督方程是线性线性的，监督元和信息元之间是线性运算关的，监督元和信息元之间是线性运算关系，所以由监督方程所确定的分组码是系，所以由监督方程所确定的分组码是线性分组码线性分组码。3642654165054CCCCCCCCCCCCC信息组信息组对应码字对应码字0 0 00 0 00 0 0 0 0 0 00 0 0 0 0 0 00 0 10 0 10 0 1 1 1 0 10 0 1 1 1 0 10 1 00 1 00 1 0 0 1 1 10 1 0 0 1 1 10 1 10 1 10 1 1 1 0 1 00 1 1 1 0 1 01
32、0 01 0 01 0 0 1 1 1 01 0 0 1 1 1 01 0 11 0 11 0 1 0 0 1 11 0 1 0 0 1 11 1 01 1 01 1 0 1 0 0 11 1 0 1 0 0 11 1 11 1 11 1 1 0 1 0 01 1 1 0 1 0 000000000000000000000451562456346CCCCCCCCCCCCC前例前例3 3、一致监督（校验）矩阵一致监督（校验）矩阵 为了运算方便，为了运算方便，可可将监督方程写将监督方程写成矩阵形式。成矩阵形式。前例前例：654321065432101011000011101000110001000
33、1100010C0000010110001110100H11000100110001CCCCCCCCCCCCCC 令00TTTCHHCor00000000000000000000451562456346CCCCCCCCCCCCC推广：推广：一般情况，对一般情况，对 (n n,k k)线性分组码，每个码字中的线性分组码，每个码字中的 r r(r r=n nk k)个个监督元与信息元之间的关系可由如下监督元与信息元之间的关系可由如下r r*n n 阶阶线性方程组确定：线性方程组确定：)6.2.6(000022110222212101212111ChChChChChChChChChrnnrnrnnn
34、nnnrnrrnnhhhhhhhhhH.212212111211则：则：00TTTCHorHC021.cccCnnT令：令：.0121hhhhHnnn若用若用h hi i (i=n-1,n-2,1,0)(i=n-1,n-2,1,0)表示表示H H矩阵中的矩阵中的列矢量列矢量，则，则H H可写为：可写为：0.00111111hchchchcnnnnnH H矩阵的矩阵的每一行元素每一行元素是线性方程组中一个方程的系数，由它来是线性方程组中一个方程的系数，由它来唯一确定每一个校验元。因此，唯一确定每一个校验元。因此，H H中中每一行必须是线性无关每一行必须是线性无关的，的，且必定有：且必定有：r=n
35、r=nk k 行。行。0TCH4 4、生成矩阵生成矩阵 根据（根据（n,kn,k）线性分组码的一致监督方程出发，将）线性分组码的一致监督方程出发，将信息组信信息组信息位息位与与生成的码字生成的码字之间的生成关系用矩阵来表示，就可得到之间的生成关系用矩阵来表示，就可得到生生成矩阵。成矩阵。例例 前例中，前例中，3642654165054(6.2.1)CCCCCCCCCCCCC041526,mcmcmc0101210122023041526mmcmmcmmmcmmcmcmcmc0120123456110011111101100010001mmmccccccc10111001110010011100
36、10120123456mmmccccccc生成矩阵生成矩阵G G1 1其各行为码字，互不相关。其各行为码字，互不相关。其他码字为此三个码字的线性其他码字为此三个码字的线性组合方式生成。组合方式生成。信息组信息组对应码字对应码字0 0 00 0 00 0 0 0 0 0 00 0 0 0 0 0 00 0 10 0 10 0 1 1 1 0 10 0 1 1 1 0 10 1 00 1 00 1 0 0 1 1 10 1 0 0 1 1 10 1 10 1 10 1 1 1 0 1 00 1 1 1 0 1 01 0 01 0 01 0 0 1 1 1 01 0 0 1 1 1 01 0 11
37、0 11 0 1 0 0 1 11 0 1 0 0 1 11 1 01 1 01 1 0 1 0 0 11 1 0 1 0 0 11 1 11 1 11 1 1 0 1 0 01 1 1 0 1 0 0n推广推广：对一般：对一般 (n n,k k)线性分组码，设有一组线性分组码，设有一组k k个个线性独立的码字，线性独立的码字，由此一组线性独立的码字以行向量构成的矩阵，称为线性分组由此一组线性独立的码字以行向量构成的矩阵，称为线性分组码的码的生成矩阵生成矩阵G G（k k*n n阶）：阶）：kkkknknknnnngggggCgggggCgggggC).(.).().(012122021221
38、2211011211110121202122121011211121.kkknknnnnnkgggggggggggggggG满足：满足：)2,.,2,1(,),(kiiiiknCGmC码nG G中每一行及其线性组合都是中每一行及其线性组合都是许用码字许用码字，故有：，故有：阶零矩阵。阶零矩阵。为为)(,0,0knkGHorHGTTT0 线性分组码的所有码字都可由其生成矩阵或一致校验矩阵求线性分组码的所有码字都可由其生成矩阵或一致校验矩阵求得。当已知得。当已知G G、H H中的一个，就可求另一个。中的一个，就可求另一个。n系统码：系统码：信息元以不变形式出现在码字的任意信息元以不变形式出现在码字
39、的任意k k位上。位上。n标准生成矩阵：标准生成矩阵：生成矩阵能把信息元保留在各码字的生成矩阵能把信息元保留在各码字的最左边最左边k k位位上。上。|)(knkkPIG|)(knTknkIPH0TGH 因此，因此，标准系统生成矩阵标准系统生成矩阵G G应满足如下形式：应满足如下形式：其与其与H H矩阵之间的转换关系：矩阵之间的转换关系：若非标准系统码，则若非标准系统码，则G G与与H H之间元素需要由方程组确定。之间元素需要由方程组确定。(略略)生成矩阵之间的关系生成矩阵之间的关系 对于二元（对于二元（n,kn,k）分组码，在）分组码，在2 2k k个码字中，个码字中，k k个个独立码字组独立
40、码字组不不止一个。对于同一码，选择不同的独立码字组构成生成矩阵止一个。对于同一码，选择不同的独立码字组构成生成矩阵G G也也不相同。但经过若干次不相同。但经过若干次初等变换初等变换，可变成等价的，可变成等价的标准生成矩阵标准生成矩阵。例例 一个二元（一个二元（7 7，3 3）码）码,生成矩阵为：生成矩阵为：0010111110010101110012G信信息息组组000001010011100101110111码码字字00000001110100101001101001111001110011101000111011101001生成的码字为：生成的码字为：信信息息组组0000000010010
41、10010011011100100101101110110111111码码字字0000000000000011111101000100101101001100110100100111011110010011101110011011101010100010011101110111011010011001码字集合完全相同。码字集合完全相同。但生成矩阵但生成矩阵G1G1、G2G2选取了不同的独立码字构成。选取了不同的独立码字构成。生成矩阵生成矩阵可以经过初等行变换可以经过初等行变换得到其得到其标准标准生成矩阵生成矩阵。比较：生成矩阵比较：生成矩阵G G2 2产生的码（非系统码）产生的码（非系统码）比
42、较：生成矩阵比较：生成矩阵G G1 1产生的码（系统码）产生的码（系统码）1011100111001001110011G0010111110010101110012G2 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）封闭性。（）封闭性。
43、（n,kn,k）码中任意两个码字之和仍为许用码字，）码中任意两个码字之和仍为许用码字，即：即：),(,),(,knCCCknCCkjiji则若字。）线性分组码的许用码为（即knCHCHCHCHCHCCHCHCTTjTiTkTjiTjTi,00)(,0,0kk3 3）含有零码字。）含有零码字。n n位长的零矢量为（位长的零矢量为（n,kn,k）线性分组码的许用码字。）线性分组码的许用码字。（因为满足（因为满足 ）00TTHCH4 4）所有许用码字可由其中）所有许用码字可由其中k k个独立码字（基底）线性组合而成。个独立码字（基底）线性组合而成。在在 个许用码字中，个许用码字中，k k个独立许用码
44、字不止一组。它们可个独立许用码字不止一组。它们可构成生成矩阵构成生成矩阵G G。k25 5）码的最小距离等于非零码字的最小重量。即：）码的最小距离等于非零码字的最小重量。即：0),(,)(minminiiiCknCCWd因为：因为：),(,0)(min),(,)(min),(,),(minminknCCCWknCCCCCCWknCCCCCCDdkkkjijijijijiji，封闭性定理定理 设（设（n,kn,k）线性分组码）线性分组码C C的校验矩阵为的校验矩阵为H H，则码的最小距离为，则码的最小距离为d d的的充要条件充要条件为：为：H H中任意中任意d-1d-1个列向量线性无关，且有个列
45、向量线性无关，且有d d个列向量个列向量线性相关。线性相关。（提供了构造最小距离为（提供了构造最小距离为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 矩阵所对应的分组码，矩阵所对应的分组码，具有相同的具有相同的最小距离
46、最小距离，则它们在纠错能力和码率上等价。，则它们在纠错能力和码率上等价。u对于分组码来说，由于可以进行对于分组码来说，由于可以进行初等变换初等变换进行等价变换，进行等价变换，系统码系统码和和非系统码非系统码的纠错能力是相同的，而系统码的编译码比非系统码简的纠错能力是相同的，而系统码的编译码比非系统码简单，且单，且G G、H H矩阵可方便互求，因此，一般只需讨论系统码。矩阵可方便互求，因此，一般只需讨论系统码。例例6 6、线性分组码的纠错与伴随式、线性分组码的纠错与伴随式：接收到一个序列接收到一个序列 R R 后，校验后，校验 H H R RT T=0=0T T 是否成立：是否成立：n若关系成立
47、，则认为若关系成立，则认为 R R 是一个码字；是一个码字；n否则判为码字在传输中发生了错误；否则判为码字在传输中发生了错误；伴随式（伴随式（/监督子监督子/校验子）校验子）：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,
48、n2,02,0。接收序列接收序列 R R：R R=(=(r rn 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 即：即：分析分析：001
49、1221101210121.eheheheheeeehhhhHESnnnnnnnnTTn对于对于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
50、，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 H HT T=（00000000），无法发现此错误；），无法发现此错误；若若发送码矢发送码矢C C1 1=0100111=0100111，C C2 2=1101001=1101001，错误图样错误图样 E E1 1=（10000001000000），），接收码字接收码字 R R1 111001111100111
