reed-muller

Reed-Muller碼是差錯控制編碼技術的一種。

基本介紹

• 中文名：reed-muller
• 性質：差錯控制編碼技術的一種
• 提出者：R.Hamming和M.Golay
• 提出時間：20世紀40年代

差錯控制編碼理論的起源和發展

1948年，Bell實驗室的C.E.Shannon發表的《通信的數學理論》，是關於現代信息理論的奠基性論文，它的發表標誌著信息與編碼理論這一學科的創立。Shannon在該文中指出，任何一個通信信道都有確定的信道容量C，如果通信系統所要求的傳輸速率R小於C，則存在一種編碼方法，當碼長n充分大並套用最大似然解碼（MLD，MaximumLikelihoodDecoding）時，信息的錯誤機率可以達到任意小。從Shannon信道編碼定理可知，隨著分組碼的碼長n或卷積碼的約束長度N的增加，系統可以取得更好的性能（即更大的保護能力或編碼增益），而解碼的最優算法是MLD，MLD算法的複雜性隨n或N的增加呈指數增加，因此當n或N較大時，MLD在物理上是不可實現的。因此，構造物理可實現編碼方案及尋找有效解碼算法一直是信道編碼理論與技術研究的中心任務。

Shannon指出了可以通過差錯控制碼在信息傳輸速率不大於信道容量的前提下實現可靠通信，但卻沒有給出具體實現差錯控制編碼的方法。20世紀40年代，R.Hamming和M.Golay提出了第一個實用的差錯控制編碼方案，使編碼理論這個套用數學分支的發展得到了極大的推動。通常認為是R.Hamming提出了第一個差錯控制碼。當時他作為一個數學家受僱於貝爾實驗室，主要從事彈性理論的研究。他發現計算機經常在計算過程中出現錯誤，而一旦有錯誤發生，程式就會停止運行。這個問題促使他編制了使計算機具有檢測錯誤能力的程式，通過對輸入數據編碼，使計算機能夠糾正這些錯誤並繼續運行。Hamming所採用的方法就是將輸入數據每4個比特分為一組，然後通過計算這些信息比特的線性組合來得到3個校驗比特，然後將得到的7個比特送入計算機。計算機按照一定的原則讀取這些碼字，通過採用一定的算法，不僅能夠檢測到是否有錯誤發生，同時還可以找到發生單個比特錯誤的比特的位置，該碼可以糾正7個比特中所發生的單個比特錯誤。這個編碼方法就是分組碼的基本思想，Hamming提出的編碼方案後來被命名為漢明碼。

雖然漢明碼的思想是比較先進的，但是它也存在許多難以接受的缺點。首先，漢明碼的編碼效率比較低，它每4個比特編碼就需要3個比特的冗餘校驗比特。另外，在一個碼組中只能糾正單個的比特錯誤。M.Golay研究了漢明碼的這些缺點，並提出了兩個以他自己的名字命名的高性能碼字：一個是二元Golay碼，在這個碼字中Golay將信息比特每12個分為一組，編碼生成11個冗餘校驗比特。相應的解碼算法可以糾正3個錯誤。另外一個是三元Golay碼，它的操作對象是三元而非二元數字。三元Golay碼將每6個三元符號分為一組，編碼生成5個冗餘校驗三元符號。這樣由11個三元符號組成的三元Golay碼碼字可以糾正2個錯誤。

漢明碼和Golay碼的基本原理相同。它們都是將q元符號按每k個分為一組．然後通過編碼得到n-k個q元符號作為冗餘校驗符號，最後由校驗符號和信息符號組成有n個q元符號的碼字元號。得到的碼字可以糾正t個錯誤，編碼碼率為為k/n。這種類型的碼字稱為分組碼，一般記為(q,n,k,t)碼，二元分組碼可以簡記為(n,k,t)碼或者(n,k)碼。漢明碼和Golay碼都是線性的，任何兩個碼字經過模q的加操作之後，得到的碼字仍舊是碼集合中的一個碼字。

在Golay碼提出之後最主要的一類分組碼就是Reed-Muller碼。它是Muller在1954年提出的，此後Reed在Muller提出的分組碼的基礎上得到了一種新的分組碼，稱為Reed-Muller碼，簡記為RM碼。在1969年到1977年之間，RM碼在火星探測方面得到了極為廣泛的套用。即使在今天，RM碼也具有很大的研究價值，其快速的解碼算法非常適合於光纖通信系統。