Cyclic code - AbsoluteAstronomy.com

Coding theory

Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...

, cyclic codes are linear block

Linear code

In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although Turbo codes can be seen as a hybrid of these two types. Linear codes allow for...

error-correcting codes that have convenient algebraic structures for efficient error detection and correction

Error detection and correction

In information theory and coding theory with applications in computer science and telecommunication, error detection and correction or error control are techniques that enable reliable delivery of digital data over unreliable communication channels...

Definition

Let

be a linear code

Linear code

over a finite field

Finite field

In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

of block length n.

is called a cyclic code, if for every codeword c=(c₁,...,c_n) from C, the word (c_n,c₁,...,c_n-1) in

obtained by a cyclic right shift

Circular shift

In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse operation...

of components is again a codeword. Same goes for left shifts. One right shift is equal to n − 1 left shifts and vice versa. Therefore the linear code

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

be a polynomial ring

Polynomial ring

In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the Hilbert basis theorem, to the construction of...

over the finite field

. Identify the elements of the cyclic code C with polynomials in R such that

maps to the polynomial

: thus multiplication by x corresponds to a cyclic shift. Then C is an ideal

Ideal (ring theory)

In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring. The ideal concept allows the generalization in an appropriate way of some important properties of integers like "even number" or "multiple of 3"....

in R, and hence principal

Principal ideal

In ring theory, a branch of abstract algebra, a principal ideal is an ideal I in a ring R that is generated by a single element a of R.More specifically:...

, since R is a principal ideal ring

Principal ideal ring

In mathematics, a principal right ideal ring is a ring R in which every right ideal is of the form xR for some element x of R...

. The ideal is generated by the unique monic element in C of minimum degree, the generator polynomial g.
This must be a divisor of

. It follows that every cyclic code is a polynomial code

Polynomial code

In coding theory, a polynomial code is a type of linear code whose set of valid code words consists of those polynomials that are divisible by a given fixed polynomial ....

.
If the generator polynomial g has degree d then the rank of the code C is

.

The idempotent of C is a codeword e such that e² = 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. 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 maximal in R, so that its generator is an irreducible polynomial

Irreducible polynomial

In mathematics, the adjective irreducible means that an object cannot be expressed as the product of two or more non-trivial factors in a given set. See also factorization....

Examples

For example, if A=

and n=3, the set of codewords contained in the (1,1,0)-cyclic code is precisely

.

It corresponds to the ideal in

generated by

.

Note that

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

The idempotent of this code is the polynomial

, corresponding to the codeword (0,1,1).

Trivial examples

Trivial examples of cyclic codes are Aⁿ itself and the code containing only the zero codeword. These correspond to generators 1 and

respectively: these two polynomials must always be factors of

.

Over GF(2) the parity bit

Parity bit

A parity bit is a bit that is added to ensure that the number of bits with the value one in a set of bits is even or odd. Parity bits are used as the simplest form of error detecting code....

code, consisting of all words of even weight, corresponds to generator

. Again over GF(2) this must always be a factor of

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

Quasi-cyclic codes:
An

quasi-cyclic code is a linear block code such that, for some

coprime with

, the polynomial

is a codeword polynomial whenever

is a codeword polynomial.

Here codeword polynomial is a linear code whose code word

Code word

In communication, a code word is an element of a standardized code or protocol. Each code word is assembled in accordance with the specific rules of the code and assigned a unique meaning...

s 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

. For any codeword

codeword polynomial corresponds to the

Definition

Shortened codes:
An

linear code is called a proper shortened cyclic code if it can be obtained by deleting

positions from an

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,

−

is fixed, and then

is decreased which eventually decreases

. 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

cyclic code to

shortened code, set

symbols to zero and drop them from each codeword. Any cyclic code can be converted to quasi-cyclic codes by dropping every

th symbol where

is a factor of

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

Hamming code

In telecommunication, Hamming codes are a family of linear error-correcting codes that generalize the Hamming-code invented by Richard Hamming in 1950. Hamming codes can detect up to two and correct up to one bit errors. By contrast, the simple parity code cannot correct errors, and can detect only...

s 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.

The (7,4) Hamming code has a generator polynomial

. This polynomial has a zero in Galois extension field

Galois extension

In mathematics, a Galois extension is an algebraic field extension E/F satisfying certain conditions ; one also says that the extension is Galois. The significance of being a Galois extension is that the extension has a Galois group and obeys the fundamental theorem of Galois theory.The definition...

at the primitive element

, and all codewords satisfy

. Cyclic codes can also be used to correct double errors over the field

. Blocklength will be

equal to

and primitive elements

and

as zeros in the

because we are considering the case of two errors here, so each will represent one error.

The received word is a polynomial of degree

given as

where

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

We define the Syndrome Polynomial,

as the remainder of polynomial

when divided by the generator polynomial

i.e.

is zero.

For correcting two errors

Let the field elements

and

be the two error location numbers. If only one error occurs then

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

Let

and

.

These field elements are called "syndromes". Now because

is zero at primitive elements

and

, so we can write

and

. If say two errors occur, then

and

.

And these two can be considered as two pair of equations in

with two unknowns and hence we can write

and

.

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)

Hamming(7,4)

In coding theory, Hamming is a linear error-correcting code that encodes 4 bits of data into 7 bits by adding 3 parity bits. It is a member of a larger family of Hamming codes, but the term Hamming code often refers to this specific code that Richard W. Hamming introduced in 1950...

code may be written as a cyclic code over GF(2) with generator

. In fact, any binary Hamming code

Hamming code

of the form Ham(2,q) is equivalent to a cyclic code when

is even. Hamming codes of the form Ham(r,2) are also cyclic when

- they are

-codes.

Hamming code for correcting single error

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

rows, then each column is an

-bit binary number. There are

possible columns. Therefore if a check matrix of a binary code with

at least 3 has

rows, then it can only have

columns, not more than that. This defines a

codes, called Hamming codes.

It is easy to define Hamming codes for large alphabets of size

. We need to define one matrix with linearly independent columns. For any word of size

there will be columns who are multiples of each other. So, to get linear independence all non zero

-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

nonzero columns with one as top most non zero element. Therefore, Hamming code is a

code.

Now, for cyclic codes, Let

be primitive element in

, and let

. Then

and thus

is a zero of the polynomial

and is a generator polynomial for the cyclic code of block length

.

But for

. And the received word is a polynomial of degree

given as

where,

where

represents the error locations.

But we can also use

as an element of

to index error location. Because

, we have

and all powers of

from

are distinct. Therefore we can easily determine error location

from

unless

which represents no error. So, hamming code is a single error correcting code over

with

and

Cyclic codes for correcting burst errors

From Hamming distance

Hamming distance

In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...

concept, a code with minimum distance

can correct any

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

is a vector whose nonzero components are among

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

In polynomial form cyclic burst of length

can be described as

with

as a polynomial of degree

with nonzero coefficient

. Here

defines the pattern and

defines the starting point of error. Length of the pattern is given by deg

. Syndrome poynomial is unique for each pattern and is given by

Note that A linear block code that corrects all burst errors of length

or less must have at least

check symbols. Because any linear code that can correct burst pattern of length

or less cannot have a burst of length

or less as a codeword because if it did then a burst of length

could change the codeword to burst pattern of length

, which also could be obtained by making a burst error of length

in all zero codeword. Now, any two vectors that are non zero in the first

components must be from different co-sets of an array to avoid their difference being a codeword of bursts of length

. Therefore number of such co-sets are equal to number of such vectors which are

. Hence at least

co-sets and hence at least

check symbol.

This property is also known as Rieger bound and it is similar to the singleton bound

Singleton bound

In coding theory, the Singleton bound, named after Richard Collom Singleton, is a relatively crude bound on the size of a block code C with block length n, size r and minimum distance d.-Statement of the Bound:...

for random error correcting.

Fire codes as cyclic bounds

Fire code is a cyclic burst error correcting code over

with the generator polynomial

where

is a prime polynomial with degree

not smaller than

and

does not divide

. Block length of the fire code is the smallest integer

such that

divides

.

A fire code can correct all burst errors of length t or less if no two bursts

and

appear in the same co-set. This can be proved by contradiction. Suppose there are two distinct nonzero bursts

and

of length

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

it is also a multiple of

. Therefore,

.

This shows that

is a multiple of

, So

for some

. Now, as

is less than

and

is less than

is a codeword. Therefore,

.

Since

degree is less than degree of

cannot divide

. If

is not zero, then

also cannot divide

is less than

and by definition of

divides

for no

smaller than

. Therefore

and

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

and

are equal, redundancy is least and is equal to

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

For error detection cyclic codes are widely used and are called

cyclic redundancy codes

Cyclic redundancy check

A cyclic redundancy check is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data...

Cyclic codes on Fourier transform

Applications of Fourier transform

Fourier transform

In mathematics, Fourier analysis is a subject area which grew from the study of Fourier series. The subject began with the study of the way general functions may be represented by sums of simpler trigonometric functions...

are wide spread in signal processing. But their applications are not limited to the complex fields only, fourier transform also exist in the Galois field

. Cyclic codes using fourier transform can be described in a setting closer to the signal processing.

Fourier transform over finite fields

The discrete Fourier transform of vector

is given by a vector

where,

where exp(

) is an

th root of unity. Similarly in the finite field

th root of unity is element

of order

. Therefore

If is a vector over , and be an element of of order , then Fourier transform of the vector is the vector and components are given by

where,

Here

is time index,

is frequency and is the spectrum. One important difference between Fourier transform in complex field and Galois field is that complex field

exists for every value of

while in Galois field

exists only if

divides

. In case of extension fields, there will be a Fourier transform in the extension field

divides

for some

.
In Galois field time domain vector

is over the field

but the spectrum may be over the extension field

Spectral description of cyclic codes

Any codeword of cyclic code of blocklength

can be represented by a polynomial

of degree at most

. Its encoder can be written as

. Therefore in frequency domain encoder can be written as

. Here codeword spectrum

has a value in

but all the components in the time domain are from

. As the data spectrum

is arbitrary, the role of

is to specify those

where

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

.

So, cyclic codes are vectors in the field

and the spectrum given by its inverse fourier transform is over the field

and are constrained to be zero at certain components. But note that every spectrum in the field

and zero at certain components may not have inverse transforms with components in the field

. Such spectrum can not be used as cyclic codes.

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

BCH bound

be a factor of

for some

. The only vector in

of weight

or less that has

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

Hartmann-Tzeng bound

be a factor of

for some

, and

an integer that is coprime with

. The only vector

of weight

or less whose spectral
components

equal zero for

, where

and

, is the all zero vector.

Roos bound

be a factor of

for some

and

. The only vector in

of weight

or less whose spectral components

equal to zero for

, where

and

takes at least

values in the range

, is the all-zero vector.

Quadratic residue codes

When the prime

is a quadratic residue modulo the prime

there is a quadratic residue code

Quadratic residue code

A quadratic residue code is a type of cyclic code.There is a quadratic residue code of length pover the finite field GF whenever pand l are primes, p is odd andl is a quadratic residue modulo p....

which is a cyclic code of length

, dimension

and minimum weight at least

over

Generalizations

A constacyclic code is a linear code with the property that for some constant λ if (c₁,c₂,...,c_n) is a codeword then so is (λc_n,c₁,...,c_n-1). A negacyclic code is a constacyclic code with λ=-1. A quasi-cyclic code has the property that for some s, any cyclic shift of a codeword by s places is again a codeword. A double circulant code is a quasi-cyclic code of even length with s=2.