Cyclic code

A cyclic code is inserted in the digital signal processing and communications technology of the channel code. Cyclic codes are part of the group of linear codes and are used among other things for forward error correction transmission channels or data stores.

As such it is the basis for a number of methods for signal transmission, with which the recipient of a message can check them for errors, and can correct errors which may have occurred without confirmation to the sender due to the additional redundancy introduced.

• 4.1 Examples

Definition

A cyclic code is a linear code, which has the following additional property: If a code word, then a code word. It follows that the code words are of.

Polynomial representation

Cyclic codes can be described as ideals of the ring. The characters of a code word are regarded as coefficients of a polynomial:

Elements of the ring are residue classes of polynomials with respect to the polynomial by. Each coset has an excellent element of degree less than n, which is used to denote the residue class. Multiplication by x and reduction modulo lead to the polynomial

That currently has the cyclically shifted coefficient sequence. So to be the property periodically in the polynomial ring means that the code C to multiplication by x, and thus any monomials with degree is completed.

Since the code C is linear, ie contains multiples and sums of codewords, it follows that with a polynomial of the coefficient sequences of all polynomials are contained in the code, the code corresponds to an ideal in the ring.

As a principal ideal ring, which the codewords corresponding polynomials and is already ideal generated by a polynomial of smallest degree contained therein generated ( generating polynomial ). This is always a divisor of. So you know all of Teilerpolynome, so one also knows all cyclic linear codes. Special interest enjoy the codes corresponding to the irreducible factors.

Encoding and Decoding

Encoding

The generator polynomial have the degree. The code then has the dimension. A plaintext word is encoded either by multiplication or division by a code word:

The multiplication is the obvious method.

The ring is a Euclidean ring with respect to the polynomial. Therefore, in the equation, the polynomials and uniquely determined ( is calculated by polynomial division ). The word is then coded.

Advantage of this method is on the one hand, that the information symbols / information bits directly as plain text in the code word. Furthermore, the circuit realization of this method for binary codes is very simple ( see below).

Decoding

A received word is divided by. If the remainder is equal to zero, was already in the code. If the remainder is nonzero, then joined the transmission will fail. The rest corresponds to the syndrome, the word can then be decoded with the help of a syndrome table.

Circuitry means that for encoding and decoding, by dividing - the whole - the same circuits can be used.

Realizations

The advantage of the cyclic code in practical applications, such as digital circuits, is the ability to generate these codes by means of linear feedback shift registers ( LFSR).

In this diagram is to illustrate a cyclic ( 15,11 ) Hamming encoder with the generator polynomial z4 z 1 shown. In the encoder, the data bits of d are as a serial data stream in the middle is read up and right output the codeword c serially. The switches are located initially in position A: In order for the data bits in the code word first output directly and simultaneously pushed into the LFSR. If all the bits of a data word is read, replace both switch in position B: the contents of the LFSR is then bitwise corresponding to the testing p. Are all inspection issued, the process repeats. To simplify the necessary clock and synchronization circuits are lines not shown in the circuit diagram.

The decoding of cyclic code on the receiver side can be done by LFSR, which usually comes a syndrome decoding applied.

Examples

Besides the aforementioned cyclic Hamming codes, there are specific cyclic variants of Reed -Solomon codes, which are used in the data format of the CD -ROM among others. In turn a special case of the latter, the codes used in the cyclic redundancy check (CRC) for error detection.

Literature sources

• Martin Bossert: Channel coding. 2nd completely revised and expanded edition. Teubner, Stuttgart 1998, ISBN 3-519-16143-5 (Information technology).
• Todd K. Moon: Error Correction Coding. Mathematical Methods and Algorithms. Wiley- Interscience, Hoboken NJ 2005, ISBN 0-471-64800-0.
• Harm Pralle: coding theory, Lecture notes. Technical University of Braunschweig, 2005 ( http://www-public.tu-bs.de:8080/ hpralle ~ / scripts / coding.pdf ).

• Communications Engineering
• Coding Theory