第六章 信道编码

1、第6章 信道编码信息论与编码信息论与编码u信道模型1 1离散信道的数学模型离散信道的数学模型u根据信道的统计特性即条件概率根据信道的统计特性即条件概率P(y|x) 的不同，离散信道可以的不同，离散信道可以分为三种情况：分为三种情况： （1）无干扰信道）无干扰信道 （2）有干扰无记忆信道）有干扰无记忆信道 （3）有干扰有记忆信道）有干扰有记忆信道信道有关概念回顾YX信道信道输入信号输入信号输出信号输出信号图图6.1 离散信道模型离散信道模型 条件概率反映信条件概率反映信道的统计特性道的统计特性 1)|(xyP),.,(21NYYYY ),.,(21NXXXX )|(xyP2 2单符号离散信道的数

2、学模型单符号离散信道的数学模型单符号离散信道的输入变量为单符号离散信道的输入变量为X X，取值于，取值于a1, a2, ,ar，输出变，输出变量为量为Y Y，取值于，取值于b1, b2, , bs，并有，并有条件概率条件概率( (信道的传递概信道的传递概率率) ) ：P(y|x)= P(y=bj|x=ai) = P(bj |ai) (i=1,2,r；j=1,2, , s)模型：模型：P(bj |ai) 图图6.2 6.2 单符号离散信道单符号离散信道aaaXr21Ybbbs21一般离散单符号信道的传递概率可用以下形式的矩一般离散单符号信道的传递概率可用以下形式的矩阵来表示阵来表示(信道转移概率

3、信道转移概率)： 并满足式并满足式 。sjijriabP1), 2 , 1(1)|( b1 b2 bsP(b1|a1) P(b2|a1) P(bs|a1)P(b1|a2) P(b1|a2) P(bs|a2)P(b1|a2) P(b1|a2) P(bs|a2)a1 a2a3定义定义6.1 已知发送符号已知发送符号 ai ，通过信道传输接收到的，通过信道传输接收到的符号为符号为 bj 的概率的概率 P( (bj|ai) )称为称为前向概率前向概率。已知信道输。已知信道输出端接收到的符号为出端接收到的符号为 bj，而发送符号为，而发送符号为 ai 的概率的概率P(ai|bj)称为称为后向概率后向概率

4、。u有时，也把有时，也把 P( (ai) )称为输入符号的称为输入符号的先验概率先验概率( (即在接即在接收到一个输出符号收到一个输出符号以前以前输入符号的概率输入符号的概率) )，而对应地，而对应地把把 P( (ai|bj) )称为输入符号的称为输入符号的后验概率后验概率( (即在接收到一即在接收到一个输出符号个输出符号以后以后输入输入符号的概率符号的概率) ) 。u信道疑义度和平均互信息1. 1. 先验熵先验熵信道输入信号信道输入信号X 的熵的熵H(X) 是在接收到输出是在接收到输出Y 以前，关于输入以前，关于输入X X的先验不的先验不确定的度量，称为确定的度量，称为先验熵先验熵。如果信道

5、中如果信道中无无干扰（噪声），接收到传送过来的干扰（噪声），接收到传送过来的符号后就消除了对发送符号的先验不确定性。符号后就消除了对发送符号的先验不确定性。但一般信道中但一般信道中有有干扰存在，接收到输出干扰存在，接收到输出Y 对发送的对发送的是什么符号仍有不确定性。是什么符号仍有不确定性。XriiixPxPaPaPXH)(log)()(1log)()(12. 2. 信道疑义度信道疑义度( (条件熵条件熵) )信息疑义度表示在输出端收到输出变量信息疑义度表示在输出端收到输出变量Y 的符号的符号后，对于输入端的变量后，对于输入端的变量X X 尚存在的平均不确定性尚存在的平均不确定性( (即存在疑

6、义即存在疑义) )。 这个对这个对X 尚存在的不确定性是由干扰尚存在的不确定性是由干扰( (噪声噪声) )引起引起的。的。如果是一一对应信道，那么接收到输出如果是一一对应信道，那么接收到输出Y 后，对后，对X 的不确定性将完全消除，则信道疑义度的不确定性将完全消除，则信道疑义度 H(X|Y)=0。XYyxPxyPYXH)|(1log)()|(3.3. 平均互信息平均互信息定义定义6.3 6.3 称称 I(X;Y)= H(X)-H(X|Y) 为为X X 和和Y Y 之间的之间的平均互信息平均互信息。平均互信息平均互信息表示接收到输出符号表示接收到输出符号Y 后平均每个符后平均每个符号获得的关于输

7、入变量号获得的关于输入变量X 的信息量。的信息量。经过推算得出：经过推算得出： 其中其中X是输入随机变量，是输入随机变量，Y是输出随机变量是输出随机变量 平均互信息用于表示传输信息率。平均互信息用于表示传输信息率。XYyPxyPxyPYXI)()|(log)();(u信道编码定理：信道编码定理：若有一离散无记忆平稳信道，其若有一离散无记忆平稳信道，其容量为容量为 C，输入序列长度为，输入序列长度为 L，只要待传送的信，只要待传送的信息率息率 RC，总可以找到一种编码，当，总可以找到一种编码，当 L 足够长时，足够长时，译码差错概率译码差错概率PeC时，任何编码的时，任何编码的 Pe 必大于零，

8、当必大于零，当 L，Pe1。u信道编码定理说明：信道编码定理说明：同无失真信源编码定理类似，同无失真信源编码定理类似，信道编码定理也是一个理想编码的存在性定理。信道编码定理也是一个理想编码的存在性定理。它指出信道容量是一个临界值，只要信息传输率它指出信道容量是一个临界值，只要信息传输率不超过这个临界值，信道就可几乎无失真地把信不超过这个临界值，信道就可几乎无失真地把信息传送过去，否则就会产生失真。息传送过去，否则就会产生失真。u在数字通信中，根据不同的目的，编码可分为信在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。源编码和信道编码。信源编码信源编码是为了提高数字信是为了提高数字信

9、号的有效性以及为了使模拟信号数字化而采取的号的有效性以及为了使模拟信号数字化而采取的编码。编码。信道编码信道编码是是为了降低误码率，为了降低误码率， 提高数字通提高数字通信的可靠性而采取的编码。信的可靠性而采取的编码。u 数字信号在传输过程中，加性噪声、码间串扰数字信号在传输过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，等都会产生误码。为了提高系统的抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。采用信道编码技术。6.1 信

10、道编码的概念信道编码的概念6.1.1 6.1.1 信道编码的作用和分类信道编码的作用和分类信道编码是以信息在信道上的正确传输为目标的编信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：码，可分为两个层次上的问题：u如何正确接收载有信息的信号如何正确接收载有信息的信号线路编码线路编码u如何避免少量差错信号对信息内容的影响如何避免少量差错信号对信息内容的影响纠纠错编码错编码广义信道编码广义信道编码=特定信道上传输信息而进行的传输特定信道上传输信息而进行的传输信号或信号格式的设计与实现信号或信号格式的设计与实现 广义信道编码有如下分类广义信道编码有如下分类: 描述编码描述编码

11、用于对特定数据信号的描述用于对特定数据信号的描述 约束编码约束编码 用于对特定信号特性的约束用于对特定信号特性的约束 扩频编码扩频编码 用于扩展信号频谱为近似白噪声谱并用于扩展信号频谱为近似白噪声谱并满足某些相关特性满足某些相关特性 纠错编码纠错编码 用于检测与纠正信号传输过程中因噪用于检测与纠正信号传输过程中因噪声干扰导致的差错声干扰导致的差错1234所有频率具有相同所有频率具有相同能量的随机噪声称能量的随机噪声称为白噪声为白噪声 信号的频谱一般是针对确定信号的频谱一般是针对确定性信号而言性信号而言, , 它描述了信号它描述了信号在各个频率上的分布大小。在各个频率上的分布大小。 011011

12、,0,1, 0,1ninicccccrrrrr消息消息crm 信道编码信道编码 编码信道编码信道 信道译码信道译码 m码码字字接收接收向量向量消消息息编码信道模型编码信道模型6.1.2 编码信道编码信道 当码字c和接受向量R均由二元序列表时，称编码信道为二进制信道. c=(c0,c1,cn-1)如果对于任意的n都有： p(r/c)=p(ri/ci)则称此二进制信道为无记忆二进制信道。 p(0/1)=p(1/0)=pb则称此信道为无记忆二进制对称信道，简称记忆二进制对称信道，简称BSC.错误传输错误传输概率一样概率一样BSC转移概率转移概率BSC编码信道编码信道mod2(1), (0) 1bbr

13、c ep ep p ep BSC输入输出关系等效为输入输出关系等效为e=1表示差表示差错错,e=0表示正确表示正确u差错图案：差错图案：指指n长的长的随机序列随机序列e=(e0,e1, en-1). iu称称e=(e0,e1, en-1)中中ei=1为为第第i位上的一个随机错误位上的一个随机错误. . u第第i i至第至第j j位之间有很多错误时位之间有很多错误时, ,称为一个称为一个j-i+1长的长的突发错误突发错误.发送序列c: (1111011000)接收序列的r: (0110010110)比较c和r，可写出另一个序列e：1001001110r = c + e (mod 2)或e = r

14、+c (mod 2)如如:i对于一个对于一个BSCBSC信道总有转移概率信道总有转移概率 1/21/2， 比比特传输中发生差错数目越少，概率越大，即特传输中发生差错数目越少，概率越大，即 bpnnbtnbtbnbbnbpppppp1111从而总认为发生差错的图案是差错数目较少的图案从而总认为发生差错的图案是差错数目较少的图案( (概率大的事件发生概率大的事件发生, ,可以利用此进行纠错可以利用此进行纠错) ) u二元软判决信道二元软判决信道 用多个比特（理想情况下为实数）表示每一个无记忆用多个比特（理想情况下为实数）表示每一个无记忆编码信道的二元符号输出编码信道的二元符号输出, ,此时的二元此

15、时的二元无记忆编码信道无记忆编码信道,称称为为二元软判决信道二元软判决信道 . 信道干扰信道干扰z z为零均值正态分布的随机变量，为零均值正态分布的随机变量，噪声干扰功率为均方差噪声干扰功率为均方差 ，z z的概率分布为的概率分布为 。对于对于BPSKBPSK调制，二元输入符号调制，二元输入符号 为二元符号取为二元符号取值为值为+1+1或或-1. -1. 2)(zpczcr2221( ) , 2zp zez 6.1.3 检错与纠错的基本原理u为了使原信息能正确地传送到接收方，可以在为了使原信息能正确地传送到接收方，可以在信息传送前进行一次抗干扰编码信息传送前进行一次抗干扰编码(即即检错编码检错

16、编码与纠错编码纠错编码)，再传送抗干扰编码后的数字信，再传送抗干扰编码后的数字信息。息。检纠错是根据信道输出序列检纠错是根据信道输出序列r来判断是否来判断是否可能是发送的可能是发送的c，或纠正导致，或纠正导致r不等不等c的错误。的错误。u冗余编码：冗余编码：为了实现检纠错为了实现检纠错,所以码字所以码字c的长度的长度n一定大于消息一定大于消息m的长度的长度k。110,kmmmm110,ncccc纠错编码纠错编码u编码码率编码码率R ：每个码字的序列符号（或码元）：每个码字的序列符号（或码元）平均传送的消息比特数平均传送的消息比特数,称为编码码率称为编码码率: nkR/对检纠错码的基本要求是对检

17、纠错码的基本要求是: 检错和纠错能力尽量强；检错和纠错能力尽量强； 编码效率尽量高；编码规律尽量简单。编码效率尽量高；编码规律尽量简单。 实际中要根实际中要根据具体指标要求，据具体指标要求， 保证有一定纠、保证有一定纠、 检错能力和编检错能力和编码效率，并且易于实现。码效率，并且易于实现。 例例6.1 偶（或奇）校验方法：偶（或奇）校验方法：实现检纠错目的的一个实现检纠错目的的一个基本方法。基本方法。一个偶校验位一个偶校验位p是对消息是对消息m使得如下校验方使得如下校验方程成立的二进制符号，即程成立的二进制符号，即 : )2(mod01210pmmmmk)2(mod110kmmmp称称c=m0

18、,m1, mk-1,p一个偶校验码码字一个偶校验码码字, ,所有可能的所有可能的c的全体的全体C称为一个码率为称为一个码率为 k/(k+1)的的(k+1,k)的偶校验码的偶校验码.c下面介绍两个简单的检错编码的例子下面介绍两个简单的检错编码的例子:或或:也就是说也就是说:如果是如果是偶校验码偶校验码，在附加上一个校验位以后，在附加上一个校验位以后，码长为码长为n的码字中的码字中“1”的个数为偶数个的个数为偶数个;如果是如果是奇校验奇校验码码，在附加上一个校验位以后，码长为，在附加上一个校验位以后，码长为n的码字中的码字中“1”的个数为奇数个的个数为奇数个. 编码可以产生多个奇偶校验位，即一个校

19、编码可以产生多个奇偶校验位，即一个校验位可以由消息位的部分或全部按某种校验方验位可以由消息位的部分或全部按某种校验方程产生，例如对阵列消息进行垂直与水平校验程产生，例如对阵列消息进行垂直与水平校验以及总校验的码字以及总校验的码字c和其码率分别为和其码率分别为: tstsststssttppppmmpmmc,1,0, 11, 10, 1, 01, 00, 0,为了增为了增强校验强校验能力能力sttstsststR11112 mod 1, 1 , 0 2, mod 1, 1 , 0 2, mod 10,10,10,10,tjjssititssijijstjjitimmptjmpsimp编码码率编码

20、码率:u如如:1 1 0 0 1 0 1 0 0 00 1 0 0 0 0 1 1 0 10 1 1 1 1 0 0 0 0 11 0 0 1 1 1 0 0 0 01 0 1 0 1 0 1 0 1 000101 1 1 0 0 0 1 1 1 1 0 002 mod ,.1, 11, 1 , 0 2, mod ,.0, 01, 1 , 0 2, mod 10,10,1 ,0 ,10, 1, 010,tjjssititssssijijstttjjitimmppptjmpppsimp 例例6.2 6.2 重复消息位：重复消息位： 在发送端把消息重复发几遍，可使接收端接收消在发送端把消息重复发几

21、遍，可使接收端接收消息时错误减少，从而提高通信的可靠性。如：在二元息时错误减少，从而提高通信的可靠性。如：在二元对称信道中，当发送符号对称信道中，当发送符号0时，不是只发一个时，不是只发一个0而是连而是连续发三个续发三个0；同样，发送符号；同样，发送符号1时也连续发送三个时也连续发送三个1。于。于是信道输入端有两个码字是信道输入端有两个码字000和和111。u一个一个(n,k)重复码是一个码率为重复码是一个码率为1/n的码，仅有两个码字的码，仅有两个码字 c0和和c1,传送传送1比特（比特（k=1）消息。）消息。111,00010ccn重复码可以重复码可以检测检测出任意小于出任意小于n个差错的

22、错个差错的错误图案，误图案，纠正纠正任意小于任意小于 n/2 个差错的错误图案。个差错的错误图案。纠纠n/2 =1 1位差错位差错的的3 3重复码重复码 ,关于关于这点这点,下面再说下面再说.例例6.3 恒比码方法：恒比码方法： 码字中 1 的数目与 0 的数目保持恒定比例的码称为恒比码。 由于恒比码中，每个码组均含有相同数目的 1 和 0，因此恒比码又称等重码。这种码在检测时，只要计算接收码元中 1 的数目是否正确，就知道有无错误。 目前我国电传通信中普遍采用 32 码，又称“5 中取 3”的恒比码，即每个码组的长度为 5，其中 3 个“1”。这时可能编成的不同码组数目等于从 5 中取 3

23、的组合数 10，这 10 个许用码组恰好可表示 10 个阿拉伯数字(0-9)，在汉字电报码中,每个汉字又是以四位十进制数来代表的。实践证明，采用这种码后，我国汉字电报的差错率大为降低。 表表 10-1 32 10-1 32 恒比码恒比码 5:3恒比码恒比码 22log15log0.6635nmRn5 5中取中取3 3等重码可以检测出等重码可以检测出全部奇数位差错，因为只全部奇数位差错，因为只要奇数位有错要奇数位有错,1,1的个数就的个数就不为不为3;3;对某些码字的传输对某些码字的传输则可以检测出部分偶数位则可以检测出部分偶数位差错差错n:m的码率为的码率为:二进制位数二进制位数,即需要的最即

24、需要的最大信息位数大信息位数.6.1.4 6.1.4 差错控制方式差错控制方式 和能力和能力图 10-1 差错控制方式 发端纠错码收端前向纠错FEC发端检错码收端检错重发ARQ判决信号发端检错和纠错码收端混合纠错HEC判决信号n差错控制方式差错控制方式 1. 1. 检错重发方式检错重发方式 检错重发又称自动请求重传方式，记作ARQ(Automatic Repeat Request)。 由发端送出能够发现错误的码，由收端判决传输中无错误产生，如果发现错误，则通过反向信道把这一判决结果反馈给发端，然后，发端把收端认为错误的信息再次重发，从而达到正确传输的目的。其特点是需要反馈信道，译码设备简单，对

25、突发错误和信道干扰较严重时有效， 但实时性差，主要在计算机数据通信中得到应用。 2. 前向纠错方式前向纠错方式 前向纠错方式记作FEC(Forword ErrorCorrection)。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。其特点是单向传输，实时性好，但译码设备较复杂。 3. 混合纠错方式混合纠错方式 混合纠错方式记作HEC(Hybrid ErrorCorrection)是FEC和ARQ方式的结合。发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力， 但能检测出来，则经过反馈信道请

26、求发端重发。这种方式具有自动纠错和检错重发的优点，可达到较低的误码率，因此， 近年来得到广泛应用。 另外，按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。具有脉冲干扰的信道是典型的突发信道， 错误是成串成群出现的，即在短时间内出现大量错误。短波信道和对流层散射信道是混合信道的典型例子，随机错误和成串错误都占有相当比例。对于不同类型的信道，应采用不同的差错控制方式。 先给出汉明距离的概念:定义定义: 设X=(x1,x2,xn)，Y=(y1,y2,yn)，xiF2，yiF2，i=1,n，

27、称 X 和 Y 对应分量不相等的分量个数为X 和Y 的汉明汉明(Hamming) )距离距离，记为d(X, Y)。定理定理: 设 X 和Y 是长为 n 的二元码字，则（1）0d(X, Y) n （非负且有界性）（2）d(X, Y)=0 当且仅当 X=Y（自反性）（3）d(X, Y)=d(Y, X)（对称性）（4） d(X, Z) d(X, Y)+ d(Y,Z) （三角不等式）n差错控制能力差错控制能力二元数域二元数域F2=0,1的异或运算：的异或运算：F2的加法运算：的加法运算：0+0=0， 0+1=1， 1+0=1， 1+1=0F2的乘法运算：的乘法运算：00= 01=10=0， 11=1例

28、如 11000 与 10011之间的距离d=3。码组集中任意两个码字之间距离的最小值称为码的最小距离，用dmin表示。u最小码距是码的一个重要参数， 它是衡量码检错、纠错能力的依据。下面定理给出了检纠错能力: dmin=mind(X,Y)|X,YC, XY定理定理 对一个最小距离为对一个最小距离为dmin纠错码，如下结论纠错码，如下结论成立成立: （1 1） 可以检测出任意小于等于可以检测出任意小于等于l个差错个差错,其中其中: :1min dl（2 2） 可以纠正任意小于等于可以纠正任意小于等于t个差错个差错,其中其中:21mindt（3 3）可以检测出任意小于等于可以检测出任意小于等于l同

29、时纠正小于同时纠正小于等于等于t个差错，其中个差错，其中l和和t满足满足: :ltdtl1min最小码距与检纠错能力最小码距与检纠错能力 n 编码增益编码增益 实际的通信系统，信号的传送需要一定的信噪比实际的通信系统，信号的传送需要一定的信噪比 Eb/N0，它直接影，它直接影响信道转移概率的大小，误码率响信道转移概率的大小，误码率 pbe与信噪比与信噪比 Eb/N0 的关系如图所示，的关系如图所示，当采用纠错码之后，达到同样的误码率需要的信噪比减小量称为编码当采用纠错码之后，达到同样的误码率需要的信噪比减小量称为编码增益。增益。降价了降价了信噪比信噪比n检纠错码的分类检纠错码的分类 (1) 根

30、据纠错码各码组冗余位和信息元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。 (2) 根据上述关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关， 而且还与前面若干组的信息元有关。 (3) 根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。 汉明码循环码线性分组码非线性分组码分组码线性卷积码非线性卷积码卷积码信道编码 关于分组码的纠错能力说明关于分组码的纠错能力说明: : 分组码一般可用(n,k)表示。其中，k是每组二进

31、制信息码元的数目，n是编码码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的冗余位数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个冗余位， 组成长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余 2n-2k个码字未被选用，称为禁用码组。 d1d2d3dkc1c2c3ckcnn位线性分组码元k位信息码元n k位监督码元(冗余码元)2. 2. 检错和纠错能力检错和纠错能力 若分组码码字中的冗余位在信息元之后，而且是信息元的简单重复， 则称该分组码为重复码。它是一种简单实用的检错码， 并有一定的纠错能力。u例如(2

32、,1)重复码，两个许用码组是 00 与 11，dmin=2，收端译码，出现 01、10 禁用码组时，可以发现传输中的一位错误。u如果是(3,1)重复码，两个许用码组是 000 与111, dmin=3; 当收端出现两个或三个 1 时，判为 1，否则判为 0。此时，可以纠正单个错误，或者可以检出两个错误。 检错能力与纠错能力进一步解释检错能力与纠错能力进一步解释1、码距为1时，能保证码字的唯一性，但不能检错和纠错。2、码距为2时，能检查出一位错误，但无法纠错。许用码组：00，11禁用码组：01，10能够发现一个错误，但不能纠正错误如上例中如上例中:3、码距为、码距为3时，能检查出一位或两位错误，

33、并且还可纠正时，能检查出一位或两位错误，并且还可纠正一位错误。一位错误。例：设码长为例：设码长为3，取，取000、111作为码字，其余为禁用码字。作为码字，其余为禁用码字。如接收端收到如接收端收到001，它是禁用码字，知道出错，由于，它是禁用码字，知道出错，由于001与与000相差一个码元，与相差一个码元，与111相差两个码元，根据最大似然译相差两个码元，根据最大似然译码原则将码原则将001译为译为000，因为根据前面的结论：，因为根据前面的结论： P(001/000)大于大于P(111/000)。最大似然译码原则：最大似然译码原则：当当ci为若干个发送码字中的一个，为若干个发送码字中的一个，

34、r为接收码字，若条件概率为接收码字，若条件概率P(r/ci)为最大，则认为码字为最大，则认为码字ci就是发送码字。就是发送码字。 码距的几何意义：以n = 3的编码为例 一般而言，码距是 n 维空间中单位正多面体顶点之间的汉明距离。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1l预备知识-有限域上的线性空间定义定义 是二元域F2上的 n 维线性空间。定义定义6.11 设C是F2上n维线性空间V的非空子集，如果C也是F2上的线性空间，则称C是V 的子空间子空间。定义定义6.15 设 , 称 为 X 与Y 的内积；如果

35、XY=0，则称 X 与 Y 正交。, 1,| ),(2212niFaaaaFinn6.2 线性分组码nnFxxxX221,nnFyyyY221,T21212211),(XYyyyxxxyxyxyxYXnnnn定理定理6. 5 设C是F2上线性空间的子空间，令 则C是 的子空间子空间（称为C的正交补子空间）， 且 。 , 0|2nFCCnF2nCCdimdim6.2.1 6.2.1 线性分组码的描述线性分组码的描述 相应的信息码组行向量和分组码码组行向量为相应的信息码组行向量和分组码码组行向量为 c=c1,c2,cn m=d1,d2,dk 则一个分组码组的前则一个分组码组的前k位是信息码元，后位

36、是信息码元，后n-k位是位是监督码元（设监督码元位数为监督码元（设监督码元位数为r，则有，则有r=n-k），每一），每一个分组码组可以由个分组码组可以由信息码元线性组合信息码元线性组合而成而成.d1d2d3dkc1c2c3ckcnn位 线 性 分 组 码 元k 位 信 息 码 元nk 位 监 督 码 元 (冗 余 码 元 )一个（一个（n,k）线性分组码）线性分组码C是称为码字是称为码字c的的n维向维向量的集合量的集合: C=c| c=mG其中其中m为任意的为任意的k维向量并称为维向量并称为消息向量。消息向量。G是是k行行n行列秩为行列秩为k（nk）的矩阵并称为）的矩阵并称为生成矩阵生成矩阵:

37、nknkknggggG,1 , 11 , 1.行向量行向量线性无线性无关关对每一个信息组对每一个信息组m，由矩阵，由矩阵G都可以求得都可以求得 (n,k) 线性线性码对应的码字。码对应的码字。对于对于二元二元编码，编码， 和和 是二元向量，是二元向量， 是一个是一个二元矩阵，二元矩阵， ，向量与矩阵，矩阵与矩阵，向量与矩阵，矩阵与矩阵之间的基本运算是模二加和模二乘运算。之间的基本运算是模二加和模二乘运算。 cmG1 ,0ijg表表6.2.1 6.2.1 模二加模二加/ /乘法表乘法表 例例6.2.1 6.2.1 3 3重复码是一个（重复码是一个（3 3，1 1）线性分组码）线性分组码 111G

38、0000012,111,mmmmccc例例6.2.26.2.2（4 4，3 3）偶校验码是一个（）偶校验码是一个（4 4，3 3）线性分）线性分组码组码110010101001G 2102102100123,110010101001,mmmmmmmmmcccc例例6.2.3: (7,4) 线性码的生成矩阵为线性码的生成矩阵为)1010011(11010000110100111001010100010101)1010(11010000110100111001010100017441714174GmCmG，则若线性分组码有如下性质：线性分组码有如下性质：零向量零向量(0,0,0)一定是一个码字，称

39、为零码字一定是一个码字，称为零码字(当当m为零向量时为零向量时)；任意两码字的和仍是一个码字任意两码字的和仍是一个码字(封闭性封闭性,当当m向量向量只有两个只有两个1时时)；任意码字任意码字C 是是G 的行向量的行向量(g1,g2,gk)的线性组合的线性组合: 设设C是是n,k线性码，则恰好含有线性码，则恰好含有2k 个码字。设个码字。设 是是C的生成矩阵，对的生成矩阵，对 c C，则存在惟一一组常数，则存在惟一一组常数(其实其实就是信息序列就是信息序列) (m0, , mk-1) F2 ，使，使:TkgggG,.,21kkkkgggmmmgmgmgmc.,.,.2111012110 G中每一

40、行中每一行 gi=(gi,1,gi,2, gi,n ) 都是一个码字都是一个码字(当当m向量只有一个向量只有一个1时时) ； (n,k) 线性码的每一个码字都是生成矩阵线性码的每一个码字都是生成矩阵 G 的的行矢量的线性组合，所以它的行矢量的线性组合，所以它的 2k 个码字构成个码字构成了由了由 G 的行张成的的行张成的 n 维空间的一个维空间的一个 k 维子空维子空间间 Vk。nknkknkgggggggG,1 , 11 , 121. cwcd minmin线性分组码的最小距离等于非零码字线性分组码的最小距离等于非零码字最小最小重量重量: : 该最小重量也称该最小重量也称汉明重量汉明重量.上

41、述结论给出了上述结论给出了最小最小距离距离与最小重量最小重量的关系：线性分组码的最小距离等线性分组码的最小距离等于它的最小重量。于它的最小重量。最小距离决定了检纠错能力最小距离决定了检纠错能力,因为它体现了码字因为它体现了码字之间的差别之间的差别. 码字重量就是码字码字重量就是码字中含中含“1”的个数的个数,如如码字码字 10110，码重，码重w=3。 例例:编码表编码表 从表中可见非零码组的最小码重为从表中可见非零码组的最小码重为3，则分组码的最小，则分组码的最小码距码距dmin=3，根据前面的结论可知，根据前面的结论可知:该分组码能够检该分组码能够检2位错，位错，纠纠1位错，或同时纠位错，

42、或同时纠1位错检位错检1位错。位错。r由偶校验码的检错概念，可以通过计算接收向量的所有由偶校验码的检错概念，可以通过计算接收向量的所有校验方程值是否为校验方程值是否为0来判断传输是否可能有错，那么必来判断传输是否可能有错，那么必有一个矩阵有一个矩阵H满足满足: TTHccH或显然显然 的每一列或的每一列或 的每一行确定了一个可的每一行确定了一个可能的分组码的校验方程，能的分组码的校验方程， 的线性不相关行数的线性不相关行数最少要等于该码的所有可能的校验方程数，称最少要等于该码的所有可能的校验方程数，称这样的这样的 矩阵矩阵 为为 线性分组码的一致校线性分组码的一致校验矩阵。验矩阵。 THHrn

43、rHkn,HnrrnhhhhH,1 , 11 , 1 通俗地理解：通俗地理解：在(n,k)分组码中，若每一个监督元(校验位)都是码组中某些信息元按模二和而得到的，即监督元是按线性关系相加而得到的， 所以称线性分组码。或者说，可用线性方程组表述码规律性的分组码称为线性分组码。 现以(7,3)分组码为例来说明线性分组码的特点。设其码字为A=c6 c5 c4 c3 c2 c1 c0 ，其中前 3 位是信息元，后4 位是监督元， 可用下列监督线性方程组(校验方程组)来描述该分组码，产生监督元： 4505614562463ccccccccccccc关于一致校验矩阵关于一致校验矩阵(一致监一致监督矩阵督矩

44、阵)举例举例u例如：例如：u信息码组信息码组 (101)，即，即c6=1, c5=0, c4=1u代入代入 监督方程监督方程 得：得： c3=0, c2=0, c1=1, c0=1u由信息码组由信息码组 (101) 编出的码字编出的码字为为 (1010011)。其它。其它7个码字如个码字如表表6.2.1。u为了运算方便，为了运算方便，将监督方程写成将监督方程写成矩阵形式，得矩阵形式，得:6543210654321010110000111010001100010001100010C0000010110001110100H11000100110001CCCCCCCCCCCCCC 令00000000

45、000000000000451562456346CCCCCCCCCCCCCu系数矩阵 H 的后四列组成一个 (44) 阶单位子阵，用 I4 表示，H 的其余部分用 P 表示4 347 34 3410110001110100PI11000100110001HPI( , )所以u推广到一般情况：推广到一般情况：对对 (n,k) 线性分组码，每个码字中的线性分组码，每个码字中的 r(r=nk) 个监督元与信息元之间的关系可由下面的线性个监督元与信息元之间的关系可由下面的线性方程组确定方程组确定) 6 . 2 . 6 (000022110222212101212111ChChChChChChChChC

46、hrnnrnrnnnnnnu令上式的系数矩阵为 H，码字行阵列为 C11121212221211201111H(6.2.7)C(6.2.6)HC0CH0(6.2.8)H( , )nnr nrrrnnnnTTTr nnrnn rrhhhhhhhhhCCCn k式可写成或称 为线性分组码的一致监督矩阵，简称监督矩阵。一般一般H矩阵和矩阵和G矩阵一样矩阵一样,每行之间是彼此线性无关的每行之间是彼此线性无关的10.3 10.3 线线 性性 分分 组组 码码 u下面分析一下生成矩阵和校验矩阵的关系:(课堂练习) 现以(7,4)分组码为例来说明线性分组码的特点。设其码字为C=a6 a5 a4 a3 a2

47、a1 a0，其中前 4 位是信息元，后 3 位是监督元， 可用下列线性方程组来描述该分组码，产生监督元。 (6-3)346035614562aaaaaaaaaaaa(7,4)(7,4)码的码字表码的码字表 10.3.2 10.3.2 监督矩阵监督矩阵H H和生成矩阵和生成矩阵G G 式(6-3)所述(7,4)码的 3 个监督方程式可以改写为 (6-4) 这组线性方程可用矩阵形式表示为 (6-5) 010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa000100110101010110010111T0123456aa

48、aaaaa并简记为 00TTTHCHC或(6-6) 其中，AT是A的转置，0T是0=0 0 0的转置，HT是H的转置。 100110101010110010111H(6-7) H称为监督矩阵，一旦H给定，信息位和监督位之间的关系也就确定了。H为rn阶矩阵，H矩阵每行之间是彼此线性无关的。式(6-7)所示的H矩阵可分成两部分: 其中,P为rk阶矩阵，Ir为rr阶单位矩阵。可以写成H=P Ir形式的矩阵称为典型监督矩阵。 HCT=0T，说明H矩阵与码字的转置乘积必为零，可以用来作为判断接收码字C是否出错的依据。 100110101010110010111rIPH(6-8) 若把监督方程补充为下列方

49、程 (6-9) 可改写为矩阵形式 (6-10) (6-11) 即 变换为 3456aaaaGCTTGaaaaC3456nkG1101000101010001100101110001QIGk其中 是生成矩阵，由G和信息组就可以产生全部码字。G为kn阶矩阵，各行也是线性无关的。 生成矩阵也可以分为两部分， 即 (6-12)(6-13)T110101011111PQ由此得出一个结论: (6-14)Q为kr阶矩阵,Ik为k阶单位阵。可以写成式(6-13)形式的G矩阵称为典型生成矩阵。非典型形式的矩阵经过运算也一定可以化为典型矩阵形式。 也就是说也就是说,线性系统码的监督矩阵线性系统码的监督矩阵 H 和

50、生成矩和生成矩阵阵 G 之间可以直接互换。之间可以直接互换。u如:已知(7,4)线性系统码的监督矩阵为(7,4)(7,4)1110100H0111010110100110001010100111G00101100001011可直接写出它的生成矩阵H=P IG=I QQ=PT若 与 分别是线性码C的生成矩阵与校 验矩阵，则 从而 GH T= (HG T ) T = 0T =0 。kgggG21knhhhH21knkkknknkkknghghghghggghhhHG 0 )(TT1T1T11TT2T121T另一方面另一方面,由于由于G的每一行都是一个码字，有：的每一行都是一个码字，有： rkTGH

51、 0说明生成矩阵和校验矩阵的行正交说明生成矩阵和校验矩阵的行正交,事实上：事实上：由由:HCT=0Tu对偶码对偶码u对偶码对偶码：对一个对一个(n,k)线性码线性码 CI，由于，由于HrnGTnk=0Trk，如，如果以果以G 作监督矩阵，而以作监督矩阵，而以H 作生成矩阵，可构造另一个码作生成矩阵，可构造另一个码CId，码，码CId是一个是一个(n,nk)线性码，称码线性码，称码CId为原码的对偶码。为原码的对偶码。u如如： (7,4)线性码的对偶码是线性码的对偶码是(7,3)码：码： (7,3)码的监督矩阵码的监督矩阵H(7,3)是是(7,4)码生成矩阵码生成矩阵G(7,4) 1000110

52、0100011001011100011011101000011010011100101010001GH)4,7()3 ,7(IP化成标准形式 (7,3) 码的生成矩阵码的生成矩阵 G(7,3) 是是 (7,4) 码监督矩阵码监督矩阵 H(7,4) (7,3)(7,4)11101001001110GH0111010010011111010010011101 设C是线性空间 的子空间C的正交补子空间，则也是长为 n 的(n,n-k)线性码，即 C 是线性码C 的对偶码对偶码；当 C =C 时，称C是自对偶码自对偶码。定理：定理：设C是长为n 的二元线性码，则 (1) C 恰好含有M=2dimC 个

53、码字； (2) 当C是自对偶码时， 。2dimnC nF2u设h1=(h11,h12,h1n), , hn-k=(hn-k,1, hn-k,2, , hn-k, n) 是C的基， 则 是C 的生成矩阵。 nknnknknknnnknhhhhhhhhhhhhH)(,2 ,1 ,221211121121定理定理 设C是n,k线性码， 是C的对偶码 C 的生成矩阵，对 ， 则 XC 的充要条件是 。 0THX),(21nxxxXknhhhH21就是监就是监督方程督方程knr 由线性空间的理论，当由线性空间的理论，当H的行秩为的行秩为r时，有如下时，有如下的维数关系成立的维数关系成立nCCdimdim

54、一个定理一个定理定理：定理：n,k线性分组码有最小汉明距离线性分组码有最小汉明距离d的的充要条件是，充要条件是，H矩阵中任意矩阵中任意d-1列线性无关。列线性无关。l证明见教材证明见教材该定理实际给出了计算线性分组码最小码距的一该定理实际给出了计算线性分组码最小码距的一种方法种方法。 译码的概念检错译码：检错译码：译码器输出为当前接收向量译码器输出为当前接收向量r和和r是否有是否有差错的标志差错的标志s s，即，即 。sry,6.2.2 线性码的译码线性码的译码纠错译码的译码成功纠错译码的译码成功：译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字 ，即 。 c cy纠错译码的译码失

55、败：纠错译码的译码失败：译码器不能输出一个确译码器不能输出一个确切的码字，通常此时的输出切的码字，通常此时的输出y y与检错译码输出与检错译码输出相同。相同。 c n译码的问题：译码的问题：c u设行向量设行向量r=r1，r2，rn是收信端通过信是收信端通过信道收到的码组。由于信道干扰会产生误码，接道收到的码组。由于信道干扰会产生误码，接收向量收向量r和发送向量和发送向量c就会有差别，我们用向量就会有差别，我们用向量e=e1，e2，en表示这种差别。三者之间的表示这种差别。三者之间的关系为关系为:r=c+e (mod 2)u若若r中的某一位中的某一位ri与与c中的相同位中的相同位ci一样时，一

56、样时，e中的中的ei=0；若；若不同（即出现误码），则不同（即出现误码），则ei=1。可见向量。可见向量e能够反映误码能够反映误码状况，因此，称之为错误向量或错误图案。比如，发送向状况，因此，称之为错误向量或错误图案。比如，发送向量量c=11011001，而接收向量，而接收向量r=10001011，显然，显然，r中有中有3个错误，由上式可得错误图样个错误，由上式可得错误图样e=01010010。可。可见，见，e的码重就是误码的个数，因此的码重就是误码的个数，因此e的码重越小越好的码重越小越好。因为没有差错时: 令:110,rTsssrHs并称为伴随式或校正子。伴随式或校正子。 ，则传输中一定有

57、错误发生 s，则传输中要么无差错发生，要么差错图案恰好为一个码字。 ssecr否则有差错时: secr另一方面: TTTTTeHeHcHHecrHs)( 由此可见，伴随式s与错误图样e之间有确定的线性变换关系。接收端译码器的任务就是从伴随式确定错误图案e(将s与最可能的e建一张表，然后通过s查表法得到其所对应用的e)，然后从接收到的码字中减去错误图案e : ererc)2(mod根据差概率大小决定根据差概率大小决定u【例题】【例题】 已知一线性已知一线性(6，3)码的生成矩阵为码的生成矩阵为100101010011001110Gse0000000001011000000110100001100

58、01000100000100010000010001000001111100010s与e的对照表如下： 求当接收端收到码求当接收端收到码组组r=111011时，所时，所对应的信息码组对应的信息码组m。=I,Qu 解解: 根据前面根据前面HT的定义式可得的定义式可得101011110100010001TmPHI将接收码组r=111011代入下式:TrHs 1010111101 1 101 101 1100010001TSRHTrHs 从se关系表中可知，s=011所对应的错误图样为e=010000。将r=111011和e=010000代入下式可得: 从c中分出信息码组(前三位)为: m=101

59、信息码组为m=101。 101011)2(modererc伴随式纠错译码的通用译码方法伴随式纠错译码的通用译码方法 （1）按最可能出现的2r个差错图案e，计算相应的伴随式s，并构造伴随式差错图案表(s-e表)；（2）对接收向量r计算伴随式s；（3）查 s-e表得e；（4）纠错计算 : ererc)2(mod按概率大小按概率大小定理定理 可纠可纠t错的错的2元线性分组码满足元线性分组码满足 tirin02伴随式的所有可伴随式的所有可能情况能情况,每一种能纠每一种能纠一种错误一种错误.r=r1，r2，rn所有可能出错的情况所有可能出错的情况6.2.3 码例与码的重构码例与码的重构常见的线性分组码有

60、常见的线性分组码有:n重复码重复码n汉明码汉明码n里德里德-穆勒码穆勒码n戈雷码戈雷码二进制汉明码的参数二进制汉明码的参数n,k和和d分别为分别为:1212312)3,(12minmmmmmdknrmkmmn是校验位数 码长：码长： 信息位数：信息位数： 监督位数：监督位数： 最小距离：最小距离： 码率码率：1.汉明码n 汉明码是汉明于汉明码是汉明于1950年提出的纠一个错误的线性码，也年提出的纠一个错误的线性码，也是第一个纠错码。由于它编码简单，因而是在通信系统和数是第一个纠错码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应用的一类线性码。据存储系统中得到广泛应用的一类线性码。