生成矩陣

在編碼理論中，生成矩陣（英語：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]