Cubic root of a galois field element

Patent metadata

Field	Value
Publication number	US-9804828-B2
Application number	US-201414551110-A
Country	US
Kind code	B2
Filing date	Nov 24, 2014
Priority date	Nov 24, 2014
Publication date	Oct 31, 2017
Grant date	Oct 31, 2017

Abstract

A method includes receiving a first element of a Galois Field of order q m , where q is a prime number and m is a positive integer. The first element is raised to a predetermined power so as to form a second element z, wherein the predetermined power is a function of q m and an integer p, where p is a prime number which divides q m −1. The second element z is raised to a p th power to form a third element. If the third element equals the first element, the second element multiplied by a p th root of unity raised to a respective power selected from a set of integers between 0 and p−1 is output as at least one root of the first element.

First claim

The invention claimed is:

1. A method, comprising:
receiving, by at least one processor of a circuit, a corrupted code word of an error correction code;
determining a degree-three polynomial from the received corrupted code word;
determining for the degree-three polynomial, a corresponding first element of a Galois Field of order q m , where q is a prime number and m is a positive integer;
raising, by the at least one processor, the first element to a predetermined power so as to form a second element z, wherein the predetermined power is a function of q m and an integer p, where p is another prime number which divides q m −1;
raising, by the at least one processor, z to a p th power to form a third element;
when the third element equals the first element, outputting, by the at least one processor, as at least one root of the first element the second element multiplied by a p th root of unity raised to a respective power selected from a set of integers between 0 and p−1;
identifying locations of errors in the received corrupted code word from the outputted at least one root;
correcting the corrupted code word at the identified locations; and
outputting the corrected code word.

2. The method according to claim 1 , wherein m is an even integer, q=2, and p=3, so that the at least one root of the first element comprises cube roots thereof.

3. The method according to claim 2 , and comprising determining that an order of a group associated with the Galois Field is not divisible by 9.

4. The method according to claim 2 , wherein the predetermined power is selected from one of

2
m

-
1

3

+
1

3

⁢

⁢
and
⁢

⁢

⁢

2
⁢

(

2
m

-
1

3

)

+
1

3

.

5. The method according to claim 2 , wherein m=10, and wherein the predetermined power is 114.

6. The method according to claim 2 , and comprising determining that an order of a group associated with the Galois Field is divisible by 9 and not by 27.

7. The method according to claim 2 , wherein the predetermined power is selected from one of

2
m

-
1

9

+
1

3

⁢

⁢
and
⁢

⁢

⁢

2
⁢

(

2
m

-
1

9

)

+
1

3

.

8. The method according to claim 2 , wherein m=12, and wherein the predetermined power is 152.

9. The method according to claim 2 , wherein an order of a group associated with the Galois Field is divisible by 9, and comprising, when the third element equals the first element multiplied by the cube root of unity, forming, by the at least one processor, a fourth element as the second element divided by a cube root of the cube root of unity, and outputting as cube roots of the first element the fourth element, the fourth element multiplied by the cube root of unity, and the fourth element multiplied by the cube root of unity squared.

10. The method according to claim 2 , wherein an order of a group associated with the Galois Field is divisible by 9, and comprising, when the third element equals the first element multiplied by the cube root of unity squared, forming, by the at least one processor, a fourth element as the second element divided by a cube root squared of the cube root of unity, and outputting as cube roots of the first element the fourth element, the fourth element multiplied by the cube root of unity, and the fourth element multiplied by the cube root of unity squared.

11. An apparatus, comprising:
a decoder configured to receive code words including a corrupted code word, to determine a degree-three polynomial from the received corrupted code word and to determine a corresponding first element of a Galois Field of order q m , where q is a prime number and m is a positive integer, to raise the first element to a predetermined power so as to form a second element z, wherein the predetermined power is a function of q m and an integer p, where p is another prime number which divides q m −1,
to raise z to a p th power to form a third element,
to compare the first and the third elements,
in response to determining that the third element equals the first element, to output as at least one root of the first element the second element multiplied by a p th root of unity raised to a respective power selected from a set of integers between 0 and p−1, to identify locations of errors in the received corrupted code word from the outputted at least one root, and to correct the corrupted code word at the identified locations; and
an output configured to output the corrected code word.

12. The apparatus according to claim 11 , wherein m is an even integer, q=2, and p=3, so that the at least one root of the first element comprises cube roots thereof.

13. The apparatus according to claim 12 , and comprising a divisible by 9 set of components configured to determine that an order of a group associated with the Galois Field is not divisible by 9.

14. Th

Assignees

• Apple Inc

Inventors

• Anholt Micha
• Teitel Moti

Classifications

• G06F7/552

  Powers or roots {, e.g. Pythagorean sums} · CPC title

• G06F7/5525

  Roots or inverse roots of single operands · CPC title

• G06F7/724 Primary

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

• G06F2207/5526

  Roots or inverse roots of single operands · CPC title