Forward Error Correction

Reed-Solomon Encoded Message Format

DATA

PARITY

DATA

Forward Error Correction (FEC) is accomplished by applying a (31,21) Reed-Solomon code to the data. The Reed-Solomon algorithm uses 5 bit symbols, with 31 total symbols per codeword, comprised of 21 data symbols followed by 10 parity symbols. Note that the Makito X implementation does not check parity symbols.

The code over GF(2⁵) is defined by the primitive polynomial x⁵+x²+1. The power of the first of the 10 consecutive roots of the generator polynomial is 120, and the primitive of the field is given as x. Each codeword is 155 bits long. The encoded sequence is formatted as sets of 105 bits of message data, followed by 50 bits of parity information as shown in the previous figure. Symbols are packed into bytes MSb first. (i.e., the symbol 10111 would get packed into a byte as 10111000, with the next symbol starting in the 3 least significant bits of that byte.)

As the input data cannot necessarily be broken into an integer number of codewords, prior to the Reed-Solomon encoding process, a 16 bit little-endian length field (len) is prepended to the data. This length field is a count of the number of original data bytes in the message (not including the 2 bytes of len). The message data is then padded by appending sufficient zero bits as to result in an integer number of codewords. When a block of received symbols is being decoded, if the total decoded length is less than len+2, then the whole block is considered to be in error and is discarded. If it is longer than len+2, then the two bytes of len are removed, and the next len bytes are extracted and passed up to the next layer.

For example, if the input message is "hello", then the string passed to the Reed-Solomon encoder would be 05 00 68 65 6c 6c 6f., and the resulting coded sequence would be (including 49 padding bits appended to the source data to make it an integer multiple of 105 bits in length, and the five pad bits appended to the encoded sequence to fill out the last byte):

05 00 68 65 6c 6c 6f 00 00 00 00 00 00 3b e3 8b e5 c7 ac 20.