Syndrome decoding is a highly efficient method of decoding a linear code over a noisy channel - i.e. one on which errors are made. In essence, syndrome decoding is minimum distance decoding using a reduced lookup table. It is the linearity of the code which allows for the lookup table to be reduced in size.
The simplest kind of syndrome decoding is Hamming code.
Suppose that is a linear code of length and minimum distance with parity-check matrix . Then clearly is capable of correcting up to
errors made by the channel (since if no more than errors are made then minimum distance decoding will still correctly decode the incorrectly transmitted codeword).
Now suppose that a codeword is sent over the channel and the error pattern occurs. Then is received. Ordinary minimum distance decoding would lookup the vector in a table of size for the nearest match - i.e. an element (not necessarily unique) with
for all . Syndrome decoding takes advantage of the property of the parity matrix that:
for all . The syndrome of the received is defined to be:
Under the assumption that no more than errors were made during transmission, the receiver looks up the value in a table of size
(for a binary code) against pre-computed values of for all possible error patterns . Knowing what is, it is then trivial to decode as:
Read more about this topic: Decoding Methods
Famous quotes containing the word syndrome:
“Women are taught that their main goal in life is to serve others—first men, and later, children. This prescription leads to enormous problems, for it is supposed to be carried out as if women did not have needs of their own, as if one could serve others without simultaneously attending to one’s own interests and desires. Carried to its “perfection,” it produces the martyr syndrome or the smothering wife and mother.”
—Jean Baker Miller (20th century)