Intereting Posts

Calculating a Lebesgue integral involving the Cantor Function
Proving that every set $A \subset \Bbb N$ of size $n$ contains a subset $B \subset A$ with $n | \sum_{b \in B} b$
Finding a closed form expression for $\sum_{i=1}^{n-1}\csc{\frac{i\pi}{n}}$
Combinatorics question about english letters (with consonants and vowels)
The longest word in Weyl group and positive roots.
Sheafyness and relative chinese remainder theorem
congruence issue
Solve $x(x+1)=y(y+1)(y^2+2)$ for $x,y$ over the integers
Solving this summation: $\sum_{i=1}^k i\cdot2^i$
Is there much of difference between set models and class models?
Finite Group and normal Subgroup
Behaviour of $\int_0^{\frac{\pi^2}{4}}\exp(x\cos(\sqrt{t}))dt$
Linear algebra and geometric insight: a rigorous approach to vector spaces, matrices, and linear applications
Can a circle's circumference be divided into arbitrary number of equal parts using straight edge and compass only?
Deducing correct answers from multiple choice exams

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

- How original RS codes and the corresponding BCH codes are related?
- For what $(n,k)$ there exists a polynomial $p(x) \in F_2$ s.t. $\deg(p)=k$ and $p$ divides $x^n-1$?
- Generating a binary code with maximized Hamming distance
- Minimum distance of a binary linear code
- CRC computation
- Proof of Closed Form Formula to convert a binary number to it's Gray code

Sunny

- How to find a function that is the upper bound of this sum?
- What makes a context free grammar ambiguous?
- Finding the 2,147,483,647th prime number
- The Practical Implication of P vs NP Problem
- Is there a computer programm or CAS (maybe GAP?) that can calculate with projective (indecomposable) A-modules (A is a finite dimensional k-algebra)?
- Prove that the set of palindromes are not regular languages using the pumping lemma.
- Recognizing and Using Chaitin's Constant
- Understanding Reed-Solomon as it applies to Shamir secret sharing
- Computation with a memory wiped computer
- How original RS codes and the corresponding BCH codes are related?

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.

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.

- What went wrong?
- Proof that the power set of $\mathbb{N}$ is uncountable, and that the composition of two bijections is a bijection
- Infinite direct product of fields.
- Prove that $a+b$ is a perfect square
- Finding the Dimension of a Matrix Polynomial: $W$ = { $p(B)$ : $p$ is a polynomial with real coefficients}
- Monte Carlo double integral over a non-rectangular region (Matlab)
- Prove $\int_0^{2\pi}\frac{3a\sin^2\theta}{(1-a\cos \theta)^4}\mathrm{d}\theta = \int_0^{2\pi}\frac{\cos \theta}{(1-a\cos \theta)^3}\,\mathrm{d}\theta$
- Crossing the road
- A union of balls centered at all the rationals on $$ with decreasing radius $r_n \to 0$ relation with $$
- Can all theorems of $\sf ZFC$ about the natural numbers be proven in $\sf ZF$?
- Eigenvalue of a polynomial evaluated in a operator
- Galois Field Fourier Transform
- Given two subspaces $U,W$ of vector space $V$, how to show that $\dim(U)+\dim(W)=\dim(U+W)+\dim(U\cap W)$
- Showing a Transformation increases measure (Ergodic Theory)
- Is $\sum_{n=1}^\infty {1\over 3^{\sqrt{n}}}$ convergent?