CC 03 Linear Block Code

Chapter 3
Linear Block Codes
Wireless Information Transmission System Lab.

Institute of Communications Engineering
g g
National Sun Yat-
Yat-sen University
Outline
◊ Introduction to linear block codes

◊ Syndrome and error detection
◊ The minimum distance of a block code
◊ Error-detecting and error-correcting capabilities of a block
code
◊ Standard array and syndrome decoding
◊ P b bili off an undetected
Probability d d error for
f linear
li codes
d over a
binary symmetric channel (BSC).
◊ Single-Parity-Check Codes, Repetition Codes, and Self-
Dual Codes
2
Introduction to Linear Block
C d
Codes

g g
National Sun Yat-
Yat-sen University
Introduction to Linear Block Codes
◊ We assume that the output of an information source is a

sequence of binary digits “0” or “1”
◊ This binary information sequence is segmented into
message block
bl k off fixed
fi d length,
l h denoted
d d by
b u.
◊ Each message block consists of k information digits.
◊ There are a total of 2k distinct message.
◊ The encoder transforms each input message u into a binary
n-tuple v with n > k
◊ This n-tuple v is referred to as the code word ( or code vector ) of
the message u.
◊ There are distinct 2k code words.
4
◊ This set of 2k code words is called a block code.

◊ For a block
bl k coded to bbe useful,
f l there
h should
h ld be
b a one-to-one
correspondence between a message u and its code word v.
◊ A desirable structure for a block code to possess is the
linearity. With this structure, the encoding complexity will
be greatly reduced.
u E
Encoder
d v
Message block Code word
(k info. digits) (n-tuple , n > k )
(2k distinct message) (2k distinct code word)
5
◊ Definition 3.1. A block code of length n and 2k code

word is called a linear (n,
(n k) code iff its 2k code words
form a k-dimensional subspace of the vector space of all
the n-tuple
n tuple over the field GF(2).
GF(2)
◊ In fact, a binary block code is linear iff the module-2 sum

of two code word is also a code word
◊ 0 must be code word.
◊ The block code given in Table 3.1 is a (7, 4) linear code.
6
For large k, it is virtually impossible to build up the look-up table.

7
◊ Since an (n, k) linear code C is a k-dimensional subspace

of the vector space Vn of all the binary n-tuple,
n tuple it is
possible to find k linearly independent code word, g0 ,
g1 ,…, gk-1 in C
v = u 0 g 0 + u1g 1 + ⋅ ⋅ ⋅ + u k −1g k −1 (3 1)
(3.1)
where ui = 0 or 1 for 0 ≤ i < k
8
◊ Let us arrange these k linearly independent code words as
the rows of a k × n matrix as follows:
⎡ g 0 ⎤ ⎡ g 00 g 01 g 02 . . g 0,n −1 ⎤
⎢g ⎥ ⎢ g g11 g12 . . g1,n −1 ⎥⎥
⎢ 1 ⎥ ⎢ 10
⎢ . ⎥ ⎢ . . . . . . ⎥
⎢ ⎥ ⎢ ⎥
G=⎢ . ⎥=⎢ . . . . . . ⎥ (3.2)
⎢ . ⎥ ⎢ . . . . . . ⎥
⎢ ⎥ ⎢ ⎥
⎢ . ⎥ ⎢ . . . . . . ⎥
⎢g ⎥ ⎢⎢ g . . g k −1,n −1 ⎥⎥⎦
⎣ k −1 ⎦ ⎣ k −1,0 g k −1,1 g k −1,2
where gi = (gi0, gi1,…,gi,n-1) for 0 ≤ i < k
9
◊ If u = (u0,u1,…,uk-1) is the message to be encoded, the

corresponding code word can be given as follows:
v = u ⋅G
⎡ g0 ⎤
⎢g ⎥
⎢ 1 ⎥
⎢ . ⎥
= (u0 , u1 ,..., uk −1 ) • ⎢ ⎥ (3.3)
⎢ . ⎥
⎢ . ⎥
⎢ ⎥
⎢⎣ g k −1 ⎥⎦
= u0 g 0 + u1g1 + ⋅⋅⋅ + uk −1g k −1
10
◊ Because the rows of G generate the (n, k) linear code C,

the matrix G is called a generator matrix for C
◊ Note that any k linearly independent code words of an (n,

k) linear code can be used to form a generator matrix for
the code, i.e. generator matrix is not unique.
◊ It follows from (3.3) that an (n, k) linear code is

completely specified by the k rows of a generator matrix G
11
◊ Example 3.1
◊ the (7,
th (7 4) linear
li code
d given
i in
i Table
T bl 3.1
3 1 has
h the
th following
f ll i matrix
ti
as a generator matrix :
⎡ g 0 ⎤ ⎡1 1 0 1 0 0 0⎤
⎢ g ⎥ ⎢0 1 1 0 1 0 0 ⎥⎥
G = ⎢ 1⎥ = ⎢
⎢g 2 ⎥ ⎢1 1 1 0 0 1 0⎥
⎢ ⎥ ⎢ ⎥
⎣ g 3 ⎦ ⎣1 0 1 0 0 0 1⎦
◊ If u = (1 1 0 1) is the message to be encoded, its corresponding

code word, according to (3.3), would be
v = 1 ⋅ g 0 + 1 ⋅ g1 + 0 ⋅ g 2 + 1 ⋅ g 3
= (11 0 1 0 0 0) + (0 11 0 1 0 0) + (1 0 1 0 0 0 1)
= (0 0 0 11 0 1)
12
◊ A desirable property for a linear block code is the

systematic structure of the code words as shown in Fig.
Fig 3.1
31
◊ where a code word is divided into two parts
◊ The message partt consists
Th i t off k information
i f ti digits
di it
◊ The redundant checking part consists of n − k parity-check digits
◊ A linear block code with this structure is referred to as a
linear systematic block code
Redundant checking part Message part

n - k digits
di it k digits
di it
Fig. 3.1 Systematic format of a code word
13
◊ A linear systematic (n, k) code is completely specified by a

k × n matrix G of the following form :
P matrix k × k identity matrix
⎡ g 0 ⎤ ⎡ p00 p 01 . . . p0,n − k −1 | 1 0 0 . 0⎤. .

⎢g ⎥ ⎢ p p11 . . . p1,n − k −1 | 0 1 0 . 0⎥⎥
. .
⎢ 1 ⎥ ⎢ 10
⎢ g 2 ⎥ ⎢ p20 p21 . . . p2,n −k −1 | 0 0 1 . . . 0⎥
⎢ ⎥ ⎢ ⎥
G=⎢ . ⎥=⎢ | ⎥ (3.4)
⎢ . ⎥ ⎢ | ⎥
⎢ ⎥ ⎢ ⎥
⎢ . ⎥ ⎢ | ⎥
⎢g ⎥ ⎢ p . . . | 0 0 0 0 0 0 1⎥⎦
⎣ k −1 ⎦ ⎣ k −1, 0 pk −1,1 pk −1, n − k −1
where pij = 0 or 1
14
◊ Let u = (u0, u1, … , uk-1) be the message to be encoded

◊ The
h corresponding
di code d wordd isi
v = (v0 , v1 , v2 ,..., vn −1 )
= (u0 , u1 ,..., uk -1 ) ⋅ G (3.5)
◊ It follows from (3.4) & (3.5) that the components of v are

vn-k+i = ui f 0≤i<k
for
(3.6a) Message
and
vj = u0 p0j + u1 p1j + ··· + uk-1 pk-1,
k-1 j for 0 ≤ j < n-k (
(3.6b))
Parity check
15
◊ Equation (3.6a) shows that the rightmost k digits of a code

word v are identical to the information digits u0, u1,…uuk-1
to be encoded
◊ Equation (3.6b) shown that the leftmost n – k redundant

digits are linear sums of the information digits
◊ The n – k equations given by (3.6b) are called parity-check

equations of the code.
code
16
◊ Example 3.2
◊ The matrix
Th t i G given
i in
i example l 3.1
31
◊ Let u = (u0, u1, u2, u3) be the message to be encoded
◊ L v = (v
Let ( 0, v1, v2, v3, v4, v5,v6) be
b the
h corresponding
di code
d wordd
◊ Solution :
⎡1 1 0 1 0 0 0⎤
⎢0 1 1 0 1 0 0 ⎥⎥
v = u ⋅ G = (u 0 , u1 , u 2 , u3 ) ⋅ ⎢
⎢1 1 1 0 0 1 0⎥
⎢ ⎥
⎣1 0 1 0 0 0 1⎦
17
◊ By matrix multiplication, we obtain the following digits of the
code word v
v6 = u 3
v5 = u 2
v4 = u1
v3 = u 0
v2 = u1 + u 2 + u3
v1 = u 0 + u1 + u 2
v0 = u 0 + u 2 + u 3
The code word corresponding to the message (1 0 1 1) is (1 0 0 1 0 1 1)
18
◊ For any k × n matrix G with k linearly independent rows, there exists
an (n
(n-k)
k) ×n matrix H with nn-kk linearly independent rows such that
any vector in the row space of G is orthogonal to the rows of H and
any vector that is orthogonal to the rows of H is in the row space of
G.
◊ An n-tuple v is a code word in the code generated by G if and only if
v • HT = 0
◊ This matrix H is called a parity-check matrix of the code
◊ The 2n-k linear combinations of the rows of matrix H form an (n, n –
k) linear code Cd
◊ Thi code
This d is
i the
h null
ll space off the
h (n,
( k) linear
li code
d C generatedd by
b
matrix G
◊ Cd is
i called
ll d the
th dual d off C
d l code
19
◊ If the generator matrix of an (n,k) linear code is in the

systematic form of (3.4),
(3 4) the parity-check
parity check matrix may take
the following form :
[
H = I n−k PT ]
⎡1 0 0 . . . 0 p00 p10 . . . pk-1,0 ⎤
⎢0 1 0 . . . 0 p01 p11 . . . pk-1,1 ⎥⎥
⎢
⎢0 0 1 . . . 0 p02 p12 . . . pk-1,2 ⎥
⎢ ⎥
= ⎢. ⎥ (3.7)
⎢. ⎥
⎢ ⎥
⎢. ⎥
⎢0 0 0 . . . 1 p0 ,n-k- p1,n-k- . . . pk-k 1,n-k- ⎥
⎣ nk1 nk1 n k 1⎦
20
◊ Let hj be the jth row of H
g i ⋅ h j = pij + pij = 0
for 0 ≤ i < k and 0 ≤ j < n – k
◊ This implies that G • HT = 0
21
◊ Let u = (u0, u1, …, uk-1) be the message to be encoded

◊ In systematic
i form
f the
h correspondingdi code d wordd would
ld be
b
v = (v0, v1, … , vn-k-1, u0,u1, … , uk-1)
◊ Using the fact that v • HT = 0, we obtain
vj + u0 p0j + u1 p1j + ··· + uk-1 k 1j= 0
k 1 pk-1,j (3
(3.8)
8)
◊ Rearranging the equation of (3.8), we obtain the same
parity check equations of (3.6b)
parity-check (3 6b)
◊ An (n, k) linear code is completely specified by its parity-

check matrix
22
◊ Example 3.3
◊ Consider
C id the
th generator
t matrix
t i off a (7,4)
(7 4) linear
li code
d given
i in
i
example 3.1
◊ The corresponding parity-check
parity check matrix is
⎡1 0 0 1 0 1 1 ⎤
⎢
H = ⎢0 1 0 1 1 1 0 ⎥ ⎥
⎢⎣0 0 1 0 1 1 1 ⎥⎦
23
◊ Summaries
◊ For any (n, k) linear block code C, there exists a k × n

matrix G whose row space given C
◊ There exist an (n – k) × n matrix H such that an n-tuple

v is a code word in C if and only if v • HT = 0
◊ If G is
i off the
h form
f given
i by
b (3.4),
(3 4) then
h H may take
k fform
given by (3.7), and vice versa
24
◊ Based on the equation of (3.6a) and (3.6b), the encoding
circuit for an ((n,, k)) linear systematic
y code can be
implemented easily
◊ The encoding circuit is shown in Fig. 3.2
where
◊ denotes a shift-register stage (flip-flop)
◊ Pij denotes a connection if pij = 1 and no connection if pij = 0
◊ denotes a modulo-2 adder
◊ As soon as the entire message has entered the message register, the n-k
parity-check
parity check digits are formed at the outputs of the nn-kk module
module-2
2 adders
◊ The complexity of the encoding circuit is linearly proportional to

the block length
◊ The encoding circuit for the (7,4) code given in Table 3.1 is
shown in Fig 3.3
25
26
27
Syndrome
y and Error Detection

g g
National Sun Yat-
Yat-sen University
Syndrome and Error Detection
◊ Let v = (v0, v1, …, vn-1) be a code word that was
transmitted over a noisy channel
◊ Let r = (r0, r1, …, rn-1) be the received vector at the output
of the channel
v r=v+e
e
◊ e = r + v = (e0, e1, …, en-1) is an n-tuple
◊ ei = 1 for ri ≠ vi
◊ ei = 0 for ri = vi
◊ The n-tuple e is called the error vector (or error pattern)
29
◊ Upon receiving r, the decoder must first determine

whether r contains transmission errors
◊ If the presence of errors is detected, the decoder will take
actions
i to locate
l the
h errors
◊ Correct errors (FEC)
◊ Request for a retransmission of v (ARQ)
◊ When r is received, the decoder computes the following
(n – k)-tuple :
s = r • HT
= (s0, s1, …, sn-k-1) (3.10)
(併發症狀)
which is called the syndrome of r
30
◊ s = 0 if and only if r is a code word and receiver accepts r

as the transmitted code word
◊ s≠0 if and only if r is not a code word and the presence of

errors has been detected
◊ When the error pattern e is identical to a nonzero code

(i e r contain errors but s = r • HT = 0),
word (i.e., 0) error
patterns of this kind are called undetectable error patterns
◊ Since there are 2k – 1 nonzero code words
words, there are 2k – 1
undetectable error patterns
31
◊ Based on (3.7) and (3.10), the syndrome digits are as
follows : H = ⎡I P ⎤ T
s = r • HT
⎣ n−k ⎦
s0 = r0 + rn-k p00 + rn-k+1 p10 + ··· + rn-1 pk-1,0,

s1 = r1 + rn-k p01 + rn-k+1 p11 + ··· + rn-1 pk-1,1
. (
(3.11)
)
sn-k-1 = rn-k-1 + rn-k p0,n-k-1 + rn-k+1 p1,n-k-1 + ··· + rn-1 pk-1,n-k-1
◊ The syndrome s is the vector sum of the received parity
digits (r0,r1,…,rn-k-1) and the parity-check digits
recomputed
p from the received information digits g ((rn-k,,rn-
k+1,…,rn-1).
◊ Ag general syndrome
y circuit is shown in Fig. g 3.4
32
33
◊ Example 3.4
◊ The parity-check
Th it h k matrix t i is
i given
i in
i example l 3.3
33
◊ Let r = (r0, r1, r2, r3, r4, r5, r6) be the received vector
◊ Th syndrome
The d is
i given
i by
b
⎡1 0 0⎤
⎢0 1 0 ⎥⎥
⎢
⎢0 0 1⎥
⎢ ⎥
s = ( s0 , s1 , s2 ) = ( r0 , r1 , r2 , r3 , r4 , r5 , r6 ) ⋅ ⎢1 1 0⎥
⎢0 1 1⎥
注意：三個位元只 ⎢ ⎥
⎢ 1 1 1⎥
能表示八種情況
⎢1 0 1 ⎥⎦
⎣
34
◊ Example 3.4
◊ The syndrome digits are
s0 = r0 + r3 + r5 + r6
s1 = r1 + r3 + r4 + r5
s2 = r2 + r4 + r5 + r6
◊ The syndrome circuit for this code is shown below
35
◊ Since r is the vector sum of v and e, it follows from (3.10)

that
s = r • HT = (v + e) • HT = v • HT + e • HT
◊ However,
v • HT = 0
◊ Consequently, we obtain the following relation between

Consequently
the syndrome and the error pattern :
s = e • HT (3 12)
(3.12)
36
◊ If the parity-check matrix H is expressed in the systematic

form as given by (3 7) multiplying out e • HT yield the
(3.7),
following linear relationship between the syndrome digits
and the error digits :
n-k equations and n variables
s0 = e0 + en-k p00 + en-k+1 p10 + ··· + en-1 pk-1,0
s1 = e1 + en-k
n k p01 + en-k+1
n k+1 p11 + ··· + en-1 pk-1,1
k-1 1
.
. (3 13)
(3.13)
sn-k-1 = en-k-1 + en-k p0,n-k-1 + ··· + en-1 pk-1,n-k-1
37
◊ The syndrome digits are linear combinations of the error
digits
◊ The syndrome digits can be used for error correction
◊ Because the n – k linear equations of (3.13)
(3 13) do not have a
unique solution but have 2k solutions
◊ There are 2k error pattern that result in the same syndrome,
syndrome
and the true error pattern e is one of them
◊ The decoder has to determine the true error vector from a
set of 2k candidates
◊ To minimize the probability of a decoding error,
error the most
probable error pattern that satisfies the equations of (3.13)
is chosen as the true error vector
38
◊ Example 3.5
◊ We consider the (7,4)
(7 4) code whose parity-check
parity check matrix is given in
example 3.3
◊ Let v = ((1 0 0 1 0 1 1)) be the transmitted code word
◊ Let r = (1 0 0 1 0 0 1) be the received vector
◊ The receiver computes the syndrome
s = r • HT = (1 1 1)
◊ The receiver attempts to determine the true error vector
e = (e
( 0, e1, e2, e3, e4, e5, e6),
) which
hi h yields
i ld the
h syndrome
d above
b
1 = e0 + e3 + e5 + e6
1 = e1 + e3 + e4 + e5
1 = e2 + e4 + e5 + e6
◊ There are 24 = 16 error patterns that satisfy the equations above
39
◊ Example 3.5
◊ The error vector
Th t e = (0 0 0 0 0 1 0) has h the
th smallest
ll t numberb off
nonzero components
◊ If the channel is a BSC,
BSC e = (0 0 0 0 0 1 0) is the most probable
error vector that satisfies the equation above
◊ Taking e = (0 0 0 0 0 1 0) as the true error vector
vector, the receiver
decodes the received vector r = (1 0 0 1 0 0 1) into the following
code word
v* = r + e = (1 0 0 1 0 0 1) + (0 0 0 0 0 1 0)
= ((1 0 0 1 0 1 1))
where v* is the actual transmitted code word
40
The Minimum Distance of a Block
Code
g g
National Sun Yat-
Yat-sen University
The Minimum Distance of a Block Code
◊ Let v = (v0, v1, … , vn-1) be a binary n-tuple, the Hamming

weight (or simply weight) of v, v denote by w(v),
w(v) is defined
as the number of nonzero components of v
◊ F example,
For l the
th Hamming
H i weight
i ht off v = (1 0 0 0 1 1 0) iis 3
◊ Let v and w be two nn-tuple

tuple, the Hamming distance
between v and w, denoted d(v,w), is defined as the number
of places where they differ
◊ For example, the Hamming distance between v = (1 0 0 1 0 1 1)
and w = ((0 1 0 0 0 1 1)) is 3
42
◊ The Hamming distance is a metric function that satisfied
the triangle inequality
d(v, w) + d(w, x) ≥ d(v, x) (3.14)
◊ the proof of this inequality is left as a problem
◊ From the definition of Hamming distance and the
definition of module-2 addition that the Hamming distance
between two n-tuple, v and w, is equal to the Hamming
weight
g of the sum of v and w,, that is
d(v, w) = w(v + w) (3.15)
◊ For example, the Hamming distance between v = (1 0 0 1 0 1 1)
and w = (1 1 1 0 0 1 0) is 4 and the weight of v + w = (0 1 1 1 0 0
1) is also 4
43
◊ Given a block code C, the minimum distance of C, denoted dmin, is
defined as
dmin = min{d(v, w) : v, w C, v ≠ w} (3.16)
◊ If C is a linear block, the sum of two vectors is also a code vector

◊ From (3.15) that the Hamming distance between two code vectors in
C is equal to the Hamming weight of a third code vector in C
i = min{w(v + w): v,
dmin v w C, C v ≠ w}
= min{w(x): x C, x ≠0} (3.17)
≡ wmin
i
44
◊ The parameter wmin ≡ {w(x): x∈ C, x ≠0} is called the minimum
weight of the linear code C
◊ 3 1 The minimum distance of a linear block code is equal

Theorem 3.1
to the minimum weight of its nonzero code words
◊ Theorem 3.2 Let C be an (n, k) linear code with parity-check matrix

H.
◊ For each code vector of Hamming weight l, there exist l columns
of H such that the vector sum of these l columns is equal to the

zero vector.
◊ Conversely, if there exist l columns of H whose vector sum is the
zeros vector, there exists a code vector of Hamming weight l in C.
45
◊ Proof
◊ Let the parity-check
parity check matrix be
H = [ho, h1, … , hn-1]
◊ where hi represents the ith column of H
◊ Let v = (v0, v1, … , vn-1) be a code vector of weight l and v has l
nonzero components
◊ Let vi1, vi2, …, vil be the l nonzero components of v,
where 0 ≤ i1 < i2 < ··· < il ≤ n-1, then vi1 = vi2 = ··· = vil = 1
◊ since
i v is
i code
d vector, we must have h
0 = v • HT
= voh0 + v1h1 + ··· + vn-1hn-1
= vi1hi1 + vi2hi2 + ··· + vilhil
= hi1 + hi2 + ··· + hil
46
◊ Proof
◊ S
Suppose th
thatt hi1, hi2, … , hil are l columns
l off H suchh that
th t
hi1 + hi2 + ··· + hil = 0 (3.18)
◊ L x = (x
Let ( 1, x2, … , xn-1) whose
h nonzero components are xi1, xi2, xil
x • HT = x0h0 + x1h1 + ··· + xn-1hn-1
= xi1hi1 + xi2hi2 + ··· + xilhil
= hi1 + hi2 + ··· + hil
◊ It following from (3.18) that x • HT = 0, x is code vector of
weight l in C
47
◊ Let C be a linear block code with parity-check matrix H
◊ Corollary 3.2.1 If no d-1 or fewer columns of H add to 0,

the code has minimum weight at least d
◊ Corollary 3.2.2 The minimum weight of C is equal to the

smallest number of columns of H that sum to 0
48
Error-Detecting and Error-
Error- Error-
Correcting Capabilities of a Block
Code
g g
National Sun Yat-
Yat-sen University
Error- Error-Correcting
Capabilities
p of a Block Code
◊ If the minimum distance of a block code C is dmin, any two

distinct code vector of C differ in at least dmin places
◊ A block code with minimum distance dmin is capable of
d
detecting
i allll the
h error pattern off dmin – 1 or fewer
f errors
◊ However, it cannot detect all the error pattern of dmin errors
because there exists at least one pair of code vectors that
differ in dmin places and there is an error pattern of dmin
errors that will carry one into the other
◊ The random-error-detectingg capability
p y of a block code
with minimum distance dmin is dmin – 1
50
Capabilities
p of a Block Code
◊ An (n, k) linear code is capable of detecting 2n – 2k error
patterns of length n
◊ Among the 2n – 1 possible nonzero error patterns, there are
2k – 1 error patterns that are identical to the 2k – 1 nonzero
code words
◊ If any of these 2k – 1 error patterns occurs
occurs, it alters the
transmitted code word v into another code word w, thus w
will be received and its syndrome
y is zero
◊ There are 2k – 1 undetectable error patterns
◊ If an error pattern is not identical to a nonzero code word,
word
the received vector r will not be a code word and the
syndrome
y will not be zero
51
Capabilities
p of a Block Code
◊ These 2n – 2k error patterns are detectable error patterns

◊ Let Al be
b theh number
b off coded vectors off weight
i h i in
i C,
C the
h
numbers A0, A1,..., An are called the weight distribution of
C
◊ Let Pu(E) denote the probability of an undetected error
◊ Since an undetected error occurs only when the error
pattern is identical to a nonzero code vector of C
p
n
Pu ( E ) = ∑ Ai p i (1 − p ) n −i
i 1
i=
where p is the transition probability of the BSC
◊ If the minimum distance of C is dmin, then A1 to Admin – 1
are zero
52
Capabilities
p of a Block Code
◊ Assume that a block code C with minimum distance dmin is used for
random-error
random error correction.
correction The minimum distance dmin i is either odd or
even. Let t be a positive integer such that:
2t+1≤≤ dmin ≤
≤2t+2
◊ Fact 1: The code C is capable of correcting all the error patterns of t
or fewer errors.
◊ Proof:
◊ Let v and r be the transmitted code vector and the received vector,,
respectively. Let w be any other code vector in C.

d(v,r) + d(w,r) ≥ d(v,w)
◊ Suppose that an error pattern of t’ errors occurs during the
transmission of v. We have d(v,r)=t’.
53
Capabilities
p of a Block Code
◊ Since v and w are code vectors in C, we have
d(v w)≥ dmin ≥2t+1.
d(v,w)≥ ≥2t+1
d(w,r)≥d(v,w)-d(v,r)
≥ dmin-t’
t’
≥2t+1-t’≥t+1 (if t ≥t’)
>t Î d(w,r)>t’
d( )>t’
◊ The inequality above says that if an error pattern of t or fewer
errors occurs,
occurs the received vector r is closer (in Hamming
distance) to the transmitted code vector v than to any other code
vector w in C.
◊ For a BSC, this means that the conditional probability P(r|v) is
greater than the conditional probability P(r|w) for w≠v. Q.E.D.
54
Capabilities
p of a Block Code
◊ Fact 2: The code is not capable of correcting all the error patterns of
l errors with l > t,
t for there is at least one case where an error pattern
of l errors results in a received vector which is closer to an incorrect
code vector than to the actual transmitted code vector.
◊ Proof:
◊ Let v and w be two code vectors in C such that d(v,w)=d
( ) min.
◊ Let e1 and e2 be two error patterns that satisfy the following
conditions:
◊ e1+ e2=v+w
◊ e1 and e2 do not have nonzero components in common places.
◊ We have w(e1) + w(e2) = w(v+w) = d(v,w) = dmin. (3.23)
55
Capabilities
p of a Block Code
◊ Suppose that v is transmitted and is corrupted by the error pattern
e1, then the received vector is
r = v + e1
◊ The Hamming distance between v and r is
d(v, r) = w(v + r) = w(e1). (3.24)
◊ The Hamming distance between w and r is
d(w, r) = w(w + r) = w(w + v + e1) = w(e2) (3.25)
◊ Now suppose that the error pattern e1 contains more than t errors
Now,
[i.e. w(e1) ≥t+1].
◊ Since 2t + 1 ≤ dmini ≤ 2t +2,
+2 it follows from (3.23)
(3 23) that
w(e2) = dmin- w(e1) ≤ (2t +2) - (t+1) = t + 1
56
Capabilities
p of a Block Code
◊ Combining (3.24) and (3.25) and using the fact that w(e1) ≥ t+1
and w(e2) ≤ t + 1,
1 we have
d(v, r) ≥ d(w, r)
◊ This inequality say that there exists an error pattern of l (l > t)
errors which results in a received vector that is closer to an
incorrect code vector than to the transmitted code vector.
◊ Based on the maximum likelihood decoding scheme, an incorrect
decoding would be committed. Q.E.D.
57
Capabilities
p of a Block Code
◊ A block code with minimum distance dmin guarantees
correcting all the error patterns of t = ⎢⎣(d mini − 1) / 2 ⎥⎦ or fewer
errors, where ⎢⎣(d min − 1) / 2⎥⎦ denotes the largest integer no
ggreater than ((dmin – 1)/2
)
◊ The parameter t = ⎢⎣(d min − 1) / 2 ⎥⎦ is called the random-error
correctingg capability
p y of the code
◊ The code is referred to as a t-error-correcting code
◊ A block code with random
random-error-correcting
error correcting capability t is
usually capable of correcting many error patterns of t + 1
or more errors
◊ For a t-error-correcting (n, k) linear code, it is capable of
correctingg a total 2n-k error ppatterns (shown
( in next section).)
58
Capabilities
p of a Block Code
◊ If a t-error-correcting block code is used strictly for error correction
on a BSC with transition probability p,p the probability that the
decoder commits an erroneous decoding is upper bounded by:
n
⎛n⎞ i
P ( E ) ≤ ∑ ⎜ ⎟ p (1 − p )
n −i
i = t +1 ⎝ i ⎠
◊ In practice, a code is often used for correcting λ or fewer errors and

simultaneously y detectingg l ((l >λ)) or fewer errors. That is,, when λ or
fewer errors occur, the code is capable of correcting them; when
more than λ but fewer than l+1 errors occur, the code is capable of
d
detecting
i their
h i presence without
ih making
ki a decoding
d di error.
◊ The minimum distance dmin of the code is at least λ+ l+1.
59
Standard Array and Syndrome
Decoding
g g
National Sun Yat-
Yat-sen University
Standard Array and Syndrome Decoding
◊ Let v1, v2, …, v2k be the code vector of C

◊ Any decoding scheme used at the receiver is a rule to
partition the 2n possible received vectors into 2k disjoint
subsets D1, D2, …, D2k such that the code vector vi is
contained in the subset Di for 1 ≤ i ≤ 2k
◊ Each subset Di is one
one-to-one
to one correspondence to a code
vector vi
◊ If the received vector r is found in the subset Di, r is
decoded into vi
◊ Correct decoding is made if and only if the received vector
r is in the subset Di that corresponds to the actual code
vector transmitted
61
◊ A method to partition the 2n possible received vectors into 2k disjoint

subsets such that each subset contains one and onlyy one code vector
is described here
◊ First, the 2 code vectors of C are placed in a row with the all-
k
zero code
d vectort v1 = (0,
(0 00, …, 0) as the
th first
fi t (leftmost)
(l ft t) element
l t
◊ From the remaining 2n – 2k n-tuple, an n-tuple e2 is chosen and is
placed under the zero vector v1
◊ Now, we form a second row by adding e2 to each code vector vi
in the first row and placing the sum e2 + vi under vi
◊ An unused n-tuple e3 is chosen from the remaining n-tuples and
is placed under e2.
◊ Then
Th a thirdhi d row is
i formed
f d by
b adding
ddi e3 to eachh code d vector vi in
i
the first row and placing e3 + vi under vi .
◊ we continue this process until all the n-tuples are used.
used
62
63
◊ Then we have an array of rows and columns as shown in

Fig
g 3.6
◊ This array is called a standard array of the given linear
code C
◊ Theorem 3.3 No two n-tuples in the same row of a
standard array are identical. Every n-tuple appears in one
and only one row
◊ Proof
◊ The first part of the theorem follows from the fact that all the
code vectors of C are distinct
◊ Suppose that two n-tuples in the lth rows are identical, say el + vi
= el + vj with
i h i ≠j
◊ This means that vi = vj, which is impossible, therefore no two
p in the same row are identical
n-tuples
64
◊ Proof
◊ It follows from the construction rule of the standard array that
every n-tuple appears at least once
◊ Suppose that an n-tuple appears in both lth row and the mth row
with l < m
◊ Then this n-tuple must be equal to el + vi for some i and equal to
em + vj for some j
◊ As a result, el + vi = em + vj
◊ From this equality we obtain em = el + (vi + vj)
◊ Si
Since vi and
d vj are code
d vectors
t ini C,
C vi + vj isi also
l a coded vector
t
in C, say vs
◊ This implies
p that the n-tuple
p em is in the lth row of the array,
y,
which contradicts the construction rule of the array that em, the
first element of the mth row, should be unused in any previous
row
◊ No n-tuple can appear in more than one row of the array
65
◊ From Theorem 3.3 we see that there are 2n/2k = 2n-k

disjoint rows in the standard array,
array and each row consists
of 2k distinct elements
◊ The
h 2n-kk rows are called
ll d the
h cosets off the
h code
d C
◊ The first n-tuple ej of each coset is called a coset leader
◊ Any element in a coset can be used as its coset leader
66
◊ Example 3.6 Consider the (6, 3) linear code generated

by the following matrix :
⎡0 1 1 1 0 0 ⎤
⎢
G = ⎢1 0 1 0 1 0 ⎥ ⎥
⎢⎣1 1 0 0 0 1 ⎥⎦
◊ The standard arrayy of this code is shown in Fig.
g 3.7
67
68
◊ A standard array of an (n, k) linear code C consists of 2k

disjoint columns
◊ Let Dj denote the jth column of the standard array, then
Dj = {vj, e2+vj, e3+vj, …, e2n-k + vj} (3.27)
(3 27)
◊ vj is a code vector of C and e2, e3, …, e2n-k are the coset leaders
◊ The 2k disjoint
Th di j i t columns
l D1, D2, …, D2k can beb used d ffor
decoding the code C.
◊ S ppose that the code vector
Suppose ector vj is transmitted over
o er a noisy
nois
channel, from (3.27) we see that the received vector r is in
Dj if the error pattern caused by the channel is a coset
leader.
◊ If the error pattern caused by the channel is not a coset
leader, an erroneous decoding will result
69
◊ The decoding is correct if and only if the error pattern

caused by the channel is a coset leader
◊ The 2n-k coset leaders (including the zero vector 0) are
called the correctable error patterns
◊ Theorem 3.4 Every (n, k) linear block code is capable
of correcting 2n-k error pattern
◊ To minimize the probability of a decoding error, the error
patterns that are most likely to occur for a given channel
should be chosen as the coset leaders
◊ When a standard array is formed
formed, each coset leader should
be chosen to be a vector of least weight from the
remainingg available vectors
70
◊ Each coset leader has minimum weight in its coset

◊ The
h decoding
d di based b d on theh standard
d d array is
i the
h minimum
i i
distance decoding (i.e. the maximum likelihood decoding)
◊ Let αi denote the number of coset leaders of weight i, the
numbers α0 , α1 ,…,αn are called the weight distribution of
the coset leaders
◊ Since a decodingg error occurs if and only y if the error
pattern is not a coset leader, the error probability for a BSC
with transition pprobabilityy p is
n
P((E)) =1 − ∑ α i p i ((1 − p ) n −i
i =0
71
◊ Example 3.7
◊ The standard
Th t d d array for
f this
thi code
d is
i shown
h in
i Fig.
Fi 3.7
37
◊ The weight distribution of the coset leader is α0 =1, α1 = 6, α2=1
and
d α3 =α4 =α5 =α6 = 0
◊ Thus,
P(E) = 1 – (1 – p)6 – 6p(1 – p)5 – p2(1 – p)4
◊ For p = 10-2, we have P(E) ≈ 1.37 × 10-3
72
◊ An (n, k) linear code is capable of detecting 2n – 2k error

patterns it is capable of correcting only 2 nn–kk error patterns
patterns,
◊ The probability of a decoding error is much higher than the
probability
b bili off an undetected
d d error
◊ Theorem 3.5
◊ (1) For an (n, k) linear code C with minimum distance dmin, all
the n-tuples of weight of t = ⎢⎣(d min − 1) / 2 ⎥⎦ or less can be used
as coset leaders of a standard array of C.
◊ (2) If all the n-tuple of weight t or less are used as coset leader,
th is
there i att least
l t one n-tuple
t l off weight
i ht t + 1 that
th t cannott be
b usedd as
a coset leader
73
◊ Proof of the (1)

◊ Since the
Si th minimum
i i distance
di t off C is
i dmin , the
th minimum
i i weight
i ht off
C is also dmin
◊ Let x and y be two n-tuples
n tuples of weight t or less
◊ The weight of x + y is
w((x + y) ≤ w((x) + w((y) ≤ 2t < dmin (2t+1≤ dmin ≤2t+2)
◊ Suppose that x and y are in the same coset, then x + y must be a
nonzero code vector in C
◊ This is impossible because the weight of x+y is less than the
minimum weight of C. C
◊ No two n-tuple of weight t or less can be in the same coset of C
◊ All the n-tuples of weight t or less can be used as coset leaders
74
◊ Proof of the (2)

◊ Lett v be
L b a minimum
i i weight
i ht code
d vector
t off C ( i.e.,
i w((v) = dmin )
◊ Let x and y be two n-tuples which satisfy the following two
conditions:
◊ x+y=v
◊ x and y do not have nonzero components in common places
◊ It follows from the definition that x and y must be in the same
coset ((because y=x+v) and
w(x) + w(y) = w(v) = dmin
◊ Suppose
pp we choose y such that w((y) = t + 1
◊ Since 2t + 1 ≤ dmin ≤ 2t + 2, we have w(x)=t or t+1.
◊ If x is used as a coset leader,, then y cannot be a coset leader.
75
◊ Theorem 3.5 reconfirms the fact that an (n, k) linear code

with minimum distance dmin i is capable of correcting all the
error pattern of ⎢⎣(d min − 1) / 2⎥⎦ or fewer errors
◊ But it is not capable of correcting all the error patterns of
weight t + 1
◊ Theorem 3.63 6 All the 2k nn-tuples tuples of a coset have the same
syndrome. The syndrome for different cosets are different
◊ Proof
◊ Consider the coset whose coset leader is el
◊ A vector in this coset is the sum of el and some code vector vi in C
◊ The syndrome of this vector is
(el + vi)HT = elHT + viHT = elHT
76
◊ Proof
◊ Lett ej and
L d el be
b th
the cosett leaders
l d off theth jth andd lth cosets
t
respectively, where j < l
◊ Suppose that the syndromes of these two cosets are equal
◊ Then,
ejHT = elHT
(ej + el)HT = 0
◊ Thi implies
This i li thatth t ej + el is
i a code
d vector
t in
i C,
C say vj
◊ Thus, ej + el = vj and el = ej + vj
◊ Thi implies
This i li that h el isi in
i theh jth
j h coset, which
hi h contradicts
di theh
construction rule of a standard array that a coset leader should be
previously unused
77
◊ The syndrome of an n-tuple is an (n–k)-tuple and there are

2n-k distinct (n
(n–k)-tuples
k) tuples
◊ From theorem 3.6 that there is a one-to-one
correspondence
d bbetween a coset andd an ((n–k)-tuple
k) l
syndrome
◊ Using this one-to-one correspondence relationship, we can
form a decoding table, which is much simpler to use than a
standard array
◊ The table consists of 2n-k coset leaders ((the correctable
error pattern) and their corresponding syndromes
◊ This table is either stored or wired in the receiver
78
◊ The decoding of a received vector consists of three steps:

◊ Step 1.
St 1 CCompute t the
th syndrome
d off r, r • HT
◊ Step 2. Locate the coset leader el whose syndrome is equal to
r • HT, then
h el isi assumedd to be
b theh error pattern causedd
by the channel
◊ Step 3. Decode the received vector r into the code vector v
i.e., v = r + el
◊ The decoding
Th d di scheme
h described
d ib d above
b is
i called
ll d the
h
syndrome decoding or table-lookup decoding
79
◊ Example 3.8 Consider the (7, 4) linear code given in

Table 3.1,
3 1 the parity-check
parity check matrix is given in example 3.3
33
◊ The code has 23 = 8 cosets
◊ Th are eight
There i h correctable
bl error patterns (including
(i l di the h all-zero
ll
vector)
◊ Since the minimum distance of the code is 3, 3 it is capable of
correcting all the error patterns of weight 1 or 0
◊ All the 7-tuples
7 tuples of weight 1 or 0 can be used as coset leaders
◊ The number of correctable error pattern guaranteed by the
minimum distance is equal to the total number of correctable
error patterns
80
◊ The correctable error patterns and their corresponding

syndromes are given in Table 33.22
81
◊ Suppose that the code vector v = (1 0 0 1 0 1 1) is

transmitted and r = (1 0 0 1 1 1 1) is received
◊ For decoding r, we compute the syndrome of r
⎡1 0 0⎤
⎢0 1 0 ⎥⎥
⎢
⎢0 0 1⎥
⎢ ⎥
s = (1 0 0 1 1 1 1) ⎢1 1 0 ⎥ = ( 0 1 1)
⎢0 1 1⎥
⎢ ⎥
⎢1 1 1⎥
⎢1 0 1 ⎥⎦
⎣
82
◊ From Table 3.2 we find that (0 1 1) is the syndrome of the

coset leader e = (0 0 0 0 1 0 0),
0) then r is decoded into
v* = r + e
= (1 0 0 1 1 1 1) + (0 0 0 0 1 0 0)
= ((1 0 0 1 0 1 1))
◊ which is the actual code vector transmitted
◊ The decoding is correct since the error pattern caused by the
channel is a coset leader
83
◊ Suppose that v = (0 0 0 0 0 0 0) is transmitted and

r = (1 0 0 0 1 0 0) is received
◊ We see that two errors have occurred during the
transmission
i i off v
◊ The error pattern is not correctable and will cause a
decoding error
◊ When r is received,, the receiver computes
p the syndrome
y
s = r • HT = (1 1 1)
◊ From the decoding table we find that the coset leader
e = (0 0 0 0 0 1 0) corresponds to the syndrome s = (1 1 1)
84
◊ r is decoded into the code vector

v* = r + e
= (1 0 0 0 1 0 0) + (0 0 0 0 0 1 0)
= (1 0 0 0 1 1 0)
◊ Since v* is not the actual code vector transmitted
transmitted, a
decoding error is committed
◊ Using Table 3.2,
3 2 the code is capable of correcting any
single error over a block of seven digits
◊ Wh two or more errors occur, a decoding
When d di error will ill be
b
committed
85
◊ The table-lookup decoding of an (n, k) linear code may be

implemented as follows
◊ The decoding table is regarded as the truth table of n
switch functions :
e0 = f 0 ( s0 , s1 ,..., sn − k −1 )
e1 = f1 ( s0 , s1 ,..., sn − k −1 )
.
.
en −1 = f n −1 ( s0 , s1 ,..., sn − k −1 )
◊ where s0, s1, …, sn-k-1 are the syndrome digits
◊ where e0, e1, …, en-1 are the estimated error digits
86
◊ The general decoder for an (n, k) linear code based on the

table-lookup scheme is shown in Fig.
Fig 3.8
38
87
◊ Example 3.9 Consider the (7, 4) code given in Table

31
3.1
◊ The syndrome circuit for this code is shown in Fig. 3.5
◊ The decoding table is given by Table 3.2
◊ From this table we form the truth table (Table 3.3)
◊ The switchingg expression
p for the seven error digits
g are
e0 = s0 Λ s1' Λ s2' e1 = s0' Λ s1 Λ s2'
e2 = s0' Λ s1' Λ s2 e3 = s0 Λ s1 Λ s2'
e4 = s0' Λ s1 Λ s2 e5 = s0 Λ s1 Λ s2
e6 = s0 Λ s1' Λ s2
◊ where Λ denotes the logic-AND operation
◊ where s’ denotes the logic-COMPLENENT of s
88
89
◊ The complete circuit of the decoder is shown in Fig. 3.9
90
Probability
robability of An Undetected Error
for Linear Codes Over a BSC

g g
National Sun Yat-
Yat-sen University
Probability of An Undetected Error for
Linear Codes Over a BSC
◊ Let {A0, A1, …, An} be the weight distribution of an (n, k)
linear code C
◊ Let {B0, B1, …, Bn} be the weight distribution of its dual
code Cd
◊ Now we represent these two weight distribution in
polynomial form as follows :
A(z) = A0 + A1z + ··· + Anzn
B(z) = B0 + B1z + ··· + Bnzn (3 31)
(3.31)
◊ Then A(z) and B(z) are related by the following identity :
A(z) ( k) (1 + z)
A( ) = 2 -(n-k) )n B(1 – z / 1 + z)) (3
(3.32)
32)
◊ This identity is known as the MacWilliams identity
92
◊ The polynomials A(z) and B(z) are called the weight
enumerators for the (n,
(n k) linear code C and its dual Cd
◊ Using the MacWilliams identity, we can compute the
probability
b bili off an undetected
d d error for
f an (n,
( k) li
linear code
d
from the weight distribution of its dual.
◊ From equation 3.19:
n
Pu ( E ) = ∑ Ai p (1 − p )
i n −i
i =1
n
p i
= (1 − p ) ∑ Ai (
n
) (3.33)
i =1 1− p
93
◊ Substituting z = p/(1 – p) in A(z) of (3.31) and using the
fact that A0 = 1,
1 we obtain
i
⎛ p ⎞ n
⎛ p ⎞
A⎜ ⎟ − 1 = ∑ Ai ⎜ ⎟ (3.34)
⎝ 1− p ⎠ i =1 ⎝ 1− p ⎠
◊ Combining (3.33) and (3.34), we have the following
expression for the probability of an undetected error
⎡ ⎛ p ⎞ ⎤
Pu ( E ) = (1 − p ) ⎢ A ⎜
n
⎟ − 1⎥ (3.35)
⎣ ⎝ 1− p ⎠ ⎦
94
◊ From (3.35) and the MacWilliams identity of (3.32), we
finally obtain the following expression for Pu(E) :
Pu(E) = 2-(n – k) B(1 – 2p) – (1 – p)n (3.36)
where
n
B(1 − 2 p ) = ∑ Bi (1 − 2 p )i
i =0
◊ Hence, there are two ways for computing the probability of
an undetected
d d error for
f a linear
li code;
d often
f one is i easier
i
than the other.
◊ If n-kk is
i smaller
ll than
h k,k it
i is
i muchh easier
i to compute Pu(E)
from (3.36); otherwise, it is easier to use (3.35).
95
◊ Example 3.10 consider the (7, 4) linear code given in Table 3.1
◊ Th dual
The d l off this
thi code
d is
i generated
t d by
b its
it parity-check
it h k matrix
ti
⎡1 0 0 1 0 1 1⎤
⎢
H = ⎢0 1 0 1 1 1 0⎥ ⎥
⎢⎣ 0 0 1 0 1 1 1 ⎥⎦
◊ Taking the linear combinations of the row of H, we obtain the
following eight vectors in the dual code
(0 0 0 0 0 0 0), (1 1 0 0 1 0 1),
(1 0 0 1 0 1 1), (1 0 1 1 1 0 0),
(0 1 0 1 1 1 0), (0 1 1 1 0 0 1),
(0 0 1 0 1 1 1), (1 1 1 0 0 1 0)
96
◊ Example 3.10
◊ Th the
Thus, th weight
i ht enumerator
t for
f the
th dual
d l code
d is
i
B(z) = 1 + 7z4
◊ Using (3.36), we obtain the probability of an undetected error for

the (7, 4) linear code given in Table 3.1
Pu(E) = 2-3[1 + 7(1 – 2p)4] – (1 – p)7
◊ This probability was also computed in Section 3.4 using the

weight distribution of the code itself
97
◊ For large n, k, and n – k, the computation becomes
practically impossible
◊ Except for some short linear codes and a few small classes
of linear codes, the weight distributions for many known
linear code are still unknown
◊ Consequently, it is very difficult to compute their

probability of an undetected error
98
◊ It is quite easy to derive an upper bound on the average probability
of an undetected error for the ensemble of all (n,
(n k) linear systematic
codes
n
⎛n⎞ i
Pu ( E ) ≤ 2 −(n−k )
∑ ⎜ ⎟
i =1 ⎝ i ⎠
p (1 − p ) n −i
= 2 − ( n − k ) [1 − (1 − p ) n ] (3.42)
◊ Since [1 – (1 – p)n] ≤ 1, it is clear that Pu(E) ≤ 2–(n – k).

◊ There exist (n,k) linear codes with probability of an undetected error,
Pu(E),
(E) upper bboundedd d bby 2-((n-k).
◊ Only a few small classes of linear codes have been proved to have
Pu(E) satisfying
ti f i the b d 2-((n-k).
th upper bound
99
Hamming
mm g Codes

g g
National Sun Yat-
Yat-sen University
Hamming Codes
◊ These codes and their variations have been widely used for
error control in digital communication and data storage
systems
◊ For any positive
i i integer
i m ≥ 3,
3 there
h exists
i a Hamming i
code with the following parameters :
◊ Code length: n = 2m – 1
◊ Number of information symbols: k = 2m – m – 1
◊ Number of parity-check symbols: n–k=m
◊ Error-correcting capability : t = 1( dmin = 3)
◊ The parity-check matrix H of this code consists of all the nonzero
m-tuple as its columns (2m-1).
101
Hamming Codes
◊ In systematic form, the columns of H are arranged in the

following form :
H = [Im Q]
◊ where Im is an m × m identity matrix
◊ The submatrix Q consists of 2m – m – 1 columns which are the
l off weight
m-tuples i h 2 or more
◊ The columns of Q may be arranged in any order without

affecting the distance property and weight distribution of
the code
102
Hamming Codes
◊ In systematic form, the generator matrix of the code is

G = [QT I2m–m–1]
◊ where QT is the transpose of Q and I 2m–m–1 is an (2m – m – 1) ×
(2m – m – 1) id
identity
i matrix
i
◊ Since the columns of H are nonzero and distinct, no two
columns add to zero
◊ Since H consists of all the nonzero m-tuples as its columns,
the vector sum of any two columns, say hi and hj, must
also be a column in H, say hl
hi + hj + hl = 0
◊ The minimum distance of a Hamming code is exactly 3
103
Hamming Codes
◊ The code is capable of correcting all the error patterns with

a single error or of detecting all the error patterns of two or
fewer errors
◊ If we form the standard array for the Hamming code of

length 2m – 1
◊ All the (2m–1)-tuple of weight 1 can be used as coset leaders
◊ The number of (2m–1)-tuples of weight 1 is 2m – 1
◊ Since n – k = m, the code has 2m cosets
◊ The zero vector 0 and the (2m–1)-tuples of weight 1 form all the
coset leaders of the standard array
104
Hamming Codes
◊ A t-error-correcting code is called a perfect code if its

standard array has all the error patterns of t or fewer errors
and no others as coset leader
◊ Besides the Hamming codes, the only other nontrivial

binary perfect code is the (23, 12) Golay code (section 5.9)
◊ Decoding of Hamming codes can be accomplished easily

with the table
table-lookup
lookup scheme
105
Hamming Codes
◊ We may delete any l columns from the parity-check matrix

H of a Hamming code
◊ This deletion results in an m × (2m – l – 1) matrix H'
◊ Using H' as a parity-check matrix, we obtain a shortened
Hamming code with the following parameters :
◊ Code length: n = 2m – l – 1
◊ Number of information symbols: k = 2m – m – l – 1
◊ Number of parity-check symbols: n–k=m
◊ Minimum distance : dmin ≥ 3
◊ If we delete columns from H properly, we may obtain a
shortened Hamming code with minimum distance 4
106
Hamming Codes
◊ For example, if we delete from the submatrix Q all the columns of
g , we obtain an m x 2m-1 matrix.
even weight,
H’=[Im Q’]
◊ Q’ consists of 2m-1-m columns of odd weight.
◊ Since all columns of H’ have odd weight, no three columns add

to zero.
◊ However,
H ffor a column
l hi off weight
i h 3 in
i Q’,’ there
h exists
i three
h
columns hj, hl, and hs in Im such that hi +hj+hl+hs=0.
◊ Thus,
Thus the shortened Hamming code with H H’ as a parity-check
matrix has minimum distance exactly 4.
◊ The distance 4 shortened Hamming g code can be used for
correcting all error patterns of single error and simultaneously
detecting all error patterns of double errors
107
Hamming Codes
◊ When a single error occurs during the transmission of a code
vector,, the resultant syndrome
y is nonzero and it contains an odd
number of 1’s (e x H’T corresponds to a column in H’)
◊ When double errors occurs, the syndrome is nonzero, but it
contains
t i even number b off 1’s
1’
◊ Decoding can be accomplished in the following manner :
◊ If the syndrome s is zero,
zero we assume that no error occurred
◊ If s is nonzero and it contains odd number of 1’s, we assume that
a ssingle
g e error
e o occurred.
occu ed. Thee error
e o pattern
p e ofo a single
s g e error
e o that
corresponds to s is added to the received vector for error
correction
◊ If s is
i nonzero andd it
i contains
i even number b off 1’s,
1’ an
uncorrectable error pattern has been detected
108
Hamming Codes
◊ The dual code of a (2m–1, 2m–m–1) Hamming code is a
(2m–11,m)
m) linear code
◊ If a Hamming code is used for error detection over a BSC,
its probability of an undetected error,
error Pu(E),
(E) can be
computed either from (3.35) and (3.43) or from (3.36) and
(
(3.44))
◊ Computing Pu(E) from (3.36) and (3.44) is easier
◊ Combining (3.36)
(3 36) and (3.44),
(3 44) we obtain
2 m-1 2 m–1
Pu(E) = 2 {1+(2 – 1)(1 – 2p) } – (1 – p)
-m m
◊ The probability Pu(E) for Hamming codes does satisfy the

upper bound 2–(n–k) = 2-m for p ≤ ½ [i.e., Pu(E) ≤ 2-m]
109

CC 03 Linear Block Code

Uploaded by

Copyright:

Available Formats

CC 03 Linear Block Code

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CC 03 Linear Block Code

Uploaded by

Copyright:

Available Formats

Chapter 3

Linear Block Codes

Wireless Information Transmission System Lab.

◊ Introduction to linear block codes

Wireless Information Transmission System Lab.

◊ We assume that the output of an information source is a

◊ This set of 2k code words is called a block code.

◊ Definition 3.1. A block code of length n and 2k code

◊ In fact, a binary block code is linear iff the module-2 sum

For large k, it is virtually impossible to build up the look-up table.

◊ Since an (n, k) linear code C is a k-dimensional subspace

where ui = 0 or 1 for 0 ≤ i < k

◊ If u = (u0,u1,…,uk-1) is the message to be encoded, the

◊ Because the rows of G generate the (n, k) linear code C,

◊ Note that any k linearly independent code words of an (n,

◊ It follows from (3.3) that an (n, k) linear code is

◊ If u = (1 1 0 1) is the message to be encoded, its corresponding

◊ A desirable property for a linear block code is the

Redundant checking part Message part

Fig. 3.1 Systematic format of a code word

◊ A linear systematic (n, k) code is completely specified by a

⎡ g 0 ⎤ ⎡ p00 p 01 . . . p0,n − k −1 | 1 0 0 . 0⎤. .

◊ Let u = (u0, u1, … , uk-1) be the message to be encoded

◊ It follows from (3.4) & (3.5) that the components of v are

◊ Equation (3.6a) shows that the rightmost k digits of a code

◊ Equation (3.6b) shown that the leftmost n – k redundant

◊ The n – k equations given by (3.6b) are called parity-check

The code word corresponding to the message (1 0 1 1) is (1 0 0 1 0 1 1)

◊ If the generator matrix of an (n,k) linear code is in the

◊ Let hj be the jth row of H

for 0 ≤ i < k and 0 ≤ j < n – k

◊ This implies that G • HT = 0

◊ Let u = (u0, u1, …, uk-1) be the message to be encoded

◊ An (n, k) linear code is completely specified by its parity-

◊ For any (n, k) linear block code C, there exists a k × n

◊ There exist an (n – k) × n matrix H such that an n-tuple

◊ The complexity of the encoding circuit is linearly proportional to

Wireless Information Transmission System Lab.

◊ Upon receiving r, the decoder must first determine

◊ s = 0 if and only if r is a code word and receiver accepts r

◊ s≠0 if and only if r is not a code word and the presence of

◊ When the error pattern e is identical to a nonzero code

s0 = r0 + rn-k p00 + rn-k+1 p10 + ··· + rn-1 pk-1,0,

◊ Since r is the vector sum of v and e, it follows from (3.10)

◊ Consequently, we obtain the following relation between

◊ If the parity-check matrix H is expressed in the systematic

◊ Let v = (v0, v1, … , vn-1) be a binary n-tuple, the Hamming

◊ Let v and w be two nn-tuple

◊ If C is a linear block, the sum of two vectors is also a code vector

◊ 3 1 The minimum distance of a linear block code is equal

◊ Theorem 3.2 Let C be an (n, k) linear code with parity-check matrix

of H such that the vector sum of these l columns is equal to the

◊ Let C be a linear block code with parity-check matrix H

◊ Corollary 3.2.1 If no d-1 or fewer columns of H add to 0,

◊ Corollary 3.2.2 The minimum weight of C is equal to the

◊ If the minimum distance of a block code C is dmin, any two

◊ These 2n – 2k error patterns are detectable error patterns

respectively. Let w be any other code vector in C.

transmission of v. We have d(v,r)=t’.