6-2信息论与编码.ppt

6.3线性分组码,分组码的编码包括两个基本步骤首先将信源的输出序列分为k位一组的信息组然后信道编码器根据一定的编码规则将k位信息组变换成n个码元的码字，即(n，k)分组码信息组和码字用矩阵表示如下：,信息组：k位信息,通常对编码器附加一个线性约束条件，使得码字的校验位与信息位之间呈线性关系，这种码称为(n,k)线性分组码采用线性分组码进行信道编码，就是给已知信息组按预定规则添加校验码元以构成码字。在k个信息元之后附加r=n-k个校验码元，使每个校验码元是其中某些信息码元的和,例：设信息分组长度为k=3,m=(m1,m2,m3)，在每一信息组后加上4个校验码元，构成(7,3)线性分组码,设该码的码字为c=(c1,c2,c3,c4,c5,c6,c7)，其中c1,c2,c3为信息码元，c4,c5,c6,c7为校验码元，ci0,1；信息码元和校验码元可按右方的方程组计算：,利用上式每给出一个3位的信息组，就可编出一个码字，结果如下表所示线性方程组的后4个方程确定了由信息码元得到校验码元的规则，这4个方程称为校验方程。由于所有码字都按同一规则确定，因此又称为一致校验方程，所得到的校验码元称为一致校验码元上述这种编码方法称为一致校验编码。由于一致校验方程是线性的，亦即校验码元和信息码元间是线性运算关系，所以由线性校验方程所确定的分组码是线性分组码,6.3.1线性分组码的生成矩阵和一致校验矩阵,在(n,k)线性分组码中，编码器输出的码字可以由如下方程组来决定：,如设：,则方程组的矩阵表示为：c=mG所有满足上式码字(n维向量)的全体构成(n,k)线性分组码C,生成矩阵,生成矩阵G是一个k行n列(nk)秩为k的矩阵，它建立了消息向量m与码字c的一一对应关系，它起着编码器的变换作用G的每一行都是一个码字，分别是k维消息向量组1000,01000,00010,00001所对应的码字,其中：m是任意k维消息向量,运算：模2加、模2乘,线性分组码的生成矩阵的性质,设是某个二元线性分组码的生成矩阵，则：,n维零向量是一个码字，称为零码字,封闭性：任意两个码字的和仍是一个码字，即：,(n,k)线性分组码实质上是n维n长向量构成的线性空间中的一个k维线性子空间,线性分组码的任意一个码字均是生成矩阵的行向量的线性组合，即，存在一组不全为0的系数，使得：,系统码,生成矩阵G的选择不是惟一的；如下面的G1和G2都可作为同一个(6,3)码的生成矩阵，所对应的码字如下表所示：,虽然二者用了不同形式的生成矩阵，却都是(6,3)线性分组码，因此它们的检错和纠错能力是一样的，但是G2生成的码，其前k位与消息码完全相同，等于把信息组m原封不动搬到码字的前k位，这种码称为系统码，其余的n-k位叫冗余位或一致校验位，是前k个信息位的线性组合。其生成矩阵和一致校验矩阵分别记为Gs,Hs,系统码的编码器仅需存储k(n-k)个数字(非系统码要存储kn个数字)，译码时仅需对前k个信息位纠错即可恢复信息；可见系统码的编码和译码比较简单，而性能与非系统码一样，所以系统码得到了十分广泛的应用,线性分组码的生成矩阵和一致校验矩阵的相互转换,系统码的生成矩阵可用分块矩阵表示为,在系统码字c中，前k位是信息位m，后r位为码字的校验位q，并且c=mGs，所以：,即：q=mQkr,H矩阵的每一行都代表一个校验方程,对于2进制编码,mQkr+q=0,线性分组码的生成矩阵和校验矩阵的关系,由于G的每一行都是一个码字，所以G的每一行ci都满足：,从而有：,在码字集合不变的前提下，给定任何一个线性分组码，通过其生成矩阵G实施行初等变换，均可以转换为某个系统码,例6-2(6,3)线性分组码，其生成矩阵是G=求：(1)计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统码码集并列出映射关系。(3)计算系统码的校验矩阵H。若收码r=100110,检验它是否为码字？(4)根据系统码生成矩阵画出编码器电原理图。,111010110001011101,例6-2码集与映射关系,信息码字系统码字000000000000000001011101001011010110001010110011101100011101100111010100111101100111101100110001011110001111010110111010,例6-2二元(6,3)线性分组码编码器,m1m2m3输入输出c4c5c6,例：(7,3)线性分组码,下面利用校验矩阵来构造(7，3)线性分组码的编码电路。设二元码字矢量为C=(c1,c2,c3,c4,c5,c6,c7)，而码的监督矩阵为,由HCT=0T得：,c4=c1+c3c5=c1+c2+c3c6=c1+c2c7=c2+c3,根据上式可直接画出(7,3)码的并行编码电路和串行编码电路，如图3所示。类似地，也可以利用生成矩阵来编码。设信息组为M=(m1,m2,m3)，生成矩阵为,根据C=(c1,c2,c3,c4,c5,c6,c7)=MG，将M和G代入得：c1=m1c2=m3c3=m3c4=m1+m3=c1+c3c5=m1+m2+m3=c1+c2+c3c6=m1+m2=c1+c2c7=m2+m3=c2+c3,图3线性系统码编码电路(a)并行编码电路；(b)串行编码电路,6.3.2伴随式与标准阵列译码,线性分组码用生成矩阵G编码，用校验矩阵H译码：当收到一个接收向量R后，检验R是否满足校验方程RHT=0，若关系式成立，则认为R是一个码字，否则判为码字在传输中发生了错误。因此RHT的值是否为0是接收向量出错与否的依据,称r(r=n-k)维向量S=RHT为(n,k)线性分组码的伴随式,S=RHT=(C+E)HT=CHT+EHT=0+EHT=EHT,伴随式仅与差错图案有关，与发送的具体码字无关，它反映了信道被干扰的情况,差错图案E是n重矢量，共有2n个可能的组合，而伴随式S是(n-k)重矢量，只有2r个可能的组合.不同的差错图案可以具有相同的伴随式,伴随式是差错的判别式：若S=0，则接收向量是一个码字,说明传输过程中或者没有发生差错，或者差错图案恰为一个码字；若S0，则传输过程中一定发生了差错,设接收向量为,译码器判接收向量R无错，即传输中没有发生错误，发送码字为：,设某（7,4）线性分组码的校验矩阵如右，发送码字c=1010011,求接收向量r的伴随式。,R=1010011,假设接收向量中有一位发生差错，设接收向量为,由于，译码器判定传输中有差错发生。又(7,4)码是纠单个错误的码，且等于H的第二列，因此判定接收码字r的第二位是错的，纠正该位错误后译出发送码字为：,R=1110011,假设接收向量中发生了两位差错，设接收向量为,，且是H的第1列和第4列的和，但与H中的任何一列均不相同，因此译码器无法判定差错发生在接收向量的哪些位置，此时只能发现差错，不能纠正差错,R=0011011,一般而言，译码时需要由接收向量R来确定发送码字C，若能确定差错图案E，就可以得到发送码字C的估计值：,因此，译码的关键是确定差错图案E。根据伴随式S确定差错图案E，再由上式得到译码估计值，这种译码方法称为伴随式译码,由于S=RHT是一个含有r=n-k个方程的线性方程组，欲从中解出e的n个分量，得不到唯一解；通常的做法是，在所有解中，选码字重量最小者作为E，因为E=R+C，E的码字重量最小意味着接收向量R与发送码字C的汉明距离最小,C=R+E,标准阵列译码表,上述的概率译码，如每接收一个码R就要解一次线性方程，那就太麻烦了。好在伴随式S的数目是有限的2n-k个，如果n-k不太大，我们可以预先把不同S下的方程组解出来，把各种情况下的最大概率译码输出列成一个码表。这样，在实时译码时就不必再去解方程，而只要象查字典那样查一下码表就可以了。这样构造的表格叫做标准阵列译码表。,对给定的(n，k)线性码，将2n个n重矢量划分为2k个子集的方法就是构造所谓的“标准阵列”。方法如下：先将2k个码字排成一行，作为“标准阵列”的第一行，并将全0码字C0(0,0,0)放在最左面的位置上；然后在剩下的2n2k个n重矢量中选取一个重量最轻的n重E1放在全0码字C0的下面，再将E1分别和码字C1，C2，C2k-1相加，放在对应码字下面构成阵列第二行，在第二次剩下的n重矢量中，选取重量最轻的n重E2，放在E1下面，并将E2分别加到第一行各码字上，得到第三行，继续这样做下去，直到全部n重矢量用完为止，按上述方法构造的标准阵列如表所示。,标准阵列译码表,E1+C1,S0E0S1E1SjEjS2n-k-1E2n-k-1,陪集和子集,译码表中有2n-k行，每行是一个陪集，每陪集的第一个元素(位于第一列)叫陪集首。同一陪集(同一行)中的所有元素对应共同的一个伴随式。第一行陪集的陪集首是全零伴随式S0所对应的全零差错图案E0(无差错)，而第j行陪集的陪集首是伴随式Sj所对应的重量最小的差错图案Ej(C0=0,Rj=Ej)。译码表中有2k列，每列是一个子集，每子集的第一个元素(位于第一行)叫子集头。同一子集(同一列)中的所有元素对应同一个码字，第一列子集的子集头是全零码字C0，而第i列子集的子集头是码字Ci(E0=0,Ri=Ci)。,例：已知校验矩阵：,若接收为：R=0000011，试确定是否错误，若接收错误，试进行纠错。,解：计算伴随式,错误图样：,E=0001000,对照伴随式与误码位置，确定错误图样：,于是：C=R+E,=0000011+0001000,由于，当只发生一位错码时，矩阵E中只有一个非零元素，与H的转置相乘的结果是选出其中的一列，即校正子与H矩阵的哪一列相同，则该列即为码元发生错误的位置。,=0001011,例6-3一个(5,2)系统线性码的生成矩阵是G=设收码R=(10101)，构造标准阵列译码表，译出发码的估值解：(1)构造标准阵列译码表。分别以信息组m=(00)、(01)、(10)、(11)及已知的G求得4个许用码字为C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。求出校验矩阵：H=列出方程组：,例6-3译码表的构成,伴随式有2n-k238种组合，差错图案中代表无差错的有一种，代表一个差错的图案有种，已有6种。代表两个差错的图案有种。只需挑选其中的两个，挑选方法可有若干种，不是唯一的。先将Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的线性方程组，解得对应的Sj分别是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴随式中，(011)所对应的差错图案是2k个即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最轻，任选其中一个如(00011)。同样可得伴随式(110)所对应的最轻差错图案之一是(00110)。,例6-3标准阵列译码表,将接收码R10101译码,可选以下三种方法之一译码：直接搜索码表，查得(10101)所在列的子集头是(10111)，因此译码输出取为(10111)。先求伴随式RHT=(10101)HT=(010)=S4，确定S4所在行，再沿着行对码表作一维搜索找到(10101),最后顺着所在列向上找出码字(10111)。先求出伴随式RHT=(010)=S4并确定S4所对应的陪集首(差错图案)E4=(00010)，再将陪集首与收码相加得到码字C=R+E4=(10101)+(00010)=(10111)。上述三种方法由上而下，查表的时间下降而所需计算量增大，实际使用时可针对不同情况选用。,对上例作进一步分析，还可以看到，该(5,2)码的dmin=3。纠错能力是t=INT(3-1)/2=1。因此，译码阵列中只有前6行具有唯一性、可靠性，真正体现了最大似然译码准则。而第7、8行的差错图案(00011)和(00110)中包含两个“1”，已超出了t=1的纠错能力，译码已不可靠。比如，当收码R(10100)时，根据码表译出的码字是(10111)，与收码R的汉明距离是2，然而收码R与全零码字(00000)的汉明距离也是2，为什么不能译成(00000)呢？事实上，码表的第7、8行本身就不是唯一的。注意在码表计算过程中，伴随式(011)所对应的4个差错图案中有两个并列重量最轻，如果当时选的不是(00011)而是(10100)，那么码表第7行就不是现在这样了。,例：已知(6,3)线性分组码的生成矩阵为求它的标准阵列。解：由生成矩阵可得该码许用码组的全部码字：,则它的标准阵列为：,000000,001101,010011,011110,100110,101011,110101,111000,000001,001100,010010,011111,100111,101010,110100,111001,000010,000100,001000,010000,100000,100001,001111,001001,000101,011101,101101,101100,010001,010111,011011,000011,110011,110010,011100,011010,010110,001110,111110,111111,100100,100010,101110,110110,000110,000111,101001,101111,100011,111011,010101,001010,110111,110001,111101,100101,001011,010100,111010,111100,110000,101000,011000,011001,在信道编码中，定义码字中非零码元(“1”)的数目为码字的汉明(Hamming)重量，或码组重量、码字重量，简称重。例如“010”码字的码重为1，“011”码字的码重为2。非零码字中，重量最小者称为该码的最小汉明重量。显然，不同码字的汉明重量是不同的。把两个码字中对应码元位置上具有不同码元的位数定义为两码字的汉明(Hamming)距离，或码组距离，简称码距。在一种编码中，任意两个合法码字(许用码字)间距离的最小值，即码字集合中任意两码字间的最小距离，称为这一编码的最小汉明(Hamming)距离，以dmin表示。,6.3.3码距、纠错能力、MDC码及重量谱,对于二进制编码：码重(weight)一个码组中“1”的数目码距(distance)两个码组之间对应位置上1、0不同的位数，又叫汉明(Hamming)距。10110码重：3011002距离：3,用d(C1，C2)表示两个n重C1、C2之间的汉明距离，则汉明距离有以下三个性质：(1)对称性：d(C1，C2)=d(C2，C1)；(2)非负性：d(C1，C2)0；(3)满足距离三角不等式：d(C1，C2)d(C1，C3)+d(C3，C2)。,定理6.1任何最小距离dmin的线性分组码，其检错能力为（dmin-1）,纠错能力t为逐一计算各个码字之间的汉明距离是非常麻烦的。由于各个码字之和满足封闭性，两个码字之间汉明距离即为单个码字的汉明重量！定理6.2线性分组码的最小距离等于码集中非零码字的最小重量：dmin=minw(Ci)CiC及Ci0,下面讨论码的检错、纠错能力与最小码距的数量关系。在一般情况下，对于分组码有以下结论：(1)最小码距与检错能力的关系检测e个错码，则要求最小码距：dmine+1或者说：若一种编码的最小距离为dmin，则它最多能检出(dmin-1)个错码。,(2)最小码距与纠错能力的关系纠正t个错码，则要求最小码距为：dmin2t+1或者说：若一种编码的最小码距为dmin，则它最多能纠正(dmin-1)/2个错码。,(3)最小码距与检、纠错能力的关系纠正t个错码，同时能检测e(et)个错码，则要求最小码距为dmine+t+1,et这里所述能纠正t个错码，同时能检测e个错码的含义，是指：当错码不超过t个时错码能自动予以纠正，而当错码超过t个时，则不可能纠正错误，但仍可检测e个错码，这正是混合检错、纠错的控制方式。,定理6.3(n,k)线性分组码最小距离等于dmin的充要条件是：校验矩阵H中有（dmin-1)列线性无关。定理6.4(n,k)线性分组码的最小距离必定小于等于(n-k+1)，即：dmin(n-k+1),例：(7，4)线性码H各列都不相同，任意2列之和不等于0，2列线性无关；任意2列之和一定等于矩阵中某一列，任意3列线性相关。所以该码的最小距离为3，小于n-k+14。,(n,k)线性码最小距离dmin的上边界是n-k+1。如果设计的一种(n,k)线性码的dmin达到了n-k+1，就是达到了设计性能的极点。因此，dminn-k+1的码称为极大最小距离码(MDCMaximizedminimumDistanceCode)。,总体的、平均的纠错能力不但与最小距离有关，而且与其余码距或者说与码字的重量分布特性有关。,采用差错控制编码后，在随机信道中即使只能纠正(或检测)这种码字中12个错误，也可以使误码率下降几个数量级。说明，即使是简单的差错控制编码也具有较大的实用价值。当然，如在突发信道中传输，由于错码是成串集中出现的，所以上述只能纠正码字中1或2个错码的编码，其效用就不像在随机信道中那样明显了，需要采用更为有效的纠错编码。,6.3.4完备码(Perfectcode),任何一个二元(n,k)线性分组码都有2n-k个伴随式，假如该码的纠错能力是t，则对于任何一个重量小于等于t的差错图案，都应有一个伴随式与之对应，也就是说，伴随式的数目满足条件上式称作汉明限，任何一个纠t码都应满足上述条件。,某二元(n,k)线性分组码能使等式成立，即该码的伴随式数目不多不少恰好和不大于t个差错的差错图样的数目相等，相当于在标准译码阵列中能将所有重量不大于t的差错图案选作陪集首，而没有一个陪集首的重量大于t，这时的校验位得到最充分的利用。这样的二元(n,k)线性分组码称为完备码。,汉明码(HammingCode),汉明码是1950年由汉明提出的一种能纠正单个错误(纠错能力t=1)的线性分组码。它不仅性能好而且编译码电路非常简单，易于工程实现，因此是工程中常用的一种纠错码。汉明码不是指一个码，而是代表一类码。汉明码的，既有二进制的，也有非二进制的。,汉明码是一种特殊的(n，k，d)线性分组码。对于二进制的码元，汉明码的参数n，k和d分别为码长信息位数监督位数最小距离码率,汉明码校验矩阵的构成,汉明码的校验矩阵H具有特殊的性质，能使编码的构造方法简化。一个(n,k)码的校验矩阵H有n-k行和n列，二进制时n-k个监督码元所能组成的非全0列矢量总数是2n-k-1,恰好和校验矩阵的列数n=2r-1相等。只要排列所有列，(按m位的2进制数的自然顺序从左到右排列(不包括全0列)，通过列置换将矩阵H转换成系统形式，就可以进一步得到相应的生成矩阵G。,例6.4构造一个r=3的二元(7，4)汉明码。解：先利用汉明码的特性构造一个(7，4)汉明码的校验矩阵H，再通过列置换将它变为系统形式：0001111列置换1110100H=01100110111010=QTI310101011101001再得生成矩阵G为1000101G=I4Q=010011100101100001011,由于汉明码的最小距离是3，故汉明码能纠正一个随机错误或检测两个错误,且码的校验矩阵H中任意两列线性无关。汉明码的校验矩阵H由一切r(r=n-k)维非零二元向量排列而成，即H的列为所有非零的r维向量组成，所以H的各列在二元和之下是封闭的，一旦r给定，就可构造出具体的(n，k)汉明码。,高莱（Golay）码,是二进制（23，12）线性码，其最小距离dmin7，纠错能力t=3。是完备码，因为满足等式223-12=2048=在(23,12)码上添加一位奇偶位即得二进制线性（24，12）扩展高莱码，其最小距离dmin8。,循环码是线性码的一个子类。循环码的最引人注目的特点有两个:一是，可以用反馈线性移位寄存器很容易地实现其编码和伴随式计算(普通的线性分组码需要存储码字阵列)；二是，由于循环码有许多固有的代数结构，从而可以找到各种简单实用的译码方法。循环码满足下列循环移位特性：码集C中任何一个码字的循环移位仍是码字。,6.3.5循环码,循环码的多项式描述,循环右移i位可得：,循环左移i位可得：,上表给出的(7,3)分组码的所有8个码字在移位(左移或右移)之下是封闭的，此码是一个循环码,循环码的定义：线性分组码的任意一个码字任意循环移位后得到的码字是封闭的(仍是许用码字),可见左、右循环移位彼此等价的，在不引起混淆的情况下统称为循环移位,易证：对任意i(0in-1)，左、右循环移位满足：,循环码的多项式定义,任意一个n维矢量C=(cn-1，cn-2，c1,c0)或者码字C=cn-1cn-2c1c0都可以用一个次数不超过n-1的多项式惟一确定，即C(x)=cn-1xn-1+cn-2xn-2+c1x+c0当C是一个码字时，C(x)称为相应码字的码/码字多项式。对于二进制码，ci0,1,i=0,，n-1。显然，码字C和码字多项式C(x)是一一对应的。因此任何一个(n,k)线性分组码都可以等价地看作一类由2k个次数不超过n-1的多项式组成的集合。,将式C(x)乘以x，再除以xn+1得：上式表明，码字循环左移一次的码多项式C(1)(x)是原码多项式C(x)乘x再除以xn+1所得的余式。写作：C(1)(x)xC(x)mod(xn+1),模运算,由此可以推知，C(x)的i次循环移位C(i)(x)是C(x)乘xi再除以xn+1所得的余式。即：C(i)(x)xiC(x)mod(xn+1)循环码的码字的i次循环移位等效于将码多项式乘xi后再模xn+1。上式揭示了(n，k)线性码中码字多项式与码字循环移位之间的关系，它对循环码的研究起着重要作用。,循环移一位：(cn-1cn-2c1c0)(cn-2c1c0cn-1)循环移一位：C(x)=cn-1xn-1+cn-2xn-2+c1x+c0C(1)(x)=cn-2xn-1+cn-3xn-2+c0 x+cn-1比较循环移位的前后，可用如下的多项式运算来表达循环移位移1位：C(1)(x)=xC(x)mod(xn+1)移2位：C(2)(x)=xC(1)(x)=x2C(x)mod(xn+1)移n-1位：C(n-1)(x)=xC(n-2)(x)=xn-1C(x)mod(xn+1),循环码的循环移位,例如，(7，3)循环码可由任一个码字，比如0011101经过循环移位，得到其他6个非0码字；也可由相应的码多项式x4+x3+x2+1，乘以xi(i=1，2，6)，再模x7+1得到其他6个非0码多项式。这个移位过程和相应的多项式运算如表所示。最后加上一个全0码字，构成码字空间。,表(7，3)循环码的循环移位,生成多项式,C(x)=m(x)g(x)码多项式信息多项式生成多项式生成多项式不是唯一的；g(x)=xn-k+gn-k-1xn-k-1+g2x2+g1x+1是(n-k)次的首一码多项式，即(n-k)次项的系数为1。g(x)一定是(xn+1)的因子。,校验多项式,多项式xn+1可因式分解为xn+1g(x)h(x)