生成矩阵

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

术语

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

w = s G,

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

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

G={\begin{bmatrix}I_{k}|P\end{bmatrix}}

,

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

生成矩阵可以用来构建一个码的奇偶檢驗矩陣（反过来也可以）。如果生成矩阵 G 是标准形式 $G={\begin{bmatrix}I_{k}|P\end{bmatrix}}$ ，那么 C 奇偶校验矩阵就是^[4]

H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}

,

其中 $P^{\top }$ 是 $P$ 矩阵的转置。这是由于 $C$ 的奇偶检验矩阵是对偶码 $C^{\perp }$ 的一个生成矩阵。

等价码

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

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

等价码的最小距离相同。

参见

(7,4)汉明码（英语：Hamming code (7,4)）

注释

^ 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 $\mathbf {t}$ is obtained from the source sequence $\mathbf {s}$ by a linear operation,
$\mathbf {t} =\mathbf {G} ^{\intercal }\mathbf {s}$
where $\mathbf {G}$ is the generator matrix of the code... I have assumed that $\mathbf {s}$ and $\mathbf {t}$ are column vectors. If instead they are row vectors, then this equation is replaced by
$\mathbf {t} =\mathbf {sG}$
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

外部链接

Generator Matrix at MathWorld （页面存档备份，存于互联网档案馆）

[DrMacKayECC-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 $\mathbf {t}$ is obtained from the source sequence $\mathbf {s}$ by a linear operation,
$\mathbf {t} =\mathbf {G} ^{\intercal }\mathbf {s}$
where $\mathbf {G}$ is the generator matrix of the code... I have assumed that $\mathbf {s}$ and $\mathbf {t}$ are column vectors. If instead they are row vectors, then this equation is replaced by
$\mathbf {t} =\mathbf {sG}$
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

[1]

[2]

[3]

[4]

[5]