
From:  Michael Dickens 
Subject:  Re: [Discussgnuradio] The primary issue with the Lazy Viterbi Decoder 
Date:  Tue, 1 Aug 2006 15:10:51 0400 
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 ~ 79).
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 breadthwise as Viterbi does), it seems that at high SNR it would be just as effective as the "Lazy" method, since there are very few lowmetric 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.
[Prev in Thread]  Current Thread  [Next in Thread] 