discuss-gnuradio
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Discuss-gnuradio] channel coding questions


From: Ben Reynwar
Subject: Re: [Discuss-gnuradio] channel coding questions
Date: Sun, 20 Feb 2011 14:11:01 -0700

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
<address@hidden> 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
> <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
>>>
>>
>



reply via email to

[Prev in Thread] Current Thread [Next in Thread]