編碼理論

詞語解釋

編碼理論是指在信息傳輸過程中，把信息以特定的方式編碼，以便在接收端能夠準(zhǔn)確的解碼，從而實(shí)現(xiàn)信息傳輸?shù)囊环N理論。編碼理論是通信技術(shù)中的一個(gè)重要組成部分，它是用來保證信息傳輸?shù)恼_性和完整性的一種技術(shù)。編碼理論的應(yīng)用是把信息按照特定的編碼方式編碼，以便在接收端能夠準(zhǔn)確的解碼，從而實(shí)現(xiàn)信息傳輸。在編碼過程中，可以采用編碼、調(diào)制、解碼等多種方式來實(shí)現(xiàn)信息傳輸。編碼理論的應(yīng)用可以把信息編碼成不同的形式，以便在接收端能夠準(zhǔn)確的解碼，從而實(shí)現(xiàn)信息傳輸。編碼理論的應(yīng)用可以實(shí)現(xiàn)信息的有效傳輸，這樣就可以提高信息傳輸?shù)男�。編碼理論的應(yīng)用還可以實(shí)現(xiàn)信息的加密，以便保護(hù)信息的安全性。此外，編碼理論的應(yīng)用還可以實(shí)現(xiàn)信息的壓縮，以減少信息傳輸?shù)臅r(shí)間和空間。總之，編碼理論是通信技術(shù)中的一個(gè)重要組成部分，它是用來保證信息傳輸?shù)恼_性和完整性的一種技術(shù)。它的應(yīng)用可以實(shí)現(xiàn)信息的有效傳輸、加密、壓縮等，從而提高信息傳輸?shù)男�，保護(hù)信息的安全性，減少信息傳輸?shù)臅r(shí)間和空間。

　　編碼理論是數(shù)學(xué)和計(jì)算機(jī)科學(xué)的一個(gè)分支，處理在噪聲信道傳送資料時(shí)的錯(cuò)誤傾向。按照編碼理論，資料傳送時(shí)會(huì)采用更好的方法以修正傳送途中所產(chǎn)生的大量錯(cuò)誤。
　　編碼共分兩類：
　　★信源編碼(數(shù)據(jù)壓縮[也叫：數(shù)據(jù)壓縮])
　　★信道編碼(前向糾錯(cuò))
　　bianma lilun
　　編碼理論
　　coding theory
　　研究信息傳輸過程中信號(hào)編碼規(guī)律的數(shù)學(xué)理論。編碼理論與信息論、數(shù)理統(tǒng)計(jì)、概率論、隨機(jī)過程、線性代數(shù)、近世代數(shù)、數(shù)論、有限幾何和組合分析等學(xué)科有密切關(guān)系，已成為應(yīng)用數(shù)學(xué)的一個(gè)分支。編碼是指為了達(dá)到某種目的而對(duì)信號(hào)進(jìn)行的一種變換。其逆變換稱為譯碼或解碼。根據(jù)編碼的目的不同，編碼理論有三個(gè)分支：①信源編碼。對(duì)信源輸出的信號(hào)進(jìn)行變換，包括連續(xù)信號(hào)的離散化，即將模擬信號(hào)通過采樣和量化變成數(shù)字信號(hào),以及對(duì)數(shù)據(jù)進(jìn)行壓縮,提高數(shù)字信號(hào)傳輸?shù)挠行远M(jìn)行的編碼。②信道編碼。對(duì)信源編碼器輸出的信號(hào)進(jìn)行再變換，包括區(qū)分通路、適應(yīng)信道條件和提高通信可靠性而進(jìn)行的編碼。③保密編碼。對(duì)信道編碼器輸出的信號(hào)進(jìn)行再變換，即為了使信息在傳輸過程中不易被人竊取而進(jìn)行的編碼。編碼理論在數(shù)字化遙測遙控系統(tǒng)、電氣通信、數(shù)字通信、圖像通信、衛(wèi)星通信、深空通信、計(jì)算技術(shù)、數(shù)據(jù)處理、圖像處理、自動(dòng)控制、人工智能和模式識(shí)別等方面都有廣泛的應(yīng)用。
　　歷史背景 1843年美國著名畫家S.F.B.莫爾斯精心設(shè)計(jì)出莫爾斯碼，廣泛應(yīng)用在電報(bào)通信中。莫爾斯碼使用三種不同的符號(hào)：點(diǎn)、劃和間隔，可看作是順序三進(jìn)制碼。根據(jù)編碼理論可以證明，莫爾斯碼與理論上可達(dá)到的極限只差15％。但是直到20世紀(jì)30～40年代才開始形成編碼理論。1928年美國電信工程師H.奈奎斯特提出著名的采樣定理，為連續(xù)信號(hào)離散化奠定了基礎(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)了傳真編碼、圖像編碼和話音編碼，對(duì)數(shù)據(jù)壓縮進(jìn)行了深入的研究，解決了數(shù)字通信中提出的許多實(shí)際問題。
　　在糾錯(cuò)編碼方面,1948年香農(nóng)就提出一位糾錯(cuò)碼(碼字長=7,信息碼元數(shù)=4)。1949年出現(xiàn)三位糾錯(cuò)的格雷碼(碼字長=23，信息碼元數(shù)=12)。1950年美國數(shù)學(xué)家R.W.漢明發(fā)表論文《檢錯(cuò)碼和糾錯(cuò)碼》，提出著名的漢明碼，對(duì)糾錯(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ù)量級(jí)。它已在衛(wèi)星通信中得到了廣泛的應(yīng)用。RS碼和卷積碼結(jié)合而構(gòu)造的級(jí)連碼，可用于深空通信。
　　在密碼學(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ù)壓縮（即對(duì)這些數(shù)字量進(jìn)行編碼來降低數(shù)碼率）兩個(gè)方面。信源編碼的主要任務(wù)是壓縮數(shù)據(jù)。它有四種基本方法：①匹配編碼。這種方法是根據(jù)編碼對(duì)象的出現(xiàn)概率（概率分布），分別給予不同長短的代碼，出現(xiàn)概率越大，所給代碼長度越短。這里所謂匹配就是指代碼長度與概率分布相匹配。莫爾斯碼是一種匹配編碼。匹配編碼還常采用去相關(guān)性的方法進(jìn)一步壓縮數(shù)據(jù)。②變換編碼。這種方法是先對(duì)信號(hào)進(jìn)行變換，從一種信號(hào)空間變換成另一種信號(hào)空間，然后針對(duì)變換后的信號(hào)進(jìn)行編碼。變換編碼在話音和圖像編碼中有廣泛的應(yīng)用。目前常用的變換編碼有預(yù)測編碼和函數(shù)編碼兩類。預(yù)測編碼是根據(jù)信號(hào)的一些已知情況來預(yù)測信號(hào)即將發(fā)生的變化。它不傳送信號(hào)的采樣值，而傳送信號(hào)的采樣值與預(yù)測值之差。預(yù)測編碼用在數(shù)字電話和數(shù)字電視中。函數(shù)變換最常用的是快速傅里葉變換 (FFT)、余弦變換、沃爾什變換、哈爾變換和阿達(dá)馬變換等。通過變換可得到信號(hào)的頻譜特性，因而可根據(jù)頻譜特點(diǎn)來壓縮數(shù)碼。③矢量編碼。這種方法是將可能傳輸?shù)南⒎诸惏吹刂反鎯?chǔ)在接收端的電子計(jì)算機(jī)數(shù)據(jù)庫中，發(fā)送端只發(fā)送數(shù)據(jù)庫的地址，即可查出消息的內(nèi)容，從而大大壓縮發(fā)送的數(shù)據(jù)。④識(shí)別編碼。這種方法主要用于有標(biāo)準(zhǔn)形狀的文字、符號(hào)和數(shù)據(jù)的編碼。但話音也可以進(jìn)行識(shí)別編碼。識(shí)別編碼的作用不僅限于壓縮數(shù)據(jù)，它在模式識(shí)別中也有廣泛的應(yīng)用。常用的識(shí)別方法有關(guān)聯(lián)識(shí)別和邏輯識(shí)別等方法。識(shí)別編碼可大大壓縮數(shù)據(jù)。例如，用話音識(shí)別的方法傳輸話音，平均數(shù)碼率小于100比特／秒。而用Δ調(diào)制話音的方法傳輸話音,數(shù)碼率達(dá)38400比特／秒。兩者相差約400倍。但識(shí)別編碼在恢復(fù)時(shí)是根據(jù)一個(gè)代碼恢復(fù)一個(gè)標(biāo)準(zhǔn)聲音，只能用于不必知道發(fā)話人是誰的特殊電話和問答裝置。識(shí)別編碼用于文字傳輸時(shí)，恢復(fù)出來的都是印刷體符號(hào)，只能用于普通電報(bào)。
　　信道編碼信道編碼的主要任務(wù)是為了區(qū)分通路和增加通信的可靠性。以區(qū)分通路為主要目的的編碼常采用正交碼。以增加通信可靠性為主要目的的編碼常采用糾錯(cuò)碼。正交碼也具有很強(qiáng)的抗干擾能力。在信道編碼中也采用檢錯(cuò)碼。
　　信源編碼器輸出位碼元一組的碼。它們攜帶著信息，稱為信息元。這樣的信息元通過信道編碼器后，變換成位碼元一組的碼字。信息元和碼字是一一對(duì)應(yīng)的。
　　正交碼碼字與碼字之間互相關(guān)系數(shù)為 0的碼稱為正交碼，在信道編碼時(shí)主要利用它的正交性去區(qū)分通路，但它本身也可以攜帶信息。最常用的正交碼有偽隨機(jī)碼(如 m序列、L序列、巴克序列、M序列等)和沃爾什函數(shù)序列。若一個(gè)正交信號(hào)集的補(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)收到的信號(hào)有錯(cuò)誤時(shí)，通過反饋通道發(fā)出自動(dòng)請(qǐng)求重發(fā)(ARQ)的信號(hào)。
　　糾錯(cuò)碼接收到錯(cuò)誤的碼字后能在譯碼時(shí)自動(dòng)糾正錯(cuò)誤的碼稱為糾錯(cuò)碼。糾錯(cuò)碼是一種重要的抗干擾碼，可增加通信的可靠性。糾錯(cuò)碼是利用碼字中有規(guī)律的冗余度，即利用冗余度使碼字的碼元之間產(chǎn)生有規(guī)律的相關(guān)性，或使碼字與碼字之間產(chǎn)生有規(guī)律的相關(guān)性。通常把信息元中的碼元數(shù)與對(duì)應(yīng)碼字的碼元數(shù) 的比值R稱為編碼效率，即R=/，碼字的冗余度為1-R。
　　糾錯(cuò)碼有兩類：分組碼和卷積碼。分組碼常記作(,)碼，其中是一個(gè)碼字的碼元數(shù)（即碼字長），是信息碼元數(shù)，-是監(jiān)督碼元數(shù)。在一個(gè)碼字中,如果信息碼元安排在前位，監(jiān)督碼元安排在后-位，這種碼稱為組織碼或系統(tǒng)碼。如果分組碼中任何兩個(gè) 比特的碼字進(jìn)行模2相加（即不進(jìn)位的普通二進(jìn)制加法，模2加法記號(hào)是）可得到另一個(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)，而是在個(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ò)散，但對(duì)同步有較高的要求。它廣泛用于通信系統(tǒng)中。分組密碼是算法在密鑰控制下對(duì)明文按組加密。這樣產(chǎn)生的密文位一般與相應(yīng)的明文組和密鑰中的位有相互依賴性，因而能引起誤碼擴(kuò)散。它多用于消息的確認(rèn)和數(shù)字簽名中。
　　密碼學(xué)還研究通過破譯來截獲密文的方法。破譯方法有確定性分析法和統(tǒng)計(jì)性分析法兩類。確定性分析法是利用一個(gè)或幾個(gè)未知量來表示所期望的未知量從而破譯密文。統(tǒng)計(jì)分析法是利用存在于明文與密文或密鑰之間的統(tǒng)計(jì)關(guān)系破譯密文。
　　參考書目
　　張宏基編著：《信源編碼》，人民郵電出版社，北京，1980。
　　漢明著，朱雪龍譯：《編碼和信息理論》，科學(xué)出版社,北京,1984。(R.W.Hamming,Codin and InfomationTheory,PrenticeHall,1980.
　　饒世麟　楊述明　王耀勛

掃碼付費(fèi)即可復(fù)制

編碼理論

編碼理論

相關(guān)資料下載

隨機(jī)推薦詞語