算術(shù)編碼

《算術(shù)編碼》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

實(shí)現(xiàn)算術(shù)編碼及其譯碼一、實(shí)驗(yàn)內(nèi)容借助C++編程來(lái)實(shí)現(xiàn)對(duì)算術(shù)編碼的編碼及其譯碼算法的實(shí)現(xiàn)二、實(shí)驗(yàn)環(huán)境1.計(jì)算機(jī)2.VC++6.0三、實(shí)驗(yàn)?zāi)康?.進(jìn)一步熟悉算術(shù)編碼的原理，及其基本的算法；2.通過(guò)編譯，充分對(duì)于算術(shù)編碼有進(jìn)一步的了解和掌握；3.掌握C++語(yǔ)言編程（尤其是數(shù)值的進(jìn)制轉(zhuǎn)換，數(shù)值與字符串之間的轉(zhuǎn)換等）四、實(shí)驗(yàn)原理算術(shù)編碼　　算術(shù)編碼的基本原理是將編碼的消息表示成實(shí)數(shù)0和1之間的一個(gè)間隔，消息越長(zhǎng)，編碼表示它的間隔就越小，表示這一間隔所需的二進(jìn)制位就越多。算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率和它的編碼間隔。信源符號(hào)的概率決定壓縮編碼的效率，也決定編碼過(guò)程中信源符號(hào)的間隔，而這些間隔包含在0到1之間。編碼過(guò)程中的間隔決定了符號(hào)壓縮后的輸出。給定事件序列的算術(shù)編碼步驟如下：（1）編碼器在開(kāi)始時(shí)將“當(dāng)前間隔”設(shè)置為[0，1)。（2）對(duì)每一事件，編碼器按步驟（a）和（b）進(jìn)行處理（a）編碼器將“當(dāng)前間隔”分為子間隔，每一個(gè)事件一個(gè)。（b）一個(gè)子間隔的大小與下一個(gè)將出現(xiàn)的事件的概率成比例，編碼器選擇子間隔對(duì)應(yīng)于下一個(gè)確切發(fā)生的事件相對(duì)應(yīng)，并使它成為新的“當(dāng)前間隔”。（3）最后輸出的“當(dāng)前間隔”的下邊界就是該給定事件序列的算術(shù)編碼。編碼過(guò)程　假設(shè)信源符號(hào)為{A，B，C，D}，這些符號(hào)的概率分別為{0.1，0.4，0.2，0.3}，根據(jù)這些概率可把間隔[0，1]分成4個(gè)子間隔：[0，0.1]，[0.1，0.5]，[0.5，0.7]，[0.7，1]，其中[x，y]表示半開(kāi)放間隔，即包含x不包含y。上面的信息可綜合在表03-04-1中。

1下表為信源符號(hào)，概率和初始編碼間隔符號(hào)ABCD?概率0.10.40.20.3?初始編碼間隔[0，0.1)[0.1，0.5)[0.5，0.7)[0.7，1]?如果二進(jìn)制消息序列的輸入為：CADACDB。編碼時(shí)首先輸入的符號(hào)是C，找到它的編碼范圍是[0.5，0.7]。由于消息中第二個(gè)符號(hào)A的編碼范圍是[0，0.1]，因此它的間隔就取[0.5，0.7]的第一個(gè)十分之一作為新間隔[0.5，0.52]。依此類推，編碼第3個(gè)符號(hào)D時(shí)取新間隔為[0.514，0.52]，編碼第4個(gè)符號(hào)A時(shí)，取新間隔為[0.514，0.5146]，…。消息的編碼輸出可以是最后一個(gè)間隔中的任意數(shù)。整個(gè)編碼過(guò)程如圖03-04-1所示。編碼和譯碼的全過(guò)程分別表示在下表。?編碼過(guò)程步驟?輸入符號(hào)編碼間隔?編碼判決1C[0.5，0.7]符號(hào)的間隔范圍[0.5，0.7]?2A[0.5，0.52][0.5，0.7]間隔的第一個(gè)1/103D[0.514，0.52][0.5，0.52]間隔的最后一個(gè)1/104A[0.514，0.5146][0.514，0.52]間隔的第一個(gè)1/105C[0.5143，0.51442][0.514，0.5146]間隔的第五個(gè)1/10開(kāi)始，二個(gè)1/106D[0.514384，0.51442][0.5143，0.51442]間隔的最后3個(gè)1/107B[0.5143836，0.514402][0.514384，0.51442]間隔的4個(gè)1/10，從第1個(gè)1/10開(kāi)始8從[0.5143876，0.514402]中選擇一個(gè)數(shù)作為輸出：0.5143876譯碼過(guò)程步驟?間隔譯碼符號(hào)?譯碼判決?

21[0.5，0.7]C0.51439在間隔[0.5，0.7)2[0.5，0.52]A0.51439在間隔[0.5，0.7)的第1個(gè)1/103[0.514，0.52]D0.51439在間隔[0.5，0.52)的第7個(gè)1/104[0.514，0.5146]A0.51439在間隔[0.514，0.52]的第1個(gè)1/105[0.5143，0.51442]C0.51439在間隔[0.514，0.5146]的第5個(gè)1/106[0.514384，0.51442]D0.51439在間隔[0.5143，0.51442]的第7個(gè)1/107[0.51439，0.5143948]B0.51439在間隔[0.51439，0.5143948]的第1個(gè)1/108譯碼的消息：CADACDB五、實(shí)驗(yàn)設(shè)計(jì)：算術(shù)編碼是一種無(wú)損數(shù)據(jù)壓縮方法，也是一種熵編碼的方法。和其它熵編碼方法不同的地方在于，其他的熵編碼方法通常是把輸入的消息分割為符號(hào)，然后對(duì)每個(gè)符號(hào)進(jìn)行編碼。而算術(shù)編碼是直接把整個(gè)輸入的消息編碼為一個(gè)數(shù)，一個(gè)滿足(0.0≤n<1.0)的小數(shù)n。所以用兩個(gè)基本的參數(shù)：符號(hào)的概率和它的編碼間隔。信源符號(hào)的概率決定壓縮編碼的效率，也決定編碼過(guò)程中信源符號(hào)的間隔，而這些間隔包含在0到1之間。算術(shù)編碼的算法思想如下：（1）對(duì)一組信源符號(hào)按照符號(hào)的概率從大到小排序，將[0,1)設(shè)為當(dāng)前分析區(qū)間。按信源符號(hào)的概率序列在當(dāng)前分析區(qū)間劃分比例間隔。（2）檢索“輸入消息序列”，鎖定當(dāng)前消息符號(hào)（初次檢索的話就是第一個(gè)消息符號(hào)）。找到當(dāng)前符號(hào)在當(dāng)前分析區(qū)間的比例間隔，將此間隔作為新的當(dāng)前分析區(qū)間。并把當(dāng)前分析區(qū)間的起點(diǎn)（即左端點(diǎn)）指示的數(shù)“補(bǔ)加”到編碼輸出數(shù)里。當(dāng)前消息符號(hào)指針后移。（3）仍然按照信源符號(hào)的概率序列在當(dāng)前分析區(qū)間劃分比例間隔。然后重復(fù)第二步。直到“輸入消息序列”檢索完畢為止。（4）最后的編碼輸出數(shù)就是編碼好的數(shù)據(jù)。六、實(shí)驗(yàn)程序：#include#include"math.h"

3//定義所需要用到的變量及數(shù)組charS[100],A[10];floatP[10],f[10],gFs;//編碼程序voidbianma(inta,inth){inti,j;floatfr;floatps=1;floatFs=0;floatSp[100],b[100],F[100];//以待編碼的個(gè)數(shù)和字符個(gè)數(shù)為循環(huán)周期，將待編碼的字符所對(duì)應(yīng)的概率存入到Fs中for(i=0;i(int)l)l=(int)l+1;elsel=int(l);//將Fs轉(zhuǎn)換成二進(jìn)制的形式intd[20];intm=0;while(l>m){Fs=2*Fs;if(Fs>1)

4{Fs=Fs-1;d[m]=1;}elseif(Fs<1)d[m]=0;else{d[m]=1;break;}m++;}intz=m;//解決有關(guān)算術(shù)編碼的進(jìn)位問(wèn)題,給二進(jìn)制數(shù)加1if(m>=l){while(1){d[m-1]=(d[m-1]+1)%2;//最后位加1if(d[m-1]==1)break;elsem--;}}cout<<"s=";for(inte=0;e-1;j--){Ft=Fs;Pt=Ps;Ft+=Pt*f[j];//對(duì)進(jìn)行逆編碼Pt*=P[j];if(gFs>=Ft)//對(duì)其進(jìn)行判斷，并且將值存入到數(shù)組A中

5{Fs=Ft;Ps=Pt;cout<>a;cout<<"請(qǐng)輸入符號(hào)及其相對(duì)應(yīng)的概率值，并按回車跳轉(zhuǎn)："<>x;A[i]=x;//將字符依次存入數(shù)組A中cin>>y;P[i]=y;//將字符所對(duì)應(yīng)的概率依次存入到數(shù)組P中}for(i=1;i>ss;

6if(ss=='*')break;//在以“*”為結(jié)尾的時(shí)候結(jié)束存儲(chǔ)S[h++]=ss;}cout<<"輸入的字符經(jīng)過(guò)算術(shù)編碼之后為："<