【文章內(nèi)容簡(jiǎn)介】 ? ? 2 . 7 5 12 . 7 5DHXRn? ? ?(比特 /碼元時(shí)間 ) 信息論與編碼 167。 等長(zhǎng)碼及等長(zhǎng)編碼定理 一．等長(zhǎng)編碼定理 考慮對(duì)一簡(jiǎn)單信源 S進(jìn)行等長(zhǎng)編碼，信源符號(hào)集有 K個(gè)符號(hào)，碼符號(hào)集含 D個(gè)符號(hào)，碼字長(zhǎng)度記為 n。對(duì)信源作等長(zhǎng)無(wú)差錯(cuò)編碼，要得到惟一可譯碼，必須滿足下式： K ≤ D n 對(duì)單符號(hào)信源 S的 L次擴(kuò)展信源 S（ L） 進(jìn)行等長(zhǎng)編碼，要得到長(zhǎng)為 n的惟一可譯碼，必須滿足 : K L ≤ D n 對(duì)上式兩邊取對(duì)數(shù)，得： loglognKLD?信息論與編碼 ，對(duì)信源輸出的 L長(zhǎng)序列 si ， i = 1, 2, …, KL 進(jìn)行等長(zhǎng)編碼，碼字是長(zhǎng)度為 n的 D進(jìn)制符號(hào)串，當(dāng)滿足條件 ，則 L →∞ 時(shí)，可使譯碼差錯(cuò) pe δ(ε、 δ為無(wú)窮小量 ) ；反之，當(dāng) 時(shí)，則不可能實(shí)現(xiàn)無(wú)差錯(cuò)編碼。 對(duì)于那些出現(xiàn)概率極小的字符序列不予編碼，這樣可以減小平均碼長(zhǎng)，當(dāng)然這樣會(huì)帶來(lái)一定的失真。 下面的定理將證明，當(dāng)滿足一定的條件時(shí)，在 L →∞ 時(shí)，失真 pe →0 。 【 定理 】 等長(zhǎng)編碼定理 設(shè)離散無(wú)記憶信源 S ={x1, x2, …, xk}的熵為 H(X)， S的 L維擴(kuò)展信源為 ? ?12, , , L(L ) kS s s s?? ?logHXnLD???? ?logHXnLD???信息論與編碼 二．編碼效率 根據(jù)等長(zhǎng)碼的編碼定理，我們可以得到一個(gè)衡量編碼質(zhì)量的重要指標(biāo)，編碼效率。 等長(zhǎng)編碼定理要求 ，即 ，可看出比值 是一個(gè)小于 1的無(wú)量綱純數(shù)，定義它為等長(zhǎng)編碼的 編碼效率 ，記為： ? ?logHXnLD??? [ ( ) ]1lo gL H XnD???()logLH XnDDnXLHlo g)(??編碼效率 η是衡量編碼質(zhì)量的一個(gè)重要指標(biāo)，對(duì)信源編碼時(shí)應(yīng)盡量提高編碼效率。 信息論與編碼 【 例 】 （ 1）給定離散無(wú)記憶信源 ，對(duì)該信源進(jìn)行二進(jìn)制等長(zhǎng)編碼，并求編碼效率。 0 1 2( ) 0 .1 0 .7 0 .2X x x xPX? ? ? ??? ? ? ?? ? ? ?【 解 】 先確定碼長(zhǎng)：信源消息數(shù)目 K＝ 3，信源序列長(zhǎng)度 L＝ 1，碼符號(hào)數(shù) D＝ 2 loglognKLD?① 根據(jù) 1l o g l o g 3 1 .5 8 5l o g l o g 2LKnD? ? ?② 根據(jù)等長(zhǎng)編碼定理： ? ?logHXnLD???? ?2 l o g l o g 2LH XnD? ? ?( ) 0 . 1 l o g 0 . 1 0 . 7 l o g 0 . 7 0 . 2 l o g 0 . 2 1 . 1 5 6HX ? ? ? ? ?（比特 /符號(hào)） 0 1 2: 0 0 : 0 1 : 1 0x x x； ；根據(jù)前面計(jì)算，由等長(zhǎng)編碼定理計(jì)算出的下界更小，但由于碼長(zhǎng)都取整，故取 n1=n2=2。并做如下編碼： ，得到唯一可譯碼。 信息論與編碼 編碼效率為： 12( ) 1 . 1 5 6 0 . 5 7 8l o g 2 l o g 2LH XnD??? ? ? ?（ 2）對(duì)原信源進(jìn)行 L=2維擴(kuò)展，得到新信源： ( 2 )0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2( 2 ) 0 . 0 1 0 . 0 7 0 . 0 2 0 . 0 7 0 . 4 9 0 . 1 4 0 . 0 2 0 . 1 4 0 . 0 4()X x x x x x x x x x x x x x x x x x xpX?? ???????????對(duì)擴(kuò)展信源進(jìn)行二進(jìn)制等長(zhǎng)編碼。 【 解 】 對(duì)擴(kuò)展碼 K＝ 3，信源序列長(zhǎng)度 L＝ 2，碼符號(hào)數(shù) D＝ 2 ① 由 確定碼長(zhǎng)： loglognKLD? 3 l o g 2 l o g 3 3 .1 7 0l o g l o g 2LKn D? ? ?取 n3=4，對(duì)擴(kuò)展信源編碼的編碼如下： 信源序列 x0x0 x0x1 x0x2 x1x0 x1x1 x1x2 x2x0 x2x1 x2x2 碼字 0000 0001 0010 0011 0100 0101 0110 0111 1000 信息論與編碼 編碼效率： 33( ) 2 1 . 1 5 6 0 . 5 7 8l o g 4 l o g 2L H XnD??? ? ?② 按等長(zhǎng)編碼定理： ? ?42 1 .1 5 6 l o g l o g 2LH XnD?? ? ?取 n4=3，對(duì)擴(kuò)展信源編碼的編碼如下： 信源序列 x0x0 x0x1 x0x2 x1x0 x1x1 x1x2 x2x0 x2x1 x2x2 碼字 000 001 000 010 011 100 101 110 111 對(duì)于二進(jìn)制碼，取碼長(zhǎng)為 3，共可構(gòu)成 8個(gè)不同的碼字，而擴(kuò)展信源含 9個(gè)序列，故編碼時(shí)對(duì)序列中概率小的兩個(gè)序列賦予同一個(gè)碼字 000，這樣勢(shì)必存在譯碼差錯(cuò)概率 pe： ?44( ) 2 1 . 1 5 6 0 . 7 7 1l o g 3 l o g 2L H XnD??? ? ?信息論與編碼 167。 變長(zhǎng)碼及變長(zhǎng)編碼定理 一．變長(zhǎng)碼 對(duì)等長(zhǎng)碼的討論是在 L足夠大的條件下得到的結(jié)論，當(dāng) L為有限值時(shí)，則總會(huì)帶來(lái)一定程度的失真。對(duì)于變長(zhǎng)碼，往往在 L不是很大的情況下就可編出高效且無(wú)失真的碼。 變長(zhǎng)碼也要求原碼的任意 L次擴(kuò)展碼也是惟一可譯的。變長(zhǎng)碼分為即時(shí)碼和延長(zhǎng)碼，為保證即時(shí)譯碼，要求變長(zhǎng)惟一可譯碼采用即時(shí)碼。 對(duì)于變長(zhǎng)碼，要求整個(gè)碼集的平均碼長(zhǎng)力求最小，此時(shí)編碼效率最高。對(duì)于給定信源，使平均碼長(zhǎng)達(dá)到最小的編碼方法，稱為 最佳編碼 ，得到的碼集稱為 最佳碼 。 信息論與編碼 二．克拉夫特不等式 定理