lt_demo.m

这是本人写的LT_codes

%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This program is for LT encoder and decoder 
% which is programed by Zhiwei YAN, [e-mail]
% July, 16, 2008
%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

clear;
clear all;

%% the Luby transform codes for demo
fprintf(1,'\nLuby Transform Codes for Demostration\n');
fprintf(1,'Author: Zhiwei YAN, [e-mail], at XJTU.EDU.CN\n');


%% We assume there is a file of K=100 packets, ie, s_1=0, s_2=1,
%% s_3=0,...,s_K=1
K = 100;
s_bits = floor(rand(1,K)+0.5);

%% Probability of successfully decoding equals to (1- delta)
delta = 0.9;

%% We generate the numbers K, with certain probability distribution
% Ideal solition Distribution
rho = zeros(1,K);
rho(1) = 1/K;
for i = 2:K
    rho(i)=1/(i*(i-1));
end

%% Robust solition Distribution
tau = zeros(1,K);
% delta = 0.01;
S = 0.2*log(K/delta)*sqrt(K);

for i=1:(floor(K/S)-1)
    tau(i) = (S/K)*(1/i);
end
tau(floor(K/S)) = (S/K)*log(S/delta);

Z = sum(rho)+sum(tau);
rho = (rho + tau)/Z;

%% To simplify the process, we map the probability value into the intervals
%of real number axe (0, 10000). That is to say, we set the interval (0, 100),
%if rho(1)=0.01, and the interval (100, 5100) if rho(2)=0.5.
MAX_NUMBER = 10000;
interval = zeros(1,K);
interval = interval + ceil(MAX_NUMBER * rho);
for i=1:K
    interval(i) = interval(i)+interval(i-1+(i==1))*(i~=1);
end

%% We denote the G(N,K) as Generating Matrix. In fact, we could consider the
% N as the clock, and K is the file of K packets.
% If N = 120 and K = 100, we have,
% N = 120;
% K = 100;
N = ceil(K*Z);
% N = 10;
G = zeros(K,N);
degree = zeros(1,K);
en_bits = zeros(1,N);

for i=1:N
    
    % For the i-th column of Generator matrix
    rand_num =floor(MAX_NUMBER*rand(1));
    
    % Indentify how many packets are selected 
    degree = find(rand_num<interval,1,'first');
    
    % Indentify which packets are selected via uniform distribution
    f = zeros(1,degree);
    for j=1:degree
        t = ceil(K*rand(1));
        while (isempty(find(f==t,1,'first'))~=1)
            t = ceil(K*rand(1));
        end
        f(j) = t;
    end
    
    % Set the i-th colum of Generator matrix
    G(f,i)=1;
     
    % Produce the encoded bit according to the i-th column of Generator
    % matrix
    en_bits(i)=mod(sum(s_bits(1,f(1:degree))),2);
end

%% Decoding process via BP scheme
% According to the index of encoded bit, arrange the Generator 
% Matrix G_2(K, N_2) for decoding.
G_2 = G;
N_2 = N;
% K = 100;
de_bits = zeros(1,K)+ 6;
re_bits = en_bits;
% Find a column which contains only 1 within the matrix G_2
%while (1)
for i=1:10000
    X = ones(1,K);
    Y = X*G_2;
    if (any(Y)==0)
%         error('There is no way to decode the packets\n');
        break;
    end;

    col_idx = find(Y==1,1,'first');
    if (isempty(col_idx))
%         error('There are not the bits with degree =1');
        break;
    end
    row_idx = find(G_2(:,col_idx)==1,1,'first');

    % Record the coordinates of the item (k for row, n for column), which has value = 1
    k = row_idx;
    n = col_idx;

    % We can know the s_k = t_n
    de_bits(1,k) = re_bits(1,n);

    % Clear the item 
    G_2(k,n) = 0;

    % Find those items, value=1, on the k-th row
    idx_one = find(G(k,:)==1);
    num_one = length(idx_one);

    % Do XOR operation between, s_k and the last search results 
    re_bits(1,idx_one(1:num_one))= xor(re_bits(1,idx_one(1:num_one)),de_bits(1,k));

    % Clear these items in Generator Matrix
    G_2(k,idx_one(1:num_one)) = 0;

% Return to the first step of decoding algorithm
end


%% Display the results
fprintf(1,'\n===============BEGIN====================\n');

fprintf(1,'Orignial bits:(length=%d)\n',K); fprintf(1,'%d',s_bits);
fprintf(1,'\nEncoded bits:(length=%d) \n',N); fprintf(1,'%d',en_bits);
fprintf(1,'\nDecoded bits:(length=%d) \n',K); fprintf(1,'%d',de_bits);
fprintf(1,'\nDifference between Orignail and Decoded bits: \n');
fprintf(1,'%d ',find((xor(s_bits,de_bits))==1));
% fprintf(1,'\nGenerator matrix:\n %d'); 
% fprintf(1,'%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d\n',G);
fprintf(1,'\n================END=====================\n');
%% The program is over
clear;
clear all;