對于緊致碼在三種編碼方法下的編碼特性研究

廖慶洪+吳雙雙+劉志偉+彭維

摘 要：本文針對一種被稱為緊致碼的特殊的信源空間分布，基于Shannon，Fano和Huffman三種編碼方法，并分別對其進行了證明，發現對于某種特殊的信源分布的緊致碼，平均碼長與其信源概率分布有關。同時通過引入Huffman tree構造方法證明了Huffman編碼方法的情況，簡化了對于這種特殊的信源分布的緊致碼編碼過程。

關鍵詞：緊致碼；Shannon；Fano；Huffman；Huffman tree

DOI：10.16640/j.cnki.37-1222/t.2015.24.247

1 引言

21世紀，國際社會已進入信息化時代。信息論作為信息科學和技術的基本理論，猶如信息科學大廈的地基，在信息社會中占據越來越重要的地位。信息論的創始人Shannon，他在 1949 年發表了《保密通信的信息理論》，是每一位研究信息學者必讀的一篇文章[1]。隨著信息技術的發展， 編碼技術已經在媒體技術、網絡技術、無線通信技術、數字電視技術等方面得到廣泛應用[2]。信息論、錯誤控制編碼和密碼學是現在數字通信系統中的三大支柱。信息論基礎是應用概率論、隨機過程和近世代數等方法研究信息的存儲、傳輸和處理中一般規律的學科，主要解決通信過程中信息傳輸的有效性、可靠性與安全性的問題，是信息科學和通信科學領域中的一門基礎理論[3，4]。

信息論將信息的傳遞作為一種統計現象來考慮，給出了估算通信信道容量的方法。信息傳輸和信息壓縮是信息論研究中的兩大領域。緊致碼在信息論的研究中有著至關重要的作用，并且具有重大實際意義。

本文的目的是用信息論觀點對緊致碼進行若干研究，以Shannon，Fano和Huffman三種編碼方法為例，分別介紹它們的編碼原理以及相關證明，進一步得出結論。

2 緊致碼

這里我們介紹一種特殊的信源分布，如果其中各消息概率滿足pi

其中hi為任意正整數，對信源進行二進制編碼，該編碼為最佳編碼，或者說獲得碼是緊致碼[5]。

編碼效率

。

式中H（X）=-∑pilog2pi為信源熵，r為碼符號數，這里考慮二進制編碼，r=2，為編碼后平均碼長，定義表達式為。

從平均碼長的角度出發，對于給定信源，使平均碼長達到最小的編碼方法，稱為最佳編碼，得到的碼稱為最佳碼，即緊致碼。

本文考慮信源的每個消息的概率滿足，信源消息編碼后的碼長為ni=hi，則編碼效率為

下面我們將對上述結論進行證明。

3 三種編碼法及其證明

3.1 對于Shannon編碼的證明

首先介紹Shannon編碼方法。步驟如下：

（1）將信源發出的M個消息，按其概率遞減順序進行排列，得

P（x1）≥p（x2）≥…≥p（xM）

（2）計算出各消息的-logp（xm）值，m=1，2，…M；

（3）根據-logp（xm）≤nm<-logp（xm）+1。（-logp（xm）為整數時取等號），計算出每個消息的二進制代碼的長度nm（m=1，2，…，M），nm，nm取正整數；

（4）為得到唯一可譯碼，計算出第m個消息的累加概率，再將pm變換成二進制小數，取小數點后面nm位作為第m個消息的代碼組（碼字）。

然后我們考慮上面介紹的緊致碼。記離散信源，其中滿足，對其進行Shannon編碼[6]，由第三步可知，任一信源xi其對應的二進制代碼長度nm=-logp（xm）=hi，這就是我們要證明的對緊致碼進行Shannon編碼后每個信源對應的碼長為hi。

3.2 對于Fano編碼的證明

對Fano編碼的思路與Shannon編碼類似。首先介紹Fano編碼方法[7]。步驟如下：

（1）信源發出的M個消息，按其概率遞減順序排列，得

P（x1）≥p（x2）≥…≥p（xM）

把消息集{x1，x2，…xM}按其概率大小分解成兩個子集，使兩個子集的概率之和盡可能相等，把第一個子集編碼為0，第二個子集編碼為1，作為代碼組的第一個碼元；

（2）對子集做第二次分解，同樣分解成兩個子集，并使兩個子集概率之和盡可能接近相等，再把第一個子集編碼為0，第二個子集編碼為1，作為第二個代碼組的碼元；

（3）如此一直進行下去，直到各子集僅含一個消息為止；

（4）將逐次分解過程中得到的碼元排列起來就是各消息代碼。

下面證明作上述操作后得到的每個消息對應的碼長為hi。

由上述步驟可知，經過n次分解后得到的消息xi其對應的碼長一定為n，于是問題轉為證明對應概率為的消息需要hi次分解后得到的子集僅含該消息。為簡便，以下將把某個消息經過分解后得到的子集僅含該消息簡稱為將該消息分出來。

由Fano編碼步驟可知，進行第n次分解，會得到2n個子集，其中每個子集中所包含消息概率和為2-n，現在考慮第hi次分解，將會得到個子集，其中每個子集中所包含的消息概率和為，可知概率為的消息將會在本次分解中被分出來。也即概率為的消息將在第hi次分解中被分出來。

由上述可知對于緊致碼用Fano編碼法進行編碼后每個信源對應的碼長也為hi。

3.3 對于Huffman編碼的證明

同樣首先引出Huffman編碼[8]。將信源符號按概率遞減的次序排列；

（1）將概率最小的兩個符號連在一起。將這兩個符號的概率之和寫在他們的結合節點上。將這兩個分別標記為0和1；

（2）將這兩個概率和看作一個新符號的概率。重新排列信源符號，并將概率最小的兩個信源符號，將他們綁定在一起構成一個新的概率。每一次我們把兩個符號結合在一起是符號總數減1。每當把兩個概率結合在一起時，總是把兩個分支標記為0和1；endprint

（3）將此過程繼續下去直至只剩一個概率，就完成了Huffman樹的構造；

（4）對于任意符號的碼字，找到從最后節點到該符號的一個路徑，反向追蹤路徑并讀出分支的碼字，即為該符號的碼字。

下面開始證明。

首先我們考慮最特殊也是最理想的一種情況，信源概率分布如表1所示，

對于這種信源分布顯然每個信源編碼后的碼長為hi。

上述討論的概率分布是對于的概率分布最特殊也是最基本的情況，一切其他的情況都是有此種情況轉化而來。換句話說任何概率分布為的概率均可以轉化為從2-1，2-2，一直排到2-M+1，2-M+1的排列。下面我們考慮這種序列所具有的特性，可得出如下結論：

對于一個信源空間X，其概率分布為

其中hi為任意正整數。將其按概率降序排列為

p1≥p2≥…≥pM

其中M為消息個數。那么其最小的兩個概率和必定是相等的。舉個簡單例子，概率從大到小為1/2，1/4，1/8，1/16，1/16。如果只有一個1/16，那么前三項加起來應該是15/16，但前面三項中最小的也是1/8，怎么相加都不會加到15/16。

下面用反證法進行證明。

假設有pM-1>pM即hM-1

現在回到Huffman方法。由上面的結論可知，對于上述的一個信源空間進行Huffman編碼，每一次合并重排后，最下面的兩個信源符號，也就是概率最小的兩個信源的概率一定是相等的。因為每一次合并重排后，原信源空間會形成一個新的信源空間，原來概率最小的兩個信源符號合并成一個新的信源符號，也就是說形成一個新的概率分布，由于相加的兩個概率相等，則相加得到的新的概率仍然滿足p=2-h，也就是說新的概率分布仍然滿足，則同樣滿足結論。這個結論當我們引入Huffman tree的概念后對證明就會變得極其有用。

下面先介紹一些樹的基本概念，然后引出Huffman tree的概念。

（1）路徑和路徑長度。在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1。

（2）結點的權及帶權路徑長度。若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。

（3）樹的帶權路徑長度。樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL。

然后是Huffman tree的構造。

假設有n個權值，則構造出的Huffman tree有n個葉子結點。n個權值分別設為w1w2……wn，則Huffman tree的構造規則為：

（1） 將w1w2……wn看成是有n棵樹的森林（每棵樹僅有一個結點）；

（2）在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；

（3）從森林中刪除選取的兩棵樹，并將新樹加入森林；

（4）重復（2）、（3）步，直到森林中只剩一棵樹為止，該樹即為所求得的Huffman tree。

此時在看結論2我們會發現，在Hufuman tree中每個節點的兩個子節點權值，在這里也就是信源符號對應的概率一定是相等的，舉個例子就是如圖1所示。

也就是說，從根結點開始進行分支，每i次分支得到的兩個子節點概率為2-i，反之概率為的節點一定是經過第hi次分支得到。由于Human tree的定義，某一結點的路徑長度就等于得到該節點所需的分支次數，因此對于緊致碼每個概率為的信源進行Huffman編碼后其碼長一定為hi。

4 結論

本文針對一種被稱為緊致碼的特殊的信源空間分布，分別用Shannon，Fano和Huffman三種編碼方法對其進行了證明，發現對于某種特殊的信源分布的緊致碼，平均碼長與其信源概率分布有關。我們引入Huffman tree構造方法證明了Huffman編碼方法的情況，簡化了對于這種特殊的信源分布的緊致碼編碼過程，具有重要的實際意義。

參考文獻：

[1]王鶴鳴.從信息化發展歷程看密碼學發展——專訪西安電子科技大學通信工程學院王育民教授[J].信息安全與通信保密，2011（11）：13-19.

[2]鄧家先.與編碼課程教學改革探討[J].電子教學學報，2007（02）：111-114

[3]陳運.信息論與編碼[M].北京：電子工業出版社，2007.

[4]D CMacKay.Information Theory，Inference，and Learning Algorithms[M].Cambridge： Cambridge University Press，2000.

[5]曹雪虹，張宗橙.信息論與編碼[M].北京：清華大學出版社，2004（03）.

[6]曲煒，朱詩兵.信息論基礎及應用[M].北京：清華大學出版社，2005（01）.

[7]沈世鎰，吳忠華.信息論基礎與應用[M].北京：高等教育出版社，2004.

[8]傅祖蕓.信息論——基礎理論與應用[M].北京：電子工業出版社，2001.

[9]馬秋芳.關于離散無記憶信源的最佳編碼問題[J].江漢石油學院學報，1987.

項目：江西省省級教改項目（編號：JXJG-12-1-17） 和南昌大學學位與研究生教育教學改革研究項目（編號：YJG2012002）資助的課題。

*為通訊作者