Finite Fields and RS Codes It is customary to call any primitive element “alpha” or Here’s an example of three Finite Fields with 16 4-bit elements. - OR- Now, let’s call the elements in the second column the locations, Li, of the codeword or received word symbols/coefficients as illustrated below where Since, as we’ve seen above, the syndrome for Suppose the error pattern has nonzero error values of Va and Vb in locations, La and Lb. Then,
With two errors, there are 4 unknowns so we need 4 simultaneous equations to solve for the 4 unknowns. If the locations of two errors are known, then we only need 2 simultaneous equations since there are only 2 unknowns. In general, to correct t errors, 2t redundant symbols are needed. To correct s erasures, s redundant symbols are required, and to simultaneously correct t errors and s erasures, 2t+s redundant symbols are required. RS codes are “almost perfect” so only a minimum number of redundant symbols are required. RS decoders find the unknown error location and error values. For erasures, the error location is known and only the error value is unknown. It is possible for the error value to be 0 for an erasure, but not for an error. It took many mathematicians many years to discover practical methods for solving the above simultaneous equations. The good news is that today a number of different practical methods exist that are easily implemented in digital logic. It is next to impossible for non-mathematicians to understand why the methods work, but it is easy for most engineers to understand how to implement the methods. Developers, manufacturers and users do not need to understand why methods work, they just need to be sure the methods work, and mathematicians have proved that the methods will always work. ECC Tek makes use of Willard Eastman’s Euclideanized version of the Berlekamp-Massey algorithm to find error locations and values. Most RS and BCH decoders make use of what is called the key equation/congruency. An error locator polynomial, L(x), and an error evaluator polynomial, V(x) are defined and the key equation is The B-M algorithm finds the lowest degree L(x) and V(x) given S(x) (and possibly erasure locations when erasures are being corrected as well as errors) that satisfy the key congruency. Mod x2t means the highest degree of V(x) is 2t-1. When the algorithm is finished, the roots of L(x) indicate the locations of the errors and a simple formula is used to compute the values of the errors. For parallel RS implementations, a parity generator matrix is used for encoding and a parity check matrix for calculating the syndrome. Then the B-M algorithm is executed in a parallelized and pipelined fashion. For serial RS implementations, operations are performed serially. Distinction Between Errors and Erasures As far as ECC Tek’s encoder and decoder designs are concerned, we make the following definitions for errors and erasures. These definitions may not be the same as what you may find in a textbook or papers on coding theory. Their definition of erasure may involve an additional erasure character. For errors, both the location and value of the actual error are unknown, and the error value is not zero. For erasures, the location of the “potential” error is known, the value is unknown, and the value could be nonzero or zero. RS RAID Implementing RAID-2 RAID-2 corrects for 1 unknown component failure. The following figure illustrates one row of RS symbols across multiple components. Each RS row symbol is stored in a separate component. Both the location and value of the error are unknown. Since there are 2 unknowns, 2 simultaneous equations are needed to solve for the unknown error location and error value. RS RAID Implementing RAID-3, RAID-4, and RAID-5 RS RAID Implementing RAID-6 Scalable RS RAID RS RAID systems tolerate s component failures and t errors in each row as long as 2t + s < R where R is the number of redundant components. |
Mathematics >