算数游程编码.doc

算术编码与游程编码1 .课题描述 1. 理解和掌握算术编码和游程编码的基本原理。2. 编程实现算术编码和游程编码的基本流程。3. 了解算术编码和游程编码的优缺点。4. 分析实验结果。2 信源编码的相关介绍 编码实质上是对信源的原始符号按一定规则进行的一种变换。编码可分为信源编码和信道编码。信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。 信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。 无失真信源编码定理：是离散信源/数字信号编码的基础； 限失真信源编码定理：是连续信源/模拟信号编码的基础。 信源编码的分类： 离散信源编码：独立信源编码,可做到无失真编码； 连续信源编码：独立信源编码,只能做到限失真信源编码； 相关信源编码：非独立信源编码。 信源编码的作用之一是设法减少码元数目和降低码元速率，即通常所说的数据压缩：作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的数字化传输。 最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：Huffman编码、算术编码、L-Z编码，这三种都是无损编码，另外还有一些有损的编码方式。信源编码的目标就是使信源减少冗余，更加有效、经济地传输，最常见的应用形式就是压缩。 另外，在数字电视领域，信源编码包括 通用的MPEG2编码和H.264（MPEGPart10 AVC）编码等 相应地，信道编码是为了对抗信道中的噪音和衰减，通过增加冗余，如校验码等，来提高抗干扰能力以及纠错能力。3 . 算术编码 3.1算术编码算法算术编码在图像数据压缩标准中扮演了重要的角色, 是无损压缩的一种算术编码中用0和1之间的实数进行编码, 该编码用到两个基本的参数 符号的概率和它的编码间隔信源符号的概率决定了压缩编码的效率, 也决定了编码过程中信源符号的间隔, 而这些间隔包含在0到1之间 编码过程中的间隔决定了符号压缩后的输出算术编码的编码过程如下算术编码把一个信源集合表示为实数线上的 0 到 1 之间的一个区间。这个集合中的每个元素都要用来缩短这个区间。信源集合的元素越多,所得到的区间就越小,当区间变小时,就需要更多的数位来表示这个区间,这就是区间作为代码的原理。算术编码首先假设一个信源的概率模型,然后用这些概率来缩小表示信源集的区间。设英文元音字母采用固定模式符号概率分配如下:设编码的数据串为 eai 。令 high 为编码间隔的高端 ,low 为编码间隔的低端 , range 为编码间隔的长度 ,rangelow 为编码字符分配的间隔低端 ,rangehigh 为编码字符分配的间隔高端。初始 high=1,low=0,rangehigh-low, 一个字符编码后新的 low 和 high 按下式计算 :low =lowrange rangelowhigh =lowrangerangehigh信源符号概率初始编码间隔a0.5(0,0,5)b0.25(0.5,0.75)c0.125(0.75,0,875)d0.125(0.875,1.0)(1) 在第一个字符 e 被编码时 ,e 的 rangelow0.2,rangehigh=0.5, 因此 :low0 + 1 0.2 0.2high=0 + 1 0.5 0.5range=highlow=0.50.2=0.3此时分配给 e 的范围为 0.2,0.5 。(2)第二个字符 a 编码时使用新生成范围 0.2,0.5,a 的 rangelow=0, rangehigh=0.2, 因此：low=0.2 十 0.3 0=0.2 high=0.2 0.3 0.2=0.26range=0.06范围变成 0.2,0.26 。(3) 对下一个字符 i 编号,i 的 rangelow=0.5,rangehigh=0.6, 则：low=0.2 0.06 0.5=0.23high=0.2 0.06 0.6=0.236即用 0.23,0.236 表示数据串 eai, 如果解码器知道最后范围是 0.23,0.236 这一范 围 , 它马上可解得一个字符为 e, 然后依次得到惟一解 a, 即最终得到 eai 。算术编码的算法思想如下：（1）对一组信源符号按照符号的概率从大到小排序，将0,1)设为当前分析区间。按信源符号的概率序列在当前分析区间划分比例间隔。（2）检索“输入消息序列”，锁定当前消息符号（初次检索的话就是第一个消息符号）。找到当前符号在当前分析区间的比例间隔，将此间隔作为新的当前分析区间。并把当前分析区间的起点（即左端点）指示的数“补加”到编码输出数里。当前消息符号指针后移。（3）仍然按照信源符号的概率序列在当前分析区间划分比例间隔。然后重复第二步。直到“输入消息序列”检索完毕为止。（4）最后的编码输出数就是编码好的数据。3.2算术编码的特点1）不必预先定义概率模型 , 自适应模式具有独特的优点;2）信源符号概率接近时 , 建议使用算术编码 , 这种情况下其效率高于 Huffman 编码;3）算术编码绕过了用一个特定的代码替代一个输入符号的想法 , 用一个浮点输出数值代替一个流的输入符号 , 较长的复杂的消息输出的数值中就需要更多的位数。4）算术编码实现方法复杂一些 , 但 JPEG 成员对多幅图像的测试结果表明 , 算术编码比Huffman 编码提高了 5% 左右的效率 , 因此在 JPEG 扩展系统中用算术编码取代 Huffman 编码。4. 算术编码的C程序实现 4.1 程序设计#include #include#include #define M 100#define N 4class suanshu int count,length;char numberN,n;long double chanceN,c;char codeM;long double High,Low,high,low,d;public:suanshu() High=0;Low=0;void get_number();void get_code();void coding();suanshu();void suanshu:get_number()coutplease input the number.endl;for(int i=0;in; numberi=n; coutplease input the chance.endl;for(int i=0;ic;chancei=c; if(i=20) coutthe number is full.endl;count=i;void suanshu:get_code()coutlength;while(length=M) coutlength;for(int i=0;icodei;void suanshu:coding()long double tp;/从区间取数 long double x=0.0; int i,j=0;for(i=0;icount;i+) if(code0=numberi) break;while(ji) Low+=chancej+;d=chancej;High=Low+d;for(i=1;ilength;i+) for(j=0;jcount;j+) if(codei=numberj) if(j=0) low=Low; high=Low+chancej*d; High=high; d*=chancej; else float chance_l=0.0; for(int k=0;k=j-1;k+) chance_l+=chancek; low=Low+d*chance_l; high=Low+d*(chance_l+chancej); Low=low; High=high; d*=chancej; else continue; coutthe result is:Lowhighendl;tp=(low+high)/2.0;/取区间的中点编码printf(n选取的小数为：%.17fn,tp); for(j=0;j1.0) tp=tp-1; codej=1; else codej=0; printf(编码为：n);/输出编码 for(i=0;ilow)&(xhigh)/判断恢复的是否成功 printf(n恢复的小数仍在允许区间n);int main()suanshu a;a.get_number();a.get_code();a.coding();return 0; 4.2 运行结果 3 游程编码 3.1 游程编码算法 编码的基本原理是：用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“行程”。行程编码因此而得名），使符号长度少于原始数据的长度。只在各行或者各列数据的代码发生变化时，一次记录该代码及相同代码重复的个数，从而实现数据的压缩。在m元序列中，可能m种游程，连着出现m种符号ar的游程，其长度L（r）就是r游程长度，这是一个随机变量。用L（r）也可构成游程序列但是这种变换必须再加一些符号，才能成为一一对应或可逆的。游程长度编码的主要思想是将一个相同值的连续申用其值和申长(重复的个数)的数对二元组来替代。例如，在图像编码中，可以定义沿特定方向上具有相同灰度值的相邻像素为一轮，其延续的长度称之为延续的行程，即游程。游程终点位置由前一游程终点的相对距离确定，这样就可以由灰度游程串来表示图像数据。例如，若沿水平方向有一串M 个像素具有相同的灰度N，则按游程长度编码后，只传递两个值(N，M)就可以代替这M 个像素的M个灰度值NJ简单来说，游程长度编码的主要任务是统计连续相同字符的个数，解码时要根据字符及连续相同字符的个数，恢复原来的数据。 3.1 游程编码特点 游程编码仍是变长码，有其固有的缺点，及需要大量的缓冲和优质的信道。此外，编程长度1可以从一直到无限，这在码字的选择和码表的建立方面都有困难，实际应用是尚需采用某些措施来改进。一般情况下游程长度越长，其概率越小，这在以前的计算中也可以看见，而且将随着长度的增大渐进向零。对于小概率的码字，其长度为达到概率匹配或较长，损失不会太大，也就是对平均码字长度影响较小。再按哈夫曼编码或其他方法处理以达到压缩码率的目的 。4. 游程编码的C程序实现 4.1 程序设计 #includeusing namespace std; void create(int a2020,int i,int j)int m,n,x; cout请输入:endl; for(m=0;mi;m+) for(n=0;nx; amn=x; a00=5;a01=5;a02=5;a03=5;a04=4;a05=4;a06=4;a07=4;a10=4;a11=4;a12=4;a13=6;a14=6;a15=2;a16=2;a17=2;a20=2;a21=2;a22=3;a23=3;a24=3;a25=3;a26=3;a27=7;a30=7;a31=7;a32=7;a33=7;a34=0;a35=0;a36=0;a37=0;a40=1;a41=1;a42=1;a43=1;a44=1;a45=1;a46=1;a47=1;a50=2;a51=2;a52=2;a53=2;a54=3;a55=3;a56=3;a57=3;a60=5;a61=5;a62=5;a63=5;a64=5;a65=5;a66=7;a67=7;a70=1;a71=1;a72=1;a73=1;a74=1;a75=1;a76=3;a77=3; cout像素值为:endl;for(m=0;mi;m+)for(n=0;nj;n+) coutamn ; coutendl;void show2(int a2020,int i,int j,int c20,int & g,int v20) int m, n , w,k,l=0; for(m=0;mi;m+) for(n=0;nj;) cout(amn,; w=1; cg+=amn; for(k=n+1;kj;k+) if(amn=amk) w+; else if(amn!=amk | w=j-n) coutw) ; vl+=w-1; break; n=k; if(n=j-1) coutw) ; vl+=w-1; coutendl; 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=0; for(i=0;ig;i+)for(k=0;km;k+)dik=0; for(i=0;i=0;k-) if(ci/2=0) dik=ci%2; ci=ci/2; else break;void bianma(int d2020,int c20,int f2020,int v20,int g,int m,int n)/编码 int i,k,j; zhuanhuan1(c,d,g,m);for(i=0;ig;i+)vi=vi+1; zhuanhuan1(v,f,g,n); cout 编码结果为：endl; for(i=0;ig;i+) for(k=0;km;k+) coutdik ; cout.; for(j=0;jn;j+) coutfij ; coutendl; void yima(int d2020,int f2020,int g,int m,int n) int i,j,k=0,s=0,tmp=0,t=0; int p20; int q20 ; cout开始译码:endl; for(i=0;ig;i+) pi=tmp=0; for(j=0;j0) tmp*=2; k-; pi+=tmp; if(dij%2!=0) pi=pi+dim-1; for(i=0;ig;i+) qi=tmp=0; for(j=0;j0) tmp*=2; k-; qi+=tmp; if(fij%2!=0) qi=qi+fin-1; for(i=0;ig;i+) for(j=0;jqi+1;j+) coutpi ;t+; if(t%8=0) coutendl; void main() int i,j,h,g=0,m,n;char x; int a2020; int c20; int v20; cout请输入灰度:h; duishu(h,m); cout请输入行数和列数：ij; duishu(j,n); create(a,i,j); show2(a,i,j,c,g,v); int d2020; int f2020;for(i=0;ig;i+)vi=vi-1; bianma(d,c