- 相關(guān)推薦
對于緊致碼在三種編碼方法下的編碼特性研究
摘要:本文針對一種被稱為緊致碼的特殊的信源空間分布,基于Shannon,F(xiàn)ano和Huffman三種編碼方法,并分別對其進(jìn)行了證明,發(fā)現(xiàn)對于某種特殊的信源分布的緊致碼,平均碼長與其信源概率分布有關(guān)。同時(shí)通過引入Huffman tree構(gòu)造方法證明了Huffman編碼方法的情況,簡化了對于這種特殊的信源分布的緊致碼編碼過程。
關(guān)鍵詞:緊致碼;Fano;Huffman;Huffman tree;Shannon
一、引言
21世紀(jì),國際社會已進(jìn)入信息化時(shí)代。信息論作為信息科學(xué)和技術(shù)的基本理論,猶如信息科學(xué)大廈的地基,在信息社會中占據(jù)越來越重要的地位。信息論的創(chuàng)始人Shannon,他在 1949 年發(fā)表了《保密通信的信息理論》,是每一位研究信息學(xué)者必讀的一篇文章[1]。隨著信息技術(shù)的發(fā)展, 編碼技術(shù)已經(jīng)在媒體技術(shù)、網(wǎng)絡(luò)技術(shù)、無線通信技術(shù)、數(shù)字電視技術(shù)等方面得到廣泛應(yīng)用[2]。信息論、錯誤控制編碼和密碼學(xué)是現(xiàn)在數(shù)字通信系統(tǒng)中的三大支柱。信息論基礎(chǔ)是應(yīng)用概率論、隨機(jī)過程和近世代數(shù)等方法研究信息的存儲、傳輸和處理中一般規(guī)律的學(xué)科,主要解決通信過程中信息傳輸?shù)挠行、可靠性與安全性的問題,是信息科學(xué)和通信科學(xué)領(lǐng)域中的一門基礎(chǔ)理論[3,4]。
信息論將信息的傳遞作為一種統(tǒng)計(jì)現(xiàn)象來考慮,給出了估算通信信道容量的方法。信息傳輸和信息壓縮是信息論研究中的兩大領(lǐng)域。緊致碼在信息論的研究中有著至關(guān)重要的作用,并且具有重大實(shí)際意義。
本文的目的是用信息論觀點(diǎn)對緊致碼進(jìn)行若干研究,以Shannon,F(xiàn)ano和Huffman三種編碼方法為例,分別介紹它們的編碼原理以及相關(guān)證明,進(jìn)一步得出結(jié)論。
二、緊致碼
這里我們介紹一種特殊的信源分布,如果其中各消息概率滿足pi
其中hi為任意正整數(shù),對信源進(jìn)行二進(jìn)制編碼,該編碼為最佳編碼,或者說獲得碼是緊致碼[5]。
編碼效率。
式中H(X)=-∑pilog2pi為信源熵,r為碼符號數(shù),這里考慮二進(jìn)制編碼,r=2,為編碼后平均碼長,定義表達(dá)式為。
從平均碼長的角度出發(fā),對于給定信源,使平均碼長達(dá)到最小的編碼方法,稱為最佳編碼,得到的碼稱為最佳碼,即緊致碼。
本文考慮信源的每個消息的概率滿足,信源消息編碼后的碼長為ni=hi,則編碼效率為
下面我們將對上述結(jié)論進(jìn)行證明。
三、三種編碼法及其證明
3.1 對于Shannon編碼的證明
首先介紹Shannon編碼方法。步驟如下:
(1)將信源發(fā)出的M個消息,按其概率遞減順序進(jìn)行排列,得
P(x1)≥p(x2)≥…≥p(xM)
(2)計(jì)算出各消息的-logp(xm)值,m=1,2,…M;
(3)根據(jù)-logp(xm)≤nm<-logp(xm)+1。(-logp(xm)為整數(shù)時(shí)取等號),計(jì)算出每個消息的二進(jìn)制代碼的長度nm(m=1,2,…,M),nm,nm取正整數(shù);
(4)為得到唯一可譯碼,計(jì)算出第m個消息的累加概率,再將pm變換成二進(jìn)制小數(shù),取小數(shù)點(diǎn)后面nm位作為第m個消息的代碼組(碼字)。
然后我們考慮上面介紹的緊致碼。記離散信源,其中滿足,對其進(jìn)行Shannon編碼[6],由第三步可知,任一信源xi其對應(yīng)的二進(jìn)制代碼長度nm=-logp(xm)=hi,這就是我們要證明的對緊致碼進(jìn)行Shannon編碼后每個信源對應(yīng)的碼長為hi。
3.2 對于Fano編碼的證明
對Fano編碼的思路與Shannon編碼類似。首先介紹Fano編碼方法[7]。步驟如下:
(1)信源發(fā)出的M個消息,按其概率遞減順序排列,得
P(x1)≥p(x2)≥…≥p(xM)
把消息集{x1,x2,…xM}按其概率大小分解成兩個子集,使兩個子集的概率之和盡可能相等,把第一個子集編碼為0,第二個子集編碼為1,作為代碼組的第一個碼元;
(2)對子集做第二次分解,同樣分解成兩個子集,并使兩個子集概率之和盡可能接近相等,再把第一個子集編碼為0,第二個子集編碼為1,作為第二個代碼組的碼元;
(3)如此一直進(jìn)行下去,直到各子集僅含一個消息為止;
(4)將逐次分解過程中得到的碼元排列起來就是各消息代碼。
下面證明作上述操作后得到的每個消息對應(yīng)的碼長為hi。
由上述步驟可知,經(jīng)過n次分解后得到的消息xi其對應(yīng)的碼長一定為n,于是問題轉(zhuǎn)為證明對應(yīng)概率為的消息需要hi次分解后得到的子集僅含該消息。為簡便,以下將把某個消息經(jīng)過分解后得到的子集僅含該消息簡稱為將該消息分出來。
由Fano編碼步驟可知,進(jìn)行第n次分解,會得到2n個子集,其中每個子集中所包含消息概率和為2-n,現(xiàn)在考慮第hi次分解,將會得到個子集,其中每個子集中所包含的消息概率和為,可知概率為的消息將會在本次分解中被分出來。也即概率為的消息將在第hi次分解中被分出來。
由上述可知對于緊致碼用Fano編碼法進(jìn)行編碼后每個信源對應(yīng)的碼長也為hi。
3.3 對于Huffman編碼的證明
同樣首先引出Huffman編碼[8]。將信源符號按概率遞減的次序排列;
(1)將概率最小的兩個符號連在一起。將這兩個符號的概率之和寫在他們的結(jié)合節(jié)點(diǎn)上。將這兩個分別標(biāo)記為0和1;
(2)將這兩個概率和看作一個新符號的概率。重新排列信源符號,并將概率最小的兩個信源符號,將他們綁定在一起構(gòu)成一個新的概率。每一次我們把兩個符號結(jié)合在一起是符號總數(shù)減1。每當(dāng)把兩個概率結(jié)合在一起時(shí),總是把兩個分支標(biāo)記為0和1;
(3)將此過程繼續(xù)下去直至只剩一個概率,就完成了Huffman樹的構(gòu)造;
(4)對于任意符號的碼字,找到從最后節(jié)點(diǎn)到該符號的一個路徑,反向追蹤路徑并讀出分支的碼字,即為該符號的碼字。
下面開始證明。
首先我們考慮最特殊也是最理想的一種情況,信源概率分布如表1所示,
對于這種信源分布顯然每個信源編碼后的碼長為hi。
上述討論的概率分布是對于的概率分布最特殊也是最基本的情況,一切其他的情況都是有此種情況轉(zhuǎn)化而來。換句話說任何概率分布為的概率均可以轉(zhuǎn)化為從2-1,2-2,一直排到2-M+1,2-M+1的排列。下面我們考慮這種序列所具有的特性,可得出如下結(jié)論:
對于一個信源空間X,其概率分布為
其中hi為任意正整數(shù)。將其按概率降序排列為
p1≥p2≥…≥pM
其中M為消息個數(shù)。那么其最小的兩個概率和必定是相等的。舉個簡單例子,概率從大到小為1/2,1/4,1/8,1/16,1/16。如果只有一個1/16,那么前三項(xiàng)加起來應(yīng)該是15/16,但前面三項(xiàng)中最小的也是1/8,怎么相加都不會加到15/16。
下面用反證法進(jìn)行證明。
假設(shè)有pM-1>pM即hM-1 現(xiàn)在回到Huffman方法。由上面的結(jié)論可知,對于上述的一個信源空間進(jìn)行Huffman編碼,每一次合并重排后,最下面的兩個信源符號,也就是概率最小的兩個信源的概率一定是相等的。因?yàn)槊恳淮魏喜⒅嘏藕,原信源空間會形成一個新的信源空間,原來概率最小的兩個信源符號合并成一個新的信源符號,也就是說形成一個新的概率分布,由于相加的兩個概率相等,則相加得到的新的概率仍然滿足p=2-h,也就是說新的概率分布仍然滿足,則同樣滿足結(jié)論。這個結(jié)論當(dāng)我們引入Huffman tree的概念后對證明就會變得極其有用。
下面先介紹一些樹的基本概念,然后引出Huffman tree的概念。
(1)路徑和路徑長度。在一棵樹中,從一個結(jié)點(diǎn)往下可以達(dá)到的孩子或?qū)O子結(jié)點(diǎn)之間的通路,稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1,則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長度為L-1。
(2)結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長度。若將樹中結(jié)點(diǎn)賦給一個有著某種含義的數(shù)值,則這個數(shù)值稱為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長度為:從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)的權(quán)的乘積。
(3)樹的帶權(quán)路徑長度。樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和,記為WPL。
然后是Huffman tree的構(gòu)造。
假設(shè)有n個權(quán)值,則構(gòu)造出的Huffman tree有n個葉子結(jié)點(diǎn)。n個權(quán)值分別設(shè)為w1w2……wn,則Huffman tree的構(gòu)造規(guī)則為:
(1) 將w1w2……wn看成是有n棵樹的森林(每棵樹僅有一個結(jié)點(diǎn));
(2)在森林中選出兩個根結(jié)點(diǎn)的權(quán)值最小的樹合并,作為一棵新樹的左、右子樹,且新樹的根結(jié)點(diǎn)權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和;
(3)從森林中刪除選取的兩棵樹,并將新樹加入森林;
(4)重復(fù)(2)、(3)步,直到森林中只剩一棵樹為止,該樹即為所求得的Huffman tree。
此時(shí)在看結(jié)論2我們會發(fā)現(xiàn),在Hufuman tree中每個節(jié)點(diǎn)的兩個子節(jié)點(diǎn)權(quán)值,在這里也就是信源符號對應(yīng)的概率一定是相等的,舉個例子就是如圖1所示。
也就是說,從根結(jié)點(diǎn)開始進(jìn)行分支,每i次分支得到的兩個子節(jié)點(diǎn)概率為2-i,反之概率為的節(jié)點(diǎn)一定是經(jīng)過第hi次分支得到。由于Human tree的定義,某一結(jié)點(diǎn)的路徑長度就等于得到該節(jié)點(diǎn)所需的分支次數(shù),因此對于緊致碼每個概率為的信源進(jìn)行Huffman編碼后其碼長一定為hi。
四、結(jié)論
本文針對一種被稱為緊致碼的特殊的信源空間分布,分別用Shannon,F(xiàn)ano和Huffman三種編碼方法對其進(jìn)行了證明,發(fā)現(xiàn)對于某種特殊的信源分布的緊致碼,平均碼長與其信源概率分布有關(guān)。我們引入Huffman tree構(gòu)造方法證明了Huffman編碼方法的情況,簡化了對于這種特殊的信源分布的緊致碼編碼過程,具有重要的實(shí)際意義。
參考文獻(xiàn):
[1]王鶴鳴.從信息化發(fā)展歷程看密碼學(xué)發(fā)展――專訪西安電子科技大學(xué)通信工程學(xué)院王育民教授[J].信息安全與通信保密,2011(11):13-19.
[2]鄧家先.與編碼課程教學(xué)改革探討[J].電子教學(xué)學(xué)報(bào),2007(02):111-114
[3]陳運(yùn).信息論與編碼[M].北京:電子工業(yè)出版社,2007.
[4]D CMacKay.Information Theory,Inference,and Learning Algorithms[M].Cambridge: Cambridge University Press,2000.
[5]曹雪虹,張宗橙.信息論與編碼[M].北京:清華大學(xué)出版社,2004(03).
[6]曲煒,朱詩兵.信息論基礎(chǔ)及應(yīng)用[M].北京:清華大學(xué)出版社,2005(01).
[7]沈世鎰,吳忠華.信息論基礎(chǔ)與應(yīng)用[M].北京:高等教育出版社,2004.
[8]傅祖蕓.信息論――基礎(chǔ)理論與應(yīng)用[M].北京:電子工業(yè)出版社,2001.
[9]馬秋芳.關(guān)于離散無記憶信源的最佳編碼問題[J].江漢石油學(xué)院學(xué)報(bào),1987.
【對于緊致碼在三種編碼方法下的編碼特性研究】相關(guān)文章:
新刑訴法下社區(qū)矯正問題研究09-05
地域文化影響下的企業(yè)文化構(gòu)建研究06-14
對于體育鍛煉態(tài)度、參與度與體育價(jià)值觀的相關(guān)研究05-28
小議3D 視頻編碼傳輸技術(shù)05-07
復(fù)合頂板下錨網(wǎng)索支護(hù)參數(shù)優(yōu)化研究08-28
文化視角下我國古代文學(xué)的研究(通用8篇)07-26
InP/InGaAs HBT頻率特性分析06-17