Byte-parallel system for implementing reed-solomon error-correcting codes
First Claim
1. A parallel encoder for generating R redundant bytes responsive to receiving a message word having K variable message bytes for forming a code word having N=K+R bytes, wherein each of the bytes is an element of a finite field and includes w binary bits, and K and R are positive integers;
- said parallel encoder including;
R redundant byte generators, each receiving a message word in byte-parallel fashion and moving each of the variable message bytes through a multiplying stage, thereby to generate K intermediate product bytes, each of the intermediate product bytes representing one of said variable message bytes multiplied by a different one of K constant generator bytes, wherein each of the constant generator bytes is a predetermined constant element of the finite field; and
wherein each redundant byte generator further includes byte adder circuitry for receiving the intermediate product bytes in parallel and for pairing said intermediate product bytes for addition in a plurality of successive byte-additive stages including a final byte-additive stage that generates its associated one of R redundant bytes.
1 Assignment
0 Petitions
Accused Products
Abstract
A high-speed byte-parallel pipelined error-correcting system for Reed-Solomon codes includes a parallelized and pipelined encoder and decoder and a feedback failure location system. Encoding is accomplished in a parallel fashion by multiplying message words by a generator matrix. Decoding is accomplished with or without byte failure location information by multiplying the received word by an error detection matrix, solving the key equation and generating the most-likely error word and code word in a parallel and pipelined fashion. Parallelizing and pipelining allows inputs to be received at very high (fiber optic) rates and outputs to be delivered at correspondingly high rates with minimum delay. The error-correcting system can be used with any type of parallel data storage or transmission media to create an arbitrary level of fault-tolerance and allows previously considered unreliable media to be effectively used in highly reliable memory or communications systems.
310 Citations
38 Claims
-
1. A parallel encoder for generating R redundant bytes responsive to receiving a message word having K variable message bytes for forming a code word having N=K+R bytes, wherein each of the bytes is an element of a finite field and includes w binary bits, and K and R are positive integers;
- said parallel encoder including;
R redundant byte generators, each receiving a message word in byte-parallel fashion and moving each of the variable message bytes through a multiplying stage, thereby to generate K intermediate product bytes, each of the intermediate product bytes representing one of said variable message bytes multiplied by a different one of K constant generator bytes, wherein each of the constant generator bytes is a predetermined constant element of the finite field; and wherein each redundant byte generator further includes byte adder circuitry for receiving the intermediate product bytes in parallel and for pairing said intermediate product bytes for addition in a plurality of successive byte-additive stages including a final byte-additive stage that generates its associated one of R redundant bytes. - View Dependent Claims (2, 3, 4, 5, 6, 7)
- said parallel encoder including;
-
8. In a system for parallel encoding of message words into code words provided to data channels, and for parallel decoding of an output of the data channels comprised of received words, each received word having a plurality of variable received word bytes and each variable received word byte including w binary bits where w is an integer greater than one, circuitry for generating a syndrome word in response to inputting a received word of K variable message bytes and R variable redundant bytes, where K and R are positive integers;
- said circuitry including;
R syndrome byte generators, each syndrome byte generator having as a parallel input a received word, and moving the received word through a multiplying stage to generate N intermediate product bytes where N=K+R, each intermediate product byte representing a multiplication of one of N variable received bytes of the received word by an associated one of N predetermined constant error detection bytes; and wherein each syndrome byte generator further includes byte adder circuitry for receiving the intermediate product bytes in parallel and for pairing of the intermediate product bytes for addition in successive byte-additive stages including a final byte-additive stage for generating its associated one of R syndrome bytes. - View Dependent Claims (9, 10, 11, 12)
- said circuitry including;
-
13. In a system for parallel encoding and decoding of data in which the data take the form of message words having K message bytes and code words having N=K+R bytes where R is the number of redundant bytes, wherein the code words are provided to a plurality of data channels in parallel and a parallel output of the data channels takes the form of received words, a decoding system including:
-
a syndrome generator for generating a syndrome polynomial responsive to receiving a received word as an input; a key equation solver circuit for generating an error locator polynomial L(x) and an error evaluator polynomial V(x) representative of solutions to the key equation;
space="preserve" listing-type="equation">S(x)L(x)=V(x) modulo x.sup.R+1where R is the number of redundant bytes and S(x) is said syndrome polynomial; and a most-likely error word generating circuit for generating a most-likely error word based on receiving said error locator polynomial and said error evaluator polynomial. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
-
21. An error correcting system including:
-
a parallel encoder for receiving message words, each message word including K message bytes where each of the message bytes includes w binary bits, said parallel encoder generating as its output a code word having N bytes including the message bytes plus R redundant bytes; N parallel data channels for receiving the code word in byte parallel fashion and providing a parallel data channel output based on the code word; a parallel decoder for receiving the parallel data channel output as a received word and, based on the received word, generating a most-likely error word and a most-likely code word each having N bytes; and a failure location system, coupled to receive failure location information from said data channels and further coupled to provide byte failure location information to the parallel decoder, said failure location system including a microprocessing means for sequentially reading every location in the data handling channels and accumulating failure information associated with each of said locations;
said processor system being adapted to identify at least one of said locations as a failed location based on a sensed frequency of errors at least equal to a predetermined threshold frequency;said failure location system further including a memory means for storing a record of failed locations, said memory providing the byte failure location information to the parallel decoder. - View Dependent Claims (22, 23)
-
-
24. A variable byte multiplier circuit for multiplying two variable data bytes wherein each of the variable data bytes is composed of w data bits and w is an integer greater than one;
- said variable-byte multiplier circuit including;
w constant byte multipliers in parallel, each one of the constant byte multipliers receiving a first variable byte in parallel and generating a first intermediate byte representing the product of the first variable byte and a constant byte corresponding to said one constant byte multiplier, wherein each of the constant bytes is a predetermined constant element of a finite field; w logic sets in parallel for receiving a second variable byte, each of said logic sets receiving a different one of w bits of the second variable byte and further receiving a different one of said first intermediate bytes; wherein each one of said logic sets includes w AND logic gates in parallel, each of the AND logic gates receiving as bit inputs (i) the bit of said second variable byte corresponding to said one logic set, and (ii) a different one of w bits of the first intermediate byte that corresponds to said one logic set;
each of said logic gates performing an AND logic function on its inputs to generate an intermediate bit, with the logic gates of the logic set together generating a second intermediate byte composed of the intermediate bits; andbyte adder circuitry for receiving the second intermediate bytes from said logic sets in parallel and for pairing said second intermediate bytes in a plurality of successive byte-additive stages including a final byte-additive stage that generates a resultant byte representing a product of the first and second variable bytes. - View Dependent Claims (25, 26, 27)
- said variable-byte multiplier circuit including;
-
28. In a system for parallel decoding of an output of parallel data channels in the form of received words having N=K+R bytes where K is the number of data bytes and R is the number of redundant bytes, a key equation solving circuit for receiving a syndrome product of a constant polynomial x and a syndrome polynomial S(x) of R bytes based on the received words from the parallel data channels, and generating an error locator polynomial L(x) and an error evaluator polynomial V(x) representing a solution to the key equation:
-
space="preserve" listing-type="equation">S(x)L(x)=V(x) modulo x.sup.R+1said key equation solving circuit including; R successive stages, each stage receiving a byte-parallel input and generating a byte-parallel output representing a single iteration of an iterative algorithm for solving the key equation, wherein a first one of said stages receives said syndrome product, and wherein the stage output of a final one of said stages includes said error locator polynomial L(x) and an evaluator product of said error evaluator polynomial V(x) and said polynomial x. - View Dependent Claims (29, 30, 31, 32)
-
-
33. In a system for parallel decoding of data channel output of received words having N=K+R bytes where K is the number of data bytes and R is the number of redundant bytes, including a key equation solving circuit for receiving the product of a constant polynomial x and a syndrome polynomial S(x) of R bytes and generating an error locator polynomial L(x) and error evaluator polynomial V(x) representing a solution to the key equation:
-
space="preserve" listing-type="equation">S(x)L(x)=V(x) modulo x.sup.R+1 ;a most-likely error word generator, including; N most-likely error byte generating circuits, each one of the error byte generating circuits receiving the error locator polynomial an d the error evaluator polynomial in parallel and, based on the error locator polynomial, the error evaluator polynomial and a first derivative of the error locator polynomial, generating a most-likely error byte, the most-likely error bytes of the respective most-likely err or byte generating circuits together providing the most-likely error word. - View Dependent Claims (34, 35, 36, 37, 38)
-
Specification