↑ arvau

Wikipedia / Cyclic code

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.

Definition

be a linear code over a finite field (also called Galois field of block length is called a cyclic code obtained by a cyclic right shift 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

be a quotient of a polynomial ring is an ideal, and hence principal is a principal ideal ring of minimum degree, the generator polynomial.. It follows that every cyclic code is a polynomial code.

is a cyclic code, the dual code is also called the parity-check polynomial or simply check polynomial denotes the reciprocal polynomial.

The idempotent is an idempotent element are coprime such a word always exists and is unique; it is a generator of the code.

An irreducible code, so that its check polynomial is an irreducible polynomial.

Examples

is precisely

.

is irreducible in the polynomial ring, and hence the code is an irreducible code.

.

Trivial examples

.

the parity bit.

Other examples

Many types of commonly used error-correcting codes can be represented as cyclic codes, including BCH codes, Reed-Solomon codes, and some classes of low-density parity-check codes defined from finite geometries.

For correcting errors

Cyclic codes can be used to correct errors, like Hamming codes as 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.

The (7,4) Hamming code has a generator polynomial. This polynomial has a zero in Galois extension field because we are considering the case of two errors here, so each will represent one error.

can have at most two nonzero coefficients corresponding to 2 errors.

We define the syndrome polynomial i.e.

.

For correcting two errors

is equal to zero and if none occurs both are zero.

.

. If say two errors occur, then

.

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). 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.-code.

Hamming code for correcting single errors

-bit binary number code, called Hamming code.

. We need to define one there will be columns who are multiples of each other. So, to get linear independence-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.

code.

.

given as

represents the error locations.

.

For correcting burst errors

From Hamming distance 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

(cyclically) consecutive components, the first and the last of which are nonzero.

. The syndrome polynomial is unique for each pattern and is given by

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. Fire code with the generator polynomial

.

. Therefore,

.

, So

is a codeword. Therefore,

.

equals to zero. That means both that both the bursts are same, contrary to assumption.

. By using multiple fire codes longer burst errors can also be corrected.

cyclic redundancy codes.

On Fourier transform

Applications of Fourier transform are widespread in signal processing. Cyclic codes using Fourier transform can be described in a setting closer to the signal processing.

Fourier transform over finite fields

Fourier transform over finite fields

where,

where,

th root of unity. Therefore

and components are given by

where,

is time is frequency and is the spectrum. In Galois field time domain but the spectrum .

Spectral description

. Here codeword spectrum will be zero.

Thus, cyclic codes can also be defined as

Given a set of spectral indices,, whose elements are called check frequencies, the cyclic code is the set of words over whose spectrum is zero in the components indexed by. Any such spectrum will have components of the form.

. Such spectrum can not be used as cyclic codes.

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

BCH bound

consecutive components of its spectrum equal to zero is all-zero vector.

Hartmann-Tzeng bound

, is the all zero vector.

Roos bound

, is the all-zero vector.

Quadratic residue codes

there is a quadratic residue code.

Generalizations

Constacyclic codes

A constacyclic code. A negacyclic code.

Quasi-cyclic code

A quasi-cyclic code.-QC code. A double circulant code.

Shortened cyclic codes

linear code is called a shortened cyclic code cyclic code. Code of this form are not generally cyclic.

symbols is a common approach, in principle any set of information symbols can be deleted. . If the dropped symbols are not check symbols, this cyclic code is also a shortened cyclic code.

Other generalizations

Quasi-twisted codes. Multi-twisted codes are further generalizations of QT codes, which join multiple QT codes end to end.

See also

Notes

References

Further reading