66 ALGEBRAIC CODING THEORY
Generator polynomial
■ The cyclic code B(n,k,d)is defined by the unique generator polynomial
g(z) = g
0
+ g
1
z +···+g
n−k−1
z
n−k−1
+ g
n−k
z
n−k
(2.59)
of minimal degree deg(g(z)) = n − k with g
n−k
= 1.
■ Non-systematic encoding
b(z) = u(z) g(z) (2.60)
■ Systematic encoding
b
0
+ b
1
z +···+b
n−k−1
z
n−k−1
≡−z
n−k
u(z) mod g(z) (2.61)
Figure 2.39: Encoding of a cyclic code with the help of the generator polynomial g(z)
The non-systematic and systematic encoding schemes for this cyclic binary Hamming code
are illustrated in Figure 2.40.
Cyclic Redundancy Check
With the help of the generator polynomial g(z) of a cyclic code B(n,k,d), the so-called
cyclic redundancy check (CRC) can be defined for the detection of errors (Lin and Costello,
2004). Besides the detection of e
det
= d − 1 errors by a cyclic code B(n,k,d) with min-
imum Hamming distance d, cyclic error bursts can also be detected. With a generator
polynomial g(z) of degree deg(g(z)) = n − k, all cyclic error bursts of length
burst
≤ n − k
can be detected (Jungnickel, 1995). This can be seen by considering the error model r(z) =
b(z) + e(z) with the received polynomial r(z), the code polynomial b(z) and the error
polynomial e(z) (see also Figure 2.46). Errors can be detected as long as the parity-check
equation
g(z) |r(z) ⇔ r(z) ∈ B(n,k,d)
of the cyclic code B(n,k,d) is fulfilled. Since g(z)|b(z), all errors for which the error
polynomial e(z) is not divisible by the generator polynomial g(z) can be detected. As long
as the degree deg(e(z)) is smaller than deg(g(z)) = n − k, the error polynomial e(z) cannot
be divided by the generator polynomial. This is also true if cyclically shifted variants z
i
e(z)
of such an error polynomial are considered. Since for an error burst of length
burst
the
degree of the error polynomial is equal to
burst
− 1, the error detection is possible if
deg(e(z)) =
burst
− 1 <n− k = deg(g(z)).