1、（n,k）线性分组码l线性码：按照一组方程构成的代数码。即每个码字的监督码元是信息码元的线性组合。n基本概念l代数码：建立在代数学基础上的编码。102nnaaaS-监督关系式若 S=0，认为无错（偶监督时）；若 S=1，认为有错。若要构造具有纠错能力的（n，k）码，则需增加督元的数目。2121rrnkr 或 当“=”成立时，构造的线性分组码 称为汉明码),(),(rknrr1212校正子n 构造原理只有一位监督元-检错汉明码的例例21rn 由表可见:仅当一位错码的位置在a2、a4、a5 或a6 时，校正子S1为1；否则S1为 0。16542Saaaa26531Saaaa36430Saaaa65
2、4653613204000aaaaaaaaaaaa654621536430aaaaaaaaaaaa(A)移项运算解出监督位(A)654621536430aaaaaaaaaaaa16542Saaaa26531Saaaa36430Saaaa例例接收端译码检错纠错过程以上构造的线性分组码，称为汉明码。最小码距：121crknrrRnn 当 n很大和 r 很小时，码率 Rc 接近 1。编码效率：),(),(rknrr1212汉明码特点:21rn d0=3（纠1或检2）r 是不小于3的任意正整数000034613562456aaaaaaaaaaaa0100110100101011000101110123
3、45601234560123456aaaaaaaaaaaaaaaaaaaaan线性分组码的一般原理u H-监督矩阵 010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa65432101110100011010100210110010aaaaaaa （模）H A=a6 a5 a4 a3 a2 a1 a00=000监督矩阵 或转置转置“T”r 行n 列111010011010101011001H=P Ir r k 阶矩阵r r 阶方阵 u H 矩阵的性质 H 的行数 等于监督位的数目r。H 的每行中“1”的位置表示相应
4、码元之间存在的监督关系。(7，4)码r=3 H的各行应该是线性无关的，否则得不到r个线性无关的监督关系式。若一矩阵能写成典型阵形式 P Ir，则其各行一定是线性无关的。将上面汉明码例子中的监督位公式：改写成矩阵形式：u G-生成矩阵 654621536430aaaaaaaaaaaa或者写成：6251403aaaaaaa111011011011P 阵6251403aaaaaaa11101101101121065436543a a aa a a aa a a a111110101011Q式中，Q 为一个k r 阶矩阵，它为P 的转置，即:Q=PT P 阵Q 阵 G34560123456aaaaaa
5、aaaaaGA3456aaaa将Q的加上1个k k 阶单位方阵，就构成矩阵:生成矩阵，或者因此，若找到了码的G，则编码的方法就完全确定了。具有IkQ形式的称为由得到的码称为系统码。1000010000111111010100001 011kGQI I码组A中，信息位的位置不变，监督位附在其后。由它可以产生整个码组，即有:u G 矩阵的性质 G 矩阵的各行是线性无关的。GA3456aaaa由式可以看出:任一码组A都是G的各行的线性组合。G共有，若它们线性无关，则可以组合出2k 种不同的码组A。它恰是有k位信息位 的全部码组。u G 和H 的关系 0121bbbbnnB0121eeeenn EA-
6、Biiiiiababe当当,10u 校正子与错误图样 设发送码组为一个n列的行矩阵 A，接收码组的行矩阵 B则发送码组和接收码组之差就是）：0121aaaannA式中(模2)A=B+E例例E 发送接收来进行检测。将 B=A+E 代入上式，可得00000E若,则 S为0，否则 S 不为 0。译码2)由S 找到错误图样E；3)由公式 A=B+E 得到译码器译出的码组。译码 封闭性A1和A2(A1+A2)证明：若A1和A2是两个码组，则有A1 HT=0 和 A2 HT=0，将两式相加，有 A1 HT+A2 HT=(A1+A2)HT=0 最小距离（证毕）n线性分组码的性质a6 a3a2 a1 a0a6
7、 a3a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111表中所列的(7,4)汉明码的最小码距 d0=？d0=3 纠1 或检2根据性质 只需找最小码重无需两两码组比较循 环 码表中的第 2 码组向 右移一位即得到第 5 码组；(7,3)循环码11.6.1 循环码原理表中的第 6 码组向 右移一位即得到第 3码组。注意：码字（1100101）的多项式可表示为：n码多项式 多项式的系数就是码组中的各码元，x 仅是
8、码元位置标记。n=7 例例1.码多项式的按模运算 一般说来，一个整数m 可以表示为npnpQnm,（Q 为整数）m p (模n)在模n 运算下，有 u 码多项式的按模运算：()()()()()F xR xQ xN xN x()()()()F xN x Q xR x或则()()()F xR xN x（模）例例 运算过程：即有 则有）（模)()()(1nixxAxAx这是因为，A(x)正是 A(x)代表的码组向左循环移位 i 次的结果。u循环码的码多项式则 A(x)也是该编码中的一个许用码组。例例1256xxxxA)(循环码组，其码长n=7。现给定 i=3，则）（模)()()(1172353589
9、25633xxxxxxxxxxxxxxAx652()1A xxxx532()A xxxxx01011101100101左移 i 位32.循环码的生成矩阵G 生成矩阵 G可由k 引思：那么，如何寻找这 个线性无关的码组呢？因此，用这个线性无关的码组可构成该循环码的生成矩阵G，即)()()()()(xgxxgxgxxgxxkk21Gr=n-k=7-3=4，001011101011101011100G解2643253242()()()()1x g xxxxxxxg xxxxxg xxxxG例例码组中唯一一个4次码多项式代表的或据此，可以写出此循环码多项式A(x):)()()()()()()()()(
10、)(xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaaaxA452645262456456GA(x)g(x)）（模)()()(1nixxAxAx11nnkxxAxQxxAx)()()(g(x)A(x)=g(x)A(x)=h(x)g(x)A(x)xkA(xn xk A(x)()()(xAxxAxnk1)()(1xhxxgxkn上式左端分子和分母都是n次多项式，故商式Q(x)=1。上式可化成将 和 代入上式，化简后得到11nnkxxAxQxxAx)()()(A(x)=g(x)A(x)=h(x)g(x)求(7,3)循环码的生成多项式 g(x)。例例将(x7+1)进行因式分解：解：n k
11、)()(11113237xxxxxx即有或4327321(1)(1)xxxxxx 4723(111)xxxxxx 11.6.2 循环码的编解码方法1.循环码的编码 信息码(an-1 an-2 an-k)的m(x)=an-1xk-1+an-2 xk-2+an-k其最高次数为k-1 循环码的多项式为：121212()()()()()kknnnknnnkxg xxg xaaaxaaaxg xg xGA(x)=1212()()kknnn kaxaxag x A(x)=m(x)g(x)（1）用 乘（2）作除 xn-k 将信元左移（n k）位，附上（n k）个0，预留给督元。()()()()n kxm x
12、Q xg xxr xg得到余式，作为监督码元 即得循环码的码多项式。循环码的编码步骤：（3）作 A=xn-k 例例编码电路：可采用(n k)级移位寄存器组成的除法电路实现。11101n kn kn kn kg xgxgxg xg 1xx2x4A(x)m(x)例如，上例(7,3)循环码的生成多项式 g(x)=x4+x2+x+1，其编码电路：2.循环码的解码目的：若能除尽，则无错；若除不尽而有余项，则表示在传输中发生错误。检错：纠错：11.6.3 截短循环码n例：构造一个能够纠正1位错码的(13,9)码。可由(15,11)循环码的码组中选出前两信息位均为“0”的码组，构成一个新的码组集合。在发送时
13、不发送这两位“0”。于是发送码组成为(13,9。n截短目的：在设计纠错编码方案时，若找不到合适的码长n及信息位k 时，把循环码的码长截短以得到符合要求的编码。n截短方法：设给定一个(n,k)循环码，它共有 2k 种码组，现使其前 i(0 i k)个信息位全为“0”，于是它变成仅有 2k-i 种码组。然后从中删去这 i 位全“0”的信息位，最终得到一个(n i ,k i)的线性码。n截短循环码性能：循环码截短前后至少具有的纠错能力，并且编解码方法仍和截短前的方法一样。11.6.4 BCH码解决了生成多项式与纠错能力的关系问题，可以在给定纠错能力要求的条件下寻找到码的生成多项式。有了生成多项式，编
14、码的基本问题就随之解决了。n BCH码的重要性:n 何谓BCH码？n BCH码的分类：u汉明码是能够纠正单个随机错误的码。可以证明，具有循环性质的汉明码就是能纠正单个随机错误的本原BCH码。n BCH码的性能：u 码长n 与监督位、纠错个数 t 之间的关系：对于正整数m(m 3)和正整数t 1，且除得尽(2m-1)），则为非本原BCH码。n BCH码的设计：u在工程设计中，一般不需要用计算方法去寻找生成多项式g(x)。因为前人早已将寻找到的g(x)列成表，故可以用查表法找到所需的生成多项式。u教材353页的表11-7 给出了码长n 127的二进制本原BCH码生成多项式。nktg(x)nktg(
15、x)17212333419121222212232472716635343514566471334765657324534046524443073357107613543000671717773537在上表中的(23,12)码称为戈莱(Golay)码。其最小码距为7，能纠3个随机错码；其生成多项式系数 (5343)8=(101 011 100 011)2，对应g(x)=x11+x9+x7+x6+x5+x+1，且解码容易，实际应用较多。BCH码的长度都为奇数。在应用中，为了得到偶数长度的码，并增大检错能力，可以在BCH码生成多项式中乘上一个因式(x+1)，从而得到扩展BCH码(n+1,k)。扩展
16、BCH码相当于在原BCH码上增加了一个校验位，因此码距比原BCH码增加1。扩展BCH码已经不再具有循环性。例如，广泛实用的扩展戈莱码(24,12)，其最小码距为8，码率为1/2，能够纠3个错码和检4个错码。它比汉明码的纠错能力强很多，付出的代价是解码更复杂，码率也比汉明码低。此外，它不再是循环码了。n 扩展BCH码：11.6.5 RS码 它是一类具有很强纠错能力的多进制BCH码。由里德和索洛蒙(Reed Solomon)提出。一个能够纠t个错误符号的m进制的RS码有如下参数：d0=2t+1个 符号，或 q（2t+1）比特n=m 1=2q 1个符号，r=n-k=2t 个符号，或 2tq 比特k 个符号，或 k q个比特参数或 q(2q 1)个比特 能够纠正t个m进制错码，即能纠正码组中t个不超过q位连续的错码，特别适用于存在的信道，例如，移动通信网等中。此外，它是多进制纠错编码，特别适合用于的场合。RS码的生成多项式：g(x)=(x+)(x+2)(x+2t)式中，是伽罗华域GF(2q)中的本原元素。应用
