g第5章：信源編碼1

1、第五章 信源編碼通信系統(tǒng)的優(yōu)化模型n信源信源編碼加密信道編碼信源譯碼信道譯碼信道解密信宿密 鑰 源噪聲密 鑰 源ULVLULSmCmXnYnCmSmVLK1K2本章內(nèi)容n離散信源編碼離散信源編碼n連續(xù)信源編碼連續(xù)信源編碼5.1 離散信源編碼n編碼的基本概念編碼的基本概念n碼的分類碼的分類n定長(zhǎng)編碼定理定長(zhǎng)編碼定理n變長(zhǎng)編碼定理變長(zhǎng)編碼定理n香農(nóng)編碼香農(nóng)編碼n費(fèi)諾編碼費(fèi)諾編碼n赫夫曼編碼赫夫曼編碼 a1, a2, , aK 為信源符號(hào)集，序列中每一個(gè)符號(hào)為信源符號(hào)集，序列中每一個(gè)符號(hào)uml都取自信源符都取自信源符號(hào)集。號(hào)集。 b1 ，b2 ，bD 是適合信道傳輸?shù)氖沁m合信道傳輸?shù)腄個(gè)符號(hào)，用作信

2、源編碼器的個(gè)符號(hào)，用作信源編碼器的編碼符號(hào)。編碼輸出碼字編碼符號(hào)。編碼輸出碼字cm = cm1 cm2 cmn， c mk b1 ，b2 ，bD k = 1, 2 , , n ，n表示碼字長(zhǎng)度，簡(jiǎn)稱表示碼字長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)碼長(zhǎng) 信源符號(hào)信源符號(hào) a1,a2, , aK 信道符號(hào)（碼符號(hào)）信道符號(hào)（碼符號(hào)） b1, b2, , bD 信源編碼器信源編碼器 ui = ui1 ui2 uiL 碼字碼字ci = ci1 ci2 cin 1、編碼的基本概念信源符號(hào)集信源符號(hào)集=我我, 是是, 一名一名，學(xué)生，老師，編碼，理論，學(xué)生，老師，編碼，理論, 信道符號(hào)集信道符號(hào)集=I=I ，am，is, are,

3、 a, student, coding, theory, apple, 如果某次該編碼器的輸入是如果某次該編碼器的輸入是“我是一名學(xué)生我是一名學(xué)生”，即輸入序列，即輸入序列ui = (ui1=“我我”，ui2=“是是” ，ui3=“一名一名” ，ui4=“學(xué)生學(xué)生”)，編碼器，編碼器的輸出的輸出“I am a student”，即輸出序列，即輸出序列ci = (ci1=“I”, ci2 =“am”, ci3 =“a”, ci4 =“student”) 信源編碼可看成是從信源符號(hào)集到碼符號(hào)集的一種映射信源編碼可看成是從信源符號(hào)集到碼符號(hào)集的一種映射，即將，即將信源符號(hào)集中的每個(gè)元素（可以是單符號(hào)

4、，也可以是符號(hào)序列）映信源符號(hào)集中的每個(gè)元素（可以是單符號(hào)，也可以是符號(hào)序列）映射成一個(gè)長(zhǎng)度為射成一個(gè)長(zhǎng)度為n的碼字。對(duì)于同一個(gè)信源，編碼方法是多種的。的碼字。對(duì)于同一個(gè)信源，編碼方法是多種的?！纠纠?.1】 用用 u1 ，u2 ，u3，u4， 表示信源的四個(gè)消息，碼符號(hào)集為表示信源的四個(gè)消息，碼符號(hào)集為0,1，表，表1列出了該信源的幾種不同編碼。列出了該信源的幾種不同編碼。表1 同一信源的幾種不同編碼2、編碼的分類信源信源消息消息各消息各消息概率概率碼碼1 1碼碼2 2碼碼3 3碼碼4 4u1q( (u1) )000001u2q( (u2) )1101110u3q( (u3) )10100

5、0100u4q( (u4) )1111111000碼碼5 51010010001 3.變長(zhǎng)碼變長(zhǎng)碼若碼字集合若碼字集合C中的所有碼字中的所有碼字cm (m = 1,2, ,M)，其碼長(zhǎng)不都相同，稱其碼長(zhǎng)不都相同，稱碼碼C為變長(zhǎng)碼，表為變長(zhǎng)碼，表1中列出的碼中列出的碼3、碼、碼4 和碼和碼5就是變長(zhǎng)碼。就是變長(zhǎng)碼。 2.等長(zhǎng)碼等長(zhǎng)碼在一組碼字集合在一組碼字集合C中的所有碼字中的所有碼字cm (m = 1,2, ,M)，其碼長(zhǎng)都相同，其碼長(zhǎng)都相同，則稱這組碼則稱這組碼C為等長(zhǎng)碼，表為等長(zhǎng)碼，表1中列出的碼中列出的碼1、碼、碼2 就碼長(zhǎng)就碼長(zhǎng)n = 2等長(zhǎng)碼等長(zhǎng)碼一般，可以將碼簡(jiǎn)單的分成如下幾類：一

6、般，可以將碼簡(jiǎn)單的分成如下幾類： 1.二元碼二元碼若碼符號(hào)集為若碼符號(hào)集為0，1，則碼字就是二元序列，稱為二元碼，則碼字就是二元序列，稱為二元碼, ,二元碼二元碼通過(guò)二進(jìn)制信道傳輸，這是數(shù)字通信和計(jì)算機(jī)通信中最常見的一種通過(guò)二進(jìn)制信道傳輸，這是數(shù)字通信和計(jì)算機(jī)通信中最常見的一種碼，表碼，表1列出的列出的5種碼都是二元碼。種碼都是二元碼。 5.非奇異碼非奇異碼從信源消息到碼字的影射是一一對(duì)應(yīng)的，每一個(gè)不同的信源消從信源消息到碼字的影射是一一對(duì)應(yīng)的，每一個(gè)不同的信源消息都用不同的碼字對(duì)其編碼，例表息都用不同的碼字對(duì)其編碼，例表1 1中的碼中的碼2、碼、碼3、碼、碼4和碼和碼5都都是非奇異碼。是非奇

7、異碼。 4.奇異碼奇異碼對(duì)奇異碼來(lái)說(shuō)，從信源消息到碼對(duì)奇異碼來(lái)說(shuō)，從信源消息到碼字的影射不是一一對(duì)應(yīng)的。例表字的影射不是一一對(duì)應(yīng)的。例表1中中的碼的碼1 1，信源消息，信源消息u2和和u4都用碼字都用碼字11對(duì)其編碼，因此這種碼就是奇異碼對(duì)其編碼，因此這種碼就是奇異碼，奇異碼不具備惟一可譯性。，奇異碼不具備惟一可譯性。6 6）唯一可譯碼：）唯一可譯碼：若碼的任意一串有限長(zhǎng)的碼符號(hào)序列只能唯一地被譯成所對(duì)應(yīng)若碼的任意一串有限長(zhǎng)的碼符號(hào)序列只能唯一地被譯成所對(duì)應(yīng)的信源符號(hào)序列，則此碼稱為唯一可譯碼，否則就稱為非唯一的信源符號(hào)序列，則此碼稱為唯一可譯碼，否則就稱為非唯一可譯碼。可譯碼。1110010

8、04321ssss等長(zhǎng)碼等長(zhǎng)碼非奇異碼非奇異碼0 0 0 1 1 0 1 14321ssss唯一可譯唯一可譯 如果接收端收到一個(gè)完整的碼字后，不能立即譯碼，還要如果接收端收到一個(gè)完整的碼字后，不能立即譯碼，還要等下一個(gè)碼字開始接收后才能判斷是否可以譯碼，這樣的碼叫等下一個(gè)碼字開始接收后才能判斷是否可以譯碼，這樣的碼叫做非即時(shí)碼。做非即時(shí)碼。7 7 非即時(shí)碼：非即時(shí)碼：10001001014321ssss非奇異碼非奇異碼1 1 0 1 0 0 1 0 0 01 0?2s01不即時(shí)不即時(shí)任何一個(gè)碼字是其它碼字的延長(zhǎng)或前綴任何一個(gè)碼字是其它碼字的延長(zhǎng)或前綴如果收到一個(gè)完整的碼字以后，就可以立即譯碼，

9、則叫做即時(shí)碼。如果收到一個(gè)完整的碼字以后，就可以立即譯碼，則叫做即時(shí)碼。即時(shí)碼要求任何一個(gè)碼字都不是其他碼字的前綴部分，也叫做即時(shí)碼要求任何一個(gè)碼字都不是其他碼字的前綴部分，也叫做異異前綴碼。前綴碼。8 8、即時(shí)碼、即時(shí)碼00010010114321ssss非奇異碼非奇異碼1 0 1 0 0 1 0 0 0 1任何一個(gè)碼字不是其它碼字的延長(zhǎng)或前綴任何一個(gè)碼字不是其它碼字的延長(zhǎng)或前綴即 時(shí) 碼0 12s即時(shí)n即時(shí)碼的判決準(zhǔn)則即時(shí)碼的判決準(zhǔn)則n克拉夫特不等式：克拉夫特不等式：設(shè)信源為設(shè)信源為 ，對(duì)其進(jìn)行，對(duì)其進(jìn)行r元信源編碼，相應(yīng)碼字長(zhǎng)度為元信源編碼，相應(yīng)碼字長(zhǎng)度為 ，則即時(shí)碼存在，則即時(shí)碼存在的

10、充要條件是：的充要條件是：nuuuU,21nlll,2111nilirn唯一可譯碼的判決準(zhǔn)則唯一可譯碼的判決準(zhǔn)則n麥克米倫不等式：麥克米倫不等式：設(shè)信源為設(shè)信源為 ，對(duì)其進(jìn)行，對(duì)其進(jìn)行r元信源編碼，相應(yīng)碼字長(zhǎng)度為元信源編碼，相應(yīng)碼字長(zhǎng)度為 ，則唯一可譯碼，則唯一可譯碼存在的充要條件是：存在的充要條件是：nuuuU,21nlll,2111nilirn不同編碼方式的衡量標(biāo)準(zhǔn)不同編碼方式的衡量標(biāo)準(zhǔn)n平均碼長(zhǎng)：平均碼長(zhǎng)：對(duì)離散無(wú)記憶信源進(jìn)行信源編碼，設(shè)編碼后各個(gè)對(duì)離散無(wú)記憶信源進(jìn)行信源編碼，設(shè)編碼后各個(gè)碼字的碼長(zhǎng)分別為碼字的碼長(zhǎng)分別為 ，則定義該碼的平均碼長(zhǎng)為：，則定義該碼的平均碼長(zhǎng)為：n如果某種編碼

11、方式的平均碼長(zhǎng)小于所有其他編碼方式，則該如果某種編碼方式的平均碼長(zhǎng)小于所有其他編碼方式，則該碼稱為緊致碼或最佳碼。碼稱為緊致碼或最佳碼。 niiilupL1nlll,21n編碼信息率編碼信息率(編碼速率編碼速率)：n碼長(zhǎng)碼長(zhǎng) 表示長(zhǎng)為表示長(zhǎng)為N的信源序列用多少個(gè)的信源序列用多少個(gè)r進(jìn)制碼符號(hào)表示，因進(jìn)制碼符號(hào)表示，因此此 表示平均一個(gè)信源符號(hào)用多少個(gè)表示平均一個(gè)信源符號(hào)用多少個(gè)r進(jìn)制符號(hào)表示，再進(jìn)制符號(hào)表示，再乘以乘以 表示將表示將r進(jìn)制轉(zhuǎn)換成二進(jìn)制進(jìn)制轉(zhuǎn)換成二進(jìn)制signbitrNlR/logNl /rlogln編碼效率：編碼效率：n含義：理論上平均每個(gè)信源符號(hào)用多少個(gè)二進(jìn)制符號(hào)的個(gè)數(shù)含義：

12、理論上平均每個(gè)信源符號(hào)用多少個(gè)二進(jìn)制符號(hào)的個(gè)數(shù)除以實(shí)際上用的二進(jìn)制碼符號(hào)的個(gè)數(shù)，即表示一種編碼的效除以實(shí)際上用的二進(jìn)制碼符號(hào)的個(gè)數(shù)，即表示一種編碼的效率。率。 RuHn 有時(shí)消息太多，不可能或者沒(méi)必要給每個(gè)消息都分配有時(shí)消息太多，不可能或者沒(méi)必要給每個(gè)消息都分配一個(gè)碼字；一個(gè)碼字；n 給多少消息分配碼字可以做到幾乎無(wú)失真譯碼？給多少消息分配碼字可以做到幾乎無(wú)失真譯碼？n 傳送碼字需要一定的信息率，碼字越多，所需的信息傳送碼字需要一定的信息率，碼字越多，所需的信息率越大。編多少碼字的問(wèn)題可以轉(zhuǎn)化為對(duì)信息率大小的率越大。編多少碼字的問(wèn)題可以轉(zhuǎn)化為對(duì)信息率大小的問(wèn)題；問(wèn)題；n 信息率越小越好，最小能

13、小到多少才能做到無(wú)失真譯信息率越小越好，最小能小到多少才能做到無(wú)失真譯碼呢？碼呢？ 這些問(wèn)題就是信源編碼定理要研究的問(wèn)題。這些問(wèn)題就是信源編碼定理要研究的問(wèn)題。 碼字與信息率的關(guān)系 信源編碼有信源編碼有定長(zhǎng)定長(zhǎng)和和變長(zhǎng)變長(zhǎng)兩種方法。兩種方法。n定長(zhǎng)編碼：定長(zhǎng)編碼：碼字長(zhǎng)度碼字長(zhǎng)度 K 是固定的，相應(yīng)的編碼是固定的，相應(yīng)的編碼定理稱為定長(zhǎng)信源編碼定理，是尋求定理稱為定長(zhǎng)信源編碼定理，是尋求最小最小 K 值值的編碼方法。的編碼方法。n變長(zhǎng)編碼：變長(zhǎng)編碼：K 是變值，相應(yīng)的編碼定理稱為變是變值，相應(yīng)的編碼定理稱為變長(zhǎng)編碼定理。這里的長(zhǎng)編碼定理。這里的 K 值最小意味著值最小意味著數(shù)學(xué)期望數(shù)學(xué)期望最小

14、最小。信源編碼的方法n定長(zhǎng)編碼定理定長(zhǎng)編碼定理：一個(gè)熵為一個(gè)熵為 H(X) 的的離散無(wú)記憶信源離散無(wú)記憶信源 X1X2XlXN，若對(duì)信源長(zhǎng)為，若對(duì)信源長(zhǎng)為 N 的符號(hào)序列進(jìn)行定長(zhǎng)編的符號(hào)序列進(jìn)行定長(zhǎng)編碼，設(shè)碼字是從碼，設(shè)碼字是從 m 個(gè)字母的碼符號(hào)集中，選取個(gè)字母的碼符號(hào)集中，選取 K 個(gè)碼元個(gè)碼元組成組成Y1Y2YkYK。對(duì)于任意。對(duì)于任意0，0 ，只要滿足，只要滿足 則當(dāng)則當(dāng) N 足夠大時(shí)，必可使譯碼差錯(cuò)小于足夠大時(shí)，必可使譯碼差錯(cuò)小于，即譯碼錯(cuò)誤概，即譯碼錯(cuò)誤概率能為任意小率能為任意小.反之，若：反之，若： 則不可能實(shí)現(xiàn)無(wú)失真編碼，而當(dāng)則不可能實(shí)現(xiàn)無(wú)失真編碼，而當(dāng) N 足夠大時(shí)，譯碼錯(cuò)誤

15、足夠大時(shí)，譯碼錯(cuò)誤概率近似等于概率近似等于1.)(log2XHmNK2)(log2XHmNK3、定長(zhǎng)編碼定理n定理中的公式改寫成：定理中的公式改寫成：Klog2mNH(X) Klog2m：表示長(zhǎng)為：表示長(zhǎng)為 K 的碼符號(hào)序列能載荷的最大信息量的碼符號(hào)序列能載荷的最大信息量NH(X) ：代表長(zhǎng)為：代表長(zhǎng)為N 的信源序列平均攜帶的信息量的信源序列平均攜帶的信息量 平均符號(hào)熵。平均符號(hào)熵。 定長(zhǎng)編碼定理告訴我們：定長(zhǎng)編碼定理告訴我們：只要碼字傳輸?shù)男畔⒘看笥谛旁磾y只要碼字傳輸?shù)男畔⒘看笥谛旁磾y帶的信息量，總可實(shí)現(xiàn)幾乎無(wú)失真編碼。帶的信息量，總可實(shí)現(xiàn)幾乎無(wú)失真編碼。 譯碼差錯(cuò)率：譯碼差錯(cuò)率：編碼效率：

16、編碼效率： )()(XHXH：mNK2log)(1XH )(log2XHmNKn可以證明： 。整整數(shù)數(shù)譯譯碼碼差差錯(cuò)錯(cuò)率率小小于于任任意意正正 niiiiiiiiXHxpxpXHxIEXHXHxIxIEXHxIExID1222222222)()(log)()()()()()(2)()()()(22)(xN 只要2222)1 ()()(XHxNn信源編碼定理從理論上說(shuō)明了編碼效率接近于信源編碼定理從理論上說(shuō)明了編碼效率接近于 1，即：，即： 的理想編碼器的存在性，代價(jià)是在實(shí)際編碼時(shí)的理想編碼器的存在性，代價(jià)是在實(shí)際編碼時(shí) 取無(wú)限長(zhǎng)的信源符號(hào)取無(wú)限長(zhǎng)的信源符號(hào) (N) 進(jìn)行統(tǒng)一編碼。進(jìn)行統(tǒng)一編碼。

17、說(shuō)明：說(shuō)明：定長(zhǎng)編碼定理是在平穩(wěn)無(wú)記憶離散信源的條定長(zhǎng)編碼定理是在平穩(wěn)無(wú)記憶離散信源的條件下論證的，但它同樣適用于平穩(wěn)有記憶信源，只件下論證的，但它同樣適用于平穩(wěn)有記憶信源，只是要求有記憶信源的是要求有記憶信源的極限熵極限熵和和極限方差極限方差存在即可。存在即可。對(duì)于平穩(wěn)有記憶信源，定理中的熵應(yīng)改為極限熵。對(duì)于平穩(wěn)有記憶信源，定理中的熵應(yīng)改為極限熵。1log)(2mNKXH例例：設(shè)單符號(hào)信源模型為：設(shè)單符號(hào)信源模型為：n其信息熵為：其信息熵為：H(X)=2.55（比特符號(hào)）（比特符號(hào)） 2(x)=1.323n若要求編碼效率為若要求編碼效率為 = 90%，即：即：n譯碼差錯(cuò)率為譯碼差錯(cuò)率為=10

18、6，則，則=0.28，n在差錯(cuò)率和效率要求都不苛刻的情況下，就必須有在差錯(cuò)率和效率要求都不苛刻的情況下，就必須有1600多萬(wàn)個(gè)多萬(wàn)個(gè)信源符號(hào)一起編碼，技術(shù)實(shí)現(xiàn)非常困難。信源符號(hào)一起編碼，技術(shù)實(shí)現(xiàn)非常困難。 04. 005. 006. 007. 010. 010. 018. 04 . 0)(87654321xxxxxxxxxpX90. 0)()( XHXH722106875. 1)(xN例：離散無(wú)記憶信源：n其信息熵為：n自信息的方差為： 41,43,)(21xxxpX（比比特特信信源源符符號(hào)號(hào)）811. 034log434log41)(22 XH 4715. 0)811. 0(41log414

19、3log43)()(log)()(2222212222 niiiiXHxpxpxID n若對(duì)信源若對(duì)信源X采取等長(zhǎng)二元編碼時(shí)，要求采取等長(zhǎng)二元編碼時(shí)，要求=0.96，=105n信源序列長(zhǎng)度需長(zhǎng)達(dá)信源序列長(zhǎng)度需長(zhǎng)達(dá)4130萬(wàn)萬(wàn)以上，才能實(shí)現(xiàn)給定的要以上，才能實(shí)現(xiàn)給定的要求，這在實(shí)際中很難實(shí)現(xiàn)。求，這在實(shí)際中很難實(shí)現(xiàn)。n一般來(lái)說(shuō)，當(dāng)一般來(lái)說(shuō)，當(dāng) N 有限時(shí)，高傳輸效率的等長(zhǎng)碼往往要引有限時(shí)，高傳輸效率的等長(zhǎng)碼往往要引入一定的失真和錯(cuò)誤，它不能像變長(zhǎng)碼那樣可以實(shí)現(xiàn)無(wú)入一定的失真和錯(cuò)誤，它不能像變長(zhǎng)碼那樣可以實(shí)現(xiàn)無(wú)失真編碼。失真編碼。7522222221013.410)04.0()96.0()811.

20、0(4715.0)1()()(XHxN(1) 基本概念基本概念(2) 碼樹圖碼樹圖(3) 變長(zhǎng)編碼定理變長(zhǎng)編碼定理 4、變長(zhǎng)編碼定理(1) 基本概念基本概念n變長(zhǎng)編碼（不等長(zhǎng)編碼）：變長(zhǎng)編碼（不等長(zhǎng)編碼）：不等長(zhǎng)編碼允許把等長(zhǎng)的消不等長(zhǎng)編碼允許把等長(zhǎng)的消息變換成不等長(zhǎng)的碼序列。通常把經(jīng)常出現(xiàn)的消息編成息變換成不等長(zhǎng)的碼序列。通常把經(jīng)常出現(xiàn)的消息編成短碼短碼，不常出現(xiàn)的消息編成，不常出現(xiàn)的消息編成長(zhǎng)碼長(zhǎng)碼。這樣可使。這樣可使平均碼長(zhǎng)平均碼長(zhǎng)最最短，從而提高通信效率，代價(jià)是增加了編譯碼設(shè)備的復(fù)短，從而提高通信效率，代價(jià)是增加了編譯碼設(shè)備的復(fù)雜度。雜度。 例如：在不等長(zhǎng)碼字組成的序列中要正確識(shí)別每個(gè)

21、長(zhǎng)例如：在不等長(zhǎng)碼字組成的序列中要正確識(shí)別每個(gè)長(zhǎng)度不同的碼字的起點(diǎn)就比等長(zhǎng)碼復(fù)雜得多。度不同的碼字的起點(diǎn)就比等長(zhǎng)碼復(fù)雜得多。n譯碼延時(shí)譯碼同步：譯碼延時(shí)譯碼同步：接收到一個(gè)不等長(zhǎng)碼序列后，有接收到一個(gè)不等長(zhǎng)碼序列后，有時(shí)不能馬上斷定碼字是否真正結(jié)束，因而不能立即譯出時(shí)不能馬上斷定碼字是否真正結(jié)束，因而不能立即譯出該碼，要等到后面的符號(hào)收到后才能正確譯出。該碼，要等到后面的符號(hào)收到后才能正確譯出。例例：碼碼 1：顯然不是惟一可譯碼。顯然不是惟一可譯碼。x2 和和 x4 對(duì)應(yīng)于同一碼字對(duì)應(yīng)于同一碼字“11”，碼碼 1 是一個(gè)奇異碼。是一個(gè)奇異碼。碼碼 2：是非奇異碼，不是惟一可譯碼。當(dāng)收到一串碼符

22、是非奇異碼，不是惟一可譯碼。當(dāng)收到一串碼符號(hào)號(hào)“01000”時(shí)，可將它譯成時(shí)，可將它譯成“x4 x3 x1”，也可譯為，也可譯為“x4x1x3”， “x1x2x3”或或“x1x2x1x1”等，這種碼從單等，這種碼從單個(gè)碼字來(lái)看雖然不是奇異的，但從有限長(zhǎng)的碼序列來(lái)看，個(gè)碼字來(lái)看雖然不是奇異的，但從有限長(zhǎng)的碼序列來(lái)看，它仍然是一個(gè)奇異碼。它仍然是一個(gè)奇異碼。例例：碼碼 3：雖然是惟一可譯碼，但它要等到下一個(gè)雖然是惟一可譯碼，但它要等到下一個(gè)“1”收到收到后才能確定碼字的結(jié)束，譯碼有延時(shí)。后才能確定碼字的結(jié)束，譯碼有延時(shí)。碼碼 4：既是惟一可譯碼，又沒(méi)有譯碼延時(shí)。碼字中的符既是惟一可譯碼，又沒(méi)有譯碼

23、延時(shí)。碼字中的符號(hào)號(hào)“1”起了逗點(diǎn)的作用，故稱為起了逗點(diǎn)的作用，故稱為逗點(diǎn)碼逗點(diǎn)碼。即時(shí)碼即時(shí)碼/前綴條件碼前綴條件碼/異前置碼異前置碼/異字頭碼異字頭碼/逗點(diǎn)碼逗點(diǎn)碼/非延非延長(zhǎng)碼長(zhǎng)碼：如果一個(gè)碼的任何一個(gè)碼字都不是其它碼字的前：如果一個(gè)碼的任何一個(gè)碼字都不是其它碼字的前綴。綴。碼 4 是即時(shí)碼 (2) 碼樹圖碼樹圖 m 元（元（m 進(jìn)制）碼樹圖進(jìn)制）碼樹圖n樹根：樹根：最頂部畫一個(gè)起始點(diǎn)。最頂部畫一個(gè)起始點(diǎn)。n樹枝：樹枝：從根部引出從根部引出 m 條線段，每條線段都稱為樹枝。條線段，每條線段都稱為樹枝。n一級(jí)節(jié)點(diǎn)：一級(jí)節(jié)點(diǎn)：自根部起自根部起,通過(guò)一條樹枝到達(dá)的節(jié)點(diǎn)。一級(jí)通過(guò)一條樹枝到達(dá)的節(jié)

24、點(diǎn)。一級(jí)節(jié)點(diǎn)最多有節(jié)點(diǎn)最多有 m 個(gè)個(gè).nn 級(jí)節(jié)點(diǎn)：級(jí)節(jié)點(diǎn)：通過(guò)通過(guò) n 條樹枝達(dá)到的節(jié)點(diǎn)。最多有條樹枝達(dá)到的節(jié)點(diǎn)。最多有 mn。n終節(jié)點(diǎn)終節(jié)點(diǎn)/終端節(jié)點(diǎn)：終端節(jié)點(diǎn)：下面不再有樹枝的節(jié)點(diǎn)。下面不再有樹枝的節(jié)點(diǎn)。n中間節(jié)點(diǎn)：中間節(jié)點(diǎn)：除了樹根和終節(jié)點(diǎn)以外的節(jié)點(diǎn)。除了樹根和終節(jié)點(diǎn)以外的節(jié)點(diǎn)。n聯(lián)枝：聯(lián)枝：串聯(lián)的樹枝。串聯(lián)的樹枝。n滿樹：滿樹：在碼樹圖中，在碼樹圖中，當(dāng)每一個(gè)碼字的串聯(lián)枝數(shù)都相同時(shí)，當(dāng)每一個(gè)碼字的串聯(lián)枝數(shù)都相同時(shí)，就是定長(zhǎng)碼。此時(shí)的碼樹稱為滿樹。就是定長(zhǎng)碼。此時(shí)的碼樹稱為滿樹。 例如：碼長(zhǎng)為例如：碼長(zhǎng)為 N 的滿樹的終節(jié)點(diǎn)個(gè)數(shù)為的滿樹的終節(jié)點(diǎn)個(gè)數(shù)為 mN，即可表示，即可表示 mN

25、個(gè)碼字。個(gè)碼字。n非滿樹：非滿樹：有些樹枝未用時(shí)的碼樹。有些樹枝未用時(shí)的碼樹。 非滿樹構(gòu)造的就是變長(zhǎng)碼非滿樹構(gòu)造的就是變長(zhǎng)碼。 如果每一個(gè)碼字都被安排在終節(jié)點(diǎn)上如果每一個(gè)碼字都被安排在終節(jié)點(diǎn)上,這種碼就是即時(shí)碼。這種碼就是即時(shí)碼。(3) 變長(zhǎng)編碼定理變長(zhǎng)編碼定理 變長(zhǎng)編碼定理（香農(nóng)第一定理）變長(zhǎng)編碼定理（香農(nóng)第一定理）n平均碼長(zhǎng)：平均碼長(zhǎng)：n變長(zhǎng)編碼定理：變長(zhǎng)編碼定理：若一若一離散無(wú)記憶信源離散無(wú)記憶信源的平均符號(hào)熵為的平均符號(hào)熵為 H(X)，對(duì)信源符號(hào)進(jìn)行，對(duì)信源符號(hào)進(jìn)行 m 元變長(zhǎng)編碼，一定存在一種元變長(zhǎng)編碼，一定存在一種無(wú)失真編碼方法，其碼字平均長(zhǎng)度無(wú)失真編碼方法，其碼字平均長(zhǎng)度 滿足下

26、列不等滿足下列不等式：式： 其平均信息率滿足不等式其平均信息率滿足不等式 H(X) + RH(X)，式，式中中為任意正數(shù)。為任意正數(shù)。mXHKmXH22log)(log)(1 niiikxpK1)(n多符號(hào)情況多符號(hào)情況n 對(duì)于平穩(wěn)無(wú)記憶信源來(lái)說(shuō)，當(dāng)信源輸出的是長(zhǎng)度為對(duì)于平穩(wěn)無(wú)記憶信源來(lái)說(shuō)，當(dāng)信源輸出的是長(zhǎng)度為 N 的消息序列時(shí)，容易證明定理中式子可改進(jìn)為：的消息序列時(shí)，容易證明定理中式子可改進(jìn)為：n 這時(shí)的這時(shí)的 代表代表平均碼序列長(zhǎng)度。平均碼序列長(zhǎng)度。mXNHKmXNH22log)(log)(1K 證明：證明：n 多符號(hào)情況多符號(hào)情況n 已知編碼后已知編碼后平均每個(gè)信源符號(hào)能載荷的最大信息

27、量平均每個(gè)信源符號(hào)能載荷的最大信息量為（不等長(zhǎng)信源編碼信源平均輸出為（不等長(zhǎng)信源編碼信源平均輸出信息率信息率）：）：，mNKR2logNmN2log足夠大時(shí)，可使當(dāng))(log)(2XHRNmXH故有：n對(duì)信源進(jìn)行變長(zhǎng)編碼一般所要求的信源符號(hào)長(zhǎng)度對(duì)信源進(jìn)行變長(zhǎng)編碼一般所要求的信源符號(hào)長(zhǎng)度N 比定比定長(zhǎng)編碼小的多。長(zhǎng)編碼小的多。：，得得到到編編碼碼效效率率的的下下界界由由： )()(XHRXHNmXHXHRXH2log)()()( 變長(zhǎng)編碼定理（香農(nóng)第一定理）n信道的信息傳輸率為（從信道的角度看）：n編碼效率定義為：n二元無(wú)損無(wú)噪信道中 m=2，所以 Hm(X)=H(X) 碼碼符符號(hào)號(hào)比比特特信信

28、源源符符號(hào)號(hào)碼碼符符號(hào)號(hào)信信源源符符號(hào)號(hào)比比特特/)(/)(KHKHRX XX X KmHKHm2log)()(X XX X ：平平均均碼碼長(zhǎng)長(zhǎng)KRKH )(X X 例例：設(shè)單符號(hào)信源模型為：設(shè)單符號(hào)信源模型為：其信息熵為：其信息熵為：H(X)=2.55（比特（比特/符號(hào)）符號(hào)）這里這里 m=2，log2m=1要求要求90%，則：，則： 04. 005. 006. 007. 010. 010. 018. 04 . 0)(87654321xxxxxxxxXPX428. 019 . 0155. 255. 2NN例例：與定長(zhǎng)編碼相比，對(duì)同一信源，要求編碼效率都達(dá)到與定長(zhǎng)編碼相比，對(duì)同一信源，要求編碼

29、效率都達(dá)到 90% 時(shí)，變長(zhǎng)編碼只需時(shí)，變長(zhǎng)編碼只需 N=4 進(jìn)行編碼，而等長(zhǎng)碼則進(jìn)行編碼，而等長(zhǎng)碼則要求要求 N 大于大于 1.6875107。用變長(zhǎng)編碼時(shí)。用變長(zhǎng)編碼時(shí), N 不需要不需要很大就可以達(dá)到相當(dāng)高的編碼效率而且可實(shí)現(xiàn)無(wú)失真編很大就可以達(dá)到相當(dāng)高的編碼效率而且可實(shí)現(xiàn)無(wú)失真編碼。碼。例例：離散無(wú)記憶信源：離散無(wú)記憶信源：n其信息熵為：其信息熵為：n用二元碼符號(hào)用二元碼符號(hào)(0,1)來(lái)構(gòu)造一個(gè)即時(shí)碼：來(lái)構(gòu)造一個(gè)即時(shí)碼：x10，x21n這時(shí)平均碼長(zhǎng)：這時(shí)平均碼長(zhǎng)：n編碼效率為：編碼效率為：n信道信息傳輸率為：信道信息傳輸率為：R=0.811 比特比特/二元碼符號(hào)二元碼符號(hào) 41,43,

30、)(21xxxpX信信源源符符號(hào)號(hào)）（比比特特/811. 034log434log41)(22 XH信信源源符符號(hào)號(hào)）（二二元元碼碼符符號(hào)號(hào)/1 K811. 0)( KXH 例例：n為了提高傳輸效率，對(duì)無(wú)記憶信源為了提高傳輸效率，對(duì)無(wú)記憶信源 X 的二次擴(kuò)展信源的二次擴(kuò)展信源 X2 進(jìn)行編碼，下面給出擴(kuò)展信源進(jìn)行編碼，下面給出擴(kuò)展信源 X2 及其某一個(gè)即時(shí)碼：及其某一個(gè)即時(shí)碼：信信源源符符號(hào)號(hào)）（二二元元碼碼符符號(hào)號(hào)/322722 KK二二個(gè)個(gè)信信源源符符號(hào)號(hào)）（二二元元碼碼符符號(hào)號(hào) /162731613163216311692 K 這個(gè)碼的平均長(zhǎng)度為：這個(gè)碼的平均長(zhǎng)度為： 信源符號(hào)信源符號(hào)X

31、中每一單個(gè)符號(hào)的平均碼長(zhǎng)為：中每一單個(gè)符號(hào)的平均碼長(zhǎng)為：例例：n其編碼效率為：其編碼效率為：n信息傳輸速率為：信息傳輸速率為：n編碼復(fù)雜了一些，但信息傳輸率有了提高。編碼復(fù)雜了一些，但信息傳輸率有了提高。n對(duì)信源對(duì)信源X的三次和四次擴(kuò)展信源進(jìn)行編碼，編碼效率為：的三次和四次擴(kuò)展信源進(jìn)行編碼，編碼效率為：n信息傳輸率為：信息傳輸率為：二二元元碼碼符符號(hào)號(hào)）（比比特特/96102.R 9610278110322. 二二元元碼碼符符號(hào)號(hào)）（比比特特二二元元碼碼符符號(hào)號(hào)）（比比特特/9910/985043.R.R 9910985043. 例例：n 與定長(zhǎng)碼比較：對(duì)于同一信源，要求編碼效率都達(dá)到與定長(zhǎng)碼

32、比較：對(duì)于同一信源，要求編碼效率都達(dá)到96%時(shí)，變長(zhǎng)碼只需對(duì)二次擴(kuò)展信源（時(shí)，變長(zhǎng)碼只需對(duì)二次擴(kuò)展信源（N=2）進(jìn)行編碼，）進(jìn)行編碼，而等長(zhǎng)碼則要求而等長(zhǎng)碼則要求N4.13107。n 結(jié)論結(jié)論n 用變長(zhǎng)碼編碼時(shí)，用變長(zhǎng)碼編碼時(shí)，L不需要很大就可以達(dá)到相當(dāng)高的不需要很大就可以達(dá)到相當(dāng)高的編碼效率，而且可以實(shí)現(xiàn)無(wú)失真編碼。編碼效率，而且可以實(shí)現(xiàn)無(wú)失真編碼。n 隨著擴(kuò)展信源次數(shù)的增加，編碼的效率越來(lái)越接近于隨著擴(kuò)展信源次數(shù)的增加，編碼的效率越來(lái)越接近于1比特比特/二元碼符號(hào)，達(dá)到信源與信道匹配，使信道得二元碼符號(hào)，達(dá)到信源與信道匹配，使信道得到充分利用。到充分利用。n設(shè)離散無(wú)記憶信源：設(shè)離散無(wú)記憶信

33、源： niininixpxpxpxpxpxxxxXPX121211)(,)(,),(,),(),(,)(5、香農(nóng)編碼n 二進(jìn)制香農(nóng)碼的編碼步驟如下：二進(jìn)制香農(nóng)碼的編碼步驟如下：n將信源符號(hào)按概率從大到小的順序排列，為方便起見，令：將信源符號(hào)按概率從大到小的順序排列，為方便起見，令： p(x1) p(x2) p(xn)n 令令 p(x0)=0，用，用 pa(xj)，j=i+1 表示第表示第 i 個(gè)碼字的個(gè)碼字的累加概累加概率率，則：，則：n確定滿足下列不等式的整數(shù)確定滿足下列不等式的整數(shù) ki ，并令，并令 ki 為第為第 i 個(gè)碼字的長(zhǎng)個(gè)碼字的長(zhǎng)度度log2 p(xi) ki 1 log2 p

34、(xi)n 將將 pa(xj) 用二進(jìn)制表示，并取小數(shù)點(diǎn)后用二進(jìn)制表示，并取小數(shù)點(diǎn)后 ki 位作為符號(hào)位作為符號(hào) xi 的的編碼。編碼。njxpxpjiija, 2 , 1, )()(10 例例6.1.1 ：有一單符號(hào)離散無(wú)記憶信源：有一單符號(hào)離散無(wú)記憶信源：n對(duì)該信源編二進(jìn)制香農(nóng)碼。對(duì)該信源編二進(jìn)制香農(nóng)碼。 05. 010. 015. 020. 025. 025. 0,)(654321xxxxxxXPXn計(jì)算出給定信源香農(nóng)碼的平均碼長(zhǎng)：計(jì)算出給定信源香農(nóng)碼的平均碼長(zhǎng)：n若對(duì)上述信源采用等長(zhǎng)編碼，要做到無(wú)失真譯碼，每個(gè)符若對(duì)上述信源采用等長(zhǎng)編碼，要做到無(wú)失真譯碼，每個(gè)符號(hào)至少要用號(hào)至少要用 3

35、 個(gè)比特表示。相比較，香農(nóng)編碼對(duì)信源進(jìn)個(gè)比特表示。相比較，香農(nóng)編碼對(duì)信源進(jìn)行了壓縮。行了壓縮。)/(7 .2505.0410.03)15.02 .0(2225.0符符號(hào)號(hào)比比特特 Kn由離散無(wú)記憶信源熵定義，可計(jì)算出信源上熵為：由離散無(wú)記憶信源熵定義，可計(jì)算出信源上熵為：n對(duì)上述信源采用香農(nóng)編碼的信息率為：對(duì)上述信源采用香農(nóng)編碼的信息率為：n編碼效率為信源熵和信息率之比。則：編碼效率為信源熵和信息率之比。則：可以看出，編碼效率并不是很高。可以看出，編碼效率并不是很高。)/(42. 2)(log)()(612符符號(hào)號(hào)比比特特 iiixpxpXH2, 17 . 22log17 . 2log22 m

36、LmLKR這這里里%63.897 . 242. 2)( RXH n將概率按從大到小的順序排列，令：將概率按從大到小的順序排列，令：p(x1) p(x2) p(xn)n按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相等。如等。如編二進(jìn)制碼就分成兩組，編二進(jìn)制碼就分成兩組，編編 m 進(jìn)制碼就分成進(jìn)制碼就分成 m 組。組。n給每一組分配一位碼元。給每一組分配一位碼元。n將每一分組再按同樣原則劃分，重復(fù)步驟將每一分組再按同樣原則劃分，重復(fù)步驟 2 和和 3，直，直至概率不再可分為止。至概率不再可分為止。6、費(fèi)諾編碼例例6.3.1：設(shè)有一單符號(hào)離散信源：設(shè)

37、有一單符號(hào)離散信源n對(duì)該信源編二進(jìn)制費(fèi)諾碼。對(duì)該信源編二進(jìn)制費(fèi)諾碼。05. 010. 015. 020. 025. 025. 0,)(654321xxxxxxXPX表表二進(jìn)制費(fèi)諾編碼二進(jìn)制費(fèi)諾編碼 信源符號(hào)信源符號(hào) 概率概率 編碼編碼 碼字碼字 碼長(zhǎng)碼長(zhǎng) x1 0.25 0 00 2 x2 0.25 0 1 01 2 x3 0.20 0 10 2 x4 0.15 0 110 3 x5 0.10 0 1110 4 x6 0.05 1 1 1 1 1111 4 n該信源的熵為：該信源的熵為：n平均碼長(zhǎng)為：平均碼長(zhǎng)為：n對(duì)上述信源采用費(fèi)諾編碼的信息率為：對(duì)上述信源采用費(fèi)諾編碼的信息率為：n編碼效率為

38、：編碼效率為：n本例中費(fèi)諾編碼有較高的編碼效率。費(fèi)諾碼比較適合于本例中費(fèi)諾編碼有較高的編碼效率。費(fèi)諾碼比較適合于每次分組概率都很接近每次分組概率都很接近的信源。特別是對(duì)每次的信源。特別是對(duì)每次分組概率分組概率都相等都相等的信源進(jìn)行編碼時(shí)，可達(dá)到理想的編碼效率。的信源進(jìn)行編碼時(shí)，可達(dá)到理想的編碼效率。)/(42325. 2)(log)()(612符號(hào)比特iiixpxpXH)/( 54 . 2)(61符號(hào)比特iiikxpK2, 145. 22log145. 2log22mLmLKR這里%91.9845. 242325. 2)(RXH例例6.3.2：有一單符號(hào)離散無(wú)記憶信源：有一單符號(hào)離散無(wú)記憶信源

39、n對(duì)該信源編二進(jìn)制費(fèi)諾碼，編碼過(guò)程如下表。對(duì)該信源編二進(jìn)制費(fèi)諾碼，編碼過(guò)程如下表。 16/116/116/116/18/18/14/14/1,)(87654321xxxxxxxxXPXn信源熵為：信源熵為：H(X)=2.75(比特比特/符號(hào)符號(hào))n平均碼長(zhǎng)為：平均碼長(zhǎng)為：n編碼效率為編碼效率為=1。之所以如此，因?yàn)槊看嗡謨山M的。之所以如此，因?yàn)槊看嗡謨山M的概率恰好相等。概率恰好相等。（比比特特符符號(hào)號(hào)）75. 2440625. 03212. 02)25. 025. 0( K 哈夫曼哈夫曼( (HuffmanHuffman) ) 編碼是一種效率比較高的變長(zhǎng)無(wú)失編碼是一種效率比較高的變長(zhǎng)無(wú)失真

40、信源編碼方法。真信源編碼方法。7、哈弗曼編碼編碼步驟(1) 將信源符號(hào)按概率從大到小的順序排列，令：將信源符號(hào)按概率從大到小的順序排列，令：p(x1) p(x2) p(xn)(2) 信源的第一次縮減信源：信源的第一次縮減信源：給兩個(gè)概率最小的信源符號(hào)給兩個(gè)概率最小的信源符號(hào) p(xn1) 和和 p(xn) 各分配一個(gè)碼位各分配一個(gè)碼位“0”和和“1”，將這，將這兩個(gè)信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小的概兩個(gè)信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小的概率之和作為新符號(hào)的概率，結(jié)果得到一個(gè)只包含率之和作為新符號(hào)的概率，結(jié)果得到一個(gè)只包含 (n1) 個(gè)信源符號(hào)的新信源，用個(gè)信源符號(hào)的新信源，用

41、 S1 表示。表示。(3) 將縮減信源將縮減信源 S1 的符號(hào)仍按概率從大到小順序排列，的符號(hào)仍按概率從大到小順序排列，重復(fù)步驟重復(fù)步驟 (2)，得到只含，得到只含 (n2) 個(gè)符號(hào)的縮減信源個(gè)符號(hào)的縮減信源 S2。(4) 重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號(hào)為止，此重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號(hào)為止，此時(shí)所剩兩個(gè)符號(hào)的概率之和必為時(shí)所剩兩個(gè)符號(hào)的概率之和必為 1。然后從最后一級(jí)縮。然后從最后一級(jí)縮減信源開始，依編碼路徑向前返回，就得到各信源符號(hào)減信源開始，依編碼路徑向前返回，就得到各信源符號(hào)所對(duì)應(yīng)的碼字。所對(duì)應(yīng)的碼字。例例 設(shè)單符號(hào)離散無(wú)記憶信源如下，要求對(duì)信源編二進(jìn)制設(shè)單符號(hào)離散

42、無(wú)記憶信源如下，要求對(duì)信源編二進(jìn)制哈夫曼碼。哈夫曼碼。 04. 005. 006. 007. 01 . 01 . 018. 04 . 0,)(87654321xxxxxxxxXPXn在圖中讀取碼字的時(shí)候，一定要從后向前讀，此時(shí)編出在圖中讀取碼字的時(shí)候，一定要從后向前讀，此時(shí)編出來(lái)的碼字才是可分離的異前置碼。若從前向后讀取碼字，來(lái)的碼字才是可分離的異前置碼。若從前向后讀取碼字，則碼字不可分離。則碼字不可分離。n信源熵為：信源熵為：n平均碼長(zhǎng)為：平均碼長(zhǎng)為：n編碼效率為：編碼效率為：n若采用定長(zhǎng)編碼，碼長(zhǎng)若采用定長(zhǎng)編碼，碼長(zhǎng) K=3，則編碼效率：，則編碼效率：n哈夫曼的編碼效率提高了哈夫曼的編碼效

43、率提高了 12.7%。)/(55. 2)(log)()(812符符號(hào)號(hào)比比特特 iiixpxpXH（比比特特符符號(hào)號(hào)）61. 25)04. 005. 0(4)06. 007. 010. 0(3) 1 . 018. 0(14 . 0)(81 iiikxpK%7 .9761. 255. 2)()( KXHRXH %85355. 2 n 注意：注意：哈夫曼的編法并不唯一。哈夫曼的編法并不唯一。n 每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”和和“1”碼元是任意的，所以可得到不同的碼字。只要碼元是任意的，所以可得到不同的碼字。只要在各次縮在各次縮減信源中保持碼元分配的

44、一致性，減信源中保持碼元分配的一致性，即能得到可分離碼字。即能得到可分離碼字。n 不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng)不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng) ki 不不變，平均碼長(zhǎng)變，平均碼長(zhǎng) 也不變，所以沒(méi)有本質(zhì)區(qū)別；也不變，所以沒(méi)有本質(zhì)區(qū)別；n 縮減信源時(shí)，若合并后的新符號(hào)概率與其他符號(hào)概率縮減信源時(shí)，若合并后的新符號(hào)概率與其他符號(hào)概率相等，從編碼方法上來(lái)說(shuō)，相等，從編碼方法上來(lái)說(shuō)，這幾個(gè)符號(hào)的次序可任意排這幾個(gè)符號(hào)的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同列，編出的碼都是正確的，但得到的碼字不相同。不同的編法得到的碼字長(zhǎng)度的編法得到的碼字長(zhǎng)度 ki 也不盡相

45、同。也不盡相同。 例例 ：?jiǎn)畏?hào)離散無(wú)記憶信源：?jiǎn)畏?hào)離散無(wú)記憶信源 用兩種不同的方法對(duì)其編二進(jìn)制哈夫曼碼。用兩種不同的方法對(duì)其編二進(jìn)制哈夫曼碼。n方法一：方法一：合并后的新符號(hào)排在其它相同概率符號(hào)的后面。合并后的新符號(hào)排在其它相同概率符號(hào)的后面。 1 . 01 . 02 . 02 . 04 . 0,)(54321xxxxxXPX n方法二：方法二：合并后的新符號(hào)排在其它相同概率符號(hào)的前面。合并后的新符號(hào)排在其它相同概率符號(hào)的前面。n單符號(hào)信源編二進(jìn)制哈夫曼碼，編碼效率主要決定于信單符號(hào)信源編二進(jìn)制哈夫曼碼，編碼效率主要決定于信源熵和平均碼長(zhǎng)之比。對(duì)相同的信源編碼，其熵是一樣源熵和平均碼長(zhǎng)之比

46、。對(duì)相同的信源編碼，其熵是一樣的，采用不同的編法，得到的平均碼長(zhǎng)可能不同。平均的，采用不同的編法，得到的平均碼長(zhǎng)可能不同。平均碼長(zhǎng)越短，編碼效率就越高。碼長(zhǎng)越短，編碼效率就越高。n編法一的平均碼長(zhǎng)為：編法一的平均碼長(zhǎng)為：n編法二的平均碼長(zhǎng)為：編法二的平均碼長(zhǎng)為：n可見可見 ，本例兩種編法的平均碼長(zhǎng)相同，所，本例兩種編法的平均碼長(zhǎng)相同，所以編碼效率相同。以編碼效率相同。（比比特特符符號(hào)號(hào)） 5122 . 23) 1 . 01 . 0(2)2 . 02 . 04 . 0()(iiikxpK21KK （比特符號(hào)）（比特符號(hào)） 5112 . 24)1 . 01 . 0(32 . 022 . 014 .

47、 0)(iiikxpKn討論：n碼字長(zhǎng)度的方差碼字長(zhǎng)度的方差2：長(zhǎng)度長(zhǎng)度 ki 與平均碼長(zhǎng)與平均碼長(zhǎng) 之差的之差的平方的數(shù)學(xué)期望，即：平方的數(shù)學(xué)期望，即：n編法一碼字長(zhǎng)度方差：編法一碼字長(zhǎng)度方差：n編法二碼字長(zhǎng)度方差：編法二碼字長(zhǎng)度方差： niiiiKkxpKkE1222)()( 36. 1)2 . 24)(1 . 01 . 0()2 . 23(2 . 0)2 . 22(2 . 0)2 . 21(4 . 0222221 16. 0)2 . 23)(1 . 01 . 0()2 . 22)(2 . 02 . 04 . 0(2222 哪種方哪種方法更好？法更好？Kn比較：比較：第二種編碼方法的碼長(zhǎng)方

48、差要小許多。第二種編第二種編碼方法的碼長(zhǎng)方差要小許多。第二種編碼方法的碼長(zhǎng)變化較小，比較接近于平均碼長(zhǎng)。碼方法的碼長(zhǎng)變化較小，比較接近于平均碼長(zhǎng)。n第一種方法編出的第一種方法編出的 5 個(gè)碼字有個(gè)碼字有 4 種不同的碼長(zhǎng)；種不同的碼長(zhǎng)；n第二種方法編出的碼長(zhǎng)只有兩種不同的碼長(zhǎng)；第二種方法編出的碼長(zhǎng)只有兩種不同的碼長(zhǎng)；n第二種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn)，所以更好。第二種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn)，所以更好。n結(jié)論結(jié)論：m 進(jìn)制哈夫曼編碼n對(duì)如下單符號(hào)離散無(wú)記憶信源編三進(jìn)制哈夫曼碼對(duì)如下單符號(hào)離散無(wú)記憶信源編三進(jìn)制哈夫曼碼. 04. 005. 006. 007. 01 . 01 . 018. 04

49、 . 0,)(87654321xxxxxxxxXPXm 進(jìn)制哈夫曼編碼n對(duì)對(duì)m進(jìn)制編碼，可分離的碼字?jǐn)?shù)必為進(jìn)制編碼，可分離的碼字?jǐn)?shù)必為n即信源所含有的符號(hào)數(shù)為上值，如果不等于，則必須增加即信源所含有的符號(hào)數(shù)為上值，如果不等于，則必須增加s個(gè)不用個(gè)不用的碼字，此時(shí)的碼字，此時(shí)sC，則傳輸總要失真。，則傳輸總要失真。n 完全無(wú)失真?zhèn)魉筒豢蓪?shí)現(xiàn)完全無(wú)失真?zhèn)魉筒豢蓪?shí)現(xiàn)n 實(shí)際的信源常常是連續(xù)的，信息率無(wú)限大，要無(wú)失實(shí)際的信源常常是連續(xù)的，信息率無(wú)限大，要無(wú)失真?zhèn)魉鸵笮诺廊萘空鎮(zhèn)魉鸵笮诺廊萘緾 為無(wú)窮大；為無(wú)窮大；n 實(shí)際信道帶寬是有限的，所以信道容量受限制。要實(shí)際信道帶寬是有限的，所以信道容量受限

50、制。要想無(wú)失真?zhèn)鬏?，所需的信息率大大超過(guò)信道容量想無(wú)失真?zhèn)鬏?，所需的信息率大大超過(guò)信道容量 RC。(2) 實(shí)際中允許一定程度的失真實(shí)際中允許一定程度的失真n 實(shí)際生活中，人們一般并不要求獲得完全無(wú)失真的消實(shí)際生活中，人們一般并不要求獲得完全無(wú)失真的消息，通常只要求近似地再現(xiàn)原始消息，即允許一定的失息，通常只要求近似地再現(xiàn)原始消息，即允許一定的失真存在。真存在。n 打電話：打電話：即使語(yǔ)音信號(hào)有一些失真，接電話的人也即使語(yǔ)音信號(hào)有一些失真，接電話的人也能聽懂。人耳接收信號(hào)的帶寬和分辨率是有限的。能聽懂。人耳接收信號(hào)的帶寬和分辨率是有限的。n 放電影：放電影：理論上需要無(wú)窮多幅靜態(tài)畫面，由于人眼理

51、論上需要無(wú)窮多幅靜態(tài)畫面，由于人眼的的“視覺(jué)暫留性視覺(jué)暫留性”，實(shí)際上只要每秒放映，實(shí)際上只要每秒放映 24 幅靜態(tài)幅靜態(tài)畫面。畫面。n 有些失真沒(méi)有必要完全消除。有些失真沒(méi)有必要完全消除。n 既然允許一定的失真存在，對(duì)信息率的要求便可降既然允許一定的失真存在，對(duì)信息率的要求便可降低。低。(3) 信息率失真理論信息率失真理論n 信息率失真理論研究的內(nèi)容信息率失真理論研究的內(nèi)容: 與與之間的之間的關(guān)系關(guān)系.n 信息率失真函數(shù)信息率失真函數(shù)n 香農(nóng)定義了信息率失真函數(shù)香農(nóng)定義了信息率失真函數(shù) R(D)。n “保真度準(zhǔn)則下的信源編碼定理保真度準(zhǔn)則下的信源編碼定理”指出：指出：在允許一在允許一定失真度

52、定失真度 D 的情況下，信源輸出的信息率可壓縮到的情況下，信源輸出的信息率可壓縮到 R(D)。n 信息率失真理論是信息率失真理論是量化量化（模數(shù)轉(zhuǎn)換）、（模數(shù)轉(zhuǎn)換）、數(shù)模轉(zhuǎn)換數(shù)模轉(zhuǎn)換、頻帶壓縮頻帶壓縮和和數(shù)據(jù)壓縮數(shù)據(jù)壓縮的理論基礎(chǔ)。的理論基礎(chǔ)。(3) 信息率失真理論信息率失真理論n 信息率失真函數(shù)信息率失真函數(shù)極小值極小值問(wèn)題問(wèn)題n I(X;Y) 是是 P(X) 和和 P(Y/X) 的二元函數(shù)；的二元函數(shù)；n 在討論信道容量時(shí)在討論信道容量時(shí)：規(guī)定了規(guī)定了P(Y/X) ， I(X;Y) 變成變成了了P(X) 的函數(shù)。在離散情況下，因?yàn)榈暮瘮?shù)。在離散情況下，因?yàn)?I(X;Y) 對(duì)對(duì) p(xi)

53、是上凸函數(shù)，所以變更是上凸函數(shù)，所以變更 p(xi) 所求極值一定是所求極值一定是 I(X;Y)的極大值；在連續(xù)情況下，變更信源的極大值；在連續(xù)情況下，變更信源 P(X) 求出的也求出的也是極大值，但求極值時(shí)還要一些其它的限制條件。是極大值，但求極值時(shí)還要一些其它的限制條件。(3) 信息率失真理論信息率失真理論n 信息率失真函數(shù)信息率失真函數(shù)極小值極小值問(wèn)題問(wèn)題n 在討論信息率時(shí)在討論信息率時(shí)：可規(guī)定可規(guī)定 p(xi)，變更，變更 p(yj /xi) 來(lái)來(lái)求平均互信息的極值，稱為求平均互信息的極值，稱為信道容量對(duì)偶問(wèn)題信道容量對(duì)偶問(wèn)題。由于由于I(X;Y) 是是 p(yj /xi) 的下凸函數(shù)

54、，所求的極值一定是的下凸函數(shù)，所求的極值一定是極小值極小值。但若。但若 X 和和 Y 相互統(tǒng)計(jì)獨(dú)立（相互統(tǒng)計(jì)獨(dú)立（p(yj /xi)= p(yj )），這個(gè)極小值就是），這個(gè)極小值就是 0，因?yàn)?，因?yàn)?I(X;Y) 是非負(fù)的，是非負(fù)的，0 必為極小值，這樣求極小值就沒(méi)意義了。必為極小值，這樣求極小值就沒(méi)意義了。n 引入一個(gè)失真函數(shù)，計(jì)算在失真度一定的情況下信引入一個(gè)失真函數(shù)，計(jì)算在失真度一定的情況下信息率的極小值就變的有意義了。息率的極小值就變的有意義了。n失真的度量失真的度量n信息率失真函數(shù)信息率失真函數(shù)n離散信源的信息率失真函數(shù)離散信源的信息率失真函數(shù)n連續(xù)信源的信息率失真函數(shù)連續(xù)信源的信

55、息率失真函數(shù)n限失真信源編碼定理限失真信源編碼定理-香農(nóng)第三定理香農(nóng)第三定理5.2.1 信息的度量(1) 失真度(2) 常用失真函數(shù)(3) 平均失真度 （1）失真度）失真度n 設(shè)離散無(wú)記憶信源為：設(shè)離散無(wú)記憶信源為： )(,),(),(,)(2121mmjypypypyyyypYY：到到接接收收端端信信源源符符號(hào)號(hào)通通過(guò)過(guò)信信道道傳傳送送 )(,),(),(,)(2121nnixpxpxpxxxxpX )/()/()/()/()/()/()/()/()/()/(212222111211nmnnmmxypxypxypxypxypxypxypxypxypXYp信信道道的的傳傳遞遞概概率率矩矩陣陣：

56、失真的度量n 失真度失真度n 對(duì)每一對(duì)對(duì)每一對(duì) (xi,yj)，指定一個(gè)非負(fù)函數(shù)，指定一個(gè)非負(fù)函數(shù)d(xi,yj)0 i=1,2,n j=1,2,m稱稱 d(xi,yj) 為為單個(gè)符號(hào)的單個(gè)符號(hào)的（失真函數(shù)）。表示（失真函數(shù)）。表示信源發(fā)出一個(gè)符號(hào)信源發(fā)出一個(gè)符號(hào) xi，在接收端再現(xiàn)，在接收端再現(xiàn) yj 所引起的誤差所引起的誤差或失真?；蚴д?。n 失真矩陣失真矩陣n 失真度還可表示成矩陣的形式失真度還可表示成矩陣的形式n 稱稱 D D 為失真矩陣。它是為失真矩陣。它是 nm 階矩陣。階矩陣。n 連續(xù)信源和連續(xù)信道的失真函數(shù)連續(xù)信源和連續(xù)信道的失真函數(shù) 在連續(xù)信源和連續(xù)信道情況下，失真度定義為：

57、在連續(xù)信源和連續(xù)信道情況下，失真度定義為：d(x,y)0 ),(),(),(),(),(),(),(),(),(212221212111mnnnmmyxdyxdyxdyxdyxdyxdyxdyxdyxdD D（2）常用的失真函數(shù)）常用的失真函數(shù)n 第一種：第一種：n 當(dāng)當(dāng) i=j 時(shí)，時(shí)，X 與與 Y 的取值一樣，用的取值一樣，用 Y 來(lái)代表來(lái)代表 X 就沒(méi)就沒(méi)有誤差，所以定義失真度為有誤差，所以定義失真度為 0；n 當(dāng)當(dāng) ij 時(shí)，用時(shí)，用 Y 代表代表 X 就有誤差。就有誤差。n 這種定義認(rèn)為對(duì)所有不同的這種定義認(rèn)為對(duì)所有不同的 i 和和 j 引起的誤差都一樣，引起的誤差都一樣，所以定義所

58、以定義。 0000000),(aaaaaaaaaaaajiaajiyxdjiD D特點(diǎn)：特點(diǎn)：對(duì)角線上的元素均為對(duì)角線上的元素均為 0，對(duì)角線以外的其它元素都，對(duì)角線以外的其它元素都為常數(shù)為常數(shù) a。n 漢明失真函數(shù)漢明失真函數(shù)： a=1 。 0000000),(aaaaaaaaaaaajiaajiyxdjiD Dn 第二種（平方誤差失真函數(shù)）：第二種（平方誤差失真函數(shù)）：d(xi,yj)=(yjxi)2n 失真矩陣：失真矩陣：平方誤差失真矩陣平方誤差失真矩陣。n 若信源符號(hào)代表輸出信號(hào)的幅度值，則較大的幅度若信源符號(hào)代表輸出信號(hào)的幅度值，則較大的幅度失真比較小的幅度失真引起的錯(cuò)誤更為嚴(yán)重失真

59、比較小的幅度失真引起的錯(cuò)誤更為嚴(yán)重, 嚴(yán)重程度嚴(yán)重程度用平方表示用平方表示.n 第三種（絕對(duì)失真函數(shù)）：第三種（絕對(duì)失真函數(shù)）：n 失真矩陣：失真矩陣：絕對(duì)失真矩陣絕對(duì)失真矩陣。n 反映信宿接收幅值偏離信源發(fā)出幅值的程度反映信宿接收幅值偏離信源發(fā)出幅值的程度 jijiyxyxd),(n 第四種（相對(duì)失真函數(shù)）：第四種（相對(duì)失真函數(shù)）：n 失真矩陣：失真矩陣：相對(duì)失真矩陣相對(duì)失真矩陣。n 反映信宿收到信息后主觀感覺(jué)上的失真程度反映信宿收到信息后主觀感覺(jué)上的失真程度 ijijixyxyxd/),(n 二元對(duì)稱信源二元對(duì)稱信源 1 , 0Xn 漢明失真函數(shù)為漢明失真函數(shù)為1)0 , 1 () 1 ,

60、 0(0) 1 , 1 ()0 , 0(ddddn 接收變量接收變量 1 , 0Yn失真矩陣為失真矩陣為 0110Dn表示：當(dāng)發(fā)送信源符號(hào)表示：當(dāng)發(fā)送信源符號(hào)0(或符號(hào)或符號(hào)1)而接收后再現(xiàn)的仍是符號(hào)而接收后再現(xiàn)的仍是符號(hào)0(或符號(hào)或符號(hào)1)時(shí)，則認(rèn)為無(wú)失真存在，反之，則認(rèn)為有錯(cuò)誤存在時(shí)，則認(rèn)為無(wú)失真存在，反之，則認(rèn)為有錯(cuò)誤存在n 信源信源 1 , 0Xn失真函數(shù)為失真函數(shù)為1)2 , 1 ()2 , 0(2)0 , 1 () 1 , 0(0) 1 , 1 ()0 , 0(ddddddn 接收變量接收變量21 , 0 ，Yn失真矩陣為失真矩陣為 102120Dn 信源信源21 , 0 ，Xn失