1.3 信道編碼問題

信道編碼的歷史仍然可以追溯到香農于1948年出版的那篇著名論文。香農發現，任何通信信道（或存儲信道）都有自己的信道容量C，其單位是比特/秒（bit/s），其物理意義為：當一個通信（或存儲）系統的信息速率R小于信道容量C時，通過使用信道編碼技術，是有可能使得系統輸出的錯誤概率任意小的。但是，香農并沒有指出如何找到合適的碼，他的貢獻主要是證明了這些碼的存在并定義了它們的作用。其后在整個20世紀50年代，人們一直在努力尋找能夠得到任意小錯誤概率且具有明確構造方法的編碼方案，但是進展緩慢。20世紀60年代，人們不再癡迷于這個宏偉的目標，信道編碼的研究方向開始確定下來，并逐漸分成了兩個方向。

1.線性分組碼

第一個研究方向是線性分組碼，該類碼具有嚴格的代數結構，并且主要采用分組碼的形式。歷史上第一種線性分組碼是1950年R.W.Hamming發明的可以糾正1個錯誤的漢明碼。其后不久，Muller提出了一種可以糾正多個錯誤的編碼方法（1954年），緊接著Reed給出了該碼的一種譯碼算法（1954年）。無論是漢明碼還是Reed-Muller碼，其性能距離香農給出的好碼都非常大。之后，學者們付出了大量的辛勤研究工作，但是一直沒有找到更好的碼，直到十年之后，Bose、Ray—Chaudhuri（1960年）和Hocquenghem（1959年）才提出了一類可以糾正多個錯誤的編碼方法，即BCH碼。接著，Reed和Solomon（1960年）以及Arimoto（1961年）分別獨立地發現了一類適用于非二進制信道的編碼方法，即RS碼。

BCH碼的發現引起了一系列關于實用方法的研究工作，人們紛紛通過設計軟件或硬件來實現編碼器和譯碼器。第一種較好的譯碼算法是Peterson于1960年發現的方法，隨后Berlekamp（1968年）和Massey（1969年）發現了一種更為有效的譯碼算法，并且隨著數字電子技術的進步，該算法的實現已成為可能。此外，面向不同的應用和不同的編碼需求，該算法也逐漸出現了很多變種。

2.卷積碼

第二個研究方向是從概率的角度來理解編碼和譯碼的過程，這條道路逐漸產生了序列譯碼（SequentialDecoding）的概念。序列譯碼要求引入長度不定的非分組碼，這種碼可以用樹狀圖來描述，并且可以通過搜索樹狀圖的算法來實現譯碼。其中最為有用的一種樹狀碼（TreeCodes）是高度結構化的卷積碼（ConvolutionalCodes），這種碼可以通過線性移位寄存器電路來生成。到20世紀50年代末，使用基于序列譯碼的算法實現了卷積碼的成功譯碼。其后直到1967年，A.J.Viterbi才提出了一種更為簡單的譯碼算法，即維特比算法。對于中等復雜度的卷積碼，維特比算法獲得了廣泛的使用，但是該算法對于強度更大的卷積碼是不實用的。

經過二十多年的發展，到了20世紀70年代，兩個研究方向在某些領域開始匯聚并相互滲透。J.L.Massey和G.D.Forney開始研究卷積碼的代數理論，開創了卷積碼的一種新的研究視角。而在分組碼領域，人們開始研究碼長較大的好碼的構造方案，G.D.Forney在1966年引入了級聯碼（Concatenatedcodes）的思想，J.Justesen使用該思想設計了一種完全可構造且性能很好的長碼。同時期的V.D.Goppa于1970年定義了一類能夠確保得到好碼的編碼方法，盡管沒有給出如何識別好碼的方法。

到了20世紀80年代，信道編碼器和譯碼器開始頻繁出現在新設計的數字通信系統和存儲系統中。例如，在CD中使用了可以糾正兩個字節錯誤的RS碼；RS碼也常常出現在許多磁帶設備、網絡調制解調器和數字視頻光盤中；而在基于電話線的調制解調器中，代數編碼開始被諸如網格編碼調制（1982年由G.Ungerboeck提出）的歐式空間編碼所取代，這類方法的成功開始引起對基于歐氏距離的非代數編碼方法的研究熱潮。

到了20世紀90年代，信道編碼、信號處理和數字通信之間的界限越來越模糊。Turbo碼的出現可以看作是這個階段的中心事件，用于長二進制碼的軟判決譯碼出現了實用的迭代算法，并且實現了香農給出的性能限。1996年，D.MacKay和M.Neal等人對R.G.Gallager在1963年提出的LDPC碼重新進行了研究，發現該碼具有逼近香農限的優異性能，并且具有譯碼復雜度低、可并行譯碼以及譯碼錯誤的可檢測性等特點，從而成為信道編碼理論新的研究熱點。

進入21世紀，最大的突破性成果是2008年由土耳其畢爾肯大學ErdalArikan教授首次提出的Polar碼。該碼是一種可以實現對稱二進制輸入離散無記憶信道和二進制擦除信道容量的新型代碼構造方法，一出現便在學術界和產業界引起了廣泛關注。