%Fano編碼的MATLAB程序：
%作者：四川大學(xué)電氣信息學(xué)院 本科 通信工程 謝東 于2007年12月29日清晨-2008年1月1日凌晨
%自己改進(jìn)于2008年1月2日清晨.
%費(fèi)諾編碼：一種信源編碼。設(shè)有離散無記憶信源X,P(X)．二進(jìn)制費(fèi)諾編碼為：1.將信源符號按
%概率從大到小的順序排列2.將信源分成兩組――按兩組概率之差為最小分．3.上面一組編碼為
%0，下面一組編碼為1，一直分到一組只有一個信源為止．4.將一個信源分組得到的0和1全部連
%接起來，組成該信源的碼字，信源即得到自己的費(fèi)諾編碼．該程序采用費(fèi)諾編碼算法，通過調(diào)
%用函數(shù)遞歸實現(xiàn)。程序看點：調(diào)用用f1函數(shù)將輸入變量賦初值，f1函數(shù)完成第一次分組后，并
%對字符數(shù)組x（存放碼字）第一列賦值得到第一個分界點d，再用f1,f2函數(shù)相互調(diào)用和自身調(diào)用
%分別實現(xiàn)第一分界點以上和以下的符號再次分組并賦值給字符數(shù)組x;因為f1,f2函數(shù)分別每次，
%實現(xiàn)分界點以上和以下尋找下一個分界點所采用的算法不同，兩個函數(shù)相互調(diào)用彌補(bǔ)了不足，最
%終完成程序設(shè)計要求，堪稱經(jīng)典；本程序的難點是字符數(shù)組x如何存放碼字，程序采用每次調(diào)用
%增加存放碼字?jǐn)?shù)組x的列數(shù)r，在尋得分界點后即賦值,可是最后程序輸出只有第一列的值，原來
%變量x每次的值被沖了，沒有保存，困惑我好久，最后采用global全局變量解決了上問題，不過
%采用global全局變量定義x后，x的類型需要轉(zhuǎn)換為char最關(guān)鍵的是程序開頭必須用clear all把
%global定義的變量歸零，不然global定義的變量中存放的還是上次所存的值.
clc;clear all;
N=input('N=');%輸入信源符號的個數(shù)
s=0;l=0;H=0;
for i=1:N
    fprintf('第%d個',i);
    p(i)=input('p=');%輸入信源符號概率分布矢量,p(i)<1
    if p(i)<=0
    error('不符合概率分布')
    end
    s=s+p(i)
    H=H+(- p(i)*log2(p(i)));%計算信源信息熵
end
if (s<=0.999999||s>=1.000001)
error('不符合概率分布')
end
tic;
for i=1:N-1 %按概率分布大小對信源排序
    for j=i+1:N
        if p(i)<p(j)
           m=p(j);p(j)=p(i);p(i)=m;
        end
   end
end
x=f1(1,N,p,1);
for i=1:N       %計算平均碼長
    L(i)=length(find(x(i,:)));
    l=l+p(i)*L(i);
end
n=H/l; %計算編碼效率
fprintf('按概率降序排列的碼字:\n');
disp(x) %顯示按概率降序排列的碼字
fprintf('平均碼長:\n');
disp(l)% 顯示平均碼長
fprintf('編碼效率:\n');
disp(n) %顯示編碼效率
fprintf('計算耗時time= %f\n',toc);