生成矩阵

Disambig gray.svg  关于概率论中的生成矩阵，请见“转移率矩阵”。

在编码理论中，生成矩阵（英语：generator matrix）是一个矩阵，该矩阵的行是线性码（英语：linear code）的一组基。所有码字都是该矩阵的行的线性组合，也就是说，线性码是其生成矩阵的行空间。

术语

若 G 为一矩阵，它生成线性码 C 的码字（英语：codeword）的方式为，

w = s G,

其中 w 是线性码 C 的一个码字，而 s 是任意向量。[1] 线性   码的生成矩阵的格式为  ，其中 n 为码字的长度，k 为信息比特的数量（作为向量子空间的 C 的维数），d 为码的最小距离，而 q 为有限域的大小, 即字典中符号的个数（因此 q = 2 表示二元码（英语：binary code），等等。）冗余比特的数量用 r = n - k 表示。

生成矩阵的标准形式为，[2]

 ,

其中   是 k×k 单位矩阵而 P 是 k×r 矩阵。当生成矩阵为标准形式时，码 C 在其前 k 个坐标位置为系统码（英语：Systematic code）。[3]

生成矩阵可以用来构建一个码的奇偶检验矩阵（反过来也可以）。如果生成矩阵 G 是标准形式  ，那么 C 奇偶校验矩阵就是[4]

 ,

其中   是   矩阵的转置。这是由于   的奇偶检验矩阵是对偶码   的一个生成矩阵。

等价码

如果一个码可以由另一个码通过下列两种变换得到的话，则码 C1 与码 C2 是等价的（记为C1 ~ C2）： [5]

  1. 任意排列码的位置
  2. 将固定位置上的做置换

等价码的最小距离相同。

参见

注释

  1. ^ MacKay, David, J.C. Information Theory, Inference, and Learning Algorithms (PDF). Cambridge University Press. 2003: 9. ISBN 9780521642989. Because the Hamming code is a linear code, it can be written compactly in terms of matrices as follows. The transmitted codeword   is obtained from the source sequence   by a linear operation,

     

    where   is the generator matrix of the code... I have assumed that   and   are column vectors. If instead they are row vectors, then this equation is replaced by

     

    The rows of the generator matrix can be viewed as defining the basis vectors.     
  2. ^ Ling & Xing 2004，p. 52
  3. ^ Roman 1992，p. 198
  4. ^ Roman 1992，p. 200
  5. ^ Pless 1998，p. 8

参考文献

  • Ling, San; Xing, Chaoping, Coding Theory / A First Course, Cambridge University Press, 2004, ISBN 0-521-52923-9 
  • Pless, Vera, Introduction to the Theory of Error-Correcting Codes 3rd, Wiley Interscience, 1998, ISBN 0-471-19047-0 
  • Roman, Steven, Coding and Information Theory, GTM 134, Springer-Verlag, 1992, ISBN 0-387-97812-7 
  • Welsh, Dominic, Codes and Cryptography, Oxford University Press, 1988, ISBN 0-19-853287-3 

延伸阅读

  • MacWilliams, F.J.; Sloane, N.J.A., The Theory of Error-Correcting Codes, North-Holland, 1977, ISBN 0-444-85193-3 

外部链接