TABLE OF CONTENTS A code is of practical use only if an efficient decoding scheme can be applied to it. In this section, we discuss a rather simple but elegant nearest neighbour decoding for linear codes, as well as a modification that improves its performance when the length of the code is large.
We begin with the notion of a coset. Cosets play a crucial role in the decoding schemes to be discussed in this chapter.
Let C be a linear code of length n over F q, and let u ? 
be any vector of length n; we define the coset of C determined by u to be the set
For the reader who knows some group theory, note that, by considering the vector addition, is a finite abelian group, and a linear code C over F q of length n is also a subgroup of . The coset of a linear code defined above coincides with the usual notion of a coset in group theory.
Let q = 2 and C = {000 , 101 , 010 , 111}. Then
Note that
Let C be an [ n, k, d] -linear code over the finite field F q . Then,
every vector of is contained in some coset of C;
for all u ? , C
