Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-06-30
2001-03-06
Ngo, Chuong Dinh (Department: 2787)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06199088
ABSTRACT:
FIELD OF INVENTION
This invention relates to data error correction systems, and in particular to Galois Field division operations performed by the systems.
BACKGROUND OF THE INVENTION
The importance of error correction coding of data in digital computer systems has increased greatly as the density of the data recorded on mass storage media, more particularly magnetic disks, has increased. With higher recording densities, a tiny imperfection in the recording surface of a disk can corrupt a large amount of data. In order to avoid losing that data, error correction codes (“ECC's”) are employed to, as the name implies, correct the erroneous data.
Before a string of data symbols is recorded on a disk, 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 on the disk. When the stored data is to be accessed from the disk, the code words containing the data symbols are retrieved from the disk 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 straight forward. One solution to determining the inverse is to test each element of the field, by multiplying the element by B. 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 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
+1
=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 full 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. The system must also hold the 2M-bit conversion factor D that is used to produce C, until C
−1
is retrieved from the look-up table.
We have devised an improved system that, for selected Galois Fields GF(2
2M
) where 2M+1 is prime, produces the multiplicative inverse of A in fewer clock cycles. Further, the improved system uses less complex circuitry than the system of the '876 patent. We discuss the improved system below.
SUMMARY OF THE INVENTION
For selected Galois Fields GF(2
2M
), the improved system performs a Galois Field division of two elements B/A by first producing a multiplicative inverse of A, where A is represented by a (2M+1)-bit symbol, and then multiplying B by A
−1
, preferably using a (2M+1)-bit symbol for B.
The system directly converts the (2M+1)-bit representation of A to an associated element C=A
2
M
+1
that is also an element of the subfield GF(2
M
). As discussed in more detail below, A
2
M
is produced by permuting the (2M+1) bits of A, and C is produced by multiplying A by the permuted bits. The multiplication is simplified, however, because of the duplication of bits between A and A
2
M
, and the multiplier produces only M+1 bits to represent the 2M+1 bits of C. Accordingly, the multiplier performs fewer bit manipulations, and is less complex and faster than a full Galois Field multiplier. Indeed, the permutation of the bits to produce A
2
M
is incorporated directly into the bit manipulations and need not be performed as a separate operation, as is done in the prior system. Further, there is no need to retain the quantity A
2
M
for a later multiplication operation, since the quantity is readily produced by permuting the 2M+1 bits of A.
The M+1 bits that represent C are used to enter a (2
M
−1)-entry look-up table that contains the multiplicative inverse of C. The multiplicative inverse, C
−1
, is also represented by M+1 bits, and thus, the amount of storage space required for each entry of the table is reduced from 2M bits to M+1 bits. The (M+1)-bit representation of C
−1
is then converted to the multiplicative inverse A
−1
by multiplying the M+1 bits by the (2M+1)-bit representation of A
2
M
. As discussed, the quantity A
2
M
is produced, without delay, by permuting the 2M+1 bits of A.
The multiplier that produces A
−1
multiplies the 2M+1 permuted bits by M+1 bits, and thus, performs approximately one-half of the bit manipulations that are performed by a full Galois Field multiplier that multiplies two 2M-bit symbols. Accordingly, the multiplier is less complex and faster than the full multiplier.
The multiplicative inverse A
−1
is next multiplied by B to produce the quotient B/A. The system preferably represents B by a (2M+1)-bit symbol and performs the multiplication by exclusive-OR'ing cyclically shifted copies of B, as discussed in more detail below.
REFERENCES:
patent: 4975867 (1990-12-01), Weng
patent: 4989171 (1991-01-01), Hollmann
patent: 5612910 (1997-03-01), Meyer
patent: 5890800 (1999-04-01), Meyer
Langer Diana
Weng Lih-Jyh
Ngo Chuong Dinh
Quantum Corp.
Sheehan Patricia A.
LandOfFree
Circuit for determining multiplicative inverses in certain... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circuit for determining multiplicative inverses in certain..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit for determining multiplicative inverses in certain... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2445312