SMOG-P short codes

In my previous post I talked about the FEC used by the SMOG-P and ATL-1. In there, I reverse-engineered the long frames transmitted by SMOG-P and found that they use the AO-40 FEC protocol.

After publishing that post I started reverse-engineering the short frames. Meanwhile, Peter Horvath pointed me to a Github repository containing an implementation of the FEC used for short frames and long frames. I hadn’t seen that repository before (it’s not easy to search for SMOG-P or ATL-1 in Google, as many unrelated results come up). Indeed this repository contains the source of a FEC decoder for the short frames, so there is no need to reverse-engineer it.

Timur Kristóf, the author of that repository, says that the team plans to release the source for the decoder, but that they are currently very busy with the early operations of the satellites. This is very good news.

I have studied the code in the Github repository and included a decoder for the short FEC frames in gr-satellites.

Continue reading “SMOG-P short codes”

Decoding SMOG-P and ATL-1

Last Friday, an Electron rocket from Rocket Lab was launched from Mahia Launch Complex, New Zealand, carrying the ALE-2 microsatellite and 6 PocketQubes into a 400km polar orbit. Two of these PocketQubes are SMOG-P and ATL-1 from Budapest University of Technology and Economics.

They transmit in the 70cm Amateur satellite band, and although they have beeen successfully coordinated with IARU (see here and here), documentation about the protocols they use has not been published. There is some groundstation software available here, but the interesting part is implemented in the atlgnd_x86_64 and smogpgnd_x86_64 binary executables, for which source code is not available. As far as I know both satellites transmit using the same (or very similar) protocols.

In this post I describe my first attempts at reverse-engineering the transmissions of SMOG-P, with successful results. Preliminary support for decoding SMOG-P and ATL-1 has been added to gr-satellites in the maint-3.8 branch.

Continue reading “Decoding SMOG-P and ATL-1”

QO-100 beacon FEC decoder

Since the BPSK beacon on the QO-100 narrowband transponder was first activated, I had thought that it only transmitted messages using the AO-40 uncoded protocol. However, a Twitter conversation a few days ago with Rob Janssen PE1CHL convinced me that FEC messages might be sent in between uncoded messages.

The AO-40 FEC protocol used a concatenated code with a (160, 128) Reed-Solomon code and an r=1/2, k=7 convolutional code, together with scrambling and interleaving to achieve very good performance. The same protocol has then been used in the FUNcube satellites, so I have an AO-40 FEC decoder in gr-satellites since I added support for AO-73.

It is quite easy to notice that the QO-100 beacon transmits both uncoded and FEC messages. Indeed, using my gr-satellites decoder, I see that an uncoded message is transmitted every 23 seconds approximately. Since an uncoded message comprises 514 bytes, it takes 10.28 seconds to transmit it at 400baud, so something else must be sent between uncoded messages.

A FEC message is formed by 5200 symbols (after applying FEC), so it takes 13 seconds to transmit at 400baud. This gives us the total 23.28 seconds that I had observed between uncoded messages. Note that the contents of the uncoded and FEC blocks are different. An uncoded block contains 8 lines of 64 characters plus 2 bytes of CRC. A FEC block only contains 4 lines of 64 characters, and no CRC.

I have added a FEC decoder to the QO-100 decoder in gr-satellites, so that it now decodes both FEC and uncoded messages.

P25 vocoder FEC

Following a discussion with Carlos Cabezas EB4FBZ over on the Spanish telegram group Radiofrikis about using Codec2 with DMR, I set out to study the error correction used in DMR, since it quickly caught my eye as something rather interesting. As some may know, I’m not a fan of using DMR for Amateur Radio, so I don’t know much about its technical details. On the other hand, Carlos knows a lot about DMR, so I’ve learned much with this discussion.

In principle, DMR is codec agnostic, but all the existing implementations use a 2450bps AMBE codec. The details of the encoding and FEC are taken directly from the P25 Half Rate Vocoder specification, which encodes a 2450bps MBE stream as a 3600bps stream. Here I look at some interesting details regarding the FEC in this specification.

Continue reading “P25 vocoder FEC”

Using a Golay(24,12) decoder for Golay(23,12)

Yesterday I explained an algebraic decoding algorithm for Golay(24,12) and commented that it was not easy to adapt it to decode Golay(23,12). Today I’ve thought of a simple way to use any Golay(24,12) decoder to decode Golay(23,12).

Recall that a systematic Golay(23,12) code is obtained from a systematic Golay(24,12) by omitting the last component of each codeword (i.e., the codeword \((c_1,\ldots,c_{24})\) from the Golay(24,12) code gives the codeword \((c_1,\ldots,c_{23})\) from the Golay(23,12) code). Conversely, one can obtain a systematic Golay(24,12) code from a systematic Golay(23,12) code by adding a parity bit at the end. This means that \(c_{24} = \sum_{j=1}^{23} c_j\), since \(\sum_{j=1}^{24} c_j = 0\) for all words in a Golay(24,12) code.

The idea to decode a Golay(23,12) code with a Golay(24,12) decoder is first to restore the parity bit \(c_{24}\) and then apply the Golay(24,12) decoder. However, if there are errors in the received codeword, the restored parity bit can also be in error, increasing the number of errors in one.

The key remark is that both Golay(23,12) and Golay(24,12) are able to correct up to 3 errors. Therefore, we only care about restoring the parity bit correctly in the case when there are exactly 3 errors. If there are 2 or less errors, adding another error still gives a word decodable by the Golay(24,12) decoder.

Now note that if there are exactly 3 errors in \((c_1,\ldots,c_{23})\), then \(\sum_{j=1}^{23} c_j\) gives the opposite from the parity of the original codeword. Therefore, we should restore \(c_{24}\) as\[c_{24} = 1 + \sum_{j=1}^{23} c_j\]and then apply the Golay(24,12) decoder.

Algebraic decoding of Golay(24,12)

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.

Continue reading “Algebraic decoding of Golay(24,12)”

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.

Continue reading “Soft Viterbi decoder for AO-40 FEC”

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.

Continue reading “Testing LDPC code erasure decoding performance”

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.

Continue reading “Outernet LDPC code revisited”