Cyclic Codes - Basic Terminology I

I We discuss cyclic codes, which is a subclass of linear binary block

codes where all codewords are cyclic shifts of one another. Given
u = [u0 , u1 , . . . , un−1 ], we have

u i = [un−i , un−i+1 , . . . , un−1 , u0 , u1 , . . . , un−i−1 ] (1)

I The generator polynomial g (X ) for an (n, k) cyclic code has de-
gree n − k and is formulated as

g (X ) = g0 + g1 X + g2 X 2 + · · · + gn−k X n−k , (2)

where g0 = gn−k = 1, gi ∈ {0, 1}.

I We also write the input message m in message polynomial form

m (X ) = m0 + m1 X + m2 X 2 + · · · + mk−1 X k−1 (3)

Hence we get the codeword polynomial as u (X ) = m (X )gg (X ).

Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 1 / 10
Cyclic Codes - Basic Terminology II
I Systematic cyclic codes are formed by firstly multiplying m (X ) by
X n−k

X n−k m (X ) = m0 X n−k + m1 X n−k+1 + · · · + mk−1 X n−1 (4)

I Add the remainder p (X ) = rem[X n−k m (X ), g (X )] to X n−k m (X )

hence

u (X ) = p0 + · · · + pn−k−1 X n−k−1 + m0 X n−k + · · · + mk−1 X n−1

(5)

I The message m are moved to the k rightmost digits of the code-

word u

u = [p0 , p1 , · · · , pn−k−1 , m0 , m1 , · · · , mk−1 ] (6)

Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 2 / 10

Cyclic Codes - Polynomial Encoding
Given g (X ) = 1 + X + X 3 , verify that for message m = [1011], the
systematic codeword from (7,4) cyclic code is u = [1001011], where
the code is also called BCH (7,4,3) code.
1. Express message m in polynomial form m (X ) = 1 + X 2 + X 3
2. Shift m (X ) by X n−k and arrive at X 3 (1+X 2 +X 3 ) = X 3 +X 5 +X 6
3. Find the reminder p (X ) = 1 since

X 3 + X 5 + X 6 = (1 + X + X 2 + X 3 )(1 + X + X 3 ) + 1 (7)

4. Add the remainder and we get

u (X ) = p (X ) + X n−k m (X ) = 1 + X 3 + X 5 + X 6 (8)

Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 3 / 10

Cyclic Codes - Shift Register Encoding
g(X) = 1 + X + X 3
Switch 1

r0 r1 r2

Output
m(X) = 1 + X 2 + X 3
Input
Switch 2
Operation
1. for the first k = 4 shifts, switch 1 close and switch 2 down, flush
k = 4 message bits to the output and initialise the shift register
2. for the remaining n − k = 3 shifts, switch 1 open and switch 2
up, flush the n − k = 3 parity bits to the output and empty the
shift register
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 4 / 10
Cyclic Codes - Shift Register Encoding
g(X) = 1 + X + X 3
Switch 1

r0 r1 r2

Output
Input Shift r0 , r1 , r2 Codeword m(X) = 1 + X 2 + X 3
1011 0 000 - Input
101 1 110 1 Switch 2

10 2 101 11
1 3 100 011
- 4 100 1011
- 5 010 01011
- 6 001 001011
- 7 000 1001011

Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 5 / 10

Cyclic Codes - State-Transition and Trellis Diagram
’0’
’1’ J=1J=2J=3J=4J=5J=6J=7
000 000
000
001 001
001
010 010
010
011 011
011
100 100 100

101 101 101

’0’ 110 110 110

’1’ 111 111 111

I We can see the encoding process always starts at the all-zero state
(shift 0) and ends at the all zero state (shift 7).
I For the first k = 4 shifts, the output is the same as the input.
I The number of states is equal to 2n−k = 8.
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 6 / 10
 ’0’
’1’ J=1J=2J=3J=4J=5J=6J=7
1 1 1 1 1 1 1
000 2 3 2 2

001 1 2 1 1

010 2 1 1

011 0

100 1

101 1 0

110 0

111 0
Received 1 0 0 0 0 0 0
Decoded 0 0 0 0 0 0 0

Figure: Error-free hard Viterbi decoding. Assume all zero was transmitted.
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 7 / 10
 ’0’
’1’ J=1J=2J=3J=4J=5J=6J=7
1 1 2 2 1 1 1
000 1 2 2 2

001 0 1 2 1

010 1 1

011 0 1 0

100

101 1

110 0 1 1

111

Received 1 0 1 0 0 0 0
Decoded 1 0 1 1 0 0 0

Figure: Erroneous hard Viterbi decoding. Assume all zero was transmitted.
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 8 / 10
 ’0’
’1’ J=1J=2J=3J=4J=5J=6J=7
-0.8 0.4 -0.2 2.0 2.4 3.7 4.6
000 0.4 2.0 0.3 3.6
2.6 2.4 1.6 4.5
001
0.2 1.2 3.2
010
2.0
011
-1.0
100
-0.4 3.6
101

110 0.8

111 1.4
Received 0.8 -1.2 0.6 -2.2 -0.4 -1.3 -0.9
(1) (0) (1) (0) (0) (0) (0)
Decoded 0 0 0 0 0 0 0

Figure: Error-free soft Viterbi decoding. Assume all zero was transmitted.
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 9 / 10
Summary

I Some concepts are important, such as generator polynomial, mes-

sage polynomial and codeword polynomial.
I The polynomial encoding for systematic cycle codes and the rela-
tion between polynomial encoding and shift register encoding.
I The operation of shift register encoding and its state-transition
as well trellis diagram.
I The hard and soft Viterbi decoding for cyclic codes (BCH codes
in particular).

Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 10 / 10