《信源編碼》PPT課件.ppt

《《信源編碼》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《信源編碼》PPT課件.ppt（70頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第 5 章 信源編碼,5.1 編碼的定義,5.2 無失真信源編碼,5.3 限失真信源編碼定理,5.4 常用信源編碼方法簡介,編碼,通信的實質(zhì)是傳輸信息，通信系統(tǒng)的性能指標(biāo)主,要有有效性、可靠性、安全性等，這些指標(biāo)正是信息,論研究的對象。編碼的目的是為了優(yōu)化通信系統(tǒng)，就,是使這些指標(biāo)達(dá)到最佳。,按不同的編碼目的，編碼分為三類：,信源編碼,信道編碼,安全編碼/密碼,信源編碼,信源編碼是以提高通信的有效性為目的編碼。,通常通過壓縮信源的冗余度來實現(xiàn)。,采用的一般方法是壓縮每個信源符號的平均比特,數(shù)或信源的碼率。同樣多的信息用較少的碼率來,傳送，使單位時間內(nèi)傳送的平均信息量增加，從,而提高通信的有效性

2、。,在不失真或允許失真的條件下，用,盡可能少的符號傳送信源信息。,信道編碼：, 是以提高信息傳輸?shù)目煽啃詾槟康牡木幋a。, 通常通過增加信源的冗余度來實現(xiàn)。采用的,一般方法是增大碼率/帶寬。,在信道受干擾的情況下增加信號的抗干,擾能力，同時又使得信息傳輸率最大。,密碼：,是以提高通信系統(tǒng)的安全性為目的的編碼。,通常通過加密和解密來實現(xiàn)。,無失真編碼,無失真信源編碼定理,信源編碼,限失真編碼,限失真信源編碼定理,無失真 ( 冗余度壓縮編碼 ) ：僅對信源的冗余度進(jìn)行,壓縮，不改變信源的熵。無失真編碼是可逆的，即當(dāng),信源符號變換成代碼后，可從代碼無失真地恢復(fù)出原,信源符號。只適用于離散信源。,限失真

3、 ( 熵壓縮編碼 ) ：在失真受限的情況下進(jìn)行限,失真編碼。在連續(xù)信源的情況下，由于信源的信息量,趨于無限，顯然不能用離散符號序列來完成無失真編,碼，而只能進(jìn)行限失真編碼。,離散信源,無失真信源編碼定理稱為第一極限定理,離散和連續(xù)信道,信道編碼定理稱為第二極限定理,限失真信源編碼定理稱為第三極限定理,連續(xù)信源,信源編碼的主要任務(wù),符號變換：使信源輸出符號與信道輸入符號匹配。,減少冗余，提高編碼效率。,針對信源輸出符號序列的統(tǒng)計特性，尋找一定的方,法把信源輸出符號序列變換為最短的碼字序列。,信源編碼的基本途徑,使序列中的各個符號盡可能地互相獨立，即解,除相關(guān)性，去冗余；,使編碼中各個符號出現(xiàn)的概

4、率盡可能地相等，,即概率均勻化。,本章討論離散信源編碼。首先從無失真編碼定理,出發(fā)，重點討論以香農(nóng)碼、費諾碼和霍夫曼碼為,代表的最佳無失真碼。,5.1 編碼的定義,信源編碼：信源輸出符號經(jīng)信源編碼器編碼后,轉(zhuǎn)換成另外的壓縮符號,無失真信源編碼：可精確無失真地復(fù)制信源輸,出的消息,編碼器的作用,將信源符號集 X 中的符號 變換成由碼,符號集 y 中的碼元 組成的長度為 Ki 的一,一對應(yīng)的碼字 。,碼字集合叫做代碼組Y；碼字 所含碼元的個數(shù)稱,為該碼字的碼長，記為 Ki 。,分組碼,將信源消息分成若干組，即符號序列，每個符號,序列依照固定碼表映射成一個碼字，這樣的碼稱,為

5、分組碼，有時也叫塊碼。只有分組碼才有對應(yīng),的碼表，而非分組碼中則不存在碼表。,例：,若將信源 X 通過二元信道傳輸，就必須把信源符,號ai 變換成由0 、 1符號組成的碼符號序列，這個,過程就是信源編碼。,定長碼,固定長度的碼，碼中所,有碼字的長度都相同。,變長碼,可變長度碼，碼中的碼字長短不一。,定長碼 變長碼,若 0 、 01 都是碼字，譯碼時如何分離？,分組碼 / 塊碼將信源符號集中的每個符號映射成一個固,定的碼字。分組碼必須具有某些屬性，才能保證在接,收端能夠迅速可靠地譯碼。,碼的不同屬性,碼表,信源符號,信源,出現(xiàn)概率 p(ai),符號 ai,碼 1,碼 2,碼 3,碼 4,a 1,

6、1/2,0,0,1,1,a 2,1/4,11,10,10,01,a 3,1/8,00,00,100,001,a 4,1/8,11,01,1000,0001,奇異碼,奇異碼和非奇異碼,1,若信源符號和碼字是一一對應(yīng)的，則該碼為非奇異,碼。反之為奇異碼。,,,,,,,,,唯一可譯碼,2,任意有限長的碼元序列，只能,被唯一地分割成一個個碼字。,例： 0,10,11 是一種唯一可譯碼。,任意一串有限長碼序列，如 100111000 ，只能被分割,成 10、0、11、10 、0、0 。任何其他分割法都會產(chǎn)生,一些非定義的碼字。,奇異碼不是唯一可譯碼,非唯一可譯碼,碼 2 ，可譯成 a1a1或a3,非奇異

7、碼,唯一可譯碼,碼 3 ， 但譯碼有延時,,非即時碼,唯一可譯碼,即時碼,非即時碼,接收端收到一個完整的碼字后，不能立即譯碼，還需,等下一個碼字開始接收后才能判斷是否可以譯碼。 碼 3,即時碼 ( 非延長碼 ) ( 異前綴碼 ),在譯碼時無需參考后續(xù)的碼符號就能立即作出判斷，,譯成對應(yīng)的信源符號。,碼 4,任意一個碼字都不是其它碼字的前綴部分,,碼 1,碼 2,碼 3,碼 4,ai,a1,0,0,1,1,a2,11,10,10,01,a3,00,00,100,001,a4,11,01,1000,0001,即時碼,奇異碼,非唯一 可譯碼,非即時碼,用碼樹來構(gòu)造碼字,碼樹從樹根開始向下長出 m 個

8、樹枝，成為 m 進(jìn)制,碼樹，樹枝代表碼元，樹枝與樹枝的交點叫做節(jié)點。,經(jīng)過 r 個樹枝才能到達(dá)的節(jié)點稱為 r 階節(jié)點。向下不長,出樹枝的節(jié)點稱為終端節(jié)點或端點。 m 進(jìn)制碼樹各節(jié),點 ( 包括樹根 ) 向下長出的樹枝不會超過m，若等于m稱,為滿樹 (整樹) ，否則稱為非滿樹 (非整樹 ) 。,碼樹上任一節(jié)點都對應(yīng)一個碼字，組成該碼字的,碼元就是從樹根開始到該節(jié)點所經(jīng)過的樹枝 ( 碼元 ) 。,若一個碼所有碼字均處于終端節(jié)點，則該碼為即時碼。,滿樹 等長碼,節(jié)數(shù) 碼長,非滿樹 變長碼,樹碼：若有 n 個信源符號，那么在碼樹上就要選擇 n,個終端節(jié)點，用相應(yīng)的 m 元基本符號表示這些碼字。,任一即

9、時碼都可用樹圖法來表示。,當(dāng)碼字長度給定，即時碼不是唯一的。,該碼樹從根到終端節(jié)點所經(jīng)路徑上，,每一個中間節(jié)點皆為碼字，因此碼 3,不是即時碼，但它是唯一可譯碼。,唯一可譯碼存在的充分和必要條件,各碼字的長度 K i 應(yīng)符合克勞夫特 (Kraft) 不等式：,m ：碼元進(jìn)制數(shù),n ：信源符號數(shù),Ki ：各個碼字的長度,例： 設(shè)二進(jìn)制碼樹中 X( a1, a2, a3, a4)，,K1 =1 ， K2 =2 ， K3 =2 ， K4 =3 。,應(yīng)用 Kraft 不等式，得：,不存在滿足這種 K i 的唯一可譯碼,要形成滿足上述長度 的碼字，必須在中間 節(jié)點放置碼字。,中間節(jié)點,如果將各碼字長度改

10、成：,存在唯一可譯碼,K1 =1 ， K2 =2 ， K3 =2 ， K4 =3 。,K1 =1 , K2 =2 , K3 =3 , K4 =3 。,注意,Kraft 不等式只是用來說明唯一可譯碼是,否存在，并不能作為唯一可譯碼的判據(jù)。,如碼字 0，10，010，111 雖然滿足 Kraft 不等式，,但它不是唯一可譯碼。,K1 =1 , K2 =2 , K3 =3 , K4 =3 。,5.2 無失真信源編碼,要求能夠無失真或無差錯地譯碼，同時希望所,得編碼的平均碼長最小。,對信源的 L 長符號序列進(jìn)行 m 進(jìn)制編碼，碼長 KL,只要可用的碼字?jǐn)?shù)不少于擴(kuò)展信源的符號數(shù)：,就可做到唯一譯碼,編碼

11、輸出碼,字的個數(shù),KL/L 是平均每個信源符號所需要的碼元符號個數(shù),編碼后平均每個信源符號能載荷的最大信息量為：,,5.2.1 定長編碼定理,在定長編碼中， K=KL 是定值，且為唯一可譯碼。,編碼的目的是尋找最小 K 值,若對信源進(jìn)行定長編碼，必須滿足:,對于定長唯一可譯碼，每個信源符號至少需用,（ log n / log m ）個碼符號來變換。,例: 英文電報符號， n =27 ， L =1 ， m =2( 二元編碼 ),log 2 n,K ,= log 2 27 5,每個英文電報符號至少,log 2 m,要用5位二元符號編碼,,實際英文電報符號信源，平均每個英文電報符號所,提供的信息量約

12、等于 1.4 比特，大大小于 5 比特。,定長編碼后每個碼字 (5個二元符號)只攜帶約1.4比特,信息量。定長編碼的信息傳輸效率極低,當(dāng)考慮信源符號出現(xiàn)的概率及符號間的依賴關(guān)系后,（考慮信源的冗余度），在定長編碼中每個信源符,號平均所需的碼長可以減少。,定長編碼定理給出了信源進(jìn)行定長編碼所需碼,長的理論極限值。,定長編碼定理,編碼器的平均輸出信息率,對于二進(jìn)制編碼，每個信源符號必須,輸出的碼長,定長編碼定理說明：,只要碼字所能攜帶的信息量大于信源序列輸出的,信息量，則可以使傳輸幾乎無失真，當(dāng)然條件是,L足夠大。,當(dāng) 時，不可能構(gòu)成無失真的編碼，也,就是不可能做一種編碼器，能使收端譯碼時

13、差,錯概率趨于零。,當(dāng) 時，則為臨界狀態(tài)，可能無失真，,也可能有失真。,差錯概率,設(shè)差錯概率用 Pe 表示，則有：, 為一正數(shù),為信源序列的自信息方差,當(dāng) 均為定值時，只要 L 足夠大， Pe可以小,于任一正數(shù)。即：,當(dāng)信源序列長度 L 滿足,能達(dá)到差錯率要求：,編碼效率,編碼效率總,定義編碼效率為：,是小于 1,信源的平均符號熵為 HL (X) ，采用平均符號碼長,為 K 來編碼后所得的效率。,最佳編碼效率：,編碼定理從理論上闡明了編碼效率接近 1 的理想編碼,器的存在性，它使輸出符號的信息率與信源熵之比接,近于 1 ，即：,若要實現(xiàn)，取無限長 L 的,信源符號進(jìn)行統(tǒng)一編碼

14、。,例： 設(shè)離散無記憶信源概率空間為,信源熵： H ( X ) = - p ( xi ) log p ( xi ) = 2.55 bit / 符號,i = 1,對信源符號采用定長二元編碼, 要求編碼效率為 90 ,若取 L 1 ，則,即每個符號用 2.83bit 進(jìn)行定長編碼，共有 22.83 =7.11 種,可能，按 7 種可能性計算，信源符號中就有一種符號,沒有對應(yīng)的碼字，取概率最小的 a8 ，則 Pe=0.04 , 太大,信源序列的自信息方差：,若要求譯碼錯誤概率 10-6,L 應(yīng)滿足：,對于定長編碼，即使在編碼效率和譯碼錯誤概率的要,求并不十分苛刻的情況下，就需要 10 8 個信源符

15、號一,起進(jìn)行編碼。這顯然是很難實現(xiàn)的。,5.2.2 變長編碼定理,在變長編碼中，碼長 KL是變化的。,根據(jù)信源各個符號的統(tǒng)計特性，如概率大的符號用,短碼，概率小的用較長的碼，使得編碼后平均碼長,降低，從而提高編碼效率。（統(tǒng)計匹配）,編碼后碼字 Y1 , Y 2 , , Y n 碼長分別為 K 1 , K 2 , , K n,碼的平均長度為：,編碼后的信息傳輸率為：,對于某一信源和某一碼符號集，若有一個唯一可譯,碼，其平均長度小于所有其他唯一可譯碼的平均長,度，則稱該碼為最佳碼（緊致碼）。,單個符號變長編碼定理,若離散無記憶信源的符號熵為 H(X) ，每個信源符號,用 m 進(jìn)制碼元進(jìn)行變長編碼，

16、一定存在一種無失真,編碼方法，其碼字平均長度 K 滿足下列不等式：,H ( X ),H ( X ), K <,+ 1,log m,log m,,,,,離散平穩(wěn)無記憶序列變長編碼定理,對于平均符號熵為 HL(X) 的離散平穩(wěn)無記憶信,源，必存在一種無失真編碼方法，使平均信息率R ,滿足不等式：,其中 為任意小正數(shù)。,無失真變長信源編碼定理（香農(nóng)第一定理）,對于平均符號熵為 HL(X) 的離散平穩(wěn)無記憶信源（離散,無記憶信源 X 的 L 次擴(kuò)展信源,對其進(jìn)行 m 元編碼，必存在一種無失真編碼方法，構(gòu),成唯一可譯碼，使信源 X 中每個信源符號所需的平均碼,長 滿足：,用變長編碼可達(dá)到相當(dāng)高的編

17、碼效率，一般所要求,的符號長度 L 可以比定長編碼小得多。,編碼效率的下界,為了衡量各種編碼方法與最佳碼的差距，定義碼的,剩余度為：,同前例：,設(shè)離散無記憶信源概率空間為,信源熵： H ( X ) = 2 . 55 bit / 符號,要求編碼效率為 90 ,用二進(jìn)制變長編碼， m 2,例： 設(shè)離散無記憶信源概率空間為,信源熵： H ( X ) = 1/4 log4 +3/4 log3/4 = 0. 811 bit / 信源符號,若用二元定長編碼 (0,1) 來構(gòu)造一個即時碼：,平均碼長： 二元碼符號 / 信源符號,編碼效率：,輸出的信息傳輸率：,再對長度 L 為 2 的信源序列進(jìn)行,變長編

18、碼，其即時碼如表：,碼字平均長度：,單個符號的平均碼長,編碼效率,輸出的信息傳輸率： R2 0.961bit/ 二元碼符號,信源序列的長度增加 :,編碼復(fù)雜一些，但信息傳輸率有了提高,變長編碼： L 2 ， 2 = 0.961,定長編碼：,要求編碼效率達(dá)到 96 時，允許譯碼錯誤概率 10 5,說明,(1) 定長碼需要的信源序列長，使碼表很大，且總存,在譯碼差錯。而用變長碼編碼時， L 不需要很大就可,達(dá)到相當(dāng)高的編碼效率，而且可實現(xiàn)無失真編碼。,(2) 隨著信源序列長度的增加，編碼的效率越來越接,近于 1 。編碼后的傳輸率 R 也越來越接近于無噪無損,二元對稱信道的信道容量 (1bit/

19、二元碼符號 ) ，達(dá)到信,源與信道的匹配。,最佳變長編碼,5.2.3,凡是能載荷一定的信息量，且碼字的平均長度最,短，可分離的變長碼的碼字集合稱為最佳變長碼。,編碼主要方法有：香農(nóng)編碼、費諾編碼、哈夫曼,編碼等。,僅哈夫曼編碼是真正意義下的最佳編碼,哈夫曼編碼效率最高，費諾編碼效率次之，香農(nóng),編碼效率最低，甚至低于定長編碼的效率。因此，香,農(nóng)編碼的實用價值不大，但卻有深遠(yuǎn)的理論意義，因,為按香農(nóng)的方法對信源序列編碼，當(dāng)序列長度趨于無,窮時，平均碼長會趨于信源的熵。,香農(nóng)（ Shannon ）編碼方法,1,香農(nóng)第一定理指出了平均碼長與信源之間的關(guān)系，同,時也指出了可以通過編碼使平均碼長達(dá)到極限值

20、。,香農(nóng)第一定理指出，選擇每個碼字的長度 K i 滿足下,式，就可以得到香農(nóng)碼：,二進(jìn)制香農(nóng)碼的編碼步驟,按信源符號的概率從大到小的順序排隊，不妨設(shè)：,1,確定滿足下列不等式的整數(shù)碼長 K i ：,2,令 p ( a0 )=0 ，計算第 i 個消息的累加概率 P i ：,3,將累加概率 Pi 變換成二進(jìn)制數(shù)，并取小數(shù)點后 Ki 位,4,作為符號 ai的編碼。,例： 有一單符號離散無記憶信源,對該信源編二,進(jìn)制香農(nóng)碼。,香農(nóng)碼的平均碼長,信源熵,編碼效率,為提高編碼效率，可把 x 4 x 5 換成前面的節(jié),點，可減小平均碼長。,不應(yīng)先規(guī)定碼長，而是由碼樹來規(guī)定碼,字，可得更好的結(jié)果。,例： 設(shè)信

21、源共 7 個符號消息，其概率如表所示：,費諾（ Fano ）編碼方法,概率匹配,2,按信源符號的概率從大到小的順序排隊，不妨設(shè)：,p ( a 1 ) p ( a 2 ) p ( a n ),按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接,近或相等。如編二進(jìn)制碼就分成兩組，編 m 進(jìn)制,碼就分成 m 組。,給每一組分配一位碼元。,將每一分組再按同樣原則劃分，重復(fù)步驟 2 和 3 ，,直至概率不再可分為止。,信源符號對應(yīng)的碼字即為費諾碼。,例： 對前例信源進(jìn)行二進(jìn)制費諾編碼。,費諾編碼的基本特點:,1) 費諾編碼在構(gòu)造碼樹時，是從樹根開始到終端節(jié),點結(jié)束；,2) 由于賦碼元時的任意性，因此編出的碼字

22、不唯一；,3) 費諾編碼雖屬于概率匹配范疇，但并未嚴(yán)格遵守,匹配規(guī)則，有時出現(xiàn)概率小的碼長反而小。因此,平均碼長一般不會最小。,費諾碼比較適合于每次分組概率都很接近的信源，特,別是對每次分組概率都相等的信源進(jìn)行編碼時，可達(dá),到理想的編碼效率。,例：,對該信源進(jìn)行二,進(jìn)制費諾編碼。,平均碼長：,編碼效率：,例：,二進(jìn)制費諾編碼,信源符號,概率,編碼,碼字,碼長,x 1,0.25,0,0,00,2,x 2,0.25,1,01,2,x 3,0.125,0,100,3,0,x 4,0.125,1,101,3,x 5,0.0625,0,1100,4,1,0,x 6,0.0625,1,1101,4,1,x

23、 7,0.0625,0,1110,4,1,x 8,0.0625,1,1111,4,平均碼長,K = 2 . 75 碼元 / 符號,每次所分兩組的,信源熵,H ( X ) = 2 . 75 bit / 符號,概率恰好相等。,H ( X ),編碼效率 =,= 1,K log 2,,,,,,,,,,,,,,,樹圖：,哈夫曼（ Huffman ）編碼方法,3,將信源符號按概率由大到小順序排隊,1,給兩個概率最小的符號各分配一個碼元，將其概率,2,相加后合并作為一個新的符號，與剩下的符號一,起，再重新排隊,給縮減信源中概率最小的兩個符號各分配一個碼元,3,4 重復(fù)步驟 2 、 3 直至概率和為 1,從

24、最后一級開始，向前返回得到各個信源符號所對,5,應(yīng)的碼元序列，即相應(yīng)的碼字。,例：,試對該信源編二進(jìn)制哈夫曼碼。,讀取碼字的時候，要從后向前讀，此,時編出來的碼字是可分離的即時碼。,平均碼長,信源熵,H(X) = H (0.2,0.19,0.18,0.17,0.15,0.1,0.01)=2.61 bit/ 符號,編碼效率,哈夫曼編碼的基本特點,1) 哈夫曼編碼在構(gòu)造碼樹時，是從端點開始直到樹,根結(jié)束；,2) 哈夫曼編碼采用概率匹配方法來決定各碼字長度，,概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)與長,碼，充分利用了短碼，從而使平均碼長最??；,3) 哈夫曼編碼時，縮減信源的最后二個碼字總是最,后一

25、位不同，從而保證了哈夫曼碼是即時碼。,費諾碼是從樹根開始，把各節(jié)點分給某子集，若子,集已是單點集，它就是一片樹葉而作為碼字。,哈夫曼編碼是先給每一符號一片樹葉，逐步合并成,節(jié)點直到樹根。,哈夫曼的編法并不惟一。,說明,每次對概率最小的符號分配 “0” 和 “1” 碼元是任意,的，所以可得到不同的碼字。只要在各次縮減信源,中保持碼元分配的一致性，即能得到可分離碼字。,不同的碼元分配，得到的具體碼字不同，但碼長 K i,不變，平均碼長也不變，所以沒有本質(zhì)區(qū)別。,縮減信源時，若合并后的新符號概率與其他符號概,率相等，從編碼方法上來說，這幾個符號的次序可,任意排列，編出的碼都是正確的，但得到的碼字不,

26、相同，不同的編法得到的碼字長度 K i 也不盡相同。,在哈夫曼編碼過程中，對縮減信源符號按概率由大,到小的順序重新排列時，應(yīng)使合并后的新符號盡可,能排在靠前的位置，這樣可使合并后的新符號重復(fù),編碼次數(shù)減少，使短碼得到充分利用。,m 進(jìn)制哈夫曼編碼,在編 m 進(jìn)制哈夫曼碼時，為了使短碼得到充分利用，,使平均碼長最短，必須使最后一步的縮減信源有 m 個,信源符號。,縮減次數(shù),每次縮減所減少,的信源符號個數(shù),信源符號數(shù) n 應(yīng)滿足：,不滿足時：設(shè)q個概率為 0 的信源符號，使q+n 滿足要求,第一次對最小概率符號分配碼元時只取 (m-q) 個，分別,配以 0,1,, m-q-1 ，把這些符號的概率相

27、加作為一個新,符號的概率，與其它符號一起重新排列。以后每次取,m 個符號，分別配以 0,1,, m-1；如此下去，直至所有,概率相加得 1 為止，即得到各符號的 m 進(jìn)制碼字。,,,單符號離散無記憶信源，,例,試對該信源編三進(jìn)制哈夫曼碼。,m =3 ， n =8,無法滿足 n = s ( m -1) + m,s =3 ， q =1,q + n = s ( m -1) + m,第一次取 m - q =2 個符號進(jìn)行編碼,,平均碼長,信息傳輸率,編碼效率,香農(nóng)碼、費諾碼、哈夫曼碼都考慮了信源的統(tǒng)計特,性，使經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字，使平,均碼長縮短，從而實現(xiàn)了對信源的壓縮；,香農(nóng)碼有系統(tǒng)的

28、、惟一的編碼方法，費諾碼和哈夫,曼碼的編碼方法都不惟一；,費諾碼比較適合于對分組概率相等或接近的信源編,碼，費諾碼也可以編 m 進(jìn)制碼，但 m 越大，信源的符,號數(shù)越多，可能的編碼方案就越多，編碼過程就越,復(fù)雜，有時短碼未必能得到充分利用；,哈夫曼碼對信源的統(tǒng)計特性沒有特殊要求，編碼效,率比較高，對編碼設(shè)備的要求也比較簡單，因此綜,合性能優(yōu)于香農(nóng)碼和費諾碼。,5.3 限失真信源編碼定理,設(shè)離散無記憶信源 X 的信息率失真函數(shù)為 R (D) ，, 當(dāng)信息率 R R (D) 時，只要信源序列長度 L 足,夠長，一定存在一種編碼方法，其譯碼失真小,于或等于 D+，為任意小的正數(shù)；, 反之，若 R R

29、 (D) ，則無論采用什么樣的編碼方,法，其譯碼失真必大于 D 。,如是二元信源，則對于任意小的 0 ，每一個信,源符號的平均碼長滿足如下公式：,5.4 常用信源編碼方法簡介,5.4.1 游程編碼,游程：數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。,在二元序列中，連 0 段稱為 0 游程，連 1 段稱為 1 游程,游程長度序列 / 游程序列：用交替出現(xiàn)的 “0” 游程,和 “1” 游程長度表示任意二元序列。,游程變換：是一種一一對應(yīng)的變換，也是可逆變換。,游程序列： 3113213,二元序列： 000101110010001,若已知二元序列以 0 起始，從游程序列很容易恢復(fù)成,原來的二元序列。,游程變換

30、將二元序列變換成了多元序列；這樣,就適合于用其他方法，如哈夫曼編碼，進(jìn)一步,壓縮信源，提高通信效率。,編碼方法：, 首先測定 “0” 游程長度和 “1” 游程長度的概率,分布，即以游程長度為元素，構(gòu)造一個新的,信源；, 對新的信源 ( 游程序列 ) 進(jìn)行哈夫曼編碼。,5.4.2 算術(shù)編碼,算術(shù)編碼是近十多年來發(fā)展迅速的一種無失真信源,編碼，它與最佳的哈夫曼碼相比，理論性能稍加遜,色，而實際壓縮率和編碼效率卻往往還優(yōu)于哈夫曼,碼，且實現(xiàn)簡單，故很受工程上的重視。,算術(shù)編碼不同于哈夫曼碼，它是非分組 ( 非塊 ) 碼。它,從全序列出發(fā)，考慮符號之間的關(guān)系來進(jìn)行編碼。,算術(shù)編碼利用了累積概率的概念。,算術(shù)碼主要的編碼方法是計算輸入信源符號序列所,對應(yīng)的區(qū)間。,