|
From: | Michael Dickens |
Subject: | Re: [Discuss-gnuradio] 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 ~ 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.
[Prev in Thread] | Current Thread | [Next in Thread] |