LOW-POWER ERROR CORRECTION CODE COMPUTATION IN GF (2R)

Abstract

A method of performing division operations in an error correction code includes the steps of receiving an output ω∈F†{0} wherein F=GF(2.sup.r) is a Galois field of 2.sup.r elements, ω=Σ.sub.0≤i≤r−1β.sub.i×α.sup.i wherein α is a fixed primitive element of F, and β.sub.i∈GF(2), wherein K=GF(2.sup.s) is a subfield of F, and {1, α} is a basis of F in a linear subspace of K; choosing a primitive element δ∈K, wherein ω=ω.sub.1+α×ω.sub.2, ω.sub.1=Σ.sub.0≤i≤s−1γ.sub.i×δ.sup.i∈K, ω.sub.2=Σ.sub.0≤i≤s−1γ.sub.i+s×δ.sup.i∈K, and γ=[γ.sub.0, . . . , γ.sub.r−1].sup.T∈GF(2).sup.r; accessing a first table with ω.sub.1 to obtain ω.sub.3=ω.sub.1.sup.−1, computing ω.sub.2×ω.sub.3 in field K, accessing a second table with ω.sub.2=ω.sub.3 to obtain (1+α×ω.sub.2×ω.sub.3).sup.−1=ω.sub.4+α×ω.sub.5, wherein ω.sup.−1=(ω.sub.1×(1+α×ω.sub.2×ω.sub.3)).sup.−1=ω.sub.3×(ω.sub.4+α×ω.sub.5)=ω.sub.3×ω.sub.4+α×ω.sub.3×ω.sub.5; and computing products ω.sub.3×ω.sub.4 and ω.sub.3×ω.sub.5 to obtain ω.sup.−1=Σ.sub.0≤i≤s−1θ.sub.i×δ.sup.i+α.Math.Σ.sub.i≤i≤s−1θ.sub.i+s=δ.sup.i where θ.sub.i∈GF(2).

Claims

1. A computer implemented method of performing division operations in an error correction code, comprising the steps of: receiving an output ω of an error correction code (ECC) algorithm, wherein ω∈F*=F\{0} wherein F=GF(2.sup.r) be a Galois field of 2.sup.r elements, r=2s, r and s are integers, ω=Σ.sub.0≤i≤r−1β.sub.i×α.sup.i wherein α is a fixed primitive element of F, and β.sub.i∈GF(2), wherein K=GF(2.sup.s) is a subfield of F, and {1, α} is a basis of F in a linear subspace of K; choosing a primitive element δ∈K, wherein ω=ω.sub.1+α×ω.sub.2, ω.sub.1=Σ.sub.0≤i≤s−1γ.sub.i×δ.sup.i∈K, ω.sub.2=Σ.sub.0≤i≤s−1γ.sub.i+s×δ.sup.i∈K, and γ=[γ.sub.0, . . . , γ.sub.r−1].sup.T∈GF(2).sup.2; accessing a first table with ω.sub.1 to obtain ω.sub.3=ω.sub.1.sup.−1 where ω.sub.3∈K, and computing ω.sub.2×ω.sub.3 in field K, when ω.sub.1≠0; accessing a second table with ω.sub.2=ω.sub.3 to obtain (1+α×ω.sub.2×ω.sub.3).sup.−1=ω.sub.4+α×ω.sub.5, where ω.sub.4, ω.sub.5∈K, and wherein ω.sup.−1=(ω.sub.1×(1+α×ω.sub.2×ω.sub.3)).sup.−1=ω.sub.3×(ω.sub.4+α×ω.sub.5)=ω.sub.3×ω.sub.4+α×ω.sub.3×ω.sub.5; and computing products ω.sub.3×ω.sub.4 and ω.sub.3×ω.sub.5 in field K to obtain ω.sup.−1=Σ.sub.0≤i≤s−1θ.sub.i×δ.sup.i+α.Math.Σ.sub.i≤i≤s−1θ.sub.i+s=δ.sup.i where θ.sub.i∈GF(2).

2. The method of claim 1, wherein α is of minimal hamming weight.

3. The method of claim 1, wherein β is of minimal hamming weight.

4. The method of claim 1, further comprising computing a linear transformation A that transform every β=[β.sub.0, . . . , β.sub.r−1].sup.T of GF(2).sup.r to γ=A×β=[γ.sub.0, . . . , γ.sub.r−1].sup.T of GF(2).sup.r wherein:
β*=Σ.sub.0≤i≤s−1γ.sub.i×δ.sup.i+α.Math.Σ.sub.0≤i≤s−1γ.sub.i+s×δ.sup.i=Σ.sub.0≤i≤r−1β.sub.i×α.sup.i, wherein ω=ω.sub.1+α×ω.sub.2, ω.sub.1=Σ.sub.0≤i≤s−1γ.sub.i×δ.sup.i∈K and ω.sub.2=Σ.sub.0≤i≤s−1γ.sub.i+s×δ.sup.i∈K; and applying an inverse linear transformation A.sup.−1 on θ=[θ.sub.0, . . . , θ.sub.r−1].sup.T wherein λ=A.sup.−1×θ=[λ.sub.0, . . . , λ.sub.r−1].sup.T∈GF(2).sup.r and ω.sup.−1=Σ.sub.0≤i≤r−1λ.sub.i×α.sup.i.

5. The method of claim 4, wherein the linear transformation A is computed offline.

6. The method of claim 1, wherein the first table T.sub.1 is
T.sub.1={(β,γ):β=(β.sub.0, . . . ,β.sub.s−1)∈V,γ=(γ.sub.0, . . . ,γ.sub.s−1)∈V:Σ.sub.0≤i≤s−1γ.sub.i×δ.sup.i=(Σ.sub.0≤i≤s−1β.sub.i×δ.sup.i).sup.−1}, wherein V=GF(2).sup.s, W=GF(2).sup.r and β is an index of an entry that contains γ, wherein a size of the first table is s×2.sup.s.

7. The method of claim 1, wherein the second table T.sub.2 is
T.sub.2={(β,γ):β=(β.sub.0, . . . ,β.sub.s−1)∈V,γ=(γ.sub.0, . . . ,γ.sub.r−1)∈W: Σ.sub.0≤i≤s−1γ.sub.i×δ.sup.i+α.Math.Σ.sub.0≤i≤s−1γ.sub.i+s×δ.sup.i=(1+α.Math.Σ.sub.0≤i≤s−1β.sub.i×δ.sup.i).sup.−1}, wherein V=GF(2).sup.s, W=GF(2).sup.r and β is an index of an entry that contains γ, wherein a size of the second table is r×2.sup.s.

8. The method of claim 1, further comprising, when ω.sub.1=0, accessing the first table with ω.sub.2=Σ.sub.0≤i≤s−1γ.sub.i+s×δ.sup.i to obtain θ=(θ.sub.0, . . . , θ.sub.s−1)∈V such that ω.sub.2.sup.−1=Σ.sub.0.Math.i≤s−1θ.sub.i×δ.sup.i; and calculating ω.sup.−1 from β.Math.α.sup.−1=Σ.sub.0≤i≤r−1β.sub.i.Math.α.sup.i−1=Σ.sub.1≤i≤r−1β.sub.i.Math.α.sup.i−1+β.sub.0.Math.Σ.sub.0≤i≤r−1a.sub.i+1.Math.α.sup.i wherein ω.sup.1=α.sup.−1×ω.sub.2.sup.−1, wherein a.sub.i's are coefficients of a minimal polynomial of α with a minimal Hamming weight, and β is an arbitrary element of F*F\{0}.

9. A computer implemented method of performing log operations in an error correction code, comprising the steps of: receiving an output ω of an error correction code (ECC) algorithm, wherein ω∈F*=F\{0} wherein F=GF(2.sup.r) be a Galois field of 2.sup.r elements, r=2s, r and s are integers, ω=Σ.sub.0≤i≤r−1β.sub.i×α.sup.i wherein α is a fixed primitive element of F, and β.sub.i∈GF(2), wherein K=GF(2.sup.s) is a subfield of F, and {1, α} is a basis of F in a linear subspace of K; choosing a primitive element δ∈K, wherein ω=ω.sub.1+α×ω.sub.2, ω.sub.1=Σ.sub.0≤i≤s−1γ.sub.i×δ.sup.i∈K, ω.sub.2=Σ.sub.0≤i≤s−1γ.sub.i+s×δ.sup.i∈K, and γ=[γ.sub.0, . . . , γ.sub.r−1].sup.T∈GF(2).sup.2; accessing a first table with ω.sub.1 to obtain ω.sub.3=ω.sub.1.sup.−1 where ω.sub.3∈K, and computing ω.sub.2×ω.sub.3 in field K, when ω.sub.1≠0; accessing a third table with ω.sub.1 to obtain log(ω.sub.1); accessing a fourth table with with 1+α×ω.sub.2×ω.sub.3 to obtain log(1+α×ω.sub.2×ω.sub.3); and computing log(ω)=log(ω.sub.1×(1+α×ω.sub.2×ω.sub.1.sup.−1))=mod(q−1, log(ω.sub.1)+log(1+α×ω.sub.2×ω.sub.1.sup.−1)).

10. The method of claim 9, wherein α is of minimal hamming weight.

11. The method of claim 9, wherein β is of minimal hamming weight.

12. The method of claim 9, further comprising computing a linear transformation A that transform every β=[β.sub.0, . . . , β.sub.r−1].sup.T of GF(2).sup.r to γ=A×β=[γ.sub.0, . . . , γ.sub.r−1].sup.T of GF(2).sup.r wherein:
β*=Σ.sub.0≤i≤s−1γ.sub.i×δ.sup.i+α.Math.Σ.sub.0≤i≤s−1γ.sub.i+s×δ.sup.i=Σ.sub.0≤i≤r−1β.sub.i×α.sup.i, wherein ω=ω.sub.1+α×ω.sub.2, ω.sub.1=Σ.sub.0≤i≤s−1γ.sub.i×δ.sup.i∈K and ω.sub.2=Σ.sub.0≤i≤s−1γ.sub.i+s×δ.sup.i∈K.

13. The method of claim 9, wherein the third table T.sub.3 is
T.sub.3={(β,j):β=(β.sub.0, . . . ,β.sub.s−1)∈V,0≤j≤q−2:j=log(Σ.sub.0≤i≤s−1β.sub.i×δ.sup.i)}, wherein V=GF(2).sup.s, and β is an index of an entry that contains j, wherein a size of the third table is r×2.sup.s.

14. The method of claim 9, wherein the fourth table T.sub.3 is
T.sub.4={(β,j):β=(β.sub.0, . . . ,β.sub.s−1)∈V,0≤j≤q−2:j=log(1+α.Math.Σ.sub.0≤i≤s−1β.sub.i×δ.sup.i)}, wherein V=GF(2).sup.s, and β is an index of an entry that contains j, wherein a size of the fourth table is r×2.sup.s.

15. The method of claim 9, further comprising, when ω.sub.1=0, wherein ω=α×ω.sub.2; accessing the third table with ω.sub.2 to obtain j=log(ω.sub.2); calculating log(ω)=log(α×ω.sub.2)=mod(q−1, 1+j), wherein log(α)=1.

16. A computer implemented method of performing division and log operations in an error correction code, comprising the steps of: receiving an output ω of an error correction code (ECC) algorithm, wherein ω∈F* wherein F=GF(2.sup.r) be a Galois field of 2.sup.r elements, r is an integer, ω=Σ.sub.0≤i≤r−1β.sub.i×α.sup.i wherein α is a primitive element of F and β.sub.i∈GF(2); when μ(β)=0, wherein μ(β)=min{0≤i≤r−1: β.sub.i=1}, reading 1/β from a first table and reading log(β) from a second table.

17. The method of claim 16, wherein the first table is T′.sub.1={1/β: β∈F* and μ(β)=0}, wherein a size of the first table is |F|/2.

18. The method of claim 16, wherein the second table T′.sub.2 is T′.sub.2={log(β): β∈F*} and μ(β)=0, wherein a size of the second table is |F|/2.

19. The method of claim 16, wherein when μ(β)=s≥1, further comprising reading 1/γ from the first table, wherein γ=β/α.sup.s; computing 1/β from 1/β=γ.Math.α.sup.−s, and computing.Math.α.sup.−1 from β.Math.α.sup.−1=Σ.sub.0≤i≤r−1β.sub.i.Math.α.sup.i−1=Σ.sub.1.Math.i≤r−1β.sub.i.Math.α.sup.i+1+β.sub.0.Math.Σ.sub.0≤i≤r−1a.sub.i+1.Math.α.sup.i wherein ω.sup.−1=α.sup.−1×ω.sub.2.sup.−1, wherein a.sub.i's are coefficients of a minimal polynomial of α with a minimal Hamming weight, and β is an arbitrary element of F*=F\{0}.

20. The method of claim 16, wherein when μ(β)=s≥1, further comprising reading log(γ) from the second table, wherein γ=β/α.sup.s and calculating log(β)=mod(q−1, s+log(γ)).

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0026] FIG. 1 is a flowchart of an algorithm according to an embodiment for performing division and log operations.

[0027] FIG. 2 is a flowchart of an algorithm according to another embodiment for performing division and log operations.

[0028] FIG. 3(A) illustrates an ASIC that implements an error correction code with prior art LUTS for the log and inversion operations, and FIGS. 3(B) and 3(C) illustrate an ASIC that implements an error correction algorithm as modified to implement a method for performing division and log operations with a few small tables, according to an embodiment of the disclosure.

[0029] FIG. 4 is a block diagram of a computer system that implements a method for performing division and log operations with a few small tables, according to an embodiment of the disclosure.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

[0030] Exemplary embodiments of the disclosure as described herein generally provide systems and methods for performing division and log operations with a few small tables. While embodiments are susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that there is no intent to limit the disclosure to the particular forms disclosed, but on the contrary, the disclosure is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the disclosure.

[0031] According to an embodiment, a discrete inverse and log operation can be computed with the aid of relatively small tables and relatively small computational complexity, wherein the overall cost of these operation is considerably reduced, in comparison to current practice. According to one embodiment, the overall size of the tables is 3.5×|F|.sup.1/2, with a moderate increase of computational complexity per operation. In another embodiment, the overall size of the tables is |F|=2.sup.r with little added computational complexity. Here F is the associated finite field. In current practice of algebraic ECC implementation, the overall size of both tables is 2.Math.|F|. Operations according to embodiments of the disclosure are suitable for low-power 6-bit cell or mobile ECCs.

[0032] Embodiments of the present disclosure provide smaller tables for the inverse and log operations at the cost of increased arithmetic complexity per operation. One embodiment is for even r. In this case the overall tables' size is 3.5×r×2.sup.r/2 bits as opposed to 2×r×2.sup.r in current practice. The resulting computational complexity cost of a single division or a single log operation is not much greater than the complexity of single product operation in the field. Denote by n the code length and by t the number of error after going through the channel. In RS and BCH, there are O(n.sup.2) products and O(t) divisions and log operations. In another embodiment, the tables for the inverse and log are each of half the field size, when there are near zero computations. In this embodiment the computational complexity is relatively negligible. This embodiment is suitable for every r.

[0033] FIG. 3(A) illustrates an ASIC that implements an error correction code with prior art LUTS for the log and inversion operations, and FIGS. 3(B) and 3(C) illustrate an ASIC that implements an error correction algorithm as modified to implement a method for performing division and log operations with a few small tables, according to an embodiment of the disclosure. Referring to FIG. 3(A), error correction code (ECC) ASIC 300 receives a message, performs error correction, accesses tables 301 and 302 for respectively performing log and division operations, and outputs a decoded message. The size of each table is r×2.sup.T. Referring to FIG. 3(B), error correction code (ECC) ASIC 310 receives a message, performs error correction, and outputs a decoded message. Additional logic 311 performs the log and division operations, and accesses tables T1, T2, T3 and T4 while performing the log and division operations. The size of tables T1, T2, T3 and T4 are, respectively, s2.sup.s, r2.sup.s, r2.sup.s, and r2.sup.s, where r=2s. Tables T1, T2, T3 and T4 will be defined below. Referring to FIG. 3(C), error correction code (ECC) ASIC 320 receives a message, performs error correction, and outputs a decoded message. Additional logic 321 performs the log and division operations, and accesses tables T1′ and T2′ while performing the log and division operations. The size of tables T1′ and T2′ are, respectively, 2.sup.r and 2.sup.r. Tables T1′ and T2′ will be defined below.

First Embodiment

[0034] Suppose that, r=2×s, for positive integer s. Let F=GF(2.sup.r), and α∈F be a primitive element of minimal Hamming weight, where the Hamming weight is the number of one's in the bit representation of α. That is,

p(x)=Σ.sub.0≤i≤r−1a.sub.i×α.sup.i,a.sub.i∈GF(2),  (1)

is the minimal polynomial of a with minimal hamming weight,
Note that by EQ. (1):

α.sup.r=Σ.sub.0≤i≤r−1a.sub.i×α.sup.i and also α.sup.−1Σ.sub.0≤i≤r−1+1a.sub.i×α.sup.i.

[0035] Let r′=ham(p(x))−1. It appears that r′=2 would be available in many real world applications. Note that a.sub.0=a.sub.r=1. Then there are r′ nonzero coefficients in the right side of both equations. The fact that this is typically a small number enables us to achieve further complexity reduction. Take now an arbitrary element β∈F*=F\{0} and consider its binary representation with respect to the basis of F over GF(2), {1, α, . . . , α.sup.r−1}:

β=Σ.sub.0≤i≤r−1β.sub.i.Math.α.sup.i

where β.sub.i∈GF(2). Define ham.sub.α(β)=ham(β.sub.0, . . . , β.sub.r−1). Note that

β.Math.α=Σ.sub.0≤i≤r−1β.sub.i.Math.a.sup.i+1=Σ.sub.0≤i≤r−2β.sub.i.Math.α.sup.i+1+β.sub.r−1Σ.sub.0≤i≤r−1a.sub.i.Math.α.sup.i.  (2)

Thus a cyclic shift and r′ GF(2) additions are required for the computation of β−α, when β.sub.r−1=1 and when β.sub.r−1=0, for half the fields elements, there are no additions.

[0036] Similarly

β.Math.α.sup.−1=Σ.sub.0≤i≤r−1β.sub.i.Math.α.sup.i−1=Σ.sub.1≤i≤r−1β.sub.i.Math.α.sup.i−1+β.sub.0.Math.Σ.sub.0≤i≤r−1a.sub.i+1.Math.β.sup.i.  (3)

Hence, here too, a cyclic shift and r′ GF(2) additions are required for the computation of β.Math.β.sup.−1, when β.sub.0=1 and when β.sub.0=0, for half the fields elements, there are no additions.

[0037] For each β∈F*, define log(β)=j to be the unique integer in {0, . . . , q−2} such that α.sup.i=β. A following scheme according to an embodiment proposes reduced size LUTs for inverse and log operations at the cost of increased computational complexity per each inverse or log operation. It embodies a profitable tradeoff of computational complexity vs. hardware.

[0038] With the reduced tables according to an embodiment, the complexity cost of a single division or single log operation does not greatly exceed the complexity of single product operation in the field F. In RS and BCH, there are O(n.sup.2) products and O(t) divisions and log operations, where t is the number of errors caused by the channel. The overall tables' size according to an embodiment is 3.5×2.sup.s F-symbols as oppose to 2.sup.r+1 in current practice. Consider the field K=GF(2.sup.s) as a subfield of F. Note that [F:K]=2, i.e., |F|=2|K|, and that {1, α} is a basis of F over K.

[0039] Let δΣK be a primitive element of minimal hamming weight. Then, according to an embodiment, an arbitrary element τ of K can be written with the representation:

τ=Σ.sub.0≤i≤s−1τ.sub.i×δ.sup.i,τ.sub.i∈GF(2).  (4)

Given this representation, note that the product of two elements from K has ¼ of the complexity of a product in F, and is far easier to implement.

[0040] According to an embodiment, an element β* in F can be written uniquely by:

β*=Σ.sub.0≤i≤r−1β.sub.i×α.sup.i,β.sub.i∈GF(2),  (5)

where r=2×s, as defined above. That is, β* is represented by the basis {α.sup.i: 0≤i≤r−1} of F as a linear space over GF(2).

[0041] Alternatively, according to an embodiment, similar to EQS. (2) and (3), above, β* can be written uniquely in the form:

β*=Σ.sub.0≤i≤s−1γ.sub.i×δ.sup.i+α.Math.Σ.sub.0≤i≤s−1γ.sub.i+s×δ.sup.i,γ.sub.i∈GF(2).  (6)

That is, β* is represented by the basis {δ.sup.i, α×δ.sup.i:0≤i≤s−1} of F as a linear space over GF(2). Note that the first term on the right hand size is purely in the field K, while the second term is α multiplied by an element in field K.

[0042] Hence, there is an invertible linear transformation over GF(2) that takes β=[β.sub.0, . . . , β.sub.r−1].sup.T to γ=[γ.sub.0, . . . , γ.sub.r−1].sup.T, when EQS. (2) and (3) hold. This linear transformation can be represented by an r×r matrix A∈GF(2).sup.r×r such that A×β=γ. According to an embodiment, matrices A and B=A.sup.−1 are stored in permanent memory, allocating for this purpose 2×r.sup.2 bits. Note that the matrices are easy to compute, can be precomputed offline and stored in memory, and require relatively little storage as compared to the inverse and log tables that will be introduced below.

[0043] According to an embodiment, let V=GF(2).sup.s and W=GF(2).sup.r. In addition to A and B, the tables stored in memory include the following LUTs: {T.sub.i}.sub.1≤i≤4. The LUTs are structured so that β is the input and γ or j are the output. According to an embodiment, β is not stored explicitly, but is rather the index of the entry that contains γ or j, and is written in the form: (β,γ) or (β,j).

T.sub.1={(β,γ):β=(β.sub.0, . . . ,β.sub.s−1)∈V,γ=(γ.sub.0, . . . ,γ.sub.s−1)∈V:Σ.sub.0≤i≤s−1γ.sub.i×δ.sup.i=(Σ.sub.0≤i≤s−1β.sub.i×δ.sup.i).sup.−1},

T.sub.2={(β,γ):β=(β.sub.0, . . . ,β.sub.s−1)∈V,γ=(γ.sub.0, . . . ,γ.sub.r−1)∈W: Σ.sub.0≤i≤s−1γ.sub.i×δ.sup.i+α.Math.Σ.sub.0≤i≤s−1γ.sub.i+s×δ.sup.i=(1+α.Math.Σ.sub.0≤i≤s−1β.sub.i×δ.sup.i).sup.−1},

T.sub.3={(β,j):β=(β.sub.0, . . . ,β.sub.s−1)∈V,0≤j≤q−2:j=log(Σ.sub.0≤i≤s−1β.sub.i×δ.sup.i)},

T.sub.4={(β,j):β=(β.sub.0, . . . ,β.sub.s−1)∈V,0≤j≤q−2:j=log(1+α.Math.Σ.sub.0≤i≤s−1β.sub.i×δ.sup.i)}.

For a table T, denote by |T| the number of bits in T. It holds that |T.sub.1|=s×2.sup.s, |T.sub.2|=|T.sub.3|=|T.sub.4|=r×2.sup.s.

Preliminary Steps:

[0044] FIG. 1 is a flowchart of an algorithm according to an embodiment for performing division and log operations. Referring to the figure, the input of the following procedure, which is an output of an ECC algorithm, received at step 110, is an arbitrary ω∈F*, which is given by a standard representation of F:

[0045] In the following exposition, ω.sub.u, 1≤i≤5, is a notation for an element in the small field K. All standard arithmetic operations can be performed in K. A first step 112, according to an embodiment, is to apply the linear transformation A to β=[β.sub.0, . . . , β.sub.r−1].sup.T. The result is γ=[γ.sub.0, . . . , γ.sub.r−1].sup.T, such that, γ=A×β, which implies:

ω=ω.sub.1+α×ω.sup.2,  (7)

which follows from EQ. (6), above, where ω.sub.1=Σ.sub.0≤i≤s−1γ.sub.i×δ.sup.i∈K and ω.sub.2=Σ.sub.0≤i≤s−1γ.sub.i+s×δ.sup.i∈K.

[0046] At step 114, test for whether ω.sub.1≠0. If ω.sub.1≠0, then, at step 116, by accessing the table T.sub.1, a procedure according to an embodiment finds ω.sub.3=ω.sub.1.sup.−1 where ω.sub.3∈K is given by EQ. (1). The procedure then computes the product of ω.sub.2×ω.sub.3 in the small field K, based on the representation of EQ. (1). Note that

ω=ω.sub.1×(1+α=ω.sub.2×ω.sub.3).  (8)

Inversion Computation:

[0047] According to an embodiment, a next step 118 is to access T.sub.2 to find the inverse of 1+α×ω.sub.2×ω.sub.1.sup.−1 written by:

ω.sub.4+α×ω.sub.5=(1+αω.sub.2×ω.sub.3).sup.−1,

where ω.sub.2×ω.sub.3∈K and ω.sub.4, ω.sub.5∈K are given by EQ. (1). Observe that:

ω.sup.−1=(ω.sub.1×(1+α×(ω.sub.2×ω.sub.3)).sup.−1=ω.sub.3×(ω.sub.4+α×ω.sub.5)=ω.sub.3×ω.sub.4+α×ω.sub.3×ω.sub.5.

At step 120, an inversion procedure according to an embodiment computes the products ω.sub.3×ω.sub.4 and ω.sub.3×ω.sub.5 in the small field K. Thus of ω.sup.−1 has been found in the form of EQ. (3):

ω.sup.−1=Σ.sub.0≤i≤s−1θ.sub.i×δ.sup.i+α.Math.Σ.sub.i≤i≤s−1θ.sub.i+s=δ.sup.i,θ.sub.i∈GF(2).

[0048] Applying the linear transformation B on θ=[θ.sub.0, . . . , θ.sub.r−1].sup.T at step 122, a result λ=[λ.sub.0, . . . , λ.sub.r−1].sup.T∈GF(2).sup.r is obtained, such that, λ=B×θ and hence:

ω.sup.−1=Σ.sub.0≤i≤r−1λ.sub.i×α.sup.i.

[0049] The overall complexity of this inversion procedure is 2 products of a fixed r×r-bit-matrix by r-bit-vectors and 2 table reads and 3 products in the small field K.

[0050] According to an embodiment, if, at step 114, ω.sub.1=0, then ω=α×ω.sub.2, and hence ω.sup.−1=α.sup.−1×ω.sub.2.sup.−1. Recall that EQ. (7) provides the following representation for ω.sub.2:

ω.sub.2=Σ.sub.0≤i≤s−1γ.sub.i+s×δ.sup.i.

[0051] At step 130, accessing table T, yields θ=(θ.sub.0, . . . , θ.sub.s−1)∈V such that

ω.sub.2.sup.−1Σ.sub.0≤i≤s−1θ.sub.i×δ.sup.i.

[0052] Next, at step 132, α.sup.−1 can be calculated from EQ. (3):β.Math.α.sup.−1=Σ.sub.0≤i≤r−1β.sub.i.Math.α.sup.i−1=Σ.sub.1≤i≤r−1β.sub.i.Math.α.sup.i−1+β.sub.0.Math.Σ.sub.0≤i≤r−1a.sub.i+1.Math.α.sup.i, so that ω.sup.1=α.sup.−1×ω.sub.2.sup.−1.

Log Computation:

[0053] Suppose again that EQ. (4) is computed so that {ω.sub.i}.sub.1≤i≤3 is already computed wherein ω.sub.3=ω.sub.1.sup.311 and ω.sub.2×ω.sub.3 is computed, and ω=ω.sub.1×(1+α×ω.sub.2×ω.sub.3). A log algorithm according to an embodiment proceeds by transitioning to step 124 after step 116, instead of transitioning to step 118. At step 124, table T.sub.3 is accessed to find log(ω.sub.1) and table T.sub.4 is accessed at step 126 to find log(1+α×ω.sub.2×ω.sub.3). Finally, at step 128, the log of w is found by computing

log(ω)=log(ω.sub.1×(1+α×ω.sub.2×ω.sub.1.sup.−1))=mod(q−1,log(ω.sub.1)+log(1+α×ω.sub.2×ω.sub.1.sup.−1)),

where the mod(q−1, *) reflects the q−1 non-zero elements in the field.

[0054] According to an embodiment, if, at step 114, ω.sub.1=0, then ω=α×ω.sub.2, and a simplified version of the above can be performed. In particular, at step 134, table T.sub.3 can be accessed to find ω.sub.3=log(ω.sub.2), after which a procedure according to an embodiment jumps to step 128 to compute log(ω)=log(α×ω.sub.2)=mod(q−1, 1+ω.sub.3), where log(α)=1

Alternative Embodiment

[0055] Embodiments of the disclosure also provide a scheme for inverse and log operations with tables of half the field size and very small computational cost per log or inverse operation. These operations are suitable for any finite field of characteristic 2, i.e., a finite field GF(2.sup.r).

[0056] FIG. 2 is a flowchart of an algorithm according to another embodiment for performing division and log operations. According to an embodiment, let F=GF(2.sup.r), and a be a fixed root of a primitive polynomial of degree r, p(x)=Σ.sub.0≤i≤ra.sub.i×x.sup.i, a.sub.i∈GF(2), whose hamming weight is minimal. Let r′=ham(p(x))−1, the number of 1-bits. This number should be as small as possible. Referring to the figure, the input of the following procedure, which is an output of an ECC algorithm, received at step 210, is β∈F* and consider the standard binary representation:

β=Σ.sub.0≤i≤r−1β.sub.i×α.sup.i,β.sub.i∈GF(2).

[0057] Define

μ(β)=min{0≤i≤r−1: β.sub.i=1},

which is the index of the first 1-bit in β.

[0058] According to an embodiment, the following table is stored:

T′.sub.1={1/β:β∈F* and μ(β)=0}

which is the first bit in β.

[0059] Since the first bit of β is 1, i.e., β.sub.0=1, the size of the table is reduced by 2, so it holds that: |T′.sub.1|=|F|/2. Noting that when β.sub.0=1, the address of 1/β on the table is given by (β.sub.1, . . . , β.sub.r−1). Let β∈F*. If, at step 212, μ(β)=0, then 1/β can be read from T.sub.1 at step 224, and hence in this case no is computations are needed. Otherwise, μ(β)=s≥1. Let γ=β/α.sup.s∈T′.sub.1 and note that μ(γ)=0. Thus 1/γ is in T′.sub.1. Now, β=α.sup.−s×γ.sup.−1 and hence, 1/γ can be read from T.sub.1 at step 216.

[0060] Note that a repetitive application of EQ. (2) provides a computation of the scalars {β.Math.α.sup.i}.sub.1≤i≤N where N≥1 with at most N.Math.r′ GF(2) additions and an average over all β∈F of N.Math.r′/2 additions. Likewise it follows from EQ. (3) that the scalars {β.Math.α.sup.−i}.sub.i≤i≤N can be computed with at most N.Math.r′ GF(2) additions and an average over all β∈F of N.Math.r′/2 additions. Thus, 1/β can be computed at step 218, with s×r′/2 XORs, in a straightforward manner, applying the aforementioned recursion. Noting that for r>s≥0, Pr(μ(β)=s)<2.sup.−(s+1), it holds that that on average there are fewer than r′/2 XORs to find 1/β for random β∈F*.

[0061] Similarly, for the log operation, the following table is stored:

T′.sub.2={log(β):β∈F* and μ(β)=0}.

Similar to T′.sub.1, it then holds that |T′.sub.2|=|F|/2. Let β∈F*. If μ(β)=0 at step 212, log(β) can be read from T′.sub.2 at step 220. Otherwise, μ(β)=s≥1. Then, γ=β/α.sup.s∈T′.sub.2 and hence log(γ) can be read from T′.sub.2 at step 222, from which the log(β) can be calculated at step 224:

log(β)=mod(q−1,s+log(γ)).

Observe that log(β)=log(γ)+s, when log(γ)+s≤q−2 and log(β)=log(γ)+s−(q−2) when log(γ)+s>q−2.

System Implementations

[0062] It is to be understood that embodiments of the present disclosure can be implemented in various forms of hardware, software, firmware, special purpose processes, or a combination thereof. In one embodiment, the present disclosure can be implemented in hardware as an application-specific integrated circuit (ASIC), or as a field programmable gate array (FPGA). In another embodiment, the present disclosure can be implemented in software as an application program tangible embodied on a computer readable program storage device. The application program can be uploaded to, and executed by, a machine comprising any suitable architecture.

[0063] FIG. 4 is a block diagram of a system for performing division and log operations with a few small tables, according to an embodiment of the disclosure. Referring now to FIG. 4, a computer system 41 for implementing the present invention can comprise, inter alia, a central processing unit (CPU) or controller 42, a memory 43 and an input/output (I/O) interface 44. The computer system 41 is generally coupled through the I/O interface 44 to a display 45 and various input devices 46 such as a mouse and a keyboard. The support circuits can include circuits such as cache, power supplies, clock circuits, and a communication bus. The memory 43 can include random access memory (RAM), read only memory (ROM), disk drive, tape drive, etc., or a combinations thereof. The present disclosure can be implemented as a routine 47 that is stored in memory 43 and executed by the CPU or controller 42 to process the signal from the signal source 48. As such, the computer system 41 is a general purpose computer system that becomes a specific purpose computer system when executing the routine 47 of the present invention. Alternatively, as described above, embodiments of the present disclosure can be implemented as an ASIC or FPGA 47 that is in signal communication with the CPU or controller 42 to process the signal from the signal source 48.

[0064] The computer system 41 also includes an operating system and micro instruction code. The various processes and functions described herein can either be part of the micro instruction code or part of the application program (or combination thereof) which is executed via the operating system. In addition, various other peripheral devices can be connected to the computer platform such as an additional data storage device and a printing device.

[0065] It is to be further understood that, because some of the constituent system components and method steps depicted in the accompanying figures can be implemented in software, the actual connections between the systems components (or the process steps) may differ depending upon the manner in which the present invention is programmed. Given the teachings of the present invention provided herein, one of ordinary skill in the related art will be able to contemplate these and similar implementations or configurations of the present invention.

[0066] While the present invention has been described in detail with reference to exemplary embodiments, those skilled in the art will appreciate that various modifications and substitutions can be made thereto without departing from the spirit and scope of the invention as set forth in the appended claims.