Re: [Discuss-gnuradio] The primary issue with the Lazy Viterbi Decoder

[Michael Dickens]

That's the "quickie" overview.  'k-1', BTW, is the memory order  
required to realize the actual encoder; the "constraint length" is  
effectively how long a single ("impulse") input bit can possibly  
effect output bits.  Codes are (sometimes) referred to as (n,m,k),  
where 'n' is the number of inputs, 'm' is the number of outputs, and  
'k' is the total memory order.  Some places use (n,m,k+1), for the  
constraint length.

For "high" SNR (e.g. Es/N0 ~ 6 dB for a (2,1,8) CDMA code), the Lazy  
method basically traverses the convolutional code's trellis directly;  
it is necessary to just find the best path metric and follow that set  
of nodes.  The Lazy method does have some bookkeeping, but the  
reduction by a factor of approximately 2^k is very large when it  
comes to standard NASA codes (k ~ 7-9).

For "low" SNR (e.g. Es/N0 ~ 0 dB for a (2,1,8) CDMA code), the Lazy  
method spends a lot of time doing bookkeeping, and thus is probably a  
little slower than the standard Viterbi decoder which systematically  
goes through all possible nodes and node outputs to determine the  
best path.

At "middle" SNR's, the Lazy is a generally faster than other  
algorithms, but the benefits really show at higher SNR's.

While I don't know much about the "A*" algorithm (which traverses the  
trellis lengthwise [in time] instead of breadth-wise as Viterbi  
does), it seems that at high SNR it would be just as effective as the  
"Lazy" method, since there are very few low-metric paths through the  
trellis.

On Aug 1, 2006, at 2:16 PM, Bob McGwier N4HY wrote:
> That is straightforward.
>
> In High SNR,  the lazy algorithm is O(1)!!!
>
> In low SNR, both the lazy algorithm and the traditional algorithm  
> are both O(2^k) where k+1 is the constraint length.
>
> It is not a simple relationship as the SNR falls off but in many of  
> the cases we would consider,  the lazy algorithm should be a win.