Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Berlekamp-Massey Decoder Implementation

IP.com Disclosure Number: IPCOM000116831D
Original Publication Date: 1995-Nov-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 149K

Publishing Venue

IBM

Related People

Hassell, CA: AUTHOR [+2]

Abstract

A programmable decoder for (N,K) Reed-Solomon error/erasure detection and correction codes using the Berlekamp-Massey algorithm is disclosed. A (32,24) code is used in this implementation which features improved decoding delay, due to an optimized error locator/magnitude calculation algorithm, as well as several status reporting mechanisms which provide improved recording channel performance.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 44% of the total text.

Berlekamp-Massey Decoder Implementation

      A programmable decoder for (N,K) Reed-Solomon error/erasure
detection and correction codes using the Berlekamp-Massey algorithm
is disclosed.  A (32,24) code is used in this implementation which
features improved decoding delay, due to an optimized error
locator/magnitude calculation algorithm, as well as several status
reporting mechanisms which provide improved recording channel
performance.

      High-performance data recording channels require data error
correction circuitry, usually performed by a (N,K) Reed-Solomon
decoder
that can handle both error and erasure corrections.  Minimization of
decoder calculation delay is critical in recording channels due to
the
adverse effect on data rate and the importance of feeding back
outer-code
pointers to the erasure pointer generation logic.

      Information intrinsic to the decoder logic can be used by the
device control program to improve drive performance.  For example,
the frequency and distribution of errors and erasures in the data
read back from the recording medium can be used in the implementation
of write-skip and other adaptive ERP algorithms.  Another example is
the contents of the data block header.  During a read-while-write
operation, the availability of selected fields in the block header to
the control program is useful in verifying the integrity of newly
written data.

The decoding algorithm is split into three key operation cycles.
They are:
  o  Syndrome and Erasure Calculations
  o  Error/Erasure Locator and Evaluator Calculations
  o  Error and Erasure Correction

      The first and last cycle takes N clocks.  The design of the
second cycle can be tailored to meet the desired decoding delay and
the data rate.

      The Berlekamp-Massey algorithm evaluates three GF(256)
polynomials.  They are the Error/Erasure Locator, Auxiliary
Error/Erasure Locator, and Error/Erasure Evaluator polynomials.  The
same set of Galois Field multipliers are shared to calculate
Error/Erasure Locator and Error/Erasure Evaluator polynomials.  With
(N-K) GF multipliers and one GF inverter, the Error/Erasure Locator
and Auxiliary Error/Erasure Locator update requires three clocks per
error.  Once the Error/Erasure Locator is defined, each Error/Erasure
Evaluator Coefficient takes one clock.  Therefore, a (N-K) erasure
correction decoder requires (N-K) times 4   clock cycles which, for
an optimum design, should equal N.  In general, the delay to the
first codeword correction is equal to N + c times (N-K).  The
constant c depends on the algorithm and technology constraints.

      The hardware for (32,24) Reed-Solomon decoder is based on the
Galois Field of size 256, denoted as GF(256), where each symbol is 8
bits wide.  The generator polynomial for the field is X sup 8 + X sup
4 + X sup 3 + X sup 2 + 1.

      The decoder hardware provides for a continuous data rate of 20
MBytes/s using a 20 MHz clock a...