System for computing the multiplicative inverse of an...

Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Reexamination Certificate

active

06279023

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to data processing systems and, more particularly, to systems that manipulate data codewords that are encoded using codes based on Galois fields.
BACKGROUND OF THE INVENTION
Data stored on magnetic media, such as a magnetic 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 disk, or noise. As the density of the data stored on the disk increases, more errors are likely, and the system is required to correct greater numbers of errors, which include greater numbers of burst errors. A burst error is typically defined as a contiguous number of symbols in which the first symbol and the last symbol are erroneous. The speed with which the system corrects the errors, including the burst errors, is important to the overall speed with which the system processes the data.
Prior to recording, multiple-bit data symbols are encoded using an error correction code (ECC). When the data symbols are retrieved from the disk and demodulated, the ECC is employed to, as the name implies, correct the erroneous data.
Specifically, before a string of k data symbols is written to a disk, it is mathematically encoded using an (n, k) ECC to form n-k ECC symbols. The ECC symbols are then appended to the data string to form an n-symbol error correction code word, which is then written to, or stored, on the disk. When the data are read from the disk, the code words containing the data symbols and ECC symbols are retrieved and mathematically decoded. During decoding, 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,
2nd Ed. MIT Press, 1972].
To correct multiple errors in strings of data symbols, the system typically uses an ECC that efficiently and effectively utilizes the various mathematical properties of sets of symbols known as Galois fields. Galois fields are represented “GF (P
M
)”, where “P” is a prime number and “M” can be thought of as the number of digits, base “P”, in each element or symbol in the field. P usually has the value 2 in digital computer and disk drive applications and, therefore, M is the number of bits in each symbol. The ECC's commonly used with the Galois Fields are Reed Solomon codes or BCH codes.
Reed Solomon and BCH decoding operations involve a plurality of division operations. One method of dividing a Galois field element A by a Galois field element B is to determine the multiplicative inverse, B
−1
, of B and then multiply A by B
−1
. In prior systems a look-up table is typically used to determine the multiplicative inverse, so that the system need not perform a known, time-consuming series of steps to produce the inverse. The look-up table contains 2
m
−1 entries. For systems using GF(2
8
), that is, using 8-bit symbols, the look-up table has 2
8
−1, or 255, entries.
As the density of the data increases, larger Galois Fields are used to produce the longer data codewords that are required to protect the data. Consequently, larger look-up tables are required to provide the multiplicative inverses. For GF(2
10
) or GF(2
12
), for example, the required tables have 1023 and 4095 entries, respectively. Each of the tables thus consumes a great deal of storage space, which for some systems is too expensive and/or impractical. Accordingly, what is needed is a mechanism that, without being overly complex, relatively quickly calculates the multiplicative inverses, and thus, eliminates the need for the look-up table.
SUMMARY OF THE INVENTION
A system for determining the multiplicative inverse of an element of GF(2
m
) by raising the element to the power 2
m
−2. The system takes advantage of the fact that all non-zero elements of GF(2
m
) are roots of the polynomial x
2
m
−x=0 or x
2
m
−1
−1=0, and thus, for any &agr;
j
∈GF(2
m
),
(&agr;
j
)
2
m
−1
=1  eqn. 1
Multiplying both sides of equation 1 by (&agr;
j
)
−1
:
(&agr;
j
)
−1
*(&agr;
j
)
2
m
−1
=(&agr;
j
)
−1
*1
where “*” represents multiplication, gives the inverse of &agr;
j
as
&agr;
−j
=(&agr;
j
)
2
m
−2
  eqn. 2
The system may raise the element &agr;
j
to the power 2
m
−2 by repeatedly multiplying the element by itself 2
m
−3 times. Alternatively, the system may produce the exponent 2
m
−2 as the sum of:
2
m−1
+2
m−2
+ . . . +2
3
+2
2
+2
1
and thus (&agr;
j
)
2
m
−2
as
(&agr;
j
)
2
m
−1
*(&agr;
j
)
2
m
−2
* . . . *(&agr;
j
)
2
3
*(&agr;
j
)
2
2
*(&agr;
j
)
2
  eqn. 3
To do this, the system may iteratively square &agr;
j
to produce the various factors of eqn. 3 and, using a single multiplier, multiply and accumulate the results. This implementation of the system is not complex, but requires m-1 time-consuming multiplication cycles. Alternatively, the system may use a plurality of circuits operating in parallel and simultaneously raise the element &agr;
j
to the powers 2
m−2
, 2
m−2
and so forth, and a plurality of tiered multipliers to then multiply the factors together. This implementation is fast, but includes a relatively large number of complex multiplier circuits.
Preferably, the system raises the element &agr;
j
to the power 2
m
−2 using a relatively small number of “stages,” as a best trade-off between complexity and delay. To do this the system produces the exponent 2
m
−2 as a combination of various products and sums. The products are implemented by raising the appropriate elements to powers of 2 and the sums are implement by multiplying elements together. The system thus includes a first stage in which circuits in parallel raise the element &agr;
j
to various powers of 2; a second stage in which multipliers selectively combine the results produced in the first stage; and one or more stages in which circuits raise selected products produced in the preceding stages to various powers of 2 and/or multipliers selectively combine the results produced in preceding stages. The system produces the inverses using a minimal number of stages, each with at most one multiplier, such that the system includes relatively few multipliers and the associated delay is minimized.


REFERENCES:
patent: 5195052 (1993-03-01), Karim
patent: 5206824 (1993-04-01), Arazi
patent: 5467297 (1995-11-01), Zook
patent: 5890800 (1999-04-01), Meyer
patent: 6049815 (2000-04-01), Lambert et al.
patent: 6052704 (2000-04-01), Wei

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

System for computing the multiplicative inverse of an... 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 computing the multiplicative inverse of an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for computing the multiplicative inverse of an... will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-2546963

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.