前面介紹過，香農在1948年發表了《通信的一個數學理論》完整地解決了通信速度上限的問題。“信息論”(Information Science)從此誕生。(見上文《數字通信介紹(2)香農與信息論》，http://www.de-sci.org/blogs/fouyang /archives/19714， http://www./pc/pccon.php?id=2721&nid=60453， http://blog.sina.com.cn/s/blog_48dcfed30100chf2.html , http://www.sciencenet.cn/m/user_content.aspx?id=275997 )。但是香農也留下了一個巨大挑戰：怎樣才能達到這個速度上限?這個挑戰，就開闢了後來五十年來十分熱門的研究領域：信道編碼。在繼續讀下去以前，建議讀者先複習一下上文的內容。

　　在數據傳送時，我們不是直接把一個一個數碼(比特)送去調製，而是只傳送一些預先選定的序列(稱為碼字，codewords)。要傳送的數據被對應到相應的碼字來傳送。在接收方，根據收到的碼字就能恢復出原始數據。這種傳送的方法就稱為編碼。編碼的目的可以有多種。一個目的是保密，這裡不討論。另一個目的是加快數據傳送速度。把不常用的數據編成長碼，常用的編成短碼，就能降低碼的平均長度，而傳送更多的數據。上文開始時介紹的摩斯碼就是這個原理。我們現在常用zip程式來壓縮文檔，也是如此。在通信中，這種編碼叫做源編碼(source coding)有時也稱數據壓縮。香農在這方面也有開創性的工作，按下不表。第三個目的，就是糾正噪聲引起的傳送錯誤。這在上文中也有簡單介紹。這種編碼就叫信道編碼(channel coding),也叫糾錯碼(forward error correction, FEC)。信道編碼就是本文的主題。

　　香農在證明他的信道容量定理中，引進了“典型序列”的概念。典型序列就是指序列中的符號出現的比例與符號的先驗概率相同。對於足夠長的序列，所有出現機率不為零的序列都是典型序列。通過選取一些典型序列作為碼字，香農證明了最大傳送速率。但是這個概念實行起來有困難。很長的序列在編碼和解碼兩方面都會非常困難。而如果序列不長的話，就無法利用“典型序列”的概念。所以，香農給出的傳輸速率，在幾十年中都不能達到。

　　最早的編碼類型是分組碼(block code)。這也是最容易理解的一種碼。顧名思義，分組碼這種編碼方式就是把輸入數據(二進制)分為長度固定的組，對每一組分別編碼。比如，最早的分組碼是海明碼，寫為(7，4，3)。它的意思是把數據分成4個比特一組，所以共有2的4次方，也就是16種可能的序列。每個序列對應了一個7比特的碼字。它的編碼率(code rate)是4/7，也就是說在每7比特傳送的數據中，有4比特的有效信息，剩下3比特稱為冗餘(redundancy)。當然，一般說來我們並不能說7 比特中哪個比特是信息哪個比特是冗餘，它們是組合在一起的。

　　(7，4，3)中最後那個數字3，是碼字間的最小距離。碼字間的距離(稱為海明距離)是指它們之間不相同的比特數。比如，兩個碼字A(0010110)和 B(0110011)的海明距離是3，因為它們有三個比特不同(從左數起比特2，5，7)。如果我們收到了(0110110)，我們可以知道傳送的更可能是A，因為它與A只有一個比特不同(比特2)，而與B有兩個比特不同(比特5和7)。換句話說，如果傳送的是A而接收時錯了一位，我們能糾正這個錯誤。如果錯了兩個比特，那它就可能更接近B而導致我們的判斷錯誤。但它還是不等於B，所以我們還是知道出了錯。假如錯三比特的話，那我們就可能認為發射的是B而無法糾正或檢測到錯誤。所以如果碼字間的最小海明距離是3的話，這個碼就可以糾正1比特的錯誤，檢測2比特的錯誤。這裡面的關係，讀者自己想一下就明白了。

　　由此可見，分組碼的性能是由編碼率和最小距離決定的。編碼率決定了同樣調製方式下信息傳輸的速度。最小距離決定了糾錯的能力。糾錯能力越強，就能在越強的噪聲下(也就是越低的信噪比下)保持很低的誤碼率(也就是每一比特信息出錯的幾率)。所以，性能優越的碼，就是要在同樣的編碼率下達到儘可能高的最小距離。我們還記得，香農定理說，在給定的信噪比下有一個最大傳送速率。只要數據轉送速率在此限度以下，就可以做到沒有錯誤。或者反過來說，給定傳送速率時，有一個最小的信噪比，只要信噪比大於這個限度就可以做到沒有錯誤。而對於現實的編碼來說，絕對沒有錯誤是不可能的。對於一個特定的碼，它的傳送速率是固定的。在不同的信噪比下，它有不同的誤碼率。我們可以在一個可以接受的誤碼率(如10的-7次方)下比較它所需要的信噪比與不編碼情況下(同樣的信息傳送速率)的信噪比。這兩者的差稱為編碼增益(coding gain)。編碼增益越大，這個碼的性能就越好。而香農定理給出了編碼增益的上限，這個上限同時也是研究者的努力目標。

　　圖1 給出了描寫編碼性能的一個例子。縱坐標是誤碼率(每個比特出錯的幾率)。橫坐標是信噪比(這裡用分貝即dB來表示。3個分貝的區別意味着噪聲功率差一倍)。這裡信噪比的定義已經考慮了信號傳送速率的區別，所以對各個碼來說是一個公平的比較。對於每個碼，都有誤碼率與信噪比關係的一條曲線。我們可以看到，在較高信噪比的情況下，編碼增益分別約為1分貝，1.5分貝和2.2分貝。而這些碼的性能與香農上限還相差很遠。

　　對實際應用來說，除了糾錯性能外，一個碼要求的運算複雜度也是很重要的。我們上面其實已經給出了一個最直接的，也是最優的解碼方法(稱為最大似然法，Maximum Likelihood)：把收到的數據序列與所有碼字比較，找出海明距離最短的那個作為解碼結果。這樣，運算量就與碼長(上面例子中的4)成指數關係。這對於稍長的碼來說就很難實現了。而實用的分組碼是基於種種數學結構而產生的，編碼和解碼都使用某些數學運算而不是硬性搜尋。這樣運算的複雜度就會低很多。人們為此發展了種種技術。目前通用的也只是普遍認為最好的幾個系列。一般來說，碼越長，糾錯能力就越強，但需要的運算量也就越大。

　　圖一：編碼性能舉例(引自[1]圖4)

　　除了分組碼以外，另一類編碼是卷積碼。它是基於卷積運算，如圖二所示。圖中輸入數據進入移位寄存器。在每一個時鐘點，移位寄存器里儲存的比特依次向前移一位，也就是得到一位(比特)新的輸入數據，同時丟掉一位最老的數據。同時，寄存器里的數據與兩個係數序列(圖上標為碼1和碼2)逐位相乘，結果相加後成為輸出比特。在輸出端，兩個碼產生的兩個輸出比特被依次輸出。注意，以上說的加法是以2為模的。即0+0=0，0+1=1，1+1=0，沒有進位。

　　在這種情況下，每個輸入比特產生兩個輸出比特。所以編碼率是1/2。對於一個傳送序列，開始的一段和最後的一段是收，發雙方約定的，用來幫助解碼。我們也可以說卷積碼是一種很長的分組碼：一個傳送序列就是一個碼組。當然，由於卷積結構的限制，卷積碼的性能並不是同樣長度分組碼中的最優。

　　圖二：卷積碼編碼器舉例

　　卷積碼沒有複雜的代數結構，其解碼方法就是上面描述過的最大似然法。上面說過，這種方法的複雜度與碼長成指數關係。幸運的是，1967年維特比(Viterbi)提出了著名的維特比算法。它遵照最大似然法的原則(因而也是最優的)，但利用了卷積碼的結構，而使得解碼器的複雜度與序列長度成線性關係。這個發明使得卷積碼成為一種實用和有吸引力的編碼方法。

　　維特比算法的基本原理可以用一個簡單的例子來說明。假如我們要找一條從A到B費時最短的路。這就是最大似然法的基本要求。從A到B要經過一座橋C。從A到 C有5條路，從C到B有4條路。這樣組合一下就有20(5×4)種走法，需要做20次測量來找出費時最小的選擇。但是，維特比指出了另一種方法：我們可以先找出A到C的最好路程，需要做5此測量。然後再找出從C到B的最好路程，4次測量。總共測量9次(5+4)，就解決問題了。這個乘法到加法的轉變，就把複雜度從指數增長變成了線性增長。這個問題可以簡化的關鍵在於：我們要優化的參數(時間)是每段路程之值的線性相加。而卷積碼正具有這個特性。

　　以上說的解碼方法，都是基於已經解調的信號(也就是收到的比特序列)。但解調過程中已經丟掉了一些信息。如果我們規定收到-1V為0，1V為1，那麼如果收到0.1V或0.9V，解調的結果都是1。但是這兩種情況下這個“1”的確定程度是不同的，前者更有可能出錯。要提高解碼增益，就要試圖利用這個附加信息，也就是把解調與解碼結合起來。對於分組碼，這樣做法需要特殊的設計。而對於卷積碼，這個要求可以在維特比算法下自然完成。這也就是卷積碼的主要吸引力。

　　卷積碼的另一個特點，就是它在低信噪比條件下解碼增益高，而在高信噪比條件下表現就不那麼好。也就是說，在輸入數據含有很多錯誤時，它可以把誤碼率降低。但在低誤碼率的輸入情況下，它的進一步的糾錯能力就不高了。於是，人們把兩種編碼方法合起來使用。把分組碼作為“外碼”，即最先編碼，最後解碼。而卷積碼作為“內碼”。這樣，在接收器中，收來的信號先經過維特比算法的解調/解碼，產生較低誤碼率的比特序列。這個序列再經過分組碼解碼，進一步降低誤碼率。

　　以上談到的分組碼和卷積碼有一個共性，就是碼字是經過精心設計的，使得碼字之間的最小距離儘可能大，來增強糾錯能力，降低誤碼率。分組碼有着種種特別的數學性質，以便使用巧妙的解碼方法。而卷積碼通常用維特比算法來解碼。另外，還有把調製和卷積碼編碼結合在一起的“格狀編碼調製”(Trellis Coding Modulation, TCM)，這裡就不細談了。這些碼的性能離開香農極限都有幾個分貝。在一段時間內，人們認為要達到香農極限即使可能也是非常困難的。

　　但是柳暗花明，九十年代初期人們走出了另一條路。回到香農定理的證明，那裡的“碼字”就是“典型序列”。而如果我們隨機產生序列的話，只要足夠長，絕大多數結果都是典型序列。所以隨機產生的碼字就是好碼字。問題是，這樣沒有結構的碼沒有好的解碼方法。所以長的隨機碼是不現實的。但是人們發現了具有一定結構的碼也可以具有這樣隨機的特性。而它們的結構可以幫助解碼。首先發現的是turbo碼。它也叫乘積碼。編碼方法是把兩個短碼(分組碼或卷積碼)，一個編碼後把次序按一定規律打亂，再編一次碼。這樣，最後的碼長是兩個短碼長度的乘積。解碼時，也是對於兩個短碼分別解，但採用迭代的辦法。第一次解碼，只是得到一個“可能”的結果。把這個結果及其相關的概率再輸入解碼器一遍，就得到一個更加“可靠”一些的結果。如此反覆，就能提高解碼增益。從理論上講這種方法不一定是最優的，但實際上最後性能非常接近香農極限。Turbo碼也是有結構的，但這個結構不是為了增加碼字間的最小距離，而是為了給解碼提供方便。在 Turbo碼的碼字中，可能有距離很近(也就是很容易出錯)的碼字。但這些碼字只占總體的很小一部分，所以總的來說誤碼率還是很低。而在分組碼，卷積碼中，不同碼字出錯的幾率是差不多的。可見，Turbo碼的思路與以前的編碼技術有很大區別，可以說是一場革命。在此啟發下，又有人重新發現了另一種隨機碼 ——低密度奇偶校驗碼(LDPC)也有類似的特徵。LDPC碼也可以用迭代方法解碼，性能也接近香農極限。LDPC碼早在1960就被提出了，但後來幾十年間這個技術慢慢被人遺忘了。直到1990年代中葉，人們用圖論重新詮釋LDPC碼，找到了系統的設計方法和有效的解碼技術，才使得LDPC重振雄風。

　　隨機碼的發明使得編碼增益大大提高，基本達到了香農極限。到2000年代，這些碼已經被現代通信系統採納了。當然，它們的實現還是比較複雜，所以常常是作為可選功能。

　　從香農的信息論提出後的半個多世紀，人們為了實現香農預言的傳送速度極限作出了巨大的努力，發展了很多精緻有效的數學工具，也進行了很多大海撈針式的搜尋。隨着香農極限的基本達到，編碼的研究是否到了終點呢?當然，性能和複雜性的權衡總是有工作要做的，特別是在硬件性能突飛猛進的今天。另外，除了香農所研究的基本信道外，還有許多更加複雜有趣的信道。特別是無線通信的發展，產生了多天線通信，協同通信等新技術，給信道容量和實現信道容量提出了很多新課題。這些方面我們以後會繼續介紹。

【參考文獻】
[1]D. J. Costello and D. Forney, “Channel Coding: The Road to Channel Capacity”, Proceedings of the IEEE, vol. 95, No. 6, June 2007 p. 1150

相關文章
數字通信介紹（1） 調製
數字通信介紹（2）香農與信息論