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