合工大信息论课程设计

1、课 程 设 计 设计题目：游程编码与算术编码 姓 名：邹 军 学 号：20103075 专业班级：信息安全10-2班指导教师：苏 兆 品时 间：2012年12月25号1、 问题描述1. 理解和掌握算术编码和游程编码的基本原理。2. 编程实现算术编码和游程编码的基本流程。3. 了解算术编码和游程编码的优缺点。4. 分析实验结果。 二、基本要求 1、对于游程编码： 测试数据为二维数组形式； 对输入的测试数据，先用霍夫曼编码法编码并译码，再用游程编码法 对霍夫曼编码的结果进行编码并译码。 2、对于算术编码: 测试数据为自己的学号； 对测试数据能进行编码和译码。三、信源编码的相关介绍 编码实质上是对信

2、源的原始符号按一定规则进行的一种变换。编码可分为信源编码和信道编码。信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的基础；限失真信源编码定理：是连续信源/模拟信号编码的基础。信源编码的分类：离散信源编码：独立信源编码,可做到无失真编码；连续信源编码：独立信源编码,只能做到限失真信源编码；相关信源编码；非独立信源编码

3、。 信源编码的作用之一是设法减少码元数目和降低码元速率，即通常所说的数据压缩：作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的数字化传输。 最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：Huffman编码、算术编码、L-Z编码，这三种都是无损编码，另外还有一些有损的编码方式。信源编码的目标就是使信源减少冗余，更加有效、经济地传输，最常见的应用形式就是压缩。 另外，在数字电视领域，信源编码包括 通用的MPEG2编码和H.264（MPEGPart10 AVC）编码等 相应地，信道编码是为了对抗信道中的噪音和衰减，通过增加冗

4、余，如校验码等，来提高抗干扰能力以及纠错能力。四、算法思想1、游程编码算法： 游程编码的基本原理是：用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“行程”，行程编码因此而得名），使符号长度少于原始数据的长度。只在各行或者各列数据的代码发生变化时，一次记录该代码及相同代码重复的个数，从而实现数据的压缩。在m元序列中，可能m种游程，连着出现m种符号ar的游程，其长度L（r）就是r游程长度，这是一个随机变量。用L（r）也可构成游程序列但是这种变换必须再加一些符号，才能成为一一对应或可逆的。游程长度编码的主要思想是将一个相同值的连续申用其值和申长(重复的个数)的数对二元组来替代。

5、例如，在图像编码中，可以定义沿特定方向上具有相同灰度值的相邻像素为一轮，其延续的长度称之为延续的行程，即游程。游程终点位置由前一游程终点的相对距离确定，这样就可以由灰度游程串来表示图像数据。例如，若沿水平方向有一串M 个像素具有相同的灰度N，则按游程长度编码后，只传递两个值(N，M)就可以代替这M 个像素的M个灰度值NJ简单来说，游程长度编码的主要任务是统计连续相同字符的个数，解码时要根据字符及连续相同字符的个数，恢复原来的数据。游程编码特点 ：游程编码仍是变长码，有其固有的缺点，及需要大量的缓冲和优 质的信道。此外，编程长度1可以从一直到无限，这在码字的选择和码表的建立方面都有困难，实际应用

6、是尚需采用某些措施来改进。一般情况下游程长度越长，其概率越小，这在以前的计算中也可以看见，而且将随着长度的增大渐进向零。对于小概率的码字，其长度为达到概率匹配或较长，损失不会太大，也就是对平均码字长度影响较小。再按哈夫曼编码或其他方法处理以达到压缩码率的目的 2、算术编码算法算术编码在图象数据压缩标准中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码。算术编码用到了两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。算术编码的算法思想如下：对一组信源符号按照

7、符号的概率从大到小排序，将0,1)设为当前分析区间。按信源符号的概率序列在当前分析区间划分比例间隔。检索“输入消息序列”，锁定当前消息符号（初次检索的话就是第一个消息符号）。找到当前符号在当前分析区间的比例间隔，将此间隔作为新的当前分析区间。并把当前分析区间的起点（即左端点）指示的数“补加”到编码输出数里。当前消息符号指针后移。仍然按照信源符号的概率序列在当前分析区间划分比例间隔。然后重复第二步。直到“输入消息序列”检索完毕为止。最后的编码输出数就是编码好的数据要编码的是一个来自四符号信源A，B，C，D的由五个符号组成的符号序列：ABBCD。假设已知各信源符号的概率分别为：P（A）=0.2,P

8、(B)=0.4,P(C)=0.2,P(D)=0.2。编码时，首先根据各个信源符号的概率将区间0，1。分成四个子区间。符号A对应0，0.2，符号B对应0.2,0.6，符号C对应0.6,0.8，符号D对应0.8,1.0。符号序列中第一个符号是A，其对应的区间为0,0.2，接下来将这个区间扩展为整个高度，再根据各个信源符号的概率将这个间扩展为整个高度，再根据各个信源符号的概率将这个新区间分成四段；第二个符号是B，它对应新的子区间的第二个子区间，即对应区间0.04,0.12；再将该区间扩展为整个高度，再根据这个过程直接最后一个符号得到一个区间0.08032,0.0816，这样该区间内的任何一个实数就可

9、以表示整个符号序列，如0.081（一般取区间的中间值）。五、模块划分1、游程编码算法模块划分(1)Huffman编码部分struct Huffmantree /霍夫曼树的节点 int weight; int parent,ld,rd;void build(int n); /建立霍夫曼树 void select(int &a,int &b); /选择两个权值最小的节点 void Code(); /霍夫曼编码int match(int l,int h) /译码的辅助函数（寻找匹配） void deCode(); /霍夫曼译码(2)游程编码部分（利用huffman编码结果再进行游程编

10、码）void create(int a ,int i,int j) /游程编码函数void show2(int a ,int i,int j,int c ,int & g,int v ) /输出游程数对void duishu(int a,int & i) /计算连续相同数的个数void zhuanhuan1(int c20,int d2020,int g,int m) /转换成二进制void bianma(int a ,int d ,int c ,int f ,int v ,int g,int m,int n)/ 游程编码void yima(int d2020,int f202

11、0,int g,int m,int n) /游程译码 2、自适应算术编码算法模块划分double proc=0.10,0.10,0.10,0.10,0.10,0.10,0.10,0.10,0.10,0.10;/计算09每个数出现的概率，初始化都为0.10int Num10=1,1,1,1,1,1,1,1,1,1;/计算09每个数的个数，初始化都为1bool readdat() /统计用户输入的字符串，并判断是否合法void encord() /对用户输入的字符串进行自适应算术编码void decord() /对用户输入的字符串进行自适应算术译码六、源代码1、游程编码#include<io

12、stream>#include<cstring>#include<algorithm>#include<map>using namespace std;/-霍夫曼编码函数-#define INF 0x7fffffff /无穷大 struct Huffmantree /霍夫曼树的节点 int weight;int parent,ld,rd;struct myNode int ch;int num;struct mycode /字符和其对应的编码 int ch; /字符 int s50; /ch的编码 int len; /编码长度 ;int nNode;

13、/叶子节点数目int totalNode; /霍夫曼树的总节点个数char toCode100000 ; /待编码的字符串myNode myToCode100000; /待编码的字符串和权值int weightOfToCode100000 ; /字符串的权值！Huffmantree myHuffmantree1000000; /霍夫曼树(数组模拟)int allchar1000000; /所哟出现过的字符 mycode coder1000000; /字符与对应的编码 int Len; /待编码的字符的总长度 int Coding100000; /译码之后的01串 int lenOfCoding

14、 ; /01串的长度 void build(int n); /建立霍夫曼树 void select(int &a,int &b); /选择两个权值最小的节点 void Code(); /编码 void printCode(); /打印编码void deCode(); /译码 int match(int l,int h);void build(int n) /建立霍夫曼树int i;int m=2*n-1; /n个叶子节点的霍夫曼树总节点数为2*n-1for(i=1;i<=n;i+) /初始化霍夫曼数组myHuffmantreei.weight=weightOfToCode

15、i; /叶子节点权值为字符出现次数myHuffmantreei.ld=-1; /叶子节点没有左孩子myHuffmantreei.rd=-1; /叶子节点没有右孩子myHuffmantreei.parent=i; /叶子节点父节点先初始化为他本身for(i=n+1;i<=m;i+)int a,b;select(a,b);myHuffmantreea.parent=i;myHuffmantreeb.parent=i;myHuffmantreei.ld=a;myHuffmantreei.rd=b;myHuffmantreei.weight=myHuffmantreea.weight+myHuf

16、fmantreeb.weight;myHuffmantreei.parent=i;for(i=1;i<=totalNode;i+)/printf("节点：%3d 权值： %3d 左节点： %3d 右节点：%3d 父节点： %3d n",i,myHuffmantreei.weight,myHuffmantreei.ld,myHuffmantreei.rd,myHuffmantreei.parent);void Code() /huffman编码 int i,j;int numOfCode100000;cout<<"-各字符编码结果如下-"

17、<<endl; if(Len=1) cout<<toCode0<<" : "<<"0n" return ;for(i=1;i<=nNode;i+)j=i;int h=0;while(myHuffmantreej.parent!=j)int x=j;j=myHuffmantreej.parent;if(myHuffmantreej.ld=x)numOfCodeh+=0;else if(myHuffmantreej.rd=x)numOfCodeh+=1;cout<<" "&

18、lt;<allchari-48<<" : "int x=0;coderi.len=h;coderi.ch=allchari;for(int k=h-1;k>=0;k-)coderi.sx+=numOfCodek; printf("%d",numOfCodek);cout<<endl; void select(int &a,int &b) /选择两个权值最小的节点int i;int min1=INF;int min2=INF;int sign1=1; /最小值的下标int sign2=2; /次小值的下标

19、for(i=1;i<=totalNode;i+)if(myHuffmantreei.parent=i) /说明其是已经更新过的节点if(myHuffmantreei.weight<min1)min1=myHuffmantreei.weight;sign1=i;for(i=1;i<=totalNode;i+)if(myHuffmantreei.parent=i) /说明其是已经更新过的节点if(myHuffmantreei.weight<min2&&i!=sign1)min2=myHuffmantreei.weight;sign2=i;a=sign1;b=

20、sign2;totalNode+; /总节点数加1void printCode() /打印编码结果！ int i;if(Len=1) /长度为1的时候特殊考虑 cout<<"0n"return ; int h=0; for(i=0;i<Len;i+)for(int j=1;j<=nNode;j+)if(toCodei=coderj.ch)for(int k=0;k<coderj.len;k+)printf("%d",coderj.sk);Codingh+=coderj.sk;lenOfCoding=h;cout<<

21、;endl;void deCode() /huffman译码 int i;int begin=0;for(i=0;i<lenOfCoding;i+)if(match(begin,i)!=-1)int x=match(begin,i);printf("%c",coderx.ch);begin=i+1; printf("n"); int match(int l,int h) /译码的辅助函数（寻找匹配） int i,j,k; int flag=0; for(i=1;i<=nNode;i+) if(coderi.len!=h-l+1) contin

22、ue;k=l;for(j=0;j<coderi.len;j+)if(Codingk!=coderi.sj) break;if(j=coderi.len-1)flag=1;goto ok;k+; ok:if(flag=1) /查找成功返回对应的下表return i;else /查找不成功返回-1；return -1;/-游程编码函数-void create(int a2020,int i,int j)int m,n,x;/cout<<"请输入:"<<endl;for(m=0;m<i;m+)for(n=0;n<j;n+) /cin>

23、;>x;amn=toCodem*i+n;void show2(int a2020,int i,int j,int c20,int & g,int v20) int m, n , w,k,l=0;for(m=0;m<i;m+) for(n=0;n<j;) cout<<"("<<amn-48<<","w=1;cg+=amn-48;for(k=n+1;k<j;k+)if(amn=amk) w+;else if(amn!=amk | w=j-n) cout<<w<<&qu

24、ot;)"<<" "vl+=w-1;break;n=k;if(n=j-1)cout<<w<<")"<<" " vl+=w-1;cout<<endl;void duishu(int a,int & i) int k=0;int b=a; while (a/2!=0) a=a/2;k+;if(b%2=0) i=k;else i=k+1;void zhuanhuan1(int c20,int d2020,int g,int m)/转换成二进制 int i,k,j=

25、0;for(i=0;i<g;i+)for(k=0;k<m;k+)dik=0;for(i=0;i<g;i+)for(k=m-1;k>=0;k-)if(ci/2>=0)dik=ci%2;ci=ci/2;else break;void bianma(int a2020,int d2020,int c20,int f2020,int v20,int g,int m,int n)/编码 int i,k,j;for(i=0;i<g;i+)vi=vi+1;zhuanhuan1(v,f,g,n);cout<<" 编码结果为："<<

26、endl;int h=0;for(i=0;i<g;i+) for(j=1;j<=nNode;j+)if(ci=coderj.ch-48)for(int k=0;k<coderj.len;k+)printf("%d",coderj.sk);Codingh+=coderj.sk;break;cout<<"."for(j=0;j<n;j+)cout<<fij<<" "cout<<endl;void yima(int c20,int d2020,int f2020,int

27、 g,int m,int n) int i,j,k=0,s=0,tmp=0,t=0;zhuanhuan1(c,d,g,m);int p20;int q20 ;cout<<"开始译码:"<<endl;for(i=0;i<g;i+)pi=tmp=0; for(j=0;j<m;j+)k=m-1-j;tmp=dij;while(k>0) tmp*=2;k-;pi+=tmp;if(dij%2!=0) pi=pi+dim-1;for(i=0;i<g;i+) qi=tmp=0; for(j=0;j<n;j+)k=n-1-j;tmp=f

28、ij;while(k>0) tmp*=2;k-;qi+=tmp;if(fij%2!=0) qi=qi+fin-1;for(i=0;i<g;i+)for(j=0;j<qi+1;j+)cout<<pi<<" "t+;if(t%8=0)cout<<endl; int main() int i,p,q;cout<<"n=霍夫曼编码程序=n"while(1)int flag=0;cout<<"请输入图像的行数和列数:"cin>>p>>q;pri

29、ntf("请输入待编码的字符串n");for(i=0;i<p*q;i+)cin>>toCodei;int len=strlen(toCode);if(len=1) flag=1; Len=len; map<char,int>myMap;for(i=0;i<len;i+) /统计字符串中各字符出现的频次！myMaptoCodei+;map<char,int>:iterator iter;int h=1;for(iter=myMap.begin();iter!=myMap.end();iter+) myToCodeh.ch=ite

30、r->first;allcharh=iter->first;weightOfToCodeh=iter->second;myToCodeh+.num=iter->second;nNode=h-1; /叶子节点个数cout<<"-字符统计如下-"<<endl;cout<<" 字符 次数"<<endl;for(i=1;i<h;i+) /显示将要编码的字符串中的各字符和他出现的次数！cout<<" "<<myToCodei.ch-48<

31、<" "<<myToCodei.num<<endl;cout<<endl;totalNode=nNode; /totalNode初始值为nNode/cout<<"-霍夫曼树节点信息如下(子节点为-1表示是叶子节点)-"<<endl<<endl; build(nNode);cout<<endl;Code();cout<<"n-字符串的编码结果如下-n"printCode();cout<<"n-01串的译码结果如下-

32、n" deCode();cout<<endl;cout<<"n=游程编码程序=n"int j,g=0,m,n;char x;int a2020;int c20;int v20;/cout<<"请输入灰度:"<<endl;/cin>>h;h = 8;duishu(h,m);/cout<<"请输入行数和列数："<<endl;/cin>>i>>j;duishu(q,n);create(a,p,q);show2(a,p,q,c

33、,g,v);int d2020;int f2020;for(i=0;i<g;i+)vi=vi-1;bianma(a,d,c,f,v,g, m, n);yima(c,d,f,g,m,n);cout<<"n是否继续？(Y/N)n"char con10;cin>>con;char fang=toupper(con0); if(fang='N'|'n') break; getchar();return 0;2、自适应算术编码/*自适应模式算术编码 */#include<math.h>#include<s

34、tring.h>#include<stdio.h>double proc=0.10,0.10,0.10,0.10,0.10,0.10,0.10,0.10,0.10,0.10;int Num10=1,1,1,1,1,1,1,1,1,1;double result,areaBegin,areaEnd;int cord1000,cordLength;char str1000;int strLength=0;bool readdat()printf("* 自适应模式算术编码 *n");printf("请输入字符串(0-9): n");scanf

35、("%s",str);while(strstrLength!='0')strLength+;for(int i=0;i<strLength;i+) /输入是否合法if(stri>'9' | stri<'0') return 1;return 0;void encord() int sum=10;int i;printf(" 编 码 :");double w=0.0,len;areaBegin=0.0,areaEnd=1.0;for(i=0;i<strLength;i+)int n=stri-'0',k;w=0.0;for(k=0;k<n;k+) w += prock; /计算所在区间len=areaEnd-areaBegin;/计算新的区间areaEnd = areaBegin+len*(w+prock);areaBegin += len*w;Numn+; sum+; for(int l=0;l<10;l+) procl=Numl/double(sum);