費諾編碼基本原理
首先,將信源符號以機率遞減的次序排列進來，將排列好的信源符號劃分為兩大組，使第組的機率和近於相同,並各賦於一個二元碼符號”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);
}
