Reed Solomon Polynomial Generator

Question

I am developing a sample program to generate a 2D Barcode, using Reed-Solomon error correction codes. By going through this article, I am developing the program. But I couldn't understand how he generated the generator polynomial.

Can anybody explain how they generated the generator polynomial? Please guide me to complete this correction step.

Answer 1

Let me show a toy example of a case, where we can use $\alpha=2$. In the more general finite field we cannot think of $\alpha$ as having a numerical 'value'. I use the finite field $GF(11)$ that is isomorphic to the ring of residue classes of integers modulo 11. I assume that you are at least somewhat familiar with modular arithmetic. This way we can take a look at the use of the generator polynomial in encoding the message without having to worry about the construction of the finite field as well. Also the answer will be of a `reasonable' size :-) $$ GF(11)=\{0,1,2,3,4,5,6,7,8,9,A=-1\}, $$ where $A$ stands for the residue class of $10\equiv-1\pmod{11}$. The Reed-Solomon codes use the fact that the multiplicative group of non-zero elements of this (and any other) finite field is cyclic, i.e. consists of powers of a carefully selected element $\alpha$. Trial and error shows that we can select $\alpha=2$, because $\alpha^0=1$, $\alpha^1=2$, $\alpha^2=4$, $\alpha^3=8$, $\alpha^4=16= 5$, $\alpha^5=\alpha\cdot \alpha^4=2\cdot 5=10=-1$, $\alpha^6=2\cdot A=20= 9$, $\alpha^7=2\cdot9=18= 7$, $\alpha^8=2\cdot7=14=3$, and $\alpha^9=2\cdot3=6$. Note that i) I simply equate any two numbers that are congruent with each other modulo 11, because then the two numbers represent the same element of the field, ii) I won't get any new elements by continuing, because $\alpha^{10}=2\cdot6=12=1=\alpha^0$, so the powers of $\alpha$ repeat starting from the tenth power. A similar thing happens with all the finite fields.

In this toy example I describe the encoding procedure using an RS-code with alphabet $GF(11)$ that has $r=4$ check symbols (IOW the code will have minimum distance $r+1=5$ and thus be able to correct up to $t=2$ errors, because $2t+1=5$. This type of an RS-code can carry a message consisting of up to six ($6=11-1-r$) symbols $m_0,m_1,m_2,m_3,m_4,m_5$ that are all elements of the field $GF(11)$. We could agree to use shorter messages, but this time I go with the maximum. The encoding process expands this message into a longer sequence $c_0,c_1,c_2,\ldots,c_9$ of ten symbols from the field $GF(11)$. In order to make the algebra easier to describe we view such sequences as a polynomials. So let $x$ be an unknown, and write $$m(x)= m_0+m_1x+m_2x^2+m_3x^3+m_4x^4+m_5x^5$$ and $$c(x)= c_0+c_1x+c_2x^2+c_3x^3+\cdots+c_9x^9.$$ For the error-correction to work as described, we must make sure that the polynomial $c(x)$ represents a valid codeword, so it has to be a multiple of the generator polynomial of degree $r=4$ $$ g(x)=(x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4)=(x-2)(x-4)(x-8)(x-5). $$ As an exercise you are invited to verify that after expanding this product and reducing all the coefficients modulo 11 you get $$ g(x)=x^4+3x^3+5x^2+8x+1. $$ There are two common ways of turning the message polynomial $m(x)$ to a codeword $c(x)$ that is always divisible by $g(x)$. The simplest way (algebraically) is to declare $$ c(x)=g(x)m(x). $$ This is what is known (see e.g. the Wikipedia page) as non-systematic encoding, so e.g. the said Wikipedia page and Dilip's answer denote this polynomial $c_{nonsys}(x)$. For example, if the message sequence that you want to encode is $(m_0,m_1,m_2,m_3,m_4,m_5)=(3,0,0,0,0,1)$, the message polynomial is $m(x)=3+x^5$, and $$ c_{nonsys}(x)=g(x)m(x)=g(x)(x^5+3)=3 + 2x + 4x^2 + 9x^3 + 3x^4 + x^5 + 8x^6 + 5x^7 + 3x^8 + x^9, $$ so the encoded message is the sequence $(3,2,4,9,3,1,8,5,3,9)$.

For practical reasons engineers often prefer to use so called systematic encoding. Dilip's answer (linked to above) gives you the following recipe: Compute the polynomial $x^rm(x)=x^4(x^5+3)=x^9+3x^4$, and then compute the remainder, when you divide this polynomial with the generator polynomial $g(x)$. The answer is $r(x)=4x+4x^2+x^3$. Thus the polynomial $$ c_{sys}(x)=x^4 m(x)-r(x)=x^9+3x^4-x^3-4x^2-4x=7x+7x^2+Ax^3+3x^4+x^9 $$ is also divisible by $g(x)$. This time the encoded sequence is thus $(0,7,7,A,3,0,0,0,0,1)$. The reason why this is called systematic is that you see the payload message sequence $(3,0,0,0,0,1)$ at the end.

=======================

Added: Constructing finite fields of characteristic two.

Here we need more algebra. The field $GF(256)$ is of characteristic two. In other words, every element $\beta \in GF(256)$ satisfies the relation $\beta+\beta=0$. To give you the idea I first describe, how you get a smaller field $GF(8)$. This is just to save space. The idea is that we want to list the elements of this field as powers of a special element $\alpha$ the same way we used powers of two in the earlier example. A field will always have special elements $0,1$, so to get to eight elements we want the field to look like $$ GF(8)=\{0,1,\alpha,\alpha^2,\alpha^3,\alpha^4,\alpha^5,\alpha^6\}. $$ In the above example of $GF(11)$ the powers of $\alpha$ started repeating after the tenth power ($2^{10}\equiv 1\pmod{11}$). Here we want the powers to start repeating starting from the seventh ($7=8-1$, $10=11-1$), so we want $\alpha^7=1$. Furthermore, we want to be able to add elements of the field together, like $\alpha^3+\alpha^5$ or $1+\alpha^4$ should be one of the elements. The way to achieve this is to declare that $\alpha$ is a root of certain carefully chosen polynomial equation. This time we choose the equation $$\alpha^3+\alpha+1=0.$$ IOW, $\alpha$ is a root of the polynomial $p(x)=x^3+x+1$.

How does that help? The idea is that then we can calculate with powers of $\alpha$, and always use that equation $p(\alpha)=0$ to reduce to lower powers of $\alpha$. This is much the same way as when you multiply complex numbers together, you use the equation $i^2=-1$, e.g. $(2+i)(3+i)=6+2i+3i+i^2=6+5i+i^2=6+5i-1=5+5i$. Only this time the equation only begins to help, when we reach the third power. Here $$ \alpha^3=\alpha^3+0=\alpha^3+p(\alpha)=\alpha^3+\alpha^3+\alpha+1=1+\alpha, $$ because $\alpha^3+\alpha^3=0$. Let's see what happens, when we reduce the powers of $\alpha$ using this relation. In the last column of the following table I always list the fully reduced version of that power of $\alpha$. $$ \eqalign{ \alpha^0&=&&=1,\\ \alpha^1&=&&=\alpha,\\ \alpha^2&=&&=\alpha^2,\\ \alpha^3&=&&=1+\alpha,\\ \alpha^4&=&\alpha\cdot\alpha^3=\alpha(1+\alpha)&=\alpha+\alpha^2,\\ \alpha^5&=&\alpha\cdot\alpha^4=\alpha(\alpha+\alpha^2)=\alpha^2+\alpha^3=\alpha^2+(1+\alpha)&=1+\alpha+\alpha^2,\\ \alpha^6&=&\alpha\cdot\alpha^5=\alpha(1+\alpha+\alpha^2)=\alpha+\alpha^2+\alpha^3= \alpha+\alpha^2+(1+\alpha)&=1+\alpha^2,\\ \alpha^7&=&\alpha\cdot\alpha^6=\alpha(1+\alpha^2)=\alpha+\alpha^3=\alpha+(1+\alpha)&=1. }$$ Here the last row was in a way superfluous, but I wanted to show you that this choice of the polynomial $p(x)$ leads to the desired conclusion that the powers of $\alpha$ start repeating after the seventh. Notice how a new line always depends on the preceding one, and how the relation $\alpha^3=\alpha+1$ is applied as many times as necessary to get rid of all the cubic terms and higher.

Now you should notice that the end results in the last column contain all the quadratic polynomials of the form $b_0+b_1\alpha+b_2\alpha^2$, where all the coefficients $b_i,i=0,1,2$ are bits, i.e. elements of the set $\{0,1\}$. That this worked out in this way is kind of a miracle, but it happened, because we were smart in choosing the polynomial $p(x)$. Notice that $p(x)$ is of degree three, and $8=2^3$. Further notice that we can choose to represent the elements of $GF(8)$ in two ways: either as a power of $\alpha$ or as a quadratic polynomial of $\alpha$. Which do we use? Depends on what we want to do! If we want to add two elements of the field, we first switch to the quadratic polynomial form, so for example $$ \alpha^3+\alpha^5=(1+\alpha)+(1+\alpha+\alpha^2)=(1+1)+(\alpha+\alpha)+\alpha^2=\alpha^2. $$ On the other hand, if we want to multiply two elements of the field, we simply use the fact that the powers start repeating after the seventh, so $\alpha^6\cdot\alpha^4=\alpha^{10}= \alpha^{7}\cdot\alpha^3=1\cdot\alpha^3=\alpha^3$. Or, if the elements are given in the quadratic polynomial form, then we read the table from right to left e.g. $$ (1+\alpha)(1+\alpha+\alpha^2)=\alpha^3\cdot\alpha^5=\alpha^8=\alpha\cdot\alpha^7=\alpha. $$ Observe that addition of two quadratic polynomials $$ (a_0+a_1\alpha+a_2\alpha^2)+(b_0+b_1\alpha+b_2\alpha^2)=(c_0+c_1\alpha+c_2\alpha^2) $$ amounts to (because of the $\beta+\beta=0$ rule) bitwise XORing of the bit strings, or $c_0c_1c_2=(a_0a_1a_2)$^$(b_0b_1b_2)$, if I remember the correct C-notation.

For these reasons I keep two look up tables at hand, when I implement a finite field of characteristic two in a program. One to convert the powers $\alpha^i$ to low degree polynomials, and another to go to the reverse direction.

Ok, so that was $GF(8)$, but you want $GF(256)$, where $256=2^8$. This time the field should look like $$ GF(256)=\{0,1,\alpha,\alpha^2,\alpha^3,\ldots,\alpha^{254}\}. $$ Now the powers of $\alpha$ start repeating starting from the $255^{th}$, so $\alpha^{255}=1$. Instead of quadratic polynomials we now end up using the representation in the form $$ b_0+b_1\alpha+b_2\alpha^2+\cdots+b_7\alpha^7 $$ in terms of $8$ bits $b_0,b_1,\ldots,b_7$. In other words, a single byte will represent an element of this field in the 'additive' form. How do we build the conversion table? To do that we need a suitable polynomial $p(x)$. This time $p(x)$ must be of degree 8. The most common choice is $$ p(x)=x^8+x^4+x^3+x^2+1. $$ The page that you linked to seems to be using this. The replacement rule that we get out of this is $\alpha^8=\alpha^4+\alpha^3+\alpha^2+1$. You can use this relation to get rid of all the eighth powers (and higher!) of $\alpha$. This time the table would have 255 rows, so I hope that you understand, why I won't reproduce it here. Your link seems to have that table.

For a list of other possible polynomials see this link. They give some further links there, too. The links from your other questions lead to some hopefully useful C-code.

Answer 2

Taking a special case of more general results, the generator polynomial of a cyclic $(n, n-2t)$ Reed-Solomon code over GF$(q)$, the finite field of $q$ elements, is of the form $$g(x) = g_0 + g_1x + \cdots + g_{2t}x^{2t} = (x-\alpha)(x - \alpha^2)\cdots (x-\alpha^{2t})$$ where $n$ is the number of symbols in a codeword, $t$ is the number of errors that can be corrected, and $\alpha$ is a primitive $n$-th root of unity in the field. In OP Sunny's special case, $q = 2^8 = 256$, $n = 255$ and $\alpha$ is a primitive element of the field. The elements of GF$(256)$ can be stored as $8$-bit bytes, and addition in the field is the bit-by-bit Exclusive OR operation which is typically included as a machine instruction on most processors. Also, we can replace the minus signs in the above expression by plus signs since addition and subtraction are the same operation in any GF$(2^n)$.

OP Sunny's question seems to be: how do I compute the coefficients $g_i, 0 \leq i \leq 2t$? The obvious answer is of course to multiply the given factors together (which is what the article that he refers to tells him to do), but since he seems to be unsure about how to do this, here is an iterative procedure for it.

Suppose that the coefficients are to be stored in a $(2t+1)$-byte array g with g[i] storing $g_i$, with g[0] initialized to $1$ and all other g[i] to $0$. The elements $\alpha, \alpha^2,\cdots, \alpha^{2t}$ are stored in a $2t$-byte array alpha with alpha[i] storing $\alpha^i$. Assume that we have a program mult(x,y) that takes two bytes $x$ and $y$ representing elements of GF$(256)$ as input and returns the byte value of the product of $x$ and $y$ in GF$(256)$. Then, the coefficients $g_i$ are obtained in g via the following calculation:

for i = 1 step 1 until 2t do
     begin
     for j = 2t step -1 until 1 do
           begin
           g[j] = mult(g[j], alpha[i]) XOR g[j-1]
           end
     g[0] = mult(g[0]), alpha[i])
     end

This seems to be getting off-topic a bit for math.SE but I suspect that the folks on the StackOverflow.SE etc are not too familiar with finite field arithmetic and the likes.