Cheers. I'm planning on having a go at some sub-optimal algorithms in the next week or two.
Ben On Sun, Feb 20, 2011 at 1:46 PM, Achilleas Anastasopoulos <[email protected]> wrote: > Ben, > > I have found some time and implemented two versions of > a turbo (sccc) decoder block in the gr-trellis project. > I have added a couple of example python scripts as well. > > I have also refactored all "core algorithms" > (such as Viterbi, SISO, turbo, etc) > into a separate file and used C++ templates to simplify > coding. It is this file that will need to be enriched with other > suboptimal algorithms if you want to work in this direction. > > You can find all these changes in the "turbo" branch on my github site: > > https://github.com/anastas/gnuradio_turbo/commits/turbo > > I hope it will soon be merged to the gnuradio master. > > Achilleas > > > > > > On Sun, Feb 13, 2011 at 12:02 PM, Achilleas Anastasopoulos > <[email protected]> wrote: >> 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
