算术编码与游程编码1 .课题描述1.理解和掌握算术编码和游程编码的基本原理。
2.编程实现算术编码和游程编码的基本流程。
3.了解算术编码和游程编码的优缺点。
4.分析实验结果。
2 信源编码的相关介绍编码实质上是对信源的原始符号按一定规则进行的一种变换。
编码可分为信源编码和信道编码。
信源编码：以提高通信有效性为目的的编码。
通常通过压缩信源的冗余度来实现。
采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。
即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。
•信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。
–无失真信源编码定理：是离散信源/数字信号编码的基础；–限失真信源编码定理：是连续信源/模拟信号编码的基础。
•信源编码的分类：–离散信源编码：独立信源编码,可做到无失真编码；–连续信源编码：独立信源编码,只能做到限失真信源编码；–相关信源编码：非独立信源编码。
信源编码的作用之一是设法减少码元数目和降低码元速率，即通常所说的数据压缩：作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的数字化传输。
最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。
但现代通信应用中常见的信源编码方式有：Huffman编码、算术编码、L-Z编码，这三种都是无损编码，另外还有一些有损的编码方式。
信源编码的目标就是使信源减少冗余，更加有效、经济地传输，最常见的应用形式就是压缩。
另外，在数字电视领域，信源编码包括通用的MPEG—2编码和H.264（MPEG—Part10 AVC）编码等相应地，信道编码是为了对抗信道中的噪音和衰减，通过增加冗余，如校验码等，来提高抗干扰能力以及纠错能力。
•3 . 算术编码3.1算术编码算法算术编码在图像数据压缩标准中扮演了重要的角色, 是无损压缩的一种算术编码中用0和1之间的实数进行编码, 该编码用到两个基本的参数Α符号的概率和它的编码间隔信源符号的概率决定了压缩编码的效率, 也决定了编码过程中信源符号的间隔, 而这些间隔包含在0到1之间 编码过程中的间隔决定了符号压缩后的输出 算术编码的编码过程如下Α算术编码把一个信源集合表示为实数线上的0 到1 之间的一个区间。
这个集合中的每个元素都要用来缩短这个区间。
信源集合的元素越多,所得到的区间就越小,当区间变小时,就需要更多的数位来表示这个区间,这就是区间作为代码的原理。
算术编码首先假设一个信源的概率模型,然后用这些概率来缩小表示信源集的区间。
]设英文元音字母采用固定模式符号概率分配如下:设编码的数据串为eai 。
令high 为编码间隔的高端,low 为编码间隔的低端, range 为编码间隔的长度,rangelow 为编码字符分配的间隔低端,rangehigh 为编码字符分配的间隔高端。
初始high=1,low=0,range＝high-low, 一个字符编码后新的low 和high 按下式计算: ·low =low＋range × rangelow·high =low＋range×rangehigh(1) 在第一个字符e 被编码时,e 的rangelow＝0.2,rangehigh=0.5, 因此:low＝0 + 1 × 0.2 ＝0.2high=0 + 1 × 0.5 ＝0.5range=high－low=0.5－0.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.2high=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 <iostream.h>#include<math.h>#include <stdio.h>#define M 100#define N 4class suanshu{int count,length;char number[N],n;long double chance[N],c;char code[M];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(){cout<<"please input the number."<<endl;for(int i=0;i<N;i++){cin>>n;number[i]=n;}cout<<"please input the chance."<<endl;for(int i=0;i<N;i++){cin>>c;chance[i]=c;}if(i==20)cout<<"the number is full."<<endl;count=i;}void suanshu::get_code(){cout<<"please input the code’s length:";cin>>length;while(length>=M){cout<<"the length is too larger,please input a smaller one."; cin>>length;}for(int i=0;i<length;i++){cin>>code[i];}}void suanshu::coding(){long double tp;//从区间取数long double x=0.0;int i,j=0;for(i=0;i<count;i++)if(code[0]==number[i]) break;while(j<i)Low+=chance[j++];d=chance[j];High=Low+d;for(i=1;i<length;i++)for(j=0;j<count;j++){if(code[i]==number[j]){if(j==0){low=Low;high=Low+chance[j]*d;High=high;d*=chance[j];}else{float chance_l=0.0;for(int k=0;k<=j-1;k++)chance_l+=chance[k];low=Low+d*chance_l;high=Low+d*(chance_l+chance[j]);Low=low;High=high;d*=chance[j];}}else continue;}cout<<"the result is:"<<Low<<high<<endl; tp=(low+high)/2.0;//取区间的中点编码printf("\n选取的小数为：%.17f\n",tp);for(j=0;j<n;j++){tp=tp*2;if(tp>1.0){tp=tp-1;code[j]=1;}elsecode[j]=0;}printf("编码为：\n");//输出编码for(i=0;i<n;i++){printf("%d",code[i]);x+=code[i]*pow(2,(-i-1));}printf("\n恢复的小数为：%.17f",x);if((x>low)&&(x<high))//判断恢复的是否成功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’游程长度，这是一个随机变量。
