第六章 线性分组码纠错编码（FEC）主要分为分组码和卷积码两大类，这一章主要介绍分组码6-1 汉明码（Hamming Code）汉明码是一种基本的线性分组码6-1-1 线性分组码的定义分组码是一种代数编码，它的基本关系一个码字包括独立的信息 元和监督元，其监督元与信息元之间是一种代数关系，如果这种代数 关系为线性的则称为线性分组码分组码的编码器的模型为：[m]=（叫叫"•••mnL | [C]=（Cn-1，Cn-2，-，C0）[m]为编码器的输入，称为信息码元（信息位），它由k位码元组 成[C]为编码器的输出，称为码字矢量，它由n位码元组成，其中 有 k 位信息元， r=n-k 位监督元对于二元编码来说， k 位信息码元 共有 2k 个不同组合，根据编码器为一一对应关系，输出的码字矢量 也应当有2k种码字对于长度为n的二元序列来（n-重）说，共有2n 个可能的码字矢量，编码器只是在这2n个可能码矢中选择2k个码字, 被选中的2k个n-重称为许用码字,其余的2n-2k个码字称为禁用码字, 称这2k个码字矢量的集合为（n,k）分组码信息元监督元［线性分组码定义］:长度为n有2k个码字的分组码，当且仅当 这2k个码字是GF(2)上n维矢量空间(所有n重)的一个k维子空 间时，称为(n,k)线性分组码，简称(n,k)码。
■二元分组码为线性分组码的充要条件为两个码字的模二加也 是一个码字■ 由于 k 维子空间是在模 2 加法下运算的，构成了一个加法交换 群(阿贝尔群)，所以线性分组码也称为群码■线性分组码的一个重要参数为码率(Code rate)： R=k/n;它实际 上也就是编码效率或传输效率■如果(n,k)码位信息位没有变化，与信息码元排列相同，并且与 监督位分开，称为系统码，否则称为非系统码6-1-2 基本监督矩阵(Parity check matrix)线性分组码可以用GF(2)上的矢量空间的矩阵和GF(2)上多项式来 描述，对于汉明码这一类分组码用矩阵描述更为方便［汉明码定义］:对于任意正整数r$3，存在有下列参数的线性分 组码，码长： n=2r-1信息位： k=2r-1-r=n-r监督位： r=n-k最小码距：d . =3min这种码称为狭义汉明码，也称为完备汉明码这种码的码字矢量为：[C] = {Cn-l，Cn-2,……C1，C°}如果对于系统码，其前k位为信息位，后r位位监督位信息位=叫1，叫-2,……，m0] = [Cn-1，Cn-2,……，％]监督位=[c ,……C1,C0]n-k-1 1 0由于线性分组码的监督元与信息元之间的线性关系，可以用二元域上的线性方程组描述。
记为：c =h c +h c + +h cn-k-1 1，n-1 n-1 1，n-2 n-2 1，n-k n-kCn-k-2=h2,n-1 Cn-1 +h2,n-2Cn-2+ +h2,n-kCn-kc =h c +h c + +h c0 r,n-1 n-1 r,n-2 n-2 r,n-k n-k在二元域上， h.j:{0,1}整理这个方程组可得：… h1,n-k10 …… h2,n-k01 …• • •...hr,n-k• • •0• • •0 …cn-1cn-2=[0][H][C]T=[0][C]T为[C]的转置，称矩阵[H]为分组码的基本监督矩阵（一致校验 矩阵，一致监督矩阵）可见系统码的基本监督矩阵为：[H]=[P Ir][P] h h …hl」 1,n 1,n 1,n-1-2-kh2,nh2,n•h2,n-1-2-khr,nhr,n•hr,n-1-2-k10•001•0• • •00••1[Ir]［P］为rXk矩阵,［Ir］为rXr单位阵［举例］：(7,4)系统汉明码, n=7, k=4, r=3[C]=[c6,c5,c4,c3,c2,c1,c0];其中[c c c4,c3]为信息位，[c2,c c0]为监督0 6 5 4 3 2 1 00 11110 0巴 10 110 10=110 10 0 1由[H][C]t= [0]可知：监督方程为: c2=c5+c4+c c1=c6+c4+c c0=c6+c5+c根据这个方程组可以进行编码。
例如信息码元m=［1011］，则有c =c +c +c =0+1+1=02543c =c +c +c =1+1+1=11643c =c +c +c =1+0+1=00653则汉明码字[C]=[1011010]6-1-3 生成矩阵(Generator matrix)(1) ［生成矩阵的基本形式］： 由上面(7,4)汉明码的例子； 可以将基本监督方程扩展写为c6=c6c5=cc4=c4c3=cc2=c5+c4+cc1=c6+c4+cc0=c6+c5+c用矩阵表示：[c6,c5,c4,c3,c2,c1,c0]=3],m2,m1,1 0 0 0 0 1 10 1 0 0 1 0 10 0 1 0 1 1 00 0 0 1 1 1 11000011[c ,c ,c ,l 6 5 40100101u rc ]. o J001011030001111[c6,c5,c4,c3,c2,c1,c0]［汉明码字］=［信息码字］［生成矩阵］可以写为：[C]=[m3,m2,m1,m0].[G][G]称为(7,4)汉明码的生成矩阵例如：[m]=[1100], [C]=[1100][G]=[1100110]可以看出：（n,k）码的生成矩阵的基本形式为:[G]g1,n-g1,n.g1,1g1,01-2g2,n-g2,n.g2,1g2,01• • •-2• • •• • • • • •• • •gk,n-gk,n. gk,1gk,01-2同样，利用生成矩阵的编码关系为[C]=[m][G]而系统（n,k）码的生成矩阵的基本形式应当为10.0g1,n- .k-1g1,0[G]01.0g2,n- .g2,0—0k-1• • •• • •• • • • • •• • •00.1gk,n- .gk,0k-1这种系统码的生成矩阵也称为典型生成矩阵，其基本形式为；[G] =[Ik，Q], [Q]为 kXr 矩阵，[IJ为 kXk 单位阵。
2）[系统码基本监督矩阵与典型生成矩阵的关系]:从生成矩阵与码字矢量的关系可以看出：[G]矩阵的每一行都是一 个码字矢量，分别对应信息码字[10...0],[010...0]...[00...01啲分组码 的码字由于每一行都是码字，把每一行作为一个码字矢量，都应当满足 监督矩阵所规定的监督关系，即应当有:[H] [G]t=[0],同时有：[G][H]t=[0]称[H]与[G]为正交矩阵，由[P Ir] [Ik Q]T=[0][P+QT]=[0] [P]=[Q]T [Q] = [P] TP 矩阵与 Q 矩阵互为转置矩阵对于系统码，已知监督矩阵[H]就可以确定典型生成矩阵[G],反 之，已知生成矩阵也就可以确定监督矩阵3）[生成矩阵的一般性质]：根据线性分组码的定义，（n,k）线性分组码[C]是二元n重矢量空间 中的一个k维子空间，因此，在码字[C]的集合中（2k个码元的码组 中），可以找到k个线性独立的码字，gl，g2，^gk；使[C]中的所有码字 都是这k个码字的线性组合g1 = [g1,n-1,g1,n-29 ,g1,0]g2=[g2,n-1,g2,n-29 ,g2,0]• • •gk=[gk,n-1,gk,n-2? ,gk,0][C]=mn-igi+mn-2g2+……+叫-&其 中 系 数 就 是 信 息 码 字 矢 量 的 元 素 ： [mn-1，mn-2……mn-k] = [mk-1，mk-2……叫]■根据线性矢量空间的知识，这k个码字矢量就可以张成（生成） 这个k维子空间，将这k个矢量组成的矩阵就是（n,k）分组码的 生成矩阵。
所以生成矩阵是一个k行n列的矩阵■确定（n,k ）码的生成矩阵的问题实际上就是确定n-重矢量空间 中k维子空间的k个线性无关的码字矢量的问题也就是寻找 基底的问题■ (n,k)码的n-重矢量空间中的一个k维子空间的基底可以有多 个，因此可以有不同的生成矩阵[G],但都产生相同的码组■ (n,k)码的n-重矢量空间中可以有多个k维子空间，产生不同的 码组)(4) [非系统汉明码]： 可以证明非系统汉明码的一致监督矩阵可以用一种简单方法得 到例如：(7,4)非系统汉明码的[H]为0 0 0 1 1 1 1[H] 0 1 1 0 0 1 110 10 10 1其每一例都是二进制数的1，2, 3 利用[H][C]t= [0]的基本关系,可以得到非系统形式的汉明码通过[H]矩阵的列换位，可以将[H]变 为系统码的形式6-1-4 校验子与译码(Syndrome Matrix and Decoding)设发送码字为：[C]=(c c 2,……,c0)；由于信道干扰产生差错，n-1 n-2 0反映到接收码字上可以用一个二元矢量[E]表示，称为错误图样(error patterns)，[E]=(en-1,en-2, ,e0)其中： ei=1 表明相应位有错， ei=0 表明相应位无错。
这时接收码ii字可以表示为，[R] = [C] + [E]=(Cn-1+en-1,Cn-2+en-2,……丁即译码器的作用就是从接收码字[R]中得到发送码字的估计值，或者 说从接收码字中确定错误图样[E],然后由[C]=[R]-[E]得到发送码字的 估计值，如果估计正确则译码正确，否则译码错误定义[S]为校验 子（伴随式）：[S]=[R][H]T=[C][H]T+[E][H]T=[E][H]T 或 [S]T=[H][R]T=[H][C]T+[H][E]T=[H][E]T （本教材的表示方法）⑸= [Sr，Sr-F S1]= [Sn-k，Sn-k『 计]可以看出：如果校验子矢量[S]H0,接收码字一定有错误，如果 校验子矢量[S]=0,译码器认为接收码字无错误下面通过例子说明校验子的作用7,4）汉明码的基本监督矩阵[H]为已知，0 11110 0巴 10 110 10=110 10 0 1由其得到的汉明码字如下表：000000001001001000100011011000000010101101100000001010010110011001110110111111010100100100。