Code covered by the BSD License  

Highlights from
Viterbi Trellis Generator

Viterbi Trellis Generator

by

 

Creates the trellis struct needed by convenc & vitdec, for use with viterbi encoding and decoding.

viterbi_trellis_generator(constraint_length, g1_taps, g2_taps)
function trellis = viterbi_trellis_generator(constraint_length, g1_taps, g2_taps)

%Function to generate a the trellis required for viterbi encoding/decoding 
%   functions in Matlab (convenc, vitdec)
%
% INPUTS:
%   constraint_length: 
%       Number of bits used in encoder for generating output bit.
%       Note thate a constraint length of 7 corresponds to a shift register
%       of 6 bits.  (7 is a standard constraint length)
%
%   g1_taps:
%       The indices of the shift register to xor together for creating
%       the g1 output.  Note that the incoming bit is already accounted 
%       for, and should not be included in the taps.  
%       Indices and endinanness of shift register: 
%           Incoming bit -> [1|2|3|4|...|constraint_length-1]
%
%   g2_taps:
%       Same as g1_taps, but for g2.
%
% OUTPUTS:
%   Returns a struct, specifically a struct that is a Matlab trellis.
%   The matlab trellis becomes a parameter for convenc or vitdec

% REVISION HISTORY:
%   12-December-2008: Created by Andrew A. Muehlfeld, undergraduate student
%       at the University of Illinois at Urbana Champaign, under the
%       guidance of Professor Jonathan J. Makela
%       amuehlf2@gmail.com


% Rate = 1/2
% Any constraint length
% Any set of taps for G1 and G2


% Define constants
num_states = 2^(constraint_length - 1);
%g1_taps = [2 3 5 6];
%g2_taps = [1 2 3 6];

% Create zero'd arrays
next_state_in0_dec = zeros(1,num_states);
next_state_in1_dec = zeros(1,num_states);
next_state = zeros(num_states,2);
g1_in0 = zeros(1,num_states);
g1_in1 = zeros(1,num_states);
g2_in0 = zeros(1,num_states);
g2_in1 = zeros(1,num_states);
g_in0 = zeros(1,num_states);
g_in1 = zeros(1,num_states);
g = zeros(num_states,2);


%Main Loop, generates next states and outputs for each state
for i=1:num_states
    %----------------------------------------
    %       Initialize Shift Register 
    %----------------------------------------
    state_dec = i-1; %decimal
    %Convert decimal state number to binary represntation, 
    %to serve as initial shift register value
    state_bin = dec2binvec(state_dec,constraint_length - 1); %binary

    %----------------------------------------
    %       Determine Next States
    %----------------------------------------
    %Next States
    %For Input 0, binary, then decimal
    %Shift in zero
    next_state_in0_bin = [0 state_bin(1:constraint_length-2)];
    next_state_in0_dec(i) = binvec2dec(next_state_in0_bin);
    
    %For Input 1, binary, then decimal
    %Shift in one
    next_state_in1_bin = [1 state_bin(1:constraint_length-2)];
    next_state_in1_dec(i) = binvec2dec(next_state_in1_bin);
    
    %Create 2 value next-state vector, 
    %to be placed into array, for use in trellis
    next_state(i,:) = [next_state_in0_dec(i) next_state_in1_dec(i)];

    %----------------------------------------
    %       Determine Outputs
    %----------------------------------------
    %Outputs
    %Convert stat_bin to:
    %   binary 0 => decimal 1
    %   binary 1 => decimal -1
    %to facilitate xor'ing through multiplication
    state_bin = (-2*state_bin)+1;
    
    %Generate outputs
    g1_in0(i) = prod(state_bin(g1_taps));
    g1_in1(i) = g1_in0(i)*-1;
      
    g2_in0(i) = prod(state_bin(g2_taps));
    g2_in1(i) = g2_in0(i)*-1;

    %Convert outputs back from (1,-1) to (0,1) notation
    g1_in0(i) = (-g1_in0(i)+1)/2;
    g1_in1(i) = (-g1_in1(i)+1)/2;
    g2_in0(i) = (-g2_in0(i)+1)/2;
    g2_in1(i) = (-g2_in1(i)+1)/2;
    
    %Convert two bits of output to one decimal number
    g_in0(i) = binvec2dec([g1_in0(i) g2_in0(i)]);
    g_in1(i) = binvec2dec([g1_in1(i) g2_in1(i)]); 
    
    %Create 2 value output vector
    %to be placed into array for trellis 
    g(i,:) = [g_in0(i) g_in1(i)];
end

%Mold results into trellis struct from
trellis = struct('numInputSymbols',2,'numOutputSymbols',4,...
    'numStates',num_states,'nextStates',next_state,...
    'outputs',g);

%Check if a valid trellis was created
if(istrellis(trellis) == 1)
    display('Trellis generated successfully');
else
    display('Trellis generation failed');
end
end


Contact us