费诺编码

费诺编码基本原理

首先，将信源符号以概率递减的次序排列进来，将排列好的信源符号划分为两大组，使第组的概率和近于相同，并各赋于一个二元码符号”0”和”1”.然后，将每一大组的信源符号再分成两组，使同一组的两个小组的概率和近于相同，并又分别赋予一个二元码符号。依次下去，直至每一个小组只剩下一个信源符号为止。这样，信源符号所对应的码符号序列则为编得的码字。译码原理，按照编码的二叉树从树根开始，按译码序列进行逐个的向其叶子结点走，直到找到相应的信源符号为止。之后再把指示标记回调到树根，按照同样的方式进行下一序列的译码到序列结束。如果整个译码序列能够完整的译出则返回成功，否则则返回译码失败。

费诺编码的方法

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

2.将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。

3.将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。

4.如此重复，直至每个组只剩下一个信源符号为止。

5.信源符号所对应的码字即为费诺码。

程序实现

Matlab实现

编码如下：

clc;

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:n

B(i,1)=A(i);%生成B的第1列

end

%生成B第2列的元素

a=sum(B(:,1))/2;

for k=1:n-1

if abs(sum(B(1:k,1))-a)<=abs(sum(B(1:k+1,1))-a)

break;

end

end

for i=1:n%生成B第2列的元素

if i<=k

B(i,2)=0;

else

B(i,2)=1;

end

end

%生成第一次编码的结果

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:n

if x==-1

break;

else

if B(q,j-1)==x

y=1;

continue;

else

y=0;

break;

end

end

end

if y==1

q=q+1;

end

if q==p|q-p==1

B(p,j)=-1;

else

if q-p==2

B(p,j)=0;

END(p)=[char(END(p)),'0'];

B(q-1,j)=1;

END(q-1)=[char(END(q-1)),'1'];

else

a=sum(B(p:q-1,1))/2;

for k=p:q-2

if abs(sum(B(p:k,1))-a)<=abs(sum(B(p:k+1,1))-a);

break;

end

end

for i=p:q-1

if i<=k

B(i,j)=0;

END(i)=[char(END(i)),'0'];

else

B(i,j)=1;

END(i)=[char(END(i)),'1'];

end

end

end

end

p=q;

end

C=B(:,j);

D=find(C==-1);

[e,f]=size(D);

if e==n

j=0;

else

j=j+1;

end

end

B

A

END

for i=1:n

[u,v]=size(char(END(i)));

L(i)=v;

end

avlen=sum(L.*A)

C++实现

/*FenoEncoding*/

#include

#include

#include

#include

using namespace std;

#define MaxStrLength 50 /*输入字符串的最大长度*/

#define MaxNode 24 /*设定最大不重复符号个数*/

#define MaxBit 5 /*设定最大编码长度*/

typedef struct{

char Character; /*字符*/

float data; /*字符的概率值*/

int bit[MaxBit]; /*编码后的码字*/

int length; /*码字长度*/

}CodeType;

CodeType FanoNode[MaxNode]; /*定义结构体数组*/

int Group(CodeType FanoNode[],int low,int high){ /*一次分组(一分为二)并编码*/

float MinSum=FanoNode[low].data,MaxSum=FanoNode[high].data;

FanoNode[low].bit[FanoNode[low].length++]=1;

FanoNode[high].bit[FanoNode[high].length++]=0;

while(low+1

if(MinSum>MaxSum){

MaxSum+=FanoNode[--high].data;

FanoNode[high].bit[FanoNode[high].length++]=0; /*编码加0*/

}

else{

MinSum+=FanoNode[++low].data;

FanoNode[low].bit[FanoNode[low].length++]=1; /*编码加1*/

}

}

return low; /*返回分组的第一部分的上界*/

}

void Disp(CodeType FanoNode[],int m,char str[],int SLength){ /*输出函数*/

float K=0,R=0,H=0;

printf("MessageSymbol Character

Probability

CodeLength

Code\n");

for(int i=0;i

printf("FanoNode[%d]

%c

%.2f",i,FanoNode[i].Character,FanoNode[i].data);

printf("

%d

",FanoNode[i].length);

for(int j=0;j

printf("%d",FanoNode[i].bit[j]); printf("\n");

K+=FanoNode[i].data*FanoNode[i].length; /*求平均码长*/

H+=-FanoNode[i].data*log(FanoNode[i].data); /*求H(X)的大小*/

}

printf("The code of the string is\n"); /*输出整个字符串的编码*/

for(i=0;i

for(int k=0;k

if(FanoNode[k].Character==str[i]){

for(int j=0;j

printf("%d",FanoNode[k].bit[j]);

break;

}

R=H/K; /*求信息传输速率*/

printf("\nThe average length of code is %.3f\n",K);

printf("The rate of transport is %.3f\n",R);

}

int IsnotIn(char a,char t[],int n,int count[]){ /*检查字符a是否在数组t[]中*/

for(int k=0;k

if(a==t[k]){

count[k]++;

return 0;

}

return 1;

}

void ExChangeFloat(float p[],int i,int j){ /*交换两个数值*/

float temp1;

temp1=p[i];

p[i]=p[j];

p[j]=temp1;

}

void ExChangeChar(char t[],int i,int j){ /*交换两个字符*/

char temp2;

temp2=t[i];

t[i]=t[j];

t[j]=temp2;

}

void main(){ /*主函数*/

float p[MaxStrLength];/*p[]每个字符的概率*/

char str[MaxStrLength],t[MaxStrLength];/*str[]输入的字符串,t[]不重复的字符串*/

int count[MaxStrLength]={0},m=1; /*count[]每个字符的个数,m为不重复的字符的个数*/

printf("----------------------------FanoEncoding-----------------------\n");

printf("Please enter a string：");

scanf("%s",str);

for(int SLength=0;str[SLength]!='\0';SLength++) /*计算数组中实际存储字符串的长度*/

printf("The total length of the string is %d\n",SLength);

t=str;

count++;

for(int i=1;i

if(IsnotIn(str[i],t,m,count)){

t[m]=str[i];

count[m++]++;

}

}

printf("The length of not repeating string is %d\n",m);

for(int j=0;j

p[j]=float(count[j])/float(SLength);

printf("The number of character %c appear is %d，Probability is %f\n",t[j],count[j],p[j]);

}

for(i=1;i

for(j=0;j

if(p[j]>p[j+1]){

ExChangeFloat(p,j,j+1);

ExChangeChar(t,j,j+1);

}

for(i=0;i

FanoNode[i].data=p[i];

FanoNode[i].length=0;

FanoNode[i].Character=t[i];

}

FanoEncoding(FanoNode,0,m-1);

Disp(FanoNode,m,str,SLength);

}