Method and apparatus to determine the log of an element in GF(2.sup.m) with the help of a small adjustable size table
AssigneeQLOGIC, Corporation
InventorAlok Gupta
Life of this patent
Estimating the term…
Abstract
A system for determining the log of an element in Galois field GF(2.sup.m) using a small, selectable size table, a finite field multiplier, and a counter. The system allows for a flexible trade-off between speed and integrated circuit area, and applies for any GF(2.sup.m) for all possible m. The system allows for on-the-fly error location determination without the need for storing all possible logs for the GF(2.sup.m) under consideration.
Claims12
A method for determining the logarithm of a predetermined element of a Galois field GF(2.sup.m) utilizing a table stored in a device, the table having a plurality of logarithm values for a predetermined range of the GF(2.sup.m) elements stored therein, the predetermined element having a power n such that 0.ltoreq.n.ltoreq.(2.sup.m -1), the method comprising the steps of:
- a. initializing a counter to a preset value;
- b. using the predetermined element as an address to the table, wherein the table produces (1) a first predetermined output if the predetermined element is not a valid address to the table and (2) a second predetermined output if the predetermined element is a valid address to the table;
- c. if the output from the table is the first predeterimined output, then:
- i. incrementing the counter;
- ii. reducing the power of the predetermined element by an amount equal to the number of logarithm values stored in the table;
- and
- iii. returning to step b;
- d. if the output from the table is the second predetermined output, then:
- i. combining the value of the counter with at least a portion of the output of the table to produce a combined output, wherein the combined output is the logarithm of the predetermined element.
An apparatus for determining the logarithm of a predetermined element of a Galois field GF(2.sup.m) utilizing a table stored in a device, the table having a plurality of logarithm values for a predetermined range of the GF(2.sup.m) elements stored therein, the predetermined element having a power n such that 0.ltoreq.n.ltoreq.(2.sup.m -1), the apparatus comprising:
- a. a counter having an initial value therein;
- b. means for addressing the table utilizing the predetermined element as an address, wherein the table produces (1) a first predetermined output if the predetermined element is not a valid address to the table and (2) a second predetermined output if the predetermined element is a valid address to the table;
- c. means, responsive to the first predetermined output, for incrementing the counter;
- d. means, responsive to the first predetermined output, for adjusting the power of the predetermined element by the an amount equal to the number of logarithm values stored in the table;
- e. means for feeding back the adjusted predetermined element to the means for addressing, wherein the means for addressing utilizes the adjusted predetermined element as an address to the table and wherein the means for incrementing, the means for adjusting, and the means for feeding back continue to respond to the first predetermined output until a second predetermined output is produced in response to an adjusted predetermined element;
- f. means, responsive to the second predetermined output from the table, for combining the value of the counter with at least a portion of the second predetermined output, to produce a combined output, wherein the combined output is the logarithm of the predetermined element.
Dependencies are inferred from the claim text.