Generator Polynomial

A generator polynomial for a Cyclic Code is a polynomial such that

Theorem

Every Cyclic Code has a unique generator polynomial.

Proof

Take the polynomial of the smallest degree. Use division algorithm.

Proposition

If cyclic codes and have generator polynomials and
then .

Lemma

Let be a Cyclic Code of length with generator polynomial
(where )
Then is a basis for
In particular, .

Corollary

Let be a Cyclic Code with generator polynomial

The Generator Matrix of is: