香浓编码

实验名称：实验四香农编码一、实验目的：加深对香农公式的理解及其具体的实现过程。

二、实验内容与原理：内容：计算二进制香农编码三、实验步骤1．分析香农公式的算法2．将香农公式的流程转换为具体的代码四、实验数据及结果分析(可附程序运行截图)编码的结果：平均码长和编码效率：五、代码附录clear;% c = strcat(a,b)字符串连接p=[0.25 0.25 0.2 0.15 0.1 0.05];P=fliplr(sort(p));%按大到小排序Pa=[0;0];%累加和的定义----第一行为累加和，第二行为Ki %求累加和for x=1for y=1:1:5%Pa(x,y)=1;Pa(x,y+1)=P(x,y)+ Pa(x,y);endend%ceil 是取向离它最近的大整数圆整for i=2for j=1:1:6Pa(i,j)=ceil( -log2(P(1,j)) );endend%信源熵H=0;L=0;for i=1:1:6H=H-P(i)*log2(P(i));L=L+P(i)*Pa(2,i);endu=H/L;disp('平均码长：；');disp(L);disp('编码效率：');disp(u);%求各符号的编码temp=[];%临时的编码值:1:6for m=1:1:6fprintf('a(%d):',m);for n=1:1:abs(Pa(2,m))temp(m,n)=Pa(1,m)*2;if temp(m,n)>=1O(m,n)=1;Pa(1,m)=temp(m,n)-1;elseO(m,n)=0;Pa(1,m)=temp(m,n);endfprintf('%d',O(m,n));endfprintf('\n');end六、其他：实验总结、心得体会及对本实验方法、手段及过程的改进建议等。

实验起初是想把累加和及Ki和编码放在一个二维矩阵中，但具体的实现较为复杂，所以最后改为逐行存放并成功完成了实验。

实验四 香农编码一、实验目的：掌握香农编码的方法二、实验内容：对信源123456,,,,,()0.250.250.020.150.10.05a a a a a a X P X ⎧⎫⎛⎫=⎨⎬ ⎪⎝⎭⎩⎭进行二进制香农编码。

并计算其平均码长，信源熵，和编码效率。

三、实验步骤（1）将信源符号按概率从大到小的顺序排列。

（2）用Pa （i ）表示第i 个码字的累加概率（3）确定满足下列不等式的整数K （i ），并令K （i ）为第i 个码字的长度22log ()()1log ()Pa i K i Pa i -≤<-（4）将Pa （i ）用二进制表示，并取小数点后K （i ）位最为a （i ）的编码四、实验数据及结果分析（1）将信源符号按概率从大到小的顺序排列。

P=（0.25 0.25 0.2 0.15 0.1 0.05）；（2）用Pa （i ）表示第i 个码字的累加概率。

Pa=（0 0.2500 0.5000 0.7000 0.8500 0.9500）（3）确定满足下列不等式的整数K （i ）。

K=（2 2 3 3 4 5）（4）将Pa （i ）用二进制表示，并取小数点后K （i ）位最为a （i ）的编码0001100101110111110（5）计算其平均码长，信源熵，和编码效率平均码长 L=2.7信源熵H=2.4232编码效率xiaolv=0.89749五、代码附录N=input('N='); %输入信源符号的个数s=0;L=0;H=0;Pa=zeros(1,6);for i=1:NP(i)=input('P=');%输入信源符号概率分布s=s+P(i);endif s~=1error('不符合概率分布');endP=sort(P,'descend');Pa(1)=0;for i=2:NPa(i)=Pa(i-1)+P(i-1);enddisp(Pa);for i=1:Na=-log2(P(i));if mod(a,1)==0 %计算第i个码字的长度K(i)=a;elseK(i)=fix(a+1);endL=L+P(i)*K(i); %计算平均码长H=H-P(i)*log2(P(i));%计算信源熵Endxiaolv=H/L; %计算编码效率for i=1:Nfor j=1:K(i)W(i,j)=fix(Pa(i)*2);Pa(i)=Pa(i)*2-fix(Pa(i)*2);fprintf('%d',W(i,j));endfprintf('\n');end六，实验总结：通过该实验，掌握了香农编码。

香农编码的原理-回复香农编码，也被称为经典编码或香农-福斯特编码，是一种用于无失真数据压缩的编码方法，由克劳德·香农于1948年提出。

该编码方法可以将信息通过二进制数据流传输，以尽可能少的比特数来表示。

为了理解香农编码的原理，需要先了解信息理论的一些基本概念。

首先是信息的概率和信息量。

信息的概率指的是某个事件发生的概率；而信息量是一种度量，表示以二进制形式表示的信息所需要的比特数。

根据信息量的定义，信息量与事件发生的概率成反比。

在香农编码中，我们将每个字符映射到一个唯一的二进制序列，以尽可能少的比特数来表示。

这个序列由两部分组成：前缀码和编码字。

前缀码是一种特殊的编码形式，其中没有任何一个编码字是另一个编码字的前缀。

这样可以确保在解码时不会出现歧义。

那么，如何构建香农编码呢？下面是一步一步的过程：1. 统计字符的出现频率：首先，对待编码的字符进行统计，计算每个字符在信息中出现的频率。

频率越高的字符，其信息量越小，因为它们出现的概率高。

2. 构建概率分布表：将字符按照出现频率的顺序排列，并计算每个字符的出现概率。

概率分布表的目的是为了确定每个字符在编码中所占的比特数。

3. 构建编码树：通过概率分布表，构建一棵编码树。

在构建编码树时，将概率最小的两个字符进行合并，形成一个新的节点，该节点的概率为这两个字符的概率之和。

重复这个过程，直到所有的字符都合并成一个节点。

4. 分配编码字：在编码树的每个分支上分配编码字。

一般来说，向左分支分配0，向右分支分配1。

将编码树中每个叶子节点的编码字串联起来，就是每个字符的编码。

5. 编码和解码：使用构建好的编码对信息进行编码。

在解码时，通过比较编码串与编码表中的编码，逐个识别并解码字符。

香农编码的优点在于，可以根据不同字符的频率分配变长的编码，减小了信息的传输成本。

在统计学上，香农编码接近于理论上的信息上限，即信息熵。

同时，通过构建前缀码，可以确保在解码时不会出现二义性。

香农编码计算简单例题香农编码是一种无损数据压缩算法，它通过为出现频率较高的符号分配较短的编码，而为出现频率较低的符号分配较长的编码，从而实现对数据进行压缩。

下面我将给出一个简单的例题来说明香农编码的计算过程。

假设我们有一个消息，由以下5个符号组成，A、B、C、D、E。

它们的出现频率分别是，A(0.4)、B(0.3)、C(0.2)、D(0.08)、E(0.02)。

首先，我们需要按照出现频率从高到低对符号进行排序：1. A(0.4)。

2. B(0.3)。

3. C(0.2)。

4. D(0.08)。

5. E(0.02)。

然后，我们为每个符号分配一个二进制编码。

编码的长度取决于符号的出现频率，频率越高，编码越短。

接下来，我们按照以下步骤计算香农编码：1. 将频率最高的符号A分配一个初始编码0。

2. 计算下一个符号B的编码。

由于A的编码长度为1，我们将B的编码设置为A的编码加上1，即编码为10。

3. 接着计算符号C的编码。

C的频率为0.2，小于A和B的频率之和(0.4+0.3=0.7)，所以C的编码长度应为2。

C的编码为B的编码加上1，即编码为11。

4. 然后计算符号D的编码。

D的频率为0.08，小于A、B和C的频率之和(0.4+0.3+0.2=0.9)，所以D的编码长度应为3。

D的编码为C的编码加上1，即编码为111。

5. 最后计算符号E的编码。

E的频率为0.02，小于A、B、C和D的频率之和(0.4+0.3+0.2+0.08=0.98)，所以E的编码长度应为3。

E的编码为D的编码加上1，即编码为1111。

最终，我们得到了每个符号的香农编码：A: 0。

B: 10。

C: 11。

D: 111。

E: 1111。

这样，我们就完成了对给定消息的香农编码计算。

需要注意的是，香农编码是一种理想情况下的编码方案，它假设消息中的符号是独立且符合特定的概率分布。

在实际应用中，可能会存在一些特殊情况需要进行调整。

此外，为了保证解码的正确性，编码和解码的过程需要进行同步。

二元香农编码（Binary Shannon Encoding）是一种用于数据压缩和通信的编码方法。

它基于香农信息理论，通过将输入数据转换为二进制形式，以实现更高的数据压缩和传输效率。

假设我们要对一组数据 "ABCD" 进行二元香农编码。

首先，我们需要确定每个字符的二进制位数。

对于一个由四个字符组成的数据，我们可以使用4位二进制来表示。

接下来，我们将每个字符转换为二进制形式。

对于字母 "A"，我们可以使用ASCII 码进行转换，得到二进制表示为 "0100"。

同理，我们可以得到 "B"、"C" 和 "D" 的二进制表示分别为 "0101"、"0110" 和 "0111"。

然后，我们将这些二进制位组合在一起，形成一个二进制数。

对于 "ABCD"，其二进制表示为 "0100 0101 0110 0111"。

因此，对于输入数据 "ABCD"，其二元香农编码为 "0100 0101 0110 0111"。

在接收端，我们可以将这些二进制位解码回原始的字符形式，即 "ABCD"。

总之，二元香农编码通过将输入数据转换为二进制形式，实现了更高的数据压缩和传输效率。

在处理大量数据时，它能够显著降低存储和传输成本。

信息论霍夫曼、香农-费诺编码LT二、实验原理：1、香农-费诺编码首先,将信源符号以概率递减的次序排列进来，将排列好的信源符号划分为两大组，使第组的概率和近于相同,并各赋于一个二元码符号”0”和”1”.然后，将每一大组的信源符号再分成两组，使同一组的两个小组的概率和近于相同，并又分别赋予一个二元码符号。

依次下去，直至每一个小组只剩下一个信源符号为止。

这样，信源符号所对应的码符号序列则为编得的码字。

译码原理，按照编码的二叉树从树根开始，按译码序列进行逐个的向其叶子结点走，直到找到相应的信源符号为止。

之后再把指示标记回调到树根，按照同样的方式进行下一序列的译码到序列结束。

如果整个译码序列能够完整的译出则返回成功，否则则返回译码失败。

2、霍夫曼编码霍夫曼编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。

同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。

生成霍夫曼编码算法基于一种称为“编码树”（coding tree）的技术。

算法步骤如下：（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。

（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。

（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。

（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。

三、实验环境matlab7.1四、实验内容1、对于给定的信源的概率分布，用香农-费诺编码实现图像压缩2、对于给定的信源的概率分布，用霍夫曼编码实现图像压缩五、实验过程1.香农-费诺编码编码1function c=shannon(p)%p=[0.2 0.15 0.15 0.1 0.1 0.1 0.1 0.1] %shannon(p)[p,index]=sort(p)p=fliplr(p)n=length(p)pa=0for i=2:npa(i)= pa(i-1)+p(i-1) endk=ceil(-log2(p))c=cell(1,n)for i=1:nc{i}=”tmp=pa(i)for j=1:k(i)tmp=tmp*2if tmp>=1tmp=tmp-1 c{i(j)='1'elsec{i}(j) = '0' endendendc = fliplr(c)c(index)=c编码2clc;clear;A=[0.4,0.3,0.1,0.09,0.07,0.04]; A=fliplr(sort(A));%降序排列[m,n]=size(A);for i=1:nB(i,1)=A(i);%生成B的第1列end%生成B第2列的元素a=sum(B(:,1))/2;for k=1:n-1ifabs(sum(B(1:k,1))-a)<=abs(sum(B(1:k+1, 1))-a)break;endendfor i=1:n%生成B第2列的元素if i<=kB(i,2)=0;elseB(i,2)=1;endend%生成第一次编码的结果END=B(:,2)';END=sym(END);%生成第3列及以后几列的各元素j=3;while (j~=0)p=1;while(p<=n)x=B(p,j-1);for q=p:nif x==-1break;elseif B(q,j-1)==xy=1;continue;elsey=0;break;endendif y==1q=q+1;endif q==p|q-p==1B(p,j)=-1;elseif q-p==2B(p,j)=0;END(p)=[char(END(p)),'0'];B(q-1,j)=1;END(q-1)=[char(END(q-1)),'1']; elsea=sum(B(p:q-1,1))/2;for k=p:q-2abs(sum(B(p:k,1))-a)<=abs(sum(B(p:k+1, 1))-a);break;endendfor i=p:q-1if i<=kB(i,j)=0;END(i)=[char(END(i)),'0'];elseB(i,j)=1;END(i)=[char(END(i)),'1'];endendendendendC=B(:,j);D=find(C==-1);[e,f]=size(D);if e==nj=0;elsej=j+1;endendBAENDfor i=1:n[u,v]=size(char(END(i))); L(i)=v;avlen=sum(L.*A)2. 霍夫曼编码function c=huffman(p)n=size(p,2)if n==1c=cell(1,1)c{1}=''returnend[p1,i1]=min(p)index=[(1:i1-1),(i1+1:n)] p=p(index)n=n-1[p2,i2]=min(p)index2=[(1:i2-1),(i2+1:n)] p=p(index2);i2=index(i2)index=index(index2)p(n)=p1+p2c=huffman(p)c{n+1}=strcat(c{n},'1')c{n}=strcat(c{n},'0') index=[index,i1,i2]c(index)=c。

香农编码
香农编码（Shannon coding）是一种基于信息论的无失真压缩算法。

它由克劳德·香农于1948年提出，是一种前缀
编码方法，用于将一串符号串压缩成更短的编码串。

香农编码的基本思想是根据符号的出现概率分配不同长度
的编码。

出现概率高的符号分配较短的编码，出现概率低
的符号分配较长的编码。

这样，编码串的平均长度就可以
降低，实现了数据的无失真压缩。

具体的步骤如下：
1. 计算每个符号的出现概率。

2. 按照概率从高到低对符号进行排序。

3. 给较高概率的符号分配较短的编码，较低概率的符号分
配较长的编码。

可以使用二叉树进行编码，每个符号对应
树上的一个叶子节点，编码为从根节点到叶子节点的路径。

4. 根据编码生成压缩后的编码串。

由于香农编码是一种无失真压缩算法，可以保证压缩后的数据能够完全恢复成原始数据。

然而，香农编码会导致编码长度不固定，需要附加一些额外的信息来标识编码的边界，这会增加一定的开销。

为了解决这个问题，后续发展出了其他压缩算法，如哈夫曼编码。

《信息论与编码》实验报告题目信源编码实验指导教师学院专业班级姓名学号日期目录一、香农编码 (3)实验目的 (3)实验要求 (3)编码算法 (3)调试过程 (3)参考代码 (4)调试验证 (7)实验总结 (7)二、哈夫曼编码 (8)实验目的 (8)实验原理 (8)数据记录 (9)实验心得 (10)一、香农编码3、Shannon 编码算法 1：procedure SHANNON(q,｛Pi ｝)2: 降序排列｛Pi ｝ 3: for i=1 q do 4: F(i s ) 5：i l 2[]log 1/()i p s 6：将累加概率F(i s )（十进制小数）变换成二进制小数。

7：取小数点后i l 个二进制数字作为第i 个消息的码字。

8：end for9：end procedure------------------------------------------------------------------------------------------------------------------4、调试过程1、fatal error C1083: Cannot open include file: 'unistd.h': No such file or directoryfatal error C1083: Cannot open include file: 'values.h': No such file or directory原因：unistd.h 和values.h 是Unix 操作系统下所使用的头文件纠错：删去即可2、error C2144: syntax error : missing ')' before type 'int'error C2064: term does not evaluate to a function原因：l_i(int *)calloc(n,sizeof(int)); l_i 后缺少赋值符号使之不能通过编译纠错：添加上赋值符号3、error C2018: unknown character '0xa1'原因：有不能被识别的符号纠错：在错误处将不能识别的符号改为符合C 语言规范的符号4、error C2021: expected exponent value, not ' '原因：if(fabs(sum-1.0)>DELTA); 这一行中DELTA 宏定义不正确11()i k k p s -=∑纠错：# define DELTA 0.0000015、error C2143: syntax error : missing ';' before '}'原因：少写了“;”号纠错：在对应位置添加上“;”号5、参考代码# include<stdio.h># include<math.h># include<stdlib.h># include<string.h># define DELTA 0.000001/*精度*/void sort(float*,int);/*排序*/int main(void){register int i,j;int n; /*符号个数*/int temp;/*中间变量*/float *p_i; /*符号的概率*/float *P_i; /*累加概率*/int *l_i; /*码长*/char * *C; /*码集合*//*用sum来检验数据，用p来缓存了中间数据*/float sum,p;/*输入符号数*/fscanf(stdin,"%d",&n);/*分配内存地址 */p_i=(float *)calloc(n,sizeof(float));P_i=(float *)calloc(n,sizeof(float));l_i=(int *)calloc(n,sizeof(int));/* 存储信道传输的概率*/for(i=0;i<n;i++)fscanf(stdin,"%f",&p_i[i]);/*确认输入的数据*/sum=0.0;for(i=0;i<n;i++)sum+=p_i[i];if(fabs(sum-(1.0))>DELTA)fprintf(stderr,"Invalid input data \n");fprintf(stdout,"Starting…\n\n");/*以降序排列概率*/sort (p_i,n);/*计算每个符号的码长*/for(i=0;i<n;i++){p=(float)(-(log(p_i[i])))/log(2.0);l_i[i]=(int)ceil(p);}/*为码字分配内存地址*/C=(char **)calloc(n,sizeof(char *));for(i=0;i<n;i++){C[i]=(char *)calloc(l_i[i]+1,sizeof(char));C[i][0]='\0';}/*计算概率累加和*/P_i[0]=0.0;for(i=1;i<n;i++)P_i[i]=P_i[i-1]+p_i[i-1];/*将概率和转变为二进制编码*/for(i=0;i<n;i++){for(j=0;j<l_i[i];j++){/*乘2后的整数部分即为这一位的二进制码元*/ P_i[i]=P_i[i]*2;temp=(int)(P_i[i]);P_i[i]=P_i[i]-temp;/*整数部分大于0为1，等于0为0*/if(temp==0)C[i]=strcat(C[i],"0");elseC[i]=strcat(C[i],"1");}}/*显示编码结果*/fprintf(stdout,"The output coding is :\n");for(i=0;i<n;i++)fprintf(stdout,"%s",C[i]); fprintf(stdout,"\n\n");/*释放内存空间*/for(i=n-1;i>=0;i--)free(C[i]);free(C);free(p_i);free(P_i);free(l_i);exit(0);}/*冒泡排序法*/void sort(float *k,int m){int i=1;/*外层循环变量*/int j=1;/*内层循环变量*/int finish=0;/*结束标志*/float temp;/*中间变量*/while(i<m&&!finish){finish=1;for(j=0;j<m-i;j++){/*将小的数后移*/if(k[j]<k[j+1]){temp=k[j];k[j]=k[j+1];k[j+1]=k[j];finish=0;}i++;}}}6、调试验证：程序结果：7、实验总结1949年香农在《有噪声时的通信》一文中提出了信道容量的概念和信道编码定理，为信道编码奠定了理论基础。