Forward Error Correction (FEC)

topics: Programming

A technique to recover the error occurring in data storage, data transfer, without having to retransmit the original data. This is mostly used in Deep Space communication, CD/DVD storage, udpcast, etc.

FEC works by adding redundant information to the original data, which can be used to reconstruct the lost or corrupted data. The amount of redundant information added depends on the level of error correction required.

There are a few different types of FEC (forward error correction), that works on different type of cases. Some of the common types of FEC are as follows:

1. Block codes: In block codes, a group of bits is taken together and checked for errors. If an error is found, the entire group is retransmitted.
2. Convolutional codes: In convolutional codes, each bit is encoded along with its neighbouring bits. This provides more redundancy and the ability to detect and correct errors in real-time.
3. Turbo codes: Turbo codes are a type of convolutional code that uses multiple encoders and decoders to provide even greater error correction capabilities.
4. Reed-Solomon codes: Reed-Solomon codes are used specifically for correcting errors in data stored on disks, CDs, and other digital media. They can correct errors on a byte-by-byte basis. This is useful in case of burst packet loss.

Overall, the choice of FEC depends on the application and the specific type of error that needs to be corrected.

Reed Solomon codes are used in situations where errors occur in bursts, such as in CD/DVD storage. These codes add extra parity bits to the data, allowing the receiver to recover the original data even if a few bits are lost due to a burst error.

Convolutional codes are used in situations where errors occur randomly, such as in wireless communication. These codes add redundancy by using a sliding window to encode the data, which allows the receiver to correct random errors in the received data.

By using both Reed Solomon and Convolutional codes, the chances of data loss due to errors can be minimized. However, this also means that more redundant information is added, which increases the amount of network bandwidth required for data transmission.

Other types of network coding

• RLNC (Random Linear Network Coding)

FEC libraries

Cli tools

• Redupe: Forward Error Correction, GitHub - rescrv/redupe: redupe implements forward error correction
  • unable to compile, got c99 standard issue
• tahoe-lafs/zfec: zfec -- an efficient, portable erasure coding tool
  • Cli tool with C and, python binding
  • only work for files. It can only encode stdin to files, send the files over, then use unzfec to merge it back. This won't work for kafka streaming.
  • We could write files with exact lines, then zfec it, transfer the files, then merge it back. But how to solve the problem of when to do the unzfec?
• GitHub - WojciechMigda/zfex: zfex — an efficient, portable erasure coding tool
  • This is very recent, can hit up to 4G/s, improvement on the zfec. But this one only work on file
• rsbep
  • GitHub - opencoff/rsbep: Add Reed Solomon Error correction to archives
  • Seem to be less efficient, as it does not use "erasure codes"
• Hackernews link that contains a few more other similar tools
  • Zfec – Efficient, portable erasure coding tool | Hacker News

Libraries

• raptorq/main.py
  • source: Hacker News
  • very fast rust based python binding for RaptorQ implementation for FEC
  • only works for python or rust
• GitHub - sleepybishop/nanorq: fast compact raptorq (rfc6330) codec in c
  • it says with single core, it can hit multi gigabit speed
  • cannot compile, oblas_avx.c:56:7: warning: implicit declaration of function ‘_mm256_loadu2_m128i’; did you mean ‘_mm256_loadu_si256’? [-Wimplicit-function-declaration]
• GitHub - catid/longhair: Longhair : O(N^2) Cauchy Reed-Solomon Block Erasure Code for Small Data
  • last updated 2 years ago
  • written in C++ with C wrapper
  • encode k=23, m=10 encode speed=1064 MB/s

Cauchy Caterpillar

GitHub - catid/CauchyCaterpillar: Cauchy Caterpillar : O(N^2) Short-Window Streaming Erasure Code

This is something that superseds the shorthair thingy
GitHub - catid/shorthair: Shorthair : Generational Block Streaming Erasure Codes
There is a limit on data rate (< 2000 packets/second)
GitHub - catid/leopard: Leopard-RS : O(N Log N) MDS Reed-Solomon Block Erasure Code for Large Data

Wirehair

GitHub - catid/wirehair: Wirehair : O(N) Fountain Code for Large Data

• written in C++ with C wrapper
• may require N+1, N+2 or more to recover, on avg, N+0.02
• test result
  • n=1000, size=1300, encoder create (925 mbps), encode (7778 mbps), decode (740 mbps), overhead piece = 0.0185 (more than n) on my laptop
  • n=1000, size=1300, encoder create (773 mbps), encode (6252 mbps), decode (621 mbps), overhead piece = 0.0185 (more than n) on 223 server
• g++ -o test2 test2.c -lwirehair
• can handle without order, but block ID has to be the same, if not it will be out of order
• cannot handle data corruption, but it can handle missing packet. This can be handled by either decompression failure or udp checksum failure

Requirements

• data must be in exact block size
• block id must be given, either from header or from sequential receiving ID
• GitHub - catid/cm256: Fast GF(256) Cauchy MDS Block Erasure Codec in C
  • last updated 2 years ago
  • written in C++ with C wrapper
• librecast/lcrq: C implementation of RFC6330 RaptorQ Codes
  • This is by a project called librecast, which is ipv6 multicast
  • Librecast - Decentralisation and Privacy with Multicast
  • looks like it has completed the features that we need, like server, client
  • this is quite an ambitious project, I think this requires bi-directional
• quiet/libcorrect: C library Convolutional codes and Reed-Solomon
  • RS from this one cannot be used, as it requires a lot of work: source: network simulation help for reed solomon codes, and only supports 255 bytes of payload
• unisync/unicast.c at main - unisync - Codeberg.org
  • librecast project's unicast code
• https://fenrirproject.org/Luker/libRaptorQ/-/wikis/libRaptorQ-RaptorQ.pdf
  • how raptorQ works
• Why DF Raptor is better than Reed Solomon for Streaming Applications.pdf
• libRaptorQ: RaptorQ RFC6330 C++11 implementation
  • need to implement a way to tell the receiver how long is each packet/block
• liberasurecode: Erasure Code API library written in C
• schifra: C++ Reed Solomon Error Correcting Library : NOGO
  • C++ library that seems promising, with example usage code and docs
  • Need to purchase license for commercial usage: Schifra Reed-Solomon Error Correcting Code Library
• OpenFEC.org
  • list of libraries for the FEC stuff
  • this only support Reed Solomon and LDPC
• GitHub - wangyu-/UDPspeeder
  • This has implementation of Reed Solomon, easily copied
  • this implementation requires C++
• libsathelper/reedsolomon.cpp
  • code using the libcorrect
• Sci-Hub | | 10.1109/ICC.2018.8422948
  • Raptor Code UDP (cannot find source code)
• GitHub - lorinder/TvRQ: Test vector RaptorQ
  • library for raptorq in C, also has python binding
• AFF3CT - A Fast Forward Error Correction Toolbox
• Flute
  • Rust based udpcast type, but also have support for python binding
• RFC 9223: Real-Time Transport Object Delivery over Unidirectional Transport (ROUTE): a new protocol with FEC frames built-in
  • route · gpac/gpac Wiki · GitHub : multimedia streaming tool that implements ROUTE protocol
• SMPTE Standard - Unidirectional Transport of Constant Bit Rate MPEG-2 Transport Streams on IP Networks
• GitHub - cea-sec/hairgap: A set of tools to transfer data over a unidirectional network link (typically a network diode).
  • GitHub - catid/wirehair: Wirehair : O(N) Fountain Code for Large Data
• GitHub - 5G-MAG/rt-libflute: File Delivery over Unidirectional Transport (FLUTE): C++

Tuning guides

• Ethernet — Performance Tuning on Linux
• How to achieve low latency with 10Gbps Ethernet

FEC modes

• Random Linear Network Coding
• LDPC

Options

• Use libcorrect then implement it on udpperf or another dpdk
• Use raptorq/main.py and implement it in python code
  • this will be better, lead to better control over the streaming, compression, etc

Error correction for UDP transmission? : r/learnpython
useful info on the implementation

the error distance must be below the group size at all times to prevent data loss. I would rather suggest to encode the RS data within the chunks to prevent multiple dropped packets in a row automatically resulting in data loss. Like with the reedsolomon library, that allows you to set the chunksize to the MTU of your network packet (I would go a little lower in case you're sending this over the internet, like 1300 or so). Then the amount of failed packets as a total counts, not in what pattern they appeared.

Generated Flashcards

#flashcards

What is Forward Error Correction? :: A technique to recover the error occurring in data storage, data transfer, without having to retransmit the original data.

What are Block codes? :: In block codes, a group of bits is taken together and checked for errors. If an error is found, the entire group is retransmitted.

What are Convolutional codes? :: In convolutional codes, each bit is encoded along with its neighbouring bits. This provides more redundancy and the ability to detect and correct errors in real-time.

What are Turbo Codes? :: Turbo codes are a type of convolutional code that uses multiple encoders and decoders to provide even greater error correction capabilities.

When do Reed Solomon Codes apply?:: Reed Solomon codes are used specifically for correcting errors in data stored on disks, CDs, and other digital media. They can correct errors on a byte-by-byte basis

Which type of FEC works on burst lost cases? :: Reed Solomon

Which type of FEC works on random packet lost cases? :: Convolutional code

What are the benefits of using both types of FEC together? :: Minimise chances of data loss

What are some drawbacks when using both types of FEC together?:: Incur more network bandwidth