Skip to main content

How to Create a Generator Polynomial

By default, this page demonstrates how to create a generator polynomial for 13 error correction code words. If you would like to see the steps for creating generator polynomial for a different number of code words (up to 68), use the form below.

Introduction to Creating a Generator Polynomial

Below, I will show the steps to create a generator polynomial for 13 error correction code words.

However, since we are working with the galois field GF256, we need to use special methods to make sure our numbers don't get too big or too small to stay in the galois field.

When we multiply two alpha values, normally we add the two exponents together. But if the result is bigger than 255, we have a problem.

For example, consider α251 * α10. Multiplying these two gives us α261, but that is too big.

To prevent that from happening, we put the resulting exponent through the following formula:
(exponent % 256) + floor(exponent / 256)

Using the exponent of 261 from the above example, this gives us:
(261 % 256) + floor(261 / 256) = (5) + floor(1.01953125) = (5 + 1) = 6.

So when we multiply α251 * α10, the result is α6.

Another problem is combining like terms. Because of the nature of the galois field, we can't simply add the numbers together. We have to XOR them.

This will cause some unexpected results. For example:
α201x2 + α199x2 = 56x2 + 14x2

If we add those together normally, we get 70x2. This number is not larger than 255, so it would seem acceptable. However, if we perform an XOR instead of addition, we get:
56 ⊕ 14 = 54.

This is the correct result. When adding like terms during the creation of a generator polynomial, you must always XOR the integers rather than adding them.

How to Create a Generator Polynomial

In each step of creating a generator polynomial, you multiply a polynomial by a polynomial. The very first polynomial that you start with in the first step is always 0x1 + α0x0). For each multiplication step, you multiply the current polynomial by 0x1 + αjx0) where j is 1 for the first multiplication, 2 for the second multiplication, 3 for the third, and so on.

Multiplication Step #

We will multiply (αx0) by (αx1 + αx0)

After multiplying each term from the first part with each term from the second part, we get:
x0 * αx1) + (αx0 * αx0)

To multiply, you add the exponents together like this:
(+)x(0+1)) + (α(+)x(0+0))

After adding the exponents, this is the result:
α0x1 + α0x0

If there are any exponents that are larger than 255, fix them by putting them through the formula
(exponent % 256) + floor(exponent / 256). In this case, all the exponents are less than or equal to 255, so we can continue.

Now you have to combine terms that have the same exponent. In this case, there is more than one term. Below is the final polynomial from this step after combining the like terms. If we needed 1 error correction code words, this would be the generator polynomial required.
αx1 + αx0


Multiplication Step #

We will multiply (αx0) by (αx1 + αx0)

After multiplying each term from the first part with each term from the second part, we get:
x0 * αx1) + (αx0 * αx0)

To multiply, you add the exponents together like this:
(+)x(0+1)) + (α(+)x(0+0))

After adding the exponents, this is the result:
α0x1 + α0x0

If there are any exponents that are larger than 255, fix them by putting them through the formula
(exponent % 256) + floor(exponent / 256). In this case, all the exponents are less than or equal to 255, so we can continue.

Now you have to combine terms that have the same exponent. In this case, there is more than one term. Below is the final polynomial from this step after combining the like terms. If we needed 1 error correction code words, this would be the generator polynomial required.
αx1 + αx0


Multiplication Step #

We will multiply (αx0) by (αx1 + αx0)

After multiplying each term from the first part with each term from the second part, we get:
x0 * αx1) + (αx0 * αx0)

To multiply, you add the exponents together like this:
(+)x(0+1)) + (α(+)x(0+0))

After adding the exponents, this is the result:
α0x1 + α0x0

If there are any exponents that are larger than 255, fix them by putting them through the formula
(exponent % 256) + floor(exponent / 256). In this case, all the exponents are less than or equal to 255, so we can continue.

Now you have to combine terms that have the same exponent. In this case, there is more than one term. Below is the final polynomial from this step after combining the like terms. If we needed 1 error correction code words, this would be the generator polynomial required.
αx1 + αx0


Multiplication Step #

We will multiply (αx0) by (αx1 + αx0)

After multiplying each term from the first part with each term from the second part, we get:
x0 * αx1) + (αx0 * αx0)

To multiply, you add the exponents together like this:
(+)x(0+1)) + (α(+)x(0+0))

After adding the exponents, this is the result:
α0x1 + α0x0

If there are any exponents that are larger than 255, fix them by putting them through the formula
(exponent % 256) + floor(exponent / 256). In this case, all the exponents are less than or equal to 255, so we can continue.

Now you have to combine terms that have the same exponent. In this case, there is more than one term. Below is the final polynomial from this step after combining the like terms. If we needed 1 error correction code words, this would be the generator polynomial required.
αx1 + αx0


Multiplication Step #

We will multiply (αx0) by (αx1 + αx0)

After multiplying each term from the first part with each term from the second part, we get:
x0 * αx1) + (αx0 * αx0)

To multiply, you add the exponents together like this:
(+)x(0+1)) + (α(+)x(0+0))

After adding the exponents, this is the result:
α0x1 + α0x0

If there are any exponents that are larger than 255, fix them by putting them through the formula
(exponent % 256) + floor(exponent / 256). In this case, all the exponents are less than or equal to 255, so we can continue.

Now you have to combine terms that have the same exponent. In this case, there is more than one term. Below is the final polynomial from this step after combining the like terms. If we needed 1 error correction code words, this would be the generator polynomial required.
αx1 + αx0


Multiplication Step #

We will multiply (αx0) by (αx1 + αx0)

After multiplying each term from the first part with each term from the second part, we get:
x0 * αx1) + (αx0 * αx0)

To multiply, you add the exponents together like this:
(+)x(0+1)) + (α(+)x(0+0))

After adding the exponents, this is the result:
α0x1 + α0x0

If there are any exponents that are larger than 255, fix them by putting them through the formula
(exponent % 256) + floor(exponent / 256). In this case, all the exponents are less than or equal to 255, so we can continue.

Now you have to combine terms that have the same exponent. In this case, there is more than one term. Below is the final polynomial from this step after combining the like terms. If we needed 1 error correction code words, this would be the generator polynomial required.
αx1 + αx0


Multiplication Step #

We will multiply (αx0) by (αx1 + αx0)

After multiplying each term from the first part with each term from the second part, we get:
x0 * αx1) + (αx0 * αx0)

To multiply, you add the exponents together like this:
(+)x(0+1)) + (α(+)x(0+0))

After adding the exponents, this is the result:
α0x1 + α0x0

If there are any exponents that are larger than 255, fix them by putting them through the formula
(exponent % 256) + floor(exponent / 256). In this case, all the exponents are less than or equal to 255, so we can continue.

Now you have to combine terms that have the same exponent. In this case, there is more than one term. Below is the final polynomial from this step after combining the like terms. If we needed 1 error correction code words, this would be the generator polynomial required.
αx1 + αx0


Multiplication Step #

We will multiply (αx0) by (αx1 + αx0)

After multiplying each term from the first part with each term from the second part, we get:
x0 * αx1) + (αx0 * αx0)

To multiply, you add the exponents together like this:
(+)x(0+1)) + (α(+)x(0+0))

After adding the exponents, this is the result:
α0x1 + α0x0

If there are any exponents that are larger than 255, fix them by putting them through the formula
(exponent % 256) + floor(exponent / 256). In this case, all the exponents are less than or equal to 255, so we can continue.

Now you have to combine terms that have the same exponent. In this case, there is more than one term. Below is the final polynomial from this step after combining the like terms. If we needed 1 error correction code words, this would be the generator polynomial required.
αx1 + αx0


Multiplication Step #

We will multiply (αx0) by (αx1 + αx0)

After multiplying each term from the first part with each term from the second part, we get:
x0 * αx1) + (αx0 * αx0)

To multiply, you add the exponents together like this:
(+)x(0+1)) + (α(+)x(0+0))

After adding the exponents, this is the result:
α0x1 + α0x0

If there are any exponents that are larger than 255, fix them by putting them through the formula
(exponent % 256) + floor(exponent / 256). In this case, all the exponents are less than or equal to 255, so we can continue.

Now you have to combine terms that have the same exponent. In this case, there is more than one term. Below is the final polynomial from this step after combining the like terms. If we needed 1 error correction code words, this would be the generator polynomial required.
αx1 + αx0


Multiplication Step #

We will multiply (αx0) by (αx1 + αx0)

After multiplying each term from the first part with each term from the second part, we get:
x0 * αx1) + (αx0 * αx0)

To multiply, you add the exponents together like this:
(+)x(0+1)) + (α(+)x(0+0))

After adding the exponents, this is the result:
α0x1 + α0x0

If there are any exponents that are larger than 255, fix them by putting them through the formula
(exponent % 256) + floor(exponent / 256). In this case, all the exponents are less than or equal to 255, so we can continue.

Now you have to combine terms that have the same exponent. In this case, there is more than one term. Below is the final polynomial from this step after combining the like terms. If we needed 1 error correction code words, this would be the generator polynomial required.
αx1 + αx0


Multiplication Step #

We will multiply (αx0) by (αx1 + αx0)

After multiplying each term from the first part with each term from the second part, we get:
x0 * αx1) + (αx0 * αx0)

To multiply, you add the exponents together like this:
(+)x(0+1)) + (α(+)x(0+0))

After adding the exponents, this is the result:
α0x1 + α0x0

If there are any exponents that are larger than 255, fix them by putting them through the formula
(exponent % 256) + floor(exponent / 256). In this case, all the exponents are less than or equal to 255, so we can continue.

Now you have to combine terms that have the same exponent. In this case, there is more than one term. Below is the final polynomial from this step after combining the like terms. If we needed 1 error correction code words, this would be the generator polynomial required.
αx1 + αx0


Multiplication Step #

We will multiply (αx0) by (αx1 + αx0)

After multiplying each term from the first part with each term from the second part, we get:
x0 * αx1) + (αx0 * αx0)

To multiply, you add the exponents together like this:
(+)x(0+1)) + (α(+)x(0+0))

After adding the exponents, this is the result:
α0x1 + α0x0

If there are any exponents that are larger than 255, fix them by putting them through the formula
(exponent % 256) + floor(exponent / 256). In this case, all the exponents are less than or equal to 255, so we can continue.

Now you have to combine terms that have the same exponent. In this case, there is more than one term. Below is the final polynomial from this step after combining the like terms. If we needed 1 error correction code words, this would be the generator polynomial required.
αx1 + αx0


Final result:
x0)