編碼理論

其逆變換稱為解碼或解碼。根據編碼的目的不同，編碼理論有三個分支：①信源編碼。對信源輸出的信號進行變換，包括連續信號的離散化，即將模擬信號通過採樣和量化變成數字信號，以及對數據進行壓縮，提高數字信號傳輸的有效性而進行的編碼。②通道編碼。對信源編碼器輸出的信號進行再變換，包括區分通路、適應通道條件和提高通信可靠性而進行的編碼。③保密編碼。對通道編碼器輸出的信號進行再變換，即為了使信息在傳輸過程中不易被人竊取而進行的編碼。編碼理論在數字化遙測遙控系統、電氣通信、數字通信、圖像通信、衛星通信、深空通信、計算技術、數據處理、圖像處理、自動控制、人工智慧和模式識別等方面都有廣泛的應用。

歷史背景 1843年美國著名畫家S.F.B.莫爾斯精心設計出莫爾斯碼，廣泛應用在電報通信中。莫爾斯碼使用三種不同的符號：點、划和間隔，可看做是順序三進位碼。根據編碼理論可以證明，莫爾斯碼與理論上可達到的極限只差15％。但是直到20世紀30～40年代才開始形成編碼理論。1928年美國電信工程師H.奈奎斯特提出著名的採樣定理，為連續信號離散化奠定了基礎。1948年美國應用數學家C.E.香農在《通信中的數學理論》一文中提出信息熵的概念，為信源編碼奠定了理論基礎。1949年香農在《有雜訊時的通信》一文中提出了通道容量的概念和通道編碼定理，為通道編碼奠定了理論基礎。無噪通道編碼定理（又稱香農第一定理）指出，碼字的平均長度只能大於或等於信源的熵。有噪通道編碼定理（又稱香農第二定理）則是編碼存在定理。它指出只要信息傳輸速率小於通道容量，就存在一類編碼，使信息傳輸的錯誤概率可以任意小。隨著計算技術和數字通信的發展，糾錯編碼和密碼學得到迅速的發展。

在信源編碼方面，1951年香農證明，當信源輸出有冗餘的消息時可通過編碼改變信源的輸出，使信息傳輸速率接近通道容量。1948年香農就提出能使信源與通道匹配的香農編碼。1949年美國麻省理工學院的R.M.費諾提出費諾編碼。1951年美國電信工程師D.A.霍夫曼提出更有效的霍夫曼編碼。此後又出現了傳真編碼、圖像編碼和話音編碼，對數據壓縮進行了深入的研究，解決了數字通信中提出的許多實際問題。

在糾錯編碼方面,1948年香農就提出一位糾錯碼(碼字長,信息碼元數)。1949年出現三位糾錯的格雷碼(碼字長，信息碼元數)。1950年美國數學家R.W.漢明發表論文《檢錯碼和糾錯碼》，提出著名的漢明碼，對糾錯編碼產生了重要的影響。1955年出現卷積碼。卷積碼至今仍有很廣泛的應用。1957年引入循環碼。循環碼構造簡單，便於應用代數理論進行設計，也容易實現。1959年出現能糾正突發錯誤的哈格伯爾格碼和費爾碼。1959年美國的R.C.博斯和D.K.雷·喬達利與法國的A.奧昆岡幾乎同時獨立地發表一種著名的循環碼，後來稱為 BCH碼(即Bose-Chaudhuri-Hocquenghem碼)。1965年提出序貫解碼。序貫解碼已用於空間通信。1967年A.J.維特比提出最大似然卷積解碼，稱為維特比解碼。1978年出現矢量編碼法。矢量編碼法是一種高效率的編碼技術。1980年用數論方法實現里德－所羅門碼（Reed-Solomon碼）,簡稱RS碼。它實際上是多進位的BCH碼。這種糾錯編碼技術能使編碼器集成電路的元件數減少一個數量級。它已在衛星通信中得到了廣泛的應用。RS碼和卷積碼結合而構造的級連碼，可用於深空通信。

在密碼學方面，1949年香農發表《保密系統的通信理論》，通常它被認為是密碼學的先驅性著作。1976年狄菲和赫爾曼首次提出公開密鑰體制，為密碼學的研究開闢了新的方向。超大規模集成電路和高速計算機的應用，促進了保密編碼理論的發展，同時也給保密通信的安全性帶來很大的威脅。70年代以來把計算機複雜性理論引入密碼學，出現了所謂P類、NP類和NP完全類問題。演演算法的複雜性函數呈指數型增長，因此密鑰空間擴大，使密碼的分析和搜索麵臨嚴重的挑戰。密碼學開始向縱深方向發展。

信源編碼 廣義的信源編碼包括模數轉換（即把模擬量變換成二進位的數字量）和數據壓縮（即對這些數字量進行編碼來降低數碼率）兩個方面。信源編碼的主要任務是壓縮數據。它有四種基本方法：①匹配編碼。這種方法是根據編碼對象的出現概率（概率分佈），分別給予不同長短的代碼，出現概率越大，所給代碼長度越短。這裡所謂匹配就是指代碼長度與概率分佈相匹配。莫爾斯碼是一種匹配編碼。匹配編碼還常採用去相關性的方法進一步壓縮數據。②變換編碼。這種方法是先對信號進行變換，從一種信號空間變換成另一種信號空間，然後針對變換后的信號進行編碼。變換編碼在話音和圖像編碼中有廣泛的應用。目前常用的變換編碼有預測編碼和函數編碼兩類。預測編碼是根據信號的一些已知情況來預測信號即將發生的變化。它不傳送信號的採樣值，而傳送信號的採樣值與預測值之差。預測編碼用在數字電話和數字電視中。函數變換最常用的是快速傅里葉變換 (FFT)、餘弦變換、沃爾什變換、哈爾變換和阿達馬變換等。通過變換可得到信號的頻譜特性，因而可根據頻譜特點來壓縮數碼。③矢量編碼。這種方法是將可能傳輸的消息分類按地址存儲在接收端的電子計算機資料庫中，發送端只發送資料庫的地址，即可查出消息的內容，從而大大壓縮發送的數據。④識別編碼。這種方法主要用於有標準形狀的文字、符號和數據的編碼。但話音也可以進行識別編碼。識別編碼的作用不僅限於壓縮數據，它在模式識別中也有廣泛的應用。常用的識別方法有關聯識別和邏輯識別等方法。識別編碼可大大壓縮數據。例如，用話音識別的方法傳輸話音，平均數碼率小於100比特／秒。而用Δ調製話音的方法傳輸話音，數碼率達38400比特／秒。兩者相差約400倍。但識別編碼在恢復時是根據一個代碼恢復一個標準聲音，只能用於不必知道發話人是誰的特殊電話和問答裝置。識別編碼用於文字傳輸時，恢復出來的都是印刷體符號，只能用於普通電報。

通道編碼 通道編碼的主要任務是為了區分通路和增加通信的可靠性。以區分通路為主要目的的編碼常採用正交碼。以增加通信可靠性為主要目的的編碼常採用糾錯碼。正交碼也具有很強的抗干擾能力。在通道編碼中也採用檢錯碼。

信源編碼器輸出 k位碼元一組的碼。它們攜帶著信息，稱為信息元。這樣的信息元通過通道編碼器后，變換成 n位碼元一組的碼字。信息元和碼字是一一對應的。

正交碼 碼字與碼字之間互相關係數為 0的碼稱為正交碼，在通道編碼時主要利用它的正交性去區分通路，但它本身也可以攜帶信息。最常用的正交碼有偽隨機碼(如 m序列、L序列、巴克序列、M序列等)和沃爾什函數序列。若一個正交信號集的補集也被利用，則可用碼組數將增加一倍，這樣的正交碼稱為雙正交碼。里德-米勒碼（Reed-Muller碼）就是一種雙正交碼。正交碼廣泛用於通信、雷達、導航、遙控、遙測和保密通信等領域。

檢錯碼 有發現錯誤能力的碼稱為檢錯碼。常用的檢錯碼有奇偶校驗碼和等重碼。採用檢錯碼的通信系統要有反饋通道，當發現收到的信號有錯誤時，通過反饋通道發出自動請求重發(ARQ)的信號。

糾錯碼 接收到錯誤的碼字后能在解碼時自動糾正錯誤的碼稱為糾錯碼。糾錯碼是一種重要的抗干擾碼，可增加通信的可靠性。糾錯碼是利用碼字中有規律的冗餘度，即利用冗餘度使碼字的碼元之間產生有規律的相關性，或使碼字與碼字之間產生有規律的相關性。通常把信息元中的碼元數k與對應碼字的碼元數 n的比值R稱為編碼效率，即，碼字的冗餘度為。

糾錯碼有兩類：分組碼和卷積碼。分組碼常記作(n，k)碼，其中n是一個碼字的碼元數（即碼字長），k是信息碼元數，是監督碼元數。在一個碼字中，如果信息碼元安排在前k位，監督碼元安排在後n-k位，這種碼稱為組織碼或系統碼。如果分組碼中任何兩個 n比特的碼字進行模2相加（即不進位的普通二進位加法，模2加法記號是嘰）可得到另一個碼字，這種碼稱為群碼。任何一致監督分組碼都是群碼。如果一個碼字經過循環以後必然是另一個碼字，這種碼稱為循環碼。循環碼是群碼的一個重要子集。著名的BCH碼是一種循環群碼。能糾正突發錯誤的費爾碼是一種分組循環碼。漢明碼也是一種群碼。通常把兩個碼字之間不同碼元的數目稱為漢明距離。兩兩碼字之間漢明距離的最小值稱為最小漢明距離，它是漢明碼檢錯糾錯能力的重要測度。漢明碼要糾正E個錯誤，它的最小漢明距離至少必須是；要發現最多E個錯誤，其最小漢明距離應為。

如果特定的一致監督關係不是在一個碼字中實現，而是在m個碼字中實現，這種碼稱為卷積碼。卷積碼可用移位寄存器來實現，這種卷積編碼器的輸出可看作是輸入信息碼元序列與編碼器響應函數的卷積。能糾正突發錯誤的哈格伯爾格碼也是一種卷積碼。在平穩高斯雜訊干擾的通道上採用序貫解碼方法的卷積碼有很好的性能，能用於衛星通信和深空通信。

保密編碼 為了防止竊譯而進行的再編碼稱為保密編碼。其目的是為了隱藏敏感的信息。它常採用替換或亂置或兩者兼有的方法。一個密碼體制通常包括兩個基本部分：加（解）密演演算法和可以更換的控制演演算法的密鑰。密碼根據它的結構分為序列密碼和分組密碼兩類。序列密碼是演演算法在密鑰控制下產生的一種隨機序列，並逐位與明文混合而得到密文。其主要優點是不存在誤碼擴散，但對同步有較高的要求。它廣泛用於通信系統中。分組密碼是演演算法在密鑰控制下對明文按組加密。這樣產生的密文位一般與相應的明文組和密鑰中的位有相互依賴性，因而能引起誤碼擴散。它多用於消息的確認和數字簽名中。

密碼學還研究通過破譯來截獲密文的方法。破譯方法有確定性分析法和統計性分析法兩類。確定性分析法是利用一個或幾個未知量來表示所期望的未知量從而破譯密文。統計分析法是利用存在於明文與密文或密鑰之間的統計關係破譯密文。

參考書目

張宏基編著：《信源編碼》，人民郵電出版社，北京，1980。

漢明著，朱雪龍譯：《編碼和信息理論》，科學出版社，北京,1984。(R.W.Hamming, Coding and Infomation Theory，Prentice-Hall, 1980.)