奇偶檢驗矩陣
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在編碼理論裏,線性區塊碼 C 的奇偶檢驗矩陣(英語:parity-check matrix)是描述碼字的成分間必須滿足的線性關係的一個矩陣。它可以用來決定一個特定向量是否為碼字,也用在譯碼演算法中。
定義
形式上,線性碼 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),如在二元碼中一樣,因此 -P = P,所以取反是不需要的。
例如,如果一個二元碼的生成矩陣
- ,
則其奇偶檢驗矩陣就是
- .
伴隨式
對向量空間環境中的任意(行)向量 x,s = Hx⊤ 稱為 x 的伴隨式。若且唯若 s = 0 時向量 x 為碼字。計算伴隨式是伴隨式譯碼演算法的基礎。[4]
參見
註釋
- ^ 比如Roman 1992,p. 200
- ^ Roman 1992,p. 201
- ^ Pless 1998,p. 9
- ^ Pless 1998,p. 20
參考文獻
- Hill, Raymond. A first course in coding theory. Oxford Applied Mathematics and Computing Science Series. Oxford University Press. 1986: 69. ISBN 0-19-853803-0.
- 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
- J.H. van Lint. Introduction to Coding Theory. GTM 86 2nd. Springer-Verlag. 1992: 34. ISBN 3-540-54894-7.