7线性分组码

编码技术•交织编码技术时间幅度到译码器原始数据123456789交织矩阵123456789发射机交织后的数据147258369射频传输信道经过空中传输后的交织数据147258369集中差错De-InterleavingMatrix123456789解交织后的数据123456789接收机差错分配•优点交织技术是改变数据流的传输顺序，将突发的错误随机化。提高纠错编码的有效性。•缺点：由于改变了数据流的传输顺序，必须要等整个数据块接收后才能纠错加大了处理延时，因此交织深度应根据不同的业务要求选择。信道编码和交织技术的结合使用床前明月光春眠不觉晓白发三千丈红豆生南国床床前前明明月月光光春春眠眠不不觉觉晓晓白白发发三三千千丈丈红红豆豆生生南南国国床春白红床春白红前眠发豆前眠发豆明不三生明不三生月觉千南月觉千南光晓丈国光晓丈国床春白红？？？？？？？？前眠发豆明不三生明不三生月觉千南月觉千南光晓丈国光晓丈国床？？前明明月月光光春？？眠不不觉觉晓晓白？？发三三千千丈丈红？？豆生生南南国国编码交织去交织解码突发错误2线性分组码–线性分组码的定义和特点•线性分组码，是指信息码元与监督码元之间的关系可以用一组线性方程来表示的分组码，即在（n，k）分组码中，每一个监督码元都是码组中某些信息码元按模2和而得到的，线性分组码是一类重要的纠错码，应用很广。–线性分组码的一般原理•线性分组码的构造–H矩阵（监督阵）000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa）（模20001011001110101011101000123456aaaaaaaHAT=0T或AHT=0监督阵»H矩阵的性质：H的行数就是监督关系式的数目，等于监督位个数r。典型监督阵可分解为[PIr]形式，P为rk阶矩阵，Ir为rr阶单位方阵。由代数理论可知，H矩阵的各行应该是线性无关的rPIH0011011010110110011100110001101001011001001111000QGkIG34560123456aaaaaaaaaaaGA][3456aaaa生成阵如果找到了码的生成矩阵G，则编码的方法就完全确定了。具有[IkQ]形式的生成矩阵称为典型生成矩阵。系统码»G矩阵的性质：G矩阵的各行是线性无关的。G的各行本身就是一个码组。如果已有k个线性无关的码组，则可以用其作为生成矩阵G。3.线性分组码的译码——伴随式（校正子）S•若某一码字为许用码组，则它必然满足式AHT=0。利用这一关系，在接收端将收到的码组和事先与发端约定好的监督矩阵相乘，看是否为零。若满足条件，则认为接收正确；反之，则认为传输过程中发生了错误，进而设法确定错误的数目和位置。例4.1（6，3）二进制分组码的输入信息组是m=(),码组输出是c=()。已知输入、输出码元之间的关系式是，求码集C。解：将关系式列成线性方程组，然后写成矩阵形式如下：210mmm543210cccccc52412211210020,,,,cmcmcmmcmmmcmm543210210100111)()010110001011ccccccmmmcmG5241302211210020cmcmcmcmmcmmmcmm2生成矩阵和校验矩阵二进制码取值于GF(2),6位二进制有=64种组合，而3位的信息组只有8种组合，一一对应到8个码字。可见，码集C包含64种组合中的8种。分别令信息组为（000），（001），…，（111），带入上面的矩阵算式，不难算得各信息组对应的码字如下表所示：62210mmm信息组()码字（)000000000000001011010010110011011101100100111101101100110110001111111010210mmm543210cccccc4.2生成矩阵和校验矩阵例：设分组码(n,k)中k=4，为了纠正1位错码，由上式可知，要求监督位数r3。若取r=3，则n=k+r=7。S1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码错码位置与校正子关系监督关系式24561aaaaS13562aaaaS03463aaaaS•令S=BHT，称为伴随式或校正子。•S=BHT=（A+E）HT=EHT•由此可见，伴随式S与错误图样E之间有确定的线性变换关系，与发送码组A无关。接收端译码器的任务就是从伴随式确定错误图样，然后从接收到的码字中减去错误图样。•从以上分析可以得出线性分组码译码的基本步骤：•①计算接收码组B的伴随式S；•②根据S找出错误图样E，判定误码位置；•③根据E纠正错误，得到正确的码组A=E+B。3线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G)0110010(1R?mind例1若线性分组码生成矩阵为：1.试由该矩阵指出（n,k）码的信息位k=?和监督元位数r=?及码长n=?2.求对应的校验矩阵H。3.若接收到一个7位码，它是否码字？若不是,判断所发的码字。4.问其伴随式有多少个？写出该分组码对应一半伴随式数目的译码表。5.该（n,k）码的许用码集中包含多少个码字？用列表的方式写出这些码字。6.该（n,k）码的最小汉明距离7.该（n,k）码的纠错能力为多少位？.3线性分组码的生成矩阵、校验矩阵、伴随式译码1000010000100001H解：1.信息位k=3，监督元位数r=n-k=4，码长n=7。2.101110011100100111001G)0110010(1R例1若线性分组码生成矩阵为：1.试由该矩阵指出（n,k）码的信息位k=?和监督元位数r=?及码长n=?2.求对应的校验矩阵H。3.若接收到一个7位码，它是否码字？若不是,判断所发的码字。.3线性分组码的生成矩阵、校验矩阵、伴随式译码1000110010001100101110001101H)0000()1000(1THR解：1.信息位k=3，监督元位数r=n-k=4，码长n=7。2.3.所以R1不是码字。101110011100100111001G)0110010(1R例1若线性分组码生成矩阵为：1.试由该矩阵指出（n,k）码的信息位k=?和监督元位数r=?及码长n=?2.求对应的校验矩阵H。3.若接收到一个7位码，它是否码字？.3线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例1若线性分组码生成矩阵为：4.伴随式有，THES得到8个伴随式的译码表为：2r=16个由伴随式Si=（s1s2s3s4）错误图案Ei=（e1e2e3e4e5e6e7）1000110010001100101110001101H.3线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例1若线性分组码生成矩阵为：4.伴随式有，THES得到8个伴随式的译码表为：2r=16个由伴随式Si=（s1s2s3s4）错误图案Ei=（e1e2e3e4e5e6e7）E1=0000000E2=0000001E3=0000010E4=0000100E5=0001000E6=0010000E7=0100000E8=10000001000110010001100101110001101H.3线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例1若线性分组码生成矩阵为：4.伴随式有，THES得到8个伴随式的译码表为：2r=16个由伴随式Si=（s1s2s3s4）错误图案Ei=（e1e2e3e4e5e6e7）E1=0000000E2=0000001E3=0000010E4=0000100E5=0001000E6=0010000E7=0100000E8=10000001000110010001100101110001101H.3线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例1若线性分组码生成矩阵为：5.该（n,k）码的许用码集中包含个码字，由C=M*G得到，如下表。信息序列M=(m1m2m3)码字C=(c1c2c3c4c5c6c7)8.3线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例1若线性分组码生成矩阵为：5.该（n,k）码的许用码集中包含个码字，由C=M*G得到，如下表。信息序列M=(m1m2m3)码字C=(c1c2c3c4c5c6c7)0000010101000111011101118.3线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例1若线性分组码生成矩阵为：5.该（n,k）码的许用码集中包含8个码字，由C=M*G得到，如下表。信息序列M=(m1m2m3)码字C=(c1c2c3c4c5c6c7)00000000000010011101010010011110010011100110111010101101001111011010011111110100R1=(0100110)C1=(0100111).3线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例1若线性分组码生成矩阵为：4mind121intmindetc6、6.，该（n,k）码的纠错能力.3线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例1若线性分组码生成矩阵为：4mind121intmindetc51minkndtiinknC02162kn80tiinC6、6.，该（n,k）码的纠错能力7.（n,k）码是完备码的条件为：此题中：该（n,k）码不是完备码。该（n,k）码不是极大最小距离码。此题中：.3线性分组码的生成矩阵、校验矩阵、伴随式译码101110011100100111001G例1若线性分组码生成矩阵为：4mind121intmindetc6、6.，该（n,k）码的纠错能力