Method and system of improved reed-solomon decoding
Embodiments of an improved Galois multiplication route are described. In some embodiments, the Galois multiplication routine looks up and retrieves a first value corresponding to an address in the Galois table, exclusive ORs the retrieved value with a data value from a data set to generate an intermediate address for the Galois table, wherein the data value is at a location associated with an index, and looks up and retrieves a second value in the Galois table by the intermediate address.
1. An apparatus comprising:
a processor; and
a memory to store a Galois table and multiplication routine which when executed by the processor causes the processor to perform actions comprising:
retrieving a first value corresponding to an address in the Galois table, wherein the Galois table includes at least one sub-table which includes a set of 2 m data values that are the result of Galois multiplies of some Galois element by all possible Galois elements in binary form order wherein the binary form represents a consistent ordered mapping of coefficients in the Galois polynomial elements to bit locations in the binary value and wherein the values have an offset address that is a multiple of 2 m added to them;
exclusive ORing the retrieved value with a data value from a data set to generate an intermediate address for the Galois table, wherein the data value is at a location associated with an index;
retrieving a second value in the Galois table by the intermediate address.
2. The apparatus of claim 1 , wherein the routine further comprises:
masking the second value to leave only a relevant portion.
3. The apparatus of claim 1 , further comprising:
prior to looking up and retrieving a second value in the Galois table by the intermediate address,
increasing the index by one; and
determining that the increased index is outside of the data set.
4. The apparatus of claim 1 , wherein the Galois table has sub-tables of size 2 m , wherein m is a dimension of a Galois field.
5. The apparatus of claim 4 , wherein a data path of the processor is greater than m.
6. The apparatus of claim 1 , wherein a Galois sub-table has values such that values of the n-m most significant bits are used as an offset address into the table and, values of the m least significant bits are the result of the Galois multiply of a first Galois element by a second Galois element and the storage location of the value is equal to the offset address plus the value of the first Galois element, wherein n is the width of the address bus and m is the dimension of the Galois field.
7. The apparatus of claim 6 wherein the result and Galois elements are the binary forms obtained by a consistent bit mapping of the coefficients of the Galois polynomial to binary numbers.
8. The apparatus of claim 6 wherein the offset address is a multiple of the length of the Galois field.
9. The apparatus of claim 1 , wherein the apparatus is a modem.
10. A method of performing Galois multiplication by a processor, the method comprising:
retrieving a first value corresponding to an address in a Galois table stored in memory, wherein the Galois table includes at least one sub-table which includes a set of 2 m data values that are the result of Galois multiplies of some Galois element by all possible Galois elements in binary form order wherein the binary form represents a consistent ordered mapping of coefficient in the Galois polynomial elements to bit locations in the binary value and wherein the values have an offset address that is multiple of 2 m added to them;
exclusive ORing the retrieved value with a data value from a data set to generate an intermediate address for the Galois table, wherein the data value is at a location associated with an index into the data set;
retrieving a second value in the Galois table by the intermediate address.
11. The method of claim 10 , wherein the method further comprises:
masking the second value to leave only a relevant portion.
12. The method of claim 10 , further comprising:
prior to looking up and retrieving a second value in the Galois table by the intermediate address,
increasing the index by one; and
determining that the increased index is outside of the data set.
13. The method of claim 10 , wherein the sub-tables are of size 2 m , wherein m is a dimension of a Galois field.
14. The method of claim 12 , wherein a data path of the processor is greater than m.
15. The method of claim 10 , wherein the Galois table values are such that values of the most significant bits are used as an offset address into the table and, values of the least significant bits are the result of the Galois multiply of a first Galois element by a second Galois element and the storage location of the value is equal to the offset address plus the value of the first Galois element.
16. The method of claim 15 wherein the result and Galois elements are the binary forms obtained by a consistent bit mapping of the coefficients of the Galois polynomial to binary numbers.
17. The method of claim 15 wherein the offset address is a multiple of the length of the Galois field.