信息论基础与编码 (16).ppt
伴随式与译码伴随式与译码译码准则译码准则最大后验概率最大后验概率准则准则最大似然最大似然译码准则译码准则当信道输入等概分布时，两种译码准则等价。当信道输入等概分布时，两种译码准则等价。最小汉明距离最小汉明距离译码译码对于给定的接收矢量，计算它与对于给定的接收矢量，计算它与M个可能的发送个可能的发送码字之间的距离，从中选择能使码字之间的距离，从中选择能使距离达到最小距离达到最小的码字的码字作为判决结果。对于作为判决结果。对于BSCBSC信道，信道，等效于最大似然译码等效于最大似然译码。伴随式与译码伴随式与译码 定义定义差错图案（错误图样）差错图案（错误图样）E：E(e1，e2，en)RC (r1c1，r2c2，rncn)二进制码中模二进制码中模2 2加与模加与模2 2减是等同的，因此有减是等同的，因此有E=R C 及及R=C E 在在E中中，e i=1=1表表明明相相应应位位有有错错，e i=0=0表表明明相相应应位位无错无错。译码译码译码器就是从接收码字译码器就是从接收码字R 得到发送码字的估得到发送码字的估计值，或者说从接收码字中计值，或者说从接收码字中确定错误图样确定错误图样E，然后由，然后由C=R E 得到发送码字的估计值。得到发送码字的估计值。如果估计正确则译码正确，否则译码错误。如果估计正确则译码正确，否则译码错误。伴随式伴随式 S 的定义的定义 因为因为CHT=0 所以所以 RHT(CE)HTCHTEHT=EHT如果收码无误：必有如果收码无误：必有RC即即E0，则则EHT=0，RHT=0。如果收码有误：即如果收码有误：即E 0，则则RHT=EHT 0。在在HT固定的前提下，固定的前提下，RHT仅仅与差错仅仅与差错图案图案E有关，而与发送码有关，而与发送码C无关。无关。定义收码定义收码R的的伴随式伴随式S:S=(s1,s2,sn-k)=RHT=EHT 伴随式伴随式S S的意义的意义从物理意义上看，伴随式从物理意义上看，伴随式S并不反映发送的码字是并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。什么，而只是反映信道对码字造成怎样的干扰。差错图案差错图案E是是n重矢量，共有重矢量，共有2n个可能的组合，而伴个可能的组合，而伴随式随式S是是(n-k)重矢量，只有重矢量，只有2n-k个可能的组合，因此个可能的组合，因此不同的差错图案不同的差错图案可能有可能有相同的伴随式相同的伴随式。接收端收到接收端收到R后，因为已知后，因为已知HT，可求出，可求出 SRHT；如；如果能知道对应的果能知道对应的E，则通过，则通过C=RE而求得而求得C。译码过程译码过程 RHT=S S=EHT C=RE R S E C 只要只要E E正确，译出的码也就是正确的。正确，译出的码也就是正确的。差错图案差错图案E E的求解的求解可以通过解线性方程求解可以通过解线性方程求解E：得到线性方程组：得到线性方程组：上述方程组中有上述方程组中有n个未知数个未知数e1,e2,en，却只，却只有有r=n-k个方程，可知方程组有多解。个方程，可知方程组有多解。在有理数或实数域中，少一个方程就可能导致在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致无限多个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少两个解，少两个方程四个解，以此类推，少 k个方程导致每个未知数有个方程导致每个未知数有2k个解。个解。因此，由上述方程组解出的因此，由上述方程组解出的E可以有可以有2k个解。到个解。到底取哪一个作为附加在收码底取哪一个作为附加在收码R上的差错图案上的差错图案E的的估值呢？估值呢？译码原则译码原则：把所有把所有2k个解的重量个解的重量(差错图案差错图案E中中1的个数的个数)作比较，选择其中最轻者作为作比较，选择其中最轻者作为E的估值，的估值，体现最小距离译码的思想体现最小距离译码的思想 。标准阵列译码表标准阵列译码表 上述的译码过程，如每接收一个码上述的译码过程，如每接收一个码R就要解就要解一次线性方程，那就太麻烦了。好在伴随式一次线性方程，那就太麻烦了。好在伴随式S的的数目是有限的数目是有限的2n-k个，如果个，如果n-k不太大，我们可以不太大，我们可以预先把不同预先把不同S下的方程组解出来，把各种情况下下的方程组解出来，把各种情况下的译码输出列成一个码表。这样，在实时译码时的译码输出列成一个码表。这样，在实时译码时就不必再去解方程，而只要象查字典那样查一下就不必再去解方程，而只要象查字典那样查一下码表就可以了。这样构造的表格叫做码表就可以了。这样构造的表格叫做标准阵列译标准阵列译码表。码表。标准阵列译码表的构成标准阵列译码表的构成 表中所列码字是接收到的码字表中所列码字是接收到的码字R。将没有任何差错时的收码将没有任何差错时的收码R放在第一行，收码等于发码放在第一行，收码等于发码R=C,差差错图案为全零，伴随式为全零。由于有错图案为全零，伴随式为全零。由于有2k个码字，码表有个码字，码表有2k列。列。在第在第2到第到第n+1的的n行中差错图案的重量为行中差错图案的重量为1(共共n个个)。如果如果(1+n)2n-k，再在下面行写出全部带有，再在下面行写出全部带有2个差错的图案个差错的图案 (共共 个个)。如果总行数如果总行数()仍然小于仍然小于2n-k，再列出带有，再列出带有3个差错的图个差错的图案，以此类推，直到放满案，以此类推，直到放满2n-k行，每行一个行，每行一个Ej,对应一个不同的对应一个不同的伴随式伴随式Sj。这样，表的行数。这样，表的行数2n-k正好等于伴随式的数目。正好等于伴随式的数目。陪集和子集陪集和子集译译码码表表中中有有2n-k行行，每每行行是是一一个个陪陪集集，每每陪陪集集的的第第一一个个元元素素(位位于于第第一一列列)叫叫陪陪集集首首。同同一一陪陪集集（同同一一行行）中中的的所所有有元元素素对对应应共共同同的的一一个个伴伴随随式式。第第一一行行陪陪集集的的陪陪集集首首是是全全零零伴伴随随式式所所对对应应的的全全零零差差错错图图案案(无无差差错错)，而而第第j行行陪陪集集的的陪陪集集首首是是伴伴随随式式Sj所所对对应应的的重重量量最最小小的的差差错图案错图案Ej。译译码码表表中中有有2k列列，每每列列是是一一个个子子集集，每每子子集集的的第第一一个个元元素素(位位于于第第一一行行)叫叫子子集集头头。同同一一子子集集（同同一一列列）中中的的所所有有元元素素对对应应同同一一个个码码字字，第第一一列列子子集集的的子子集集头头是是全全零码字，而第零码字，而第i列子集的子集头是码字列子集的子集头是码字Ci 。2 2.2.2标准阵列译码表标准阵列译码表 例例7-4，假设（，假设（6，3）码，生成矩阵为）码，生成矩阵为000 001 010 011 100 101 110 111 000000 001111 010011 011100 100110 101001 110101 111010 如果接收到的码字为（如果接收到的码字为（110110），试利用标准阵列），试利用标准阵列法译码。法译码。解：根据生成矩阵则可以写出其全部许用码字：解：根据生成矩阵则可以写出其全部许用码字：伴随式和错误图样的对应关系伴随式和错误图样的对应关系15错误图样E伴随式伴随式S000000000100000110010000011001000111000100100000010010000001001110000101 可以构造出下面的标准阵列可以构造出下面的标准阵列16000000001111010011011100100110101001110101111010100000101111110011111100000110001001010101011010010000011111000011001100110110111001100101101010001000000111011011010100101110100001111101110010000100001011010111011000100010101101110001111110000010001101010001011110100100101011110111111000000001001110010010011101100111101000110100111011110000111111100011101100010110011001000101001010任何一个二元任何一个二元(n,k)线性分组码都有线性分组码都有2n-k个伴个伴随式，假如该码的纠错能力是随式，假如该码的纠错能力是t，则对于任，则对于任何一个重量小于等于何一个重量小于等于t的差错图案，都应有的差错图案，都应有一个伴随式与之对应，也就是说，伴随式一个伴随式与之对应，也就是说，伴随式的数目满足条件的数目满足条件 上式称作上式称作汉明限汉明限，任何一个纠，任何一个纠t码都应满足码都应满足上述条件。上述条件。完备码完备码(Perfect code)完备码 某二元某二元(n,k)线性分组码能使等式线性分组码能使等式 成成立立，即即该该码码的的伴伴随随式式数数目目不不多多不不少少恰恰好好和和不不大大于于t个个差差错错的的图图案案数数目目相相等等，相相当当于于在在标标准准译译码码阵阵列列中中能能将将所所有有重重量量不不大大于于t的的差差错错图图案案选选作作陪陪集集首首，而而没没有有一一个个陪陪集集首首的的重重量量大大于于t，这这时时的的校校验验位位得得到到最最充充分分的的利利用用。这这样样的的二二元元(n,k)线性分组码称为线性分组码称为完备码完备码。汉明码(Hamming Code)汉明码不是指一个码，而是代表一类码。汉明码不是指一个码，而是代表一类码。汉汉明明码码的的纠纠错错能能力力t=1，既既有有二二进进制制的的，也也有有非非二二进进制制的的。二二进进制制时时，汉汉明明码码码码长长n和和信信息息位位k服服从从以以下下规规律：律：(n,k)=(2m-1,2m-1-m)其中其中m=n-k，是正整数。，是正整数。当当m3、4、5、6、7、8时时，有有汉汉明明码码(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247)。汉明码是完备码，因为它满足上述等式。汉明码是完备码，因为它满足上述等式。汉明码校验矩阵的构成汉明码校验矩阵的构成 汉明码的校验矩阵汉明码的校验矩阵H具有特殊的性质，能使具有特殊的性质，能使构造方法简化。一个构造方法简化。一个(n,k)码的校验矩阵有码的校验矩阵有nk行行和和n列，二进制时列，二进制时n-k个码元所能组成的列矢量总个码元所能组成的列矢量总数是数是2n-k-1,恰好和校验矩阵的列数恰好和校验矩阵的列数n=2m-1相等。相等。只要排列所有列，通过列置换将矩阵只要排列所有列，通过列置换将矩阵H转换成系转换成系统形式，就可以进一步得到相应的生成矩阵统形式，就可以进一步得到相应的生成矩阵G。例例 构造一个构造一个m=3的二元的二元(7，4)汉明码。汉明码。解解：先先利利用用汉汉明明码码的的特特性性构构造造一一个个(7，4)汉汉明明码码的的校校验验矩阵矩阵H，再通过列置换将它变为系统形式：，再通过列置换将它变为系统形式：0 0 0 1 1 1 1 列置换列置换 1 1 1 0 1 0 0 H=0 1 1 0 0 1 1 0 1 1 1 0 1 0 =PT I3 1 0 1 0 1 0 1 1 1 0 1 0 0 1再得生成矩阵再得生成矩阵G为为 1 0 0 0 1 0 1 G=I4 P=0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 设（设（n,k）线性分组码）线性分组码C的生成矩阵为的生成矩阵为G，校验，校验矩阵为矩阵为H，以以H作为生成矩阵，作为生成矩阵，G为对应的校验为对应的校验矩阵，矩阵，可构造另一个（可构造另一个（n,n-k）线性分组码）线性分组码Cd，我们称，我们称Cd为为C的对偶码。的对偶码。对偶码对偶码
