Re: [Discuss-gnuradio] channel coding questions

[Achilleas Anastasopoulos]

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
<address@hidden> 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 <address@hidden> wrote:
>> On Fri, Feb 11, 2011 at 12:59 PM, Achilleas Anastasopoulos
>> <address@hidden> 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
>>
>