【文章內(nèi)容簡(jiǎn)介】 0，后綴碼字為 101， 故 ZZ(1)的編碼為 100101。 第 4章 熵保持編碼 同理，第 2個(gè)非零值 ZZ(2)的 NNNN/SSSS=0/2，故前綴碼字為 01，－ 2的反碼為 01，因此編碼為 0101。 同理，可得到 ZZ(4)的編碼為“ 11011， 10”， ZZ(8)的編碼為“ 111010， 1”。 第 4章 熵保持編碼 表 47 亮度交流系數(shù)碼表 第 4章 熵保持編碼 表 48 色度交流系數(shù)碼表 第 4章 熵保持編碼 ZZ(31)=1：由于 NNNN=31－ 8－ 1=2215，故先編碼ZRL=16，碼字為“ 11111111001”；此后有 NNNN=22－ 16=6，此時(shí)的 SSSS=1，故 NNNN/SSSS=6/1，前綴的編碼為“ 1111011”，－ 1的反碼為 0，后綴的編碼為 0，從而 ZZ(31)的編碼為“ 11111111001+1111011+0”。 此后無(wú)非零值，直接用 EOB結(jié)束本塊數(shù)據(jù)，編碼為“ 1010”。 原始碼流需要 8 8 8=512 bit，壓縮后碼流一共有 49 bit，壓縮比為 512∶ 49=∶ 1。 第 4章 熵保持編碼 Golomb編碼與通用變長(zhǎng)碼 一元碼 一元碼定義為非負(fù)整數(shù) n的一元碼為 n1個(gè) 1后跟 1個(gè) 0；或者為 n－ 1個(gè) 0后跟 1個(gè) 1。 按此定義，整數(shù) n的一元碼長(zhǎng)度是 n比特，如表 49所示。 第 4章 熵保持編碼 Golomb編碼 1966年提出一種編碼方法，可以使服從幾何分布的正整數(shù)數(shù)據(jù)流的平均碼長(zhǎng)最短，該方法無(wú)需使用Huffman編碼算法，而是直接給出最佳變長(zhǎng)碼。 設(shè)數(shù)據(jù)流中整數(shù) n出現(xiàn)的概率為 p(n)=(1－ p)n－ 1p, 0≤p≤1 (45) 求出滿足下式的 b值 (一定存在 ) (1－ p)b+(1－ p)b+1≤1(1－ p)b1+(1－ p)b (46) 得到 b值后，就可以按“前綴碼 +尾碼”的格式進(jìn)行整數(shù) n的 Golomb編碼。具體步驟如下： 第 4章 熵保持編碼 (1) 如果 b≠2k，前綴碼是 q+1位一元碼字， ， 為下取整函數(shù)；尾碼是對(duì) 的余數(shù) r=n－ 1－ qb的二進(jìn)制編碼， r∈ {0, 1, …, b－ 1}，余數(shù)前 個(gè)用 比特編碼，后面用 比特編碼，且最高位為 1。 (2) 如果 b=2k，前綴碼產(chǎn)生規(guī)則同 b≠2k時(shí)相同；尾碼則直接用 n的二進(jìn)制表示的最低 k位表示。這類特殊的 Golomb碼又叫做 G(k)。 第 4章 熵保持編碼 【 例 46】 給出 b=3， 4， 5時(shí)的 Golomb碼。 【 解 】 如果取 b=3，則可能的余數(shù)為 0、 2，第 1個(gè)余數(shù)用 1比特編碼，后面余數(shù)用 2比特編碼，高位為 1保持尾碼的前綴性，因此余數(shù)與尾碼的對(duì)應(yīng)關(guān)系為 0 0、 1 2 11； 而前綴碼根據(jù)編碼規(guī)則，對(duì)于 n=1, 2, … ，其前綴碼的位數(shù)分別為 1, 1, 1, 2, 2, 2， … 位。若取表 49右邊一列的一元碼字，則分別為 1, 1, 1, 01, 01, 01， … 。 ? ??第 4章 熵保持編碼 表 410 b=3, 4, 5和 n≤10的 Golomb碼字 第 4章 熵保持編碼 指數(shù) Golomb碼與通用變長(zhǎng)碼 相同前綴的 Golomb碼的信息表達(dá)能力主要在于尾碼?？墒菑谋?410可見(jiàn)，其尾碼長(zhǎng)度隨 n增長(zhǎng)緩慢，因?yàn)樗饕Q于 b。而所謂指數(shù) Golomb碼，可以讓同一個(gè)前綴下的Golomb碼字?jǐn)?shù)呈指數(shù)級(jí)增長(zhǎng)。本質(zhì)上，指數(shù) Golomb碼就是以 G(0)碼為前綴，再加上 q+m位尾碼 (或稱后綴 )，尾碼事實(shí)上就 q+m位二進(jìn)制碼。 q就是 G(0)碼中“ 0”的個(gè)數(shù) (均取“ 0…01” 形式的一元碼 )，而 m≥0則為指數(shù) Golomb的階數(shù)。此時(shí)，尾碼增加 1位，即 m增加 1，碼字?jǐn)?shù)就可以翻一番。 第 4章 熵保持編碼 指數(shù) Golomb碼已經(jīng)應(yīng)用在視頻編碼中，如在我國(guó)制定的 AVS(先進(jìn)音視頻編碼系統(tǒng) )標(biāo)準(zhǔn)中，就已經(jīng)采用 m階指數(shù)Golomb碼，如表 411所示。指數(shù) Golomb碼的優(yōu)勢(shì)在于硬件復(fù)雜度較低，可以根據(jù)閉合公式解析碼字，無(wú)需查表；還可以根據(jù)整數(shù) n的分布靈活選取或自適應(yīng)改變階數(shù) m，以達(dá)到較好的壓縮性能。對(duì)于指數(shù)哥倫布編碼，當(dāng) m和 q確定后，其編碼正整數(shù) n的范圍為［ 2q+m－ 2m, 2q+m+1－ 2m－ 1］。 第 4章 熵保持編碼 表 411 m階指數(shù) Golomb碼表 第 4章 熵保持編碼 由于 0階指數(shù) Golomb碼的前綴碼始終比其尾碼多 1位，如表 411階數(shù)為 0時(shí)所示，因此可以把 q位尾碼嵌入到 q+1位前綴碼中。這就是 ITU ( )甚低碼率視頻壓縮算法采用的通用變長(zhǎng)碼 (UVLC)，如表 412所示。可以看到， UVLC實(shí)質(zhì)上就是一種前后綴交織的 0階指數(shù) Golomb碼。 UVLC碼的優(yōu)點(diǎn)在于：同等碼長(zhǎng)的 UVLC碼它不僅“異字頭”，也是“異字尾”。因此，只要碼長(zhǎng)已知，如果正向譯碼出錯(cuò)，還可以反向譯碼。這樣降低了碼字的誤碼敏感性。 第 4章 熵保持編碼 表 412 UVLC碼的結(jié)構(gòu) 第 4章 熵保持編碼 【 例 47】 設(shè)有一信源的消息符號(hào)集為 0， 177。 1， 177。 2，177。 3， 177。 4， 177。 5，其出現(xiàn)概率對(duì)稱且單調(diào)下降，如圖 45所示。假設(shè)正負(fù)符號(hào)合在一起出現(xiàn)的概率為 ， ， ， ， 。求此信息源的 UVLC碼和 Huffman碼。 第 4章 熵保持編碼 圖 45 對(duì)稱單調(diào)下降概率分布 第 4章 熵保持編碼 【 解 】 可以按照表 412把這種符號(hào)映射到表 413所示的 UVLC碼。 采用 UVLC編碼的平均碼字長(zhǎng)度為 1 +3 +5 (+)+7 (+) = bit 表 413 此信源的 UVLC碼 第 4章 熵保持編碼 該信源也可以采用 Huffman編碼，碼表如 414所示。 采用 Huffman編碼的平均碼字長(zhǎng)度為 1 +3 +4 +5 +5 +6 + 7 = bit 表 414 此信源的 Huffman碼 第 4章 熵保持編碼 按照符號(hào)的出現(xiàn)概率計(jì)算出這種信源熵值為 比較起來(lái)， Huffman碼平均碼長(zhǎng) ()更接近于信源熵值， UVLC碼 ()比 Huffman碼稍差，但 UVLC碼的編解碼的復(fù)雜度比 Huffman碼低很多，實(shí)現(xiàn)更容易，因此在最新的視頻編碼標(biāo)準(zhǔn) ， UVLC碼也是熵編碼的選擇方案之一。 第 4章 熵保持編碼 算術(shù)編碼 算術(shù)編碼的起源 :香農(nóng)編碼 早在 1948年，香農(nóng)就提出將信源符號(hào)依其概率降序排序，用符號(hào)序列累計(jì)概率的二進(jìn)制表示作為對(duì)信源的編碼，并從理論上證明了它的優(yōu)越性。香農(nóng)編碼方法歸結(jié)如下： ① 設(shè)信源符號(hào)集共有 L個(gè)符號(hào)，按符號(hào)出現(xiàn)概率大小進(jìn)行排列，則 P(x1)≥P(x2)≥…≥ P(xL) 第 4章 熵保持編碼 ② 計(jì)算概率的累計(jì)分布