第4章 無失真信源編碼A

第4章無失真信源編碼

通信的實質(zhì)是信息的傳輸。而高速度、高質(zhì)量地傳送信息是信息傳輸?shù)幕締栴}。將信源信息通過信道傳送給信宿，怎樣才能做到盡可能不失真而又快速呢？這就需要解決兩個問題：第一，在不失真或允許一定失真的條件下，如何用盡可能少的符號來傳送信源信息；第二，在信道受干擾的情況下，如何增加信號的抗干擾能力，同時又使得信息傳輸率最大。為了解決這兩個問題，就要引入信源編碼和信道編碼。一般來說，提高抗干擾能力（降低失真或錯誤概率）往往是以降低信息傳輸率為代價的；反之，要提高信息傳輸率常常又會使抗干擾能力減弱。二者是有矛盾的。然而在信息論的編碼定理中，已從理論上證明，至少存在某種最佳的編碼或信息處理方法，能夠解決上述矛盾，做到既可靠又有效地傳輸信息。這些結(jié)論對各種通信系統(tǒng)的設(shè)計和估價具有重大的理論指導(dǎo)意義。4.1編碼的定義編碼實質(zhì)上是對信源的原始符號按一定的數(shù)學(xué)規(guī)則進(jìn)行的一種變換。討論無失真信源編碼，可以不考慮干擾問題，所以它的數(shù)學(xué)描述比較簡單。圖4.1是一個信源編碼器，它的輸入是信源符，同時存在另一符號，一般來說，元素是適合信道傳輸?shù)?，稱為碼符號（或者碼元）。編碼器的功能就是將信源符號集中的符號（或者長為N的信源符號序列）變換成由組成的長度為的一一對應(yīng)的序列。編碼器輸出圖4.1無失真信源編碼器輸出的碼符號序列稱為碼字，長度稱為碼字長度或簡稱碼長?？梢?，編碼就是從信源符號到碼符號的一種映射。若要實現(xiàn)無失真編碼，則這種映射必須是一一對應(yīng)的，并且是可逆的。碼符號的分類：下圖是一個碼分類圖下面，我們給出這些碼的定義。1.二元碼若碼符號集為，所有碼字都是一些二元序列，則稱為二元碼。二元碼是數(shù)字通信和計算機系統(tǒng)中最常用的一種碼。2.等長碼：若一組碼中所有碼字的碼長都相同，即，則稱為等長碼。3.變長碼：若一組碼組中所有碼字的碼長各不相同，則稱為變長碼。4.非奇異碼：若一組碼中所有碼字都不相同，則稱為非奇異碼。5.奇異碼：若一組碼中有相同的碼字，則稱為奇異碼。6.唯一可譯碼：若碼的任意一串有限長的碼符號序列只能唯一地被譯成所對應(yīng)的信源符號序列，則此碼稱為唯一可譯碼，否則就稱為非唯一可譯碼。7.非即時碼和即時碼：如果接收端收到一個完整的碼字后，不能立即譯碼，還要等下一個碼字開始接收后才能判斷是否可以譯碼，這樣的碼叫做非即時碼。如果收到一個完整的碼字以后，就可以立即譯碼，則叫做即時碼。即時碼要求任何一個碼字都不是其他碼字的前綴部分，也叫做異前綴碼。碼樹：即時碼的一種簡單構(gòu)造方法是樹圖法。對給定碼字的全體集合來說，可以用碼樹來描述它。所謂樹，就是既有根、枝，又有節(jié)點。如圖4.2所示，圖中，最上端A為根節(jié)點，A、B、C、D、E皆為節(jié)點，E為終端節(jié)點。ABCD000E11111010010001圖4.2A、B、C、D為中間節(jié)點，中間節(jié)點不安排碼字，而只在終端節(jié)點安排碼字，每個終端節(jié)點所對應(yīng)的碼字就是從根節(jié)點出發(fā)到終端節(jié)點走過的路徑上所對應(yīng)的符號組成，如圖4.2中的終端節(jié)點E，走過的路徑為ABCDE，所對應(yīng)的碼符號分別為0、0、0、1，則E對應(yīng)的碼字為0001?？梢钥闯?，按樹圖法構(gòu)成的碼一定滿足即時碼的定義（一一對應(yīng)，非前綴碼）。從碼樹上可以得知，當(dāng)?shù)陔A的節(jié)點作為終端節(jié)點，且分配碼字，則碼字的碼長為。任一即時碼都可以用樹圖法來表示。當(dāng)碼字長度給定后，用樹圖法安排的即時碼不是唯一的。如圖4.2中，如果把左樹枝安排為1，右樹枝安排為0，則得到不同的結(jié)果。對一個給定的碼，畫出其對應(yīng)的樹，如果有中間節(jié)點安排了碼字，則該碼一定不是即時碼。每個節(jié)點上都有個分支的樹稱為滿樹，否則為非滿樹。即時碼的碼樹圖還可以用來譯碼。當(dāng)收到一串碼符號序列后，首先從根節(jié)點出發(fā)，根據(jù)接收到的第一個碼符號來選擇應(yīng)走的第一條路徑，再根據(jù)收到的第二個符號來選擇應(yīng)走的第二條路徑，直到走到終端節(jié)點為止，就可以根據(jù)終端節(jié)點，立即判斷出所接收的碼字。然后從樹根繼續(xù)下一個碼字的判斷。這樣，就可以將接收到的一串碼符號序列譯成對應(yīng)的信源符號序列?？死蛱兀↘raft）不等式定理4.1對于碼符號為的任意唯一可譯碼，其碼字為，所對應(yīng)的碼長為，則必定滿足克拉夫特不等式反之，若碼長滿足上面的不等式，則一定存在具有這樣碼長的即時碼。注意：克拉夫特不等式只是說明唯一可譯碼是否存在，并不能作為唯一可譯碼的判據(jù)（可以排除，不能肯定）。如{0，10，010，111}滿足克拉夫特不等式，但卻不是唯一可譯碼。例題：設(shè)二進(jìn)制碼樹中，對應(yīng)的，由上述定理，可得因此不存在滿足這種碼長的唯一可譯碼?？梢杂脴浯a進(jìn)行檢查。唯一可譯碼的判斷法（變長）：將碼C中所有可能的尾隨后綴組成一個集合F，當(dāng)且僅當(dāng)集合F中沒有包含任一碼字，則可判斷此碼C為唯一可譯碼。集合F的構(gòu)成方法：首先，觀察碼C中最短的碼字是否是其它碼字的前綴，若是，將其所有可能的尾隨后綴排列出。而這些尾隨后綴又有可能是某些碼字的前綴，再將這些尾隨后綴產(chǎn)生的新的尾隨后綴列出，然后再觀察這些新的尾隨后綴是否是某些碼字的前綴，再將產(chǎn)生的尾隨后綴列出，依此下去，直到?jīng)]有一個尾隨后綴是碼字的前綴為止。這樣，首先獲得了由最短的碼字能引起的所有尾隨后綴，接著，按照上述步驟將次短碼字、…等等所有碼字可能產(chǎn)生的尾隨后綴全部列出。由此得到由碼C的所有可能的尾隨后綴的集合F。例題：設(shè)碼C={0,10,1100,1110,1011,1101}，根據(jù)上述測試方法，判斷是否是唯一可譯碼。解：碼C={0,10,1100,1110,1011,1101}1.先看最短的碼字：“0”，它不是其他碼字前綴，所以沒有尾隨后綴。2.再觀察碼字“10”，它是碼字“1011”的前綴，因此有尾隨后綴：1011001001所以，集合F={11，00，10，01}，其中“10”為碼字，故碼C不是唯一可譯碼。4.2定長編碼定理前面已經(jīng)說過，所謂信源編碼，就是將信源符號序列變換成另一個序列（碼字）。設(shè)信源輸出符號序列長度為L，碼字的長度為，編碼的目的，就是要是信源的信息率最小，也就是說，要用最少的符號來代表信源。在定長編碼中，對每一個信源序列，都是定值，設(shè)等于K，我們的目的是尋找最小K值。要實現(xiàn)無失真的信源編碼，要求信源符號與碼字是一一對應(yīng)的，并求由碼字組成的符號序列的逆變換也是唯一的（唯一可譯碼）。則當(dāng)L足夠大時，必可使譯碼差錯小于；反之，當(dāng)時，譯碼差錯一定是有限值，當(dāng)L足夠大時，譯碼幾乎必定出錯。定長編碼定理：由L個符號組成的、每個符號熵為的無記憶平穩(wěn)信源符號序列，可用個符號（每個符號有m中可能值）進(jìn)行定長變碼。對任意，只要所以等長編碼定理告訴我們，只要碼字傳輸?shù)男畔⒘看笥谛旁葱蛄袛y帶的信息量，總可以實現(xiàn)幾乎無失真的編碼。條件時所取得符號數(shù)L足夠大。設(shè)差錯概率為，信源序列的自方差為則有：式中，左邊是輸出碼字每符號所能載荷的最大信息量當(dāng)和均為定值時，只要L足夠大，可小于任一整數(shù)，即此時要求：只要足夠小，就可以幾乎無差錯地譯碼，當(dāng)然代價是L變得更大。令為碼字最大平均符號信息量。定義編碼效率為：最佳編碼效率為無失真信源編碼定理從理論上闡明了編碼效率接近于1的理想編碼器的存在性，它使輸出符號的信息率與信源熵之比接近于1，但要在實際中實現(xiàn)，則要求信源符號序列的L非常大進(jìn)行統(tǒng)一編碼才行，這往往是不現(xiàn)實的。例題：設(shè)離散無記憶信源概率空間為信源熵為自信息方差為對信源符號采用定長二元編碼，要求編碼效率，無記憶信源有，因此可以得到如果要求譯碼錯誤概率，則由此可見，在對編碼效率和譯碼錯誤概率的要求不是十分苛刻的情況下，就需要個信源符號一起進(jìn)行編碼，這對存儲和處理技術(shù)的要求太高，目前還無法實現(xiàn)。如果用3比特來對上述信源的8個符號進(jìn)行定長二元編碼，L=1，此時可實現(xiàn)譯碼無差錯，但編碼效率只有2.55/3=85%。因此，一般說來，當(dāng)L有限時，高傳輸效率的定長碼往往要引入一定的失真和譯碼錯誤。解決的辦法是可以采用變長編碼。4.3變長編碼定理在變長編碼中，碼長是變化的。對同一信源，其即時碼或唯一可譯碼可以有許多種。究竟哪一種好呢？從高速傳輸信息的觀點來考慮，當(dāng)然希望選擇由短的碼符號組成的碼字，就是用碼長來作為選擇準(zhǔn)則，為此我們引入碼的平均長度。設(shè)信源為編碼后的碼字為其碼長分別為因為對唯一可譯碼來說，信源符號與碼字是一一對應(yīng)的，所以有則這個碼的平均長度為它是每個信源符號平均需用的碼元數(shù)。對某一信源來說，若有一個唯一可譯碼，其平均長度小于所有其它的唯一可譯碼的平均長度，則該碼稱為緊致碼，或稱最佳碼。無失真變長信源編碼的基本問題就是要找最佳碼。單個符號變長編碼定理：若一離散無記憶信源的符號熵為H(X)，每個信源符號用m進(jìn)制碼元進(jìn)行變長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足下面的不等式離散平穩(wěn)無記憶序列變長編碼定理（香農(nóng)第一定理）：對于平均符號熵為的離散平穩(wěn)無記憶信源，必存在一種無失真信源編碼方法，使平均信息率滿足下面的不等式其中，為任意小正數(shù)。上面的兩個定理實際上是一樣的，可以由第一個推導(dǎo)出第二個。設(shè)用m進(jìn)制碼元做變長編碼，序列長度為L個信源符號，則該序列所對應(yīng)的碼字的平均長度滿足下面的不等式而平均輸出信息率為故有當(dāng)L足夠大時，可使因此香農(nóng)第一編碼定理給出了碼字的平均長度的下界和上界。但并不是說大于這上界不能構(gòu)成唯一可譯碼，而是因為我們總是希望盡可能短。定理說明當(dāng)平均碼長小于上界時，唯一可譯碼也存在。也就是說，定理給出的是最佳碼的最短平均碼長，并指出這個最短的平均碼長與信源熵是有關(guān)的。

編碼效率為剩余度（冗余度）為其信源熵為若用二元定長編碼（0，1）來構(gòu)造一個即時碼：，這時平均碼長為編碼效率為例題：設(shè)離散無記憶信源的概率空間為輸出的信息率為再對長度為2的信源序列進(jìn)行變長編碼，其即時碼如下表所示：序列序列概率即時碼序列序列概率即時碼9/1603/161103/16101/16111這個碼的平均長度為每一單個符號的平均碼長為其編碼效率為編碼復(fù)雜了，但信息傳輸率和效率有了提高。同樣可以求得信源序列長度增加到3和4時，進(jìn)行變長編碼所得的編碼效率和信息傳輸率分別為如果對這一信源采用定長二元碼編碼，要求編碼效率達(dá)到96%，允許譯碼錯誤概率，則可以算出自信息方差為為需要的信源序列長度為可以看出，使用定長編碼時，為了使編碼效率