It is often useful to restrict our attention to vectors which form a linear subspace of _{q}^{n}. Thus, a qary (n, k, d ) linear code is a subspace of _{q}^{n} of dimension k with the property that any two vectors in the subspace are separated by a Hamming distance no less than d. Figure 1.1 depicts a ternary nonlinear code and a binary linear code.
We will typically specify a linear code by its set of basis vectors (also known as generators), which form the rows of a generator matrix G. A paritycheck matrix for a linear code is a matrix H with the property that GH^{T} = 0 for some generator matrix G of the code. For example, the linear code in Figure 1.1 has paritycheck matrix
Linear codes impose a natural cosetstructure on their ambient vector spaces.
Specifically,
given a linear code
, we can say that
two vectors
v_{1}, v_{2}_{q}^{n} are in the same coset if
and only if
. Moreover, we can represent each
coset by a coset leader which is arbitrarily chosen among the lowest
weight vectors in a coset. For example, some cosets of the linear code in
Figure 1.1 are:
C_{0}  =  {000000, 001111, 111100, 110011}  
C_{1}  =  {000001, 001110, 111101, 110010}  
C_{2}  =  {000011, 001100, 111111, 110000} 
To use an (n, k, d ) binary linear code over a communications channel, a user would split his input into blocks of k bits each and encode each block b by multiplying it by the generator matrix G. The resulting nbit vector bG is sent over the channel giving a transmission rate of k/n. The receiver then decodes the received errorcorrupted vector bG + e to the nearest vector v in the code. The vector v will be equal to bG as long as the error e contains no more than bits. Figure 1.2 depicts this transmission model. The type of decoding we have described is also known as maximumlikelihood decoding because it decodes to the most likely transmitted input. Several descriptions of this communications model may be found in [42], [7], and [4].

Often when we talk about a family of linear errorcorrecting codes, we shall be interested in the asymptotic tendency of the code. Specifically, we would like that, as the length n increases, the errorcorrection capability of the code likewise increases. It has been proven that there exist families of linear codes which achieve the GilbertVarshamov bound [42], namely
1  H_{2}.  (9) 
On the other hand, the McEliece, Rodemich, Rumsey, and Welch [4] provide a well known upper bound on the parameters of linear codes
H_{2}  .  (9) 