OK, so (almost) all suboptimal receivers can be thought of as a suboptimal search over the sequence tree: if you search everything you need Q^N sequences (for Q-ary alphabets and N-length sequences). (The Viterbi algorithm searches only a few of them because of the inherent structure and thus it is not suboptimal).
The M-algorithm works a s follows: It keeps and updates only the best M sequences. At each time t, it updates the likelihoods of all M sequences (thus generating Q*M new candidates). Then it discards all but the best M, and then proceeds to t+1... The T-algorithm works as follows: It keeps and updates only the sequences, whose likelihood is above a threshold T. At each time t, it updates all saved sequences and finds their likelihood. Then it discards all but those with likelihood >T, and then proceeds to t+1... The M is more robust for implementation because of the constant space requirements... All these algorithms have been used in applications of joint detection/decoding/estimation, where the VA is clearly not optimal (see for example the huge literature in the 90s on the subject, or maybe some papers by M Fitz and Seymour in 95/96 in IEEE Trans Communications). However they have also been used for reduced complexity decoding of trellis-based systems: eg, if you have a trellis with 256 states, then using M=64 you can only keep a list of the best 64 sequences. This is similar in principle to sequential decoding as well. In terms of gnuradio blocks, you can start with a simple combined viterbi decoder like block, add an additional parameter (eg, M or T) and modify the internal work function to reflect the reduced complexity algorithm. Everything else (ie, the interface) should be the same. Achilleas On Sat, Feb 12, 2011 at 5:55 PM, Ben Reynwar <[email protected]> wrote: > On Fri, Feb 11, 2011 at 12:59 PM, Achilleas Anastasopoulos > <[email protected]> wrote: >> Ben, >> >> >> I have a simple example of turbo coding/decoding (i think it is a sccc) in >> the examples section of gr-trellis. It is SLOW! >> I don't think there is any particular reason other than you are essentially >> have to run 2 siso blocks per iteration, ie, roughly >> 4 VA's per iteration (recall forward/backward pass)... >> The comment i made about buffering is from my experience: >> You can always get a better performance if you combine the functionality of >> multiple gnuradio blocks into one gnuradio block... >> >> >> Regarding suboptimal receivers, I don't have any intention of writing code >> for them, but if anyone is willing to work seriously on that i can help >> (maybe an undergrad student project for the summer...) >> Similarly, for a turbo decoding hierarchical block: it is trivial to put >> together siso blocks and do it (the code is essentially there: see the >> python code in the examples). I can think of an sccc and a pccc block >> whereby you define the 2 constituent FSMs (or even more), an interleaver >> structure, and the number of iterations; that's all there is to it. >> >> Regarding integration with the "constellations" class i think it is a >> wonderful idea. When I was writing gr-trellis I thought of constellations as >> arbitrary one-dimensional look-up tables with n-dim entries. Repackaging the >> "metrics" code to use constellations would be great. >> YES, I believe that the "constellations" class has to be general enough to >> include n-dimensional constellations. What if you want to implement 4-FSK, >> or even arbitrary CPM (I am currently working on that). >> Also, there are trellis-codes that output 2 QPSK (or 2 8PSK) symbols at >> every step and having these constellations as 1 2D complex constellation >> makes integration with gr-trellis very easy... >> >> Achilleas >> > > I'm up for having a look at the suboptimal receivers, at least to see > how hard it would be. If you > could suggest one that would be useful and point me in the direction > of an appropriate introductory article or > book that would be really helpful. > > Cheers, > Ben > _______________________________________________ Discuss-gnuradio mailing list [email protected] http://lists.gnu.org/mailman/listinfo/discuss-gnuradio
