SimpleFEC

Abstract

When developing MatelotRadio I came to the point where character transmission worked fine and chatting with a human partner became fun. But as it is always with radio transmission I got occasionally inverted bits due to noise. So, to go the next step and enabling any kind of radio mail or computer-to-computer communication, a forward error correction was needed. Searching around in the internet I couldn't find anything suitable, i. e. there are very enhanced algorithms implemented in WiFi drivers or Linux libraries, but none of them seemed to be easy extractable, especially for a tiny microcontroller. On the other hand side there are plenty of implementations of Hamming code, that are suitable only for academic purposes. That means, each bit info is stored in a byte, 3 bit cover a nibble (Hamming(7,4)) and there is no concept of applying this to a string. After a bit of playing around I began to write my own FEC.

Software description

Hamming(31,26)-like implementation with small footprint in RAM and ROM, suitable e. g. for AVR microcontrollers. Singe bit errors in each 26 bit block will be corrected. The correction is done in a brute force approach, therefore it isn't as fast as true Hamming would be. Memory consumption on Atmega 328p/Arduino Nano: ROM<2k, no static RAM usage.

void SimpleFecPutFec(void *data, int len, void *fecData)
reads len bytes from data, calculates the parity bits and stores them to fecData. fecData must be capable of 5 bits per each 26 bits block of data.

void SimpleFecRepairData(void *data, int len, void *fecData)
checks len bytes of data against fecData and flips bits whenever this is likely to be correct.

uint16_t SimpleFecGetFecDataLength(int len)
returns the required memory space in bytes to store FEC parity data for a data set of length len.

uint8_t CalcXorChecksum(void *data, uint16_t length)
returns a XOR checksum calculated over length bytes of data. This is a small helper not needed for FEC.

Download

Here it is.

Try it yourself

Enter a text. A random bit of every 26bit block will be corrupted and afterwards repaired.
To keep things easy (html), only standard characters are displayed. SimpleFEC works on binary data.


Text length: 65 bytes, 13 bytes needed to store FEC parity data.

INPUT:     Das tritt nach meiner Kenntnis ... ist das sofort  unverzueglich.

CORRUPTED: Tas triut Nach  eijer Keontniq .   is  das sodobt  unterzugclichn

REPAIRED:  Das tritt nach meiner Kenntnis ... ist das sofort  unverzueglich.