Cyclic code

Trivial examples of cyclic codes are ${\displaystyle A^{n}}$ itself and the code containing only the zero codeword. These correspond to generators ${\displaystyle 1}$ and ${\displaystyle x^{n}-1}$ respectively: these two polynomials must always be factors of ${\displaystyle x^{n}-1}$.

Over ${\displaystyle GF(2)}$ the parity bit code, consisting of all words of even weight, corresponds to generator ${\displaystyle x+1}$. Again over ${\displaystyle GF(2)}$ this must always be a factor of ${\displaystyle x^{n}-1}$.

Quasi-cyclic codes:

An ${\displaystyle (n,k)}$ quasi-cyclic code is a linear block code such that, for some ${\displaystyle b}$ which is coprime to ${\displaystyle n}$, the polynomial ${\displaystyle x^{b}c(x){\pmod {x^{n}-1}}}$ is a codeword polynomial whenever ${\displaystyle c(x)}$ is a codeword polynomial.

Here, codeword polynomial is an element of a linear code whose code words are polynomials that are divisible by a polynomial of shorter length called the generator polynomial. Every codeword polynomial can be expressed in the form ${\displaystyle c(x)=a(x)g(x)}$, where ${\displaystyle g(x)}$ is the generator polynomial. Any codeword ${\displaystyle (c_{0},..,c_{n-1})}$ of a cyclic code ${\displaystyle C}$ can be associated with a codeword polynomial, namely, ${\displaystyle \sum _{i=0}^{n-1}c_{i}*x^{i}}$. A quasi-cyclic code with ${\displaystyle b}$ equal to ${\displaystyle 1}$ is a cyclic code.

Shortened codes:

An ${\displaystyle [n,k]}$ linear code is called a proper shortened cyclic code if it can be obtained by deleting ${\displaystyle b}$ positions from an ${\displaystyle (n-b,k-b)}$ cyclic code.

In shortened codes information symbols are deleted to obtain a desired blocklength smaller than the design blocklength. The missing information symbols are usually imagined to be at the beginning of the codeword and are considered to be 0. Therefore, ${\displaystyle n}$−${\displaystyle k}$ is fixed, and then ${\displaystyle k}$ is decreased which eventually decreases ${\displaystyle n}$. It is not necessary to delete the starting symbols. Depending on the application sometimes consecutive positions are considered as 0 and are deleted.

All the symbols which are dropped need not be transmitted and at the receiving end can be reinserted. To convert ${\displaystyle (n,k)}$ cyclic code to ${\displaystyle (n-b,k-b)}$ shortened code, set ${\displaystyle b}$ symbols to zero and drop them from each codeword. Any cyclic code can be converted to quasi-cyclic codes by dropping every ${\displaystyle b}$th symbol where ${\displaystyle b}$ is a factor of ${\displaystyle n}$. If the dropped symbols are not check symbols then this cyclic code is also a shortened code.

Let the field elements ${\displaystyle X_{1}}$ and ${\displaystyle X_{2}}$ be the two error location numbers. If only one error occurs then ${\displaystyle X_{2}}$ is equal to zero and if none occurs both are zero.

Let ${\displaystyle S_{1}={v}(\alpha )}$ and ${\displaystyle S_{3}={v}(\alpha ^{3})}$.

These field elements are called "syndromes". Now because ${\displaystyle g(x)}$ is zero at primitive elements ${\displaystyle \alpha }$ and ${\displaystyle \alpha ^{3}}$, so we can write ${\displaystyle S_{1}=e(\alpha )}$ and ${\displaystyle S_{3}=e(\alpha ^{3})}$. If say two errors occur, then

${\displaystyle S_{1}=\alpha ^{i}+\alpha ^{i'}}$ and ${\displaystyle S_{3}=\alpha ^{3i}+\alpha ^{3i'}}$.

And these two can be considered as two pair of equations in ${\displaystyle GF(2^{m})}$ with two unknowns and hence we can write

${\displaystyle S_{1}=X_{1}+X_{2}}$ and ${\displaystyle S_{3}=(X_{1})^{3}+(X_{2})^{3}}$.

Hence if the two pair of nonlinear equations can be solved cyclic codes can used to correct two errors.

A code whose minimum distance is at least 3, have a check matrix all of whose columns are distinct and non zero. If a check matrix for a binary code has ${\displaystyle m}$ rows, then each column is an ${\displaystyle m}$-bit binary number. There are ${\displaystyle 2^{m}-1}$ possible columns. Therefore, if a check matrix of a binary code with ${\displaystyle d_{min}}$ at least 3 has ${\displaystyle m}$ rows, then it can only have ${\displaystyle 2^{m}-1}$ columns, not more than that. This defines a ${\displaystyle (2^{m}-1,2^{m}-1-m)}$ code, called Hamming code.

It is easy to define Hamming codes for large alphabets of size ${\displaystyle q}$. We need to define one ${\displaystyle H}$ matrix with linearly independent columns. For any word of size ${\displaystyle q}$ there will be columns who are multiples of each other. So, to get linear independence all non zero ${\displaystyle m}$-tuples with one as a top most non zero element will be chosen as columns. Then two columns will never be linearly dependent because three columns could be linearly dependent with the minimum distance of the code as 3.

So, there are ${\displaystyle (q^{m}-1)/(q-1)}$ nonzero columns with one as top most non zero element. Therefore, a Hamming code is a ${\displaystyle [(q^{m}-1)/(q-1),(q^{m}-1)/(q-1)-m]}$ code.

Now, for cyclic codes, Let ${\displaystyle \alpha }$ be primitive element in ${\displaystyle GF(q^{m})}$, and let ${\displaystyle \beta =\alpha ^{q-1}}$. Then ${\displaystyle \beta ^{(q^{m}-1)/(q-1)}=1}$ and thus ${\displaystyle \beta }$ is a zero of the polynomial ${\displaystyle x^{(q^{m}-1)/(q-1)}-1}$ and is a generator polynomial for the cyclic code of block length ${\displaystyle n=(q^{m}-1)/(q-1)}$.

But for ${\displaystyle q=2}$, ${\displaystyle \alpha =\beta }$. And the received word is a polynomial of degree ${\displaystyle n-1}$ given as

${\displaystyle v(x)=a(x)g(x)+e(x)}$

where, ${\displaystyle e(x)=0}$ or ${\displaystyle x^{i}}$ where ${\displaystyle i}$ represents the error locations.

But we can also use ${\displaystyle \alpha ^{i}}$ as an element of ${\displaystyle GF(2^{m})}$ to index error location. Because ${\displaystyle g(\alpha )=0}$, we have ${\displaystyle v(\alpha )=\alpha ^{i}}$ and all powers of ${\displaystyle \alpha }$ from ${\displaystyle 0}$ to ${\displaystyle 2^{m}-2}$ are distinct. Therefore, we can easily determine error location ${\displaystyle i}$ from ${\displaystyle \alpha ^{i}}$ unless ${\displaystyle v(\alpha )=0}$ which represents no error. So, a Hamming code is a single error correcting code over ${\displaystyle GF(2)}$ with ${\displaystyle n=2^{m}-1}$ and ${\displaystyle k=n-m}$.

In 1959, Philip Fire[6] presented a construction of cyclic codes generated by a product of a binomial and a primitive polynomial. The binomial has the form ${\displaystyle x^{c}+1}$ for some positive odd integer ${\displaystyle c}$.[7] Fire code is a cyclic burst error correcting code over ${\displaystyle GF(q)}$ with the generator polynomial

${\displaystyle g(x)=(x^{2t-1}-1)p(x)}$

where ${\displaystyle p(x)}$ is a prime polynomial with degree ${\displaystyle m}$ not smaller than ${\displaystyle t}$ and ${\displaystyle p(x)}$ does not divide ${\displaystyle x^{2t-1}-1}$. Block length of the fire code is the smallest integer ${\displaystyle n}$ such that ${\displaystyle g(x)}$ divides ${\displaystyle x^{n}-1}$.

A fire code can correct all burst errors of length t or less if no two bursts ${\displaystyle b(x)}$ and ${\displaystyle x^{j}b'(x)}$ appear in the same co-set. This can be proved by contradiction. Suppose there are two distinct nonzero bursts ${\displaystyle b(x)}$ and ${\displaystyle x^{j}b'(x)}$ of length ${\displaystyle t}$ or less and are in the same co-set of the code. So, their difference is a codeword. As the difference is a multiple of ${\displaystyle g(x)}$ it is also a multiple of ${\displaystyle x^{2t-1}-1}$. Therefore,

${\displaystyle b(x)=x^{j}b'(x)\mod (x^{2t-1}-1)}$.

This shows that ${\displaystyle j}$ is a multiple of ${\displaystyle 2t-1}$, So

${\displaystyle b(x)=x^{l(2t-1)}b'(x)}$

for some ${\displaystyle l}$. Now, as ${\displaystyle l(2t-1)}$ is less than ${\displaystyle t}$ and ${\displaystyle l}$ is less than ${\displaystyle q^{m}-1}$ so ${\displaystyle (x^{l(2t-1)}-1)b(x)}$ is a codeword. Therefore,

${\displaystyle (x^{l(2t-1)}-1)b(x)=a(x)(x^{2t-1}-1)p(x)}$.

Since ${\displaystyle b(x)}$ degree is less than degree of ${\displaystyle p(x)}$,${\displaystyle p(x)}$ cannot divide ${\displaystyle b(x)}$. If ${\displaystyle l}$ is not zero, then ${\displaystyle p(x)}$ also cannot divide ${\displaystyle x^{l(2t-1)}-1}$ as ${\displaystyle l}$ is less than ${\displaystyle q^{m}-1}$ and by definition of ${\displaystyle m}$, ${\displaystyle p(x)}$ divides ${\displaystyle x^{l(2t-1)}-1}$ for no ${\displaystyle l}$ smaller than ${\displaystyle q^{m}-1}$. Therefore ${\displaystyle l}$ and ${\displaystyle j}$ equals to zero. That means both that both the bursts are same, contrary to assumption.

Fire codes are the best single burst correcting codes with high rate and they are constructed analytically. They are of very high rate and when ${\displaystyle m}$ and ${\displaystyle t}$ are equal, redundancy is least and is equal to ${\displaystyle 3t-1}$. By using multiple fire codes longer burst errors can also be corrected.

For error detection cyclic codes are widely used and are called ${\displaystyle t-1}$ cyclic redundancy codes.

Fourier transform over finite fields

The discrete Fourier transform of vector ${\displaystyle v=v_{0},v_{1},....,v_{n-1}}$ is given by a vector ${\displaystyle V=V_{0},V_{1},.....,V_{n-1}}$ where,

${\displaystyle V_{k}}$ = ${\displaystyle \Sigma _{i=0}^{n-1}e^{-j2\pi n^{-1}ik}v_{i}}$ where,

${\displaystyle k=0,.....,n-1}$

where exp(${\displaystyle -j2\pi /n}$) is an ${\displaystyle n}$th root of unity. Similarly in the finite field ${\displaystyle n}$th root of unity is element ${\displaystyle \omega }$ of order ${\displaystyle n}$. Therefore

If ${\displaystyle v=(v_{0},v_{1},....,v_{n-1})}$ is a vector over ${\displaystyle GF(q)}$, and ${\displaystyle \omega }$ be an element of ${\displaystyle GF(q)}$ of order ${\displaystyle n}$, then Fourier transform of the vector ${\displaystyle v}$ is the vector ${\displaystyle V=(V_{0},V_{1},.....,V_{n-1})}$ and components are given by

${\displaystyle V_{j}}$ = ${\displaystyle \Sigma _{i=0}^{n-1}\omega ^{ij}v_{i}}$ where,

${\displaystyle k=0,.....,n-1}$

Here ${\displaystyle i}$ is time index, ${\displaystyle j}$ is frequency and ${\displaystyle V}$ is the spectrum. One important difference between Fourier transform in complex field and Galois field is that complex field ${\displaystyle \omega }$ exists for every value of ${\displaystyle n}$ while in Galois field ${\displaystyle \omega }$ exists only if ${\displaystyle n}$ divides ${\displaystyle q-1}$. In case of extension fields, there will be a Fourier transform in the extension field ${\displaystyle GF(q^{m})}$ if ${\displaystyle n}$ divides ${\displaystyle q^{m}-1}$ for some ${\displaystyle m}$. In Galois field time domain vector ${\displaystyle v}$ is over the field ${\displaystyle GF(q)}$ but the spectrum ${\displaystyle V}$ may be over the extension field ${\displaystyle GF(q^{m})}$.

Any codeword of cyclic code of blocklength ${\displaystyle n}$ can be represented by a polynomial ${\displaystyle c(x)}$ of degree at most ${\displaystyle n-1}$. Its encoder can be written as ${\displaystyle c(x)=a(x)g(x)}$. Therefore, in frequency domain encoder can be written as ${\displaystyle C_{j}=A_{j}G_{j}}$. Here codeword spectrum ${\displaystyle C_{j}}$ has a value in ${\displaystyle GF(q^{m})}$ but all the components in the time domain are from ${\displaystyle GF(q)}$. As the data spectrum ${\displaystyle A_{j}}$ is arbitrary, the role of ${\displaystyle G_{j}}$ is to specify those ${\displaystyle j}$ where ${\displaystyle C_{j}}$ will be zero.

Thus, cyclic codes can also be defined as

Given a set of spectral indices, ${\displaystyle A=(j_{1},....,j_{n-k})}$, whose elements are called check frequencies, the cyclic code ${\displaystyle C}$ is the set of words over ${\displaystyle GF(q)}$ whose spectrum is zero in the components indexed by ${\displaystyle j_{1},...,j_{n-k}}$. Any such spectrum ${\displaystyle C}$ will have components of the form ${\displaystyle A_{j}G_{j}}$.

So, cyclic codes are vectors in the field ${\displaystyle GF(q)}$ and the spectrum given by its inverse fourier transform is over the field ${\displaystyle GF(q^{m})}$ and are constrained to be zero at certain components. But every spectrum in the field ${\displaystyle GF(q^{m})}$ and zero at certain components may not have inverse transforms with components in the field ${\displaystyle GF(q)}$. Such spectrum can not be used as cyclic codes.

Following are the few bounds on the spectrum of cyclic codes.

If ${\displaystyle n}$ be a factor of ${\displaystyle (q^{m}-1)}$ for some ${\displaystyle m}$. The only vector in ${\displaystyle GF(q)^{n}}$ of weight ${\displaystyle d-1}$ or less that has ${\displaystyle d-1}$ consecutive components of its spectrum equal to zero is all-zero vector.

If ${\displaystyle n}$ be a factor of ${\displaystyle (q^{m}-1)}$ for some ${\displaystyle m}$, and ${\displaystyle b}$ an integer that is coprime with ${\displaystyle n}$. The only vector ${\displaystyle v}$ in ${\displaystyle GF(q)^{n}}$ of weight ${\displaystyle d-1}$ or less whose spectral components ${\displaystyle V_{j}}$ equal zero for ${\displaystyle j=\ell _{1}+\ell _{2}b(\mod n)}$, where ${\displaystyle \ell _{1}=0,....,d-s-1}$ and ${\displaystyle \ell _{2}=0,....,s-1}$, is the all zero vector.

If ${\displaystyle n}$ be a factor of ${\displaystyle q^{m}-1}$ for some ${\displaystyle m}$ and ${\displaystyle GCD(n,b)=1}$. The only vector in ${\displaystyle GF(q)^{n}}$ of weight ${\displaystyle d-1}$ or less whose spectral components ${\displaystyle V_{j}}$ equal to zero for ${\displaystyle j=l_{1}+l_{2}b(\mod n)}$, where ${\displaystyle l_{1}=0,...,d-s-2}$ and ${\displaystyle l_{2}}$ takes at least ${\displaystyle s+1}$ values in the range ${\displaystyle 0,....,d-2}$, is the all-zero vector.

When the prime ${\displaystyle l}$ is a quadratic residue modulo the prime ${\displaystyle p}$ there is a quadratic residue code which is a cyclic code of length ${\displaystyle p}$, dimension ${\displaystyle (p+1)/2}$ and minimum weight at least ${\displaystyle {\sqrt {p}}}$ over ${\displaystyle GF(l)}$.