生成矩陣

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

參考文獻

延伸閱讀

外部連結