[拼音]：bianma lilun

[外文]：coding theory

研究信息傳輸過程中信號編碼規(guī)律的數(shù)學(xué)理論。編碼理論與信息論、數(shù)理統(tǒng)計(jì)、概率論、隨機(jī)過程、線性代數(shù)、近世代數(shù)、數(shù)論、有限幾何和組合分析等學(xué)科有密切關(guān)系，已成為應(yīng)用數(shù)學(xué)的一個(gè)分支。編碼是指為了達(dá)到某種目的而對信號進(jìn)行的一種變換。其逆變換稱為譯碼或解碼。根據(jù)編碼的目的不同，編碼理論有三個(gè)分支：

（1）信源編碼。對信源輸出的信號進(jìn)行變換，包括連續(xù)信號的離散化，即將模擬信號通過采樣和量化變成數(shù)字信號,以及對數(shù)據(jù)進(jìn)行壓縮,提高數(shù)字信號傳輸?shù)挠行远M(jìn)行的編碼。

（2）信道編碼。對信源編碼器輸出的信號進(jìn)行再變換，包括區(qū)分通路、適應(yīng)信道條件和提高通信可靠性而進(jìn)行的編碼。

（3）保密編碼。對信道編碼器輸出的信號進(jìn)行再變換，即為了使信息在傳輸過程中不易被人竊取而進(jìn)行的編碼。編碼理論在數(shù)字化遙測遙控系統(tǒng)、電氣通信、數(shù)字通信、圖像通信、衛(wèi)星通信、深空通信、計(jì)算技術(shù)、數(shù)據(jù)處理、圖像處理、自動(dòng)控制、人工智能和模式識別等方面都有廣泛的應(yīng)用。

歷史背景

1843年美國著名畫家S.F.B.莫爾斯精心設(shè)計(jì)出莫爾斯碼，廣泛應(yīng)用在電報(bào)通信中。莫爾斯碼使用三種不同的符號：點(diǎn)、劃和間隔，可看做是順序三進(jìn)制碼。根據(jù)編碼理論可以證明，莫爾斯碼與理論上可達(dá)到的極限只差15％。但是直到20世紀(jì)30～40年代才開始形成編碼理論。1928年美國電信工程師H.奈奎斯特提出著名的采樣定理，為連續(xù)信號離散化奠定了基礎(chǔ)。1948年美國應(yīng)用數(shù)學(xué)家C.E.香農(nóng)在《通信中的數(shù)學(xué)理論》一文中提出信息熵的概念，為信源編碼奠定了理論基礎(chǔ)。1949年香農(nóng)在《有噪聲時(shí)的通信》一文中提出了信道容量的概念和信道編碼定理，為信道編碼奠定了理論基礎(chǔ)。無噪信道編碼定理（又稱香農(nóng)第一定理）指出，碼字的平均長度只能大于或等于信源的熵。有噪信道編碼定理（又稱香農(nóng)第二定理）則是編碼存在定理。它指出只要信息傳輸速率小于信道容量，就存在一類編碼，使信息傳輸?shù)腻e(cuò)誤概率可以任意小。隨著計(jì)算技術(shù)和數(shù)字通信的發(fā)展，糾錯(cuò)編碼和密碼學(xué)得到迅速的發(fā)展。

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

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

在密碼學(xué)方面，1949年香農(nóng)發(fā)表《保密系統(tǒng)的通信理論》，通常它被認(rèn)為是密碼學(xué)的先驅(qū)性著作。1976年狄菲和赫爾曼首次提出公開密鑰體制，為密碼學(xué)的研究開辟了新的方向。超大規(guī)模集成電路和高速計(jì)算機(jī)的應(yīng)用,促進(jìn)了保密編碼理論的發(fā)展,同時(shí)也給保密通信的安全性帶來很大的威脅。70年代以來把計(jì)算機(jī)復(fù)雜性理論引入密碼學(xué),出現(xiàn)了所謂P類、NP類和NP完全類問題。算法的復(fù)雜性函數(shù)呈指數(shù)型增長，因此密鑰空間擴(kuò)大，使密碼的分析和搜索面臨嚴(yán)重的挑戰(zhàn)。密碼學(xué)開始向縱深方向發(fā)展。

信源編碼

廣義的信源編碼包括模數(shù)轉(zhuǎn)換（即把模擬量變換成二進(jìn)制的數(shù)字量）和數(shù)據(jù)壓縮（即對這些數(shù)字量進(jìn)行編碼來降低數(shù)碼率）兩個(gè)方面。信源編碼的主要任務(wù)是壓縮數(shù)據(jù)。它有四種基本方法：

（1）匹配編碼。這種方法是根據(jù)編碼對象的出現(xiàn)概率（概率分布），分別給予不同長短的代碼，出現(xiàn)概率越大，所給代碼長度越短。這里所謂匹配就是指代碼長度與概率分布相匹配。莫爾斯碼是一種匹配編碼。匹配編碼還常采用去相關(guān)性的方法進(jìn)一步壓縮數(shù)據(jù)。

（2）變換編碼。這種方法是先對信號進(jìn)行變換，從一種信號空間變換成另一種信號空間，然后針對變換后的信號進(jìn)行編碼。變換編碼在話音和圖像編碼中有廣泛的應(yīng)用。目前常用的變換編碼有預(yù)測編碼和函數(shù)編碼兩類。預(yù)測編碼是根據(jù)信號的一些已知情況來預(yù)測信號即將發(fā)生的變化。它不傳送信號的采樣值，而傳送信號的采樣值與預(yù)測值之差。預(yù)測編碼用在數(shù)字電話和數(shù)字電視中。函數(shù)變換最常用的是快速傅里葉變換 (FFT)、余弦變換、沃爾什變換、哈爾變換和阿達(dá)馬變換等。通過變換可得到信號的頻譜特性，因而可根據(jù)頻譜特點(diǎn)來壓縮數(shù)碼。

（3）矢量編碼。這種方法是將可能傳輸?shù)南⒎诸惏吹刂反鎯υ诮邮斩说碾娮佑?jì)算機(jī)數(shù)據(jù)庫中，發(fā)送端只發(fā)送數(shù)據(jù)庫的地址，即可查出消息的內(nèi)容，從而大大壓縮發(fā)送的數(shù)據(jù)。

（4）識別編碼。這種方法主要用于有標(biāo)準(zhǔn)形狀的文字、符號和數(shù)據(jù)的編碼。但話音也可以進(jìn)行識別編碼。識別編碼的作用不僅限于壓縮數(shù)據(jù)，它在模式識別中也有廣泛的應(yīng)用。常用的識別方法有關(guān)聯(lián)識別和邏輯識別等方法。識別編碼可大大壓縮數(shù)據(jù)。例如，用話音識別的方法傳輸話音，平均數(shù)碼率小于100比特／秒。而用Δ調(diào)制話音的方法傳輸話音,數(shù)碼率達(dá)38400比特／秒。兩者相差約400倍。但識別編碼在恢復(fù)時(shí)是根據(jù)一個(gè)代碼恢復(fù)一個(gè)標(biāo)準(zhǔn)聲音，只能用于不必知道發(fā)話人是誰的特殊電話和問答裝置。識別編碼用于文字傳輸時(shí)，恢復(fù)出來的都是印刷體符號，只能用于普通電報(bào)。

信道編碼

信道編碼的主要任務(wù)是為了區(qū)分通路和增加通信的可靠性。以區(qū)分通路為主要目的的編碼常采用正交碼。以增加通信可靠性為主要目的的編碼常采用糾錯(cuò)碼。正交碼也具有很強(qiáng)的抗干擾能力。在信道編碼中也采用檢錯(cuò)碼。

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

正交碼

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

檢錯(cuò)碼

有發(fā)現(xiàn)錯(cuò)誤能力的碼稱為檢錯(cuò)碼。常用的檢錯(cuò)碼有奇偶校驗(yàn)碼和等重碼。采用檢錯(cuò)碼的通信系統(tǒng)要有反饋通道，當(dāng)發(fā)現(xiàn)收到的信號有錯(cuò)誤時(shí)，通過反饋通道發(fā)出自動(dòng)請求重發(fā)(ARQ)的信號。

糾錯(cuò)碼

接收到錯(cuò)誤的碼字后能在譯碼時(shí)自動(dòng)糾正錯(cuò)誤的碼稱為糾錯(cuò)碼。糾錯(cuò)碼是一種重要的抗干擾碼，可增加通信的可靠性。糾錯(cuò)碼是利用碼字中有規(guī)律的冗余度，即利用冗余度使碼字的碼元之間產(chǎn)生有規(guī)律的相關(guān)性，或使碼字與碼字之間產(chǎn)生有規(guī)律的相關(guān)性。通常把信息元中的碼元數(shù)k與對應(yīng)碼字的碼元數(shù) n的比值R稱為編碼效率，即R=k/n，碼字的冗余度為1-R。

糾錯(cuò)碼有兩類：分組碼和卷積碼。分組碼常記作(n，k)碼，其中n是一個(gè)碼字的碼元數(shù)（即碼字長），k是信息碼元數(shù)，n–k是監(jiān)督碼元數(shù)。在一個(gè)碼字中,如果信息碼元安排在前k位，監(jiān)督碼元安排在后n–k位，這種碼稱為組織碼或系統(tǒng)碼。如果分組碼中任何兩個(gè) n比特的碼字進(jìn)行模2相加（即不進(jìn)位的普通二進(jìn)制加法，模2加法記號是?\）可得到另一個(gè)碼字，這種碼稱為群碼。任何一致監(jiān)督分組碼都是群碼。如果一個(gè)碼字經(jīng)過循環(huán)以后必然是另一個(gè)碼字，這種碼稱為循環(huán)碼。循環(huán)碼是群碼的一個(gè)重要子集。著名的BCH碼是一種循環(huán)群碼。能糾正突發(fā)錯(cuò)誤的費(fèi)爾碼是一種分組循環(huán)碼。漢明碼也是一種群碼。通常把兩個(gè)碼字之間不同碼元的數(shù)目稱為漢明距離。兩兩碼字之間漢明距離的最小值稱為最小漢明距離，它是漢明碼檢錯(cuò)糾錯(cuò)能力的重要測度。漢明碼要糾正E個(gè)錯(cuò)誤，它的最小漢明距離至少必須是2E+1；要發(fā)現(xiàn)最多E個(gè)錯(cuò)誤，其最小漢明距離應(yīng)為E+1。

如果特定的一致監(jiān)督關(guān)系不是在一個(gè)碼字中實(shí)現(xiàn)，而是在m個(gè)碼字中實(shí)現(xiàn),這種碼稱為卷積碼。卷積碼可用移位寄存器來實(shí)現(xiàn)，這種卷積編碼器的輸出可看作是輸入信息碼元序列與編碼器響應(yīng)函數(shù)的卷積。能糾正突發(fā)錯(cuò)誤的哈格伯爾格碼也是一種卷積碼。在平穩(wěn)高斯噪聲干擾的信道上采用序貫譯碼方法的卷積碼有很好的性能，能用于衛(wèi)星通信和深空通信。

保密編碼

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

密碼學(xué)還研究通過破譯來截獲密文的方法。破譯方法有確定性分析法和統(tǒng)計(jì)性分析法兩類。確定性分析法是利用一個(gè)或幾個(gè)未知量來表示所期望的未知量從而破譯密文。統(tǒng)計(jì)分析法是利用存在于明文與密文或密鑰之間的統(tǒng)計(jì)關(guān)系破譯密文。

參考書目

1. 張宏基編著：《信源編碼》，人民郵電出版社，北京，1980。
2. 漢明著，朱雪龍譯：《編碼和信息理論》，科學(xué)出版社,北京,1984。(R.W.Hamming, Coding and Infomation Theory，Prentice-Hall, 1980.)

建筑資質(zhì)代辦咨詢熱線：13198516101

標(biāo)簽：編碼理論

版權(quán)聲明：本文采用知識共享 署名4.0國際許可協(xié)議 [BY-NC-SA] 進(jìn)行授權(quán)

文章名稱：《編碼理論》

文章鏈接：http://www.kaputelugumatrimony.com/13814.html

該作品系作者結(jié)合建筑標(biāo)準(zhǔn)規(guī)范、政府官網(wǎng)及互聯(lián)網(wǎng)相關(guān)知識整合。如若侵權(quán)請通過投訴通道提交信息，我們將按照規(guī)定及時(shí)處理。