% [L,cont]=...
%  dmin_prop(L,nstates,ninput,trellis_transition,trellis_output,...
%  ndepth,dmin_ub,L1)
% Returns matrix L containing information about minimum distance, 
% number of minimum distance (and subsequent) paths, and number of bits
% corresponding to the minimum distance (and sunsequent)
% paths. Also returns flag indicating whether all the paths of
% interest have been discovered.
% L is the matrix with information about all states, ndepth is the
% distance depth, and dmin_ub is some finite upper bound on the minimum
% distance. L1 is a vector with information about state 1. 
%
% George Ginis, May 2001

function [L,cont]=...
  dmin_prop(L,nstates,ninput,trellis_transition,trellis_output...
	    ,ndepth,dmin_ub,L1)
    
  % initialize matrix keeping information about states
  Lnew=zeros(nstates,1+2*(ndepth+1));
  Lnew(:,1)=dmin_ub*ones(size(L,1),1);  
  % initialize distances to the upper bound value 
   
  [st1 out1]=trellis_fn(1,0,trellis_transition,trellis_output);
  % produce next state (assumed equal to 1) and corresponding
  % output from state 1 with 0 input 
  
  cont = 0; % initialize flag

  % iterate for all states other than state 1
  for s=2:size(L,1)
          
    % expand this state only if the cost to reach this state is
    % smaller than the currently known distance of the paths of interest  
    if (L(s,1) <= L1(1)+ndepth)
      
      cont=1; % more paths of interest may exist
      
      for m=1:2^ninput    % iterate for all possible inputs

	% produce next states and corresponding outputs from state s
	[st(m) out(m)]=trellis_fn(s,m-1,trellis_transition,trellis_output);
	
	% compute distance between path leading to state st(m) and 0 path
	dp=bdistance(out(m),out1);
	
	% compute number of differing bits between the path ending at
	% state st(m) and the "top" path
	Nbp=bdistance(m-1,0);
    
	% set up polynomial with neighbors information 
	poly_neighb(1) = L(s,1)+dp; % increment distance 
	poly_neighb(2:ndepth+2) = L(s,2:ndepth+2);
	
	% update polynomial with neighbors information for target state 
	poly_neighb_add = ...
	  polyadd( Lnew(st(m),1:ndepth+2), poly_neighb(1:ndepth+2) ); 
	
	% set up polynomial with bits information 
	poly_bits(1) = L(s,1)+dp;
	poly_bits(2:ndepth+2) = L(s,ndepth+3:2*ndepth+3)+Nbp*L(s,2:ndepth+2);
	
	% update polynomial with bits information for target state
	poly_bits_add = polyadd( ...
	  [ Lnew(st(m),1) Lnew(st(m),ndepth+3:2*ndepth+3) ] , ...
	   poly_bits(1:ndepth+2) );
	
	% update matrix with information about states
	Lnew(st(m),1:ndepth+2) = poly_neighb_add(1:ndepth+2);
	Lnew(st(m),ndepth+3:2*ndepth+3) = poly_bits_add(2:ndepth+2);

      end
      
    end
    
  end
      
  L = Lnew;  % update matrix