线性分组码..

1krnk是每组二进制信息码元的数目，n是编码码组的码元总位数又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。(n,k)分组码是对每段k位长的信息组以一定的规则增加r个监督位，组成长为n的码组。2线性分组码线性:监督码元与信息码元满足线性关系(n,k)分组码（an-1an-2an-3……a0）以下将以汉明码为例引入线性分组码一般原理。汉明码是一种用来纠正单个错误的线性分组码。构造原理在偶数监督码中，一位监督位a0，和信息位构成关系式：0021aaann在接收端解码时，实际上就是在计算021aaaSnn监督关系式校正子S=0，认为无错码；S=1，就认为有错码。若监督位增加一位，两个校正子的可能值有4种组合：00，01，10，11，故能表示4种不同信息。1种表示无错其余3种能指示1位错码若有r个校正子，则可指示1位错误的(2r–1)个可能位置。码长为n，信息位数为k，则监督位r＝n－k。指示1位错码的n种可能位置，要求1212rknrr或设分组码(n,k)中k=4，为了纠正1位错码，监督位需要多少位？12rkr监督位数r3若取r=3，则n=k+r=7码组：（a6a5a4a3a2a1a0)监督位信息位假设校正子与错码位置的对应关系如表规定(也可以另外规定)。S1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码仅当一位错码在a2、a4、a5或a6时，校正子S1为1,偶数监督关系24561aaaaSa1、a3、a5和a6构成偶数监督关系：a0、a3、a4和a6构成偶数监督关系：13562aaaaS03463aaaaS如何构造监督关系式？监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使S1、S2和S3的值为0:000034613562456aaaaaaaaaaaa上式经过移项运算，解出监督位346035614562aaaaaaaaaaaa信息位a6a5a4a3监督位a2a1a0信息位a6a5a4a3监督位a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111给定信息位后，可以直接按上式算出监督位346035614562aaaaaaaaaaaa接收端收到每个码组后，先按照约定计算出S1、S2和S3，再查表判断错码情况。例如：若接收码组为1101100按监督式计算可得：S1=1，S2=1，S3=0。查表可知在a5位有1错码。码效率：k/n=(n-r)/n=1–r/n，当n很大和r很小时，码率接近1。汉明码是一种高效码。按照上述方法构造的码称为汉明码。表中所列的(7,4)汉明码的最小码距d0=3。这种码能够纠正1个错码或检测2个错码。S1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码信息位a6a5a4a3监督位a2a1a0信息位a6a5a4a3监督位a2a1a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111124561aaaaS13562aaaaS03463aaaaS线性分组码的一般原理线性分组码的构造H矩阵上面(7,4)汉明码的例子有000034613562456aaaaaaaaaaaa改写为010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa上式中已经将“”简写成“+”。矩阵形式）（模20001011001110101011101000123456aaaaaaaH称为监督矩阵。只要监督矩阵H给定，编码时监督位和信息位的关系就完全确定了。010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa简记为HAT=0T或AHT=0H矩阵ATH矩阵（r行n列）的性质：1)H的行数就是监督关系式数，等于监督位数r。每行中“1”的位置表示监督关系。H矩阵可以分成两部分rPIH001101101011011001110P为rk阶矩阵，Ir为rr阶单位方阵。我们将具有[PIr]形式的H矩阵称为典型阵。G矩阵：汉明码例子中的监督位公式为346035614562aaaaaaaaaaaa3456012101111011110aaaaaaa可以改写成转置得到Q34563456012011101110111aaaaaaaaaaa信息位的行矩阵乘矩阵Q就产生出监督位K行r列Q=PTP0111011101110001001001001000][QIGk在Q矩阵的左边再加上一个k×k的单位矩阵，就形成了一个新矩阵G：典型形式生成矩阵K行n列G称为生成矩阵具有[IkQ]形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。这种形式的码称系统码。由生成矩阵G及信息位可以产生整个码组G34560123456aaaaaaaaaaa01110111011100010010010010003456aaaa线性分组码例【1】已知线性分组码的生成矩阵为求（1）求其监督矩阵H,确定(n,k)中的n和k;（2）写出监督位的关系式，以及该线性分组码的所有许用码组。110011101100010001G（1）因为给出的生成矩阵G是典型阵，所以可以得到由Q推出：110011101Q101110011P100010001101110011rIPH可得：n=6k=3（2）线性分组码的监督关系由其监督矩阵H来确定：000035134245aaaaaaaaa0000001000100011011100110012345aaaaaaAHTT推出：根据350341452aaaaaaaaa000001010011100101110111B求许用码组线性分组码000111110011011101101001101110011010110100000000110011101100010001111011101001110010100000GB例2已知（7，4）码的生成矩阵为：0111011101110001001001001000G列出所有许用码组并求监督矩阵错码矩阵和错误图样设发送码组A为n列的行向量设接收码组B为n列的行向量0121bbbbnnB发送码组和接收码组之差为B–A=E(模2)E—传输中产生的错码行矩阵0121eeeennEiiiiiababe当当,1,0错码矩阵有时也称为错误图样021,,,aaaAnn接收端译码接收端译码时计算SEHEHAHHEABHTTTTT)(错误图样与校正子之间有确定的关系无错时，S等于零有错，S不等于零。校正子(伴随式)例设验证3个接收码组是否发生差错？若在某码组中有错码，错码的校正子是什么？然后再指出发生错码的码字中，哪位有错？100101010110001011H1011101B1101012B1100003B且有3个接收码组解：1）若无错，则错误图样为0，S为000011THBSB1无错10122THBSB2错11033THBSB3错2）∵S2=H第1列∴E=[100000]第1位错同理S3=H第3列∴E=[001000]第3位错TEHS错误图样e校正子E1:100000101E2:010000110E3:001000011E4:000100100E5:000010010E6:000001001