Call Today 716.688.4675

Reed Solomon (RS) Algorithm Overview

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)


Application of Reed-Solomon Codes
RS codes are systematic linear block codes, residing in a subset of the BCH codes called nonbinary BCH. It is block because the original message is split into fixed length blocks and each block is split into m bit symbols; linear because each m bit symbol is a valid symbol; and systmatic because the transmitted information contains the original data with extra CRC or ‘parity’ bits appended.

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).


Breakdown of a RS (255-233) Codeword
Reed Solomon codes are based on a specialized area of mathematics known as Galois fields (a.k.a. finite fields). These fields are of the form GF (p^m), where p is prime. RS makes use of Galois fields of the form GF (2^m), where elements of the field can be represented by m binary 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:

p(x) = x^8 + x^7 + x^2 + x^1 + 1
This is also known as the 0x87 polynomial, corresponding to the binary representation of the polynomial’s coefficients excluding the MSB (i.e. 10000111). This specific polynomial is used in the CCSDS specification for a RS (255, 223). In GF (2^8) there are 16 possible primitive polynomials.

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.

VOCAL Technologies, Ltd.
520 Lee Entrance, Suite 202
Amherst New York 14228
Phone: +1-716-688-4675
Fax: +1-716-639-0713
Email: sales@vocal.com