生成矩阵
在编码理论中,生成矩阵(英语:generator matrix)是一个矩阵,该矩阵的行是线性码的一组基。所有码字都是该矩阵的行的线性组合,也就是说,线性码是其生成矩阵的行空间。
术语
若 G 为一矩阵,它生成线性码 C 的码字的方式为,
- w = s G,
其中 w 是线性码 C 的一个码字,而 s 是任意向量。[1] 线性 码的生成矩阵的格式为 ,其中 n 为码字的长度,k 为信息比特的数量(作为向量子空间的 C 的维数),d 为码的最小距离,而 q 为有限域的大小, 即字典中符号的个数(因此 q = 2 表示二元码,等等。)冗余比特的数量用 r = n - k 表示。
生成矩阵的标准形式为,[2]
- ,
其中 是 k×k 单位矩阵而 P 是 k×r 矩阵。当生成矩阵为标准形式时,码 C 在其前 k 个坐标位置为系统码。[3]
生成矩阵可以用来构建一个码的奇偶检验矩阵(反过来也可以)。如果生成矩阵 G 是标准形式 ,那么 C 奇偶校验矩阵就是[4]
- ,
其中 是 矩阵的转置。这是由于 的奇偶检验矩阵是对偶码 的一个生成矩阵。
等价码
如果一个码可以由另一个码通过下列两种变换得到的话,则码 C1 与码 C2 是等价的(记为C1 ~ C2): [5]
- 任意排列码的位置
- 将固定位置上的做置换
等价码的最小距离相同。
参见
注释
- ^ 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. - ^ Ling & Xing 2004,p. 52
- ^ Roman 1992,p. 198
- ^ Roman 1992,p. 200
- ^ 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