A couple years ago, I implemented a Golay(24,12) decoder to be used in the GOMX-1 decoder in gr-satellites. The implementation can be seen here. I followed the algorithm in the book The Art of Error Correction Coding, Section 2.2.3, without taking much care to understand why the algorithm worked. Now I am doing some experiments with Golay(24,12) and Golay(23,12) codes, so I have needed to revisit that algorithm and understand it well to adapt it to my needs. Here I explain how this algebraic decoder works.
Tag: fec
Soft Viterbi decoder for AO-40 FEC
A year ago, I made a decoder for the AO-40 FEC. While AO-40 has been dead for many years, the same FEC system is used in AO-73 and the rest of the FUNcube satellites. This decoder was later included in gr-satellites and it is currently used in the decoders for AO-73, UKube-1 and Nayif-1.
When I implemented this FEC decoder, for simplicity I used a hard decision Viterbi decoder, since my main concern was to get all the system working. I always intended to replace this by a soft decision Viterbi decoder, but it seems that I forgot completely about it.
Now, while thinking about integrating gr-aausat (my AAUSAT-4 decoder OOT module) into gr-satellites and adding a soft Viterbi decoder for AAUSAT-4, I have remembered about this. While the decoder for AAUSAT-4 will have to wait, since I have found a bug in the GNU Radio Viterbi decoder that makes it segfault, I have already added a soft Viterbi AO-40 FEC decoder to the FUNcube decoders in gr-satellites.
BCH decoder for S-NET
In my previous post, I talked about the coding used by the S-NET cubesats and the implementation of my decoder included in gr-satellites. The decoder was still missing a BCH decoder. I have now implemented a BCH decoder and included it in gr-satellites. Here I describe the details of this decoder.
Testing LDPC code erasure decoding performance
In my previous post I talked about the RFC5170 LDPC codes used in Outernet. There I explained in some detail the pseudorandom construction of the LDPC codes and the simple erasure decoding algorithm used both in free-outernet and in the official closed-source receiver.
The Outernet LDPC codes follow what I call the “identity scheme”. This is different from the staircase and triangle schemes introduced in the RFC. The identity scheme already appeared in the literature, but it did not make it into the RFC. See, for instance, the report by Roca and Neumann Design, Evaluation and Comparison of Four Large Block FEC Codecs, LDPC, LDGM, LDGM Staircase and LDGM Triangle, plus a Reed-Solomon Small Block FEC Codec, especially Section 2, where it is called “LDGM”.
I also commented that erasure decoding for an LDPC code (or any other linear code) amounts to solving a linear system. This can be done using any algebraic method, such as Gaussian elimination. However, the simple decoding algorithm used in Outernet is as follows: try to find an equation with only one unknown, solve for that unknown, and repeat until the system is solved. Clearly this algorithm can fail even if the system can be solved (see my previous post for some examples and formal results). I will refer to this algorithm as iterative decoding, as it is done in the RFC.
With these two things in mind, I wondered about the performance of the LDPC codes used in Outernet and the iterative decoding algorithm. I’ve done some simulations and here I present my results.
Outernet LDPC code revisited
I have been preparing the slides for my future talk about reverse-engineering Outernet at FAQin 2018. While doing this, I have been re-reading some of the material about the work done on LDPC code and FEC in Outernet by George Hopkins in January 2017. One of the things I didn’t do back then was to read carefully the LDPC decoding function implemented by George.
In my post I explained that the LDPC code used in Outernet followed RFC5170, and I wondered whether it used the staircase scheme or the triangle scheme. I also commented that erasure decoding with an LDPC code (or any other linear code, actually) was mathematically equivalent to solving a linear system where the unknowns correspond to the erased symbols. I observed that the decoding function looked very different from this mathematical procedure, but should do more or less the same thing. Now I have read the decoder implementation carefully and I have the answer to both questions.
ÑuSat finally decoded
More than a year ago, I spoke about my efforts to decode ÑuSat-1 and -2. I got as far as reverse-engineering the syncword and packet length, and I conjectured that the last 4 bytes of the packet were a CRC, but without the scrambler algorithm I couldn’t do much. Recently I’ve been exchanging some emails with Gerardo Richarte from Satellogic, which is the company behind the ÑuSat satellites. He has been able to provide me the details of the protocol that I wasn’t able to reverse engineer. The result of this exchange is that a complete decoder for ÑuSat-1 and -2 is now included in gr-satellites, together with an example recording. The beacon format is still unknown, but there is some ASCII data in the beacon. Here I summarise the technical details of the protocol used by ÑuSat. Thanks to Gerardo for his help and to Mike DK3WN for insisting into getting this job eventually done.
An erasure code based on Vandermonde matrices
I’ve been looking at an erasure code by Luigi Rizzo which is based on Vandermonde matrices, since this code is used in Outernet. In fact, it is the code implemented by the zfec library. Luigi Rizzo describes his code in a paper from 1997, but the paper can be very confusing and misleading because it describes the mathematics in very little detail. I needed to go to the source code to understand how it works. Actually, the idea behind this code is very simple. Here I do a mathematical description of the code and show that it is the same as a Reed-Solomon code. This is rather weird, because Luigi Rizzo makes no mention of Reed-Solomon codes, which were first described in 1960.
free-outernet gets LDPC decoding
In my previous post I talked about some small updates made by George Hopkins to my free-outernet project. In fact, George has been reverse engineering the ondd binary quite in depth and he has been able to reverse engineer the LDPC code which is used for file FEC. This solves a long-standing issue of free-outernet. Formerly, LDPC decoding was not implemented, so to recover a file successfully all the file blocks had to be received correctly. Now, with LDPC decoding the file can be recovered even if some of the file blocks are lost. Thus, the performance of free-outernet in this aspect should now be the same as the performance of the closed source ondd binary included in the official Outernet receiver. Many thanks to George, as this is a substantial improvement of free-outernet. Here I describe the latest changes made by George in free-outernet.