信息论与编码实验报告 费诺编码_信息论与编码实验
时间：2020-08-03 21:36:06 来源：天一资源网 本文已影响 人 
哈尔滨理工大学荣成学院
信息论与编码实验报告
——费诺编码
班级： 电信12-1班
姓名： 李 赛
学号： 1230160109
日期： 2015.6.17
费诺编码
C语言代码：
#include<stdio.h>
#include<math.h>
#include <string.h>
static char p[20][20];
void Fano(int m,int n,float y[20]);
main()
{
int i,j,flag,count,b[20]; //count:信源符号个数,b[]: 码长
float a[20],temp,sum=0.0,l=0.0,H=0.0,y,R; // a[]：输入概率分布 l:平均码长 H：信源熵 y:编码效率 R:信源信息率
flag=0; //flag:输入概率的判断标志位。为0时表示输入概率有误
/************ 输入信源符号个数并判断是否是正数 ******************/
printf("Please input the amount of probabilities\n");
scanf("%d",&count);
while(count<=0)
{
printf("Please input the positive number! Try again!\n");
printf("Please input the amount of probabilities\n");
scanf("%d",&count);
}
/*************** 输入信源输入概率并判断 *****************/
while(flag==0)
{
flag=1;
printf("Please input all probabilities!\n");
for(i=1;i<=count;i++)
{
scanf("%f",&a[i]);
if((a[i]<0)||(a[i]>1)) //判断单个概率是否小于0或大于1
{
printf("Please input the number between 0 and 1\n");
flag=0;
}
else sum=sum+a[i];
}
if(sum>1.0000001||sum<0.9999999) //判断概率和是否大于1或小于0
{
printf(" the sum of all the numbers is %lf not 1!\n",sum);
flag=0;
sum=0.0;
}
}
/************ 冒泡排序，由大到小 ***************************/
for(i=1;i<count;i++)
{
for(j=i+1;j<count+1;j++)
{
if(a[i]<a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
Fano(1,count,a); //调用费诺编码
for (i=1;i<=count;i++)//求码长
{
b[i]=strlen(p[i]);
}
/**************** 输出编码 **********************/
printf("\nThe fano code is:\n");
printf("Probability\t\tFano code\t\tcode length\n");
for(i=1;i<=count;i++)
{
printf("%.3f\t\t\t",a[i]);
printf("%s\t\t\t%d\n",p[i],b[i]);
}
/*************** 计算平均码长 *******************/
for(i=1;i<=count;i++)
{
l+=a[i]*b[i];
}
printf("The average length of code is: ");
printf("%5.2fbit/symbol\n",l);
/***************** 计算信源熵 *********************/
for(i=1;i<=count;i++)
{
H+=-a[i]*(log(a[i])/log(2));
}
printf("The source entropy is: ");
printf("%5.2fbit/symbol\n",H);
/******************** 计算信源信息率 *******************/
R=l*(log(2)/log(2));
printf("The rate of transport is: ");
printf("%5.2f\n",R);
/************** 计算编码效率(百分制表示) *****************/
y=H/R;
printf("The coding efficiency is: ");
printf("%5.2f%%\n",y*100);
}
/********** 费诺编码子函数 **********************/
void Fano(int m,int n,float y[20]) // m:各个组的初始点 n:各个组的结束点 y[]：经过从大到小排序后，各个组的元素
{
int i,k; //k:当前点位置
float sum=0.0,s=0.0,s1;
//sum:组内元素之和 s：初始点到k的组内元素的和 s1:从初始点到k-1的组内元素的和
if(m==n) return;//组内元素只有一个，不用再分
for(i=m;i<=n;i++) //组内元素求和
{
sum=sum+y[i];
}
k=m;
while(s<=sum-s) //判断组内元素依次累加，是否达到组和的一半
{
s1=s;
s=s+y[k++];
}
if((sum-2*s1)<=(2*s-sum))//判断两组和是否是最接近
{
k--;
}
for(i=m;i<k;i++) //分组后在上方的一组概率编码为0
{
strcat(p[i],"0");
}
for(i=k;i<=n;i++) //分组后在下方的一组概率编码为1
{
strcat(p[i],"1");
}
Fano(m,k-1,y); // 对分组后的上方的概率再一次分组
Fano(k,n,y); //对分组后的下方的概率再一次分组
}
程序流程图：
主函数
开始
开始
输入信源符号个数
输入信源符号个数count及对应概率a[i]的概率P
检测符号个数概率分布是否有错误
检测符号个数概率分布是否有错误
冒泡排序（由大到小）
冒泡排序（由大到小）
调用费诺编码子函数
调用费诺编码子函数
通过
通过strlen（）函数求码长
根据公式计算平均码长，信源熵，信源信息率，编码效率
根据公式计算平均码长，信源熵，信源信息率，编码效率
输
输出
终止
终止
子函数：
通过strcat（）函数给第一组码字为0，第二组码字为1分组点即第一个编号？分组点为该组倒数第二个？通过累加求和确定分组后每组概率累加尽可能相近或相等组内元素个数是否为
通过strcat（）函数给第一组码字为0，第二组码字为1
分组点即第一个编号？
分组点为该组倒数第二个？
通过累加求和确定分组后每组概率累加尽可能相近或相等
组内元素个数是否为1
F
T
分组点为新分组的第一个编号，其他依次
分组点为新分组的第一个编号，其他依次...
输出 T T F F分组点为新分组的第一个编号，其他依次...以分组点为断点，
输出
T
T
F
F
分组点为新分组的第一个编号，其他依次...
以分组点为断点， 重新编号分为两组
算法分析：
1.子函数递归调用
2.算法基本原理
1）将概率按从大到小的顺序排列；?
2）按编码进制数将概率分组，使每组概率和尽可能接近或相等；?
如编二进制码就分成两组，编m进制就分成m组
3）给每组分配一位码元；?
4）将每一分组再按同样原则划分，重复2、3，直到概率不再可分为止。
相关关键词： 集中式饮用水水源编码 数字编码教学反思 编码器测长度 编码 编码器
