Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how he generated the Generator Polynomial. Anybody can explain me how they generated the generator polynomial. Please guide me to complete this correction step.

Help Appreciated,

Thanks

Sunny

share|improve this question
3  
Did you understand the calculations in my answer to this question? Reproducing those is doable in this space, but an example involving $GF(256)$ is a tall(er) order :-). Mind you, I don't like the article you linked to very much. Some of the terminology used there is a bit off me thinks. For example, I have never seen the term error correction code words used to mean the sequence of check symbols :-) –  Jyrki Lahtonen Oct 26 '11 at 11:19
    
Ok I came to know the generator polynomial is G(x)=(x-α)(x-α2).....(x-αt) where t=N-K-1 after generating this polynomial in the same article there is a log and anti-log table giving the values of α till <a href="thonky.com/qr-code-tutorial/log-antilog-table/">; α ^255</a>. Keep aside generator polynomial how to know the α value based on its power ...... I dont know may be i am asking very simple question as i am naive to this ...... thanks .... –  dungeon Hunter Oct 26 '11 at 15:12
2  
I am in agreement with @JyrkiLahtonen that I don't like the article that you are using. Not only does it use strange terminology, but a quick look shows that there are several mistakes as well. For example, even the definition of the generator polynomial that you have copied from the article into your comment above is suspect. I think that you need to find an article that will help you understand the concept of a finite field a little more than you seem to do, and I strongly recommend not using anything from thonky.com; look elsewhere. –  Dilip Sarwate Oct 26 '11 at 17:06
    
Can anyone of you please suggest me an article/resource where i can find reed solomon in simple terms ..... –  dungeon Hunter Oct 26 '11 at 18:20
    
I don't know, if my attempt answers your question at all, but I use it as a first iteration. Unfortunately I cannot promise to give you several iterations per day, so look for other sources (and Dilip's and other posters' eventual answers). There is a lot of stuff to cover, if you want to understand the actual error correction algorithms. I won't take you the distance (it's almost a full course's worth of material), but would like to get you started. If you want me to work out the other toy example (links above), I can do that (hopefully some time tomorrow). @ping me! –  Jyrki Lahtonen Oct 26 '11 at 19:05

2 Answers 2

up vote 13 down vote accepted
+100

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=19= 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.

share|improve this answer
1  
@Sunny: People look up those polynomials from tables. And there's a reason for that! The theory proving that they exist is not too demanding, but finding them is a lot of work. –  Jyrki Lahtonen Oct 29 '11 at 4:54
3  
@Sunny Jyrki Lahtonen has added enough material to his answer that I wish I could add another upvote! I will add that the two tables he refers to as being on hand are the log table and antilog table. The antilog table is the one Jyrki has constructed in his answer: it answers the question "What is the polynomial corresponding to $\alpha^i$?" Writing the right hand entries as $100$, $010$, $001$, $110$, $011$, $111$, $101$ and sorting on those, so that the $7$-th item (corresponding to $111$) in the table is $5$ meaning $1 + \alpha + \alpha^2 = \alpha^5$ is the log table. –  Dilip Sarwate Oct 29 '11 at 13:46
1  
This answer's almost like a survey paper/field guide... too bad I can't give another upvote. –  J. M. Oct 30 '11 at 9:42
1  
Sorry guys, may be I got carried away a bit...? –  Jyrki Lahtonen Oct 30 '11 at 12:48
2  
Gee, why are you apologizing? It actually sucks that this answer can't get more upvotes... we should be thanking you profusely for this work! –  J. M. Oct 30 '11 at 15:29

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.