% [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