RS Forward Error Correction for Variable-Length Frames

Goddard Space Flight Center, Greenbelt, Maryland

A method of forward error correction by Reed-Solomon (RS) coding has been devised to increase the link margins of data-communication systems that must handle variable-length frames or packets of data. Heretofore, RS coding has involved fixed-length blocks: In order to encode variable-length frames, it has been necessary to (a) choose a fixed block length equal to a multiple of some given block length and greater than or equal to the length of the longest variable-length frame and (b) in the case of a frame shorter than the fixed block length, pad or fill the remainder of the block with extra bytes. This is very inefficient because the fill conveys no useful information, and any errors in the fill diminish the overall coding gain by using up some or all of the available error-correction capacity.

Virtual Fill Symbols conceptually occupy the portion of a code block not occupied by a data frame shorter than the longest allowable frame. Unlike pad or real fill symbols in the traditional approach, virtual fill symbols are not transmitted. In the present method, the number of virtual fill symbols is varied dynamically to compensate for variable frame length.

The present method accommodates dynamically varying frame length by use of equations that relate the frame length to a quantity known as the virtual-fill parameter. The concept of virtual fill (see figure) is not new; what is new here is the way in which virtual fill is used. In the traditional fixed-length-block approach, all of the code parameters, including the virtual-fill parameter and the frame length, are set in advance or initialized at startup time and are not changed during the encoding/decoding process. In the present method, the virtual-fill parameter and the frame length are allowed to vary while the other parameters are held constant.

Let

m ≡ the number of bits per symbol

n ≡ 2^m-1 total number of symbols per code block

t ≡ number of correctable errors

VF ≡ number of virtual fill symbols (-0)

I ≡ interleaving parameter (-1)

FL ≡ total frame length [number of data + parity (check) symbols]

FSPL ≡ frame-synchronization-pattern length

DFL ≡ length of (number of symbols in) the data field in a code block

CBL ≡ number of data plus parity (check) symbols in a code block.

Then the basic equations for the RS code parameters are the following:

FL = FSPL + (n – 2t – VF)I + 2tI,
DFL = n – 2t – VF, and
CBL= n – VF.

Straightforward algebraic manipulation of the foregoing equations yields:

DFL = (FL – FSPL)/I – 2t and
VF = n – (FL – FSPL)/I.

Equation 4 is used in the RS encoder because DFL is a parameter of the encoding algorithm. Equation 5 is used to dynamically obtain the virtual fill length for a given frame based on its length. In both the encoder and decoder, the limit check on valid frame length is given by

FSPL + 2tI ≤ FL ≤ FSPL + nI.

These equations can readily be incorporated into a software implementation and conceivably also into a hardware implementation of the RS encoder and decoder, provided that the encoder and decoder can each act individually to determine the length of the current frame.

Even in a system in which data are generated in fixed-length frames, it could be advantageous to dynamically vary FL, in response to the bit-error rate, to optimize the forward-error-correction capability. In general, the number of check symbols per code block and the coding gain increase as FL decreases. The disadvantage of this method is that proportions of overhead are greater for smaller packets.

This work was done by Steve Duran of Goddard Space Flight Center.

GSC-13916