实验六 信源编码仿真实现
一、实验目的
理解信源编码的思想，掌握信源编码的编程实现原理及技术。
二、实验内容
1．随机产生二进制信源消息序列。
2．统计 2、4 次扩展信源的消息符号概率。
3．根据相应的概率进行信源编码。
4．生成编码序列。
5．计算编码效率。
6．对编码序列进行译码。
三、程序
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <math.h>
#define MAX 1000
typedef char ElemType;
typedef struct //树的结构体
{
ElemType elem; //元素类型；
unsigned int m_weight; //元素的权值
unsigned int parent,lchild,rchild; //结点
}HTNode,*HuffmanTree;
typedef char** HuffmanCode; //定义二维编码数组
typedef int Status;
typedef struct weight //字符结构体
{
char elem;
unsigned int m_weight;
}Weight;
void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);
void Select(HuffmanTree,int,int *,int *);
void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);
Status main(void)
{ int
i,j,k,m,n,wei,a0=0,a1=0,a00=0,a01=0,a10=0,a11=0,a0000=0,a0001=0,a0010=0,a0011=0,a0100=0,
a0101=0,a0110=0,a0111=0,a1000=0,a1001=0,a1010=0,a1011=0,a1100=0,a1101=0,a1110=0,a111
1=0;
char b[MAX];//存放信源的字符数组
char
c[16][5]={"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001","1010","10
11","1100","1101","1110","1111"};
char d[MAX/4][5];//存放长生信源的字符串数组
char *e[MAX/4];
float H=0,L=0,g,p0,p1;
float h[16],p[16],l[16],l1[16];
HuffmanTree HT;
HuffmanCode HC;
Weight *w;
/*产生消息序列*/
time_t t;
srand((unsigned) time(&t));
printf("产生消息序列为：\n");
for(i=0; i<MAX; i++)
{k=rand() % 5;
if(k==0||k==1||k==2) {m='0';a0++;}
else {m='1';a1++;}
printf("%c",m);
b[i]=m;
}p0=(float)a0/MAX;p1=(float)a1/MAX;
printf("\n");
printf("信源符号 0 或 1 的产生概率为：");
printf("p(0)=%.4f p(1)=%.4f\n\n\n",p0,p1);
/*统计 2 次扩展信源概率*/
for(i=0; i<MAX; i++)
{if(b[i]=='0')
{i++;
if(b[i]=='0') a00++;
else a01++;
}
else
{i++;
if(b[i]=='0') a10++;
else a11++;
}
}
printf("2 次扩展信源的概率为：");
printf("p(00)=%.3f p(01)=%.3f p(10)=%.3f
p(11)=%.3f\n",(float)2*a00/MAX,(float)2*a01/MAX,(float)2*a10/MAX,(float)2*a11/MAX);
/*统计 4 次扩展信源的概率*/
for(i=0; i<MAX; i++)
{if(b[i]=='0')
{i++;
if(b[i]=='0')
{i++;
if(b[i]=='0')
{i++;
if(b[i]=='0') a0000++;
else a0001++;}
else
{i++;
if(b[i]=='0') a0010++;
else a0011++;}
}
else
{i++;
if(b[i]=='0')
{i++;
if(b[i]=='0') a0100++;
else a0101++;}
else
{i++;
if(b[i]=='0') a0110++;
else a0111++;}}
}
else
{i++;
if(b[i]=='0')
{i++;
if(b[i]=='0')
{i++;
if(b[i]=='0') a1000++;
else a1001++;}
else
{i++;
if(b[i]=='0') a1010++;
else a1011++;}
}
else
{i++;
if(b[i]=='0')
{i++;
if(b[i]=='0') a1100++;
else a1101++;}
else
{i++;
if(b[i]=='0') a1110++;
else a1111++;}}}
}
printf("4 次扩展信源的概率为：\n");
printf(" p(0000)=%.3f p(0001)=%.3f p(0010)=%.3f p(0011)=%.3f\n p(0100)=%.3f
p(0101)=%.3f p(0110)=%.3f p(0111)=%.3f\n p(1000)=%.3f p(1001)=%.3f p(1010)=%.3f
p(1011)=%.3f\n p(1100)=%.3f p(1101)=%.3f p(1110)=%.3f
p(1111)=%.3f\n",(float)4*a0000/MAX,(float)4*a0001/MAX,(float)4*a0010/MAX,(float)4*a0011
/MAX,(float)4*a0100/MAX,(float)4*a0101/MAX,(float)4*a0110/MAX,(float)4*a0111/MAX,(flo
at)4*a1000/MAX,(float)4*a1001/MAX,(float)4*a1010/MAX,(float)4*a1011/MAX,(float)4*a110
0/MAX,(float)4*a1101/MAX,(float)4*a1110/MAX,(float)4*a1111/MAX);
printf("\n");printf("\n");
n=16;
w=(Weight *)malloc(n*sizeof(Weight));
w[0].m_weight=a0000;w[1].m_weight=a0001;w[2].m_weight=a0010;w[3].m_weight=a0011;
w[4].m_weight=a0100;w[5].m_weight=a0101;w[6].m_weight=a0110;w[7].m_weight=a0111;
w[8].m_weight=a1000;w[9].m_weight=a1001;w[10].m_weight=a1010;w[11].m_weight=a1011;
w[12].m_weight=a1100;w[13].m_weight=a1101;w[14].m_weight=a1110;w[15].m_weight=a1111
;
for(i=0;i<16;i++)
{
w[i].elem=i;
}
printf("信源 0000--1111 依次出现的次数为：");
for(i=0;i<n;i++)
{printf("%d ",w[i].m_weight);
}
HuffmanCoding(&HT,&HC,w,16);
printf("\n 序号\t4 次扩展信源\t 出现次数\t 霍夫曼编码\n");
for(i=1;i<=n;i++)
printf("%d\t %s\t\t %d\t\t %s\n",i,c[i-1],w[i-1].m_weight,HC[i]);
/*编码序列输出*/
for(i=0;i<MAX/4;i++)
{for(j=0;j<5;j++) d[i][j]=b[4*i+j];d[i][4]='\0';
}
printf("编码序列输出为\n");
for(i=0;i<MAX/4;i++)
{for(j=0;j<17;j++)
if(strcmp(d[i],c[j-1])==0) {printf("%s ",HC[j]);e[i]=HC[j];}
}printf("\n");
/*计算编码效率*/
for(i=0;i<16;i++)
{p[i]=(float)4*w[i].m_weight/MAX;
if(p[i]==0) h[i]=0;
else h[i]=p[i]*(log(1/p[i])/log(2));
H=H+h[i];}
for(i=0;i<16;i++)
{l[i]=strlen(HC[i+1]);l1[i]=4*w[i].m_weight*l[i]/MAX;L=L+l1[i];}
g=H/L;printf("编码效率η=%.4f\n",g);
/*译码*/
printf("译码为：");
for(i=0;i<MAX/4;i++)
{
for(j=1;j<17;j++)
if(strcmp(e[i],HC[j])==0) printf("%s ",c[j-1]);
}
printf("\n");
getchar();
}
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)
{
int i,m,s1,s2,start,c,f;
