Cyclic code

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

As such, it is the basis for a number of methods for signal transmission with which the recipient of a message can check it for errors and, if necessary, correct any errors that have occurred without asking the sender through the additional redundancy introduced .

definition

A cyclic code is a linear code that also has the following property: If a code word is from , then a code word is from . It follows that code words are also from . ${\displaystyle C}$ ${\displaystyle (a_{0},a_{1},\dots ,a_{n-1})}$ ${\displaystyle C}$ ${\displaystyle (a_{1},a_{2},\dots ,a_{n-1},a_{0})}$ ${\displaystyle C}$ ${\displaystyle (a_{2},a_{3},\dots ,a_{n-1},a_{0},a_{1}),(a_{3},a_{4},\dots ,a_{n-1},a_{0},a_{1},a_{2}),\ldots ,(a_{n-1},a_{0},a_{1},\ldots ,a_{n-2})}$ ${\displaystyle C}$

Polynomial representation

Cyclic codes of length can be described as ideals of the ring . The characters of a code word are regarded as coefficients of a polynomial : ${\displaystyle n}$ ${\displaystyle R:=\mathbb {F} _{q}[x]/(x^{n}-1)}$ ${\displaystyle a}$ ${\displaystyle a(x)}$

${\displaystyle (a_{0},a_{1},a_{2},\dots ,a_{n-1})\leftrightarrow a_{0}+a_{1}x+a_{2}x^{2}+\dots +a_{n-1}x^{n-1}}$.

Elements of the ring are residual classes of polynomials with respect to the polynomial division by . Each coset has an excellent element of degree less , which is used to designate the residue class: . Multiplication with and reduction modulo lead to the polynomial ${\displaystyle R}$ ${\displaystyle x^{n}-1}$ ${\displaystyle n}$ ${\displaystyle a(x)=a_{0}+a_{1}x+\dots +a_{n-1}x^{n-1}}$ ${\displaystyle x}$ ${\displaystyle x^{n}-1}$

${\displaystyle x\,a(x)\mod x^{n}-1=a_{n-1}+a_{0}x+\dots +a_{n-2}x^{n-1}}$,

which just has the cyclically shifted coefficient sequence. The property of being cyclic means in the polynomial ring that the code is closed against multiplication with and thus with monomials of any degree. ${\displaystyle C}$ ${\displaystyle x}$

Since the code is also linear, i.e. contains multiples and sums of code words, it follows that with a polynomial the coefficient sequences of all polynomials are also contained in the code, i.e. the code corresponds to an ideal in the ring. ${\displaystyle C}$ ${\displaystyle a(x)}$ ${\displaystyle b(x)a(x)\mod x^{n}-1}$

Since there is a main ideal ring , the ideal that is generated by and the polynomials that correspond to code words is already generated by a polynomial of the lowest degree contained therein (generator polynomial ). This is always a divider of . So if you know all of the polynomials of , you also know all the cyclic linear codes in . The codes that correspond to the irreducible factors are of particular interest . ${\displaystyle \mathbb {F} _{q}[x]}$ ${\displaystyle (x^{n}-1)}$ ${\displaystyle g(x)}$ ${\displaystyle (x^{n}-1)}$ ${\displaystyle (x^{n}-1)}$ ${\displaystyle \mathbb {F} _{q}^{n}}$

Encoding and decoding

Coding

The generator polynomial has degree . The code then has the dimension . A plaintext word is coded into a code word either by multiplication or by division : ${\displaystyle g(x)}$ ${\displaystyle n-k}$ ${\displaystyle k}$ ${\displaystyle w\leftrightarrow w(x)=w_{0}+\dots +w_{k-1}x^{k-1}}$ ${\displaystyle c(x)}$

multiplication

The multiplication by the obvious method: . ${\displaystyle g(x)}$ ${\displaystyle c(x)=w(x)\cdot g(x)}$

division

The ring is a Euclidean ring with respect to the polynomial division. Therefore the polynomials and with are uniquely determined in the equation ( is calculated using polynomial division). The word is then coded after . ${\displaystyle R}$ ${\displaystyle w(x)\cdot x^{n-k}=q(x)\cdot g(x)+r(x)}$ ${\displaystyle q(x)}$ ${\displaystyle r(x)}$ ${\displaystyle {\text{Grad}}(r(x))<{\text{Grad}}(g(x))}$ ${\displaystyle r(x)}$ ${\displaystyle w(x)}$ ${\displaystyle c(x)=w(x)\cdot x^{n-k}-r(x)}$

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

Decoding

A received word is divided by. If the remainder is zero, the code was already out of the code. If the remainder is not equal to zero, an error occurred during the transfer. The rest corresponds to the syndrome , the word can then be decoded with the help of a syndrome table. ${\displaystyle b(x)}$ ${\displaystyle g(x)}$ ${\displaystyle b(x)}$

In terms of circuitry, this means that the same circuits can be used - by and large - for coding by means of division and for decoding.

Realizations

Cyclic code generator in the form of an LFSR

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

In the figure opposite, a cyclic (15,11) hammering encoder with the generator polynomial z ⁴  +  z  + 1 is shown. In the encoder, the user data bits d are read in as a serial data stream in the top center and the code word c is output serially on the right. The switches are initially in position A : This means that the data bits in the code word are initially output directly and simultaneously pushed into the LFSR. When all data bits of a data word have been read in, the two switches change to position B : The content of the LFSR that corresponds to the test points p is now output bit by bit . When all test points have been issued, the process is repeated. For the sake of simplification, the necessary clock lines and synchronization circuits are not shown in the circuit diagram.

The decoding of cyclic code on the receiver side can be done using LFSR, with syndrome decoding mostly being used .

Examples

In addition to the cyclic Hamming codes mentioned, there are special cyclic variants of the Reed-Solomon codes that are used, among other things, in the data format of the CD-ROM . Another special case of the latter are the codes that are used in the cyclical 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.