基本介紹
- 中文名：編碼理論
- 所屬學科：數學、計算機
編碼理論,分支,信源編碼（數據壓縮）,信道編碼（前向糾錯）,歷史背景,信源編碼,基本方法,常用的識別方法,信道編碼,正交碼,檢錯碼,糾錯碼,保密編碼,參考書目,
編碼理論
研究信息傳輸過程中信號編碼規律的數學理論。編碼理論與資訊理論、數理統計、機率論、隨機過程、線性代數、近世代數、數論、有限幾何和組合分析等學科有密切關係，已成為套用數學的一個分支。編碼是指為了達到某種目的而對信號進行的一種變換。其逆變換稱為解碼或解碼。
分支
根據編碼的目的不同，編碼理論有三個分支：
②信道編碼。對信源編碼器輸出的信號進行再變換，包括區分通路、適應信道條件和提高通信可靠性而進行的編碼。
③保密編碼。對信道編碼器輸出的信號進行再變換，即為了使信息在傳輸過程中不易被人竊取而進行的編碼。編碼理論在數位化遙測遙控系統、電氣通信、數字通信、圖像通信、衛星通信、深空通信、計算技術、數據處理、圖像處理、自動控制、人工智慧和模式識別等方面都有廣泛的套用。
信源編碼（數據壓縮）
在計算機科學和資訊理論中，數據壓縮或者源編碼是按照特定的編碼機制用比未經編碼少的數據比特（或者其它信息相關的單位）表示信息的過程。例如，如果我們將“compression”編碼為“comp”那么這篇文章可以用較少的數據位表示。一種流行的壓縮實例是許多計算機都在使用的ZIP檔案格式，它不僅僅提供了壓縮的功能，而且還作為歸檔工具（Archiver）使用，能夠將許多檔案存儲到同一個檔案中。
信道編碼（前向糾錯）
前向糾錯（英語：Forward error correction,縮寫FEC）是一種在單向通信系統中控制傳輸錯誤的技術，通過連同數據傳送額外的信息進行錯誤恢復，以降低誤碼率（bit error rate,BER）。FEC又分為帶內FEC和帶外FEC。FEC的處理往往發生在早期階段處理後的數位訊號是第一次收到。也就是說，糾錯電路往往是不可分區的一部分的模擬到數字的轉換過程中，還涉及數字調製解調，或線路編碼和解碼。
FEC是通過添加冗餘信息的傳輸採用預先確定的算法。1949年漢明（Hamming）提出了可糾正單個隨機差錯的漢明碼。1960年Hoopueghem,Bose和Chaudhum發明了BCH碼，Reed與Solomon又提出ReedSolomon（RS）編碼，糾錯能力很強，後來稱之為里德-所羅門誤碼校正編碼（The reed-solomon error correction code,即後來的附加的前向糾錯）。ITU-T G.975/G.709規定了“帶外FEC”是在SDH層下面增加一FEC層，專門處理FEC的問題。帶外FEC編碼冗餘度大，糾錯能力較強。FEC有別於ARQ，發現錯誤無須通知傳送方重發。一旦系統丟失了原始的數據包，FEC機制可以以冗餘數據包加以補入。例如有一數據包為“10”，分成二個數據包，分別為“1”和“0”，有一冗餘數據包“0”，收到任意兩個數據包就能組裝出原始的包。但這些冗餘數據包也會產生額外負擔。
歷史背景
1843年美國著名畫家S.F.B.莫爾斯精心設計出莫爾斯碼，廣泛套用在電報通信中。莫爾斯碼使用三種不同的符號：點、劃和間隔，可看作是順序三進制碼。根據編碼理論可以證明，莫爾斯碼與理論上可達到的極限只差15%。但是直到20世紀30～40年代才開始形成編碼理論。1928年美國電信工程師H.奈奎斯特提出著名的採樣定理，為連續信號離散化奠定了基礎。1948年美國套用數學家C.E.香農在《通信中的數學理論》一文中提出信息熵的概念，為信源編碼奠定了理論基礎。1949年香農在《有噪聲時的通信》一文中提出了信道容量的概念和信道編碼定理，為信道編碼奠定了理論基礎。無噪信道編碼定理（又稱香農第一定理）指出，碼字的平均長度只能大於或等於信源的熵。有噪信道編碼定理（又稱香農第二定理）則是編碼存在定理。（見香農三大定理）它指出只要信息傳輸速率小於信道容量，就存在一類編碼，使信息傳輸的錯誤機率可以任意小。隨著計算技術和數字通信的發展，糾錯編碼和密碼學得到迅速的發展。
在信源編碼方面
1951年香農證明，當信源輸出有冗餘的訊息時可通過編碼改變信源的輸出，使信息傳輸速率接近信道容量。1948年香農就提出能使信源與信道匹配的香農編碼。1949年美國麻省理工學院的R.M.費諾提出費諾編碼。1951年美國電信工程師D.A.哈夫曼提出更有效的哈夫曼編碼。此後又出現了傳真編碼、圖像編碼和話音編碼，對數據壓縮進行了深入的研究，解決了數字通信中提出的許多實際問題。
在糾錯編碼方面
1948年香農就提出一位糾錯碼(碼字長=7，信息碼元數=4)。1949年出現三位糾錯的格雷碼(碼字長=23，信息碼元數=12)。1950年美國數學家理察·衛斯里·漢明發表論文《檢錯碼和糾錯碼》，提出著名的漢明碼，對糾錯編碼產生了重要的影響。1955年出現卷積碼。卷積碼至今仍有很廣泛的套用。1957年引入循環碼。循環碼構造簡單，便於套用代數理論進行設計，也容易實現。1959年出現能糾正突發錯誤的哈格伯爾格碼和費爾碼。1959年美國的R.C.博斯和D.K.雷·喬達利與法國的A.奧崑岡幾乎同時獨立地發表一種著名的循環碼，後來稱為BCH碼(即Bose-Chaudhuri-Hocquenghem碼)。1965年提出序貫解碼，序貫解碼已用於空間通信。1967年A.J.維特比提出最大似然卷積解碼，稱為維特比解碼。1978年出現矢量編碼法。矢量編碼法是一種高效率的編碼技術。1980年用數論方法實現里德－所羅門碼（Reed-Solomon碼），簡稱RS碼。它實際上是多進制的BCH碼。這種糾錯編碼技術能使編碼器積體電路的元件數減少一個數量級。它已在衛星通信中得到了廣泛的套用。RS碼和卷積碼結合而構造的級連碼，可用於深空通信。
在密碼學方面
信源編碼
基本方法
它有四種基本方法：
①匹配編碼。這種方法是根據編碼對象的出現機率（機率分布），分別給予不同長短的代碼，出現機率越大，所給代碼長度越短。這裡所謂匹配就是指代碼長度與機率分布相匹配。莫爾斯碼是一種匹配編碼。匹配編碼還常採用去相關性的方法進一步壓縮數據。
②變換編碼。這種方法是先對信號進行變換，從一種信號空間變換成另一種信號空間，然後針對變換後的信號進行編碼。變換編碼在話音和圖像編碼中有廣泛的套用。常用的變換編碼有預測編碼和函式編碼兩類。預測編碼是根據信號的一些已知情況來預測信號即將發生的變化。它不傳送信號的採樣值，而傳送信號的採樣值與預測值之差。預測編碼用在數字電話和數位電視中。函式變換最常用的是快速傅立葉變換 (FFT)、餘弦變換、沃爾什變換、哈爾變換和阿達馬變換等。通過變換可得到信號的頻譜特性，因而可根據頻譜特點來壓縮數碼。
③矢量編碼。這種方法是將可能傳輸的訊息分類按地址存儲在接收端的電子計算機資料庫中，傳送端只傳送資料庫的地址，即可查出訊息的內容，從而大大壓縮傳送的數據。
④識別編碼。這種方法主要用於有標準形狀的文字、符號和數據的編碼。但話音也可以進行識別編碼。識別編碼的作用不僅限於壓縮數據，它在模式識別中也有廣泛的套用。
常用的識別方法
有關聯識別和邏輯識別等方法。識別編碼可大大壓縮數據。例如，用話音識別的方法傳輸話音，平均數碼率小於100比特/秒。而用Δ調製話音的方法傳輸話音,數碼率達38400比特/秒。兩者相差約400倍。但識別編碼在恢復時是根據一個代碼恢復一個標準聲音，只能用於不必知道發話人是誰的特殊電話和問答裝置。識別編碼用於文字傳輸時，恢復出來的都是印刷體符號，只能用於普通電報。
信道編碼
信道編碼的主要任務是為了區分通路和增加通信的可靠性。以區分通路為主要目的的編碼常採用正交碼。以增加通信可靠性為主要目的的編碼常採用糾錯碼。正交碼也具有很強的抗干擾能力。在信道編碼中也採用檢錯碼。
信源編碼器輸出 位碼元一組的碼。它們攜帶著信息，稱為信息元。這樣的信息元通過信道編碼器後，變換成 位碼元一組的碼字。信息元和碼字是一一對應的。
正交碼
碼字與碼字之間互相關係數為 0的碼稱為正交碼，在信道編碼時主要利用它的正交性去區分通路，但它本身也可以攜帶信息。最常用的正交碼有偽隨機碼(如 m序列、L序列、巴克序列、M序列等)和沃爾什函式序列。若一個正交信號集的補集也被利用，則可用碼組數將增加一倍,這樣的正交碼稱為雙正交碼。里德-米勒碼 （Reed-Muller碼）就是一種雙正交碼。正交碼廣泛用於通信、雷達、導航、遙控、遙測和保密通信等領域。
檢錯碼
糾錯碼
接收到錯誤的碼字後能在解碼時自動糾正錯誤的碼稱為糾錯碼。糾錯碼是一種重要的抗干擾碼，可增加通信的可靠性。糾錯碼是利用碼字中有規律的冗餘度，即利用冗餘度使碼字的碼元之間產生有規律的相關性，或使碼字與碼字之間產生有規律的相關性。通常把信息元中的碼元數與對應碼字的碼元數 的比值R稱為編碼效率，即R=/，碼字的冗餘度為1-R。
糾錯碼有兩類：分組碼和卷積碼。
分組碼
常記作(,)碼，其中是一個碼字的碼元數（即碼字長），是信息碼元數，-是監督碼元數。在一個碼字中,如果信息碼元安排在前位，監督碼元安排在後-位，這種碼稱為組織碼或系統碼。如果分組碼中任何兩個 比特的碼字進行模2相加（即不進位的普通二進制加法，模2加法記號是）可得到另一個碼字，這種碼稱為群碼。任何一致監督分組碼都是群碼。如果一個碼字經過循環以後必然是另一個碼字，這種碼稱為循環碼。循環碼是群碼的一個重要子集著名的BCH碼是一種循環群碼。能糾正突發錯誤的費爾碼是一種分組循環碼。漢明碼也是一種群碼。通常把兩個碼字之間不同碼元的數目稱為漢明距離。兩兩碼字之間漢明距離的最小值稱為最小漢明距離，它是漢明碼檢錯糾錯能力的重要測度漢明碼要糾正E個錯誤，它的最小漢明距離至少必須是2E+1；要發現最多E個錯誤，其最小漢明距離應為E+1。
卷積碼
如果特定的一致監督關係不是在一個碼字中實現，而是在個碼字中實現，這種碼稱為卷積碼。卷積碼可用移位暫存器來實現，這種卷積編碼器的輸出可看作是輸入信息碼元序列與編碼器回響函式的卷積。能糾正突發錯誤的哈格伯爾格碼也是一種卷積碼。在平穩高斯噪聲干擾的信道上採用序貫解碼方法的卷積碼有很好的性能，能用於衛星通信和深空通信。
保密編碼
為了防止竊譯而進行的再編碼稱為保密編碼。其目的是為了隱藏敏感的信息。它常採用替換或亂置或兩者兼有的方法。一個密碼體制通常包括兩個基本部分：加（解）密算法和可以更換的控制算法的密鑰。密碼根據它的結構分為序列密碼和分組密碼兩類。序列密碼是算法在密鑰控制下產生的一種隨機序列，並逐位與明文混合而得到密文。其主要優點是不存在誤碼擴散，但對同步有較高的要求。它廣泛用於通信系統中。分組密碼是算法在密鑰控制下對明文按組加密。這樣產生的密文位一般與相應的明文組和密鑰中的位有相互依賴性，因而能引起誤碼擴散。它多用於訊息的確認和數字簽名中。
密碼學還研究通過破譯來截獲密文的方法。破譯方法有確定性分析法和統計性分析法兩類。確定性分析法是利用一個或幾個未知量來表示所期望的未知量從而破譯密文。統計分析法是利用存在於明文與密文或密鑰之間的統計關係破譯密文。
參考書目
張宏基編著：《信源編碼》，人民郵電出版社，北京，1980。
漢明著，朱雪龍譯：《編碼和信息理論》，科學出版社,北京,1984。(R.W.Hamming,Codin and InfomationTheory,PrenticeHall,1980.
饒世麟 楊述明 王耀勛
