SSDV systematic erasure FEC

This Rust crate implements a systematic erasure FEC scheme for SSDV. The FEC scheme is based on a Reed-Solomon code over GF(2¹⁶) used as a fountain-like code. This idea was first described in the blog post An erasure FEC for SSDV by the author of this crate.

Given an SSDV image formed by k SSDV packets, the FEC encoder can generate up to 2¹⁶ different SSDV packets identified by a packet ID from 0 to 2¹⁶-1. The packets with IDs from 0 to k-1 which are called "systematic packets" and are the same as the k packets of the original image. The remaining packets are called "FEC packets". Each packet can be generated on demand according to the needs of the transmitter. The large amount of 2¹⁶ distinct packets than can be generated provides a virtually limitless source of packets. The receiver can recover the original SSDV image from any set of k distinct packets.

This implementation of the FEC scheme uses 218-byte SSDV packets following the format used by Longjiang-2, which omits the sync byte, packet type and callsign fields (but includes them implicitly in the generation of the CRC-32).

The crate supports no_std and the implementation is designed with small microcontrollers in mind. The GF(2¹⁶) arithmetic only uses two tables of 256 bytes each that are included in the .rodata section. The FEC encoder and decoder work with externally provided slices, giving freedom as to how to perform memory allocation, and do the computations in-place when possible. The memory required for encoding corresponds to a buffer containing the k SSDV packets of the original image, and a buffer containing the packet being encoded. The memory required for decoding corresponds to a buffer containing at least k distinct received SSDV packets, and another buffer where the k SSDV packets that compose the original image can be written. Besides these buffers, the algorithms use only a small amount of stack space.

A simple CLI application that can perform encoding and decoding can be built with the cli feature, which is enabled by default.

CLI application usage

The CLI application can be installed using

cargo install ssdv-fec

The ssdv-fec application supports the commands encode and decode. To perform encoding, it is necessary to specify the number of packets to generate in the output. This can be done with the --npackets argument to specify a fixed number of packets, or with the --rate argument to specify the coding rate. If --rate is used, the number of encoded packets is equal to the number of packets in the original image divided by the coding rate (which must be between 0 and 1). An example SSDV image can be found in the src/test_data directory. These are examples of encoding.

ssdv-fec encode --rate 0.8 src/test_data/img_230.ssdv encoded.ssdv
ssdv-fec encode --npackets 256 src/test_data/img_230.ssdv encoded.ssdv
ssdv-fec encode --first 57 --npackets 15 src/test_data/img_230.ssdv encoded.ssdv

By default the packet ID of the first encoded packet is zero, but another first packet ID can be chosen with the --first argument. The remaining packets use consecutive packet IDs. The --first argument can be used to encode an additional set of packets distinct from the previously encoded packets.

Decoding only requires the input file and output file as arguments. Here is an example of decoding.

ssdv-fec decode encoded.ssdv decoded.ssdv

The input file for decoding should only contain packets of a single image. The packets can be in any order an they can be repeated. If decoding fails, the application indicates the cause of the error.

API documentation

The documentation for the ssdv-fec Rust crate is hosted in docs.rs.

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.