信息论算术编码

实验三算术编码一、实验目的1．进一步学习C++语言概念和熟悉VC 编程环境。

2．学习算术编码基本流程, 学会调试算术编码程序。

3. 根据给出资料，自学自适应0 阶算术编、解码方法。

二、实验内容与原理（一）实验原理：1．算术编码基本原理这是将编码消息表示成实数0 和1 之间的一个间隔，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。

算术编码用到两个基本的参数：符号的概率和它的编码间隔。

信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。

编码过程中的间隔决定了符号压缩后的输出。

首先借助下面一个简单的例子来阐释算术编码的基本原理。

考虑某条信息中可能出现的字符仅有a b c 三种，我们要压缩保存的信息为bccb。

在没有开始压缩进程之前，假设对a b c 三者在信息中的出现概率一无所知（采用的是自适应模型），暂认为三者的出现概率相等各为1/3，将0 - 1 区间按照概率的比例分配给三个字符，即a 从0.0000 到0.3333，b 从0.3333 到0.6667，c 从0.6667 到1.0000。

进行第一个字符b编码，b 对应的区间0.3333 -0.6667。

这时由于多了字符b，三个字符的概率分布变成：Pa = 1/4，Pb = 2/4，Pc = 1/4。

按照新的概率分布比例划分0.3333 - 0.6667 这一区间，划分的结果可以用图形表示为：+-- 0.6667 Pc = 1/4 | +-- 0.5834 | | Pb = 2/4 | | | +-- 0.4167 Pa = 1/4 | +-- 0.3333 接着拿到字符c，现在要关注上一步中得到的c 的区间0.5834 -0.6667。

新添了c 以后，三个字符的概率分布变成Pa = 1/5，Pb = 2/5，Pc = 2/5。

用这个概率分布划分区间0.5834 - 0.6667：+-- 0.6667 | Pc = 2/5 | +-- 0.6334 | Pb = 2/5 || +-- 0.6001 Pa = 1/5 | +-- 0.5834 输入下一个字符c，三个字符的概率分布为：Pa = 1/6，Pb = 2/6，Pc = 3/6。

1.判定唯一可译码2.LZw 编码3.算数编码一 判定唯一可译码1．任务说明输入：任意的一个码(即已知码字个数及每个具体的码字)输出：判决结果（是/不是）输入文件:in1.txt ，含至少2组码，每组的结尾为”$”符输出文件:out1.txt ，对每组码的判断结果说明：为了简化设计，可以假定码字为0，1串2．问题分析、实现原理、流程图参考算法伪代码：For all ,i j W W C ∈ doif i W 是j W 的前缀 then将相应的后缀作为一个尾随后缀放入集合0F 中End ifEnd forLoopFor all i W C ∈ doFor all j n W F ∈ doif i W 是j W 的前缀 then将相应的后缀作为一个尾随后缀放入集合1n F +中Else if j W 是i W 的前缀 then将相应的后缀作为一个尾随后缀放入集合1n F +中End ifEnd forEnd fori i F F ←If ,i i W F W C ∃∈∈ thenReturn falseElse if F 中未出现新的元素 thenReturn trueEnd if//能走到这里，说明F 中有新的元素出现，需继续End loop3．实现源码#include <iostream>#include <string>using namespace std;struct strings{char *string;struct strings *next;};struct strings Fstr, *Fh, *FP;//输出当前集合void outputstr(strings *str){do{cout<<str->string<<endl;str = str->next;}while(str);cout<<endl;}inline int MIN(int a, int b){ return a>b?b:a; }inline int MAX(int a, int b){ return a>b?a:b; }#define length_a (strlen(CP))#define length_b (strlen(tempPtr))//判断一个码是否在一个码集合中，在则返回0，不在返回1int comparing(strings *st_string,char *code){while(st_string->next){st_string=st_string->next;if(!strcmp(st_string->string,code))return 0;}return 1;}//判断两个码字是否一个是另一个的前缀，如果是则生成后缀码void houzhui(char *CP,char *tempPtr){if (!strcmp(CP,tempPtr)){cout<<"集合C和集合F中有相同码字:"<<endl<<CP<<endl<<"不是唯一可译码码组!"<<endl;exit(1);}if (!strncmp(CP, tempPtr, MIN(length_a,length_b))){struct strings *cp_temp;cp_temp=new (struct strings);cp_temp->next=NULL;cp_temp->string=new char[abs(length_a-length_b)+1];char *longstr;longstr=(length_a>length_b ? CP : tempPtr);//将长度长的码赋给longstr //取出后缀for (int k=MIN(length_a,length_b); k<MAX(length_a,length_b); k++) cp_temp->string[k - MIN(length_a,length_b)]=longstr[k];cp_temp->string[abs(length_a-length_b)]=NULL;//判断新生成的后缀码是否已在集合F里，不在则加入F集合if(comparing(Fh,cp_temp->string)){FP->next=cp_temp;FP=FP->next;}}}void main(){//功能提示和程序初始化准备cout<<"\t\t唯一可译码的判断!\n"<<endl;struct strings Cstr,*Ch, *CP,*tempPtr;Ch=&Cstr;CP=Ch;Fh=&Fstr;FP=Fh;char c[]="C :";Ch->string=new char[strlen(c)];strcpy(Ch->string, c);Ch->next=NULL;char f[]="F :";Fh->string=new char[strlen(f)];strcpy(Fh->string, f);Fh->next=NULL;//输入待检测码的个数int Cnum;cout<<"输入待检测码的个数:";cin>>Cnum;cout<<"输入待检测码"<<endl;for(int i=0; i<Cnum; i++){cout<<i+1<<" ：";char tempstr[10];cin>>tempstr;CP->next=new (struct strings);CP=CP->next;CP->string=new char[strlen(tempstr)] ;strcpy(CP->string, tempstr);CP->next = NULL;}outputstr(Ch);CP=Ch;while(CP->next->next){CP=CP->next;tempPtr=CP;do{tempPtr=tempPtr->next;houzhui(CP->string,tempPtr->string);}while(tempPtr->next);}outputstr(Fh);struct strings *Fbegin,*Fend;Fend=Fh;while(1){if(Fend == FP){cout<<"是唯一可译码码组!"<<endl;exit(1);}Fbegin=Fend;Fend=FP;CP=Ch;while(CP->next){CP=CP->next;tempPtr=Fbegin;for(;;){tempPtr=tempPtr->next;houzhui(CP->string,tempPtr->string);if(tempPtr == Fend)break;}}outputstr(Fh);//输出F集合中全部元素}}4.运行结果：输入、输出及结果分析5．设计体会通过对判定唯一可译码算法的实现，我进一步了解判定唯一可译码缩的基本原理及过，体会到了其重要性,同时也锻炼了我独立分析问题以及解决问题的能力,这次课程设计让我深刻认识到了自己编程能力的不足，在以后的学习中要加强自己的编程能力。

信息论算术编码课程设计一、课程目标知识目标：1. 学生理解信息论中编码的基本概念，掌握算术编码的原理和步骤。

2. 学生能够运用算术编码方法对给定数据进行编码和解码。

3. 学生了解算术编码在信息传输和压缩中的应用。

技能目标：1. 学生掌握算术编码的具体算法，能够运用编程语言实现算术编码过程。

2. 学生具备分析数据特点并选择合适编码方法的能力，提高信息处理的效率。

情感态度价值观目标：1. 学生培养对信息论和编码技术的兴趣，激发学习主动性和创新意识。

2. 学生认识到编码技术在现代通信和计算机领域的重要性，增强对科技进步的敬畏感。

3. 学生通过团队协作解决问题，培养合作精神和沟通能力。

分析课程性质、学生特点和教学要求：本课程为高中信息技术学科，旨在帮助学生掌握信息论中算术编码的知识。

考虑到学生已具备一定的数学基础和编程能力，课程将重点放在算术编码的原理、实现和应用上。

教学要求注重理论与实践相结合，鼓励学生动手实践和团队协作，培养解决问题的能力。

课程目标分解为具体学习成果：1. 学生能够阐述算术编码的原理和步骤。

2. 学生能够运用编程语言实现算术编码，并成功解码。

3. 学生能够分析不同编码方法的优缺点，选择合适的方法进行信息传输和压缩。

4. 学生通过小组合作，共同完成算术编码的实际应用案例，提升团队协作能力。

二、教学内容1. 算术编码基本概念：信息论基础，编码的基本原理，算术编码的定义和特点。

- 教材章节：第三章第二节“编码方法及其应用”2. 算术编码原理与步骤：算术编码的数学模型，编码和解码的详细步骤。

- 教材章节：第三章第三节“算术编码的原理与实现”3. 编程实现算术编码：利用编程语言（如Python）实现算术编码的算法。

- 教材章节：第三章第四节“算术编码的编程实现”4. 算术编码的应用案例分析：分析实际应用中的算术编码案例，如文件压缩、图像传输等。

- 教材章节：第三章第五节“算术编码的应用实例”5. 编码方法比较与选择：比较算术编码与其他编码方法（如哈夫曼编码、LZ77等）的优缺点，讨论不同场景下的编码选择。

华侨大学工学院实验报告课程名称：信息论与编码实验项目名称：算术编码学院：工学院专业班级：11级信息工程姓名：学号：1195111016指导教师：傅玉青2013年11月25日一、实验目的（1）进一步熟悉算术编码算法（2）掌握MATLAB语言程序设计和调试过程中数值的进制转换、数值与字符串之间的转换等技术。

二、实验仪器（1）计算机（2）编程软件MATLAB三、实验原理算术编码是图像压缩的主要算法之一。

是一种无损数据压缩方法，也是一种熵编码的方法。

和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足(0.0 ≤ n < 1.0)的小数n。

当所有的符号都编码完毕，最终得到的结果区间即唯一的确定了已编码的符号串行。

任何人使用该区间和使用的模型参数即可以解码重建得到该符号串行。

实际上我们并不需要传输最后的结果区间，实际上，我们只需要传输该区间中的一个小数即可。

在实用中，只要传输足够的该小数足够的位数（不论几进制），以保证以这些位数开头的所有小数都位于结果区间就可以了。

四、实验内容及步骤（1）计算信源符号的个数n（2）将第i （i=1~n ）个信源符号变换成二进制数（3）计算i （i=1~n ）个信源符号的累加概率Pi 为()11i i k k P p a -==∑（4）预先设定两个存储器，起始时令()()1,0A C φφ==，φ表示空集（5）按以下公式迭代求解C 和A()()()()(),,r rC S r C S A S P A S r A S p =+=对于二进制符号组成的序列，r=0，1。

注意事项：计算C （S ，r ）时的加法运用的是二进制加法（6）计算序列S 编码后的码长度L 为()21log L p S ⎡⎤=⎢⎥⎢⎥ （7）如果C 在第L 位后没有尾数，则C 的小数点后L 位即为序列S 的算术编码；如果C 在第L 位后有尾数，则取C 的小数点后L 位，再进位到第L 位，即为序列S 的算术编码。

数学中的信息论与编码理论数学建模信息论与编码理论是数学中重要的分支领域，旨在研究信息传输和存储的原理与方法。

数学建模在该领域的应用，不仅可以提供对信息传输的理论分析，还可以设计和优化编码方案。

本文将从数学建模的角度，探讨信息论与编码理论在数学中的应用。

一、信息论的基本概念和理论模型信息论是由香农于1948年提出的，用于量化信息的度量和信息传输的极限。

信息的度量单位称为比特，用来表示信息的多少和信息源的不确定性。

信息的传输受到噪声的干扰，因此需要利用编码方法来提高传输的可靠性。

信息论的基本概念包括熵、条件熵、联合熵等。

熵是衡量信息不确定性的度量，表示一个随机变量的平均信息量。

条件熵是在已知一些信息的情况下，对另一个随机变量的平均信息量。

联合熵是两个变量同时出现时的平均信息量。

二、信息论在数据压缩中的应用数据压缩是信息论中的一个重要应用领域，目的是用较少的比特数来表示大量的信息。

常见的压缩方法有无损压缩和有损压缩两种。

无损压缩是指压缩后的数据可以完全恢复成原始数据，常用的方法有霍夫曼编码和算术编码。

霍夫曼编码通过构建最优前缀码，将出现频率较高的符号用较短的编码表示，出现频率较低的符号用较长的编码表示，从而实现数据的无损压缩。

算术编码则是通过将整个数据流映射到一个区间来进行压缩。

有损压缩是指压缩后的数据不完全能够恢复成原始数据，但在保证主要信息不丢失的前提下，减少数据量。

常用的方法有离散余弦变换（DCT）和小波变换。

离散余弦变换在图像和音频压缩中广泛应用，通过将时域信号转换为频域信号，然后舍弃高频分量，实现数据的有损压缩。

小波变换也是一种多尺度分析方法，可以在时频域上进行信号分析和压缩。

三、编码理论的基本原理和应用编码理论是信息论的重要分支，主要研究编码和解码的原理与方法，用于实现可靠的信息传输。

编码理论主要包括信道编码和解码、错误检测和纠正等。

信道编码主要用于提高信道传输的可靠性，常用的编码方法有海明码和卷积码。