7 Groups and Codes 255(ii)|x+y|≤|x|+|y|.
The vector spaceVacquires the structure of a metric space if we define the (Hamming)
distancebetween the vectorsxandyto be d(x,y)=|x−y|.
Abinary linear codeis a subspaceUof the vector spaceV.IfUhas dimension
k,thenagenerator matrixfor the code is ak×nmatrixGwhose rows form a basis
forU.Theautomorphism groupof the code is the group of all permutations of then
coordinates which mapUonto itself. An [n,k,d]-binary codeis one for whichVhas
dimensionn,Uhas dimensionkanddis the least weight of any nonzero vector inU.
There are useful connections between codes and designs. Corresponding to any
design with incidence matrixAthere is the binary linear code generated overF 2 by
the rows ofA. Given a binary linear codeU, on the other hand, a theorem of Assmus
and Mattson (1969) provides conditions under which the nonzero vectors inUwith
minimum weight form the rows of the incidence matrix of at-design.
Suppose now thatHis a Hadamard matrix of ordern, normalized so that all el-
ements in the first row are 1. ThenA=(H+Jn)/2 is a matrix of 0’s and 1’s with
all elements in the first row 1. The codeC(H)definedby the Hadamard matrixHis
the subspace generated by the rows ofA, considered as vectors in then-dimensional
vector spaceV=Fn 2.
In particular, takeH =H 24 to be the Hadamard matrix of order 24 formed by
Paley’s construction:
H 24 =I 24 +
[
0 e 23
−et 23 Q]
,
whereQ=(qjk)withqjk=0ifj=kand otherwise=1or−1 according asj−k
is or is not a square mod 23( 0 ≤j,k≤ 22 ). It may be shown that theextended binary
Golay code G 24 =C(H 24 )is a 12-dimensional subspace ofF^242 , that the minimum
weight of any nonzero vector inG 24 is 8, and that the sets of nonzero coordinates
of the vectorsx ∈G 24 with|x|=8 form the blocks of a 5-( 24 , 8 , 1 )design. The
Mathieu groupM 24 may be defined as the automorphism group of this design or as the
automorphism group of the codeG 24.
Again, suppose thatH(m)is the Hadamard matrix of ordern= 2 mdefined by
H(m)=H 2 ⊗···⊗H 2 (mfactors),where
H 2 =[
11
1 − 1
]
.
Thefirst-order Reed–Muller code R( 1 ,m)=C(H(m))is an(m+ 1 )-dimensional sub-
space ofFn 2 and the minimum weight of any nonzero vector inR( 1 ,m)is 2m−^1 .Itmay
be mentioned that the 3-( 2 m, 2 m−^1 , 2 m−^2 − 1 )design associated with the Hadamard
matrixH(m)has a simple geometrical interpretation. Its points are the points of
m-dimensional affine space over the field of two elements, and its blocks are the
hyperplanes of this space (not necessarily containing the origin).
In electronic communication a message is sent as a sequence of ‘bits’ (an abbrevi-
ation forbinary digits), which may be realised physically byofforonand which may