US4975867A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus for dividing elements of a Galois Field GF (2QM)
Assignee: Maxtor Corp
•
Filing: 1987-06-26
•
Granted: 1990-12-04
•
Expires: 2007-06-26
Abstract
Abstract The invention is an apparatus and/or method which enables one to divide two elements, A and B, of GF(2 2M ), that is, perform the operation B/A, by finding the multiplicative inverse of the divisor A, and then multiplying the inverse by the numerator, B. The multiplicative inverse, A -1 , of A is found by computing a conversion factor, D, and then multiplying A by D to convert it to an element C, where C is also an element of a smaller Galois Field, GF(2 M ), which is a subfield of GF(2 2M ). Specifically, C is equal to A 2 .spsp.M.sbsp.+1), or A 2 .spsp.M *A, in the field GF(2 2M ). Next, the multiplicative inverse, C -1 , of C in GF(2 M ) is found by appropriately entering a stored look-up table containing the 2 M elements of GF(2 M ). The multiplicative inverse, C -1 , of C is thereafter converted, by multiplying it by the conversion factor D calculated above, to the element of GF(2 2M ) which is the multiplicative inverse, A -1 , of the original divisor, A. The multiplicative inverse, A -1 , of A is then multiplied by B to calculate the quotient, B/A.
Inventors
- 👤 Lih-Jyh Weng
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 04:57
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/38; G06F7/48; G06F7/52; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; G06F7/60; G06F7/72; G06F7/724; G06F7/726; G06F2207/00; G06F2207/72; G06F2207/7209
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
157 words
An encoding apparatus containing means for computing the quotient, B/A, of two elements of Galois Field FG(2 QM ), said apparatus comprising: A. means for converting the divisor, A, into an element C of GF(2 QM ), where C is A P and P equals 2.sup.(Q-1)m +2.sup.(Q-2)M +. . . + 2 M +1, the element C being also an element of a smaller Galois Field GF(2 M ) which is a sub-field of GF(2 QM ); B. means for finding the multiplicative inverse, C -1 , of the element C in the smaller Galois Field GF(2 M ); C. means for converting the multiplicative inverse, C -1 , into an element of GF(2 QM ) which is the multiplicative inverse, A-1, of A by multiplying C -1 by A S where S equals 2.sup.(Q-1)M +23.sup.(Q-2)M +. . . +2 M ; and D. means for multiplying the element B by the multiplicative inverse A -1 .
Claim 2
Dependent Claim
157 words
An encoding apparatus containing means for computing the quotient, B/A, of two elements of Galois Field FG(2 QM ), said apparatus comprising: A. means for converting the divisor, A, into an element C of GF(2 QM ), where C is A P and P equals 2.sup.(Q-1)m +2.sup.(Q-2)M +. . . + 2 M +1, the element C being also an element of a smaller Galois Field GF(2 M ) which is a sub-field of GF(2 QM ); B. means for finding the multiplicative inverse, C -1 , of the element C in the smaller Galois Field GF(2 M ); C. means for converting the multiplicative inverse, C -1 , into an element of GF(2 QM ) which is the multiplicative inverse, A-1, of A by multiplying C -1 by A S where S equals 2.sup.(Q-1)M +23.sup.(Q-2)M +. . . +2 M ; and D. means for multiplying the element B by the multiplicative inverse A -1 .
Claim 3
Dependent Claim
38 words
The apparatus recited in claim 1 wherein said means for calculating C comprises: A. means for calculating a conversion factor of the form A S ; and B. means for multiplying said conversion factor by the element A.
Claim 4
Dependent Claim
35 words
The apparatus recited in claim 1 wherein said means for finding the multiplicative inverse, C -1 , further includes the use of a look-up table consisting of all [2 M ]elements of GF(2 M ).
Claim 5
Dependent Claim
36 words
The apparatus of claim 1 wherein said means for converting the multiplicative inverse, C -1 , into the multiplicative inverse of element A further includes multiplying the multiplicative inverse, C -1 , by the conversion factor.
Claim 6
Dependent Claim
148 words
An encoding apparatus containing means for computing the quotient, B/A, of two elements of Galois Field GF(2 2M ), said apparatus comprising: A. means for converting the divisor, A, into an element C of GF(2 2M ), where C is A T and T equals w M +1, the element C being also an element of a smaller Galois Field GF(2 M ) which is a sub-field of GF(2 2M ); B. means for finding the multiplicative inverse, C -1 , of the element C in the smaller Galois Field GF(2 M ); C. means for converting the multiplicative inverse, C -1 , into an element of GF(2 2M ) which is the multiplicative inverse, A -1 , of A by multiplying C -1 by A R where R equals 2 M ; and D. means for multiplying the element B by the multiplicative inverse A -1 .
Claim 7
Dependent Claim
148 words
An encoding apparatus containing means for computing the quotient, B/A, of two elements of Galois Field GF(2 2M ), said apparatus comprising: A. means for converting the divisor, A, into an element C of GF(2 2M ), where C is A T and T equals w M +1, the element C being also an element of a smaller Galois Field GF(2 M ) which is a sub-field of GF(2 2M ); B. means for finding the multiplicative inverse, C -1 , of the element C in the smaller Galois Field GF(2 M ); C. means for converting the multiplicative inverse, C -1 , into an element of GF(2 2M ) which is the multiplicative inverse, A -1 , of A by multiplying C -1 by A R where R equals 2 M ; and D. means for multiplying the element B by the multiplicative inverse A -1 .
Claim 8
Dependent Claim
38 words
The apparatus recited in claim 5 wherein said means for calculating C comprises: A. means for calculating a conversion factor of the form A R ; and B. means for multiplying said conversion factor by the element A.
Claim 9
Dependent Claim
159 words
A decoding apparatus containing means for computing the quotient, B/A, of two elements of Galois Field GF(2 QM ), said apparatus comprising: A. means for converting the divisor, A, into an element C of GF(2 QM ), where C is A P and P equals 2.sup.(Q-1)M +2.sup.(Q-2)M +. . . + 2 M +1, the element C being also an element of a smaller Galois Field GF(2 M ) which is a sub-field of GF(2 QM ); B. means for finding the multiplicative inverse, C -1 , of the element C in the smaller Galois Field GF(2 M ); C. means for converting the multiplicative inverse, C -1 , into an element of GF(2 QM ) which is the multiplicative inverse, A -1 , of A by multiplying C -1 by A S where S equals 2.sup.(Q-1)M +2.sup.(Q-2)M +. . . +2 M ; and D. means for multiplying the element B by the multiplicative inverse A -1 .
Claim 10
Dependent Claim
159 words
A decoding apparatus containing means for computing the quotient, B/A, of two elements of Galois Field GF(2 QM ), said apparatus comprising: A. means for converting the divisor, A, into an element C of GF(2 QM ), where C is A P and P equals 2.sup.(Q-1)M +2.sup.(Q-2)M +. . . + 2 M +1, the element C being also an element of a smaller Galois Field GF(2 M ) which is a sub-field of GF(2 QM ); B. means for finding the multiplicative inverse, C -1 , of the element C in the smaller Galois Field GF(2 M ); C. means for converting the multiplicative inverse, C -1 , into an element of GF(2 QM ) which is the multiplicative inverse, A -1 , of A by multiplying C -1 by A S where S equals 2.sup.(Q-1)M +2.sup.(Q-2)M +. . . +2 M ; and D. means for multiplying the element B by the multiplicative inverse A -1 .
Claim 11
Dependent Claim
38 words
The apparatus recited in claim 7 wherein said means for calculating C comprises: A. means for calculating a conversion factor of the form A S ; and B. means for multiplying said conversion factor by the element A.
Claim 12
Dependent Claim
33 words
The apparatus recited in claim 7 wherein said means for finding the multiplicative inverse, C -1 , further includes the use of a look-up table consisting of all elements of GF(2 M ).
Claim 13
Dependent Claim
36 words
The apparatus of claim 7 wherein said means for converting the multiplicative inverse, C -1 , into the multiplicative inverse of element A further includes multiplying the multiplicative inverse, C -1 , by the conversion factor.
Claim 14
Dependent Claim
148 words
A decoding apparatus containing means for computing the quotient, B/A, of two elements of Galois Field GF(2 2M ), said apparatus comprising: A. means for converting the divisor, A, into an element C of GF(2 2M ), where C is A T and T equals w M +1, the element C being also an element of a smaller Galois Field GF(2 M ) which is a sub-field of GF(2 2M ); B. means for finding the multiplicative inverse, C -1 , of the element C in the smaller Galois Field GF(2 M ); C. means for converting the multiplicative inverse, C -1 , into an element of GF(2 2M ) which is the multiplicative inverse, A -1 , of A by multiplying C -1 by A R where R equals 2 M ; and D. means for multiplying the elements B by the multiplicative inverse A -1 .
Claim 15
Dependent Claim
148 words
A decoding apparatus containing means for computing the quotient, B/A, of two elements of Galois Field GF(2 2M ), said apparatus comprising: A. means for converting the divisor, A, into an element C of GF(2 2M ), where C is A T and T equals w M +1, the element C being also an element of a smaller Galois Field GF(2 M ) which is a sub-field of GF(2 2M ); B. means for finding the multiplicative inverse, C -1 , of the element C in the smaller Galois Field GF(2 M ); C. means for converting the multiplicative inverse, C -1 , into an element of GF(2 2M ) which is the multiplicative inverse, A -1 , of A by multiplying C -1 by A R where R equals 2 M ; and D. means for multiplying the elements B by the multiplicative inverse A -1 .
Claim 16
Dependent Claim
38 words
The apparatus recited in claim 11 wherein said means for calculating C comprises: A. means for calculating a conversion factor of the form A R ; and B. means for multiplying said conversion factor by the element A.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-12-03 | 1994-06-04 | 1994-12-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-12-03 | 1998-06-04 | 1998-12-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-12-03 | 2002-06-04 | 2002-12-04 | $7700.00 | Window Closed / Lapsed |