生成矩陣
在編碼理論中,生成矩陣(英語: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