Re: Soft-Decoding Binary Golay (was: [USRP-users] GPP requirements for USRP B210 amsat)

[Daniel Estévez]

El 24/5/21 a las 0:37, Marcus Müller escribió:

> > In comparison, algebraic decoding takes a handful arithmetic operations and 
> > that's all.
> > So algebraic decoding might be faster, after all.
> Yeah, that sounds very true; I simply have no intuition for the complexity of 
> it.

Hi Marcus,

Here

https://github.com/daniestevez/gr-satellites/blob/master/lib/golay24.c

you have my take at implementing the algorithm in Robert 
Morelos-Zaragoza's book. Working with 32-bit words it boils down to a 
couple dozen popcounts() and paritys(). Most of them can be computed in 
parallel. So in a GPU-like platform it would be blazingly fast, I guess. 
In a typical CPU I guess it's a few hundreds of cycles, and the data 
might even fit in the registers if we're lucky. It seems that the 
algorithm needs some branches, though.

> > However, your idea about maximum-likelyhood decoding makes me think what would 
> > happen if
> > we try to do decoding from soft symbols.
> Have to think about that for a moment. (In my head: what received words would be
> incorrectly decoded by HD but could be correctly decoded using SD?)

Fair point! I mentioned SD without giving it any serious thought, but I 
think your question is very good and it got me thinking for a while.

I'm also quite a noob in this, so maybe I'm thinking in terms that are 
not so standard. As usual, let's assume the channel has independent 
errors for each symbol. Below is an attempt at explaining how/why SD and 
HD may give different results.

Let's write the codewords as vectors of +/-1's instead of 1's and 0's, 
because it makes the notation easier. Say we receive a codeword. Then we 
can think of the log-likelyhood ratios of each received symbol (defined 
as log of the likelyhood of 1 minus log of the likelyhood of -1). These 
log-likelyhoods ratios are a vector of 23 real numbers, call it v.

The question about maximum likelyhood SD can be phrased as follows. 
Consider a word w in the Golay(23,12) code, denote by w*v the 
component-wise product of w and v, and by S(w*v) the sum of its 
components. Then the maximum likelyhood decode is the word w from the 
code that maximizes S(w*v).

Now let's look at HD. We know that for each vector of 23 bits there is a 
unique codeword that is at a Hamming distance at most 3. Looking at the 
signs of v, this means that there is a unique codeword w such that w*v 
has at most 3 negative signs. This codeword is what is produced by HD.

Now, it might well happen that with HD you end up with a w*v with at 
most three negative components but that those negative components are 
huge in comparison with the remaining positive components. In that case 
SD will choose another codeword, since in order to maximize the sum it 
pays off to make those huge components positivem even at the cost of 
ending up with more than three negative components in the end.

For a concrete example, let's say our log-likelyhood vector has 100 in 
its first component, and the remaining components are between -1 and 0. 
Then HD will choose the codeword which is all -1's (the codeword that is 
all zeros in the typical binary code). SD will choose another codeword, 
which will definitely have a 1 in the first component, even though that 
means that there must be 1's in 6 other components.

Intuitively (and going back to the usual representation of the code as 
0's and 1's), this means that if we receive a codeword and we're very 
sure that the first symbol is a one and we're not so sure about what are 
the other symbols, but think that it's more likely that each of them are 
zeros, then HD will just say that it's the first 1 that is in error, and 
that the transmitted codeword must have been all zeros. On the other 
hand, SD will say "now way!" For SD the only thing we're sure is that 
the first symbol is a 1, so it will chose a codeword in which the first 
symbol is 1, and as a consequence 6 other symbols are also 1's, even 
though we thought that they were zeros.

> :) That's certainly true; I mean, after all, this takes a BER > 1/8 within the 
> header to
> go wrong. I guess the payload is classical RS algebraic HD decoder?

Indeed. There is optionally the possibility of adding k=7, r=1/2 
convolutional encoding on top. Not so many satellites use this. In 
gr-satellites this is implemented using the SD Viterbi decoder from GR 
(the Extended FEC Decoder block). I don't know if the software from 
GOMspace does HD or SD.

> If we wanted to go SD on that: I must plainly admit I've got no idea how to SD 
> decode an
> RS code, and the green book sadly only deals in techniques that are 
> well-established :D.

Luckily RS is used for the JT65 mode that people use for moonbounce, so 
Joe Taylor & co. have already given this some thought. There is 
something called the Koetter-Vardy decoder, which does SD of RS but 
unfortunately is closed source. This was used in WSJT until Joe & co. 
came up with a better SD that they called FT:

https://physics.princeton.edu/pulsar/k1jt/FrankeTaylor_QEX_2016.pdf

I don't know how this algorithm compares with the references you gave. 
You're well ahead of my with the literature on this topic, and it's 
being quite a while since I ready the paper about FT, so I don't 
remember any of the ideas.

> > PS: Please keep me in CC, since I'm not on the mailing list.
>
> Sure thing! I think we should moving this to discuss-gnuradio, as it leaves the 
> realm of
> using USRPs pretty robustly, even if that's worse for Martin (sorry!), who I 
> believe is
> not on gr-discuss (but might also not be that much into block codes). So, let's 
> do that.

Done. I've cut off usrp-users from the CC.

In his reply Martin mentioned that he's found that the GFSK Mod and GFSK 
Demod blocks from GNU Radio can't talk to each other, so it might also 
be good to move that (and Martin) to discuss-gnuradio, since we might 
have a bug or potential use case for a new example flowgraph there.

Best,

Dani.

OpenPGP_signature
Description: OpenPGP digital signature