古詩詞大全網 - 成語故事 - 編碼理論的信源編碼

編碼理論的信源編碼

廣義的信源編碼包括模數轉換(即把模擬量變換成二進制的數字量)和數據壓縮(即對這些數字量進行編碼來降低數碼率)兩個方面。信源編碼的主要任務是壓縮數據。 它有四種基本方法:

①匹配編碼。這種方法是根據編碼對象的出現概率(概率分布),分別給予不同長短的代碼,出現概率越大,所給代碼長度越短。這裏所謂匹配就是指代碼長度與概率分布相匹配。莫爾斯碼是壹種匹配編碼。匹配編碼還常采用去相關性的方法進壹步壓縮數據。

②變換編碼。這種方法是先對信號進行變換,從壹種信號空間變換成另壹種信號空間,然後針對變換後的信號進行編碼。變換編碼在話音和圖像編碼中有廣泛的應用。常用的變換編碼有預測編碼和函數編碼兩類。預測編碼是根據信號的壹些已知情況來預測信號即將發生的變化。它不傳送信號的采樣值,而傳送信號的采樣值與預測值之差。預測編碼用在數字電話和數字電視中。函數變換最常用的是快速傅裏葉變換 (FFT)、余弦變換、沃爾什變換、哈爾變換和阿達馬變換等。通過變換可得到信號的頻譜特性,因而可根據頻譜特點來壓縮數碼。

③矢量編碼。這種方法是將可能傳輸的消息分類按地址存儲在接收端的電子計算機數據庫中,發送端只發送數據庫的地址,即可查出消息的內容,從而大大壓縮發送的數據。

④識別編碼。這種方法主要用於有標準形狀的文字、符號和數據的編碼。但話音也可以進行識別編碼。識別編碼的作用不僅限於壓縮數據,它在模式識別中也有廣泛的應用。 信道編碼的主要任務是為了區分通路和增加通信的可靠性。以區分通路為主要目的的編碼常采用正交碼。以增加通信可靠性為主要目的的編碼常采用糾錯碼。正交碼也具有很強的抗幹擾能力。在信道編碼中也采用檢錯碼。

信源編碼器輸出 位碼元壹組的碼。它們攜帶著信息,稱為信息元。這樣的信息元通過信道編碼器後,變換成 位碼元壹組的碼字。信息元和碼字是壹壹對應的。 接收到錯誤的碼字後能在譯碼時自動糾正錯誤的碼稱為糾錯碼。糾錯碼是壹種重要的抗幹擾碼,可增加通信的可靠性。糾錯碼是利用碼字中有規律的冗余度,即利用冗余度使碼字的碼元之間產生有規律的相關性,或使碼字與碼字之間產生有規律的相關性。通常把信息元中的碼元數與對應碼字的碼元數 的比值R稱為編碼效率,即R=/,碼字的冗余度為1-R。

糾錯碼有兩類:分組碼和卷積碼。

分組碼

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

卷積碼

如果特定的壹致監督關系不是在壹個碼字中實現,而是在個碼字中實現,這種碼稱為卷積碼。卷積碼可用移位寄存器來實現,這種卷積編碼器的輸出可看作是輸入信息碼元序列與編碼器響應函數的卷積。能糾正突發錯誤的哈格伯爾格碼也是壹種卷積碼。在平穩高斯噪聲幹擾的信道上采用序貫譯碼方法的卷積碼有很好的性能,能用於衛星通信和深空通信。 為了防止竊譯而進行的再編碼稱為保密編碼。其目的是為了隱藏敏感的信息。它常采用替換或亂置或兩者兼有的方法。壹個密碼體制通常包括兩個基本部分:加(解)密算法和可以更換的控制算法的密鑰。密碼根據它的結構分為序列密碼和分組密碼兩類。序列密碼是算法在密鑰控制下產生的壹種隨機序列,並逐位與明文混合而得到密文。其主要優點是不存在誤碼擴散,但對同步有較高的要求。它廣泛用於通信系統中。分組密碼是算法在密鑰控制下對明文按組加密。這樣產生的密文位壹般與相應的明文組和密鑰中的位有相互依賴性,因而能引起誤碼擴散。它多用於消息的確認和數字簽名中。

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