Lecture “Channel Coding”

Chapter 6: Cyclic Codes

Prof. Dr.-Ing. Antonia Wachter-Zeh

x
Outline of this Chapter

1. Cyclic Codes:
Definition
Examples
Generator and parity-check polynomials
Generator and parity-check matrices

2. Structure of Finite Fields:

Cyclotomic cosets
Minimal polynomials

3. BCH Codes:
Definition
BCH bound
Known codes as BCH codes
Golay codes
Decoding

Antonia Wachter-Zeh (TUM) 2

Outline

Cyclic Codes

Structure of Finite Fields

BCH Codes

Antonia Wachter-Zeh (TUM) 3

Cyclic Codes: Definition
Definition: Cyclic Code
A linear block code is cyclic, if any cyclic shift of a codeword is again a codeword, i.e.,
(c0 , c1 , . . . , cn−1 ) ∈ C =⇒ (cn−1 , c0 , . . . , cn−2 ) ∈ C.

Polynomial description:
• We associate the vector c = (c0 , c1 , . . . , cn−1 ) ∈ Fnq with the polynomial
c(x ) := c0 + c1 x + c2 x 2 + · · · + cn−1 x n−1
• A cyclic shift is then given by
cn−1 + c0 x + · · · + cn−2 x n−1 = x · c(x ) − cn−1 · (x n − 1) = x · c(x ) mod (x n − 1)
=⇒ A linear code is cyclic if and only if
c(x ) ∈ C =⇒ x · c(x ) mod (x n − 1) ∈ C.
• By linearity, for every a(x ) ∈ Fq [x ]:

c(x ) ∈ C =⇒ a(x ) · c(x ) mod (x n − 1) ∈ C.

Antonia Wachter-Zeh (TUM) 4

Cyclic Codes: Examples

• Repetition codes are cyclic.

• Single Parity Check codes are cyclic.

Primitive RS codes are cyclic:

• We have n | q − 1, α is an element of order n, αi = αi , i = 0, . . . , n − 1, and ν00 , . . . , νn−1
0
=1
 
1 α ... αn−1
α2 α2(n−1) 
 
1 ...
=⇒ H RS =
.
 .. .. ... ..


 . . 

1 αn−k . . . α(n−1)(n−k)
• The vector representation H RS · c T = 0 implies that c(α) = c(α2 ) = · · · = c(αn−k ) = 0.
• Let c(x
e ) := x · c(x ) − cn−1 · (x n − 1) = x · c(x ) mod (x n − 1)
`
=⇒ Then, c(α
e ) = α` · c(α` ) − cn−1 ((α` )n − 1) = α` · c(α` )
`
=⇒ c(α
e ) = 0 for ` = 1, . . . , n − k
=⇒ c(x
e ) is also a codeword of the RS code.

Antonia Wachter-Zeh (TUM) 5

Cyclic Codes: Generator Polynomial
Theorem: Generator Polynomial
Let C be a cyclic [n, k, d]q code. Then, there is a unique monic polynomial g(x ) such that for every
c(x ) ∈ Fq [x ] of degree n − 1:
c(x ) ∈ C ⇐⇒ g(x ) | c(x ).

[Proof: see blackboard]

• This polynomial is called generator polynomial.

=⇒ C = {u(x )g(x ) : u(x ) ∈ Fq [x ] and deg u(x ) < k}
• deg g(x ) = n − k

Lemma
Let g(x ) be the generator polynomial of a cyclic [n, k, d]q code. Then, g(x )|(x n − 1).

[Proof: see blackboard]

Antonia Wachter-Zeh (TUM) 6
Cyclic Codes: Parity-Check Polynomial

Definition: Parity-Check Polynomial

Let g(x ) be the generator polynomial of a cyclic [n, k, d]q code. The parity-check polynomial h(x ) is
the monic polynomial of degree k obtained by:
xn − 1
h(x ) := .
g(x )

Lemma: Generator Polynomial of Dual Code

Let C be a cyclic [n, k, d]q code and let h(x ) be its parity-check polynomial. Then, the dual code of C is a
cyclic [n, n − k, d ⊥ ]q code with generator polynomial

⊥ x k h(x −1 )
g (x ) = .
h(0)

Antonia Wachter-Zeh (TUM) 7

Cyclic Codes: Examples
• [n, 1, n]2 Repetition Code:
I u(x ) = u0
I g(x ) = 1 + x + x 2 + · · · + x n−1
n
I h(x ) = xg(x−1) = x − 1

• [n, n − 1, 2]2 Single Parity Check Code:

I Dual code to the repetition code.
k −1
I g(x ) = x hhRP (x )
=x −1
RP (0)
n
I h(x ) = xg(x−1) = i=1 (x − αi ) = 1 + x + x 2 + · · · + x n−1
Q n−1

• RS(n, k) Primitive RS Code over Fq where n | q − 1 and ord(α) = n:

I From Slide 5: c(α` ) = 0 for ` = 1, . . . , n − k
I g(x ) = (x − α) · (x − α2 ) · · · (x − αn−k )
n
I h(x ) = xg(x−1) = (x − αn−k+1 ) · · · (x − αn−1 ) · (x − 1)
I g ⊥ (x ) = (x − 1) · (x − α) · · · (x − αk−1 ) 6= h(x )

Antonia Wachter-Zeh (TUM) 8

Cyclic Codes: Generator and Parity-Check Matrix
• For g(x ) = g0 + g1 x + · · · + gn−k x n−k , calculating u(x ) · g(x ) is equivalent to:
 
g g1 . . . gn−k
 0 

g 0 g 1 . . . gn−k

(u0 , u1 , . . . , uk−1 ) · 
 


. . . . . . . . . . . .



 
g0 g1 . . . gn−k
| {z }
=:G
=⇒ G is a generator matrix

Theorem: Parity-Check Matrix

Let C be a cyclic [n, k, d]q code with parity-check polynomial h(x ) = h0 + h1 x + · · · + hk x k . The (n − k) × n
matrix  

h k hk−1 . . . h 0 

hk h k−1 . . . h 0

H=
 


. .. . .. . .. . ..



 
hk hk−1 . . . h0
is a parity-check matrix of C.
Antonia Wachter-Zeh (TUM) 9
Outline

Cyclic Codes

Structure of Finite Fields

BCH Codes

Antonia Wachter-Zeh (TUM) 10

Structure of Finite Fields: Cyclotomic Coset
Definition: Cyclotomic Coset
Let n divide q s − 1, for some integer s, then the cyclotomic coset Ci with respect to n is defined by:
Ci := {i · q j mod n, ∀j = 0, 1, . . . , ni − 1},
where ni is the smallest integer such that i · q ni = i mod n.

Properties:
• |Ci | ≤ s
• Ci ∩ Cj = ∅ or Ci = Cj
• C0 = {0}
• i Ci = {0, 1, . . . , n − 1}.
S

Example: q = 2, n = 15, i = 0, 1, 3, 5, 7. [See blackboard]

Antonia Wachter-Zeh (TUM) 11

Structure of Finite Fields: Minimal Polynomial
Definition: Minimal Polynomial
Let α be an element of Fqs of order n and let Ci be the i-th cyclotomic coset with respect to n. Then,
(x − αj )
Y
mi (x ) =
j∈Ci

is called the minimal polynomial of αi .

Properties:
• deg mi (x ) = |Ci |
• α ∈ Fqs , but mi (x ) ∈ Fq [x ] [Proof: see blackboard]
• mi (x ) is irreducible
• mi (x )|(x n − 1) since x n − 1 = nj=1 (x − αj )
Q

(Continued) Example: q = 2, n = 15, i = 0, 1, 3, 5, 7.

[See blackboard]
Antonia Wachter-Zeh (TUM) 12
Outline

Cyclic Codes

Structure of Finite Fields

BCH Codes

Antonia Wachter-Zeh (TUM) 13

BCH Codes: Definition

Definition: BCH Code

Let D = Ci1 ∪ Ci2 ∪ · · · ∪ Ci` be the union of ` ≥ 1 distinct cyclotomic cosets with respect to n (which
divides q s − 1). Let α ∈ Fqs be an element of order n. Then, an [n, k, d]q BCH code is defined by the
following generator polynomial:
(x − αi ).
Y
g(x ) =
i∈D

• n | (q s − 1) implies that gcd(n, q) = 1. For example, there are no even-length binary BCH codes.
• Since the i range over a union of cyclotomic cosets, g(x ) ∈ Fq [x ] and the BCH code is a q-ary code.
• deg g(x ) = n − k = |D| = `j=1 |Cij |
P

=⇒ k = n − |D|, not all values from {1, . . . , n} are possible for k.

• When n = q s − 1, it is called a primitive BCH code.

Antonia Wachter-Zeh (TUM) 14

BCH Codes: The BCH Bound

What is the minimum distance d of a BCH code constructed by g(x ) = i∈D (x − αi )?

Q

Theorem: The BCH Bound

Let C be an [n, k, d]q cyclic code (BCH code) where n | (q s − 1) and α is an element of order n. Assume
that {b, b + 1, . . . , b + δ − 2} ⊆ D for some integers b, δ ≥ 2. Then d ≥ δ.

Proof:
• g(x
e ) := (x − αb ) · · · (x − αb+δ−2 ) divides g(x )
• g(x
e ) is the generator polynomial of an RS(n, n − δ + 1) code over Fqs of minimum distance δ with
αj = αj and νj = αbj for j = 0, . . . , n − 1.
• Every codeword of C is a codeword of RS(n, n − δ + 1).
=⇒ d ≥ δ.

Antonia Wachter-Zeh (TUM) 15

BCH Codes: The BCH Bound and Subfield Subcodes

=⇒ δ − 1 consecutive roots give a minimum distance of at least δ.

However, the true minimum distance d can be larger than the BCH bound δ. There are also better lower
bounds on the distance.

BCH Codes as Subfield Subcodes of RS Codes

Since every codeword of an [n, k, d ≥ δ]q BCH code C is also a codeword of an RS(n, n − δ + 1) code
over Fqs , the BCH code is a subfield subcode of the RS code. Namely,
C = Fnq ∩ RS(n, n − δ + 1),
i.e., all codewords of the RS code which lie in the subfield Fq are codewords of the BCH code.

Antonia Wachter-Zeh (TUM) 16

BCH Codes: Known Codes as Special BCH Codes

• [n, 1, n]2 Repetition Code:

I g(x ) = 1 + x + x 2 + · · · + x n−1 = Qn−1 i
i=1 (x − α )
=⇒ This is a BCH code with D = i\{0} Ci .
S

• [n, n − 1, 2]2 Single Parity Check Code:

I Dual code to the repetition code.
I g(x ) = x − 1
=⇒ This is a BCH code with D = C0 .

• [2m − 1, 2m − 1 − m, d = 3]2 Binary Hamming Code:

=⇒ The BCH code with D = C1 = {1, 2, 4, . . . , 2m−1 } is a Hamming code
I However, there is an equivalent non-cyclic Hamming code (by permuting the columns of H)
I BCH bound: {1, 2} ⊆ D, thus δ ≥ 3

Antonia Wachter-Zeh (TUM) 17

BCH Codes: The perfect Golay Codes
• [23, 12, 7]2 Binary Golay Code:
I n = 23 | (211 − 1), hence there is α ∈ F211 of order 23.
I C1 = {1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12}
I g(x ) = Qi∈C1 (x − αi ) = x 11 + x 9 + x 7 + x 6 + x 5 + x + 1
=⇒ k = n − |C1 | = 12.
I BCH bound: four consecutive roots 1, 2, 3, 4 give d ≥ δ = 5.
I However, the true minimum distance is d = 7.
I By the sphere-packing bound, this is a perfect code.

• [11, 6, 5]3 Ternary Golay Code:

I n = 11 | (35 − 1), hence there is α ∈ F35 of order 11.
I C1 = {1, 3, 9, 5, 4}
I g(x ) = Qi∈C1 (x − αi ) = x 5 + x 4 − x 3 + x 2 − 1
=⇒ k = n − |C1 | = 6.
I BCH bound: three consecutive roots 3, 4, 5 give d ≥ δ = 4.
I However, the true minimum distance is d = 5.
I By the sphere-packing bound, this is a perfect code.

Antonia Wachter-Zeh (TUM) 18

BCH Codes: Decoding

• Since every [n, k, d ≥ δ]q BCH code C is a subfield subcode of an RS(n, n − δ + 1) code over Fqs , we can
simply decode in the RS code.
I Unique decoding up to δ−1
j k
2 errors possible.
I List decoding up to the same radius as the RS(n, n − δ + 1) code.

• However, since the BCH code contains less codewords than the RS code and has a larger true minimum
distance, improvements are possible. (not topic of this lecture.)

Antonia Wachter-Zeh (TUM) 19