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

disadvantage maybe overcome byusing a larger message space. For instance,
if we want to look at binary15-arycodes, we need onlygo to linear codes over
F

1 2 , and omit all codewords containing some fixed value.
Given that there are manyequivalent matrices, we need a canonical choice.
It can be shown that two k

×

n matrices generate equivalent linear [ n,k ]-codes

F q if and onlyif one can be obtained from the other bya sequence of the
following operations.

over

R1. A permutation of the rows.

R2. Multiplication of a row bya nonzero scalar.

R3. Addition of a scalar multiple of one row to another.

C1. A permutation of the columns.

C2. Multiplication of a column bya nonzero scalar.

Furthermore, if G is a generator matrix for an [ n,k ]-code, then operations
R1-R3 and C1-C2 can transform G into standard form,

10 ··· 0 m 1 ,k +1 ··· m 1 ,n

01 ··· 0 m 2 ,k +1 ··· m 2 ,n

[ I k | M k,n − k ]= ,

. . . . . . . . . . . . . . .

00 ··· 1 m k,k +1 ··· m k,n

where I k is the k × k identitymatrix and M k,n − k is a k × ( n − k ) matrix.

Therefore, [ I k | M k,n − k ] has the first k columns to provide the codewords and the

−

remaining n k columns to add redundancy. Note that the generator matrix

G must have rows that are a basis for a k -dimensional subspace of the space
of all vectors of length n , namely, our linear code C . Hence, everycodeword is
uniquelyexpressible as a linear combination of the rows of G , which must be
linearlyindependent.
The first k bits are called the information symbols and the last n k bits are

the check symbols . This means, as the above example shows, that in the encod-
ing, the information symbols appear in the clear. Any code that satisfies this
propertyis said to be systematic . Moreover, the redundancyin the remaining
n

−

− k columns can be employed to do a parity check in the following fashion.

Given a generating matrix G =[ I k ,M k,n − k ], set P =[ M k,n − k | I n − k ] , where

M k,n − k is the transpose of M k,n − k . Then P is called a parity-check matrix .
Indeed, anymatrix M that, given any c

−

F n , satisfies cM t = 0 if and onlyif ∈

C is called a parity-check matrix for C . 11.8 Thus, anyerrors in transmission

c ∈

11.8 Note that when C is an [ n, k ]-code over F q with parity-checkmatrix P , then d ( C )isthe
smallest number of columns of P that are linearly dependent. It follows that if every subset
of 2 t or fewer columns of P is linearly independent, then C is capable of correcting all errors
of weight up to size t .If q = 2, this implies that when all possible linear combinations of no
more than t columns of P are distinct, then d ( C ) ≥ 2 t + 1, whence C can correct all errors
up to weight t .