trellisgen.m

The Viterbi algorithm

function [trellis_transition, trellis_out] = trellisgen(constlen, codegen)
% Returns trellis description of the convolutional code described
% by the constraint length matrix (constlen) & generator matrix (codegen).
% The algorithm applies to k/n convolutional codes only.
%
% Mahdi Zahedi 5 June 2008

%% convert elements of generator matrix from     octal to decimal
%   G=gen_convert(G);
G=oct2dec(codegen); % Octal 2 Decimal
%% initialize
[No_in No_out] = size(G); % No_in=k,  No_out=n (without punc)
n_tap = sum(constlen)-No_in; % Total Number of Register = Number of Taps
nstates=2^(n_tap)  ;    % Number of states
reg(1) = 0; % pointer combine k register and make state
x = fliplr(constlen);
for p=1:No_in
    reg(p+1) = sum(x(1:p))-p;
end
%% construct the Transition Matrix(Next State Matrix)
for i=1:nstates
    nstate_bit= de2bi(i-1,n_tap,'left-msb');
    for j=1:2^No_in
        bits_in = de2bi(j-1,No_in);
        mat=[];
        for k=1:No_in
            m = nstate_bit(reg(k)+1:reg(k+1));
            mm = bitshift(bi2de(m,'left-msb'),-1);
            mat_k = de2bi(mm,x(k)-1,'left-msb');
            mat_k(1) = bits_in(k);
            mat = [mat mat_k];
        end
        trellis_transition(i,j)=  bi2de(mat,'left-msb');
    end
end
%% construct the Output Matrix
for i=1:nstates
    nstate_bit= de2bi(i-1,n_tap,'left-msb');
    for j=1:2^No_in
        bits_in = de2bi(j-1,No_in,'left-msb'); % 
        for n=1:No_out
            for k=1:No_in
                m = nstate_bit(reg(end-k)+1:reg(end-k+1));
                x = de2bi(G(k,n),constlen(k),'left-msb');
                g = [bits_in(k) m];
                b=0;
                for r=1:constlen(k)
                    if (x(r) == 1)
                        b=bitxor(g(r),b);
                    end
                end
                bb(k)=b;
            end
            c=0;
            for k=1:No_in
                c=bitxor(c,bb(k));
            end
            cc(n)=c;
        end        
        trellis_out(i,j)=  bi2de(cc,'left-msb');
    end
end