Discrete Mathematics and Algorithms (CSE611)

Dr. Ashok Kumar Das

Assistant Professor
Center for Security, Theory and Algorithmic Research
International Institute of Information Technology, Hyderabad
Gachibowli 500 032, Hyderabad, India
E-mail: [Link]@[Link]
Homepage: [Link]
Personal Homepage: [Link]

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

1 / 32

Topic: Coding Theory (Group

Codes)

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

2 / 32

Error Detection

Pb : probability that of a single bit error; also known as the bit error
rate.
P1 : probability that a frame arrives with no bit erros.
P2 : probability that a frame arrives with one or more undetected
bit errors.
Then, we have
P1 = (1 Pb )|F | ,
P2 = 1 P1 ,
where |F | is the number of bits per frame.

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

3 / 32

Error Detection
Transmitter
E=f(Data)

Data

Data

Receiver
Data

E=f(Data)

Compare?

E, E : Error detecting codes

f: Error detecting code function
Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

4 / 32

Error Detection

For a given frame of bits, additional bits that constitute an

error-detecting code are added by the transmitter. This code is
calculated as a function of the other transmitted bits.
The receiver performs the same calculation and compare the two
results. A detected error occurs if and only if there is a mismatch.

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

5 / 32

Group Codes

Definition
Let x and y be binary n-tuples, i.e., x = hx1 , x2 , . . . , xn i and
y = hy1 , y2 , . . . , yn i, where xi , yi {0, 1}. The Hamming distance
between x and y denoted as H(x, y) is the number of co-ordinates
(components) in which they differ.
Example: The Hamming distance between h1, 0, 1i and h1, 1, 0i is
H(h1, 0, 1i, h1, 1, 0i) = 2.
The Hamming distance between two n-tuples is equal to the
number of independent single errors needed to change one
n-tuple into the other.

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

6 / 32

Group Codes

Properties
H(x, y ) 0, x, y C, where C is the set of code words which
are n-tuples ci = hci,1 , ci,2 , . . . , ci,n i, ci,j {0, 1}.
H(x, y ) = 0 if and only if x = y .
H(x, y ) = H(y , x), x, y C.
H(x, z) H(x, y ) + H(y, z), x, y, z C.

Definition
The minimum distance (or minimum Hamming distance) of an
n-coordinate code, C is Hc = minci ,cj C H(ci , cj ).

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

7 / 32

Group Codes

Theorem
A code C can detect all combinations of d or fewer errors if and only if
its minimum distance is at least (d + 1).
In other words,
C can detect d errors
if and only if
Hc = minimum distance of C = minci ,cj C H(ci , cj ) (d + 1).

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

8 / 32

Group Codes
Theorem
A code C can correct every combination of t or fewer errors if and only
if its minimum distance is at least (2t + 1).
Proof. Let C be a code of n-tuple code words ci , where
ci = hci,1 , ci,2 , . . . , ci,n i, ci,j {0, 1}.
The Hamming distance H(x, y) between two n-tuple code words x abd
y , where x, y C, is H(x, y) = number of coordinates in which they
differ.
The minimum Hamming distance is given by Hc = minci ,cj C H(ci , cj ).
() : Given C can correct t errors.
RTP: Hc = 2t + 1, that is, x, y C, H(x, y) (2t + 1).
If possible, let x, y C such that H(x, y) = 2t.
Let l1 , l2 , . . . , l2t be the coordinates (positions) where x and y differ.
Select l1 , l2 , . . . , lt and change x to another n-tuple x 0 by changing x in
these positions. Therefore, H(x, x 0 ) = t.
Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

9 / 32

Group Codes
Proof (Continued . . .)

x
t

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

10 / 32

Group Codes

Proof (Continued . . .) But, then from the property of Hamming

distance, we have:
H(x, y) H(x, x 0 ) + H(x 0 , y)
= t +t
H(x, y) 2t.
There exists some n-tuple x 0 that satisfies H(x, x 0 ) = t and
H(x 0 , y ) t.
This is a contradiction. Hence, Hc = 2t + 1, that is,
x, y C, H(x, y) (2t + 1).

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

11 / 32

Group Codes
Proof (Continued . . .)
() : Given Hc = 2t + 1, that is, x, y C,
H(x, y ) 2t + 1.

(1)

Let x 0 be a received n-tuple that is corrupted by NOT more than t

errors and x be a code word. x 0 has thus changed from x by t or fewer
errors. Hence,
H(x, x 0 ) t.

(2)

From the properties of Hamming distance, we have

H(x, y) H(x, x 0 ) + H(x 0 , y)
H(x 0 , y) H(x, y) H(x, x 0 )
t + 1, using Eqns. (1) and (2).
Therefore, every code word y is farther than x 0 than is x, and x can be
correctly decoded.
2
Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

12 / 32

Group Codes
Definition
A group code is a code from which n-tuple code words forms a group
with respect to the operation (modulo-2 or bitwise XOR), where
x y = hx1 y1 , x2 y2 , . . . , xn yn i.

Definition
The weight of a code word x, denoted by w(x), is the number of its
coordinates (or components) that are 1s, that is, w(x) = number of 1s
in x.
Example: w(h1, 1, 1, 1i) = 4
w(h1, 1, 0, 0i) = 2.
We denote the n-tuple h0, 0, . . . , 0i by 0.
Note that w(x) = H(x, 0),
H(x, y) = H(x y , 0) = w(x y ).
Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

13 / 32

Group Codes

Lemma
The minimum distance of a group code, C is equal to the minimum
weight of its non-zero code words.

Definition
Let H be an r n binary matrix. Then the set of binary n-tuples x that
satisfies x.H t = 0 is called the null space of H, N(H). In other words,
N(H) = {x|x.H t = 0, x C},
where C is the group code and H t the transposition of the matrix H.

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

14 / 32

Group Codes
Theorem
The null space N(H) of an r n binary matrix H is a group under ,
componentwise addition modulo-2 (XOR).
Proof. Let H be an r n binary matrix (parity-check matrix) and C a
group code of n-tuples code words. Then the null space of H, N(H) is
N(H) = {x|x.H t = 0, x C},
where C is the group code and H t the transposition of the matrix H.
RTP: hN(H), i is a group.
Closure: Let x, y N(H). Then, x.H t = 0 and y.H t = 0.
Therefore,
x.H t y .H t = 0 (x y ).H t = 0. (x y) N(H). Hence,
closure axiom holds.
Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

15 / 32

Group Codes
Proof (Continued . . .). .
Associativity: Since ((x y) z).H t = (x (y z)).H t ,
x, y , z N(H), we have
(x y) z = x (y z). Associativity under holds.
Existence of Identity: We have:
(0 x).H t = (x 0).H t = x.H t , x N(H). Thus,
0 x = x = x 0, x N(H). This implies that 0 = h0, 0, . . . , 0i is
the identity in N(H).
Existence of Inverse: It is noted that
(x x).H t = 0.H t = 0
x x = 0, x N(H).
It shows that every element x N(H) is its own inverse.
As a result, N(H) forms a group under .
2

Corollary
hN(H), i is an abelian (commutative) group.
Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

16 / 32

Group Codes
Theorem
Let c1 , c2 , . . . , cd be d distinct columns of the parity check r n matrix
H. Then the r -tuple sum c1 c2 cd is 0 if and only if the null
space of H, N(H) has a code word of weight d.

Theorem
H is a parity-check matrix for a code of minimum weight at least 3 if
and only if
(i) no column of H is all 0s; and
(ii) no two columns are identical.
(iii) there exists three columns, whose sum is 0, that is, Ci , Cj , Ck
such that Ci Cj Ck = 0.

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

17 / 32

Error detection/correction capability

Theorem
Let H be an r n binary parity-check matrix of the form [P|Ir ], where Ir
is an r r identity matrix, and P an arbitrary r (n r ) matrix. Then
the code defined by H has 2nr code words. H is called the canonical
parity-check matrix.
Error detection/correction capability of N(H), the null space of a
parity-check matrix H of a code, C
= minimum weight of C
= minimum number of columns, d of H that sum to 0
= d.

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

18 / 32

Code generation by parity checks

Let H = [P|Ir ] be a canonical parity-check matrix, where Ir is an r r
identity matrix, and P an arbitrary r (n r ) matrix.
Let k = n r .
Let

h11 h12 h1k 1 0 0

h21 h22 h2k 0 1 0

.. ..
..
..
..
..
.. .
H = ...
. .
.
.
.
.
.

hr 1 hr 2 hrk 0 0 1
P
Ir
Encoding Procedure:
Given a k -tuple message x = hx1 , x2 , . . . , xk i, we need to compute
the corresponding n-tuple code word (frame = message + error
code) y = hy1 , y2 , . . . , yk , yk+1 , . . . , yn i, where k = n r , that is,
n = k + r.
Set yi xi , for all 1 i k.
Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

19 / 32

Code generation by parity checks

Compute yk+i for 1 i r as the modulo-2 sum:

y1 h11 y2 h12
yk h1k yk+1 h1,k+1 = 0, since h1,k+1 = 1
yk+1 = y1 h11 y2 h12 yk h1k .
Similarly,
yk+2 = y1 h21 y2 h22 yk h2k .
In general,
yk+i

k
M

yj hi,j .

j=1

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

20 / 32

Code generation by parity checks

Decoding Procedure:
Let C be a group code with individual code words ci .
Assume that the true code word is the n-tuple x, but the observed
n-tuple is x 0 , which is x after it has been corrupted by errors.
Note that Hamming code is a single-error correcting code since H
generates a code of minimum weight at least 3.
Let  be the error n-tuple that satisfies
x0 = x 
x

= x 0 .

We now show that the problem of finding  reduces the problem of

finding the coset to which x 0 belongs.

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

21 / 32

Code generation by parity checks

Decoding Procedure (Continued...):
For each ci , let us find the error vector i that satisfies x 0 = ci i ,
that is, i = ci x 0 .
The error vectors i s forms the set E = C x 0 . Because C is a
subgroup of the group, G = h{ all n-tuples }, i, C x 0 is a coset
(right) of the group G.
Thus, we wish to find , the n-tuple of least weight in the coset that
contains x 0 (by the Maximum Likelihood method). This  is called
the coset leader for that coset.
In summary,
(i) Determine the coset to which the observed n-tuple x 0 belongs;
(ii) Find the coset leader  for that coset; and
(iii) Decode x 0 as the n-tuple x = x 0 .

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

22 / 32

Code generation by parity checks

Definition
For any observed n-tuple x 0 , the syndrome of x 0 is the r -tuple x 0 .H t ,
where r is the number of parity-check bits.

Theorem
Two n-tuples are in the same coset if and only if they have the same
syndrome.

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

23 / 32

Code generation by parity checks

Problem:
Given the following 4 9 parity-check matrix H.

1 1 0 1 0 1 0 0 0
1 0 0 1 1 0 1 0 0

0 1 1 0 1 0 0 1 0
0 0 1 1 0 0 0 0 1

(a) Does its null space N(H) have single-error correcting capability?
Justify your answer.
(b) Encode the message tuple (1 1 0 1 0).
(c) Find the error, if any, in the tuple ( 0 1 0 1 1 1 0 0 1) and hence
show that its syndrome is same as that of error tuple.

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

24 / 32

Code generation by parity checks

Solution:
Here r = 4, n = 9, k = n r = 5.
(a) N(H), the null space of H has single-error correcting capability,
because H satisfies the following properties:
(i) No column of H is all 0s;
(ii) No two columns of H are identical;
(iii) at least three columns sum is 0, i.e., minimum wight is at least 3,
since



1
1
0
1
1
0

c1 =
0 , c4 = 0 , c9 = 0 such that c1 c4 c9 = 0.
0
1
1

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

25 / 32

Code generation by parity checks

Solution (Continued...):
b) Here the message tuple is (1 1 0 1 0 ) = hx1 , x2 , x3 , x4 , x5 i. H is of
the form [P|Ir ], where P is an 4 5 matrix and I4 is the identity matrix.
Let the encoded message tuple be y = hy1 , y2 , y3 , y4 , y5 , y6 , y7 , y8 , y9 i.
Set y1 = x1 = 1;
y2 = x2 = 1;
y3 = x3 = 0;
y4 = x4 = 1;
y5 = x5 = 0.
The parity-check equations are given by
y1 y2 y4 y6 = 0 y6 = 1;
y1 y4 y5 y7 = 0 y7 = 0;
y2 y3 y5 y8 = 0 y8 = 1;
y3 y4 y9 = 0 y9 = 1.
Hence, the encoded message is h 1 1 0 1 0 1 0 1 1 i.
Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

26 / 32

Code generation by parity checks

Solution (Continued...):
(c) The observed received tuple is x 0 = h 0 1 0 1 1 1 0 0 1i. The error
syndrome is x 0 .H t = h 1 0 0 0 i. Thus, there is a single error at
(1 0 0 0)2 = 8-th position of x 0 . Hence, the decoded tuple is
x = x 0  = h 0 1 0 1 1 1 0 1 1 i, by simply flipping the 8-th bit position
of x 0 .
2

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

27 / 32

Code generation by parity checks

Problem: Let H be an r (2r 1) parity-check matrix for a
Hamming code for which the i-th column is the binary
representation of the integer i. Let H 0 be created from H by
appending a row of all 1s. Show that the null space of H 0 is a
group code with minimum distance 4.
Solution: Here H has the following form

1 0 1 0 0
0 1 1 0 1

H = 0 0 0 1 1
.. .. .. .. ..
..
. . . . .
.

1
1
1
..
.

0 0 0 0 0

where i-th column of H is the binary representation of the integer i.

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

28 / 32

Code generation by parity checks

Solution (Continued...): Now, H 0 will have the following form

1 0 1 0 0 1
0 1 1 0 1 1

0 0 0 1 1 1

H0 = . . . . .
..
.. ,
.
.
.
.
.
. . . . .
.
.

0 0 0 0 0 1
1 1 1 1 1 1
where the last row of H is appended with all 1s.

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

29 / 32

Code generation by parity checks

Solution (Continued...): N(H 0 ) is a group code with minimum

distance 4, since
No column of H 0 is all 0s;
No two columns are identical;
There does not exist three columns of H 0 whose sum is 0; and
There exists four columns C1 , C3 , C4 , and C5 such that
C1 C3 C4 C5 = 0.

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

30 / 32

Code generation by parity checks

Problem:
Given the following 3 7 parity-check matrix H.

1 0 1 0 1 0 1
0 1 1 0 0 1 1
0 0 0 1 1 1 1
(a) Explain why its null space is a single-error correcting code.
(b) What is the size of the (single-error correcting) code produced by H
- explain.
(c) Encode the message tuple (1 0 0 1).
(d) Decode the received tuple (0 1 1 0 0 1 0) assuming that error, if
any, is a single error error.

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

31 / 32

End of this lecture

Dr. Ashok Kumar Das (IIIT-H)

Discrete Maths and Algorithms (Monsoon16)

32 / 32