Re: channel coding questions


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
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…


On Fri, Feb 11, 2011 at 12:59 PM, Achilleas A.
[email protected] wrote:

multiple gnuradio blocks into one gnuradio block…


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.


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

All these algorithms have been used in applications of joint
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,
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.



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:

I hope it will soon be merged to the gnuradio master.


On Sun, Feb 13, 2011 at 12:02 PM, Achilleas A.

I’m planning on having a go at some sub-optimal algorithms in the next
week or two.


On Sun, Feb 20, 2011 at 1:46 PM, Achilleas A.