Low-power error correction code computation in GF (2R)

Patent metadata

Field	Value
Publication number	US-11438013-B2
Application number	US-202016929983-A
Country	US
Kind code	B2
Filing date	Jul 15, 2020
Priority date	Jul 15, 2020
Publication date	Sep 6, 2022
Grant date	Sep 6, 2022

Abstract

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

First claim

What is claimed is:

1. A digital electronic circuit, tangibly embodying a program of instructions executed by the digital electronic circuit to perform method steps for performing division operations in an error correction code, wherein the method steps comprise:
reading a codeword from a memory device;
performing error correction on the codeword to generate a corrected codeword; and
outputting data included in the corrected codeword,
wherein performing the error correction comprises performing a predetermined operation by using a plurality of tables;
wherein performing the predetermined operation by using the plurality of tables comprises:
receiving an output ω from an error correction code (ECC) algorithm, wherein ω∈F†{0} wherein F=GF(2 r ) is a Galois field of 2 r elements, r=2s, r and s are integers, ω=Σ 0≤i≤r−1 β i ×α i wherein α is a fixed primitive element of F, and β i ∈GF(2), wherein K=GF(2 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 ω=ω 1 +α×ω 2 , ω 1 =Σ 0≤i≤s−1 γ i ×δ i ∈K, ω 2 =Σ 0≤i≤s−1 γ i+s ×δ i ∈K, and γ=[γ 0 , . . . , γ r−1 ] T ∈GF(2) r ;
accessing a first table with ω 1 to obtain ω 3 =ω 1 −1 , computing ω 2 ×ω 3 in field K, when ω 1 ≠0;
accessing a second table with ω 2 =ω 3 to obtain (1+α×ω 2 ×ω 3 ) −1 =ω 4 +α×ω 5 , wherein ω 4 , ω 5 ∈K, and wherein ω −1 =(ω 1 ×(1+α×ω 2 ×ω 3 )) −1 =ω 3 ×(ω 4 +α×ω 5 )=ω 3 ×ω 4 +α×ω 3 ×ω 5 ; and
computing products ω 3 ×ω 4 and ω 3 ×ω 5 to obtain ω −1 =Σ 0≤i≤s−1 θ i ×δ i +α·Σ i≤i≤s−1 θ i+s =δ i where θ i ∈GF(2).

2. The digital electronic circuit of claim 1 , wherein a is of minimal hamming weight.

3. The digital electronic circuit of claim 1 , wherein δ is of minimal hamming weight.

4. The digital electronic circuit of claim 1 , wherein the method steps further comprise:
computing a linear transformation A that transform β=[β 0 , . . . , β r−1 ] T of GF(2) r to γ=A×β=[γ 0 , . . . , γ r−1 ] T of GF(2) r wherein:
β*=Σ 0≤i≤s−1 γ i ×δ i +α·Σ 0≤i≤s−1 γ i+s ×δ i =Σ 0≤i≤r−1 β i ×α i ; and
applying an inverse linear transformation A −1 on θ=[θ 0 , . . . , θ r−1 ] T wherein λ=A −1 ×θ=[λ 0 , . . . , λ r−1 ] T ∈GF(2) r and ω −1 =Σ 0≤i≤r−1 λ i ×α i .

5. The digital electronic circuit of claim 4 , wherein the linear transformation A is computed offline.

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

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

8. The digital electronic circuit of claim 1 , wherein the method steps further comprise, when ω 1 =0,
accessing the first table with ω 2 =Σ 0≤r≤s−1 γ i+s ×δ i to obtain θ=(θ 0 , . . . , θ x-1 )∈V such that ω 2 −1 =Σ 0≤i≤s−1 θ i ×δ i ; and
calculating ω −1 from β·α −1 =Σ 0≤i≤r−1 β i α i−1 +β 0 ·Σ 1≤i≤γ−1 β i + i−1 +β 0 Σ 0≤i≤r−1 a i+1 ·α i wherein ω −1 =α −1 ×ω 2 −1 , wherein a 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 digital electronic circuit, tangibly embodying a program of instructions executed by the digital electronic circuit to perform method steps for performing log operations in an error correction code, wherein the method steps comprise:
reading a codeword from a memory device;
performing error correction on the codeword to generate a corrected codeword; and
outputting data included in the corrected codeword,
wherein performing the error correction comprises performing a predetermined operation by using a plurality of tables;
wherein performing the predetermined operation by using the plurality of tables comprises:
receiving an output ω from an error correction code (ECC) algorithm, wherein ω=F*=F\{0} wherein F=GF(2 r ) be a Galois field of 2 r elements, r=2s, r and s are integers, ω=Σ 0≤i≤r−1 β i ×α i wherein α is a fixed primitive element of F, and β i ∈GF(2), wherein K=GF(2 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 ω=ω 1 +α×ω 2 , ω 1 =Σ 0≤i≤s− γ i ×δ i ∈K, ω 2 =Σ 0≤i≤s−1 γ i+s ×δ i ∈K, and γ=[γ 0 , . . . , γ r−1 ] T ∈GF(2) r ;
accessing a first table with ω 1 to obtain ω 3 =ω 1 −1 where ω=ω 1 +αω 2 , ω 1 =Σ 0≤i≤s−1 γ i ×δ i ∈K, and computing ω 2 ×ω 3 in field K, when ω 1 ≠0;
accessing a third table with ω 1 to obtain log(ω 1 );
accessing a fourth table with 1+α×ω 2 ×ω 3 to obtain log(1+α×ω 2 ×ω 3 ); and
computing log(ω)=log(ω 1 ×(1+α×ω 2 ×ω 1 −1 ))=mod(q−1, log(ω 1 )+log(1+α×ω 2 ×ω 1 −1 )).

10. The digital electronic circuit of claim 9 , wherein α is of minimal hamming weight.

11. The digital electronic circuit of claim 9 , wherein δ is of minimal hamming weight.

12. The digital electronic circuit of claim 9 , wherein the method steps further comprise
computing a linear transformation A that transform β=[β 0 , . . . , β r−1 ] T of GF (2) r to γ=A×β=[γ 0 , . . . , γ r−1 ] T pf GF(2) r wherein:
β*=Σ 0≤i≤s−1 γ i ×δ i +α·Σ 0≤i≤s−1 γ i+s ×δ i =Σ 0≤i≤r−1 β i ×α i .

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

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

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

16. A digital electronic circuit, tangibly embodying a program of instructions executed by the digital electronic circuit to perform method steps for performing division and log operations in an error correction code, wherein the method steps comprise:
reading a codeword from a memory device;
performing error correction on the codeword to generate a corrected codeword; and
outputting data included in the corrected codeword,
wherein performing the error correction comprises performing a predetermined operation by using a plurality of tables;
wherein performing the predetermined operation by using the plurality of tables comprises:
receiving an output co from an error correction code (FCC) algorithm, wherein ω∈F* wherein F=GF(2 r ) be a Galois field of 2 r elements, r is an integer, ω=Σ 0≤i≤r−1 β i ×α i wherein α is a primitive element of F and β i ∈GF(2);
when μ(β)=0, wherein μ(β)=min {0≤i≤r−1: β i =1}, reading 1/β from a first table and reading log(β) from a second table.

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

18. The digital electronic circuit of claim 16 , wherein the second table is T′ 2 ={log(β): β∈F*} and

Assignees

• Samsung Electronics Co Ltd

Inventors

• Dor Avner
• Berman Amit
• Doubchak Ariel
• Sheffi Elik Almog
• Shany Yaron

Classifications

• H03M13/153

  using the Berlekamp-Massey algorithm · CPC title

• H03M13/6516

  Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields · CPC title

• G06F7/724

  Finite field arithmetic (for error detection or correction in general H03M13/00, in computers G06F11/10) · CPC title

• G06F7/72

  using residue arithmetic · CPC title

• G06F11/1012 Primary

  using codes or arrangements adapted for a specific type of error (G06F11/1048 takes precedence) · CPC title