[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Soft-Decoding Binary Golay (was: [USRP-users] GPP requirements for U
From: |
Daniel Estévez |
Subject: |
Re: Soft-Decoding Binary Golay (was: [USRP-users] GPP requirements for USRP B210 amsat) |
Date: |
Mon, 24 May 2021 21:29:47 +0200 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.10.1 |
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