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

時(shí)間：2024-09-04 08:09:08 電子信息工程畢業(yè)論文我要投稿

相關(guān)推薦

　　摘要：本文針對(duì)一種被稱為緊致碼的特殊的信源空間分布，基于Shannon，F(xiàn)ano和Huffman三種編碼方法，并分別對(duì)其進(jìn)行了證明，發(fā)現(xiàn)對(duì)于某種特殊的信源分布的緊致碼，平均碼長(zhǎng)與其信源概率分布有關(guān)。同時(shí)通過(guò)引入Huffman tree構(gòu)造方法證明了Huffman編碼方法的情況，簡(jiǎn)化了對(duì)于這種特殊的信源分布的緊致碼編碼過(guò)程。

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

　　關(guān)鍵詞：緊致碼;Fano;Huffman;Huffman tree;Shannon

　　一、引言

　　21世紀(jì)，國(guó)際社會(huì)已進(jìn)入信息化時(shí)代。信息論作為信息科學(xué)和技術(shù)的基本理論，猶如信息科學(xué)大廈的地基，在信息社會(huì)中占據(jù)越來(lái)越重要的地位。信息論的創(chuàng)始人Shannon，他在 1949 年發(fā)表了《保密通信的信息理論》，是每一位研究信息學(xué)者必讀的一篇文章[1]。隨著信息技術(shù)的發(fā)展，編碼技術(shù)已經(jīng)在媒體技術(shù)、網(wǎng)絡(luò)技術(shù)、無(wú)線通信技術(shù)、數(shù)字電視技術(shù)等方面得到廣泛應(yīng)用[2]。信息論、錯(cuò)誤控制編碼和密碼學(xué)是現(xiàn)在數(shù)字通信系統(tǒng)中的三大支柱。信息論基礎(chǔ)是應(yīng)用概率論、隨機(jī)過(guò)程和近世代數(shù)等方法研究信息的存儲(chǔ)、傳輸和處理中一般規(guī)律的學(xué)科，主要解決通信過(guò)程中信息傳輸?shù)挠行浴⒖煽啃耘c安全性的問(wèn)題，是信息科學(xué)和通信科學(xué)領(lǐng)域中的一門基礎(chǔ)理論[3，4]。

　　信息論將信息的傳遞作為一種統(tǒng)計(jì)現(xiàn)象來(lái)考慮，給出了估算通信信道容量的方法。信息傳輸和信息壓縮是信息論研究中的兩大領(lǐng)域。緊致碼在信息論的研究中有著至關(guān)重要的作用，并且具有重大實(shí)際意義。

　　本文的目的是用信息論觀點(diǎn)對(duì)緊致碼進(jìn)行若干研究，以Shannon，F(xiàn)ano和Huffman三種編碼方法為例，分別介紹它們的編碼原理以及相關(guān)證明，進(jìn)一步得出結(jié)論。

　　二、緊致碼

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

　　其中hi為任意正整數(shù)，對(duì)信源進(jìn)行二進(jìn)制編碼，該編碼為最佳編碼，或者說(shuō)獲得碼是緊致碼[5]。

　　編碼效率。

　　式中H(X)=-∑pilog2pi為信源熵，r為碼符號(hào)數(shù)，這里考慮二進(jìn)制編碼，r=2，為編碼后平均碼長(zhǎng)，定義表達(dá)式為。

　　從平均碼長(zhǎng)的角度出發(fā)，對(duì)于給定信源，使平均碼長(zhǎng)達(dá)到最小的編碼方法，稱為最佳編碼，得到的碼稱為最佳碼，即緊致碼。

　　本文考慮信源的每個(gè)消息的概率滿足，信源消息編碼后的碼長(zhǎng)為ni=hi，則編碼效率為

　　下面我們將對(duì)上述結(jié)論進(jìn)行證明。

　　三、三種編碼法及其證明

　　3.1 對(duì)于Shannon編碼的證明

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

　　(1)將信源發(fā)出的M個(gè)消息，按其概率遞減順序進(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í)取等號(hào))，計(jì)算出每個(gè)消息的二進(jìn)制代碼的長(zhǎng)度nm(m=1，2，…，M)，nm，nm取正整數(shù);

　　(4)為得到唯一可譯碼，計(jì)算出第m個(gè)消息的累加概率，再將pm變換成二進(jìn)制小數(shù)，取小數(shù)點(diǎn)后面nm位作為第m個(gè)消息的代碼組(碼字)。

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

　　3.2 對(duì)于Fano編碼的證明

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

　　(1)信源發(fā)出的M個(gè)消息，按其概率遞減順序排列，得

　　P(x1)≥p(x2)≥…≥p(xM)

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

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

　　(3)如此一直進(jìn)行下去，直到各子集僅含一個(gè)消息為止;

　　(4)將逐次分解過(guò)程中得到的碼元排列起來(lái)就是各消息代碼。

　　下面證明作上述操作后得到的每個(gè)消息對(duì)應(yīng)的碼長(zhǎng)為hi。

　　由上述步驟可知，經(jīng)過(guò)n次分解后得到的消息xi其對(duì)應(yīng)的碼長(zhǎng)一定為n，于是問(wèn)題轉(zhuǎn)為證明對(duì)應(yīng)概率為的消息需要hi次分解后得到的子集僅含該消息。為簡(jiǎn)便，以下將把某個(gè)消息經(jīng)過(guò)分解后得到的子集僅含該消息簡(jiǎn)稱為將該消息分出來(lái)。

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

　　由上述可知對(duì)于緊致碼用Fano編碼法進(jìn)行編碼后每個(gè)信源對(duì)應(yīng)的碼長(zhǎng)也為hi。

　　3.3 對(duì)于Huffman編碼的證明

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

　　(1)將概率最小的兩個(gè)符號(hào)連在一起。將這兩個(gè)符號(hào)的概率之和寫(xiě)在他們的結(jié)合節(jié)點(diǎn)上。將這兩個(gè)分別標(biāo)記為0和1;

　　(2)將這兩個(gè)概率和看作一個(gè)新符號(hào)的概率。重新排列信源符號(hào)，并將概率最小的兩個(gè)信源符號(hào)，將他們綁定在一起構(gòu)成一個(gè)新的概率。每一次我們把兩個(gè)符號(hào)結(jié)合在一起是符號(hào)總數(shù)減1。每當(dāng)把兩個(gè)概率結(jié)合在一起時(shí)，總是把兩個(gè)分支標(biāo)記為0和1;

　　(3)將此過(guò)程繼續(xù)下去直至只剩一個(gè)概率，就完成了Huffman樹(shù)的構(gòu)造;

　　(4)對(duì)于任意符號(hào)的碼字，找到從最后節(jié)點(diǎn)到該符號(hào)的一個(gè)路徑，反向追蹤路徑并讀出分支的碼字，即為該符號(hào)的碼字。

　　下面開(kāi)始證明。

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

　　對(duì)于這種信源分布顯然每個(gè)信源編碼后的碼長(zhǎng)為hi。

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

　　對(duì)于一個(gè)信源空間X，其概率分布為

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

　　p1≥p2≥…≥pM

　　其中M為消息個(gè)數(shù)。那么其最小的兩個(gè)概率和必定是相等的。舉個(gè)簡(jiǎn)單例子，概率從大到小為1/2，1/4，1/8，1/16，1/16。如果只有一個(gè)1/16，那么前三項(xiàng)加起來(lái)應(yīng)該是15/16，但前面三項(xiàng)中最小的也是1/8，怎么相加都不會(huì)加到15/16。

　　下面用反證法進(jìn)行證明。

　　假設(shè)有pM-1>pM即hM-1　　現(xiàn)在回到Huffman方法。由上面的結(jié)論可知，對(duì)于上述的一個(gè)信源空間進(jìn)行Huffman編碼，每一次合并重排后，最下面的兩個(gè)信源符號(hào)，也就是概率最小的兩個(gè)信源的概率一定是相等的。因?yàn)槊恳淮魏喜⒅嘏藕螅旁纯臻g會(huì)形成一個(gè)新的信源空間，原來(lái)概率最小的兩個(gè)信源符號(hào)合并成一個(gè)新的信源符號(hào)，也就是說(shuō)形成一個(gè)新的概率分布，由于相加的兩個(gè)概率相等，則相加得到的新的概率仍然滿足p=2-h，也就是說(shuō)新的概率分布仍然滿足，則同樣滿足結(jié)論。這個(gè)結(jié)論當(dāng)我們引入Huffman tree的概念后對(duì)證明就會(huì)變得極其有用。

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

　　(1)路徑和路徑長(zhǎng)度。在一棵樹(shù)中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或?qū)O子結(jié)點(diǎn)之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長(zhǎng)度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)-1。

　　(2)結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長(zhǎng)度。若將樹(shù)中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。

　　(3)樹(shù)的帶權(quán)路徑長(zhǎng)度。樹(shù)的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為WPL。

　　然后是Huffman tree的構(gòu)造。

　　假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的Huffman tree有n個(gè)葉子結(jié)點(diǎn)。n個(gè)權(quán)值分別設(shè)為w1w2……wn，則Huffman tree的構(gòu)造規(guī)則為：

　　(1) 將w1w2……wn看成是有n棵樹(shù)的森林(每棵樹(shù)僅有一個(gè)結(jié)點(diǎn));

　　(2)在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和;

　　(3)從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林;

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

　　此時(shí)在看結(jié)論2我們會(huì)發(fā)現(xiàn)，在Hufuman tree中每個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)權(quán)值，在這里也就是信源符號(hào)對(duì)應(yīng)的概率一定是相等的，舉個(gè)例子就是如圖1所示。

　　也就是說(shuō)，從根結(jié)點(diǎn)開(kāi)始進(jìn)行分支，每i次分支得到的兩個(gè)子節(jié)點(diǎn)概率為2-i，反之概率為的節(jié)點(diǎn)一定是經(jīng)過(guò)第hi次分支得到。由于Human tree的定義，某一結(jié)點(diǎn)的路徑長(zhǎng)度就等于得到該節(jié)點(diǎn)所需的分支次數(shù)，因此對(duì)于緊致碼每個(gè)概率為的信源進(jìn)行Huffman編碼后其碼長(zhǎng)一定為hi。

　　四、結(jié)論

　　本文針對(duì)一種被稱為緊致碼的特殊的信源空間分布，分別用Shannon，F(xiàn)ano和Huffman三種編碼方法對(duì)其進(jìn)行了證明，發(fā)現(xiàn)對(duì)于某種特殊的信源分布的緊致碼，平均碼長(zhǎng)與其信源概率分布有關(guān)。我們引入Huffman tree構(gòu)造方法證明了Huffman編碼方法的情況，簡(jiǎn)化了對(duì)于這種特殊的信源分布的緊致碼編碼過(guò)程，具有重要的實(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]曲煒，朱詩(shī)兵.信息論基礎(chǔ)及應(yīng)用[M].北京：清華大學(xué)出版社，2005(01).

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

　　[8]傅祖蕓.信息論――基礎(chǔ)理論與應(yīng)用[M].北京：電子工業(yè)出版社，2001.

　　[9]馬秋芳.關(guān)于離散無(wú)記憶信源的最佳編碼問(wèn)題[J].江漢石油學(xué)院學(xué)報(bào)，1987.

【對(duì)于緊致碼在三種編碼方法下的編碼特性研究】相關(guān)文章：

三種Logistic映射混沌參數(shù)調(diào)制特性的研究03-07