信息論與編碼無失真信源編碼

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