編碼理論

　　編碼理論是數(shù)學和計算機科學的一個分支，處理在噪聲信道傳送資料時的錯誤傾向。按照編碼理論，資料傳送時會采用更好的方法以修正傳送途中所產(chǎn)生的大量錯誤。
　　編碼共分兩類：
　　★信源編碼(數(shù)據(jù)壓縮[也叫：數(shù)據(jù)壓縮])
　　★信道編碼(前向糾錯)
　　bianma lilun
　　編碼理論
　　coding theory
　　研究信息傳輸過程中信號編碼規(guī)律的數(shù)學理論。編碼理論與信息論、數(shù)理統(tǒng)計、概率論、隨機過程、線性代數(shù)、近世代數(shù)、數(shù)論、有限幾何和組合分析等學科有密切關(guān)系，已成為應用數(shù)學的一個分支。編碼是指為了達到某種目的而對信號進行的一種變換。其逆變換稱為譯碼或解碼。根據(jù)編碼的目的不同，編碼理論有三個分支：①信源編碼。對信源輸出的信號進行變換，包括連續(xù)信號的離散化，即將模擬信號通過采樣和量化變成數(shù)字信號,以及對數(shù)據(jù)進行壓縮,提高數(shù)字信號傳輸?shù)挠行�性而進行的編碼。②信道編碼。對信源編碼器輸出的信號進行再變換，包括區(qū)分通路、適應信道條件和提高通信可靠性而進行的編碼。③保密編碼。對信道編碼器輸出的信號進行再變換，即為了使信息在傳輸過程中不易被人竊取而進行的編碼。編碼理論在數(shù)字化遙測遙控系統(tǒng)、電氣通信、數(shù)字通信、圖像通信、衛(wèi)星通信、深空通信、計算技術(shù)、數(shù)據(jù)處理、圖像處理、自動控制、人工智能和模式識別等方面都有廣泛的應用。
　　歷史背景 1843年美國著名畫家S.F.B.莫爾斯精心設計出莫爾斯碼，廣泛應用在電報通信中。莫爾斯碼使用三種不同的符號：點、劃和間隔，可看作是順序三進制碼。根據(jù)編碼理論可以證明，莫爾斯碼與理論上可達到的極限只差15％。但是直到20世紀30～40年代才開始形成編碼理論。1928年美國電信工程師H.奈奎斯特提出著名的采樣定理，為連續(xù)信號離散化奠定了基礎。1948年美國應用數(shù)學家C.E.香農(nóng)在《通信中的數(shù)學理論》一文中提出信息熵的概念，為信源編碼奠定了理論基礎。1949年香農(nóng)在《有噪聲時的通信》一文中提出了信道容量的概念和信道編碼定理，為信道編碼奠定了理論基礎。無噪信道編碼定理（又稱香農(nóng)第一定理）指出，碼字的平均長度只能大于或等于信源的熵。有噪信道編碼定理（又稱香農(nóng)第二定理）則是編碼存在定理。它指出只要信息傳輸速率小于信道容量，就存在一類編碼，使信息傳輸?shù)腻e誤概率可以任意小。隨著計算技術(shù)和數(shù)字通信的發(fā)展，糾錯編碼和密碼學得到迅速的發(fā)展。
　　在信源編碼方面，1951年香農(nóng)證明，當信源輸出有冗余的消息時可通過編碼改變信源的輸出，使信息傳輸速率接近信道容量。1948年香農(nóng)就提出能使信源與信道匹配的香農(nóng)編碼。1949年美國麻省理工學院的R.M.費諾提出費諾編碼。1951年美國電信工程師D.A.霍夫曼提出更有效的霍夫曼編碼。此后又出現(xiàn)了傳真編碼、圖像編碼和話音編碼，對數(shù)據(jù)壓縮進行了深入的研究，解決了數(shù)字通信中提出的許多實際問題。
　　在糾錯編碼方面,1948年香農(nóng)就提出一位糾錯碼(碼字長=7,信息碼元數(shù)=4)。1949年出現(xiàn)三位糾錯的格雷碼(碼字長=23，信息碼元數(shù)=12)。1950年美國數(shù)學家R.W.漢明發(fā)表論文《檢錯碼和糾錯碼》，提出著名的漢明碼，對糾錯編碼產(chǎn)生了重要的影響。1955年出現(xiàn)卷積碼。卷積碼至今仍有很廣泛的應用。1957年引入循環(huán)碼。循環(huán)碼構(gòu)造簡單,便于應用代數(shù)理論進行設計,也容易實現(xiàn)。1959年出現(xiàn)能糾正突發(fā)錯誤的哈格伯爾格碼和費爾碼。1959年美國的R.C.博斯和D.K.雷·喬達利與法國的A.奧昆岡幾乎同時獨立地發(fā)表一種著名的循環(huán)碼，后來稱為 BCH碼(即Bose-Chaudhuri-Hocquenghem碼)。1965年提出序貫譯碼序貫譯碼已用于空間通信1967年A.J.維特比提出最大似然卷積譯碼,稱為維特比譯碼1978年出現(xiàn)矢量編碼法。矢量編碼法是一種高效率的編碼技術(shù)。1980年用數(shù)論方法實現(xiàn)里德－所羅門碼（Reed-Solomon碼）,簡稱RS碼。它實際上是多進制的BCH碼。這種糾錯編碼技術(shù)能使編碼器集成電路的元件數(shù)減少一個數(shù)量級。它已在衛(wèi)星通信中得到了廣泛的應用。RS碼和卷積碼結(jié)合而構(gòu)造的級連碼，可用于深空通信。
　　在密碼學方面，1949年香農(nóng)發(fā)表《保密系統(tǒng)的通信理論》，通常它被認為是密碼學的先驅(qū)性著作。1976年狄菲和赫爾曼首次提出公開密鑰體制，為密碼學的研究開辟了新的方向。超大規(guī)模集成電路和高速計算機的應用,促進了保密編碼理論的發(fā)展,同時也給保密通信的安全性帶來很大的威脅。70年代以來把計算機復雜性理論引入密碼學,出現(xiàn)了所謂P類、NP類和NP完全類問題。算法的復雜性函數(shù)呈指數(shù)型增長，因此密鑰空間擴大，使密碼的分析和搜索面臨嚴重的挑戰(zhàn)。密碼學開始向縱深方向發(fā)展。
　　信源編碼 廣義的信源編碼包括模數(shù)轉(zhuǎn)換（即把模擬量變換成二進制的數(shù)字量）和數(shù)據(jù)壓縮（即對這些數(shù)字量進行編碼來降低數(shù)碼率）兩個方面。信源編碼的主要任務是壓縮數(shù)據(jù)。它有四種基本方法：①匹配編碼。這種方法是根據(jù)編碼對象的出現(xiàn)概率（概率分布），分別給予不同長短的代碼，出現(xiàn)概率越大，所給代碼長度越短。這里所謂匹配就是指代碼長度與概率分布相匹配。莫爾斯碼是一種匹配編碼。匹配編碼還常采用去相關(guān)性的方法進一步壓縮數(shù)據(jù)。②變換編碼。這種方法是先對信號進行變換，從一種信號空間變換成另一種信號空間，然后針對變換后的信號進行編碼。變換編碼在話音和圖像編碼中有廣泛的應用。目前常用的變換編碼有預測編碼和函數(shù)編碼兩類。預測編碼是根據(jù)信號的一些已知情況來預測信號即將發(fā)生的變化。它不傳送信號的采樣值，而傳送信號的采樣值與預測值之差。預測編碼用在數(shù)字電話和數(shù)字電視中。函數(shù)變換最常用的是快速傅里葉變換 (FFT)、余弦變換、沃爾什變換、哈爾變換和阿達馬變換等。通過變換可得到信號的頻譜特性，因而可根據(jù)頻譜特點來壓縮數(shù)碼。③矢量編碼。這種方法是將可能傳輸?shù)南�息分類按地址存儲在接收端的電子計算機數(shù)據(jù)庫中，發(fā)送端只發(fā)送數(shù)據(jù)庫的地址，即可查出消息的內(nèi)容，從而大大壓縮發(fā)送的數(shù)據(jù)。④識別編碼。這種方法主要用于有標準形狀的文字、符號和數(shù)據(jù)的編碼。但話音也可以進行識別編碼。識別編碼的作用不僅限于壓縮數(shù)據(jù)，它在模式識別中也有廣泛的應用。常用的識別方法有關(guān)聯(lián)識別和邏輯識別等方法。識別編碼可大大壓縮數(shù)據(jù)。例如，用話音識別的方法傳輸話音，平均數(shù)碼率小于100比特／秒。而用Δ調(diào)制話音的方法傳輸話音,數(shù)碼率達38400比特／秒。兩者相差約400倍。但識別編碼在恢復時是根據(jù)一個代碼恢復一個標準聲音，只能用于不必知道發(fā)話人是誰的特殊電話和問答裝置。識別編碼用于文字傳輸時，恢復出來的都是印刷體符號，只能用于普通電報。
　　信道編碼 信道編碼的主要任務是為了區(qū)分通路和增加通信的可靠性。以區(qū)分通路為主要目的的編碼常采用正交碼。以增加通信可靠性為主要目的的編碼常采用糾錯碼。正交碼也具有很強的抗干擾能力。在信道編碼中也采用檢錯碼。
　　信源編碼器輸出 位碼元一組的碼。它們攜帶著信息，稱為信息元。這樣的信息元通過信道編碼器后，變換成 位碼元一組的碼字。信息元和碼字是一一對應的。
　　正交碼 碼字與碼字之間互相關(guān)系數(shù)為 0的碼稱為正交碼，在信道編碼時主要利用它的正交性去區(qū)分通路，但它本身也可以攜帶信息。最常用的正交碼有偽隨機碼(如 m序列、L序列、巴克序列、M序列等)和沃爾什函數(shù)序列。若一個正交信號集的補集也被利用，則可用碼組數(shù)將增加一倍,這樣的正交碼稱為雙正交碼。里德-米勒碼 （Reed-Muller碼）就是一種雙正交碼。正交碼廣泛用于通信、雷達、導航、遙控、遙測和保密通信等領域。
　　檢錯碼 有發(fā)現(xiàn)錯誤能力的碼稱為檢錯碼。常用的檢錯碼有奇偶校驗碼和等重碼。采用檢錯碼的通信系統(tǒng)要有反饋通道，當發(fā)現(xiàn)收到的信號有錯誤時，通過反饋通道發(fā)出自動請求重發(fā)(ARQ)的信號。
　　糾錯碼 接收到錯誤的碼字后能在譯碼時自動糾正錯誤的碼稱為糾錯碼。糾錯碼是一種重要的抗干擾碼，可增加通信的可靠性。糾錯碼是利用碼字中有規(guī)律的冗余度，即利用冗余度使碼字的碼元之間產(chǎn)生有規(guī)律的相關(guān)性，或使碼字與碼字之間產(chǎn)生有規(guī)律的相關(guān)性。通常把信息元中的碼元數(shù)與對應碼字的碼元數(shù) 的比值R稱為編碼效率，即R=/，碼字的冗余度為1-R。
　　糾錯碼有兩類：分組碼和卷積碼。分組碼常記作(,)碼，其中是一個碼字的碼元數(shù)（即碼字長），是信息碼元數(shù)，-是監(jiān)督碼元數(shù)。在一個碼字中,如果信息碼元安排在前位，監(jiān)督碼元安排在后-位，這種碼稱為組織碼或系統(tǒng)碼。如果分組碼中任何兩個 比特的碼字進行模2相加（即不進位的普通二進制加法，模2加法記號是）可得到另一個碼字，這種碼稱為群碼。任何一致監(jiān)督分組碼都是群碼。如果一個碼字經(jīng)過循環(huán)以后必然是另一個碼字，這種碼稱為循環(huán)碼。循環(huán)碼是群碼的一個重要子集著名的BCH碼是一種循環(huán)群碼。能糾正突發(fā)錯誤的費爾碼是一種分組循環(huán)碼。漢明碼也是一種群碼。通常把兩個碼字之間不同碼元的數(shù)目稱為漢明距離。兩兩碼字之間漢明距離的最小值稱為最小漢明距離，它是漢明碼檢錯糾錯能力的重要測度漢明碼要糾正E個錯誤，它的最小漢明距離至少必須是2E+1；要發(fā)現(xiàn)最多E個錯誤，其最小漢明距離應為E+1。
　　如果特定的一致監(jiān)督關(guān)系不是在一個碼字中實現(xiàn)，而是在個碼字中實現(xiàn),這種碼稱為卷積碼。卷積碼可用移位寄存器來實現(xiàn)，這種卷積編碼器的輸出可看作是輸入信息碼元序列與編碼器響應函數(shù)的卷積。能糾正突發(fā)錯誤的哈格伯爾格碼也是一種卷積碼。在平穩(wěn)高斯噪聲干擾的信道上采用序貫譯碼方法的卷積碼有很好的性能，能用于衛(wèi)星通信和深空通信。
　　保密編碼 為了防止竊譯而進行的再編碼稱為保密編碼。其目的是為了隱藏敏感的信息。它常采用替換或亂置或兩者兼有的方法。一個密碼體制通常包括兩個基本部分：加（解）密算法和可以更換的控制算法的密鑰。密碼根據(jù)它的結(jié)構(gòu)分為序列密碼和分組密碼兩類。序列密碼是算法在密鑰控制下產(chǎn)生的一種隨機序列，并逐位與明文混合而得到密文。其主要優(yōu)點是不存在誤碼擴散，但對同步有較高的要求。它廣泛用于通信系統(tǒng)中。分組密碼是算法在密鑰控制下對明文按組加密。這樣產(chǎn)生的密文位一般與相應的明文組和密鑰中的位有相互依賴性，因而能引起誤碼擴散。它多用于消息的確認和數(shù)字簽名中。
　　密碼學還研究通過破譯來截獲密文的方法。破譯方法有確定性分析法和統(tǒng)計性分析法兩類。確定性分析法是利用一個或幾個未知量來表示所期望的未知量從而破譯密文。統(tǒng)計分析法是利用存在于明文與密文或密鑰之間的統(tǒng)計關(guān)系破譯密文。
　　參考書目
　　張宏基編著：《信源編碼》，人民郵電出版社，北京，1980。
　　漢明著，朱雪龍譯：《編碼和信息理論》，科學出版社,北京,1984。(R.W.Hamming,Codin and InfomationTheory,PrenticeHall,1980.
　　饒世麟　楊述明　王耀勛

• 通信詞典解釋