Byte-Parallel System for Implementing Reed-Solomon Error-Correcting Codes

1. Field of the Invention

The present invention relates generally to error-correcting systems for bit-encoded data, and more particularly to Reed-Solomon error-correcting systems that operate in a parallel and pipelined fashion.

2. Description of the Prior Art

Since the development of information theory and coding theory in 1948, numerous types of error-correcting systems have been designed and developed.

The first error-correcting system corrected a single bit in error in a group of bits. Shortly thereafter, error-correcting systems were developed to correct a single burst of bit errors in a block of bits. Error-correcting systems operate on data either as a set of bits or as a set of bytes, where the number of bits per byte is normally 8, but can be any number greater than 1. Error-correcting systems that operate on bits are called binary error-correcting systems and those that operate on bytes are called nonbinary error-correcting systems. Early error-correcting systems are examples of binary systems.

Nonbinary error-correcting systems were implemented after the discovery in 1968 of an iterative algorithm to solve the key decoding equation known as the Berlekamp-Massey algorithm in honor of its inventors. Since 1968, several other iterative algorithms have been discovered to solve the key decoding equation. In addition, algorithms which operate on matrices have been developed to solve the key decoding equation. Some decoding methods do not use the key decoding equation.

Reed-Solomon error-correcting systems are nonbinary. In the past decade, their use has become widespread. They are regularly used in magnetic disk drives, optical disk drives, magnetic tape drives and in communications systems.

Nearly all prior Reed-Solomon error-correcting systems are implemented such that most of the encoding and decoding functions are done in a byte-by-byte serial fashion. Some Reed-Solomon implementations solve the key decoding equation in a parallel fashion, but nearly all Reed-Solomon implementations encode serially, generate the syndrome word serially and determine the most-likely error pattern serially, thereby limiting performance.

Some prior Reed-Solomon error-correcting systems correct errors only, some correct erasures only and some correct both errors and erasures. (An error is a byte in error about which no information is known. An erasure is a byte that is likely to be in error and the location is known by the decoder before decoding begins. In the present invention, an erasure is referred to as a byte failure location.) In prior Reed-Solomon error-correcting systems that use byte failure location information, this information is transmitted directly from the transmission or storage channel(s) to the decoder. These systems require an entire block of data to be received before decoding can begin, so, storage must be provided for at least one block of data. For example, in disk array systems where the error-correction system within each disk drive is used to indicate a failed drive, an entire sector of data must be read from each disk in the array before byte failure location information can be determined.

Prior encoders which encode Reed-Solomon codes operate on message word bytes serially, which limits the speed of encoding. Prior Reed-Solomon error-correcting systems do not implement all the decoding functions in a parallel fashion. For example, prior syndrome word generators operate serially on bytes of the received word, which limits the speed of syndrome word generation. Prior decoding circuits that generate the most-likely error word operate serially, which limits the speed of decoding.

Prior Reed-Solomon error-correcting systems have not been designed to operate in a combination parallel and pipelined fashion. This limits the performance throughput. Due to this limit on performance, semiconductor memories have not been able to take advantage of the capabilities of Reed-Solomon error-correcting systems.

In prior decoders that use byte failure location information, the channel failure indicators are communicated directly from the channels to the decoder. This is an unreliable method when determining if a channel has failed since the channel is, in effect, diagnosing itself. If an indicated byte failure location is not actually in error, the decoder has lost some of its capability to correct other random errors. Prior Reed-Solomon decoders which receive byte failure location information directly from the channels also require an entire block of data to be read before correction can begin.

Most prior storage systems that use a Reed-Solomon error-correction system to create fault-tolerance have a low-level of fault-tolerance. They can only correct for one channel failure, so a problem arises when multiple channels fail simultaneously.

Prior Reed-Solomon decoders are not easily scalable. They have been configured to work for one level of error correction and do not provide a pattern for a design which would provide a higher or lower level of error correction.

The first object of the error-correcting system is to implement highly-parallel versions of Reed-Solomon encoding and decoding algorithms so that encoding and decoding can be done in a parallel fashion, thereby overcoming the performance limitations in conventional implementations due to functions which operate on bytes serially. The encoding and decoding functions of the Reed-Solomon error-correcting system are implemented in a highly-parallel fashion through the use of parallel processing circuitry.

The second object of the error-correcting system is to provide the means to encode and decode words as fast as they can be sent. This is done by implementing Reed-Solomon encoders and decoders in a "pipelined" fashion where each segment of an encoder or decoder "pipe" is a stage of digital electronics. Each stage of a pipe encompasses one or more levels of digital logic gates. Pipelining allows parallel Reed-Solomon encoders and decoders to receive inputs at very high (fiber optic) rates and deliver outputs at correspondingly high rates. Since the error-correcting system consists of levels of digital electronics, registers can be selectively added between levels which results in higher performance in terms of the amount of information that can be encoded and decoded in a fixed unit of time even though the time through the pipe may be increased.

The third object of the error-correcting system is to combine highly-parallel versions of Reed-Solomon encoding and decoding circuitry with the encoders and decoders configured in a "pipelined" fashion to further enhance performance.

The fourth object of the error-correcting system is to provide an improved method and apparatus for generating byte failure location information and presenting it to the decoder, thereby overcoming the problems associated with prior systems which use failure indicators directly from channels to indicate failure locations.

The fifth object of the error-correcting system is to enable the design of parallel communications or storage systems with a high degree of fault-tolerance by resolving situations where multiple channel failures are indicated simultaneously. This is done by inserting an intelligent entity which uses past error-correction history between the channel failure indicators and byte failure location information received by the decoder.

The sixth object of the error-correcting system is to provide a generic pattern for the design of parallelized and pipelined Reed-Solomon encoders and decoders so that, given one level of error correction capability, the design of other implementations to correct more or fewer errors is readily apparent.

The seventh object of the error-correcting system is to enable parallelized and pipelined encoders and decoders to be implemented in a single chip. The method and apparatus of the error-correcting system is designed to reduce the number of pins required to an acceptable level.

The foregoing and other objects are preferably accomplished in the following manner for Reed-Solomon codes:

On encoding, a message word, m, is multiplied by a Reed-Solomon generator matrix, G, to generate a code word, c. Matrix G can take one of two forms; one form generates systematic code words and the other non-systematic code words. (Systematic code words contain the message word bytes unaltered, while non-systematic code words encrypt the message word.) The preferred implementation is systematic. Encoding is a one-step operation accomplished by a set of parallel processing circuits.

On decoding, the syndrome word, S, is generated in a parallel fashion by multiplying the received word, r, by an error detection matrix, D, or by multiplying by an alternative error detection matrix, D.sub.A, followed by multiplication by a roots matrix, D.sub.R, where S=rD.sub.A D.sub.R. (D is the transpose of the conventional parity check matrix, H.) The preferred implementation uses D.

The key equation is solved in a parallel fashion by implementing a variation of Willard Eastman's modification to the Berlekamp-Massey algorithm as described in Proceedings of the 1988 Tactical Communications Conference, Vol. 1 (1988), Eastman, "Euclideanization of the Berlekamp-Massey Algorithm", pp. 295-303. This algorithm, Eastman's Program 6, is implemented in a parallel fashion with or without byte failure location information. The output of the key equation solver is an error locator polynomial, L(x), and an error evaluator polynomial, V(x), multiplied by the constant polynomial x, i.e. xV(x).

The error locator polynomial, L(x), is evaluated at each possible location simultaneously to determine the error locations.

The error evaluator polynomial, V(x), is evaluated at each possible location simultaneously and divided by the corresponding evaluation of the formal derivative of the error locator polynomial, L'(x), so as to determine the most-likely error pattern. See Encyclopedia of Mathematics and its Applications, Vol. 3, The Theory of Information and Coding (1977), McEliece, pp. 181-183.

Byte failure location information is provided to the decoder based upon a feedback failure location system comprising a microprocessor, a content-addressable memory (CAM) and a random-access memory (RAM). The communications system or storage system to which the error-correcting system is being applied is exercised periodically so as to determine the locations of failures based on frequency of correction. If data from certain locations is corrected at a frequency exceeding a preset threshold level, these locations will be indicated as failed locations or channels. Byte failure location information can also be determined by prior testing of the media.

The error-correcting system provides a general-purpose way of creating highly fault-tolerant communications and storage systems. It is easily configurable to allow for many levels of error correction and fault-tolerance.

The error-correcting system can be applied to all types of transmission and storage media including magnetic and optical disk, magnetic tape, semiconductor memory, fiber optic cables, and cabling of all types. The error-correcting system can be used with real-time digital video data and will correct for errors with no slowdown of the video.

A high level of fault-tolerance can be achieved. Failed components can be removed and replaced without shutting down or slowing down the system. Increasing the level of fault tolerance leads to more reliable systems that are capable of sustained periods of operation with little or no down time. This is significant because the storage industry is moving toward systems with arrays of smaller capacity devices, rather than increasing the capacity of a single device. Without increased fault-tolerance, storage systems which contain arrays with a large number of component devices would be too unreliable to be practical.

The error-correcting system allows the use of highly-flawed, unreliable or high error rate media. Previously unusable media can be used to produce highly-reliable communications and storage systems.

The error-correcting system significantly reduces the need to test manufactured media in the factory. Fabricated media can be installed in a communications or storage system that contains the error-correcting system, and a media defect map will automatically be generated by the feedback failure location system. The failed components can be removed and replaced.

Transmission speeds and storage capacities can be increased by allowing raw error rates to increase and using the error-correcting system to reduce the error rate to an acceptable level. The error-correcting system can be used with raw error rates as high as one byte in error for every thousand bytes transferred. Current systems require raw error rates as low as one byte in error for every billion bytes transferred. Due to the unprecedented speed of the error-correction system, it can be used with high-speed transmission and storage media such as fiber optic cable and semiconductor memory chips.

The error-correcting system requires a minimum amount of redundant information. Reed-Solomon codes are optimal from the standpoint of having the most error correction power for a given amount of redundancy. From that standpoint, the error-correcting system is optimal.

When used to replace the industry standard Single Error Correcting Double Error Detecting binary error-correcting system (SECDED) in semiconductor memories, the error-correcting system can either reduce the redundancy required and keep error-correcting capabilities the same, or increase error-correcting capabilities and keep redundancy requirements the same. Also, the next generation of memory chips being produced store 4-bit quantities rather than the current single-bit quantities. The error-correcting system can correct 4-bit or wider quantities.

Other objects and advantages of the error-correcting system will become apparent from a consideration of the drawings and the following detailed description.

FIG. 1 shows the high-level logical structure of an error-correcting system constructed according to the present invention.

FIG. 2 is a block diagram of the parallel encoder.

FIG. 2-A through FIG. 2-G illustrate features of the encoder.

FIG. 3 is a block diagram of the parallel decoder.

FIG. 3-A is a block diagram of a polynomial multiplier which multiplies a variable polynomial by the constant x.

FIG. 3-B is a block diagram of a polynomial multiplier which multiplies a variable polynomial by the constant x.sup.-1.

FIG. 4 is a block diagram of the syndrome generator.

FIG. 4-A is a block diagram of a syndrome byte generator.

FIG. 5 illustrates a key equation solver composed of R stages of digital logic.

FIG. 5-A is a flowchart of the logic executed by the key equation solver stages.

FIG. 5-B through FIG. 5-J illustrate elements of the key equation solver.

FIG. 6 is a block diagram of the most-likely error word generator.

FIG. 6-A through FIG. 6-E illustrate elements of the most-likely error word generator.

FIG. 7 is a block diagram of the most-likely code word generator.

FIG. 7-A is a decomposition of the polynomial adder.

FIG. 8 is a block diagram of the output selector.

FIG. 9 is a block diagram of the feedback failure location system.

FIG. 9-A shows the content of the feedback failure location system's random access memory (RAM).

FIG. 9-B is a block diagram of the content-addressable memory (CAM).

FIG. 10 shows an apparatus for reducing the number of pins required on a VLSI chip containing the error-correcting system.

FIG. 11 illustrates the overall operation of the error-correcting system for the example case where the incoming message is "claim", channel "b" makes an error and channel "g" has previously failed.

FIG. 12 shows letter, binary and polynomial equivalents for each element in a finite field with 16 elements.

FIG. 12-A shows an addition table for a finite field with 16 elements.

FIG. 12-B shows multiplication and reciprocal tables for a finite field with 16 elements.

FIG. 12-C shows how the letters of a code word for the example case are labeled with (or identified by) the nonzero elements from a finite field with 16 elements.

FIG. 13 shows the data flow and operation of the parallel encoder for the example case where the message word "claim" is encoded into the code word "gdaclaim".

FIG. 13-A through FIG. 13-G show data flow and operation of elements of the parallel encoder for the example case.

FIG. 14 shows the content of the feedback failure location system's RAM for the example case where channel "g" has failed.

FIG. 15 shows the data flow and operation of the parallel decoder for the example case.

FIG. 16 shows the data flow and operation of the syndrome generator for the example case.

FIG. 16-A shows the data flow and operation of the first syndrome byte generator for the example case.

FIG. 16-B shows the data flow and operation of the byte adder circuitry for the first syndrome byte generator for the example case.

FIG. 17 shows the data flow and operation of the key equation solver for the example case.

FIG. 17-A through FIG. 17-C show data flow and operation of the three stages of the key equation solver for the example case.

FIG. 18 shows stage 1 of the key equation solver for the example case after simplification.

FIG. 18-A shows the generation of p.sup.T (x).sub.1 for stage 1 of the key equation solver for the example case.

FIG. 18-B shows the data flow and operation of the first byte multiplier that multiplies two variable bytes ("h" by "1" for the generation of p.sup.T (x).sub.1 for stage 1 of the key equation solver for the example case.

FIG. 19 shows stage 3 of the key equation solver for the example case after simplification.

FIG. 19-A through FIG. 19-F show data flow and operation of various elements of stage 3 of the key equation solver for the example case.

FIG. 20 shows the data flow and operation of the most-likely error word generator for the example case.

FIG. 20-A through FIG. 20-E show data flow and operation of various elements of the most-likely error word generator for the example case.

FIG. 21 shows the data flow and operation of the most-likely code word generator for the example case.

The logical structure of the preferred embodiment of the error-correcting system is described first. Next, the operation of the error-correcting system is described by choosing a particular configuration and running through an example showing how the encoding and decoding is done and how errors are corrected. The logical structure and operation are described by a series of block diagrams. The highest level block diagram shows the major functions, each function being represented as a single block. Subsequent block diagrams decompose each function into subfunctions. This is continued until the blocks/functions are well-known logical operations such as the AND, OR, NOT, and Exclusive OR (XOR) operations from Boolean Algebra used in designing digital logic circuits. All logical functions of the error-correcting system are parallelized and pipelined to maximize speed of operation, although not every function is noted as "parallelized and pipelined" in order to simplify the description.

Three line widths are used in the drawings. The narrowest lines represent single-bit data paths, the medium width lines represent byte-wide paths, and the widest lines represent polynomial-wide data paths. The actual number of physical wires for the byte-width paths and polynomial width paths depend on the number of bits per byte chosen and the maximum degree of the polynomial that is transferred over the polynomial path. For example, bytes are often 8 bits wide and a polynomial with a maximum degree of 5 would require a data path that is 6 bytes wide.

Registers can be added between stages of a pipeline of digital logic to increase performance by increasing the maximum possible clocking frequency of the system. To simplify the description, interstage registers are not shown. While the number and positioning of registers varies among systems, placement of registers is well known to those of skill in the art.

In the design of any logical circuit, it is necessary to add drivers to drive heavy loads. This is referred to as "fan-out". Fan-out is not shown but may need to be added in certain places in an actual implementation, as those of skill in the art are aware.

Systematic error-correcting systems are preferred to non-systematic ones, so figures and descriptions will be based on systematic error-correcting systems with additional comments on non-systematic implementations. In systematic error-correcting systems, the message word is retained in the code word unaltered. Non-systematic error-correcting systems encrypt the message word.

The high-level logical structure of the preferred embodiment of the error-correcting system is shown in FIG. 1. It comprises a parallel encoder 100, N parallel communications or storage channels 200, a parallel decoder 300, and a feedback failure location system 400. Each function operates on w-bit quantities, also referred to a s bytes, letters or finite field elements. Each of N channels 200 transmits a failure indicator to failure location system 400. There may also be other sources of failure location information as shown in FIG. 1. Failure location system 400 supplies byte failure location information to decoder 300 and controls the output of decoder 300 through decoder output select control lines. Conventionally, other system-level components would be connected to decoder 300 through a parallel data bus to interface with the error-correcting system.

The logical components of encoder 100 are shown in FIG. 2. K message word bytes, m.sub.i, are applied as input and N code word bytes, c.sub.i, are output. Encoder 100 contains R redundant byte generators 102. The R bytes are the redundant bytes added on to each set of message word bytes. The redundant bytes are shown in FIG. 2 as being added as a prefix, but they can be interspersed with the message word bytes or added as a suffix. The logical components of encoder 100 shown in FIG. 2 are for a systematic error-correcting system. For a non-systematic error-correcting systems, there are N rather than R generators 102 and the message word is encrypted. The mathematical basis for parallelized encoding is explained in Appendix A.

FIG. 2-A shows the components of one of generators 102. Each generator 102 contains K byte multipliers 104 that multiply a variable byte by a constant byte where each byte is an element in a finite field. The variable input is labeled "V" and the constant input is labeled "C". Each byte multiplier 104 receives one byte of the message as its "V" input and a constant byte denoted as g.sub.x,i as its "C" input. The constant bytes, g.sub.x,i, are elements from the code's generator matrix, G. G is a matrix of constants. The constants are fixed, based on the values of K and R. While shown as inputs, the constant bytes preferably are built into their respective byte multipliers as circuitry that appropriately processes the respective message bytes. The outputs of the byte multipliers 104 are added by byte adder circuitry 106.

FIG. 2-B shows one of byte multipliers 104. Each of w input bits of the message byte is input to one of w product bit generators 108. One of product bit generators 108 is shown in FIG. 2-C. It consists of w bit multipliers 110 that multiply a variable bit by a constant bit and bit adder circuitry 112. Bit multipliers 110 are fabricated to provide a constant bit input b.sub.x,i of either 1 or 0. If b.sub.x,i =1, bit multiplier 110 represents a connection between the "V" input and the output. If b.sub.x,i =0, there is no connection between the "V" input and the output. Circuit connections within product bit generator 108 are determined by the constant multiplier or "input". The mathematical basis for byte multiplier 104 is described in Appendix B.

As seen in FIG. 2-D, byte adder tree 106 comprises multiple byte adders 114. Each byte adder 114 adds two of the variable bytes (or finite field elements) output by byte multipliers 104 shown in FIG. 2-A. FIG. 2-E shows bit adder circuitry 112 in greater detail. FIG. 2-F is a decomposition of one of byte adders 114. FIG. 2-G shows one of bit adders 116 from the circuitry in FIG. 2-E.

Decoder 300 is shown in FIG. 3. Decoder 300 includes a syndrome generator 302, a key equation solver 304, a most-likely error word generator 306, a most-likely code word generator 308, a delay function 310 and an output selector 312 interconnected as shown in FIG. 3. Received word/polynomial r(x) is input from data channels 200 to syndrome generator 302. A syndrome word/polynomial S(x) is output of the syndrome generator. Syndrome word/polynomial S(x) is multiplied by constant "x" using polynomial multiplier 303 as shown in FIG. 3-A where a(x) is S(x). Key equation solver 304 inputs syndrome word/polynomial S(x) multiplied by "x" and byte failure location information and outputs error locator word/polynomial L(x) and error evaluator word/polynomial xV(x). Error evaluator word/polynomial xV(x) is multiplied by constant "x.sup.-1 " using polynomial multiplier 305 as shown in FIG. 3-B where a(x) is xV(x). L(x) and V(x) are input to most-likely error word generator 306 which generates the most-likely error word/polynomial, e(x). Most-likely code word generator 308 determines the most-likely code word/polynomial, c(x), given the most-likely error word/polynomial and a delayed version of the received word/polynomial, .DELTA.r(x). Output selector 312 is controlled by feedback failure location system 400 shown in FIG. 1. The selector is set to select either the most-likely error word, the most-likely code word or a delayed version of the received word to be output by decoder 300.

Polynomial multipliers 303 and 305 are implemented via "wiring". No actual logic gates are needed to perform these functions.

FIG. 4 shows the components of syndrome generator 302. It consists of R syndrome byte generators 314. Each byte generator 314 comprises N byte multipliers 104 and byte adder circuitry 106 as shown in FIG. 4-A. Byte multipliers 104 and byte adder circuitry 106 have previously been described in connection with encoder 100. Each byte multiplier 104 receives one byte of the received word as its "V" input and a constant byte denoted as d.sub.x,i as its "C" input. The d.sub.x,i are elements from the code's error detection matrix of constants, D. The mathematical basis for parallelized syndrome generation is described in Appendix C.

Key equation solver 304 is composed of a number of stages of digital logic. Each stage is one segment of a "pipe" as shown in FIG. 5. There are R stages, where R is the number of redundant bytes in a code word. Each stage performs the functions required by a single iteration of an iterative algorithm designed to solve the key equation S(x)L(x)=V(x) modulo x.sup.R+1. Several iterative algorithms exist to solve this equation for L(x) and V(x), given S(x) and R. A variation of the Berlekamp-Massey algorithm as modified by Willard Eastman and described in Proceedings of the 1988 Tactical Communications Conference, Vol. 1 (1988), Eastman, "Euclideanization of the Berlekamp-Massey Algorithm", pp. 295-303 (incorporated herein by reference), is employed to solve the key equation and is the basis for the logic circuitry in key equation solver 304. See FIG. 5-A for the variation. The notation in FIG. 5-A is the same as used in the Eastman reference except that subscripts have been added and an auxiliary variable, .lambda..sub.j, is used. The algorithm can correct for both errors and erasures (failure locations). The mathematical basis for key equation solver 304 is given in the Eastman reference. At the end of R stages of logic, error locator polynomial L(x) and error evaluator polynomial V(x) are output to most-likely error word generator 306. In Eastman's notation, II(x) is the error locator polynomial, .OMEGA.(x) is the error evaluator polynomial, and .gamma. is a constant finite field element. The outputs of the key equation solver are .gamma.II(x) and x.gamma..OMEGA.(x). In the present invention, L(x)=.gamma.II(x) and V(x)=.gamma..OMEGA.(x), so the outputs are L(x) and xV(x). See Appendix D for the mathematical basis for polynomial multiplication modulo x.sup.R+1.

FIG. 5-B shows the high-level structure of each stage of key equation solver 304 consisting of control circuitry 315 and polynomial processing circuitry 316. FIG. 5-C shows detailed logic in each stage of key equation solver 304, showing that control circuitry 315 includes an integer adder 318, a test circuit 320 for determining if d.sub.j =0 or .lambda..sub.j .ltoreq.2l.sub.j-1, an integer subtracter 322 and an integer selector 332, and that polynomial processing circuitry 316 includes two polynomial multipliers 303 which multiply incoming polynomials b.sup.O (x).sub.j-1 and p.sup.O (x).sub.j-1 by a constant polynomial,"x" (see FIG. 3-A), a byte selector 324, two polynomial selectors 326, two polynomial multipliers 328 which multiply .delta..sub.j-1 +W.sub.j x by polynomials b.sup.T (x).sub.j-1 and p.sup.T (x).sub.j-1, respectively, two polynomial multipliers 330 which multiply d.sub.j by the polynomials xb.sup.0 (x).sub.j-1 and xp.sup.0 (x).sub.j-1, respectively, and two polynomial adders 334.

The data items involved in solving the key equation are .mu., W.sub.i (i=1, R),.lambda.,l,.delta.,d,b.sup.O (x),b.sup.T (x), p.sup.O (x) and p.sup.T (x). Here, Eastman's notation is used. The W.sub.i, .delta. and d data items are bytes, letters or finite field elements. Items .mu.,.lambda., and l are integers. Items b.sup.O (x),b.sup.T (x),p.sup.O (x) and p.sup.T (x) are polynomials whose coefficients are bytes.

Adder 318, subtracter 322 and selector 332 of control circuitry 315 are understood from FIG. 5-C. Test circuit 320 consists of a circuit to determine if d.sub.j =0 and a circuit to determine if .lambda..sub.j .ltoreq.2l.sub.j-1. The circuit to determine if d.sub.j =0 consists of a w-input OR logic gate with an inverted (NOT) output. The circuit to determine if .lambda..sub.j .ltoreq.2l.sub.j-1 consists of an integer subtracter which subtracts l.sub.j-1 shifted left one position (which is equivalent to multiplication by 2) from .lambda..sub.j and a circuit for determining if the result has a positive sign or is zero, indicating that .lambda..sub.j .ltoreq.2l.sub.j-1. The results of the two determinations are OR'd together to determine if either condition is true.

FIG. 3-A shows one of polynomial multipliers 303.

FIG. 5-D is a decomposition of byte selector 324.

FIG. 5-E is a decomposition of polynomial selector 326.

FIG. 5-F is a decomposition of one of polynomial multipliers 328. The quantity "a" is either b.sup.T (x).sub.j-1 or p.sup.T (x).sub.j-1 depending on which of multipliers 328 is under consideration. Polynomial multiplier 328 contains byte multipliers 336 that multiply two variable bytes and byte adders 114 (see FIG. 2-F) receiving outputs of the multipliers except for the initial and final multipliers with a.sub.0 and a.sub.n, inputs, respectively. The required number of byte multipliers 336 depends upon the value of R and the level of the pipeline stage. See Appendix E for the mathematical basis for polynomial multiplier that multiplies by .delta..sub.j-1 +W.sub.j x.

FIG. 5-G is a decomposition of one of polynomial multipliers 330 shown in FIG. 5-C. Each polynomial multiplier 330 consists of a plurality of byte multipliers 336. The quantity "b" is either xb.sup.0 (x).sub.j-1 or xp.sup.0 (x).sub.j-1, depending on which of polynomial multipliers 330 is under consideration. The required number of byte multipliers 336 depends upon the value of R and the level of the pipeline stage.

FIG. 5-H shows the preferred implementation of byte multipliers 336. See Appendix B for the mathematical basis for byte multiplier 336.

FIG. 5-I is a decomposition of w ANDs function 338 shown in FIG. 5-H.

FIG. 5-J is a decomposition of polynomial adder 334 shown in FIG. 5-C.

A logical decomposition of most-likely error word generator 306 from FIG. 3 is presented in FIG. 6. The most-likely error word generator consists of N parallel most-likely error byte generators 340. Each generator 340 receives error locator word/polynomial L(x) and error evaluator polynomial V(x) as inputs, and outputs a byte i of the most-likely error word, denoted as e.sub.i.

FIG. 6-A is a logical decomposition of error byte generator 340 shown in FIG. 6. Logic level 1 consists of L'(x) selector 343 which selects coefficients of L(x) in order to form L'(x). The mathematical basis for forming L'(x) is described in Appendix F. Level 2 contains L(x) evaluator 342, L'(x) evaluator 344 and V(x) evaluator 346. L(x) evaluator 342 evaluates L(x) at a.sup.-ij, L'(x) evaluator 344 evaluates L'(x) at a.sup.-ij and V(x) evaluator 346 evaluates V(x) at a.sup.-ij. Level 3 contains a byte test for zero 348 which determines if L(a.sup.-ij)=0 and byte reciprocal generator 350, which generates the reciprocal of L'(a.sup.-ij). Byte multiplier 336 in level 4 (see FIG. 5-H) multiplies (L'(a.sup.-ij)).sup.-1 by V(a.sup.-ij) to produce e.sub.i if L(a.sup.-ij)=0. Level 5 consists of w ANDS function 338 (see FIG. 5-I). The mathematical basis for determining the most-likely error word from L(x) and V(x) is presented in Encyclopedia of Mathematics and its Applications, Vol. 3, The Theory of Information and Coding (1977), McEliece, pp. 181-183.

FIG. 6-B shows the logical decomposition of L(x) evaluator 342. The form of this circuit is the same as encoder 100 and syndrome generator 302. Each component shown in FIG. 6-B has been previously described. The powers of a are constants.

FIG. 6-C shows how the coefficients of L'(x) are selected in selector 343 from the coefficients of L(x). FIG. 6-D and FIG. 6-E are logical decompositions of L'(x) evaluator 344 and V(x) evaluator 346.

For small values of w, e.g. w<8, the preferred implementation of byte reciprocal generator 350 shown in FIG. 6-A is a read only memory or "ROM". There are many other methods of generating reciprocals. For larger values of w, the preferred implementation of byte reciprocal generator 350 is a parallelized and pipelined version of Euclid's extended algorithm for finding the greatest common divisor of two polynomials.

FIG. 7 and FIG. 7-A show most-likely code word generator 308 in more detail. It is a polynomial adder 334 which consists of a set of N byte adders 114.

FIG. 8 shows output selector 312 from FIG. 3. It consists of multiple 3-input byte selectors 324.

The preferred implementation of delay function 310 (FIG. 3) is a set of shift registers. Actual implementation of delay function 310 depends upon the VLSI circuit technology being used.

FIG. 9 is a logical decomposition of feedback failure location system 400 shown in FIG. 1. It consists of a feedback microprocessor system 402, a content-addressable memory (CAM) 404, an address selector 406 and a conventional random access memory (RAM) 408. The outputs of RAM 408 are .mu., W.sub.R, W.sub.R-1, W.sub.R-2, . . . , W.sub.1, where W.sub.i are the locations of failures and .mu. is the number of failures in a received word. The value .mu. is an integer and the W.sub.i are bytes. CAM 404 and RAM 408 are controlled by feedback microprocessor system 402.

The content of RAM 408 is shown in FIG. 9-A. RAM 408 address 0 contains the location(s) of channel 200 failures. If there are additional failure areas, such as defects, RAM 408 address i(i.noteq.0) contains the location(s) of channel 200 failures plus the location(s) of additional failure areas. The content of RAM 408 is similar to a conventional defect map.

FIG. 9-B shows the logical structure of one embodiment of CAM 404 in FIG. 9. It consists of an address counter 410, multiple beginning address of failure registers 412, multiple comparators 414, an address encoder 416, an OR function 417, a failure length hold count down counter 420 and a RAM address register 418 as shown.

One object of the error-correcting system is to design parallel encoders and decoders that can be implemented in a single VLSI chip. VLSI chip packaging normally limits the number of pins to several hundred. The number of pins required by encoder 100 and decoder 300 of FIG. 1 may exceed the number of pins available in some circumstances. This problem can be solved by a pin reduction technique shown in FIG. 10. With this technique, inputs that normally input w-bit quantities are reduced to inputs that input streams of single-bit quantities. This is accomplished with multiple w-bit shift registers and w-bit holding registers. A reverse technique can be applied to outputs as shown also in FIG. 10. This requires control circuitry not shown.

The operation of the preferred embodiment of the error-correcting system is explained with an example. The message word "claim" is used as input. Assume channel "g" has previously failed and an error occurs in channel "b" during transmission. The example will show how decoder 300 receives the failure location information and the received word and performs finite field operations on the bytes (or letters) of the received word to correct the errors. See FIG. 11 for an overall picture of the example.

The example uses K=5, R=3, and N=K+R=8. K is the number of bytes in a message, R is the number of redundant bytes, and N is the number of bytes in a code word. Normally these values are determined after deciding how much error correction power is needed in a particular error-correcting system. The value S is the maximum number of soft errors and the value H is the maximum number of hard errors that can occur and still be corrected by the error-correcting system. (A soft error is a byte in error about which the decoder has no information. A hard error is a byte that is probably in error and the decoder knows its position before decoding begins. A hard error byte is also known as a failure location or erasure.) If R bytes of redundancy are chosen, a Reed-Solomon error-correcting system can correct S soft errors and H hard errors so long as 2S+H.ltoreq.R.

The example uses a finite field with 16 elements. Each element is represented by a 4-bit quantity (w=4) referred to as a byte or letter. In the example, the elements are denoted as 0, 1, a, b, c, d, e, f, g, h, i, j, k, l, m, and n. FIG. 12 shows the letter, binary and polynomial equivalents.

FIG. 12-A and FIG. 12-B show the addition, multiplication and reciprocal tables for the finite field. The finite field shown in FIG. 12-A and FIG. 12-B was generated by considering each element to be a binary polynomial and operating on polynomials modulo p(x), where p(x) is the irreducible binary polynomial of degree 4, equal to x.sup.4 +x+1 in this example case. Any other choice of an irreducible binary polynomial of degree 4 would have resulted in an equivalent finite field. The only difference would be in the naming of the elements. Each element in the finite field can be represented as a polynomial of degree 3 or less with binary coefficients. When an element of the finite field is represented as a polynomial, it is written with the highest powers of x on the left and the lowest powers of x on the right. The powers of x are in the reverse order as the representations of message, code word and received word polynomials to differentiate them from each other. This notation allows the same symbol, namely "x", to be used for the indeterminate in both types of polynomials. Polynomials which represent messages, code words and received words have nonbinary coefficients. Intermediate polynomials generated in the key equation solver also have nonbinary coefficients.

Each finite field has at least 1 primitive element. A primitive element is an element that, when multiplied by itself repeatedly, generates all the other nonzero elements in the field. Conventionally, a primitive element has been denoted as a. In the finite field shown in FIG. 12-A and FIG. 12-B, there are 8 primitive elements, namely a, b, d, g, h, k, m and n. Every finite field with 16 elements has 8 primitive elements.

The example uses a, a.sup.2 and a.sup.3 to be the roots of the Reed-Solomon generator polynomial, g(x), where a=a. In other words, g(x)=(x-a)(x-a.sup.2)(x-a.sup.3)=(x-a)(x-b)(x-c)=f+mx+kx.sup.2 +x.sup.3.

The generator matrix, G, for the example case is ##EQU1##

FIG. 12-C shows how the position of each byte in a code word is identified. Eight non-zero elements of the finite field are used to identify each byte in a code word. The inverses of the positions are also shown. Each channel 200 is also identified by the same designators as the code word bytes as shown in FIG. 11.

Encoder 100 is shown in FIG. 13 with the example message "claim" as input and "gda" as the redundant portion of the code word as output. FIG. 13-A shows the data flow and operation of the first redundant byte generator 102. FIG. 13-B shows the data flow and operation of the first byte multiplier 104 which multiplies the variable "c" by the constant "f" as shown in FIG. 13-A. The constant "f" determines the actual connections within each product bit generator 108. Product bit generator 108 multiplies the incoming row of bits by one column of the B matrix as described Appendix B where, for this case, ##EQU2## FIG. 13-C through FIG. 13-F show the data flow and operation along with a simplification for each of the four product bit generators 108 shown in FIG. 13-B. FIG. 13-G shows the data flow and operation of the byte adder circuitry 106 shown in FIG. 13-A. Remaining redundant bytes are generated in a similar manner.

The code word "gdaclaim" is transmitted through 8 parallel communications channels 200 (or stored in 8 parallel storage channels 200) as illustrated in FIG. 11. Channel "g" has previously failed and sent a failure indicator to feedback failure location system 400. Feedback failure location system 400 has previously written it's RAM 408 with data shown in FIG. 14. The byte "m" has been changed to "a" due to the failure. An error occurs during transmission or storage in channel "b", changing "a" to "i", which is unknown to decoder 300 and feedback failure location system 400.

An overall picture of the operation of decoder 300 is given in FIG. 15. Decoder 300 receives the word "gdiclaia" as input to syndrome generator 302. Syndrome generator 302 produces syndrome word "hha" as seen in FIG. 16. FIG. 16-A and FIG. 16-B show the data flow and operation of the first syndrome byte generator 314 which outputs "h". Remaining syndrome bytes are generated in a similar manner based upon finite field operations. The error detection matrix, D, for the example case is ##EQU3##

Syndrome word "hha" is input to key equation solver 304 along with failure location information "1g00". FIG. 17 shows the inputs and outputs of each stage of key equation solver 304. There are R=3 stages. FIG. 17-A, FIG. 17-B and FIG. 17-C show the data flow and operation of the three key equation solver 304 stages.

It is important to note that key equation solver stages can be simplified as shown in FIG. 17-A through FIG. 17-C due to knowledge of the initial values, the maximum possible degrees of the intermediate polynomials and characteristics of the key equation solver algorithm chosen. More particularly:

1. the sequence of polynomials, b.sup.O (x).sub.j and b.sup.T (x).sub.j begin as degree 0 polynomials and can increase in degree only by 1 at each stage. Circuitry does not have to be provided for coefficients that do not exist;

2. since the initial values for b.sup.O (x).sub.j and p.sup.O (x).sub.j =0 and the initial values for b.sup.T (x).sub.j =1, the circuitry can be simplified;

3. the low-order coefficients of p.sup.O (x).sub.j and p.sup.T (x).sub.j are always 0. This further reduces the complexity of key equation solver 304;

4. the last stage of key equation solver 304 (in this case Stage 3) can be substantially simplified because only b.sup.T (x).sub.j and p.sup.T (x).sub.j are required outputs. Other intermediate polynomials and values need not be generated because this is the last stage;

5. all operations are modulo x.sup.R+1, which means all polynomials are of degree R or less and no higher-order coefficients need be generated or retained.

FIG. 18 and FIG. 19 show simplified versions of stage 1 and stage 3 of key equation solver 304 as a result of the circuit reductions previously mentioned. FIG. 18-A shows the generation of p.sup.T (x).sub.1 for the simplified version of stage 1 of key equation solver 304. FIG. 18-B shows the data flow and operation of the first byte multiplier 336 for the generation of p.sup.T (x).sub.1. Remaining byte multipliers 336 operate in a similar fashion. The data flow and operation of stage 2 of key equation solver 304 is not shown and is self-explanatory. FIG. 19-A through FIG. 19-C show the generation of b.sup.T (x).sub.3 and FIG. 19-D through FIG. 19-F show the generation of p.sup.T (x).sub.3 for the simplified version of stage 3 of key equation solver 304.

Outputs from key equation solver 304 are the error locator word/polynomial and the error evaluator word/polynomial. These are input to most-likely error word generator 306.

FIG. 20 shows data flow and operation of most-likely error word generator 306. The data flow and operation of the first most-likely error byte generator 340 is shown in FIG. 20-A through FIG. 20-E.

FIG. 20-B shows the data flow and operation of L(x) evaluator 342 for x=1. FIG. 20-C shows the data flow through L'(x) selector 343. FIG. 20-D shows the data flow and operation of L'(x) evaluator 344 for x=1. FIG. 20-E shows the data flow and operation of V(x) evaluator 346 for x=1. Remaining most-likely error bytes are generated in a similar manner.

The output from most-likely error word generator 306 is the most-likely error word, which is input to most-likely code word generator 308 along with a delayed version of the received word. This is shown in FIG. 21.

Refer back to FIG. 9 for an overall picture of feedback failure location system 400. Feedback microprocessor system 402 is responsible for keeping content-addressable memory (CAM) 404 and random access memory (RAM) 408 updated with failure location information. The operation of feedback failure location system 400 depends upon whether the channels 200 are communications channels or storage channels. If the channels 200 are storage channels, such as DRAM memory chips, there will usually be more failure location information to deal with than if the channels 200 are communications channels, such as coaxial cables.

When the channels 200 are storage channels, feedback microprocessor system 402 sequentially reads every location in storage in background mode when the storage is not being used. If the storage is used 100% of the time, it interrupts use to do its reads. If the storage channels 200 are made up of Dynamic Random Access Memory (DRAM) chips, this background reading process can also provide the necessary memory refresh, eliminating the need for a separate refresh mechanism. During this time, feedback microprocessor system 402 makes a determination as to which areas in storage are failing based on the frequency of errors. If a particular area in storage makes errors at a rate of 80% of the time it is read (or another predetermined threshold), then feedback microprocessor system 402 determines that area to have failed. The actual algorithm used by feedback microprocessor system 402 is application-dependent. Once a location is determined to have failed, feedback microprocessor system 402 will update CAM 404 and RAM 408 shown in FIG. 9 with the appropriate values so that when that location is addressed in the future, failure location information will be supplied to the decoder.

When the channels 200 are communications channels, feedback failure location system 400 can normally be simplified because failures are usually entire channel failures, although it is possible that some failures may always occur at a certain time into the transmission. Then, the address counter becomes more of a "location in time" counter rather than a "location in space" counter.

Feedback microprocessor system 402 monitors communications or storage channel 200 failure indicators received from the channels 200 themselves. It also monitors failure indicators from other sources, for example, a user, which indicate a channel or channels have failed. When these failure indications occur, feedback microprocessor system 402 updates CAM 404 and RAM 408 with new failure location information. Feedback microprocessor system 402 is the intelligent entity that can decide the best course to follow when multiple channel 200 failure indicators occur simultaneously.

The content of RAM 408 address 0 contains the location(s) of failed channel(s) 200. The content of other RAM 408 addresses contain the location(s) of failed channel(s) 200 plus the locations of failure areas such as defects. Failure location information received by decoder 300 comes from the content of RAM 408 address 0 unless the address of data being received by decoder 300 matches an address contained in one of the beginning address of failure registers 412. In that case, failure location information received by decoder 300 comes from the content of RAM 408 address as determined by address encoder 416.

CAM 404 shown in FIG. 9-B can be implemented in various ways depending upon the length of failures. In FIG. 9-B, all the failures are assumed to be of a fixed length. "Length" means the number of consecutive locations that are affected by the failure. When all the failures are of fixed length, only the beginning address of the failure needs to be stored. When a location with a failure is accessed, one of the beginning address of failure registers 412 will contain an address that will match the address counter. When that occurs, comparator 414 will assert that A=B and address encoder 416 will output the comparator number to RAM address register 418. RAM address register 418 will hold that address until failure length hold count down counter 420 reaches a "0" count.

CAM 404 shown in FIG. 9-B can be implemented in other ways. For example, there could be two registers for each failure, one for the beginning address of each failure and one for the ending address of each failure. In that way, no assumption is made as to the length of the defect. The exact design of CAM 404 is application-dependent. It can also be implemented with failure locations of several different fixed lengths.

In the example case, feedback microprocessor system 402 has previously been informed that channel "g" has failed. As a result, feedback microprocessor system 402 has written RAM 408 as shown in FIG. 14. Since an entire channel has failed, only RAM 408 address 0 contains any meaningful information. The content of all addresses of RAM 408 other than 0 contain "don't care" data indicated by X's in FIG. 14.

The following appendices are referenced at points throughout the preceding text.

For a systematic Reed-Solomon code, code words, c, can be calculated by multiplying message words, m, by a Reed-Solomon generator matrix, G, as shown below: ##EQU4##

The preferred implementation of encoder 100 shown in FIG. 2-A uses G as shown above. g(x) is the generator polynomial.

For a non-systematic Reed-Solomon code, code words, c, can be calculated by multiplying message words, m by an alternative Reed-Solomon generator matrix, G.sub.A, as shown below: ##EQU5## where g.sub.i are the coefficients of the code's generator polynomial.

Let p(x) be an irreducible binary polynomial of degree w that generates a finite field with 2.sup.w elements and let each element be represented as a binary polynomial of degree.ltoreq.w-1.

Assume one input of the byte multiplier is

and the other input is

Then, ##EQU6##

In matrix notation, ##EQU7##

If b(x) is a constant, B is a w.times.w matrix of constants (bits) and a B can be implemented by the circuits shown in FIG. 2-B and FIG. 2-C.

If b(x) is a variable, then a.multidot.B can be implemented by the circuit shown in FIG. 5-H.

Conventionally, for Reed-Solomon codes, the syndrome word, S, is generated by multiplying the received word, r, by an error detection matrix, D, which evaluates r(x) at a.sup.i+j, j=0, 1 . . . R-1 as shown below: (i is a constant in the range of 0-2.sup.w -1). ##EQU8##

The preferred implementation of syndrome generator 302 shown in FIG. 4-A uses the error detection matrix as shown above.

Note that the error detection matrix, D, is the transpose of the conventional parity check matrix, H, or, D=H.sup.T.

Alternatively, the syndrome word, S, can be generated by multiplying the received word, r, by an alternative error detection matrix followed with the multiplication by a g(x) roots matrix, D.sub.R, as shown below: ##EQU9##

D, D.sub.A and D.sub.R are matrices of constants from a finite field with 2.sup.w elements.

The alternative method of generating the syndrome word allows encoder 100 circuitry to be used as a component of syndrome generator 302.

Assume a(x)=a.sub.O +a.sub.1 x+a.sub.2 x.sup.2 + . . . a.sub.n x.sup.n and b(x)=b.sub.0 +b.sub.1 x+b.sub.2 x.sup.2 + . . . b.sub.n x.sup.n.

Then, a(x)b(x)modx.sup.R+1 =(a.sub.O +a.sub.1 x+a.sub.2 x.sup.2 + . . . +a.sub.n x.sup.n)b(x)modx.sup.R+1.

In matrix notation, ##EQU10##

B has R+1 columns.

Let .delta.(x)=.delta..sub.j-1 +W.sub.j x and a(x)=a.sub.0 +a.sub.1 x+a.sub.2 x.sup.2 + . . . +a.sub.n x.sup.n.

Then ##EQU11##

The circuit to implement .delta.(x)a(x) is shown in FIG. 5-F. The number of stages required depends on the degree of a(x).

Let L(x)=L.sub.0 +L.sub.1 x+L.sub.2 x.sup.2 +L.sub.3 x.sup.3 + . . . +L.sub.n x.sup.n.

Then the derivative of L(x) is L'(x)=L.sub.1 +2L.sub.2 x+3L.sub.3 x.sup.2 + . . . nL.sub.n x.sup.n-1.

The coefficient nL.sub.n means L.sub.n +L.sub.n + . . . n times. If n is even, nL.sub.n =0. If n is odd, ##EQU12##

The degree of L'(x) is less than the degree of L(x).