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

On Fri, Feb 11, 2011 at 12:59 PM, Achilleas A.

[email protected] wrote:

multiple gnuradio blocks into one gnuradio block…

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

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

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 A.

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 A.