Cubic root of a galois field element
AssigneeApple Inc.
InventorsMicha Anholt, Moti Teitel
Life of this patent
Estimating the term…
Abstract
A method includes receiving a first element of a Galois Field of order qm, 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 qm and an integer p, where p is a prime number which divides qm−1. The second element z is raised to a pth power to form a third element. If the third element equals the first element, the second element multiplied by a pth 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.
Claims20
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 qm, 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 qm and an integer p, where p is another prime number which divides qm−1;
- raising, by the at least one processor, z to a pth 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 pth 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.
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 qm, 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 qm and an integer p, where p is another prime number which divides qm−1,
- to raise z to a pth 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 pth 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.
A non-transitory computer-readable medium including instructions that, when executed by at least one processor of a circuit, cause the at least one processor to perform a method, the method comprising:
- receiving 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 r of a Galois Field of order pm, where p is a prime and m is a positive integer;
- decomposing r as a product r1.r2 . . . rn of n integers r1, r2, . . . rn, where n is a positive integer;
- iteratively extracting an ri root of a current value of the first element, where i is an integer index between 1 and n, to produce a second element;
- outputting as rth roots of the first element the second element respectively multiplied by successive elements of a set comprising rth roots of unity;
- 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.
Dependencies are inferred from the claim text.