信息論-第五章-無失真信源編碼

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

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

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

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

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

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