Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-02-28
2004-08-17
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06779011
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to data error correction systems, and in particular to Galois Field division operations performed by the systems.
2. Background Information
Data stored on magnetic media, such as a magnetic tape and disks, are typically stored in encoded form, so that errors in the stored data can possibly be corrected. The errors may occur, for example, because of inter-symbol interference, a defect in the tape or disk, or noise. As the density of the data stored on the tape or disk increases, more errors are likely, and the system is required to correct greater numbers of errors. The speed with which the system corrects the errors is important to the overall speed with which the system processes the data.
Before a string of data symbols is recorded, it is mathematically encoded to form ECC symbols. The ECC symbols are then appended to the data string to form code words—data symbols plus ECC symbols—and the code words are then stored. When the stored data is to be accessed, the code words containing the data symbols are retrieved and mathematically decoded. During decoding any errors in the data are detected and, if possible, corrected through manipulation of the ECC symbols [For a detailed description of decoding see Peterson and Weldon, Error Correction Codes, 2d Edition, MIT Press, 1972].
Stored digital data can contain multiple errors. One of the most effective types of ECC used for the correction of multiple errors is a Reed-Solomon code [For a detailed description of Reed-Solomon codes, see Peterson and Weldon, Error Correction Codes]. With Reed-Solomon codes, the encoding and decoding operations are performed over a Galois Field, using Galois Field addition, multiplication and division operations.
Galois Field division is generally a time consuming operation that significantly lengthens the ECC encoding and decoding processes. The time it takes to perform error correction operations adversely affects the rate at which data can be retrieved from a storage device and supplied to a user or to a computer application that requires the data.
One way to perform a Galois Field division operation, B/A, where A and B are elements of the Galois Field GF(2
Q
), is to determine the multiplicative inverse of A and multiply B by the inverse. Finding the inverse of a Galois Field element is not particularly straightforward. One solution to determining the inverse is to test each element of the field, by multiplying the element by A. This is very time consuming, particularly with the larger Galois Fields that are used to protect the higher-density data.
Another solution is to use a look-up table that contains the multiplicative inverses. If a Galois Field GF(2
2M
) is used, a (2
2M
−1)-element look-up table is required. With many systems, it is undesirable to have such large look-up tables, which require both large amounts of storage space and relatively complex addressing circuitry.
A better solution is described in U.S. Pat. No. 4,975,876, which has a common inventor and is incorporated herein by reference. The system described in the '876 patent determines the multiplicative inverse of an element A of GF(2
2M
) by first computing a conversion factor, D=A
2
M
, and then multiplying A by D to produce an associated element C=A
2
M
+1
. The element C is also an element of a smaller Galois Field, GF(2
M
), which is a subfield of GF(2
2M
). The system then determines the multiplicative inverse of C by entering a (2
M
−1)-element look-up table. The system next converts the inverse of C, C
−1
=A
−(2
M
+1)
, to the multiplicative inverse of A by multiplying C
−1
by the conversion factor D, to produce A
−(2
M
+1)
*A
2
M
=A
−1
, where “*” represents Galois Field multiplication.
The system described in the '876 patent works well and determines the multiplicative inverse of A relatively quickly, using a (2
M
−1)-entry look-up table rather than the larger (2
2M
−1)-entry table. The system, however, requires at least one relatively complex fall Galois Field multiplier to multiply together two 2M-bit symbols. A single multiplier may be used multiple times to multiply together A and D, and then C
−1
and D, or two of the multipliers may be used to perform the two multiplications. The multiplication operations, whether performed by one or two full Galois Field multipliers, involve manipulation of two 2M-bit symbols and are thus both relatively time consuming and complex.
We have devised an improved system that produces the multiplicative inverses of the elements of GF(2
2M
) in fewer clock cycles and/or using less complex multipliers, and/or using smaller tables. We discuss the improved system below.
SUMMARY OF THE INVENTION
The invention is a system that determines the multiplicative inverse of A&egr;GF(2
2M
) by representing A using a selected basis and performing various operations that involve raising A to powers of 2 as cyclic rotations of A. The system also performs multiplication operations over GF(2
2M
) or subfields thereof by calculating the coefficients of the product of two elements A and B that are represented using the selected basis as combinations of the coefficients of cyclically rotated versions of A and B.
The system utilizes a relatively small look-up table that contains the multiplicative inverses of selected elements of a subfield of GF(2
2M
). The system may then cyclically rotate the multiplicative inverse values read from the table to produce the multiplicative inverses of the remaining elements of the subfield. Thereafter, as applicable, the system further manipulates the multiplicative inverse of the subfield element, to produce the multiplicative inverse of the desired element of GF(2
2M
).
More specifically, the system represents the elements of GF(2
2M
) using a selected basis in which each basis element is the square of the preceding basis element. Raising a field element to a power 2
k
is then a cyclic rotation of the element by k bits. Further, multiplication of A*B, where B is also represented using the selected basis, is performed essentially by combining cyclically rotated versions of A and B, as discussed in more detail below.
The system thus raises A to the power 2
M
by cyclic rotation of A, or the equivalent thereof, to produce the conversion factor A
2
M
and multiplies the factor by A in the manner discussed above to produce A
2
M+1
, which is an element of the subfield GF(2
M
). The multiplicative inverse of this element may then be determined by entering a look-up table that contains the multiplicative inverses of elements of GF(2
M
). Using the selected basis, elements of GF(2
2M
) that are elements of the subfield GF(2
M
) have m lowest-order coefficients that are duplicates of the m highest order coefficients. Each element in the look-up table can thus be represented using only m bits, and the table can be entered with m bits. Accordingly, the table and the associated circuitry are less complex than those required when the conventional basis is used to represent the elements.
After retrieving the multiplicative inverse from the table, the system then multiplies it by the conversion factor to produce A
−1
. As discussed, the multiplication operations are readily performed using cyclically rotated versions of the elements.
The system may further manipulate A
2
M
+1
by raising the element to selected powers of 2, to produce elements that are also elements of smaller subfields of GF(2
2M
), e.g.,
G
F
(
2
M
2
)
and so forth. The system may then use correspondingly smaller look-up tables.
The size of the tables can be even further reduced by one-half or more by including therein only the multiplicative inverses of the elements of a given subfield that have one or more coefficients set to particular values. As an example, the table may include the multiplicative inverses of the elements that have the highest-order coefficient se
Hall Dana
Imrich Christine
Weng Lih-Jyh
Cesari and McKenna LLP
Malzahn David H.
Maxtor Corporation
LandOfFree
System for performing multiplication and division in GF(22M) does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for performing multiplication and division in GF(22M), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for performing multiplication and division in GF(22M) will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3274765