信息論與編碼無失真信源編碼定理與編碼山東大學(xué)期末考試知識點復(fù)習(xí)

1、第五章無失真信源編碼定理與編碼5. 1. 1 信源編碼和碼的類型1.信源編碼設(shè)值源S =值應(yīng),項,碼符號集X = 3 口2 > 口. Mr.稱為碼符號碼元,將 SiWj =3勺的氣 £ X < = > q或a. =呵 S將aL =M,產(chǎn)、工* G X這種一一對應(yīng)變換稱為信源編碼.W,稱為碼字,長度I為碼長.",的集合C稱為分組碼.2.碼的類型假設(shè)碼苻號臬中苻號數(shù)2稱為二天碼,3稱為三天碼r天碼.假設(shè)分組碼中所有碼字的碼長都相同那么稱為等長碼,否那么稱為變長 碼.假設(shè)分組碼中 所方碼字都不相 同那么 稱為非奇異碼,否那么稱為奇異碼.假設(shè)每個碼苻號?X 的傳輸

2、時間都相同那么稱為同價碼,否那么稱為非 同價碼.假設(shè)分組碼的任您一串有限長的碼苻號只備皂被唯一地譯成所對應(yīng)的 信源苻號序列那么稱為唯一可譯碼,否那么稱為非唯一可譯碼.假設(shè)分組碼中,沒有任何完裝的碼字是其他碼字的前緞.,那么稱為即 時碼又稱非延長碼或前綴條件碼,否那么稱為延長碼.本章主要研究的是同黃唯一可譯碼.5. 1. 2即時碼及其樹圖構(gòu)造法即時碼非延長碼或前綴條件碼是唯一可譯碼的一類子碼.即時碼可用樹圖法來構(gòu)造.構(gòu)造的要點是：(1) 最上端為樹根A, 從根出發(fā)向下伸出樹枝,樹枝總數(shù)等于r, 樹枝的盡頭為節(jié)點.(2) 從每個節(jié)點再伸出r枝樹枝,當(dāng)某節(jié)點被安排為碼字后,就不 再伸枝,這節(jié)點為終端

3、節(jié)點.一直繼續(xù)進行,直至都不能伸枝為止.(3) 每個節(jié)點所伸出的樹枝標(biāo)上碼符號,從根出發(fā)到終端節(jié)點所走 路徑對應(yīng)的碼苻號序列那么為終端節(jié)點的碼字.即時碼可用樹圖法來進行編碼和譯碼.從樹圖可知,即時碼可以即時進行譯碼.當(dāng)碼字長度給定,即時碼不是唯一的.可以認(rèn)為等長唯一可譯碼是即時碼的一類子碼.5. 1. 3 唯一可譯碼存在的充要條件(1) 對含有q個信源苻號的信源用含r個苻號的碼符號集進行編碼, 各碼字的碼長為11, 12,的唯一可譯碼存在的充要條件是,滿足 不等式?jīng)r1(2) 假設(shè)存在一組碼長為如以,的唯一可洋碼,那么一定存在具有相同碼長的即時碼. 所以,Kraft不等式也是即時碼存在的充要條件

4、.5. 1. 4唯一可譯碼的判斷法唯一可譯碼的判斷步驟:首先,觀察是否是非奇異碼.假設(shè)是奇異碼那么一定不是唯一可譯碼.其次,計算是否滿足不等式.假設(shè)不滿足一定不是唯一可譯碼.再次,將碼畫成一棵樹圖,觀察是否滿足即時碼的樹圖的構(gòu)造,假設(shè)灑足那么是唯一可譯碼.或用和設(shè)計的判斷方法：計并出分組碼中所有可能的尾隨后綴臬 合F,觀察F中有沒有包含任一碼字,假設(shè)無那么為唯一可譯碼；假設(shè)有那么 一定不是唯一可譯碼.上述判斷步驟中和設(shè)計的判斷方法是能確切地判斷出是否是唯一 可譯碼的方法,所以可以跳過前三個步驟直接采用該判 斷法.5. 1. 5漸近等分割性和£典型序列設(shè)離散無記憶信源-*=f F 1

5、A = 1LP3) Lpl,/>2,凡»-1其信息炳為H(S).它的N次擴展信源為SLPG),其中S' = GS,SG, a=(sw&n) (i = 1,2,尸； h ,2,i_N = L2,q).1. 漸近等分割性(AEP)假設(shè)隨機序列S百S.V是服從彼此統(tǒng)計獨立且等同分布 P(s),那么有一 §庇)=-點I."(呵免) 以概率收斂于H(S>2. e典型序列和£典型序列集<1)£典型序列N長的序列=(呵免叫)e SN,對于任意小的正數(shù)e,滿足 <e 即 _'畔宣)-H(S)| V那么稱此N長序列

6、a* 典型序列.反之.滿足lo(a,)- H(S) >e那么稱此 N 長序列ai為非8典型序列.(2)£典型序列集S、中所有E典型序列a,的集合為典型序列集.以Gx表示.S、'中所有非五典型序列Q,的 集合為非£典型序列集.以小表示,即G小=Qi： | H(S) V e« Gg =('a, J H(S)' >e i并且有G.n fl Gq = 0 U G.v = S'3. e典型序列集的特性(1)(2)假設(shè) at =(5m %)6 d 那么有2-nh?si v P(at) <C 2,v*h<s>&quo

7、t;1J當(dāng)N足修大時,那么有_p(Gn)>i-b p(Gg<s.為任意小的正數(shù))II Ga II W 2版mu其中II G* II表示集合G*中典型序列的個數(shù),(3)61) £典型序列的總數(shù)占信源序列的比值為S _ II II * 2-NkfnIICS>-t'5. 1. 6 無失真等長信源編碼定理離散信源S,其信息隔為 Hoc,用含r個字母的碼苻號集對 N長信 源苻號序列進行等長編碼,假設(shè)滿足2Hse(e>0的任蔥小數(shù)),那么當(dāng)N足 鍛大時,可實現(xiàn)幾乎無失真編碼.其中,當(dāng)S為離散無記憶信源時,Hoc(S);當(dāng)S為離散平穩(wěn)信源,Hoc為信源的極限墉；當(dāng)S

8、為馬爾可夫信源,Hs為馬爾可夫信源的極限炳.5. 1. 7 無失真變長信源編碼定理(香農(nóng)第一定理)用含I個字母的碼苻號臬對 N長信源符號序列進行變長編碼,總 能找到一種無失真的唯一可譯碼,使信源符號所需平均碼長滿足:1離散無記憶信源H.1 . U、H(S)2離散平穩(wěn)信源1 H(S】S25n) _、屁> _1_ H(S&SG logrN* N > N a logrN3離散馬爾可夫信源質(zhì)十函>甘2頑當(dāng)N = 1時.有ffiS) . 1>r>H<5) logr 十匕 M logr當(dāng)Nf 8時.有離散無記憶信源lim 理=弟魚=H,(S) nf Nlogr離

9、散平穩(wěn)和馬爾可夫信源hm與=iogr其中扣=$>3小,而人,是信源序列.,所對應(yīng)的碼字長度.所以E = E】 =史P恥又He為離散平穩(wěn)信源或馬氏信源 ? 的極策煽.5. 1. 8 無失真信源編碼定理和數(shù)據(jù)壓縮1. 無失真數(shù)據(jù)壓縮的極限值無失真信源編碼定理無論等長碼還是變長碼在理論上指出離散 信源的信息隔是信源無失真數(shù)據(jù)壓縮的極限值.在實際應(yīng)用上,變長碼與等長碼相比擬,當(dāng)N不很大時,變長碼 能更快地接近這極限值,更快地獲得較好的壓縮效果.無失真的信源數(shù)據(jù)壓縮是實現(xiàn)減少或消除信源的剩余度,所以在 工程實用 中又稱為冗余度壓縮編碼.通過無失真數(shù)據(jù)壓縮編碼可使信 道的信息傳輸率提升,提升了信息傳

10、輸系統(tǒng)的有效性到達(dá)信源與信 道的匹配,使信道得到充分利用.2, 編碼后信源信息率、碼率和編碼效率1編碼后信源信息率信源編碼后平均每個信源符號能載荷的最大信息, 即R,= iogr 等長碼R' = £|皿比特/信源符號V. V2碼率信源編碼后平均每個碼元攜帶的信息最即編碼后信道的信息傳輸率,即:等長碼的R = 黑比特/碼符號 Ln/Nijdx當(dāng)N=l,離散無記憶信源,有R =捋國 比特/碼符號3編碼效率衡量各種編碼距極限壓縮值的情況,即衡版各種編碼的優(yōu)劣,= 器=令=1£ 其中E= N為各種編碼的平均碼長當(dāng)N = 1.離散無記憶信源有n =譬魚=旦譽'Llog

11、r L4碼的剩余度碼的剩余度=1 萬當(dāng)r = 2即二元編碼時,有& =注意q是無單位的比值5. 1. 9最正確二天碼平均碼長為最短的即時碼稱為最正確碼又稱緊致碼.對于某個給定分布的離散信源,存在一個二天最正確碼,此碼滿足 如下性質(zhì)：1概 率大的信源符號所對應(yīng)的碼長不大于概率小的信源苻號所 對應(yīng)的碼長.2兩個最小概率的信源苻號所對應(yīng)的碼字 必具有 相同碼長.3兩個最小概率的信源苻號所對應(yīng)的碼字的差異,必與最后一位 碼元不同.對每一種信源編碼需掌握其編碼方法及其平均碼長的極限值苑圍o所討論的信源編碼方法都是針對離散無記憶信源的.對于離散平穩(wěn)信源只需將.N重概率空間看成無記憶信源進行編碼即可

12、.對于馬爾可夫信源,可考慮不同狀態(tài)下進行信源苻號編碼,壓縮 效果可得至U改善.5. 1. 10香農(nóng)()碼1. 編碼方法(1)確定信源符號所對應(yīng)的碼長= I log, pp-r 3 =1,2,q)其中符號r xi代表不小于的整數(shù)°依,心=1,2,q)用樹圖法構(gòu)造r元樹,可得廣元即時碼.2. 平均碼長的極限£(C)<logr5. 1. 11費諾()碼1. 編碼方法(r天費諾碼)(1) 將信源苻 號以概 率連減的次序排列.(2) 將它們劃分成r個組,使每組的概率和接近相同,并各賦予一 位碼元.(3) 再將每一組按同樣原那么劃分,重復(fù)步驟(2),直至各組不再可分 為止.這樣,

13、所對應(yīng)的碼符號序列那么為所編碼字.2, 平均碼長的極限E(C)華皇+2logr5. 1. 12霍夫曼()碼1. 編碼方法(r天霍夫曼碼)(1) 信源苻號個數(shù)q必須滿足(1)0(.表示縮減次數(shù)).不滿足時,設(shè) 一些概率為零的虛假苻號,使其滿足.當(dāng)2時,任怠整數(shù)q 一定滿足.(2) 將信源苻 號以概 率進減的次序排列.(3) 給r個概率最小的信源苻號各分配一位碼天,并將它們合并成 一個新苻號,r個最小的概率之和作為新苻號的概率,從而得到只包 含(1)個信源符號的新縮減信源S1.(4) 把縮減信源S1重新按概率遞減的次序排列(假設(shè)此時把所得的新 符號盡可能排列在靠前位置上,所得碼的方差最小),重復(fù)步

14、驟(3), 得只含2(1)個信源苻號的縮減信源S20(5) 以此繼續(xù),直至縮減信源只刺r個苻號為止.然后,從最后一 級縮減信源起,依編碼路徑向前返回,所得碼苻號序列就是所對應(yīng)的 碼字.2, 平均碼長的極限信源給定情況下,霍夫曼碼是最正確即時碼.其各碼字的碼長是唯 一的,但具體碼字不是唯一的.平均碼長的界限為平翌<E(C) W平立+】 logrlogr5. 1. 13 香農(nóng)-費諾-埃利斯碼1. 編碼方法(1) 將信源苻號al, a2,.,)依次排列(不要求以概率大小排序).H1(2) 計算出各信源符號的修正累積分布函數(shù)值. K(山)=E；p(4)+ *pcq.l-lL(3) 確定各信源符號

15、所對應(yīng)碼字的碼長：= Jog +1 (& =q)(4) 求出L F(a*)K)的二進數(shù),用這小數(shù)后的.位二進數(shù)作為符號S的碼字.(3, 表示取/位使小于等于1的數(shù).)2. 平均鈣長的極限此碼為二元即時碼.其有 H(S) + 1 < L(C) V H?S) +25. 1. 14游程編碼和編碼1.游程編碼()游程編碼是一種針對相關(guān)信源的有效編碼方法,尤其適用于二天 相關(guān)信源.有時實際工程技術(shù)中常將游程編碼和其他編碼方法混合使 用,能獲得更好的壓縮效果.信源輸出的字符序列中各種字符連續(xù)地重復(fù)出現(xiàn)而形成一段一段 的字符串,稱這種字符串的長度為游程,又稱游長.游程編碼就是將 信源字苻序列映

16、射成串的字苻、串的長度和串的位置的標(biāo)志序列.(1) 二天信源游程編碼編碼方法: 將一維二天序列中,分出一段一段的“0"苻號串和“1"符號串, 對應(yīng)段中的苻號個數(shù)標(biāo)記為“0游程長度L(0)和“1游程長度L(l). 對率的長度即游程長度用自然數(shù)標(biāo)記,并一般規(guī)定信源序列從 “0游程起始,所以二元信源序列總是“0游程和“ 1 游程交替出現(xiàn). 將二天信源序列映射成交替出現(xiàn)的表示游程長度的自然數(shù)序列 (即為對應(yīng)的游程長度的標(biāo)志序列).一般情況,對“0游程長度和“1游程長度也可分別編碼,建立各 自的碼字和碼表(如霍夫曼編碼).編碼效率(游程編碼和霍夫曼編碼)PiDo=HL(0)：| +

17、HL(l)：,一 HL(0)/p + HL(l)/中其中p0, pl為“0和“1苻號的概率.10和T1為游程長度為“o和“1 霍夫曼編碼效率.(2) 多天信源游程編碼將多天信源輸出的多天序列映射成一一對應(yīng)的標(biāo)志序列.一維多天信源序列需選用表示串的字符、串的長度的兩個標(biāo)志參二維多天信源序列需選用表示串的字符、串的長度及串的位置三 個標(biāo)志參涅'o2.編碼編碼是用于黑白二值文件 的數(shù)據(jù)壓縮碼.它是一維編碼方案. 它是游程編碼和霍夫曼碼相結(jié)合的一種標(biāo)準(zhǔn)的改良霍夫曼碼.根據(jù)“黑、“白的不同游程長度有兩張結(jié)尾碼(終端碼)表和兩張組 合碼(形成碼)表.(1) 編碼方法 游程長度在.63時,直接查表用

18、相應(yīng)的結(jié)尼碼為碼字. 游程長度在641728時,用組合碼加上結(jié)尾碼為相應(yīng)碼字. 規(guī)定每行從白游程開始,每行結(jié)束用結(jié)束碼(). 用于傳輸時,每頁文件開始第一數(shù)據(jù)前加一結(jié)束碼,每頁結(jié)尾 連續(xù)用6個結(jié)束碼.為了傳輸還要考慮實現(xiàn)同步的操作.(2) 平均碼長的極限值人職 /-W7J V方WB + 其中"W,叫為平均白、黑游程長度；P心Pb為白、黑像素出現(xiàn)的概率3wh是黑、白統(tǒng)計平均 后每個像素的墉值；品 是黑、白統(tǒng)計平均后每個像素所需二元碼的平均碼長.5. 1. 15算術(shù)編碼算術(shù)編碼是非分組碼,它從全信源序列出發(fā),考慮苻號之間的依 賴關(guān)系直接對信源苻號序列進行的編碼.算術(shù)編碼的主要概念是將信源

19、符號序列的累積分布函數(shù)和0, 1) 區(qū)間中的一個數(shù) C聯(lián)系起來,不同的信源苻號序列對應(yīng)于不同的無重 疊小 區(qū)間中 的數(shù).所以,這個碼是即 時碼.1.編碼方法(1)用逸推公式計算信源序列的累積分布函數(shù) F(s)和所對應(yīng)區(qū)間的寬度A(s):二元信源(廠= 0U)為多元信源為(F(sr) = F(s) + P(s)F.)F(m = F($)+P(s)F(Q：A(sr) = P(j)PCr>, A(sa*) = P(s)P(a»)其中信源符號累枳分布函數(shù)Fg 另P(q)(q心& A),而P是信源符號序列$的概 1-1率.卻于二元信源,可從二元整數(shù)來計算FW)FCs)=習(xí) P.)= S P(T)jro左= L-£p(y)=l S P(T)(2)確定信源