信息論-第五章-無(wú)失真信源編碼

1、第五章 無(wú)失真信源編碼5.1信源編碼的相關(guān)概念碼序列：信源輸出的符號(hào)序列，需要變換成適合信道傳輸?shù)姆?hào)序列。編碼：對(duì)信源輸出的原始符號(hào)按照一定的數(shù)學(xué)規(guī)則進(jìn)行的這種變換稱為編碼5.1.1編碼器：完成編碼功能的器件信源編碼器的輸入是信源符號(hào)集S=s1，s2，. . .sq，共有q個(gè)信源符號(hào)。同時(shí)存在另一符號(hào)集X=x1，x2xr，共有r個(gè)碼符號(hào)，碼符號(hào)集X中的元素稱為碼元或碼符號(hào)。編碼器的作用就是將信源符號(hào)集S中的符號(hào)si，i=1，2，q變換成由li個(gè)碼符號(hào)組成的一一對(duì)應(yīng)的碼符號(hào)序列。編碼器輸出的碼符號(hào)序列稱為碼字，并用wi， i=1，2，q來(lái)表示，它與信源符號(hào)si ，i=1，2，q之間是一一對(duì)應(yīng)的

2、關(guān)系碼字的集合C稱為碼，即C=w1，w2，wq。信源符號(hào)si對(duì)應(yīng)的碼字wi包含li個(gè)碼符號(hào)，li稱為碼字長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)。定長(zhǎng)碼:碼中所有碼字的長(zhǎng)度都相同變長(zhǎng)碼：碼中所有碼字的長(zhǎng)短不一，即碼字中碼符號(hào)個(gè)數(shù)不同N次擴(kuò)展碼假定信源符號(hào)集為S=s1，s2，sq2次擴(kuò)展信源為S=s1，s2，sq2次擴(kuò)展碼為C=w1,w2,wq5.1.2碼的分類分組碼和非分組碼分組碼:將信源符號(hào)集中的每個(gè)信源符號(hào)si固定地映射成一個(gè)碼字wi，這樣的碼稱為分組碼。非分組碼:又稱樹(shù)碼，編碼器輸出的碼符號(hào)通常與編碼器的所有信源符號(hào)都有關(guān)。2.奇異碼與非奇異碼非奇異碼：若一種分組碼中的所有碼字都不相同，則稱此分組碼為非奇異碼，否

3、則稱為奇異碼。非奇異碼是分組碼能夠正確譯碼的必要條件，而不是充分條件。3.唯一可譯碼與非唯一可譯碼任意有限長(zhǎng)的碼元序列，如果只能唯一地分割成一個(gè)個(gè)碼字，便稱為唯一可譯碼。一個(gè)分組碼若對(duì)于任意有限的整數(shù)N,其N次擴(kuò)展碼均為非奇異的，則為唯一可譯碼。唯一可譯碼的物理含義：不僅要求不同的碼字表示不同的信源符號(hào)，而且還要求對(duì)由信源符號(hào)構(gòu)成的符號(hào)序列進(jìn)行編碼時(shí)，在接收端仍能正確譯碼而不發(fā)生混淆唯一可譯碼首先是非奇異碼，且任意有限長(zhǎng)的碼字序列不會(huì)雷同。即時(shí)碼與非即時(shí)碼即時(shí)碼：無(wú)需考慮后續(xù)的碼符號(hào)就可以從 碼符號(hào)序列中譯出碼字，這樣的唯一可譯碼成為即時(shí)碼。收到一個(gè)碼字后立即可以譯碼，我們稱這種碼為逗點(diǎn)碼，也

4、是一種即時(shí)碼，是唯一可譯碼的一種。一個(gè)唯一可譯碼成為即時(shí)碼的充要條件是其中任何一個(gè)碼字都不是其他碼字的前綴。定理5.1一個(gè)唯一可譯碼成為即時(shí)碼的充要條件是其中任何一個(gè)碼字都不是其他碼字的前綴。充要性：如果任何一個(gè)碼字都不是其他碼字的前綴，則在接收到一個(gè)相當(dāng)于一個(gè)完整碼字的碼符號(hào)后便可立即譯碼，無(wú)需考慮其后的碼符號(hào)。必要性：如果設(shè)wi是wj的前綴，則在收到相當(dāng)于wi的碼符號(hào)序列后還不能立即判定它是一個(gè)完整的碼字，若想正確譯碼，還必須參考后續(xù)的碼符號(hào)，這與即時(shí)碼的定義相矛盾，所以即時(shí)碼的必要條件是其中任何一個(gè)碼字都不是其他碼字的前綴。5.2定長(zhǎng)碼定長(zhǎng)非奇異碼一定是唯一可譯碼。若對(duì)一個(gè)有q個(gè)信源符號(hào)

5、的信源S進(jìn)行定長(zhǎng)編碼，那么信源S存在唯一可譯定長(zhǎng)碼的條件是其中，r是碼符號(hào)集中的碼元數(shù)，l 是定長(zhǎng)碼的碼長(zhǎng)。5.3變長(zhǎng)碼及變長(zhǎng)編碼定理5.3.1 Kraft不等式和McMillan不等式Kraft不等式McMillan不等式定理5.3 設(shè)信源符號(hào)集為S=s1,s2,sq,碼符號(hào)集為X=x1,x2,xr,對(duì)信源進(jìn)行編碼，得到的碼為C= w1,w2,wq,碼長(zhǎng)分別為l1，l2，lq.即時(shí)碼存在的充要條件是 這稱為Kraft不等式。充分性：滿足不等式 便可得到即時(shí)碼。必要性：即時(shí)碼必然滿足不等式即時(shí)碼必然可以用數(shù)圖來(lái)構(gòu)造，并且葉子節(jié)點(diǎn)不會(huì)再生出樹(shù)枝。我們可取一個(gè)有 階的r叉樹(shù)且 ，樹(shù)的第0階是根，在

6、第 階上共有 個(gè)節(jié)點(diǎn)，于是長(zhǎng)為 的碼字相當(dāng)于砍去了該r叉樹(shù)第 階上的 個(gè)節(jié)點(diǎn)，q個(gè)碼字共砍去第 階的節(jié)點(diǎn)數(shù)必小于 即 舉例5.4下面以碼字集合的形式給出5種不同的編碼，第一個(gè)碼的碼符號(hào)集合為x,y,z,其他各個(gè)碼都是二進(jìn)制碼xx,xz,y,zz,xyz000,10,00,11100,101,0,1101,100,011,00,111,1010,1011,110101,111,011,00,010,110對(duì)上述5種編碼，分別回答下述問(wèn)題：（1）此碼的碼長(zhǎng)分布是否滿足Kraft-McMillan不等式？（2）此碼是否是即時(shí)碼？如果是畫(huà)出樹(shù)突。（3）此碼是否是唯一可譯碼？寫(xiě)出判斷過(guò)程。5.3.2唯一可譯碼的判別準(zhǔn)則定理5.5 一個(gè)碼是唯一可譯碼的充要條件是F1,F2,的并集中沒(méi)有C中的碼字。設(shè)C為碼字集合，按以下步驟構(gòu)造此碼的尾隨后綴集合F:(1)考查C中所有的碼字，若wi是wj的前綴，則將相應(yīng)的后綴作為一個(gè)尾隨后綴碼放入集合F1中；（2）考查C和Fi兩個(gè)集合，若wiC是wiF的前綴或wiF是wiC的前綴，則將相應(yīng)的后綴作為尾隨后綴碼放