現(xiàn)代編碼

2024年2月15日發(fā)(作者：2月14日是什么情人節(jié))

隨著現(xiàn)代信息技術(shù)的不斷發(fā)展，對原始通過應(yīng)用密碼學(xué)、概率論、信息熵、通信系統(tǒng)、隨機過程等方法的信息論科目提出了進(jìn)一步的發(fā)展要求。而編碼技術(shù)研究的主要內(nèi)容是如何既可靠又有效地傳輸信息。從1948年香農(nóng)在《貝爾系統(tǒng)技術(shù)雜志》上發(fā)表了《通信的數(shù)學(xué)理論》開始。次年，他又發(fā)表了另一篇著作《噪聲下的通信》。人們認(rèn)為這兩篇文章成了現(xiàn)在信息論的奠基著作。1959年香農(nóng)發(fā)表了“保真度準(zhǔn)則下的離散信源編碼定理”，首先提出了率失真函數(shù)及率失真信源編碼定理，此后發(fā)展成為信息率失真編碼理論?，F(xiàn)在，信息理論廣泛應(yīng)用在通信、計算機等領(lǐng)域，隨著通信安全與質(zhì)量的高要求化，編碼技術(shù)也在不斷地突飛猛進(jìn)。

編碼技術(shù)的分類：信源編碼、信道編碼

信源編碼：

概念：信源編碼是一種以提高通信有效性為目的而對信源符號進(jìn)行有目標(biāo)的變換。具體說，就是針對信源的輸出符號序列統(tǒng)計特性來尋找某種方法，把信源輸出符號序列變換為最短的碼字序列，使后者的各碼元所載荷的平均信息量最大，同時又能保證無失真地恢復(fù)原來的符號序列。

作用：信源編碼的作用之一是，即通常所說的數(shù)據(jù)壓縮；作用之二是將信源的模擬信號轉(zhuǎn)化成數(shù)字信號，以實現(xiàn)模擬信號的數(shù)字化傳輸。

發(fā)展：最原始的信源編碼就是莫爾斯電碼，另外還有ASCII碼和電報碼都是信源編碼。但現(xiàn)代通信應(yīng)用中常見的信源編碼方式有：Huffman編碼、算術(shù)編碼、L-Z編碼，這三種都是無損編碼，另外還有一些有損的編碼方式。信源編碼的目標(biāo)就是使信源減少冗余，更加有效、經(jīng)濟(jì)地傳輸，最常見的應(yīng)用形式就是壓縮。另外，在數(shù)字電視領(lǐng)域，信源編碼包括 通用的MPEG—2編碼和H.264（MPEG—Part10 AVC）編碼等。相應(yīng)地，信道編碼是為了對抗信道中的噪音和衰減，通過增加冗余，如校驗碼等，來提高抗干擾能力以及糾錯能力。

分類：信源編碼根據(jù)信源的性質(zhì)進(jìn)行分類，則有信源統(tǒng)計特性已知或未知、無失真或限定失

真、無記憶或有記憶信源的編碼；按編碼方法進(jìn)行分類可分為分組碼或非分組碼、等長碼或變長碼等。然而最常見的是討論統(tǒng)計特性已知條件下，離散、平穩(wěn)、無失真信源的編碼，消除這類信源剩余度的主要方法有統(tǒng)計匹配編碼和解除相關(guān)性編碼。比如仙農(nóng)碼、費諾碼、赫夫曼碼，它們屬于不等長度分組碼，算術(shù)編碼屬于非分組碼；預(yù)測編碼和變換編碼是以解除相關(guān)性為主的編碼。對限定失真的信源編碼則是以信息率失真R（D）函數(shù)為基礎(chǔ)，最典型的是矢量量化編碼。對統(tǒng)計特性未知的信源編碼稱為通用編碼。

信道編碼：

概念：由于移動通信存在干擾和衰落，在信號傳輸過程中將出現(xiàn)差錯，故對數(shù)字信號必須采用糾、檢錯技術(shù)，即糾、檢錯編碼技術(shù)，以增強數(shù)據(jù)在信道中傳輸時抵御各種干擾的能力，提高系統(tǒng)的可靠性。對要在信道中傳送的數(shù)字信號進(jìn)行的糾、檢錯編碼就是信道編碼。

通常糾錯碼分為兩大類，即分組碼和卷積碼。在移動通信系統(tǒng)中另一種糾錯方法就是信令重發(fā)，解碼時先存儲再逐位判決，如重發(fā)五次，三次或三次以上均為1，則判1。

信道編碼之所以能夠檢出和校正接收比特流中的差錯，是因為加入一些冗余比特，把幾個比特上攜帶的信息擴(kuò)散到更多的比特上。為此付出的代價是必須傳送比該信息所需要的更多的比特。

發(fā)展：編碼定理的證明，從離散信道發(fā)展到連續(xù)信道，從無記憶信道到有記憶信道，從單用戶信道到多用戶信道，從證明差錯概率可接近于零到以指數(shù)規(guī)律逼近于零，正在不斷完善。編碼方法，在離散信道中一般用代數(shù)碼形式，其類型有較大發(fā)展，各種界限也不斷有人提出，但尚未達(dá)到編碼定理所啟示的限度，尤其是關(guān)于多用戶信道，更顯得不足。在連續(xù)信道中常采用正交函數(shù)系來代表消息，這在極限情況下可達(dá)到編碼定理的限度。不是所有信道的編碼定理都已被證明。只有無記憶單用戶信道和多用戶信道中的特殊情況的編碼定理已有嚴(yán)格的證明；其他信道也有一些結(jié)果，但尚不完善。

作用：數(shù)字信號在傳輸中往往由于各種原因，使得在傳送的數(shù)據(jù)流中產(chǎn)生誤碼，從而使接收端產(chǎn)生圖象跳躍、不連續(xù)、出現(xiàn)馬賽克等現(xiàn)象。所以通過信道編碼這一環(huán)節(jié)，對數(shù)碼流進(jìn)行相應(yīng)的處理，使系統(tǒng)具有一定的糾錯能力和抗干擾能力，可極大地避免碼流傳送中誤碼的發(fā)生。誤碼的處理技術(shù)有糾錯、交織、線性內(nèi)插等。提高數(shù)據(jù)傳輸效率，降低誤碼率是信道編碼的任務(wù)。信道編碼的本質(zhì)是增加通信的可靠性。但信道編碼會使有用的信息數(shù)據(jù)傳輸減少，信道編碼的過程是在源數(shù)據(jù)碼流中加插一些碼元，從而達(dá)到在接收端進(jìn)行判錯和糾錯的目的，這就是我們常常說的開銷。這就好象我們運送一批玻璃杯一樣，為了保證運送途中不出現(xiàn)打爛玻璃杯的情況，我們通常都用一些泡沫或海棉等物將玻璃杯包裝起來，這種包裝使玻璃杯所占的容積變大，原來一部車能裝5000個玻璃杯的，包裝后就只能裝4000個了，顯然包裝的代價使運送玻璃杯的有效個數(shù)減少了。同樣，在帶寬固定的信道中，總的傳送碼率也是固定的，由于信道編碼增加了數(shù)據(jù)量，其結(jié)果只能是以降低傳送有用信息碼率為代價了。將有用比特數(shù)除以總比特數(shù)就等于編碼效率了，不同的編碼方式，其編碼效率有所不同。

分類：

1、RS編碼

RS碼即里德-所羅門碼，它是能夠糾正多個錯誤的糾錯碼，RS碼為（204，188，t=8），其中t是可抗長度字節(jié)數(shù)，對應(yīng)的188符號，監(jiān)督段為16字節(jié)(開銷字節(jié)段）。實際中實施（255，239，t=8）的RS編碼，即在204字節(jié)（包括同步字節(jié)）前添加51個全“0”字節(jié)，產(chǎn)生RS碼后丟棄前面51個空字節(jié)，形成截短的（204，188）RS碼。RS的編碼效率是：188/204。

2、卷積碼

卷積碼非常適用于糾正隨機錯誤，但是，解碼算法本身的特性卻是：如果在解碼過程中發(fā)生錯誤，解碼器可能會導(dǎo)致突發(fā)性錯誤。為此在卷積碼的上部采用RS碼塊，RS碼適用于檢測和校正那些由解碼器產(chǎn)生的突發(fā)性錯誤。所以卷積碼和RS碼結(jié)合在一起可以起到相互補

償?shù)淖饔?。卷積碼分為兩種：

(1)基本卷積碼:

基本卷積碼編碼效率為，η=1/2,編碼效率較低,優(yōu)點是糾錯能力強。

(2)收縮卷積碼

如果傳輸信道質(zhì)量較好，為提高編碼效率，可以采樣收縮截短卷積碼。有編碼效率為：η=1/2、2/3、3/4、5/6、7/8這幾種編碼效率的收縮卷積碼。編碼效率高，一定帶寬內(nèi)可傳輸?shù)挠行П忍芈试龃?但糾錯能力越減弱。

3、Turbo碼

1993年誕生的Turbo碼，單片Turbo碼的編碼/解碼器，運行速率達(dá)40Mb/s。該芯片集成了一個32×32交織器，其性能和傳統(tǒng)的RS外碼和卷積內(nèi)碼的級聯(lián)一樣好。所以Turbo碼是一種先進(jìn)的信道編碼技術(shù)，由于其不需要進(jìn)行兩次編碼，所以其編碼效率比傳統(tǒng)的RS+卷積碼要好。

4、線性分組碼

當(dāng)分組碼的信息碼元與監(jiān)督碼元之間的關(guān)系為線性關(guān)系時（用線性方程組聯(lián)系），這種分組碼就稱為線性分組碼。包括漢明碼和循環(huán)碼。對于長度為n的二進(jìn)制線性分組碼，它有種可能的碼字，從中可以選擇M=個碼字（k

在線性分組碼中，兩個碼字對應(yīng)位上數(shù)字不同的位數(shù)稱為碼字距離，簡稱距離，又稱漢明距離。編碼中各個碼字間距離的最小值稱為最小碼距d，最小碼距是衡量碼組檢錯和糾錯能力的依據(jù)，其關(guān)系如下：

（1）為了檢測e個錯碼，則要求最小碼距d>e+1;

（2）為了糾正t個錯碼，則要求最小碼距d>2t+1;

（3）為了糾正t個錯碼，同時檢測e個錯碼，則要求最小碼距d>e+t+1,e>t。

線性分組碼是建立在代數(shù)群論基礎(chǔ)上的，各許用碼字的集合構(gòu)成了代數(shù)學(xué)中的群，它們的主要性質(zhì)如下：

（1）任意兩許用碼字之和（對于二進(jìn)制碼這個和的含義是模二和）仍為一個需要碼字，也就是說，線性分組碼具有封閉性；

（2）碼字間的最小碼距等于非零碼的最小碼重。

5、霍夫曼編碼

設(shè)某信源產(chǎn)生有五種符號u1、u2、u3、u4和u5，對應(yīng)概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。首先，將符號按照概率由大到小排隊，如圖所示。編碼時，從最小概率的兩個符號開始，可選其中一個支路為0，另一支路為1。這里，我們選上支路為0，下支路為1。再將已編碼的兩支路的概率合并，并重新排隊。多次重復(fù)使用上述方法直至合并概率歸一時為止。從圖（a）和（b）可以看出，兩者雖平均碼長相等，但同一符號可以有不同的碼長，即編碼方法并不唯一，其原因是兩支路概率合并后重新排隊時，可能出現(xiàn)幾個支路概率相等，造成排隊方法不唯一。一般，若將新合并后的支路排到等概率的最上支路，將有利于縮短碼長方差，且編出的碼更接近于等長碼。赫夫曼碼的碼字（各符號的代碼）是異前置碼字，即任一碼字不會是另一碼字的前面部分，這使各碼字可以連在一起傳送，中間不需另加隔離符號，只要傳送時不出錯，收端仍可分離各個碼字，不致混淆。實際應(yīng)用中，除采用定時清洗以消除誤差擴(kuò)散和采用緩沖存儲以解決速率匹配以外，主要問題是解決小符號集合的統(tǒng)計匹配，例如黑（1）、白（0）傳真信源的統(tǒng)計匹配，采用0和1不同長度游程組成擴(kuò)大的符號集合信源。游程，指相同碼元的長度（如二進(jìn)碼中連續(xù)的一串0或一串1的長度或個數(shù)）。

按照CCITT標(biāo)準(zhǔn)，需要統(tǒng)計2×1728種游程（長度），這樣，實現(xiàn)時的存儲量太大。事實上長游程的概率很小，故CCITT還規(guī)定：若l表示游程長度，則l=64q+r。其中q稱主碼，r為基碼。編碼時，不小于64的游程長度由主碼和基碼組成。而當(dāng)l為64的整數(shù)倍時，只用主碼的代碼，已不存在基碼的代碼。

6、游程碼

用一個符號值或串長代替具有相同值的連續(xù)符號（連續(xù)符號構(gòu)成了一段連續(xù)的“行程”。行程編碼因此而得名），使符號長度少于原始數(shù)據(jù)的長度。只在各行或者各列數(shù)據(jù)的代碼發(fā)生變化時，一次記錄該代碼及相同代碼重復(fù)的個數(shù)，從而實現(xiàn)數(shù)據(jù)的壓縮。行程編碼是連續(xù)精確的編碼，在傳輸過程中，如果其中一位符號發(fā)生錯誤，即可影響整個編碼序列，使行程編碼無法還原回原始數(shù)據(jù)。游程長度在柵格加密時，數(shù)據(jù)量沒有明顯增加，壓縮效率較高，且易于檢索、疊加合并等操作，運算簡單，適用于機器存儲容量小，數(shù)據(jù)需大量壓縮，而又要避免復(fù)雜的編碼和解碼運算，增加處理和操作時間的情況。

編碼理論的提出，一方面是為了提高信源的有效性；一方面為了提高信道的可靠性而提出的。針對于編碼理論的存在，如果在信源以及信道處應(yīng)用了相應(yīng)的編碼技術(shù)，那么在信宿端自然也就需要一個解碼系統(tǒng)，不然信宿是不能將原始信號無差錯的進(jìn)行解析，從而導(dǎo)致編碼理論的失敗。所以一個與編碼理論對應(yīng)的解碼理論也就顯得也是非常重要的。并且隨著相關(guān)研究的不斷深入，現(xiàn)在的編碼、譯碼技術(shù)已經(jīng)相對成熟。除此以外現(xiàn)在的解碼技術(shù)和編碼技術(shù)并不需要完全的對應(yīng)關(guān)系，可以根據(jù)系統(tǒng)對有效性以及可靠性的要求，靈活選取編碼和解碼技術(shù)，從而使得信息技術(shù)得以快速發(fā)展。