% [nstates,ninput,trellis_trans,trellis_out] = trellis_gen(nstates,G)  
% Returns trellis description of the convolutional code described
% by the generator matrix G, where the number of states is
% nstates. The algorithm applies to 1/n convolutional codes only.
%
% George Ginis, May 2001

function [nstates,ninput,trellis_transition,trellis_output] = trellis_gen(nstates,G) 

  % convert elements of generator matrix from octal to decimal form
  G=gen_convert(G);
  
  % check if G corresponds to 1/n convolutional code
  if size(G,1) ~= 1
    disp('Dimensions of G are wrong.');
    break;
  end
  
  ninput=size(G,1);   % number of rows of G
  n=size(G,2);        % number of columns of G
  
  % construct the transition matrix for a rate 1/n convolutional code
  col = [1:nstates/2]';
  submatrix = [col*2-1 col*2];
  trellis_transition=[submatrix; submatrix];
  
  trellis_output=zeros(nstates,2^ninput);
  
  for k=1:nstates % iterate for all states
        
    in(1)=(k-1)*2;     % corresponds to input 0
    in(2)=(k-1)*2+1;   % corresponds to input 1 
	   
    for i=1:2^ninput   % iterate for all inputs
           
      for o=1:n
	
	out=bitand(G(1,o),in(i));  % compute o-th output 

	out_b=dec2bin(out);     % convert to binary representation
        
	if ( mod( length(find(out_b=='1')),2) == 0) % determine parity
	  trellis_output(k,i)=trellis_output(k,i)*2;
	else
	  trellis_output(k,i)=trellis_output(k,i)*2 + 1;
	end
      end
      
    end
       
  end