信息與編碼理論 第2版 課件 4.1 無失真信源編碼定理

第4章信源編碼本章內(nèi)容：無失真信源編碼定理無失真信源編碼限失真信源編碼定理限失真信源編碼§4.1無失真信源編碼定理4.1無失真信源編碼定理編碼分為無失真編碼限失真編碼信源編碼信道編碼

對(duì)信源進(jìn)行編碼，就是設(shè)計(jì)一個(gè)編碼器，將信源的原始符號(hào)按照一定的數(shù)學(xué)規(guī)則進(jìn)行變換，生成適合于信道傳輸?shù)姆?hào)，通常稱為碼元（碼序列）。我們將離散信源輸出信息定義為離散符號(hào)集，如下：4.1無失真信源編碼定理我們?cè)诮o消息分配碼字的時(shí)候分配多少可以做到無失真譯碼？碼字越多，所需要的信息率就越大，很明顯，我們希望信息率越小越好，但是信息率小到多少能保證無失真呢？我們首先要給出關(guān)于碼的定義。4.1無失真信源編碼定理1.二元碼如果碼符號(hào)集為，所得到的碼字都是二元序列，稱為二元碼。如果將信源通過二元信道進(jìn)行傳輸，那么就需要將信源符號(hào)轉(zhuǎn)換為由0和1組成的二元碼序列，這也是數(shù)字圖像處理最為常用的一種。2.等長碼（定長碼）如果一組碼中所有碼字的長度都相等，我們稱之為等長碼。3.變長碼如果一組碼中所有碼字的長度都不相同，我們稱之為變長碼。4.非奇異碼如果一組碼中所有碼字都不相同，即所有信源符號(hào)映射到不同的碼元序列，它們之間是一一對(duì)應(yīng)的，那么我們稱之為非奇異碼。4.1無失真信源編碼定理5.奇異碼如果一組碼中有相同的碼字，即所有信源符號(hào)映射到相同的碼元序列，那么我們稱之為奇異碼。6.同價(jià)碼如果碼符號(hào)集中每個(gè)碼符號(hào)所占用的傳輸時(shí)間都相同，則所得到的碼為同價(jià)碼。一般來講，二元碼都是同價(jià)碼。7.碼的次擴(kuò)展碼假設(shè)某碼，它把信源中的符號(hào)轉(zhuǎn)化成碼中的碼字，則碼的次擴(kuò)展碼是所有個(gè)碼字組成的碼字序列的集合。8.唯一可譯碼如果碼的任意一串有限長的碼符號(hào)序列只能被唯一的譯成所對(duì)應(yīng)的信源符號(hào)序列，那么此碼稱為唯一可譯碼。否則就稱為非唯一可譯碼。4.1無失真信源編碼定理4.1無失真信源編碼定理4.1無失真信源編碼定理那么最佳編碼效率為：該定理也說明，編碼信息率大于單符號(hào)熵時(shí)，可以做到幾乎無失真，前提是必須足夠大。可以證明，當(dāng)方差和均為定值時(shí)，只要信源序列長度滿足：即

譯碼差錯(cuò)率一定小于任意正數(shù)。4.1無失真信源編碼定理4.1無失真信源編碼定理變長編碼定理：

設(shè)離散無記憶信源為編碼后碼字碼長為對(duì)唯一可譯碼來講，信源符號(hào)與碼字一一對(duì)應(yīng)，因此碼的平均長度為4.1無失真信源編碼定理4.1無失真信源編碼定理4.1無失真信源編碼定理這個(gè)定理是香農(nóng)信息論中非常重要的一個(gè)定理，要做到無失真的信源編碼，信源每個(gè)符號(hào)所需要的平均碼元數(shù)就是信源的熵值，如果小于這個(gè)值，則唯一可譯碼不存在，在譯碼或反變換時(shí)必然帶來失真或差錯(cuò)，可見，信源的信息熵是無失真信源編碼的極限值。定理還指出，通過對(duì)擴(kuò)展信源進(jìn)行編碼，當(dāng)趨向于無窮時(shí)，平均碼長可以趨近該極限值。由可以得到我們定義：香農(nóng)第一定理就可以表述為：如果就存在唯一可譯變長碼如果則不存在唯一可譯變長碼4.1無失真信源編碼定理信道角度講，信道的信息傳輸率為由于所以當(dāng)平均