博客

香农编码分为五个步骤：

1. 将信源消息符号按其出现的概率大小依次排列为：

2.  确定满足下列不等式的整数码长

3. 为了编成唯一可译码，计算第i个消息的累加概率

4. 将累加概率

变换成二进制数

5. 取

二进制数的小数点后

位即为该消息符号的二进制码字

#include <stdio.h>
#include <math.h>
#include <string.h>
int i,j;
int n; // n是信源符号个数
char codeAll[20]; // 计算过程中的编码

struct xiangnong {
	char s[20]; //信源符号的表示形式 a1 a2 a3 ...
	float p; // 符号概率
	float pa; // 累积概率
	float length_f;
	int length; // 码长
	char code[20]; // 最终的编码
	float Hx; // 信源熵 
	float K; // 平均码长
	float E; // 效率 
} data[20]; // 结构体数组data

// 排序算法 将符号概率按从大到小的顺序排列
void sequ(struct xiangnong x[],int n) {
	struct xiangnong temp;
	for(i=0; i<n; i++) {
		for(j=i; j<n; j++) {
			if(x[i].p<x[j].p) {
				temp=x[j];
				x[j]=x[i];
				x[i]=temp;
			}
		}
	}
}

// 计算码长
void countlength(struct xiangnong x[],int n) {
	for(i=0; i<n; i++) {
		x[i].length_f=-log(x[i].p)/log(2);
		if((x[i].length_f-(int)x[i].length_f)>0) {
			x[i].length=(int)x[i].length_f+1;
		} else {
			x[i].length=(int)x[i].length_f;
		}
	}
}

// 计算累加概率
void countpa(struct xiangnong x[],int n) {
	float a=0;
	x[0].pa=0;
	for(i=0; i<n; i++) {
		a+=x[i].p;
		x[i+1].pa=a;
	}
}

// 将累积概率(十进制)转为二进制数，截取码长位 （将累计概率和码长作为参数传入）
void covbit(float d,int lc) {
	for(j=0; j<lc; j++) {
		codeAll[j]=(int)(d*2)+48;
		d=2*d-(int)(d*2);
	}
}

// 计算信源熵
void entropy(struct xiangnong x[],int n) {
	float h=0;
	for(i=0; i<n; i++) {
		h-=x[i].p * (log(x[i].p) / log(2));
	}
	x->Hx=h;
}

// 计算平均码长
void averageLength(struct xiangnong x[],int n){
	float l=0;
	for(i=0; i<n; i++){
		l += x[i].p * x[i].length;
	}
	x->K=(l/1)*(log(2)/log(2));
}

// 计算编码效率 
void efficiency(struct xiangnong x[]){
	data->E=data->Hx/float(data->K);
}

main() {
	printf("请输入信源符号的个数:n=");
	scanf("%d",&n);
	printf("\n");
	printf("请输入每个信源符号的表示形式：\n");
	for(i=0; i<n; i++) {
		scanf("%s",&data[i].s);
	}
	printf("\n");
	for(i=0; i<n; i++) {
		printf("p(%s)=",data[i].s);
		scanf("%f",&data[i].p);
	}
	printf("\n");
	sequ(data,n); // 排序
	countlength(data,n); // 计算码长
	countpa(data,n); // 计算累加概率
	for(i=0; i<n; i++) {
		covbit(data[i].pa,data[i].length);
		strcpy(data[i].code,codeAll);
	}
	for(i=0; i<n; i++) {
		printf("p(%s)=%f\t pa=%f\t length=%d\t code=%s\n",data[i].s,data[i].p,data[i].pa,data[i].length,data[i].code);
	}
	printf("\n");
	entropy(data,n);
	printf("信源熵hx=%f\n",data->Hx);
	averageLength(data,n);
	printf("平均码长K=%f\n",data->K);
	efficiency(data);
	printf("编码效率E=%f",data->E);
}