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

Let

C

{\displaystyle {\mathcal {C}}}

be a linear code over a finite field (also called Galois field)

G

F

(

q

)

{\displaystyle GF(q)}

of block length

n

{\displaystyle n}

.

C

{\displaystyle {\mathcal {C}}}

is called a cyclic code if, for every codeword

c

=

(

c

1

,

…

,

c

n

)

{\displaystyle c=(c_{1},\ldots ,c_{n})}

from

C

{\displaystyle {\mathcal {C}}}

, the word

(

c

n

,

c

1

,

…

,

c

n

−

1

)

{\displaystyle (c_{n},c_{1},\ldots ,c_{n-1})}

in

G

F

(

q

)

n

{\displaystyle GF(q)^{n}}

obtained by a cyclic right shift of components is again a codeword. Because one cyclic right shift is equal to

n

−

1

{\displaystyle n-1}

cyclic left shifts, a cyclic code may also be defined via cyclic left shifts. Therefore, the linear code

C

{\displaystyle {\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.