奇偶檢驗矩陣

編碼理論裡,線性區塊碼 C奇偶檢驗矩陣(英語:parity-check matrix)是描述碼字英語codeword的成分間必須滿足的線性關係的一個矩陣。它可以用來決定一個特定向量是否為碼字,也用在譯碼算法中。

定義

編輯

形式上,線性碼 C 的奇偶檢驗矩陣 H對偶碼 C生成矩陣。這就意味着當且僅當矩陣-向量乘積 Hc = 0(一些作者[1]會寫成其等價形式cH = 0)時,碼字 c 才會在 C 中。

奇偶檢驗矩陣的行是奇偶檢驗方程的係數。[2] 也就是說,它們表示每個碼字中的某些數字(成分)如何線性組合可以等於零。例如,奇偶檢驗矩陣

 ,

緊湊表示了向量   要成為 C 的碼字必須滿足的奇偶檢驗方程,

 .

根據定義,奇偶檢驗矩陣直接遵循該碼的最小距離為,使得奇偶檢驗矩陣 H 的任意 d - 1 列都線性無關並且存在 d 列線性相關的最小數 d

建立奇偶檢驗矩陣

編輯

某一給定碼的奇偶校驗矩陣可以從其生成矩陣導出(反之亦然)。[3] 若一 [n,k] 碼的生成矩陣是標準形式

 ,

則奇偶檢驗矩陣為

 ,

因為

 .

取反是在有限域 Fq 內進行的。注意如果所處的域的特徵為 2(即在這個域中 1 + 1 = 0),如在二元碼英語binary code中一樣,因此 -P = P,所以取反是不需要的。

例如,如果一個二元碼的生成矩陣

 ,

則其奇偶檢驗矩陣就是

 .

伴隨式

編輯

對向量空間環境中的任意(行)向量 xs = Hx 稱為 x伴隨式英語Syndrome decoding。當且僅當 s = 0 時向量 x 為碼字。計算伴隨式是伴隨式譯碼英語syndrome decoding算法的基礎。[4]

參見

編輯

注釋

編輯
  1. ^ 比如Roman 1992,p. 200
  2. ^ Roman 1992,p. 201
  3. ^ Pless 1998,p. 9
  4. ^ Pless 1998,p. 20

參考文獻

編輯