Reed Solomon Division: Understanding M(x) & G(x) Division

[volican]

Hi, I am looking into Reed Solomon codewords and I am looking at this paper. On page 16 the author divides M(x) by G(x) I am struggling to see how he has arrived at 14501 with a remainder of 63. Would someone be able explain what he did?

 

[rcgldr]

The message has two zeros appended to the end of it to make room for the remainder. This is the same as considering the message to be a function M(x), and the two zeros are appended by multiplying M(x) by x², and the actual division is (M(x) x²)/G(x). If you follow the long division, the last quotient term is 1. This translates into the final lines representing (1 x² + 0 x + 0) - (1 x² + 6 x + 3) , but since addition and subtraction are xor, the remainder is (6x + 3). This remainder (6x + 3) is subtracted from M(x) x², but again, since subtraction is xor, the message becomes 1 x⁶ + 2 x⁵ + 3 x⁴ + 4 x³ + 5 x² + 6 x + 3.

Perhaps the confusion is related to polynomial division. There are no borrows or carries with polynomial division. In each step of the polynomial division, the most significant term of the current dividend has to be reduced to zero in order to proceed. For this example the initial most significant term is 1, so the quotient term is 1. On the next step, the most significant term is 4 (6 xor 2), so the quotient term is 4. The quotient is 1 x⁴ + 4 x³ + 5 x² + 0 x + 1. Note that the quotient is not kept, the goal here is to produce the remainder, which is then subtracted from the extended message to create a polynomial that is an exact multiple of the generator polynomial 1 x² + 6 x + 3.

The wiki article might help

https://en.wikipedia.org/wiki/Reed–Solomon_error_correction

 

[volican]

Thank you very much for the pointer. It was the polynomial long division that I was getting confused with. If anyone else stumbles across this with a similar problem I followed this worked example to understand. Much appreciated for your help :)

 

[rcgldr]

One issue with using binary fields like GF(2^n) is that when to use addition or subtraction is lost in some descriptions. If the field is modulo a prime number p, then add is add mod p, and subtract is sub mod p. If using Forney algorithm, it affects the "formal derivative" of the gamma (or alternate name sigma) error evaluator polynomial. For binary fields the "repeated addition" means that even number of additions produces zero, and odd number of additions produce the original term (so the derivative is just a copy of the odd powered terms), while for fields modulo a prime number p, the repeated addition is the same as multiply mod p.

https://en.wikipedia.org/wiki/Forney_algorithm#Formal_derivative

 

[volican]

What happens if you want to encode a number higher than the value in the set? Eg GF(7) contains seven elements {0,1,2,3,4,5,6}. In the paper it says that it just repeats but does this not mean we would loose information? For example say I wanted to send a 9, how would we know it was 9 instead of 2?

 

[rcgldr]

What happens if you want to encode a number higher than the value in the set? Eg GF(7) contains seven elements {0,1,2,3,4,5,6}. In the paper it says that it just repeats but does this not mean we would loose information? For example say I wanted to send a 9, how would we know it was 9 instead of 2?

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).

https://en.wikipedia.org/wiki/PDF417

It's more common to use binary based fields for Reed Solomon, such as GF(2^8), which is also written as GF(256), or GF(2^12) == GF(4096). The "numbers" in the field are 8 bit polynomials, and the math is performed via a "prime" 9 bit polynomial.

 

[volican]

ah thanks, I am wanting to encode numbers that will comprise 0-9. Could I just do GF(2^4) and just not use the additional numbers?

 

[rcgldr]

ah thanks, I am wanting to encode numbers that will comprise 0-9. Could I just do GF(2^4) and just not use the additional numbers?

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: 2⁰, 2¹, 2², ... = 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]

Thank you very much for your kind help. Really appreciated :)

 

[volican]

What would you use for the irreducible prime polynomial for GF(11)?

For the multiplication table what I did was just create a table (from 0 - 10) where if the product is less than 11 you just use the product value but if it is greater than 11 use the modulus remainder. Do you mean that you could just use the 11 x 11 times table instead of this approach?

 

[rcgldr]

What would you use for the irreducible prime polynomial for GF(11)?

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).

https://en.wikipedia.org/wiki/Finite_field

For the multiplication table what I did was just create a table (from 0 - 10) where if the product is less than 11 you just use the product value but if it is greater than 11 use the modulus remainder. Do you mean that you could just use the 11 x 11 times table instead of this approach?

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]

I have an application that will output numbers comprised of the digits 0-9 (numbers like 47565, 34489, 92838 – this will be the value outputted from an ADC on a microcontroller). I want to provide some FEC via Reed Solomon encoding. I am going with GF(2⁴) and will just not use the values above 9.

From this website (table on the second page), I have found that an irreducible polynomial for GF(2⁴) is:

P(x) = x⁴ + x + 1For GF(2⁴) I have found the attached image to be the tables for addition and multiplication. In my code I will probably just have these as lookup tables with the view to reduce time taken to perform computation.

I worked out my GF(2⁴) table of polynomial using the approach proposed in this paper on page 9, except that I used the aforementioned polynomial instead of the one used in the paper. See attached.I want to maximise error correction so I am considering the following code word specification:

RS[n = 15, k = 5 ] s = 4, t = 10

From the format of the generator polynomial given in the paper linked above (page 14) and plugging in the values I worked out for my GF(2⁴) table of polynomial, I am thinking that the encoding polynomial will take the form:

G(x) = (x + 2) (x + 4) (x + 8) (x + 3) (x + 6) (x + 12) (x + 11) (x + 5) (x + 10) (x + 7)Plugging this into wolfram alpha, it tells me that in expanded form G(x) equals:

x¹⁰ + 68x⁹ + 2028x⁸ + 34878x⁷ +382431x⁶ + 2788422x⁵ + 13664132x⁴ + 44333032x³ + 90899328x² + 106024320^x + 53222400

I am stuck with what to do next :(

In the example in the paper the x0 term of G(X) is XOR with the modulo (in my case I think this would be 10011₂ = 19₁₀). The coefficient is then changed to be this new calculated value, resulting in the encoding polynomial. Would I XOR 5322240010 (converted to base 2) with 100112? The numbers are much larger than those given in the example though so I am thinking I have gone wrong.In the paper, the bit string M(x) is then multiplied by x² to shift the message left by two symbol places (in the example t = 2 is used), for me would I just multiply by x¹⁰ ?

For the example given in the paper all of the coefficients are single digit. In the case where there are multiple digits in each coefficient, how is the division performed at the end? Do you just write in the numbers and use them as one continuous number? For example take 12 and 13 and consider this to be 1213?

I have not been able to find any worked examples for the numbers 0 -9 which surprises me as surely this is a really common thing to want to do. Am I missing something?

 

[rcgldr]

GF(2^4)

For GF(2^4), both addition and subtraction are the same: exclusive or. I use subtraction in this post to show the concepts.

generator polynomial

The coefficients to the generator polynomial are modulo GF(2^4). Using hex digits for the generator polynomial.

$g(x) = (x-2)(x- 4)(x-8)(x-3)(x-6)(x-c)(x-b)(x-5)(x-a)(x-7)$
$g(x) = 1 x^{10}+4 x^{9}+8 x^{8}+a x^{7}+c x^{6}+9 x^{5}+4 x^{4}+2 x^{3}+c x^{2}+2 x+7$

M(x) ... multiply by x¹⁰

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:

$R(x) = M(x) x^{10} \ mod \ G(x)$
$E(x) = M(x) x^{10} \ - \ R(x)$

For the example given in the paper all of the coefficients are single digit.

All of the coefficients are GF(2^4), so a single hex digit.

numbers 0 -9

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.

I have a generic demo program written in C for Reed Solomon with GF(2^4), but need to clean it up. I'll post a link later.

 

[volican]

Thanks again. For your G(x) using the hex numbers did you just multiply out the brackets? Copy and pasting into wolfram alpha gives a much longer expression with different coefficients.

 

[rcgldr]

I used the demo program I wrote. You can also calculate them manually modulo hex 13 == 1 x⁴ +1 x + 1. Link to demo program source:

http://rcgldr.net/misc/eccdemo4.zip

The demo program is interactive and includes the 3 main decoder algorithms, matrix, Euclid, Berlekamp Massey. I use either an old Microsoft C compiler or Visual Studio to compile it.