Re: [Discuss-gnuradio] channel coding questions

[Achilleas Anastasopoulos]

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
>