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

**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.

syndrome |
coset leader |

David Joyner 2007-09-03