Generatorpolynom

Generatorpolynom, in coding theory, is a polynomial that generates a cyclic code. For a cyclic code of length n over a finite field F, the code can be viewed as an ideal of the quotient ring F[x]/(x^n - 1). Each cyclic code has a unique monic generator polynomial g(x) that divides x^n - 1. The code consists of all multiples a(x) g(x) modulo x^n - 1. The degree of g(x) equals n − k, where k is the dimension of the code, so g(x) fixes the amount of redundancy.

Encoding is performed by multiplying the message polynomial by g(x) modulo x^n - 1; decoding uses g(x) in error detection and correction using syndromes, etc.

Generatorpolynom is also used in the design of linear feedback shift registers (LFSRs) to produce pseudo-random sequences. In that setting the generator (or feedback) polynomial describes which register taps are connected to the input; if the polynomial is primitive over GF(2), the sequence has maximal period 2^m - 1.

Example: A binary cyclic [7,4] code with g(x) = x^3 + x + 1, which divides x^7 - 1 in GF(2)[x], yields codewords of length 7; the code consists of multiples of g(x).

Notes: The term can sometimes be used loosely to refer to any generating polynomial in sequence generation or convolutional coding; the precise mathematical definition depends on the coding context.