Cyclic code

Cyclic code

In coding theory, cyclic codes are linear block error-correcting codes that have convenient algebraic structures for efficient error detection and correction.

Contents

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(qn) obtained by a cyclic right shift 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 \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] / (xn − 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_1x +\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.[1] This must be a divisor of xn − 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 nd.

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. Such a word always exists and is unique;[2] 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.

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))\,.

It corresponds to the ideal in \mathbb{F}_2[x]/(x^3-1) generated by (1 + x).

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 + x2, corresponding to the codeword (0,1,1).

Trivial examples

Trivial examples of cyclic codes are An itself and the code containing only the zero codeword. These correspond to generators 1 and xn − 1 respectively: these two polynomials must always be factors of xn − 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 xn − 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

Quasi-cyclic codes: An (n,k) quasi-cyclic code is a linear block code such that, for some b coprime with n, the polynomial x^bc(x)(\mod x^n-1) is a codeword polynomial whenever c(x) is a codeword polynomial.

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 (c0,..,cn − 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, nk 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 (nb,kb) 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 bth 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 corrections and detections. 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.

The (7,4) Hamming code has a generator polynomial g(x) = x3 + x + 1. This polynomial has a zero in Galois extension field GF(8) at the primitive element α, and all codewords satisfy \mathcal{C}(\alpha)=0. Cyclic codes can also be used to correct double errors over the field GF(2). Blocklength will be n equal to 2m − 1 and primitive elements α and α3 as zeros in the GF(2m) because we are considering the case of two errors here, so each will represent one error.

The received word is a polynomial of degree n − 1 given as v(x) = a(x)g(x) + e(x)

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

We define the Syndrome Polynomial, S(x) as the remainder of polynomial v(x) when divided by the generator polynomial g(x) i.e.

S(x) = v(x)\mod g(x) = (a(x)g(x) + e(x))\mod g(x) = e(x)\mod g(x) as (a(x)g(x))\mod g(x) is zero.

For correcting two errors

Let the field elements X1 and X2 be the two error location numbers. If only one error occurs then X2 is equal to zero and if none occurs both are zero.

Let S1 = v(α) and S3 = v3).

These field elements are called "syndromes". Now because g(x) is zero at primitive elements α and α3, so we can write S1 = e(α) and S3 = e3). If say two errors occur, then

S1 = αi + αi' and S3 = α3i + α3i'.

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

S1 = X1 + X2 and S3 = (X1)3 + (X2)3.

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 + x3. In fact, any binary Hamming code of the form Ham(2,q) is equivalent to a cyclic code when q is even.[3] Hamming codes of the form Ham(r,2) are also cyclic when r \ge 3 - they are [2r − 1,2rr − 2,4]-codes.[4]

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

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 (qm − 1) / (q − 1) nonzero columns with one as top most non zero element. Therefore, Hamming code is a [(qm − 1) / (q − 1),(qm − 1) / (q − 1) − m] code.

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

But for q = 2, α = β. And the received word is a polynomial of degree n − 1 given as

v(x) = a(x)g(x) + e(x)

where, e(x) = 0 or xi where i represents the error locations.

But we can also use αi as an element of GF(2m) to index error location. Because g(α) = 0, we have v(α) = αi and all powers of α from 0 to 2m − 2 are distinct. Therefore we can easily determine error location i from αi unless v(α) = 0 which represents no error. So, hamming code is a single error correcting code over GF(2) with n = 2m − 1 and k = nm.

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.

In polynomial form cyclic burst of length t can be described as e(x)=x^ib(x)(\mod x^n -1) with b(x) as a polynomial of degree t − 1 with nonzero coefficient b0. Here b(x) defines the pattern and xi defines the starting point of error. Length of the pattern is given by degb(x) + 1. Syndrome poynomial is unique for each pattern and is given by

s(x) = e(x)\mod g(x)

Note that A linear block code that corrects all burst errors of length t or less must have at least 2t check symbols. 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 q2t. Hence at least q2t 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

Fire code is a cyclic burst error correcting code over GF(q) with the generator polynomial

g(x) = (x2t − 1 − 1)p(x)

where p(x) is a prime polynomial with degree m not smaller than t and p(x) does not divide x2t − 1 − 1. Block length of the fire code is the smallest integer n such that g(x) divides xn − 1.

A fire code can correct all burst errors of length t or less if no two bursts b(x) and xjb'(x) appear in the same co-set. This can be proved by contradiction. Suppose there are two distinct nonzero bursts b(x) and xjb'(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 x2t − 1 − 1. Therefore,

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

This shows that j is a multiple of 2t − 1, So

b(x) = xl(2t − 1)b'(x)

for some l. Now, as l(2t − 1) is less than t and l is less than qm − 1 so (xl(2t − 1) − 1)b(x) is a codeword. Therefore,

(xl(2t − 1) − 1)b(x) = a(x)(x2t − 1 − 1)p(x).

Since b(x) degree is less than degree of p(x),p(x) cannot divide b(x). If l is not zero, then p(x) also cannot divide xl(2t − 1) − 1 as l is less than qm − 1 and by definition of m, p(x) divides xl(2t − 1) − 1 for no l smaller than qm − 1. Therefore l and 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 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 wide spread in signal processing. But their applications are not limited to the complex fields only, fourier transform also exist in the Galois field GF(q). 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 v = v0,v1,....,vn − 1 is given by a vector V = V0,V1,.....,Vn − 1 where,

Vk = \Sigma_{i=0}^{n-1} e^{-j2\pi n^{-1}ik}v_i where,

k = 0,.....,n − 1

where exp( j2π / n) is an nth root of unity. Similarly in the finite field nth root of unity is element ω of order n. Therefore

If v = (v0,v1,....,vn − 1) is a vector over GF(q), and ω be an element of GF(q) of order n, then Fourier transform of the vector v is the vector V = (V0,V1,.....,Vn − 1) and components are given by

Vj = \Sigma_{i=0}^{n-1}\omega^{ij} v_i where,

k = 0,.....,n − 1

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

Spectral description of cyclic codes

Any codeword of cyclic code of blocklength n can be represented by a polynomial c(x) of degree at most n − 1. Its encoder can be written as c(x) = a(x)g(x). Therefore in frequency domain encoder can be written as Cj = AjGj. Here codeword spectrum Cj has a value in GF(qm) but all the components in the time domain are from GF(q). As the data spectrum Aj is arbitrary, the role of Gj is to specify those j where Cj will be zero.

Thus, cyclic codes can also be defined as

Given a set of spectral indices, A = (j1,....,jnk), whose elements are called check frequencies, the cyclic code C is the set of words over GF(q) whose spectrum is zero in the components indexed by j1,...,jnk. Any such spectrum C will have components of the form AjGj.

So, cyclic codes are vectors in the field GF(q) and the spectrum given by its inverse fourier transform is over the field GF(qm) and are constrained to be zero at certain components. But note that every spectrum in the field GF(qm) 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.

BCH bound

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

Hartmann-Tzeng bound

If n be a factor of (qm − 1) for some m, and b an integer that is coprime with n. The only vector v in GF(q)n of weight d − 1 or less whose spectral components Vj equal zero for j = \ell_1 + \ell_2b (\mod n), where \ell_1 = 0,...., d - s - 1 and \ell_2 = 0,...., s - 1, is the all zero vector.

Roos bound

If n be a factor of qm − 1 for some m and GCD(n,b) = 1. The only vector in GF(q)n of weight d − 1 or less whose spectral components Vj equal to zero for j = l_1 + l_2b (\mod n), where l1 = 0,...,ds − 2 and l2 takes at least s + 1 values in the range 0,....,d − 2, is the all-zero vector.

Quadratic residue codes

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

Generalizations

A constacyclic code is a linear code with the property that for some constant λ if (c1,c2,...,cn) is a codeword then so is (λcn,c1,...,cn-1). A negacyclic code is a constacyclic code with λ=-1.[5] A quasi-cyclic code has the property that for some s, any cyclic shift of a codeword by s places is again a codeword.[6] A double circulant code is a quasi-cyclic code of even length with s=2.[6]

See also

Notes

  1. ^ van Lint, p.76
  2. ^ van Lint, p.80
  3. ^ Hill, 1988, pp.141,163
  4. ^ Hill, 1988 p.163
  5. ^ van Lint, p.75
  6. ^ a b MacWilliams and Sloane, p.506

References

  • Ranjan Bose, Information theory, coding and cryptography , ISBN 0070482977
  • Scott A. Vanstone, Paul C. Van Oorschot, An introduction to error correcting codes with applications, ISBN 0792390172

External links

This article incorporates material from cyclic code on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • cyclic code — ciklinis kodas statusas T sritis automatika atitikmenys: angl. cyclic code vok. zyklischer Kode, m rus. циклический код, m pranc. code cyclique, m …   Automatikos terminų žodynas

  • Cyclic redundancy check — A cyclic redundancy check (CRC) is an error detecting code designed to detect accidental changes to raw computer data, and is commonly used in digital networks and storage devices such as hard disk drives. Blocks of data entering these systems… …   Wikipedia

  • Cyclic (mathematics) — There are many terms in mathematics that begin with cyclic: Cyclic chain rule, for derivatives, used in thermodynamics Cyclic code, linear codes closed under cyclic permutations Cyclic convolution, a method of combining periodic functions Cycle… …   Wikipedia

  • code cyclique — ciklinis kodas statusas T sritis automatika atitikmenys: angl. cyclic code vok. zyklischer Kode, m rus. циклический код, m pranc. code cyclique, m …   Automatikos terminų žodynas

  • Cyclic nucleotide-gated ion channel — Cyclic nucleotide gated (CNG) ion channels are ion channels that function in response to the binding of cyclic nucleotides. CNG channels are nonselective cation channels that are found in the membranes of various types of cells. Signal… …   Wikipedia

  • Code Correcteur — Un code correcteur est une technique de codage basée sur la redondance. Elle est destinée à corriger les erreurs de transmission d une information (plus souvent appelée message) sur une voie de communication peu fiable. La théorie des codes… …   Wikipédia en Français

  • Cyclic Redundancy Check — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Die zyklische Redundanzprüfung (engl. cyclic redundancy check,… …   Deutsch Wikipedia

  • cyclic binary code — ciklinis dvejetainis kodas statusas T sritis automatika atitikmenys: angl. cyclic binary code vok. zyklisch binärer Code, m rus. цикличный двоичный код, m pranc. code binaire réfléchi, m …   Automatikos terminų žodynas

  • Code correcteur — Un code correcteur est une technique de codage basée sur la redondance. Elle est destinée à corriger les erreurs de transmission d une information (plus souvent appelée message) sur une voie de communication peu fiable. La théorie des codes… …   Wikipédia en Français

  • Cyclic executive — A cyclic executive is an alternative to a real time operating system. It is a form of cooperative multitasking, in which there is only one task. The sole task is typically realized as an infinite loop in main(), e.g. in C/C++. The basic scheme is …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”