trellis_gen.m

通信中常用的卷积码信道译码源码程序

function [Trellis, Lut, TerminateF, PunctureF] = ...
    trellis_gen(Trellis, enc_type, dec_metric, varargin);

%------------------------------------------------------------------------------
% Generate binary-trellis (non-recursive / recursive RSC's).
% 
% Format:
% -------
% 
% [Trellis, Lut, TerminateF, PunctureF] = ...
%   trellis_gen(Trellis, enc_type, dec_metric, ...
%               [gen_form], [TerminateF], [PunctureF])
% 
% Author: MVe
% Date:   03.07.2002
%------------------------------------------------------------------------------

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% -- Initial parameter checking etc.. -- %% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

tmp1 = length(varargin);
switch tmp1
 case 0
  gen_form = [];
  TerminateF = 1;
  PunctureF = 0;
 case 1
  gen_form = varargin{1};
 case 2
  gen_form = varargin{1};
  TerminateF = varargin{2};
  if isempty(TerminateF)
    TerminateF = 1;
  end % if isempty(TerminateF)
 case 3
  gen_form = varargin{1};
  TerminateF = varargin{2};
  PunctureF = varargin{3};
  if isempty(TerminateF)
    TerminateF = 1;
  end % if isempty(TerminateF)
   if isempty(PunctureF)
    PunctureF = 0;
   end % if isempty(PunctureF)
end % switch tmp1

% Root directory of the files
Trellis.RootDir = pwd;
CGFile = [Trellis.RootDir '/dat/CodeGen.dat'];

% Add 
Trellis.Path_list = [Trellis.RootDir ' ' Trellis.RootDir '/tls ' ...
                     Trellis.RootDir '/decoder ' Trellis.RootDir '/encoder '];
                     %Trellis.RootDir '/blast'];

eval(['addpath ' Trellis.Path_list]);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% -- Check / fetch / modify codegenerator vectors if necessary -- %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

ErrorF = 0;
FindCGF = 0;

% -- If user hasn't defined codegenerator, fetch one from database. -- %

% Field doesnt 'g' exists in structure 'Trellis'
if ~isfield(Trellis,'g')
  FindCGF = 1;
else
  % Field 'g' is empty
  if isempty(Trellis.g)
    FindCGF = 1;
  end % if isempty(Trellis.g)
end % if isfield(Trellis,'g')

% If codegenerator is not defined, check that all necessary
% parameters are given. Fetch codegenerator from database.
if FindCGF
  if and(isfield(Trellis,'K'),isfield(Trellis,'Rate'))
    if and(~isempty(Trellis.K),~isempty(Trellis.Rate))
      switch enc_type
       case 'non-recursive'
	[Trellis.g, gen_form] = ...
	    find_codegenerator(CGFile,Trellis.Rate,Trellis.K);	
       case 'recursive'
	[Trellis.g, gen_form] = ...
	    find_codegenerator(CGFile,Trellis.Rate,Trellis.K,'recursive');
      end % switch enc_type
      Trellis.EncType = enc_type;
    else
      ErrorF = 1;
    end % if and(~isempty(Trellis.K),~isempty(Trellis.Rate))
  else
    ErrorF = 1;
  end % if and(isfield(Trellis,'K'),isfield(Trellis,'Rate'))
end % if or(isempty(Trellis.g),~isfield(Trellis,'g'))
  
if ErrorF
  error(['If codegenerator vectors are not given, then specify' ...
	 ' ''Trellis.K'' (constraint length) and ''Trellis.Rate'' ' ...
	 '(coderate)']);
end % if ErrorF

% Check, are the codegenerators in octal or binary form. If
% 'GenForm' is not given, assume binary form. Convert oct->bin if necessary.
if ~isempty(gen_form)
  switch gen_form
   case 'binary'
   case 'octal'
    % Transform Codegenerator from octal to binary
    Trellis.g = double(dec2bin((base2dec(num2str(Trellis.g(:)),8))))-48;
   otherwise
    error(sprintf('Unknown codegenerator format ''%s''', gen_form));
  end % switch gen_form
end % if ~isempty(gen_form)


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% -- Initialise some parameters -- %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Number of output bits and constraint length
[Trellis.n,Trellis.K] = size(Trellis.g);
Trellis.K = Trellis.K/Trellis.k;

% Memory in blocks
Trellis.m = (Trellis.K - 1);

% Number of states
Trellis.StNr = 2^(Trellis.m*Trellis.k);

% Number of different outputs
OutNr = 2^Trellis.n;

% Coderate
Trellis.Rate = Trellis.k/Trellis.n;

% Look-up tables (pointer->bin) for trellis states, inputs and outputs
%
Lut = struct('States',[]);
Lut.States = double(dec2bin([0:Trellis.StNr-1]))-48;
Lut.Outputs_bin = double(dec2bin([0:OutNr-1]))-48;
Lut.Outputs = [1:2^Trellis.n].';
Lut.Inputs = double(dec2bin([0:2^Trellis.k-1]))-48;
Lut.InfBits = cell(Trellis.StNr);

% Format of 'Trellis.NextState':
%  row number = previous state
%  column 1 = next state when input is 00...00
%  column 2 = next state when input is 00...01
%  column 3 = next state when input is 00...10 
%    etc..
%
Trellis.NextState = zeros(Trellis.StNr,2^Trellis.k);
nextstate_bin = cell(Trellis.StNr,2^Trellis.k);

% Format of 'Trellis.Output'
%  row number = current state
%  column 1 = output when input is 00...00
%  column 2 = output when input is 00...01
%  column 3 = output when input is 00...10
%    etc..
%
Trellis.Output = zeros(Trellis.StNr,2^Trellis.k);
Trellis.Output_bin = cell(Trellis.StNr,2^Trellis.k);


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% -- Calculate transitions in trellis to look-up tables -- %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

tmp = zeros(1,Trellis.n);

for i1 = 1:Trellis.StNr
  
  for i2 = 1:2^Trellis.k
      
    %% -- Encoder type dependant part begins -- %%

    switch enc_type
      
     % -- Non-recursive encoder -- %
     case 'non-recursive'
      
      % Calculate the next state
      state_tmp = [Lut.Inputs(i2,:),Lut.States(i1,:)];
      % Output of current branch
      for i3 = 1:Trellis.n
        tmp(1,i3) = mod(sum(state_tmp&Trellis.g(i3,:)),2);
      end % for i1 = 1:Trellis.n
     
     % -- Systematic recursive encoder -- %
     case 'recursive'
      
      % Create recursive systematic encoder from given
      % codegenerator vectors.
      feedback = Trellis.g(1,:);
      feedforward = Trellis.g(2:end,:);
      % Output systematic bit(s)
      tmp(1,:) = Lut.Inputs(i2,:);
      % Input for feedforward part
      ff_input = mod(sum(Lut.Inputs(i2,:) + ...
			 mod(sum(Lut.States(i1,:)&feedback(2:end)),2)),2);
      % Calculate the next state 
      state_tmp = [ff_input,Lut.States(i1,:)];
      % Output parity bits
      for i3 = 1:(Trellis.n-Trellis.k)
        tmp(1,Trellis.k+i3) =  mod(sum(state_tmp&feedforward(i3,:)),2);
      end % for i3 = 1:(Trellis.n-Trellis.k)

     otherwise
      error(sprintf('Encoder type: ''%s'' is not supported', enc_type));
    end
    
    %% -- Encoder type dependant part ends -- %%
    
    % -- Next state of the trellis in binary form -- %
    nextstate_bin{i1,i2} = state_tmp(1:end-Trellis.k);
    % -- Branch output in binary form -- %
    Trellis.Output_bin{i1,i2} = tmp(1,:);
  end % for i2 = 1:2^Trellis.k
  
end % for i = 1:Trellis.StNr

%% -- Binary to "pointer" conversions -- %%
  
% Convert 'Trellis.Output_bin' to "pointers"
[size1,size2] = size(Trellis.Output_bin);
LState = length(Trellis.Output_bin{1,1});
tmp = zeros(size1,LState);
for i1 = 1:2^Trellis.k
  Trellis.Output(:,i1) = ... 
      bin2dec(char(reshape([Trellis.Output_bin{:,i1}],LState,size1).' + 48))+1;
end % for i1 = 1:Trellis.StNr

% Convert 'nextstate_bin' to "pointers"
[size1,size2] = size(nextstate_bin);
LState = length(nextstate_bin{1,1});
tmp = zeros(size1,LState);
for i1 = 1:2^Trellis.k
  Trellis.NextState(:,i1) = ... 
      bin2dec(char(reshape([nextstate_bin{:,i1}],LState,size1).' + 48))+1;
end % for i1 = 1:Trellis.StNr

if strcmp(enc_type,'recursive')

  % Format of 'Trellis.Output_Parity_bin'
  %  row number = previous state
  %  column 1 = output parity bits when input is 00...00
  %  column 2 = output parity bits when input is 00...01
  %  column 3 = output parity bits when input is 00...10
  %    etc..
  %
  Trellis.Output_Parity_bin = cell(Trellis.StNr,2^Trellis.k);
  for i1 = 1:2^Trellis.k
    Trellis.Output_Parity_bin(:,i1) = ...
        num2cell(Lut.Outputs_bin(Trellis.Output(:,i1),...
                               Trellis.k+1:Trellis.n),2);
  end % for i1 = 1:2^Trellis.k

  % Format of 'Trellis.PrevState':
  %  row number = current state
  %  column 1 = previous state when input was 00...00
  %  column 2 = previous state when input was 00...01
  %  column 3 = previous state when input was 00...10 
  %    etc..
  Trellis.PrevState = zeros(Trellis.StNr,2^Trellis.k);
  Trellis.Output_PrevParity = cell(Trellis.StNr,2^Trellis.k);
  for i1 = 1:2^Trellis.k
    Trellis.PrevState(Trellis.NextState(:,i1),i1) = [1:Trellis.StNr].';
    Trellis.Output_PrevParity(Trellis.NextState(:,i1),i1) = ...
        Trellis.Output_Parity_bin(:,i1);
  end % for i1 = 1:2^Trellis.k

end % if strcmp(enc_type,'recursive')

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% -- Calculate trellis termination transitions (if required) -- %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

if TerminateF

  % Format of 'Trellis.Tail_NextState':
  %
  %  row number = previous state
  % 
  Trellis.Tail_NextState = zeros(Trellis.StNr,1);
  nextstate_termination_bin = cell(Trellis.StNr,1);

  % Format of 'Trellis.Tail_Output_bin'
  %
  %  row number = previous state
  %
  Trellis.Tail_Output_bin = cell(Trellis.StNr,1);
  
  tmp_tail = zeros(1,Trellis.n);

  if strcmp(enc_type,'recursive')
    
    for i1 = 1:Trellis.StNr
      
      %% --  Trellis termination -- %%
      %
      % Drive trellis to zero state:         
      %  Tail bits == output of the feedback.
      %         
      tail = mod(sum(Lut.States(i1,:)&feedback(2:end)),2);
      % Input for feedforward part
      ff_input = mod(sum(tail + ...
			 mod(sum(Lut.States(i1,:)&feedback(2:end)),2)),2);
      % Calculate the next state 
      state_tail = [ff_input,Lut.States(i1,:)];
      % Output systematic bit(s)
      tmp_tail(1,:) = tail;
      % Output parity bits
      for i2 = 1:(Trellis.n-Trellis.k)
	tmp_tail(1,Trellis.k+i2) =  mod(sum(state_tail&feedforward(i2,:)),2);
      end % for i2 = 1:(Trellis.n-Trellis.k)
      
      % -- Next state of the trellis in binary form -- %
      nextstate_termination_bin{i1,1} = state_tail(1:end-Trellis.k);

      % -- Trellis output in binary form -- %
      Trellis.Tail_Output_bin{i1,1} = tmp_tail(1,:);
      
    end % for i1 = 1:Trellis.StNr

  else

    for i1 = 1:Trellis.StNr

      %% --  Trellis termination -- %%
      %
      % Drive trellis to zero state:         
      %  Tail bits == output of the feedback.
      %         
      tail = zeros(1,Trellis.k);
      state_tail = [tail,Lut.States(i1,:)];      
      for i3 = 1:Trellis.n
        tmp_tail(1,i3) = mod(sum(state_tail&Trellis.g(i3,:)),2);
      end % for i1 = 1:Trellis.n

      % -- Next state of the trellis in binary form -- %
      nextstate_termination_bin{i1,1} = state_tail(1:end-Trellis.k);

      % -- Trellis output in binary form -- %
      Trellis.Tail_Output_bin{i1,1} = tmp_tail(1,:);
                  
    end % for i1 = 1:Trellis.StNr
    
    
  end % if strcmp(enc_type,

  %% -- Binary to "pointer" conversions -- %%
  
  % Convert 'nextstate_termination_bin' to "pointers"
  [size1,size2] = size(nextstate_termination_bin);
  LState = length(nextstate_termination_bin{1,1});
  tmp = zeros(size1,LState);
  Trellis.Tail_NextState(1:size1,1) = ... 
      bin2dec(char(reshape([nextstate_termination_bin{:}], ...
			   LState,size1).' + 48))+1;
  

end % if TerminateF




%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% -- Edge definitions -- %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Format of 'Trellis.Edge':
%  row = edge number
%  column = | start edge |遝nd edge |遡nput symbol |遫utput symbol遼
%
Trellis.Edge = zeros(Trellis.StNr*2^Trellis.k,4);
tmp_index = 1;
for i1 = 1:Trellis.StNr
  for i2 = 1:2^Trellis.k
    Trellis.Edge(tmp_index,:) = [i1, Trellis.NextState(i1,i2), i2, ...
		    Trellis.Output(i1,i2)];
    tmp_index = tmp_index+1;
  end % for i2 = 1:2^Trellis.k
end % for i1 = 1:Trellis.StNr



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% -- Initialise some parameters for soft/hard decoding --%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Look-up tables for decoding data sequence ('convolution'/'tcm')
% Format:
%  row = current state
%  column = previous state
%
for i1 = 1:2^Trellis.k
  for i2 = 1:Trellis.StNr
    Lut.InfBits{i2,Trellis.NextState(i2,i1)}=Lut.Inputs(i1,:);
  end % for i2 = 1:Trellis.StNr 
end % for i1 = 1:2^Trellis.k


% Select soft or hard decision decoding
%
switch dec_metric
 % Metrics is Hamming-distance.
 case 'hard'
  Trellis.SoftDecF = 0;  
 % Metrics is Euclidian-distance.    
 case 'soft'
  Trellis.SoftDecF = 1;
 otherwise
  error(sprintf('Unsupported decoding mode: ''%s''', dec_metric));
end % switch dec_metric