Information Theory and Coding - Codes: The Guide to Secrecy from Ancient to Modern Times - page 453

(2 r

For an n × − 1) matrix, P , whose columns are distinct nonzero vectors in

2 , the code C having P as its parity-check matrix is called a binary Hamming
code , denoted byHam(r , 2), which has length 2 r

F

1 and dimension 2 r 1.

Since the columns are nonzero and distinct, then the minimum distance d must
be bigger than 2. In fact d = 3 since it is possible to find codewords of weight
3 for r> 1. Hence, Ham(r , 2) for r

− − r −

≥

2 is a linear, binary[2 r

−

1 , 2 r

− −

1 , 3]
single-error-correcting code, which is also a perfect code. The latter follows from
the fact that the Hamming spheres of radius 1 around the codewords exactly
fill

r

2 r − 1

2 without anyoverlapping. Another such class of distinguished linear,
binary, perfect codes is the collection of repetition codes , which are [ n, 1] codes
with generator matrix G =[1 , 1 ,..., 1], where n is odd. We will investigate yet
a third such family, called Golay codes , later, and the latter represent the last of
the possible such families, namely, the last of the possible linear, binary, perfect
codes.
Given the above, Ham(r , 2) is a binary( N, 2 k , 3)-code (equivalentlyan
[ N,k, 3]-code), where N =2 r

F

1, and k =2 r − − r − 1, which is a distinguished

class of perfect linear codes.

Example 11.11 First, we observe that the parity check matrix P is given by
column j being the binary representation of j . For instance, if r =3 , then

0001111
0110011
1010101

,

P =

where column 1 is the binary representation of 1 , column 2 is the binary rep-
resentation of 2 , and so forth. In order to get the generator matrix, we put P
into standard form,

0111100
1011010
1101001

=[

M k,N − k ,I N − k ] , P = −

where N =2 r 1=7 , k =2 r

− − r − 1=4 , then we obtain the generating matrix

from it,

1000011
0100101
0010110
0001111

G = =[ I k ,M k,N − k ] ,

which yields the [7 , 4 , 3] Hamming code. To see that this is a perfect code, let
t =1 , n = N , k =2 r − r − 1 , and q =2 in the Hamming bound on page 445 to

get

2 N
j =0 j

2 7
7+1 =2 N − r − 1 ,

M =2 4 =2 k = =

as required.