1、區間編碼是如何工作的
區間編碼概念上要把所有的訊息符號都編碼成一個數字,這與哈夫曼編碼為每個符號賦予一個位組合格式並且將所有這些位組合格式連線到一起不同。這樣區間編碼能夠實現比哈夫曼編碼一個符號一位這個上限還要高的壓縮率,並且它沒有哈夫曼編碼處理機率不為 2 的倍數時的效率問題。
區間編碼的核心概念是:對於給定的一個範圍足夠大的整數區間以及符號的機率估計,最初的區間很容易切分成與所表示的符號機率成比例的子區間。將當前區間切分成與下一個待編碼符號的機率對應的子區間,通過這種方法就可以對訊息中的每個符號進行編碼。解碼器必須與編碼器有同樣的機率估計,這種機率估計可以事先傳送過去、從已經傳送的數據導出或者作為壓縮器或者解壓器的一部分。
當所有的符號已經編碼完成後,僅僅用子區間就可以表示整個信息(當然我們假定解碼器提取了整個訊息之後通過某種方式得到)。單個的整數實際上已經足夠表示子區間,並且可能不需要傳輸整個的整數;如果有這樣一個數字序列,即每個整數的前綴都落在某個子區間,那么前綴本身就已經足夠標識字區間並且傳輸訊息。
1.1、例子
假設我們打算編碼訊息“AABA<EOM>”,其中 <EOM> 是訊息結束符。對於這個例子來說,假設編碼器知道我們打算用十進制數表示,也知道最初的區間是 [0, 100000) 並且頻率是 {A: .60; B: .20; <EOM>: .20},第一個符號將 [0, 100000) 分成三個子區間:
A: [ 0, 60000)
B: [ 60000, 80000)
<EOM>: [ 80000, 100000)
由於第一符號是 A,所以最初的區間縮減為 [0, 60000)。第二個符號再次將這個區間分成三個子區間,跟在已經編碼的 'A' 後面表示:
AA: [ 0, 36000)
AB: [ 36000, 48000)
A<EOM>: [ 48000, 60000)
兩個符號編碼之後,區間變成 [000000, 036000),第三個符號得到下面的結果:
AAA: [ 0, 21600)
AAB: [ 21600, 28800)
AA<EOM>: [ 28800, 36000)
這一次第二段表示我們要編碼的訊息,這樣區間就變成了 [21600, 28800)。在這種情況下看起來確定子區間變得困難了一些,實際上並非如此:我們可以直接用上限減去下限得到 7200,它最前面的 4320 區間是它的 .60,後面的 1440 區間表示隨後的 .20,剩餘的 1440 表示剩餘的 .20,然後加上下限得到區間:
AABA: [21600, 25920)
AABB: [25920, 27360)
AAB<EOM>: [27360, 28800)
最後,區間縮小到 [21600, 25920),我們還有一個符號要進行編碼。與前面一樣我們區間進行切分得到:
AABAA: [21600, 24192)
AABAB: [24192, 25056)
AABA<EOM>: [25056, 25920)
由於 <EOM> 是最後一個符號,所以最後的區間就是 [25056, 25920)。因為以“251”開頭的五位整數都落在最後的區間內,這樣任何一個三位前綴在這個範圍的整數都能夠明確地傳達原始信息。存在八個這樣的前綴這個事實暗示效率仍然不是最高的,這是由於我們使用十進制而不是二進制整數引起的。
這樣看起來主要問題就是我們要選擇一個足夠大的區間,這樣不管需要編碼多少符號我們都有足夠大的區間使得子區間不為 0。但是,實際上這不是一個問題,因為編碼器不是從一個非常大的區間開始不斷減小這個區間,編碼器在任何時刻都只在一個更小的區間工作。在編碼一定熟練的數位之後,最左面的數位不再變化。在這個例子中編碼三個符號之後,我們就已經知道結果將以“2”開始。隨著更多數位從右側進來,左側的數位將不斷發送出去。
2、與算術編碼的關係
算術編碼與區間編碼一模一樣,但是它用分數取代了整數。這些分數有一個隱含的公分母,這樣所有的分數都落在 [0,1) 區間。因此,算術編碼結果都解釋為以一個隱含的“0”開始。由於這是同樣的編碼方法的不同解釋,並且由於算術編碼與區間編碼的結果相同,所以算術編碼器都是與之對應的區間編碼器,反之亦然。換句話說就是,算術編碼與區間編碼是對於同一事物稍微不同的兩種理解方法。
但是,實際套用中區間編碼器傾向於使用 Martin 論文(參見 )中描述的實現方法,然而算術編碼通常也不叫作區間編碼。類似的區間編碼器經常提及的一個特性是每次正規化(renormalization)一個位元組,而不是每次一位。換句話說,區間編碼傾向於使用位元組而不是位作為編碼數碼。儘管這會稍微地減小壓縮的比率,但是比每次正規化一位的速度要快很多。
相關詞條
-
算術編碼
算術編碼,是圖像壓縮的主要算法之一。 是一種無損數據壓縮方法,也是一種熵編碼的方法。和其它熵編碼方法不同的地方在於,其他的熵編碼方法通常是把輸入的訊息分...
編碼方法 工作原理 編碼過程 概述 相關介紹 -
信息編碼
信息編碼,(InformationCoding)是對原始信息符號按一定的數學規則所進行的變換。是為了方便信息的存儲、檢索和使用,在進行信息處理時賦予信息...
詳細概述 目的 基本原則 代碼類型 系統設計 -
變換編碼
變換編碼,是從頻域的角度減小圖像信號的空間相關性,它在降低數碼率等方面取得了和預測編碼相近的效果。進入80年代後,逐漸形成了一套運動補償和變換編碼相結合...
發展歷程 簡介 核心 -
計算機編碼
計算機編碼指電腦內部代表字母或數字的方式.常見的編碼方式有:ASCII編碼,GB2312編碼(簡體中文),GBK,BIG5編碼(繁體中文),ANSI編碼...
基本信息 編碼分類 -
預測編碼
預測編碼是根據離散信號之間存在著一定關聯性的特點,利用前面一個或多個信號預測下一個信號進行,然後對實際值和預測值的差(預測誤差)進行編碼。
預測編碼方法 PCM DPCM ADPCM 幀間預測編碼 -
區間信號系統
"區間信號系統"是鐵路部門為了保證列車在車站與車站之間的“區間”運行時的絕對安全所必須的技術裝備,也稱自動閉塞。
簡介 發展 分類 -
小區間干擾消除
小區間干擾消除的原理,是對干擾小區的干擾信號進行某種程度的解調甚至解碼,然後利用接收機的處理增益從接收信號中消除干擾信號分量。在LTE早期研究中,考慮過...
-
區間信號與列車運行控制系統
版次:1 頁數:334 開本:16開
圖書信息 內容簡介 -
線路編碼
線路編碼作用是消除或減少數字電信號中的直流和低頻分量,以便於在光纖中傳輸、接收及監測。
基本內容 基本簡介 方案 比較