離散信源無失真編碼PPT課件

1、31 緒論 為了實(shí)現(xiàn)高質(zhì)量、高效率的通信，引入了信源編碼和信道編碼。信源編碼和信道編碼主要需要解決以下兩個(gè)問題。提高傳輸效率 增強(qiáng)通信的可靠性 第1頁/共39頁（1）提高傳輸效率，用盡可能少的信道傳輸符號來傳遞信源消息，目的是提高傳輸效率，這是信源編碼主要應(yīng)考慮的問題。這里又分兩種情況討論，即允許接收信號有一定的失真或不允許失真。 綜上所述，提高抗干擾能力往往是以降低信息傳輸效率為代價(jià)的，而為了提高傳輸效率又往往削弱了其抗干擾能力。這樣，設(shè)計(jì)者在取舍之間就要作均衡考慮。 （2） 增強(qiáng)通信的可靠性如何增加信號的抗干擾能力，提高傳輸?shù)目煽啃?，這是信道編碼主要考慮的問題。解決這一問題，一般是采用冗余

2、編碼法，賦予信碼自身一定的糾錯和檢錯能力，只要采取適當(dāng)?shù)男诺谰幋a和譯碼措施，就可使信道傳輸?shù)牟铄e概率降到允許的范圍之內(nèi)。第2頁/共39頁信源編碼包括兩個(gè)功能： （1） 將信源符號變換成適合信道傳輸?shù)姆枺?（2） 壓縮信源冗余度，提高傳輸效率。第3頁/共39頁a1, a2, , aK為信源符號集，序列中每一個(gè)符號uml都取自信源符號集。b1 ，b2 ，bD是適合信道傳輸?shù)腄個(gè)符號，用作信源編碼器的編碼符號。編碼輸出碼字cm = cm1 cm2 cmn， c mkb1 ，b2 ，bD k = 1, 2 , , n ，n表示碼字長度，簡稱碼長 信源符號 a1,a2, , aK 信道符號（碼符號）b

3、1, b2, , bD 圖3-1 信源編碼器模型 信源 信源編碼器 一般來說，信源編碼可歸納為如圖3-1所示的模型。 消息 ui = ui1 ui2 uiL 碼字ci = ci1 ci2 cin 第4頁/共39頁 信源編碼可看成是從信源符號集到碼符號集的一種映射，即將信源符號集中的每個(gè)元素（可以是單符號，也可以是符號序列）映射成一個(gè)長度為n的碼字。對于同一個(gè)信源，編碼方法是多種的?！纠?.3】 用u1 ，u2 ，u3，u4表示信源的四個(gè)消息，碼符號集為0,1，表3-1列出了該信源的幾種不同編碼。表3-1 同一信源的幾種不同編碼信 源 消息各消息概率碼1碼2碼3碼4u1q(u1)000001u2

4、q(u2)1101110u3q(u3)101000100u4q(u4)11111110003.1.1 碼的分類第5頁/共39頁 3.變長碼變長碼若碼字集合C中的所有碼字cm (m = 1,2, ,M)，其碼長不都相同，稱碼C為變長碼，表3-1中列出的碼3、碼4 就是變長碼。 2.等長碼等長碼在一組碼字集合C中的所有碼字cm (m = 1,2, ,M)，其碼長都相同，則稱這組碼C為等長碼，表3-1中列出的碼1、碼2 就碼長n = 2等長碼。一般，可以將碼簡單的分成如下幾類： 1.二元碼二元碼若碼符號集為0，1，則碼字就是二元序列，稱為二元碼,二元碼通過二進(jìn)制信道傳輸，這是數(shù)字通信和計(jì)算機(jī)通信中最

5、常見的一種碼，表3-1列出的4種碼都是二元碼。第6頁/共39頁 5.非奇異碼非奇異碼從信源消息到碼字的影射是一一對應(yīng)的，每一個(gè)不同的信源消息都用不同的碼字對其編碼，例表3-1中的碼2、碼3和碼4都是非奇異碼。 4.奇異碼奇異碼對奇異碼來說，從信源消息到碼字的影射不是一一對應(yīng)的。例表3-1中的碼1，信源消息u2和u4都用碼字11對其編碼，因此這種碼就是奇異碼，奇異碼不具備惟一可譯性。第7頁/共39頁擴(kuò)展信源 信源編碼器 信源符號 a1,a2, , aK 信道符號（碼符號）b1, b2, , bD 消息 u1 uN = (u11 u12 u1L) (uN1 uN2 uNL) N次擴(kuò)展碼字 c1 c

6、N = (c11 c12 c1n) (cN1 cN2 cNn)圖3-2 N次擴(kuò)展信源編碼器模型 原碼的N次擴(kuò)展碼是將信源作N次擴(kuò)展得到的新信源符號序列u（N）=u1 uN = (u11 u12 u1L) (uN1 uN2 uNL)，對應(yīng)碼符號序列c（N）=c1 cN = (c11 c12 c1n) (cN1 cN2 cNn) ，記集合C (N) = c1(N), c2(N), ，C (N) 即原碼C的N次擴(kuò)展碼。 6.原碼原碼C的的N次擴(kuò)展碼次擴(kuò)展碼原碼C的N次擴(kuò)展碼中的每個(gè)元素是N次擴(kuò)展信源中的序列所對應(yīng)的N個(gè)碼字組成的序列。第8頁/共39頁對于定長碼，若原碼是惟一可譯碼，則它的N次擴(kuò)展碼也

7、是惟一可譯的，而對于變長碼則不盡然，見表3-2。信源消息各消息概率碼1碼2碼3u1q(u1)011u2q(u2)11001u3q(u3)00100001u4q(u4)1110000001表3-2 同一信源的幾種不同變長編碼表3-2 同一信源的幾種不同變長編碼 7.惟一可譯碼惟一可譯碼定義定義3.1 如果碼的任意N次擴(kuò)展碼都是非奇異碼，則稱該碼為惟一可譯碼。第9頁/共39頁 8. 即時(shí)碼即時(shí)碼對于變長碼，又有如下定義定義定義3.2 對于碼字c = c1 c2 cn, ,稱c、 = c1 c2 ci ( (i n) )為碼字c的字頭（前綴）。定義定義3.3 若碼中任一碼字都不是另一碼字的字頭，稱該

8、碼為異字頭碼（無前綴碼）。第10頁/共39頁表3-3中碼3，收到“1”后就知道一個(gè)碼字已經(jīng)完結(jié)，無須等待下一個(gè)符號抵達(dá)，所以無前綴碼能夠即時(shí)譯碼, 稱之為即時(shí)可譯碼，簡稱即時(shí)碼。 而對于碼2，收到“1”后，并不能立即做出判決，就是收到“10”也不能立即做出判決，則還要收到下面的碼元才能做出判決。所以非異字頭碼不能即時(shí)譯碼，稱為非即時(shí)碼，由于非異字頭碼的其中一些碼字是另一些碼字的延長，故也稱延長碼。顯然，即時(shí)碼是惟一可譯碼，而惟一可譯碼不一定是即時(shí)碼。 第11頁/共39頁即時(shí)碼可用樹圖法來構(gòu)造。圖3-3 用樹圖法編碼樹根編碼深度u1：1u2：01u3：001u4：00011 0 u1u2u3u4

9、1 1 1 0 0 【例3.4】 用樹圖法表示表3-2中的碼3，如圖3-3所示（D =2）。 第12頁/共39頁碼奇異碼非奇異碼非惟一可譯碼 惟一可譯碼變長碼等長碼即時(shí)碼延長碼 圖3-5 碼的分類結(jié)構(gòu)圖 圖3-5是碼的分類結(jié)構(gòu)圖 由上面的結(jié)構(gòu)圖可看出，將碼分為奇異碼和非奇異碼兩大類，我們只討論非奇異碼。非奇異碼又分為惟一可譯碼和非惟一可譯碼兩大類，我們只討論惟一可譯碼。 第13頁/共39頁3.1.2 平均碼長的計(jì)算平均碼長的計(jì)算 對于變長碼，碼集C的平均碼長，用符號 表示，定義為碼C中每個(gè)碼字cm( m = 1, 2, ，M)其碼長的概率加權(quán)平均值為 (3-1)式中nm是碼字cm所對應(yīng)的碼字的

10、長度，p ( cm )是碼字cm出現(xiàn)的概率。 Mmmmpnn1)(c cn對于等長碼，由于碼集C中的每個(gè)碼字的碼長都相同，平均碼長就等于每個(gè)碼字的碼長npnpnnmmmmm11)()(c cc c第14頁/共39頁N次擴(kuò)展碼的平均碼長 等于擴(kuò)展碼中碼字長度的概率加權(quán)平均值。對于2次擴(kuò)展碼，有： (3-2)設(shè)nm, ns分別是原信源消息um, us所對應(yīng)的碼長,cm, cs是um, us所對應(yīng)的碼字，則式(3-2)中的nm + ns是擴(kuò)展后新的信源序列nmns所對應(yīng)的碼字cmcs的長度，q(um) q (us)是cmcs出現(xiàn)的概率。n smmssmuquqnnn第15頁/共39頁3.1.3 信息

11、傳輸速率信息傳輸速率 信道的信息傳輸速率為信道單位時(shí)間內(nèi)所傳輸?shù)膶?shí)際信息量。若信息量以比特為單位，時(shí)間以秒為單位，則信息傳輸率定義為： (比特/秒) (3-3)nXtHtR若信息量以比特為單位，時(shí)間以碼元時(shí)間（傳輸一個(gè)碼符號的時(shí)間）為單位，則信息傳輸率記為 (比特/碼元時(shí)間) (3-4) nXHRDn為編碼后的平均碼長；H(X)為信源熵；式中：t為傳輸一個(gè)碼符號的時(shí)間。第16頁/共39頁【例3.8】 給定信源 ，為提高傳輸效率，使平均碼長盡可能短，遵照概率大取碼長短，概率小取碼長長的原則對上述信源進(jìn)行二進(jìn)制不等長編碼，得到 ，求編碼后的信息傳輸率RD 。16116116116181814141

12、)(76543210 xxxxxxxxXqX1111:101:1110:110:1001:01:1000:00:73625140 xxxxxxxx （比特/符號） （碼元/符號） (比特/碼元時(shí)間) 75. 22log75. 2161log161481log81241log412XH75. 21614481324122n 175. 275. 2nXHRD第17頁/共39頁3.2 等長碼及等長編碼定理等長碼及等長編碼定理考慮對一簡單信源S進(jìn)行等長編碼，信源符號集有K個(gè)符號，碼符號集含D個(gè)符號，碼字長度記為n。要得到惟一可譯碼，必須滿足下式K D n對單符號信源S的L次擴(kuò)展信源S（L）進(jìn)行等長編碼

13、，要得到長為n的惟一可譯碼，必須滿足K L D n （3-5）對式（3-5）兩邊取對數(shù)，得 （3-6） DKLnloglog 對于那些出現(xiàn)概率極小的字符序列不予編碼，這樣可以減小平均碼長，當(dāng)然這樣會帶來一定的失真。下面的定理3.1 將證明，當(dāng)滿足一定的條件時(shí)，在L 時(shí)，失真pe 0 第18頁/共39頁定理定理3.1 等長編碼定理等長編碼定理 設(shè)離散無記憶信源S =x1 ，x2 ，xk的熵為H（X），S的L維擴(kuò)展信源為 ，對信源輸出的L長序列si ，i = 1, 2, , KL 進(jìn)行等長編碼，碼字是長度為n的D進(jìn)制符號串，當(dāng)滿足條件 ，則L 時(shí)，可使譯碼差錯pe (、為無窮小量)；反之，當(dāng) 時(shí)，

14、則不可能實(shí)現(xiàn)無差錯編碼。,21)(LkLSs ss ss s DXHLnlog DXHLnlog編碼效率編碼效率定理3.1要求 ，即 ，可看出比值 是一個(gè)小于1的無量綱純數(shù)，定義它為等長編碼的編碼效率，記為 （3-7） DXHLnlogDnXHLlog)(1DnXLHlog)(DnXLHlog)(第19頁/共39頁3.3 3.3 變長碼及變長編碼定理 3.3.1 變長碼變長碼 對變長碼的討論是在L足夠大的條件下得到的結(jié)論，當(dāng)L為有限值時(shí)，則總會帶來一定程度的失真。對于變長碼，往往在L不是很大的情況下就可編出高效且無失真的碼。 變長碼也要求原碼的任意L次擴(kuò)展碼也是惟一可譯的。變長碼分為即時(shí)碼和延

15、長碼，為保證即時(shí)譯碼，要求變長惟一可譯碼采用即時(shí)碼。對于變長碼，要求整個(gè)碼集的平均碼長力求最小，此時(shí)編碼效率最高。對于給定信源，使平均碼長達(dá)到最小的編碼方法，稱為最佳編碼，得到的碼集稱為最佳碼。第20頁/共39頁3.3.2 克拉夫特不等式克拉夫特不等式 定理定理3.2 D進(jìn)制碼字集合C =c1, c2, cM ，碼集中每一cm（m = 1, 2, , M）都是一個(gè)D進(jìn)制符號串，設(shè)c1, c2, cM 對應(yīng)的碼長分別是n1, n2, , nM ，則存在唯一可譯碼的充要條件是 (3-10) MmnmD11式（3-10）也稱克拉夫特不等式 定理3.2只是說是存在惟一可譯碼的充要條件，這里強(qiáng)調(diào)的是“存

16、在”，但它并不是唯一可譯碼的充要條件，換言之，惟一可譯碼一定滿足克拉夫特不等式，反之，滿足克拉夫特不等式的碼不一定是惟一可譯碼。 第21頁/共39頁3.3.3 變長編碼定理變長編碼定理 定理定理3.3 給定熵為H（X）的離散無記憶信源，及有D個(gè)元素的碼符號集，則總可找到一種無失真編碼方法，構(gòu)成惟一可譯碼，其平均碼長 滿足： （3-19）n DXHnDXHlog1log定理定理3.4 變長編碼定理變長編碼定理 ( (Shannon第一定理第一定理) ) 給定熵為H（X）的離散無記憶信源 ，其L次擴(kuò)展信源 的熵記為H（X），給定有D個(gè)元素的碼符號集，對擴(kuò)展信源進(jìn)行編碼，總可以找到一種惟一可譯碼，使

17、碼長 滿足 (3-23) )()()()(2121MMxqxqxqxxxXqX)()()()(2121LMMqqqqx xx xx xx xx xx xX XX XLnLDXHLnDXHL1loglog第22頁/共39頁記 為信源每個(gè)符號所對應(yīng)的平均碼字?jǐn)?shù)，則式(3-23)為 （3-24） nLnL LDXHnDXH1loglogShannon第一定理的物理意義在于：對信源進(jìn)行編碼，使編碼后的碼集中各碼字盡可能等概分布，如果將這碼集看成為一個(gè)新的信源，這時(shí)新信源所含信息量最大。定義編碼效率編碼效率 (3-26)是一個(gè)無量綱的數(shù)，一般情況下1，在極限情況下=1。 DnXHnDXHloglog第2

18、3頁/共39頁對于同一種信源，三種編碼法中以香農(nóng)編碼法的編碼效率最低，費(fèi)諾編碼法也不是一種最佳編碼法，但用這種方法有時(shí)候也能找到緊致碼。一般情況下，霍夫曼編碼法得到的平均碼長 最短，即編碼效率 最高。DnXHlogn3.4 3.4 變長碼的編碼方法香農(nóng)（Shannon）編碼法費(fèi)諾(Fano)編碼法霍夫曼(Huffman)編碼法變長編碼法：第24頁/共39頁3.4.1 香農(nóng)編碼法 二進(jìn)制香農(nóng)編碼法其碼長的取值范圍: -log q (xm) nm -log q (xm) +1 （3-30）記離散信源 ，給定有D個(gè)元素的碼符號集，對信源進(jìn)行變長編碼，將各消息概率q(xm) (m = 1, 2, ,

19、M) 寫成如下的形式： )()()()(2121MMxqxqxqxxxXqXmtmDxq1)(取碼長nm (m = 1, 2, , M) 滿足： tm nm tm +1 （3-28） 第25頁/共39頁香農(nóng)編碼法具體步驟如下， （4）計(jì)算出第m個(gè)消息的累加概率 ，再將pi變換成二進(jìn)制小數(shù)，取小數(shù)點(diǎn)后面nm位作為第m個(gè)消息的代碼組11)(immixqp （3）根據(jù)式（3-31）：-log q (xm) nm -log q (xm) +1 （-log q (xm)為整數(shù)時(shí)取等號），計(jì)算出每個(gè)消息的二進(jìn)制代碼的長度nm。 （2）計(jì)算出各消息的 -log q(xm) 值，m =1, 2, , M； （

20、1）將信源發(fā)出的M個(gè)消息，按其概率遞減順序進(jìn)行排列第26頁/共39頁【例3.14】 對給定信源 進(jìn)行D =2進(jìn)制香農(nóng)編碼。01. 010. 015. 017. 018. 019. 02 . 0)(7654321xxxxxxxXqX消息符號消息符號ai消息概率消息概率qi-log2qi碼長碼長ni累加概率累加概率碼字碼字cia10.22.3430000a20.192.4130.2001a30.182.4830.39011a40.172.5630.57100a50.152.7430.74101a60.103.3440.891110a70.016.6670.991111110 表3-8 香農(nóng)編碼 第

21、27頁/共39頁以消息x5為例，對其進(jìn)行編碼：計(jì)算出 -log q(x5) = -log 0.15 = 2.74，取整數(shù)n5 = 3作為x5的碼字的碼長，計(jì)算出消息x1, x2, x3, x4累加概率將0.74變換成二進(jìn)制小數(shù) (0.74)10 = (0.1011110)2，取小數(shù)點(diǎn)后面三位101作為 x5的代碼。 151574. 017. 018. 019. 02 . 0)(mmxqp計(jì)算該編碼的編碼效率 先算出信源熵 =2.61(比特/符號)71)(log)()(mmmxqxqXH平均碼長 =3.14(比特/符號) 71)(mmmxqnn則編碼效率 831. 0114. 361. 2log

22、DnXH第28頁/共39頁3.4.2 費(fèi)諾編碼法費(fèi)諾編碼法 費(fèi)諾編碼法的具體步驟如下： （1）信源發(fā)出的M個(gè)消息，按其概率遞減順序進(jìn)行排列，把消息集 x1 , x2, x3, , xM 按其概率大小分解成兩個(gè)子集，使兩個(gè)子集的概率之和盡可能接近相等，把第一個(gè)子集編碼為“0”，第二個(gè)子集編碼為“1”，作為代碼組的第一個(gè)碼元 ； （2）對子集做第二次分解，同樣分解成兩個(gè)子集，并使兩個(gè)子集的概率盡可能接近相等，再把第一個(gè)子集編碼為“0”，第二個(gè)子集編碼為“1”，作為代碼組的第二個(gè)碼元； （3）如此一直進(jìn)行下去，直到各子集僅含一個(gè)消息為止 （4）將逐次分解過程當(dāng)中得到的碼元排列起來就是各消息的代碼。

23、第29頁/共39頁【例3.15.15】 對例3.14給出的 信源進(jìn)行費(fèi)諾編碼 01. 010. 015. 017. 018. 019. 02 . 0)(7654321xxxxxxxXqX （1）將信源消息分成兩個(gè)子集 x1，x2，x3和 x4，x5，x6，x7，兩個(gè)子集的和概率分別為0.2+0.19+0.18=0.57與0.17+0.15+0.10+0.01=0.43，賦予第一個(gè)子集碼元“0”，賦予第二個(gè)子集碼元“1”； （2）又將子集分成和概率盡可能接近相等的兩個(gè)子集，分別賦予第一個(gè)子集碼元“0”，賦予第二個(gè)子集碼元“1”； （3）一直進(jìn)行下去，直到每個(gè)子集僅含一個(gè)消息為止。 該編碼的編碼效

24、率 ：例3.14中已算出信源熵 H（X）=2.61（比特/符號） 平均碼長 =2.7471)(mmmxqnn則編碼效率： 935. 0174. 261. 2logDnXH第30頁/共39頁消息符號xi消息概率q(xm)第一次分解所得碼元第二次分解所得碼元第三次分解所得碼元第四次分解所得碼元碼字cm碼長nix10.2 0 0 002x20.19 10 0103x30.181 0113x40.17 10 102x50.15 10 1103 x60.10 1011104x70.01111114表3-9 費(fèi)諾編碼 第31頁/共39頁3.4.3 霍夫曼編碼法霍夫曼編碼法 設(shè)信源消息數(shù)M 2，記概率分布為

25、，存在D進(jìn)制惟一可譯碼C = c1, c2, , cM，對應(yīng)的碼長分別為n1, n2, , nM ，不失一般性，設(shè)q(x1 ) q(x2 ) q(xM )，則C = c c1, c c2, , c cM是最佳碼必須具備如下兩條性質(zhì)：1.1. n1 n2 nM；2.2.最后（最長）的D*個(gè)碼字，它們具有相同的前綴c，惟一的區(qū)別是最后一位碼符號不同，可將這D*個(gè)最長的碼字分別表示為c0，c1，c（D*-1）其中 D*2，3，D （3-31）且 D*= M mod (D-1) （3-32） )()()()(2121MMxqxqxqxxxXqX第32頁/共39頁定理定理3.5假定C * =c1 , c

26、2 , cM-D，c 為最佳碼，對應(yīng)概率Q*= q(x1 ) , q(x2 ) , q(xM-D*)，q* 其中q*可記為 q*= q(x M-D*+1) + q (xM-D*+2 ) + + q(xM)且概率分布滿足q(x1 ) q(x2 ) q(x M-D*) q (xM-D*+1 ) q(xM )則對應(yīng)概率分布為 Q =q(x1 ) , q(x2 ) , , q(xM-D*), q(x M-D*+1), q(xM) 的最佳碼是C =c1 , c2 , c cM-D*, c c0, c c1, , c c( D*-1)第33頁/共39頁 （3）將上述概率之和作為一新消息的概率，與余下的消息

27、一起組成一新的信源，再按概率遞減順序重新排列，如果概率之和與原信源的某個(gè)概率相等，則把概率之和排在上面，這樣可使合并消息重復(fù)編碼的次數(shù)減少，使短碼得到充分利用。 （4）如此一直進(jìn)行下去，直到兩個(gè)合并消息的概率之和為1； （5）從最后一步驟開始，沿編碼逆程取下各步驟得到的碼符號，如此構(gòu)成的碼符號序列即為對應(yīng)消息的碼字。 （2）將概率最小的二個(gè)消息分別編碼為“1”和“0”，（一般，將概率大的編碼為“1”，概率小的編碼為“0”），再對這兩個(gè)消息求概率之和 可以按照如下步驟編碼（先考慮D =2的情況），參見圖3-7 。 （1）將信源發(fā)出的M個(gè)消息，按其概率遞減順序進(jìn)行排列，得：q(x1 ) q(x2 ) q(x3) q(xM )第34頁/共39頁計(jì)算該編碼的編碼效率：例3.14中已算出信源熵 H（X）=2.61（比特/