# Cyclic code

{{ safesubst:#invoke:Unsubst||$N=Technical |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }} In coding theory, a cyclic code is a block code, where the circular shifts of each codeword gives another word that belongs to the code. They are error-correcting codes that have algebraic properties that are convenient for efficient error detection and correction. If 00010111 is a valid codeword, applying a right circular shift gives the string 10001011. If the code is cyclic, then 10001011 is again a valid codeword. In general, applying a right circular shift moves the least significant bit (LSB) to the leftmost position, so that it becomes the most significant bit (MSB); the other positions are shifted by 1 to the right.

## Definition

Let ${\mathcal {C}}$ be a linear code over a finite field $GF(q)$ of block length n. ${\mathcal {C}}$ is called a cyclic code if, for every codeword c=(c1,...,cn) from C, the word (cn,c1,...,cn-1) in $GF(q)^{n}$ obtained by a cyclic right shift of components is again a codeword. Because one cyclic right shift is equal to n − 1 cyclic left shifts, a cyclic code may also be defined via cyclic left shifts. Therefore the linear code ${\mathcal {C}}$ is cyclic precisely when it is invariant under all cyclic shifts.

Cyclic Codes have some additional structural constraint on the codes. They are based on Galois fields and because of their structural properties they are very useful for error controls. Their structure is strongly related to Galois fields because of which the encoding and decoding algorithms for cyclic codes are computationally efficient.

## Algebraic structure

Cyclic codes can be linked to ideals in certain rings. Let $R=A[x]/(x^{n}-1)$ be a polynomial ring over the finite field $A=GF(q)$ . Identify the elements of the cyclic code C with polynomials in R such that $(c_{0},\ldots ,c_{n-1})$ maps to the polynomial $c_{0}+c_{1}x+\cdots +c_{n-1}x^{n-1}$ : thus multiplication by x corresponds to a cyclic shift. Then C is an ideal in R, and hence principal, since R is a principal ideal ring. The ideal is generated by the unique monic element in C of minimum degree, the generator polynomial g. This must be a divisor of $x^{n}-1$ . It follows that every cyclic code is a polynomial code. If the generator polynomial g has degree d then the rank of the code C is $n-d$ .

The idempotent of C is a codeword e such that e2 = e (that is, e is an idempotent element of C) and e is an identity for the code, that is e c = c for every codeword c. If n and q are coprime such a word always exists and is unique; it is a generator of the code.

An irreducible code is a cyclic code in which the code, as an ideal is irreducible, i.e. is minimal in R, so that its check polynomial is an irreducible polynomial.

## Examples

For example, if A=$\mathbb {F} _{2}$ and n=3, the set of codewords contained in the (1,1,0)-cyclic code is precisely

$((0,0,0),(1,1,0),(0,1,1),(1,0,1))\,$ .

Note that $(1+x)$ is an irreducible polynomial in the polynomial ring, and hence the code is an irreducible code.

The idempotent of this code is the polynomial $x+x^{2}$ , corresponding to the codeword (1,1,0).

### Trivial examples

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

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

## Quasi-cyclic codes and shortened codes

Before delving into the details of cyclic codes first we will discuss quasi-cyclic and shortened codes which are closely related to the cyclic codes and they all can be converted into each other.

### Definition

Here codeword polynomial is a linear code whose code words are polynomials that are divisible by a polynomial of shorter length called generator polynomial. Note that every codeword polynomial can be expressed in the form $c(x)=a(x)g(x)$ . For any codeword $(c_{0},..,c_{n-1})$ codeword polynomial corresponds to the $\sum _{i=0}^{n-1}c_{i}*x^{i}$ .

### Definition

Shortened codes: An $[n,k]$ linear code is called a proper shortened cyclic code if it can be obtained by deleting $b$ positions from an $(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, $n$ $k$ is fixed, and then $k$ is decreased which eventually decreases $n$ . Note that 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 $(n,k)$ cyclic code to $(n-b,k-b)$ shortened code, set $b$ symbols to zero and drop them from each codeword. Any cyclic code can be converted to quasi-cyclic codes by dropping every $b$ th symbol where $b$ is a factor of $n$ . If the dropped symbols are not check symbols then this cyclic code is also a shortened code.

## Cyclic codes for correcting errors

Now, we will begin the discussion of cyclic codes explicitly with error detection and correction. Cyclic codes can be used to correct errors, like Hamming codes as a cyclic codes can be used for correcting single error. Likewise, they are also used to correct double errors and burst errors. All types of error corrections are covered briefly in the further subsections.

where $e(x)$ can have at most two nonzero coefficients corresponding to 2 errors.

### For correcting two errors

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

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

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

## Hamming code

The Hamming(7,4) code may be written as a cyclic code over GF(2) with generator $1+x+x^{3}$ . In fact, any binary Hamming code of the form Ham(r, 2) is equivalent to a cyclic code, and any Hamming code of the form Ham(r,q) with r and q-1 relatively prime is also equivalent to a cyclic code. Given a Hamming code of the form Ham(r,2) with $r\geq 3$ , the set of even codewords forms a cyclic $[2^{r}-1,2^{r}-r-2,4]$ -code.

### Hamming code for correcting single 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 $m$ rows, then each column is an $m$ -bit binary number. There are $2^{m}-1$ possible columns. Therefore if a check matrix of a binary code with $d_{min}$ at least 3 has $m$ rows, then it can only have $2^{m}-1$ columns, not more than that. This defines a $(2^{m}-1,2^{m}-1-m)$ code, called Hamming code.

It is easy to define Hamming codes for large alphabets of size $q$ . We need to define one $H$ matrix with linearly independent columns. For any word of size $q$ there will be columns who are multiples of each other. So, to get linear independence all non zero $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 $(q^{m}-1)/(q-1)$ nonzero columns with one as top most non zero element. Therefore, Hamming code is a $[(q^{m}-1)/(q-1),(q^{m}-1)/(q-1)-m]$ code.

## Cyclic codes for correcting burst errors

From Hamming distance concept, a code with minimum distance $2t+1$ can correct any $t$ errors. But in many channels error pattern is not very arbitrary, it occurs within very short segment of the message. Such kind of errors are called burst errors. So, for correcting such errors we will get a more efficient code of higher rate because of the less constraints. Cyclic codes are used for correcting burst error. In fact, cyclic codes can also correct cyclic burst errors along with burst errors. Cyclic burst errors are defined as

A cyclic burst of length $t$ is a vector whose nonzero components are among $t$ (cyclically) consecutive components, the first and the last of which are nonzero.

A linear block code that corrects all burst errors of length $t$ or less must have at least $2t$ check symbols. Proof: Because any linear code that can correct burst pattern of length $t$ or less cannot have a burst of length $2t$ or less as a codeword because if it did then a burst of length $t$ could change the codeword to burst pattern of length $t$ , which also could be obtained by making a burst error of length $t$ in all zero codeword. Now, any two vectors that are non zero in the first $2t$ components must be from different co-sets of an array to avoid their difference being a codeword of bursts of length $2t$ . Therefore number of such co-sets are equal to number of such vectors which are $q^{2t}$ . Hence at least $q^{2t}$ co-sets and hence at least $2t$ check symbol.

This property is also known as Rieger bound and it is similar to the singleton bound for random error correcting.

### Fire codes as cyclic bounds

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

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

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 $m$ and $t$ are equal, redundancy is least and is equal to $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 $t-1$ cyclic redundancy codes.

## Cyclic codes on Fourier transform

Applications of Fourier transform are widespread in signal processing. But their applications are not limited to the complex fields only; Fourier transforms also exist in the Galois field $GF(q)$ . Cyclic codes using Fourier transform can be described in a setting closer to the signal processing.

### Spectral description of cyclic codes

Thus, cyclic codes can also be defined as

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

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