Parallelized programmable encoder/syndrome generator

Details Parallelized programmable encoder/syndrome generator Parallelized programmable encoder/syndrome generator

1999-08-31

2002-06-11

Chung, Phung M. (Department: 2784)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S784000

Reexamination Certificate

active

06405339

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to algebraic codes as exemplified by codes of the Reed-Solomon (n,k) type, and more particularly to enhancing the performance of composite encoders/syndrome generators computing check symbols over data symbol strings to form codewords in a write path and error syndromes from codewords in a readback path.
DESCRIPTION OF RELATED ART
The discussion of the prior art starts with a comment on separate error path processing. This is followed by a brief resume of the properties of error correction codes (ECC), including Reed-Solomon codes as examples. The themes are brought to a focus in discussion of Cox et al., U.S. Pat. No. 5,444,719, “Adjustable Error-Correction Composite Reed-Solomon Encoder/Syndrome Generator”, issued Aug. 22, 1995.
Error Processing in Separate Paths
Traditionally, the write and read paths of a multitracked disk storage drive have been failure-independent. In the write path, a symbol stream would be error encoded, then modulation encoded, and finally written out to the disk storage medium as a signal stream.
Upon playback, the signal stream would be processed in reverse order in a separate read path. In the read path, the signals would be demodulated into a stream of digital symbols and then error decoded. Significantly, the structure for processing the digital symbols to ascertain error was separate from the encoding structure in the write path. In addition, in the art before the Cox patent, the encoders and syndrome generators provided a constant number of correction symbols per codeword.
Error Correction Codeword Generation and the Write Path
Reed-Solomon codes (RS codes) are block-based error correcting codes with a wide range of applications in digital communications and storage. RS codes are a subset of BCH codes, and are linear block codes. An RS code is specified as RS(n,k) of n symbols/codeword, where n includes k data symbols and 2t concatenated redundancy symbols of s bits each. The RS code can correct up to t symbols in error in any given codeword (in this specification, the terms “symbol” and “byte” are used synonymously).
An RS encoder generally takes an original block of digital data, usually called the message word, and adds extra “redundant” bits, usually called a checksum word, to form a codeword to be transmitted or stored. The checksum word, in essence, mathematically describes the bit patterns of the message word. Errors may occur during transmission or storage. An RS decoder then processes each block of received data and attempts to correct any errors and recover the original message word.
For example, suppose an RS(255,223) code with eight bits/symbol were specified. Each codeword would contain 255 codeword bytes, of which 223 bytes would be original data (message word) and 32 bytes would be redundant or parity bytes (checksum word). For a symbol size of s bits/symbol, the maximum codeword length (number of bytes) n for an RS(n,k) code is n=2
S
−1. If the number of bits per symbol s=8 bits/byte, then the maximum codeword length n=2
S
−1=2
8
−1=256−1=255 bytes. Thus, for this code n=255, k=32, s=8, and 2t=n−k=255−223=32, t=16 bytes of correction. That is, the code can correct up to 16 bytes in error anywhere in the codeword by using the included redundant information.
A linear code, such as an RS code, must conform to the rules of finite (or Galois) field arithmetic. This includes the closure property. That is, selected binary arithmetic operations such as addition, subtraction, multiplication, and division on field elements always produce a resultant member of or in the same field.
Error correction is the mathematical reconstitution of correct codewords. When discussing coding theory, it is common practice to treat message words, checksum words, and codewords as a number of symbols representing coefficients of a polynomial in a variable, such as “x”. A codeword is generated using a special polynomial, the generator polynomial of the code. All valid codewords are exactly divisible by the generator polynomial, that is, there is a division remainder of zero. The general form of the generator polynomial is:
 
g
(
x
)=(
x−&agr;
i
)(
x−&agr;
i+1
)(
x−&agr;
i+2
) . . . (
x−&agr;
i+2t
)
where “&agr;” is a primitive element in the field.
The codeword may be constructed using:
c
(
x
)=
x
n−k
m
(
x
)+
x
n−k
m
(
x
) modulo
g
(
x
)
where the first term is represents the message word, and the second term represents the remainder of the message word when divided by the generator polynomial. Codewords are then sent to the disk drive via the write path for storage.
Error Detection/Syndrome Processing and the Read Path
A received codeword r(x)=c(x)+e(x), where c(x) is the codeword that was originally recorded or transmitted and e(x) is the error. Relatedly, the “syndromes” of the received codeword are defined informally as:
S
i
=r
(
x
)|
x=&agr;
i
=c
(
x
)|
x=&agr;
i
+e
(
x
)|
x=&agr;
i
=e
(
x
)|
x=&agr;
i
where i=0 to 2t−1. Alternately, a non-zero beginning index may be used, for example, i=z+0 to z+2t−1 where z≠0. Thus, r(x)=c(x) if and only if g(x) divides into r(x) with a remainder of zero, i.e., S
i
=0 for all i. Otherwise, it can be shown that the syndromes are dependent only upon the errors e(x). That is, if e(x)=0, then the syndromes for the counterpart received codeword are zero. However, if e(x)≠0, S
i
≠0 for at least one value of i.
In the typical textbook Reed-Solomon code implementation, the encoder uses fixed value finite field multipliers with the values set equal to the coefficients of the generator polynomial, while the syndrome generator uses fixed value finite field multipliers with the values set equal to the roots of the generator polynomial. Both the encoding and syndrome generation can be implemented in relatively simple logic. The remainder of the decoding process (beyond syndrome generation) is not pertinent to this invention.
The Cox Patent
The aforementioned Cox ′719 patent discloses a composite encoder and syndrome generator using a recursive logical filter structure having multiple multiplier stages and a switching arrangement. The composite generator uses a preselected set of tap weights for approximating either a generating polynomial for encoding, or parity check polynomial for syndrome computation. The switching arrangement may be used to vary the correction capability of the code by selectively including or excluding ones of said stages. The effect of the inclusion or exclusion of stages is to either increase or reduce the number of redundant 2t symbols. By using a single set of multiplier stages with constant values or weights formed from the roots (x−&agr;
i
)(x−&agr;
i+1
) . . . (x−&agr;
i+2t−1
) of the generating polynomial g instead of the coefficients g
i
, Cox found that the weights or values associated with a stage could remain the same for both encoding and syndrome generation. The embodiment also utilized the electronic enablement or disablement of feed-forward coupling among the stages.
Cox provides a single composite structure for use as an encoder when the feed-forward paths are enabled, and a syndrome generator when the paths are disabled. Also, the number of n−k=2t redundant or error correcting symbols per codeword can be changed electronically as, for example, different bands on disk tracks utilize a different number of correction symbols per stored codeword. While the advantages of the Cox invention are considerable, it still serially processes each symbol.
Interfaces and Variable Data Rates
In many digital systems, the processing bottleneck is the inability to move data quickly enough. An often-used solution to this problem is to make data paths wider.

Affiliated with

Also associated with

Rating

Parallelized programmable encoder/syndrome generator does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Parallelized programmable encoder/syndrome generator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallelized programmable encoder/syndrome generator will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2970227