编码方式中的数学知识

1摘要20世纪，数学经历了前所未有的繁荣和发展，它的许多分支都已经成为当前的研究热点，其中编码理论就是热点之一。目前，讲编码的教材，大都直接给出结论，很少解释原理。本文以线性分组码为例，说明数学在编码理论中的重要作用；另一方面，也想唤起人们对知识连贯重要性的认识。关键词线性分组码生成矩阵监督矩阵线性无（相）关线性空间线性子空间常见编码方式中的数学知识在当前高等教育中普遍存在基础知识与后续知识脱节的问题，虽然很多老师已经注意到这一点，但由于课时受限，两者联系的工作很难在课堂上完成。这就要求学生课下自己总结，如果不能做到温故而知新，那么就会总觉得学的是陌生知识，并认为原来学的基础课程没有用，不能加深对知识理解，无法形成科学的知识体系。比如，刚开始学习编码时，只知道生成矩阵G可表示为QI|，监督矩阵H可表示为IQ，但并不知道为什么要这样构造，因此印象和理解都不深刻。经过用学过的线性代数的知识分析后，不但概念清晰了许多，也保持了知识的连贯性，一举两得。以下主要以线性分组码为例，看看它们中运用了哪些熟悉的知识。线性分组码的数学定义表达：信道编码可表示为由编码前的信息码字空间Uk到编码后的码字空间Cn的一个映射f，即：CUnkf:（1）其中kn。若f进一步满足下列线性关系：)()()(''uuuufff（2）其中，与}1,0{)2(GF，u与Uuk'，则称f为线性编码映射。进一步若f为一一对应映射，则称f为唯一可译线性编码。而由f编写的码字)(21ccccn称为线性分组码。)(21uuuuk为编码前的信息码字，其中k2为信息位数，n为码长，而nkR为编码速率。由上述定义可见，一个线性分组编码f是一个从矢量空间)(2kGF到另一个矢量空间)(2nGF上的一组线性变换。Guc（3）即在一般情况下，一个n位码组，它可以由k各信息位的输入信息序列u通过一个矩阵G来产生。我们称G为生成矩阵。二元（7，3）线性分组码的生成矩阵G可表示为QI343|，其中，I3是一个3阶单位阵，Q34是一个所有行都只有一个0元素的43矩阵。因此，G是一个73的矩阵。监督矩阵H可表示为]|[434IQT，它是一个47的矩阵。[3]那么就有QQIQQIHG3434434343]][|[(结果为一43的全0阵)。两个分块矩阵做运算，可以把每个小块看成书一样处理。[4]把G展开有]101111100111****100010001[，先看单位矩阵，它们的行是3维向量，且明显线性无关，因此，把这三个3维向量扩展到7维时，无论后4维添加什么元素，这样的三个7维向量都是线性无关的，所以生成矩阵行线性无关，也就是行满秩，该矩阵的秩为3。同理，监督矩阵列线性无关、满秩，其矩阵的秩为4。线性无关的向量组中每个向量增加相同个数的分量后还是线性无关。[4]令][321gggG,][4321hhhhH,则)(27spanGFgi，)(27spanGFhj[3]编码器输入为一3维向量)(321uuu，编码器输出为一7维向量)(7654321ccccccc，则331332211321321])[(iiiguguguguggguuuGuc（注：此处是模二加求和）可见，输出码序列由ui，i=1，2，3决定，必然是g1，g2，g3，的线性组合，例，)100(u，gc1；)011(u，ggc32；)111(u，gggc321，且只有8种码序列，称为码字空间。该空间是封闭的，因为cguguuguguccliiliiinimiiiniiiimnm313131311)(，其中ccclnm，因)(23GFul，cl仍在该空间中。由于hgji，gi，i=1,2,3,的线性组合c也垂直于hj,j=1,2,3,4。UIQQIUHGUHC]][|[434343设收端接收的信号为ecy，e是错误向量若Hy，则有两种可能：一，0e，即未发生误码；二，e为8种码序列中的一个，上文已经证明，此时y仍属于码子空间，这种错误情况在译码时无法察觉，但引起的误码往往严重，比如)1001110(c、)1110100(e，此时)0111010(y，译码时认为正确，信息序列从（100）错到（011），3位全错！该情况应予以避免。下面分析在实际应用中是怎样把这种概率降到最小的。通过初等变换，任何非系统码生成矩阵，等价于系统码生成矩阵。那么就用系统码生成矩阵来讨论。QIG343|，QIG343|，根据生成矩阵的构造规则，它左边的单位阵不能变，是为了保留信息位，理论上Q34是任意的，都能保证有QQIQQIHG3434434343]][|[，为什么（7，3）码的生成矩阵是]101111100111****100010001[（1），而不是]000110000010****100010001[（2）或是别的呢？这4是因为（1）矩阵的平均码重最大。矩阵（1）的可生成的码序列：（0000000），（1001110），（0100111），（0011101），（1101001），（1010011），（0111010），（1110100）。矩阵（2）的可生成的码序列：（0000000），（1000100），（0100001），（0011000），（1100101），（1011100），（0111001），（1111101）。考虑到输出任一码序列的概率相等，则5.38111iiiwpW，同理38122iiiwpW，再看另一种极端情况]111111111111****100010001[（3），此时38133iiiwpW，可见由（1）矩阵生成的码向量平均码重最大，那么e成为码子空间的一员的概率就最小，有效避免了发生重大错误而未能发觉的情况。再看，]000::::101111100111****100010001[中的列记为)(23GFj，8...2,1j都是不同的3维向量，分别对应于10进制的0-7，共8列，是完备的。因为是完备的，所以每一行i，3,2,1i中的“0”、“1”数目相等，都是42L，注意到去掉任一行后，剩余的为一82矩阵，)(22GF中共有4个不同的2维向量，而该矩阵有8列，可知每个2维向量重复了两次。例如，去掉第2行后，矩阵为]00:::10011111***100001[，其中，2维列向量00T，01T，10T，11T各出现两次。类似地，当人去掉两行后，矩阵退化为行向量，若把该行向量每一位当成1维列向量，则列向量0，1各出现4次。推广到n列k行的矩阵，删掉其中任一行后，剩下一个n列，k-1行的矩阵，这些列向量由所有k-1维2进制向量构成，但每个重复两次。类似地，如果删去j(jk)行，剩下一个n列，k-j行的矩阵，这些列向量由所有k-j维2进制向量构成，但每个重复2j次。看清楚这一点后，我们再看看由矩阵]000::::101111100111****100010001[，生成的码字5的码重（码向量中“1”的个数）。由上边介绍的知识可知，码字是生成矩阵的行i，3,2,1i的线性组合，当只取一行时，显然码重都是4；当取其中两行进行模2加时，输出码字向量的每一位的结果就是该列向量的各元素求和。根据模2加的性质，当各加数中“1”的总个数为奇数时，结果是“1”，否则结果是“0”。而00T，01T，10T，11T中，“1”为奇数个的向量有一半，于是输出码向量中的“1”的个数也是4，即码重是4。例如，信息序列是（110），则编码输出为，)11010010()0010111101001001(21C；当三行全取时，由于8个列向量中，“1”的个数是奇数的向量有一半，所以编码输出的非零码字的码重也是4。因为]000::::101111100111****100010001[中的最后一列是全“0”向量，去掉不影响编码输出码字的码重，于是变为]101111100111****100010001[。推论，当分组码（n,k）的生成矩阵G的列是由所有非零k维向量)(2kiGFv构成(此时，12kn)，编码输出码字的码距相等，都为2212kk，非零码重也都是21k。证明过程类似（7，3）码。这一类码叫做等重码。由于编码效率不高12kknkR，特别是，当k很大时，R趋于0，实际应用中往往采用它的对偶码，也就是Hamming码。由于本人能力和所学知识有限，目前只能对线性分组码做以上分析，希望能起到抛砖引玉的作用，引起大家对知识连贯性的重视。[1]吴伟陵，《信息处理与编码》，人民邮电出版社，1999[2]李道本，“InformationTheoryandChannelCoding”讲义，2004[3]MichaelT.Heath,ScientificComputing,SecondEdition，McGraw-Hill，2001[4]阮传概，《工程高等代数》，北京邮电大学出版社，1997