>On 05.07.2017 2:53, gct wrote: >>> On 04.07.2017 22:46, gct wrote: >>> >>> (snip) >>> >>>> >>>> I surely did look it up, but they're doing a non-coherent detection, >>> which >>>> I was trying to avoid for performance reasons. You can see they'reat>>>> least 1.7dB above the lower bound. >>>> --------------------------------------- >>>> Posted through http://www.DSPRelated.com >>>> >>> >>> Apologies if I sounded too harsh; I've read that article, too. >>> >>> Just some thoughts (not from actual experience). Coherent detection >>> doesn't have to mean Viterbi decoder. What about M-algorithm? Perhaps >>> you could do better than non-coherent detection without too much >>> complexity. >>> >>> Best regards, >>> Gene >> >> No worries, I haven't heard of the M-algorithm, do you have any good >> references I could look at? >> --------------------------------------- >> Posted through http://www.DSPRelated.com >> > >M algorithm is briefly reviewed in Todd Moon, "Error Correction Coding: >Mathematical Methods and Algorithms". > >Its description is actually so short that I could just quote it here. >For fun's sake, here's what the text says (pp. 521-522): > >----------------------------------------- > >12.8.6 A Variation on the Viterbi Algorithm: the M Algorithm > >For a trellis with a large number of states at each time instant, the >Viterbi algorithm can be very complex. Furthermore, since there is only >one correct path, most of the computations are expended in propagating >paths that are not be used, but must be maintained to ensure the >optimality of the decoding procedure. The M algorithm (see, e.g., [270])>is a suboptimal, breadth-first decoding algorithm whose complexity is >parametric, allowing for more complexity in the decoding algorithm while>decoding generally closer to the optimum. > >A list of M paths is maintained. At each time step, these M paths are >extended to M*2^k paths (where k is the number of input bits), and the >path metric along each of these paths is computed just as for the >Viterbi algorithm. The path metrics are sorted, then the best M paths >are retained in preparation for the next step. At the end of the >decoding cycle, the path with the best metric is used as the decoded >value. While the underlying graphical structure for the Viterbi >algorithm is a trellis, in which paths merge together, the underlying >graphical structure for the M algorithm is a tree: the merging of paths >is not explicitly represented, but better paths are retained by virtue >of the sorting operation. The M-algorithm is thus a cross between the >stack algorithm (but using all paths of the same length) and the Viterbi>algorithm. If M is equal to the number of states, the M algorithm is >nearly equivalent to the Viterbi algorithm. However, it is possible for >M to be significantly less than the number of states with only modest >loss of performance. > >Another variation is the T-algorithm. It starts just like the M >algorithm. However, instead of retaining only the best M paths, in the T>algorithm all paths which are within a threshold T of the best path at >that stage are retained. > >----------------------------------------- > >[270]: G. Pottie and D. Taylor, "A Comparison of Reduced Complexity >Decoding Algorithms for Trellis Codes," IEEE Journal on Selected Areas >in Communications, vol. 7, no. 9, pp. 1369-1380, 1989. > >----------------------------------------- > >If you follow the link, it would say something along the lines that >M-algorithm is global, while Viterbi algorithm is local. Which makes >some sense to me. > >Best regards, >GeneExcellent references, thank you! Will take a look at this. --------------------------------------- Posted through http://www.DSPRelated.com
CPFSK receiver architecture
Started by ●July 2, 2017
Reply by ●July 5, 20172017-07-05
Reply by ●July 6, 20172017-07-06
Evgeny Filatov <filatov.ev@mipt.ru> wrote:>M algorithm is briefly reviewed in Todd Moon, "Error Correction Coding: >Mathematical Methods and Algorithms".One good use of these reduced-complexity decoding algorithms is, in a packet-coded system you can try the reduced complexity algotithm, and if it results in a good CRC then you're done; if not, re-try with the full Viterbi algorithm. Way back sometime before 1995 I implemented such a system and, IIRC, described it in a MIL-STD (or at least a submission). Steve
Reply by ●July 6, 20172017-07-06
On Thu, 6 Jul 2017 15:13:00 +0000 (UTC), spope33@speedymail.org (Steve Pope) wrote:>Evgeny Filatov <filatov.ev@mipt.ru> wrote: > >>M algorithm is briefly reviewed in Todd Moon, "Error Correction Coding: >>Mathematical Methods and Algorithms". > >One good use of these reduced-complexity decoding algorithms is, >in a packet-coded system you can try the reduced complexity algotithm, >and if it results in a good CRC then you're done; if not, re-try >with the full Viterbi algorithm. > >Way back sometime before 1995 I implemented such a system and, >IIRC, described it in a MIL-STD (or at least a submission). > >SteveFWIW, sequential decoding of one form or another (including the M-algortihm) has been around for a long time (naturally). To be honest I've not seen anything but the Viterbi algorithm suggested for CP demodulation, though, and I suspect because of complexity/performance tradeoff issues. Usually sequential decoding requires a much longer constraint length to be effective compared to Viterbi decoding. Here's a paper from 1984 comparing various sequential decoders, including the M-algorithm. http://www2.ensc.sfu.ca/people/faculty/cavers/ENSC805/readings/32comm02-anderson.pdf Also FWIW, back in my early satellite comm days much of our equipment could be shipped with either a sequential decoder with a long constraint length (e.g., k=37 IIRC), or a Viterbi decoder with k=7. The sequential was an option and actually provided a bit more gain in many circumstances, but overall once the Viterbi decoders got cheaper sequentials fell out of favor. IIRC our sequential used the Fano algorithm.
