# Syndrome decoding

Let be a linear code of length over having check matrix . Let .

Definition 3.8.1   Let . The set is called the coset of v. The set of all cosets is denoted . The vector is called the syndrome of v. The set of all cosets is denoted or .

Proposition 3.8.2   The cosets are in 1-1 correspondence with the cosets: there is a bijection given by .

proof: First, we show that the map is well-defined (i.e., independent of the choice of coset representative. For all , we have if and only if if and only if if and only if . Thus is well-defined. is 1-1 by the same reasoning. is onto by definition. Let . An element in of lowest weight is called a coset leader, and intuitively represents the mostly likely error vector''.

Algorithm:

• Precomputation. Compute all syndromes , for and the corresponding coset leaders . (The table of values of the function is called the look-up table.)

• If v is the received vector, compute .

• Let be the corresponding coset leader obtained from the look-up table.

• Decode v as .

This algorithm is fast, assuming that assessing the look-up table takes no time, but may require a lot of time and memory initially to build the look-up table in the first place.

Example 3.8.3   If is the code over with check matrix given by Here is the look-up table:

 syndrome coset leader                Exercise 3.8.4   Let be the code in Example 3.8.3. Decode using the syndrome decoding algorithm. (Ans: .)

Exercise 3.8.5   Count the number of vectors in a ball of radius in .

Exercise 3.8.6   Show that the number of vectors in a ball of radius in does not depend on the radius. In other words, if then show .

Exercise 3.8.7   In Example 3.3.2, the code has minimum distance .

Exercise 3.8.8   In Example 3.3.6, the code has minimum distance .

Exercise 3.8.9   Pick a book and check that its ISBN satisfies the condition , in the notation of Example 3.3.6.

Exercise 3.8.10   For the code in Example 3.3.2, use the nearest neighbor algorithm to decode and .

Exercise 3.8.11   Consider the code with generator matrix Find the codeword obtained by encoding .

Exercise 3.8.12   For for the code in Example 3.3.2.

Exercise 3.8.13   Prove this Proposition 3.4.11.

Exercise 3.8.14   The vector was receieved. Assuming only one error was made, use the nearest neighbor algorithm to decode it.

Exercise 3.8.15   Show that the Hamming -code has minimum distance .

David Joyner 2007-09-03