The VOCAL implementation of Reed Solomon (RS) Forward Error Correction (FEC) algorithms is available in several forms. The forms include pure software and software with varying levels of hardware acceleration utilizing UDI or other custom hardware instructions. Pure software solutions are available in several different forms for both the encoder and decoder. Different versions allow speed versus memory tradeoffs to be made, and allow efficient and easy expansion of the code for assembly language optimization. Performance numbers are available for hardware assisted and optimized software implementations.
As with all VOCAL software libraries, optimized algorithms are available in both ANSI C and platform specific versions. Supported platforms include many leading DSP architectures, including but not limited to ADI, ARM, DSP Group, LSI Logic LSP, MIPS and TI families. Versions are also available for general-purpose systems without hardware acceleration such as Intel/x86, as well as PPC, MIPS, ARM, and others.
Reed Solomon Algorithm
The Reed Solomon algorithms rely on special properties of finite-arithmetic Galois Field (GF) operations. The use of hardware acceleration for these operations can be used to greatly improve performance; for example, on the MIPS architecture, UDI/CorExtend instructions may be used for this purpose. Multiple levels of hardware acceleration are available, including single cycle multiply and inverse, as well as parallel multiplication and general purpose bit-slicing/composite field operations.
Reed Solomon codes are error correcting codes that have found wide ranging applications through out the fields of digital communication and storage. Some of which include:
- Storage Devices (hard disks, compact disks, DVD, barcodes)
- Wireless Communication (mobile phones, microwave links)
- Digital Television
- Broadband Modems (ADSL, xDSL, etc)
- Deep Space and Satellite Communications Networks (CCSDS)
These codes are specified as RS (n, k), with m bit symbols. This means that the encoder takes k data symbols of m bits each, appends n – k parity symbols, and produces a code word of n symbols ( each of m bits).
Hence, RS codes of the form RS (2^8) lend themselves well to digital communication.
Primitive polynomials are of interest here because they are used to define the Galois field. A popular choice for a primitive polynomial is:
The VOCAL implementation has the ability to perform all combinations of RS (n, k) [n = 255, and 0 < k < n] , for any of the 16 possible Galois fields, including the 0x87 field used by CCSDS. Additionally, the VOCAL RS modules can use any arbitrary generator polynomial for the calculation of the parity symbols.
Encoder
The Reed-Solomon encoder reads in k data symbols, computes the n – k parity symbols, and appends the parity symbols to the k data symbols for a total of n symbols. The encoder is essentially a 2t tap shift register where each register is m bits wide. The multiplier coefficients are the coefficients of the RS generator polynomial. The general idea is the construction of a polynomial; the coefficients produced will be symbols such that the generator polynomial will exactly divide the data/parity polynomial.
Decoder
The Reed-Solomon decoder tries to correct errors and/or erasures by calculating the syndromes for each codeword. Based upon the syndromes the decoder is able to determine the number of errors in the received block. If there are errors present, the decoder tries to find the locations of the errors using the Berlekamp-Massey algorithm by creating an error locator polynomial. The roots of this polynomial are found using the Chien search algorithm. Using Forney’s algorithm, the symbol error values are found and corrected. For an RS (n, k) code where n – k = 2T, the decoder can correct up to T symbol errors in the code word. Given that errors may only be corrected in units of single symbols (typically 8 data bits), Reed-Solomon coders work best for correcting burst errors.