ECE 515

Information Theory

Simple Encoding and Decoding

 Equivalent Binary Linear Codes
Two binary linear codes are called equivalent if one can be
obtained from the other by permuting the positions of the
code.

Two k × n binary matrices generate equivalent linear codes if

one matrix can be obtained from the other by a sequence of
the following operations:
a) permutation of the rows
b) addition of one row to another
c) permutation of the columns

2
 Equivalent Codes
• Distances between codewords are unchanged by the
equivalence operations.

• Consequently, equivalent linear codes have the same

parameters (n,k,d)
• correct and detect the same number of errors

• Therefore the form of the code can be chosen to best

suit the application.

3
 Example (5,2,3) Codes
00111 11100 
G=   a) G' =  
11100   00111 

00111
b) G'' =  
 11011 

10110 
c) G''' =  
01101

4
 Systematic Codes
Let G be a generator matrix of an (n,k) code. Then by the
previous operations, G can be transformed into the form
[ Ik | P ]
where Ik is a k × k identity matrix, and P is a k × (n - k) matrix.

Example
1 1 1 1 1 1 1
1 0 0 0 1 0 1 
G= 
1 1 0 0 0 1 0
 
1 1 1 0 0 0 1

5
 Systematic Codes
Transforming G to systematic form

1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 0 1  0 1 1 1 0 1 0 
 →  →
1 1 0 0 0 1 0  0 0 1 1 1 0 1 
   
1 1 1 0 0 0 1 0 0 0 1 1 1 0

1 0 0 0 1 0 1 1 0 0 0 1 0 1
0 1 1 1 0 1 0  0 1 0 0 1 1 1 
 →  → ?
0 0 1 1 1 0 1 0 0 1 1 1 0 1
   
0 0 0 1 1 1 0 0 0 0 1 1 1 0

6
Systematic Codes

1 0 0 0 1 0 1
0 1 0 0 1 1 1 
→  [I4 P]
=
0 0 1 0 0 1 1 
 
0 0 0 1 1 1 0

7
 Systematic Codes
• For a systematic block code the data appears
unaltered in the codeword
• If the data is on the left, the generator matrix has
the structure
k n-k
1 0  0 p0,0 p0,1  p0,n−k −1 
0 1  0 p p  p 
G = 1,0 1,1 1,n − k −1 
[ Ik |P]
      
 
0 0  1 pk −1,0 pk −1,1  pk −1,n−k −1 

• P is often referred to as the parity matrix

8
Encoding with a Systematic Code
= m[Ik |=
c mG
= P ] (m|b)

1000 101 
0100 111 
=G =  [I P]
0010 011 4
 
 0001 110 
m 0111=
= c mG = m010
= 0111010
m 1011=
= c mG = m101
= 1011101
k n-k

data bits parity bits

(redundancy)
9
 Parity Check Matrix
• Define a parity check matrix H (n-k × n) such that
GHT = 0
• H is a basis for the dual space
• If G is in systematic form
G = [Ik P]
H = [-PT In-k] (= [PT In-k] in binary)
GHT = -P+P = 0
• Every codeword c satisfies the parity check equations given by
the rows of H
cHT = mGHT = 0

10
 Examples
• (3,1,3) Repetition code
1 1 0 
=G [1=
1 1] H  
1 0 1 
• (3,2,2) SPC code

 1 0 1
=G =  H [1 1 1]
 0 1 1

11
 Examples
• (8,7,2) SPC code

 1
 1 
 
 1
 
=G =
I7 1 H [11111111]
 1
 
 1
 1


12
Systematic Parity Check Matrices
If G = [Ik | P] is the generator matrix of a binary (n,k)
code C, then a parity check matrix for C is
H = [PT | In-k]

Example
 1 0 1 
  1 1 0 1 
1 1 1   
G  I4 = ⇒ H 0 1 1 1 I3 
 0 1 1 
  1 1 1 0 
 1 1 0 

13
 Dual Codes
If C is a linear (n,k) code generated by G, then the dual
code C⊥ is a linear (n,n-k) code generated by H.

The dual code is just the dual space.

Example 0 0 0
0 0 0 1 1 0
=C = C⊥
1 1 1 0 1 1
1 0 1

(3,1,3) code (3,2,2) code

14
 Dual Codes
For the (n,1) repetition code C with generator matrix
G = [1 1 … 1]
the dual code C⊥ is an (n,n-1) SPC code with generator matrix

1 1 0 0 ... 0 
1 0 1 0 ... 0 
H= 
  
 
1 0 0 0 ... 1 
The rows of G are orthogonal to the rows of H

15
 Duals of (5,2,3) Codes
• Consider two equivalent (5,2,3) codes
– nonsystematic and systematic
00111 10110 
=G   →
= G'   (permute columns 1 and 5)
11100   01101 
01101 11100 
H =00011 H' 10010 
 
11000  01001
• H and H' both generate (5,3,2) codes

16
 Decoding Linear Codes
• After transmission through a noisy channel the received
word is
r=c+e
where
c is the transmitted codeword
e is the error pattern
• For error detection, the goal is to determine if e = 0
• For error correction, the goal is to find the codeword c’
that is closest to r
– there are 2n possible received words
– there are 2k codewords
17
 Decoding Linear Codes
• One possibility is a lookup table
• The received word r is used as an address

• For error detection, just store a binary value

– 0: valid codeword (e = 0)
– 1: not a codeword (e ≠ 0)
– Example: (8,7,2) single parity check code
Address (r) Entry
00000000 0
00000001 1
00000010 1
00000011 0
⁞ ⁞

If the entry is 0, the data is the first k = 7 bits (assuming a

systematic code, G = [I P])
18
 Decoding Linear Codes
• For error correction, the table must provide the
codeword (c), message (m), or error pattern (e)
• If the probability of error is small, the most likely error
patterns are the ones with small Hamming weight
• How to determine the most likely received words
associated with these error patterns?
• The easiest way is to make a table of possible
combinations
r=c+e

19
 Standard Array
• The number of correctable error patterns ei is
2n-k
• The standard array is formed by choosing ei to
be the
– all-zero pattern
– 1 bit error patterns
– 2 bit error patterns
⁞
• Ensure that each new error pattern is not
already in the array
20
 Standard Array
c0 (all zero) c1 …… cM-2 cM-1
e1 c1+e1 …… cM-2+e1 cM-1+e1
e2 c1+e2 …… cM-2+e2 cM-1+e2
e3 c1+e3 …… cM-2+e3 cM-1+e3
⁞ ⁞ …… ⁞ ⁞
e2n-k-1 c1+ e2n-k-1 …… cM-2+ e2n-k-1 cM-1+ e2n-k-1

The array has

• 2k columns (the number of codewords M)
• 2n-k rows (the number of correctable error patterns)
21
Standard Array for the (5,2,3) Code

22
23
 Standard Array
• The rows of the standard array are called
cosets
• The first (left) column elements are called the
coset leaders
– the coset leaders are the correctable error
patterns

24
 Standard Array Decoding
• Assume that the received word is r = c1 + e3
(shown in red in the standard array)
• The most likely codeword is the one at the top of
the column containing r
• The corresponding error pattern is the coset
leader at the start of the row containing r
• Can be implemented using a lookup table which
maps all words in the array to the
– error pattern e on the left of the row containing the
received word, or the
– message m corresponding to the codeword c at the top
of the column containing the received word
25
 Syndromes
• For a received word r, there is a simpler method
to determine the closest codeword (or lowest
weight error pattern)
• To do this we use the syndrome s of the received
word r
s = rHT
• If c was corrupted by the error vector e then
r=c+e
and
s = rHT = (c + e)HT = cHT + eHT
s = 0 + eHT
• The syndrome depends only on the error vector e

26
 Syndromes
• The same error pattern added to different
codewords gives the same syndrome.

• There are 2n possible received words but only

• 2(n-k) syndromes
– (5,2,3) code has 32 received words and 8 syndromes
– (7,4,3) code 128 received words and 8 syndromes
– (255,247,3) code has 2255 received words and
28 = 256 syndromes

• Only need to determine which error pattern

corresponds to the syndrome
27
 Syndrome Decoding
Block diagram of the syndrome decoder

Compute s Look-up e
syndrome table

r c
+

28
 Syndrome Decoding - (5,2,3) Code
s0 = (00000)HT = 000
s1 = (10000)HT = 110
G
s2 = (01000)HT = 101
s3 = (00100)HT = 100
s4 = (00010)HT = 010
H s5 = (00001)HT = 001
s6 = (00011)HT = 011
s7 = (10001)HT = 111

r = (10010) rHT = 100 e = (00100) c = r+e = (10110)

r = (11000) rHT = 011 e = (00011) c = r+e = (11011)
29
 Syndrome Decoding
• Example (7,4,3) Hamming code
1 0 0 0 0 1 1
0 1 0 0 1 0 1 
=G [=
I |P ] 
0 0 1 0 1 1 0
 
0 0 0 1 1 1 1

0 1 1 1 1 0 0 
=  P T| I
H = 1 0 1 1 0 1 0 
 
1 1 0 1 0 0 1 

30
 Syndromes for the (7,4,3) Code

s0 = (0000000)HT = 000
s1 = (1000000)HT = 011
0 1 1 1 1 0 0  s2 = (0100000)HT = 101
H = 1 0 1 1 0 1 0  s3 = (0010000)HT = 110
1 1 0 1 0 0 1  s4 = (0001000)HT = 111
s5 = (0000100)HT = 100
s6 = (0000010)HT = 010
s7 = (0000001)HT = 001

31
 Syndrome Decoding
• Received word r = (1101001)
0 1 1
1 0 1 

1 1 0
 
s
= = (1 1 0 1 0 0 1 ) 1
rH T
1 =
1 0 0 0
1 0 0
 
0 1 0
0 0 1 


• e = (0000000) and r is a valid codeword

32
 Syndrome Decoding
• Received word r = (1101000)
0 1 1
1 0 1 

1 1 0
 
s
= = (1 1 0 1 0 0 0 ) 1
rH T
1 =
1 0 0 1
1 0 0
 
0 1 0
0 0 1 

• Syndrome 001 indicates an error in bit 7 of the
received word so c = (1101001)
33
There are many classes of practical codes
• Hamming codes
• Convolutional codes
• Reed-Muller codes
• Cyclic codes (CRC codes)
• Reed-Solomon codes
• Product codes
• BCH codes
• LDPC codes
• Turbo codes
• Repeat-accumulate codes
• …
All belong to the class of linear block codes

34
Deep Space Communications

35
Mars Rover 2021
 Final Exam
• Wednesday, December 15, 9:00 AM ECS 125
• 3 hour exam
• ALL course content is covered
– emphasis on topics after the test
• Materials Allowed:
– Calculator
– Two pages of notes on 8.5” × 11.5” paper

2
 Course Experience Survey
• Provide your feedback on the course at the
link given in the CES email.
• CES will be available until the end of the last
day of classes (Monday).
• Your feedback is important.
• Your responses are confidential.
• Instructors receive only summary reports after
grades have been submitted.
25