ELE5TEL 1

Telecommunications Engineering

Dr. David Tay

Room BG434
x 2529
d.tay@latrobe.edu.au

DT
ELE5TEL 114

Channel Coding I
• Signal transformation to improve communication perfor-
mance by making signals robust to noise, interference
and fading.

• Two types of channel coding:

1. Waveform coding: transforms waveform into ’better
waveforms’ to improve detection.
2. Structures sequences: transforms data sequences into
’better sequences’ by inserting redundancy. Redun-
dant bits used for detecting and/or correcting errors.

Waveform coding
• Try to make the encoded waveforms to be as different
from each other as possible.

• Cross-correlation
T
1
Z
zij = si (t)sj (t)dt
E 0

where E is the energy. Make zij as small as possible for

all pairs of i and j (i 6= j).

• Minimum zij = −1 possible only for M = 2 with antipo-

dal signal s1 = −s2 .

DT
ELE5TEL 115

• Possible to have zij = 0 for M > 2, i.e. orthogonal sig-

nalling.

• Popular types of waveform codes

1. Orthogonal: zij = 0 for all i 6= j which can be con-

structed using the Hadamard matrix.
2. Biorthogonal codes: a combination of orthogonal and
antipodal signals, i.e. zij = 0 or zij = −1.

• see book for more details on waveform coding

Structured sequences

Types of error control in structured sequences

1. Error detection (with possible retransmission).

2. FEC (Forward Error Correction).

Types of terminal connectivity: simplex, half-duplex, full du-

plex

DT
ELE5TEL 116

Different types of Automatic Repeat Request (ARQ) with

type 1 error control: see book for details.
Categories of structured sequences coding:

1. Block (including cyclic) - this chapter.

2. Convolutional - next chapter.

3. Turbo - not covered (chapter 8).

DT
ELE5TEL 117

Channel models

Mathematical/Statistical models of the effect of noise on the

transmission of digital symbols

1. Binary symmetric channel (BSC): two possible symbols

at input and output, namely 0 and 1.

P (0/1) = P (1/0) = p

P (0/0) = P (1/1) = 1 − p
symmetric probability for the two symbols.

2. Discrete memoryless channel (DMC): generalization of

BSC - see book for details.

3. Gaussian channel: used in soft decision decoding - see

book for details.

Code rate and redundancy

• For block codes, source data bits are partitioned into

blocks of k data bits.

• k bits −→ n bits (code bits).

• (n − k) bits are added to each block, i.e. redundant bits,

parity bits.

DT
ELE5TEL 118

• Code is known as (n, k) code.

(n − k)
Redundancy =
k
k
Code rate = ≤1
n

Parity-check codes (see book)

• single parity check codes.

• rectangular code.

Linear block codes:

• Uses the rules for binary field arithmetic

1. Addition:

0 ⊕ 0 = 0, 1 ⊕ 0 = 1, 0 ⊕ 1 = 1, 1 ⊕ 1 = 0

2. Multiplication:

0.0 = 0, 1.0 = 0, 0.1 = 0, 1.1 = 1

• A linear map from a k dimension binary vector (also

known as k-tuple) into a n dimension binary vector (also
known as n-tuple).

DT
ELE5TEL 119

• The theory uses concepts of vector space and vector sub-

space from abstract algebra - see book for details.

• Simple example with k = 3 and n = 6.

• There are 2k (= 23 = 8) possible distinct k-tuple mes-

sage.

• Two important properties of any linear block code:

– The all zero vector ([000000]) must be a codeword.
– Adding any two valid codeword will give another valid
codeword.
– Example [110100] + [011010] = [101110]

DT
ELE5TEL 120

• Only 2k (8) out of the 2n (= 26 = 64) n-tuples are valid

codewords. The remaining n-tuples (2n − 2k = 64 − 8 =
56) are invalid codewords.

• For example [100001] and [100011] are invalid.

• During transmission, noise and other interference per-

turbs the original codeword V into another vector V′ .
For example
[101001] −→ [100001]

• Now V is a valid codeword (from the table) but V′ may

not be in the table, i.e invalid.

• If V′ is not valid, we know an error has occured and

it is possible to recover V exactly if V′ is not too far
(different) from V.

Generator matrix
• Efficient way to perform encoding.

• Use basis of subspace to generate the codeword U:

U = m1 V1 + m2 V2 + . . . + mk Vk

where the basis vectors set {V1 , V2 , . . . , Vk } is a linearly

independent set of vectors that spans the subspace S.
mi = 0 or 1 are the message bits.

DT
ELE5TEL 121

• Generator matrix is defined as

   
V v v12 ... v1n
 1   11 
 V2   v21 v22 ... v2n
   

G=  ..  =  ..
  

 .   . 
   
Vk vk1 vk2 ... vkn

• Message vector is defined as

m = [ m1 m2 ... mk ]

• Codeword vector U is generated as follows

U = mG

Example
   
V1 1 1 0 1 0 0
   
 V2  =  0
G=   1 1 0 1 0 

V3 1 0 1 0 0 1

m=[ 1 1 0 ]
 
V1
 
U = [ 1 1 0 ]
 V2


V3

DT
ELE5TEL 122

= V1 + V2 = [ 1 0 1 1 1 0 ]

Encoder need only store k rows of G instead of the 2k vectors

in a look-up table.

Systematic linear block codes

• Part of the n-tuple codeword coincide exactly with the k

message bit.

• Generator matrix of the form

 
p p12 . . . p1,(n−k) 1 0 ... 0
 11 
 p21 p22 . . . p2,(n−k) 0 1 ... 0
 

G = [ P | Ik ] = 
 .. .. .. ..

.

 . . . 
 
pk1 pk2 ... pk,(n−k) 0 0 ... 1

where P is the parity array portion of the G matrix.

• If m = [ m1 m2 ... mk ]

U = [ p1 p2 ... pn−k m1 m2 ... mk ]

where the first part contain the parity bits and the second
part contain the message bits.

DT
ELE5TEL 123

Example: (6,3) code

 
1 1 0 1 0 0
 
U = [ m1 m2 m3 ] 
 0 1 1 0 1 0 

1 0 1 0 0 1

= [ (m1 + m3 ) (m1 + m2 ) (m2 + m3 ) m1 m2 m3 ]

Parity check matrix

• Enable decoding of received vectors.

• Orthogonal to G matrix:

G HT = 0

rows of G are orthogonal to rows of H.

• For systematic code G = [ P | Ik ]

H = [ In−k | PT ]

• If U is a valid codeword, i.e. U = m G, then:

UHT = m GHT = 0

H can be used to check the validity of a codeword.

DT
ELE5TEL 124

Syndrome testing

• Suppose during transmission

U −→ r = U + e

where r is the received vector and e is the error pattern.

• Syndrome of r is defined as

S = rHT = (U + e)HT = UHT + eHT

Since UHT = 0
S = eHT

the syndrome depends only on the error pattern.

• The syndrome tells us something about the transmission

error. If S 6= 0, then there is definitely an error.

Example:
U=[ 1 0 1 1 1 0 ]

r=[ 0 0 1 1 1 0 ]

DT
ELE5TEL 125

 
1 0 0
 

 0 1 0 

 
 0 0 1 
S=[ 0 0 1 1 1 0 ] =[ 1 0 0 ]
 

 1 1 0 

 

 0 1 1 

1 0 1

e = [ 1 0 0 0 0 0 ] ⇒ S = eHT gives the same re-

sults.
Example: Consider a systematic block code whose parity-
check equations are

p1 = m1 + m2 + m4
p2 = m1 + m3 + m4
p3 = m1 + m2 + m3
p4 = m2 + m3 + m4

where mi are the message bits and pi are the check bits.

(a) Determine the generator matrix and parity check matrix.

(b) Is the vector [10101010] a valid codeword?

(c) Is the vector [01011100] a valid codeword?

DT
ELE5TEL 126

Solution:
(a)
 
1 1 1 0 1 0 0 0
 
 1 0 1 1 0 1 0 0 
G = [ P | Ik ] = 
 

 0 1 1 1 0 0 1 0 
 
1 1 0 1 0 0 0 1
 
1 0 0 0 1 1 0 1
 
 0 1 0 0 1 0 1 1 
T
H = [ In−k | P ] = 
 

 0 0 1 0 1 1 1 0 
 
0 0 0 1 0 1 1 1

(b) S = r HT = [1 0 1 0 1 0 1 0] HT = [0 0 1 1] NOT
VALID.

(c) S = r HT = [0 1 0 1 1 1 0 0] HT = [0 0 0 0] VALID.

Error correction
• Construct the standard array as follows:

1. First row contains all valid codewords U1 , U2 , . . . , U2k

with U1 = 0 as first element.
2. First column contains all the error patterns that are
correctable e2 , e3 , . . . , e2n−k .

DT
ELE5TEL 127

3. The elements of subsequent rows are obtained by adding

the elements from the first row to the error pattern
of that row (first element).

Each row is known as a coset and the first element (error

pattern) is known as the coset leader.

• The standard array contains all possible n-tuple vectors.

• Each of the 2n possible vectors appears only once in the

array.

• Decoding algorithm replaces a corrupted vector with a

valid codeword from the top of the column.

• Only error patterns that are coset leaders are correctable.

• The syndrome of all elements of a coset is the same.

DT
ELE5TEL 128

• Different cosets (rows) have different syndromes.

• The syndrome is used to estimate the error pattern.

Error correction decoding procedure

1. Calculate syndrome of r

S = rHT

2. Locate coset leader (error pattern) ej whose syndrome

equals S.

3. Use error pattern ej to correct error

Û = r + ej (= r − ej )

Example: (6,3) code.

DT
ELE5TEL 129

All 1 bit error pattern correctable. Syndrome look-up table:

Decoding example:

U=[ 1 0 1 1 1 0 ]
transmitted codeword.

r=[ 0 0 1 1 1 0 ]
received codeword.
Syndrome calculated earlier using H shown earlier

S = rHT = [ 1 0 0 ]

DT
ELE5TEL 130

Using lookup table

ê = [ 1 0 0 0 0 0 ]

Decoded vector

Û = r + ê = [ 1 0 1 1 1 0 ]=U

correct decoding.
Question: Is it possible a non-zero error pattern produce a
syndrome S = 0? Explain. If yes, how many such error
pattern can give this results for a given (n, k)?
Answer: YES. If the error pattern itself is a valid codeword,
e.g. e = [110100] from the example in figure 6.11, then the
syndrome S = 0 by definition. There are 2k valid codeword
and only one is the zero vector. Therefore there are 2k − 1
such error patterns.
These error patterns are known as undetectable errors. The
aim of designing good codes is to ensure these error patterns
do not occur frequently.

Decoder implementation

Decoder must perform the following steps:

1. Calculate syndrome.

DT
ELE5TEL 131

2. Locate error pattern.

3. Correct for error in the received vector.

can be performed with simple digital circuits - see book for

details.

Cyclic codes

• Important subclass of linear block codes.

• Efficient implementation using feedback shift registers.

• Property - cyclic shift of bits of a valid codeword yields

another codeword. If

U = [ u0 u1 ... un−1 ]

then
U(1) = [ un−1 u0 u1 ... un−2 ]
is also a code. Any number of shifts will yield a valid
codeword.

• Use a polynomial function in variable X to describe cyclic

codes, e.g. polynomial representing U

U(X) = u0 + u1 X + u2 X 2 + . . . + un−1 X n−1

DT
ELE5TEL 132

Algebraic structure of cyclic codes:

• U(X) is a degree (n − 1) polynomial.

• Consider X i U(X) (i < n) divided by X n + 1

X i U(X) U(i) (X)

= q(X) + n
Xn + 1 X +1
(i)
(X)
where q(X) is the quotient and UX n +1 is the remainder.
The equation can also be written as

X i U(X) = q(X)(X n + 1) + U(i) (X)

or
U(i) (X) = X i U(X) modulo (X n + 1)

• The remainder U(i) (X) is also a codeword.

Example: U = [ 1 1 0 1 ] (n = 4).

U(X) = 1 + X + X 3

With i = 3
X i U(X) = X 3 + X 4 + X 6
Divide X 3 U(X) by (X 4 + 1) using long division (see end of
notes for details) gives

q(X) = X 2 + 1

DT
ELE5TEL 133

U(3) (X) = 1 + X 2 + X 3

U(3) = [ 1 0 1 1 ]

can be obtained by 3 cyclic shifts of U = [ 1 1 0 1 ].

Cyclic code properties

• Can generate a cyclic code using a generator polynomial

g(X) = g0 + g1 X + g2 X 2 + . . . + gp X p

• Given the message polynomial

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

where m0 , m1 , m2 , . . . are the message bits.

• The codeword polynomial is given by

U(X) = m(X)g(X) = u0 +u1 X +u2 X 2 +. . .+un−1 X n−1

where u0 , u1 , u2 , . . . are the codeword bits. The value of

p = n − k.

• Every valid codeword polynomial U(X) has g(X) as a

factor.

• g(X) is also a factor of (X n + 1).

DT
ELE5TEL 134

Encoding in systematic form

U = [ p0 p1 ... pn−k−1 m0 m1 ... mk−1 ]

Let

p(X) = p0 + p1 X + p2 X 2 + . . . + pn−k−1 X n−k−1

Multiply m(X) with X n−k will give a right-shifted message

polynomial

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

Add p(X) to X n−k m(X) to give the codeword U(X)

U(X) = p(X) + X n−k m(X)

= p0 + p1 X + . . . + pn−k−1 X n−k−1
+m0 X n−k + m1 X n−k+1 + . . . + mk−1 X n−1

But for cyclic code; U(X) = q(X)g(X). Therefore

p(X) + X n−k m(X) = q(X)g(X)

⇒ X n−k m(X) = q(X)g(X) + p(X)

p(X) = X n−k m(X) modulo g(X)
remainder after dividing with g(X).

DT
ELE5TEL 135

Example: (7,4) cyclic code with

g(X) = 1 + X + X 3

Message m = [ 1 0 1 1 ]

m(X) = 1 + X 2 + X 3

X n−k m(X) = X 3 (1 + X 2 + X 3 ) = X 3 + X 5 + X 6

Dividing X n−k m(X) by g(X) gives

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

• (1 + X + X 2 + X 3 ): quotient.

• (1 + X + X 3 ): generator.

• 1: remainder.

Codeword polynomial

U(X) = p(X) + X 3 m(X) = 1 + X 3 + X 5 + X 6

U=[ 1 0 0 1 0 1 1 ]

Circuits for dividing polynomials using feedback shift register

(see book for more details).
Systematic encoding with using feedback shift register (see
book for more details).

DT
ELE5TEL 136

Error detection with shift register

• Need to be able to calculate syndrome.

• Suppose codeword transmitted is U(X) and received vec-

tor (possibly corrupted by noise) is

Z(X) = U(X) + e(X)

where e(X) is the error pattern.

• Syndrome S(X) is calculated by dividing Z(X) with g(X)

Z(X) = q(X)g(X) + S(X)

• Combining the two equations above with the fact that

U(X) = m(X)g(X) we obtain:

e(X) = [m(X) + q(X)]g(X) + S(X)

• The remainder from Z(X) and e(X) are the same which
is S(X). Hence the syndrome obtained from dividing
Z(X) by g(X) will give information about the error.

• The syndrome calculation can be achieved by using the

similar dividing circuit used in the transmitter.

DT
ELE5TEL 137

Well known block codes

1. Hamming codes

(n, k) = (2m − 1, 2m − 1 − m)

where m = 2, 3, . . ..

2. Extended Golay code

(n, k) = (24, 12)

(see book for details)

3. BCH codes (cyclic codes)

• Bose-Chadhuri-Hocquenghem codes are a generaliza-

tion of Hamming codes.
• At block lengths of a few hundred, BCH codes outper-
form all other block codes with the same block length
and code rate.

(see book for details)

4. Reed-Solomon codes

• A subclass of BCH codes and are non-binary.

• Used in CD audio system.

(see chapter 8 for more details).

DT
ELE5TEL 138

Example: Encode the message 1 0 1 in systematic form using

polynomial division and the generator g(X) = 1 + X + X 2 +
X 4.
Solution: k = 3, n − k = 4, n = 7

m(X) = 1 + X 2

X n−k m(X) = X 4 (1 + X 2 ) = X 4 + X 6

Dividing X n−k m(X) by g(X) gives

X 4 + X 6 = X 2 (1 + X + X 2 + X 4 ) + (X 2 + X 3 )

• X 2 : quotient.

• 1 + X + X 2 + X 4 : generator.

• X 2 + X 3 : remainder.

Codeword polynomial

U(X) = p(X) + X 4 m(X) = X 2 + X 3 + X 4 + X 6

U=[ 0 0 1 1 1 0 1 ]

DT
ELE5TEL 139

Example: A (15,5) cyclic code has a generator polynomial as

follows:

g(X) = 1 + X + X 2 + X 5 + X 8 + X 10

(a) Find the code polynomial (in systematic form) for the
message m(X) = 1 + X 2 + X 4 .

(b) Is V(X) = 1 + X 4 + X 6 + X 8 + X 14 a valid code poly-

nomial? Justify.

Solution:
(a)

X n−k m(X) = X 10 (1 + X 2 + X 4 ) = X 10 + X 12 + X 14

Dividing X n−k m(X) by g(X) gives

X 10 +X 12 +X 14 = (1+X 4 )(1+X +X 2 +X 5 +X 8 +X 10 )

+(1 + X + X 2 + X 4 + X 6 + X 8 + X 9 )

Remainder is 1 + X + X 2 + X 4 + X 6 + X 8 + X 9 .
Codeword polynomial

U(X) = p(X) + X 10 m(X)

= 1 + X + X 2 + X 4 + X 6 + X 8 + X 9 + X 10 + X 12 + X 14

DT
ELE5TEL 140

(b) Divide V(X) by g(X)

1 + X 4 + X 6 + X 8 + X 14
2 5 8 10
= (1 + X 2 + X 4 )
1+X +X +X +X +X

X + X3 + X4 + X7 + X9
+
1 + X + X 2 + X 5 + X 8 + X 10
Remainder not zero, NOT A VALID CODEWORD.

Exercise to try yourself from texbook: problems 6.8,

6.10 (a) and (b) only (page 376), 6.34 (a) - (d) only
(page 379). Solution will be provided at a later date on
LMS.

DT