The discussion revolves around the division of polynomials in the context of Reed-Solomon codes, specifically focusing on the division of M(x) by G(x) and the implications of using different finite fields for encoding. Participants explore polynomial long division, the representation of numbers in finite fields, and the construction of irreducible polynomials.
There is no consensus on the best finite field to use for specific applications, as participants present multiple viewpoints on the implications of using different fields and the potential for information loss. The discussion remains unresolved regarding the optimal approach for encoding numbers beyond the finite field limits.
Participants express various assumptions about polynomial division and the behavior of finite fields, including the handling of addition and multiplication in different contexts. There are unresolved mathematical steps related to the construction of generator polynomials and the specifics of encoding schemes.
This discussion may be useful for individuals interested in error correction coding, particularly those working with Reed-Solomon codes and finite field arithmetic in applications such as data transmission and storage.
You wouldn't. There's a further limit with Reed Solomon used for error correction, in that the indexes to errors are calculated via log3(lcr), where lcr is 3 raised to the power of the index modulo 7, and (3^6) mod 7 == (3^0) mod 7 == 1, so the calculated indices are limited to the range 0 to 5. This is why most implementations of Reed Solomon use larger fields. For example PDF417 bar codes use GF(929).volican said:
Yes, GF(2^4) would work just fine. As an alternative, you could use GF(11) (11 is a prime number) , this would leave the value 10 unused. With GF(11), all ten non-zero numbers in the field can be considered as powers of 2: 20, 21, 22, ... = 1 2 4 8 5 10 9 7 3 6 . If it matters, add and subtract would be faster with GF(2^4), since both are XOR. For multiply and divide, 11 x 11 tables could be used for GF(11), and 16 by 16 tables for GF(2^4) (or check for zero values and using log / anti-log tables).volican said:
In the case of GF(p), where p is a prime number, the math is performed modulo p. For GF(p^k), where p is a prime number, the prime polynomial has k+1 terms, where the most significant term is 1 x^k, and math modulo that prime polynomial results in polynomials with k terms, and the math for each term is performed modulo p. Using this definition for GF(p), then the prime polynomial would be 1x + p. Since the elements of GF(p) only have a constant term (no x term), the math is just done modulo p. It is common to write GF(2^k) using a single number, such as GF(256) instead of GF(2^8) or GF(27) instead of GF(3^3).volican said:
Correct, you can just index one of the 11 rows using one of the numbers, and one of the 11 columns using the other number to get a product from the table. You could do a normal multiply and the take the modulo 11 of the product. Another option would be to use log2 and exp2 tables, except this requires a special check for numbers == 0.volican said:
For GF(2^4), both addition and subtraction are the same: exclusive or. I use subtraction in this post to show the concepts.volican said:
The coefficients to the generator polynomial are modulo GF(2^4). Using hex digits for the generator polynomial.volican said:
Correct, this appends 10 zero terms to the message, which is then divided by the generator polynomial using polynomial divide to produce a 10 term remainder, which is subtracted (same as being added) from the zero padded message. The encoded message E(x) is:volican said:
All of the coefficients are GF(2^4), so a single hex digit.volican said:
Using hex notation (0x0 == 0, 0xf = 15), although the values are limited to 0x0 to 0x9, the locations range from 0x0 to 0xf, with the right most term considered as location 0x0 and the left most term considered as location 0xf.volican said:
