SSDV is an amateur radio protocol that is used to transmit images in packets, in a way that is tolerant to packet loss. It is based on JPEG, but unlike a regular JPEG file, where losing even a small part of the file has catastrophic results, in SSDV different blocks of the image are compressed independently. This means that packet loss affects only the corresponding blocks, and the image can still be decoded and displayed, albeit with some missing blocks.
SSDV was originally designed for transmission from high-altitude balloons (see this reference for more information), but it has also been used for some satellite missions, including Longjiang-2, a Chinese lunar orbiting satellite.
Even though SSDV is tolerant to packet loss, to obtain the full image it is necessary to receive all the packets that form the image. If some packets are lost, then it is necessary to retransmit them. Here I present an erasure FEC scheme that is backwards-compatible with SSDV, in the sense that the first packets transmitted by this scheme are identical to the usual \(k\) packets of standard SSDV, and augments the transmission with FEC packets in such a way that the complete image can be recovered from any set of \(k\) packets (so there is no encoding overhead). The FEC packets work as a fountain code, since it is possible to generate up to \(2^{16}\) packets, which is a limit unlikely to be reached in practice.
Motivation and intended applications
The main motivation for this FEC scheme comes from the Longjiang-2 mission. This satellite, also known as DSLWP-B, carried a small camera and transmitted the images from the camera on demand by telecommand using SSDV. The downlink bitrate was usually 125 bps, so transmitting a single image would take around 20 or 30 minutes. It was not uncommon to miss a few of the SSDV packets. Even if the SNR was quite good when the 25 meter radiotelescope at Dwingeloo was used to receive the downlink, there could be occasional problems such as frequency jumps in the on-board TCXO.
In some cases, the missing pieces of the image corresponded to empty parts of the sky that were known to be completely black. In other cases, the missing parts were interesting, so we attempted to receive the complete image by commanding the spacecraft to transmit the missing packets again, before new images were taken that would overwrite the image in the on-board memory. There were two possible ways of doing this. It was possible to send a telecommand that would start the SSDV transmission again, starting from a particular packet number. Alternatively, it was possible to send a telecommand that would cause the transmission of a single SSDV packet.
While the first option seems too wasteful if we were only missing a few packets, in practice it turned out to be the most useful. Telecommand transmission was slow and somewhat unreliable, which meant that it was usually faster to send a single command to restart the image transmission by the point where the first packet was missing than to telecommand the transmission of a dozen packets individually. In any case, keeping track of what packets we were missing for each image was a time consuming and error-prone process.
The FEC scheme proposed in this post is ideal for this kind of situation. Assuming that the SSDV image size is \(k\) packets, the FEC algorithm is able to recover the complete image from any set of \(k\) received packets. This means that if we are missing \(d\) packets from an image, then we can telecommand the spacecraft to transmit \(d\) new FEC packets (or slightly more than \(d\), just in case we lose some of these packets also). We do not need to specify the indices of the packets that we are missing, which is what prevented us from being able to command the transmission of the packets we were missing with a single telecommand (the telecommand would need to carry the list of missing indices, and would be too large).
Additionally, when the image is transmitted for the first time, it is possible to transmit \(k + l\) packets, instead of the usual \(k\). When this is done, we can miss up to \(l\) packets and still be able to decode the image without the need to telecommand a retransmission. The number \(l\) can be fine-tuned during the mission, as we gain knowledge on the reliability that the packet transmissions have and get an estimate of the typical packet loss rate. This approach can also be used in applications where it is not possible to telecommand a retransmission, such as in most high-altitude balloon payloads.
FEC algorithm
The FEC algorithm is a systematic Reed-Solomon-like \((2^{16}, k)\) code over the field \(GF(2^{16})\), used as an erasure FEC. This can be used as a fountain code, because the original \(k\) blocks of data can be encoded as a set of \(2^{16}\) blocks with the property that the the original data can be recovered from any set of \(k\) encoded blocks. It is not necessary to generate or transmit the total set of \(2^{16}\) encoded blocks. The value \(2^{16}\) just gives a limit to the total number of distinct blocks that can be generated. In applications in which this limit is not reached, the pool from which new distinct blocks can be drawn looks endless, as in a true fountain code.
The code works as follows. We assume that we have chosen a numbering \(\alpha_0, \alpha_1,\ldots, \alpha_{2^{16}-1}\) of the elements of \(GF(2^{16})\). Given a message \((a_0, \ldots, a_{k-1})\in GF(2^{16})^k\), first we find the polynomial \(p \in GF(2^{16})[x]\) of degree at most \(k – 1\) such that \(p(\alpha_j) = a_j\) for \(j = 0,\ldots, k-1\). The coefficients of this polynomial can be found by solving a linear system (which has a Vandermonde matrix) or by using Lagrange polynomials. The encoded message is \((b_0,b_1,\ldots, b_{2^{16}-1}) \in GF(2^{16})^{2^{16}}\), where \(b_j = p(\alpha_j)\) for \(j = 0, \ldots, 2^{16}-1\). Note that \(b_j = a_j\) for \(j = 0, \ldots, k-1\) by construction, so the code is systematic.
Given a subset of \(k\) encoded symbols \(\{b_{n_1}, b_{n_2}, \ldots, b_{n_k}\}\), where the indices \(n_j\) are all distinct, we can find \(p\) as the unique polynomial of degree at most \(k – 1\) that satisfies \(p(\alpha_{n_j}) = b_{n_j}\) for \(j = 1, \ldots, k\). Again, the coefficients of \(p\) can be found by solving a linear system with a Vandermonde matrix or using Lagrange polynomials. Once we have found the polynomial \(p\), the original message can be recovered as \(a_j = p(\alpha_j)\) for \(j = 0, \ldots, k-1\).
Note that this algorithm assumes that the receiver, besides having \(k\) encoded symbols, knows the number \(k\) and also knows the indices corresponding to each of the \(k\) encoded symbols.
SSDV packet format
The format of SSDV packets is documented here. This FEC scheme maintains the format of the first \(k\) packets (the ones which correspond to the systematic part of the FEC code) unchanged, so that the typical SSDV decoder software can be used to display the image updating in real time as it is being received. These \(k\) packets are called systematic packets. The scheme is able to generate up to \(2^{16}-k\) distinct FEC packets, which are transmitted after the \(k\) systematic packets. When the receiver has collected a total of \(k\) packets, the complete image can be recovered.
Note that if the receiver is missing some packets at the end of the transmission of the systematic packets, the displayed image doesn’t change until we have collected \(k\) packets. Then it suddenly changes to show the complete image. I don’t know if it would be possible to devise a FEC scheme that allows updating the partial progress while FEC packets are being received. The usual erasure FEC algorithms either recover all the erasures or none of them. I don’t know if there are FEC algorithms that are able to recover a few erasures when they are still missing some data to recover all of them.
To define the packet format for this FEC scheme, I have focused on the variant of SSDV used by Longjiang-2. This differs from standard SSDV in that the sync byte, packet type, and callsign fields, as well as the Reed-Solomon FEC data, are not transmitted, in order to save bandwidth. However, the packet type and callsign fields are still taken into account for the calculation of the CRC-32. Since these fields have fixed values, this is equivalent to not taking them into account and performing the CRC with an initial register value of 0x4EE4FDE1, instead of the usual 0xFFFFFFFF (this value is the “partial CRC” of these implicit fields). The FEC scheme described here can also be applied to the standard SSDV packet format.
The fields from the systematic packets that are protected by the erasure FEC algorithm are the MCU offset, MCU index and payload data fields. This is a total of 208 bytes, which luckily is divisible by 2, so the data to be protected can be encoded as 104 symbols from \(GF(2^{16})\). The FEC algorithm is applied to 104 independent messages of \(k\) symbols, where \(k\) is number of systematic packets (which depends on the size of the SSDV image). Each message to be FEC encoded is formed by taking the pair of bytes in the same position in each of the \(k\) systematic SSDV packets.
The FEC packets have the following fields:
- Image ID (1 byte). This is the same as in the systematic SSDV packets.
- Packet ID (2 bytes). This corresponds to the encoded symbol index, so it keeps counting \(k\), \(k+1\), etc., as new FEC packets are generated.
- Number of systematic packets (2 bytes). This field replaces the image width and image height fields, which are present in all the systematic packets (the FEC scheme assumes that the decoder will receive at least one systematic packet to get this information). Since we need a reliable way to retrieve the number \(k\), this is stored in all the FEC packets. The decoder can find the number \(k\) either by receiving the last systematic packet (which has the EOI flag enabled) or by receiving any FEC packet.
- Flags (1 byte). The flags are as in the systematic packets, with the addition of flag
0x40(a reserved bit in standard SSDV), which marks this as a FEC packet. - FEC data (208 bytes). This stores the 104 \(GF(2^{16})\) symbols from the 104 independent codewords.
- CRC-32 (4 bytes). The same algorithm as in the systematic packets is used. The CRC-32 calculation covers all the previous fields (expect the sync byte, if sync bytes are used, which is the case in standard SSDV).
Prototype implementation
I have made a prototype implementation of this FEC scheme in this Jupyter notebook to show the algorithm in action. I used the galois Python package for the arithmetic in \(GF(2^{16})\). The notebook uses the SSDV data from one of the images of the 2 July 2019 solar eclipse taken with Longjiang-2. This particular image consists of 65 packets (so \(k = 65\)).
There are several scenarios demonstrated in the notebook. A rather extreme one involves generating \(2k\) packets (so we have 65 systematic packets and 65 FEC packets) and dropping 50% of them randomly. The results when we process such image with the standard SSDV decoder (which only use systematic packets) are pretty bad, even though most parts of the image are completely black.
When we process the systematic and FEC packets with the erasure FEC decoder, we are able to recover the complete image.
Implementation choices
There are some implementation choices that should be specified so that all the implementations of this FEC scheme are compatible. These choices are the following:
- A mapping between 16-bit strings and elements of \(GF(2^{16})\). This is used to convert between pairs of bytes and symbols in \(GF(2^{16})\) to apply the FEC algorithm. In doing so, the 16-bit string is formed from the bytes B0 B1 by first taking the 8 bits from B0 in MSB order and then the 8 bits from B1 in MSB order.
- An enumeration of all the elements of \(GF(2^{16})\), as \(\alpha_0, \alpha_1, \ldots, \alpha_{2^{16}-1}\). This is used in the FEC algorithm itself.
A straightforward way to define these two choices is to construct \(GF(2^{16})\) as the quotient \(GF(2)[x]/(p)\), where \(p\) is an irreducible polynomial of degree 16 in \(GF(2)[x]\), and to map the bit string \(b_{15}b_{14}\cdots b_1b_0\) to the polynomial\[b_{15}x^{15} + b_{14}x^{14} + \cdots + b_1 x + b_0.\]This fixes the mapping required in 1. Once such a mapping is fixed, 2. can be defined by mapping the indices \(j = 0, \ldots, 2^{16}-1\) to their binary representation in MSB order and then using the mapping in 1. to obtain the corresponding elements in \(GF(2^{16})\).
The galois Python package uses the Conway polynomial\[p(x) = x^{16} + x^5 + x^3 + x^2 + 1\]to construct the field \(GF(2^{16})\), and the rest of the prototype implementation follows the conventions described above regarding how 1. and 2. are defined. For a production implementation, I should think whether it makes sense to maintain the Conway polynomial or whether it can be advantageous for the performance of the computations to choose a different irreducible polynomial.
Future work
I am planning to write at some point a Rust implementation of the FEC algorithm described here. Probably this will have a custom implementation of the arithmetic in \(GF(2^{16})\). The implementation will have an API/ABI as a C library so that it can be called from the usual SSDV software.
2 comments