Properties of Linear Block Codes
Saravanan Vijayakumaran
[email protected]
Department of Electrical Engineering
Indian Institute of Technology Bombay
July 31, 2015
1 / 17
Minimum Distance of a Linear Block Code
Definition
The minimum distance of a block code C is defined as
dmin =
min
x,yC,x6=y
d(x, y)
Theorem
The minimum distance of a linear block code is equal to the
minimum weight of its nonzero codewords
Proof.
= min wt(x + y) x, y C, x 6= y
= min wt(v) v C, v 6= 0
dmin
2 / 17
Example
Find the minimum distance of a linear block with parity check
matrix
1 0 0 1 0 1 1
H = 0 1 0 1 1 1 0
0 0 1 0 1 1 1
Theorem
Let C be a binary linear block code with parity check matrix H.
There exists a codeword of weight w in C there exist w
columns in H which sum to the zero vector.
Corollary
If no w 1 or fewer columns of H sum to 0, the code has
minimum distance at least w.
Corollary
The minimum distance of C is the equal to the smallest number
of columns of H which sum to 0.
3 / 17
Singleton Bound
Let C be an (n, k ) binary block code with minimum distance
dmin .
dmin n k + 1
Proof.
Suppose C is a linear block code.
What is the rank of H?
Suppose C is not a linear block code.
Puncture the first dmin 1 locations in each codeword.
Can two punctured codewords be the same?
4 / 17
Error Detection using Linear Block Codes
Suppose an (n, k , dmin ) linear block code C is used for
error detection
Let x be the transmitted codeword and y is the received
vector
y=x+e
The receiver declares an error if y is not a codeword
Any error pattern of weight dmin 1 or less will be detected
Of the 2n 1 nonzero error patterns 2k 1 are the same
as nonzero codewords in C 2k 1 error patterns are
undetectable and 2n 2k are detectable
Let Ai be the number of codewords of weight i in C
Probability of undetected error over a BSC is given by
Pue =
n
X
Ai pi (1 p)ni
i=1
5 / 17
Example
Find the weight distribution of a linear block with parity check
matrix
1 0 0 1 0 1 1
H = 0 1 0 1 1 1 0
0 0 1 0 1 1 1
A0 = 1, A7 = 1, A1 = 0, A2 = 0, A3 = 7, A4 = 7, A5 = 0, A6 = 0
Pue = 7p3 (1 p)4 + 7p4 (1 p)3 + p7
6 / 17
Probability of Undetected Error
Pue = 7p3 (1 p)4 + 7p4 (1 p)3 + p7
101
102
103
104
105
106
Pue
7p3
107
108 3
10
102
p
101
7 / 17
The Standard Array
Let C be an (n, k ) linear block code
Let v1 , v2 , . . . , v2k be the codewords in C with v1 = 0
The standard array for C is constructed as follows
1. Put the codewords vi in the first row starting with 0
2. Find a smallest weight vector e Fn2 not already in the array
3. Put the vectors e + vi in the next row starting with e
4. Repeat steps 2 and 3 until all vectors in Fn2 appear in the
array
1 1 0 0
Example: G =
0 0 1 1
0000
1000
0010
0110
1100
0100
1110
1010
0011
1011
0001
0101
1111
0111
1101
1001
8 / 17
Properties of the Standard Array
Each row has 2k distinct vectors
The rows are disjoint
There are 2nk rows
The rows are called cosets of the code C
The first vector in each row is called a coset leader
Decoding using the standard array
Let 0, e2 , e3 , . . . , e2nk be the coset leaders
Let Dj be the jth column of the standard array
Dj = {vj , e2 + vj , e3 + vj , . . . , e2nk + vj }
Decode a vector which belongs to Dj to vj
Any error pattern equal to a coset leader is correctable
Every (n, k ) linear block code can correct 2nk error
patterns
9 / 17
Example
0 1 1 1 0 0
G = 1 0 1 0 1 0
1 1 0 0 0 1
000000
100000
010000
001000
000100
000010
000001
100100
011100
111100
001100
010100
011000
011110
011101
111000
101010
001010
111010
100010
101110
101000
101011
001110
110001
010001
100001
111001
110101
110011
110000
010101
110110
010110
100110
111110
110010
110100
110111
010010
101101
001101
111101
100101
101001
101111
101100
001001
011011
111011
001011
010011
011111
011001
011010
111111
000111
100111
010111
001111
000011
000101
000110
100011
The code has minimum distance 3
It corrects all single-bit errors and one double-bit error
10 / 17
Syndrome Decoding
All vectors in the same row of the standard array have the
same syndrome
Vectors in different rows have different syndromes
Steps in syndrome decoding
Compute the syndrome y H T of the received vector y
Find the coset leader ei whose syndrome equals y H T
= y + ei
Decode y into the codeword v
Let i be the number of coset leaders of weight i for C
Probability of decoding error over a BSC is given by
Pe = 1
n
X
i pi (1 p)ni
i=0
11 / 17
Probability of Decoding Error
0 1 1 1 0 0
G = 1 0 1 0 1 0
1 1 0 0 0 1
Pe = 1 (1 p)6 6p(1 p)5 p2 (1 p)4
101
102
103
104
Pe
105 3
10
102
p
101
12 / 17
Hamming Bound
Let C be an (n, k ) binary linear block code with minimum
distance dmin 2t + 1.
n
n
n
nk
2
1+
+
+ +
1
2
t
Proof.
Does dmin 2t + 1 imply that all vectors of weight t or less are
coset leaders?
Suppose wt(x) t and wt(y) t. Can x and y be in the same
coset?
13 / 17
MacWilliams Identity
Let C be an (n, k ) binary linear block code
Let A0 , A1 , . . . , An be the weight distribution of C
Let B0 , B1 , . . . , Bn be the weight distribution of C
The corresponding weight enumerators are given by
A(z) = A0 + A1 z + An z n
B(z) = B0 + B1 z + Bn z n
The MacWilliams identity states that
(nk )
A(z) = 2
(1 + z) B
1z
1+z
14 / 17
Example
1 0 0 1 0 1 1
H = 0 1 0 1 1 1 0
0 0 1 0 1 1 1
A(z) = 1 + 7z 3 + 7z 4 + z 7
B(z) = 1 + 7z 4
"
#
1z
1z 4
3
7
3
7
2 (1 + z) B
= 2 (1 + z) 1 + 7
1+z
1+z
15 / 17
Pue and A(z)
Probability of undetected error over a BSC is given by
Pue =
n
X
Ai pi (1 p)ni
i=1
n
X
i
p
= (1 p)
Ai
1p
i=1
"
i #
n
X
p
n
Ai
= (1 p) 1 +
1p
i=0
p
n
= (1 p) A
1
1p
n
16 / 17
Questions?
17 / 17
