[工學(xué)]第8章無(wú)失真的信源編碼(編輯修改稿)
2025-02-15 12:05 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 非全樹時(shí)，有 s個(gè)碼字不用： ? 第一次對(duì)最小概率符號(hào)分配碼元時(shí)就只取 (m－ s)個(gè)，分別配以 0,1,…, m－ s－ 1，把這些符號(hào)的概率相加作為一個(gè)新符號(hào)的概率，與其它符號(hào)一起重新排列。 ? 以后每次就可以取 m個(gè)符號(hào)，分別配以 0,1,…, m－1； … ；如此下去，直至所有概率相加得 1為止，即得到各符號(hào)的 m進(jìn)制碼字。 第七節(jié) 霍夫曼編碼 —— m進(jìn)制哈夫曼編碼 例：對(duì)如下單符號(hào)離散無(wú)記憶信源 (例 )編三進(jìn)制哈夫曼碼。 這里： m=3， n=8 ? 令 k=3， m+k(m－ 1)=9，則 s=9－ n=9－ 8=1 ? 所以第一次取 m－ s=2個(gè)符號(hào)進(jìn)行編碼。 1 2 3 4 5 6 7 8, , , , ,( ) 0 . 4 0 . 1 8 0 . 1 0 . 1 0 . 0 7 0 . 0 6 0 . 0 5 0 . 0 4X x x x x x x x xPX? ? ? ?? ????? ? ? ?第七節(jié) 霍夫曼編碼 —— m進(jìn)制哈夫曼編碼 第七節(jié) 霍夫曼編碼 —— m進(jìn)制哈夫曼編碼 ? 平均碼長(zhǎng)為： ? 信息率為： ? 編碼效率為： ? 可見：哈夫曼的編碼效率相當(dāng)高，對(duì)編碼器的要求也簡(jiǎn)單得多。 511( ) 0 . 4 1 ( 0 . 1 8 0 . 1 0 . 0 7 0 . 0 6 ) 2 ( 0 . 0 5 0 . 0 4 ) 3 1 . 6 9 ( /)iiiK p x k?? ? ? ? ? ? ? ? ? ? ? ?? 比特 符號(hào)221 . 6 9l o g 3 l o g 3 2 . 6 8 ( / )1KRL? ? ? 比特 符號(hào)( ) 2 .5 5 9 5 .2 %2 .6 8HXR? ? ? ?一些結(jié)論 ? 香農(nóng)碼、費(fèi)諾碼、哈夫曼碼都考慮了信源的統(tǒng)計(jì)特性，使經(jīng)常出現(xiàn)的信源符號(hào)對(duì)應(yīng)較短的碼字，使信源的平均碼長(zhǎng)縮短，從而實(shí)現(xiàn)了對(duì)信源的壓縮； ? 香農(nóng)碼有系統(tǒng)的、惟一的編碼方法，但在很多情況下編碼效率不是很高； ? 費(fèi)諾碼和哈夫曼碼的編碼方法都不惟一； ? 費(fèi)諾碼比較適合于對(duì)分組概率相等或接近的信源編碼； ? 哈夫曼碼對(duì)信源的統(tǒng)計(jì)特性沒有特殊要求，編碼效率比較高，對(duì)編碼設(shè)備的要求也比較簡(jiǎn)單，因此綜合性能優(yōu)于香農(nóng)碼和費(fèi)諾碼 。 第八節(jié) 游程編碼、算術(shù)編碼 ? 香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼主要是針對(duì)無(wú)記憶信源。當(dāng)信源有記憶時(shí)上述編碼效率不高； ? 游程編碼對(duì) 相關(guān)信源 編碼更有效； ? 香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼屬于 無(wú)失真信源編碼 ； ? 游程編碼屬于 限失真信源編碼 。 第八節(jié) 游程編碼、算術(shù)編碼、冗余編碼 ? 游程 ：數(shù)字序列中連續(xù)出現(xiàn)相同符號(hào)的一段。 ? 二元序列的游程：只有“ 0”和“ 1”兩種符號(hào)。 ? 連“ 0”這一段稱為“ 0”游程，它的長(zhǎng)度稱為 游程長(zhǎng)度 L(0)； ? 連“ 1”這一段稱為“ 1”游程，它的游程長(zhǎng)度用 L(1)表示。 游程編碼 ① 二元獨(dú)立序列游程長(zhǎng)度概率 ? 若規(guī)定二元序列總是從“ 0”開始。 ? 對(duì)于隨機(jī)序列，游程長(zhǎng)度是隨機(jī)的其取值可為 1,2,3,… ，直至無(wú)窮。 ? 游程長(zhǎng)度序列 /游程序列：用交替出現(xiàn)的“ 0”游程和“ 1”游程長(zhǎng)度表示任意二元序列。 ? 游程變換 ：是一種一一對(duì)應(yīng)的變換，也是可逆變換。 例如：二元序列： 000101110010001… ，可變換成如下游程序列： 31132131 第八節(jié) 游程編碼、算術(shù)編碼、冗余編碼 ? 游程變換減弱了原序列符號(hào)間的相關(guān)性。 ? 游程變換 將二元序列變換成了多元序列 ；這樣就適合于用其他方法，如哈夫曼編碼，進(jìn)一步壓縮信源，提高通信效率。 ? 編碼方法： ? 首先測(cè)定“ 0”游程長(zhǎng)度和“ 1”游程長(zhǎng)度的概率分布，即以游程長(zhǎng)度為元素，構(gòu)造一個(gè)新的信源 ； ? 對(duì)新的信源（游程序列）進(jìn)行哈夫曼編碼。 游程編碼 第八節(jié) 游程編碼、算術(shù)編碼、冗余編碼 ② 二元獨(dú)立序列游程長(zhǎng)度的熵 ? 若二元序列的概率特性已知，由于二元序列與游程變換序列的一一對(duì)應(yīng)性，可計(jì)算出游程序列的概率特性。 ? 令“ 0”和“ 1”的概率分別為 p0和 p1，則“ 0”游程長(zhǎng)度 L(0)的概率為 p[L(0)]=p0L(0)－ 1p1 式中 L(0)=1,2,…, ? 在計(jì)算 p[L(0)]時(shí)必然已有“ 0”出現(xiàn)，否則就不是“ 0”游程，若下一個(gè)符號(hào)是“ 1”，則游程長(zhǎng)度為 1，其概率是 p1 =1－ p0；若下一個(gè)符號(hào)為“ 0”、再下一個(gè)符號(hào)為“ 1”，則游程長(zhǎng)度為 2，其概率將為 p0p1 ；依此類推。 游程編碼 第八節(jié) 游程編碼、算術(shù)編碼、冗余編碼 游程編碼 ? 游程長(zhǎng)度至少是 1，理論上，游程長(zhǎng)度可以是無(wú)窮，但很長(zhǎng)的游程實(shí)際出現(xiàn)的概率非常小。 ? 同理可得“ 1”游程長(zhǎng)度 L(1)的概率為： P[L(1)]=p1L(1)1p0 ? “0”游程長(zhǎng)度的熵： 02( 0 ) 1 1()[ ( 0 ) ] [ ( 0 ) ] l o g [ ( 0 ) ]LHpH L p L p Lp??? ? ??第八節(jié) 游程編碼、算術(shù)編碼、冗余編碼 ③ 二元獨(dú)立序列的平均游程長(zhǎng)度 ? “ 0”游程序列的平均游程長(zhǎng)度 ? 同理可得“ 1”游程長(zhǎng)度的熵和平均游程長(zhǎng)度 ( 0 ) 10 0 1( 0 ) 1 ( 0 ) 1( 0 )10( 0 ) 1 011 2 3 4[ ( 0 ) ] ( 0 ) [ ( 0 ) ] ( 0 )1( 1 ) 1LLLLLl E L L p L L p pdppd p px x x x x????????? ? ???? ? ? ? ? ? ????0100() 1[ ( 1 ) ] [ ( 1 ) ]HpH L l E Lpp? ? ?游程編碼 第八節(jié) 游程編碼、算術(shù)編碼、冗余編碼 游程編碼 ④ 二元獨(dú)立序列的熵 ? “ 0”游程序列的熵與“ 1”游程長(zhǎng)度的熵之和除以它們的平均游程長(zhǎng)度之和，即為對(duì)應(yīng)原二元序列的熵 H(X) ? 游程變換后符號(hào)熵沒有變。因?yàn)橛纬套儞Q是一一對(duì)應(yīng)的可逆變換，所以變換后熵值不變。 0101[ ( 0 ) ] [ ( 1 )
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1