Syndrome decoding

Question 1

Syndrome

Answer 1

Let H be a parity check matrix for an (n, k) code C and let r ∈ F^n , then the syndrome s = syn(r ) is given by
s = Hr^T
We note that if the received word, r = c + e, where c is a codeword and e is the error pattern (also called the error vector) then
s = H(c + e)^T = He^T
The term syndrome refers to the fact that s reflects the error in the received word. The codeword itself does not contribute to the syndrome, and for an error-free codeword s = 0.

Question 2

Minimum distance decoder

Answer 2

A minimum distance decoder is a decoder that, given a received word r , selects the codeword c that satisfies d(r, c) < d/2 if such a word exists, and otherwise declares failure.
It is obvious that there can be at most one codeword within distance d/2 from a received word.

Question 3

Coset

Answer 3

Let C be an (n, k) code and a ∈ F^n. The coset containing a is the set a + C = {a + c|c ∈ C}.
Two words are in the same coset if and only if they have the same syndrome.

Question 4

Syndrome decoder

Answer 4

We can think of a decoder as a mapping of syndromes to error patterns. Thus for each syndrome we should choose
an error pattern with the smallest number of errors, and if there are several error patterns of equal weight with the same syndrome we may choose one of these arbitrarily. Such a syndrome decoder is not only a useful concept, but may also be a reasonable implementation if n − k is not too large.

Using cosets, we may define it in a different way:
Let r be a received word. A word of smallest weight in a coset can be found once and for all, such a word is called a coset leader. With a list of syndromes and corresponding coset leaders, syndrome decoding can be performed as follows:
Decode into r − f where f is the coset leader of the coset corresponding to syn(r ).
In this way we actually do maximum likelihood decoding and can correct q^{n−k} error patterns. If we only list the cosets where the coset leader is unique and have the corresponding syndromes we do minimum distance decoding.

Question 5

Hamming bound

Answer 5

If C is an (n, k) code over a field F with q elements that corrects t errors, then
\sum_{j=0}^t (q − 1)^j (n j) ≤ q^{n−k}.
The bound can be seen as an upper bound on the minimum distance of a code with given n and k, an upper bound on k if n and d are given or as a lower bound on n if k and d are given.