Decoding methods#Syndrome decoding

In coding theory, decoding is the process of translating received messages into codewords of a given code. There have been many common methods of mapping messages to codewords. These are often used to recover messages sent over a noisy channel, such as a binary symmetric channel.

Notation

$C \subset \mathbb{F}_2^n$ is considered a binary code with the length $n$ ; $x,y$ shall be elements of $\mathbb{F}_2^n$ ; and $d(x,y)$ is the distance between those elements.

Ideal observer decoding

One may be given the message $x \in \mathbb{F}_2^n$ , then ideal observer decoding generates the codeword $y \in C$ . The process results in this solution:

: $\mathbb{P}(y \mbox{ sent} \mid x \mbox{ received})$

For example, a person can choose the codeword $y$ that is most likely to be received as the message $x$ after transmission.

=Decoding conventions=

Each codeword does not have an expected possibility: there may be more than one codeword with an equal likelihood of mutating into the received message. In such a case, the sender and receiver(s) must agree ahead of time on a decoding convention. Popular conventions include:

:# Request that the codeword be resent{{snd}} automatic repeat-request.

:# Choose any random codeword from the set of most likely codewords which is nearer to that.

:# If another code follows, mark the ambiguous bits of the codeword as erasures and hope that the outer code disambiguates them

:# Report a decoding failure to the system

Maximum likelihood decoding

Given a received vector $x \in \mathbb{F}_2^n$ maximum likelihood decoding picks a codeword $y \in C$ that maximizes

: $\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent})$ ,

that is, the codeword $y$ that maximizes the probability that $x$ was received, given that $y$ was sent. If all codewords are equally likely to be sent then this scheme is equivalent to ideal observer decoding.

In fact, by Bayes' theorem,

: $\begin{align}
\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent}) & {} = \frac{ \mathbb{P}(x \mbox{ received} , y \mbox{ sent}) }{\mathbb{P}(y \mbox{ sent} )} \\
& {} = \mathbb{P}(y \mbox{ sent} \mid x \mbox{ received}) \cdot \frac{\mathbb{P}(x \mbox{ received})}{\mathbb{P}(y \mbox{ sent})}.
\end{align}$

Upon fixing $\mathbb{P}(x \mbox{ received})$ , $x$ is restructured and

$\mathbb{P}(y \mbox{ sent})$ is constant as all codewords are equally likely to be sent.

Therefore,

$\mathbb{P}(x \mbox{ received} \mid y \mbox{ sent})$

is maximised as a function of the variable $y$ precisely when

$\mathbb{P}(y \mbox{ sent}\mid x \mbox{ received} )$

is maximised, and the claim follows.

As with ideal observer decoding, a convention must be agreed to for non-unique decoding.

The maximum likelihood decoding problem can also be modeled as an integer programming problem.

The maximum likelihood decoding algorithm is an instance of the "marginalize a product function" problem which is solved by applying the generalized distributive law.

Minimum distance decoding

Given a received codeword $x \in \mathbb{F}_2^n$ , minimum distance decoding picks a codeword $y \in C$ to minimise the Hamming distance:

: $d(x,y) = \# \{i : x_i \not = y_i \}$

i.e. choose the codeword $y$ that is as close as possible to $x$ .

Note that if the probability of error on a discrete memoryless channel $p$ is strictly less than one half, then minimum distance decoding is equivalent to maximum likelihood decoding, since if

: $d(x,y) = d,\,$

then:

: $\begin{align}
\mathbb{P}(y \mbox{ received} \mid x \mbox{ sent}) & {} = (1-p)^{n-d} \cdot p^d \\
& {} = (1-p)^n \cdot \left( \frac{p}{1-p}\right)^d \\
\end{align}$

which (since p is less than one half) is maximised by minimising d.

Minimum distance decoding is also known as nearest neighbour decoding. It can be assisted or automated by using a standard array. Minimum distance decoding is a reasonable decoding method when the following conditions are met:

:#The probability $p$ that an error occurs is independent of the position of the symbol.

:#Errors are independent events{{snd}} an error at one position in the message does not affect other positions.

These assumptions may be reasonable for transmissions over a binary symmetric channel. They may be unreasonable for other media, such as a DVD, where a single scratch on the disk can cause an error in many neighbouring symbols or codewords.

As with other decoding methods, a convention must be agreed to for non-unique decoding.

Syndrome decoding

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. This is allowed by the linearity of the code.

Suppose that $C\subset \mathbb{F}_2^n$ is a linear code of length $n$ and minimum distance $d$ with parity-check matrix $H$ . Then clearly $C$ is capable of correcting up to

: $t = \left\lfloor\frac{d-1}{2}\right\rfloor$

errors made by the channel (since if no more than $t$ errors are made then minimum distance decoding will still correctly decode the incorrectly transmitted codeword).

Now suppose that a codeword $x \in \mathbb{F}_2^n$ is sent over the channel and the error pattern $e \in \mathbb{F}_2^n$ occurs. Then $z=x+e$ is received. Ordinary minimum distance decoding would lookup the vector $z$ in a table of size $|C|$ for the nearest match - i.e. an element (not necessarily unique) $c \in C$ with

: $d(c,z) \leq d(y,z)$

for all $y \in C$ . Syndrome decoding takes advantage of the property of the parity matrix that:

: $Hx = 0$

for all $x \in C$ . The syndrome of the received $z=x+e$ is defined to be:

: $Hz = H(x+e) =Hx + He = 0 + He = He$

To perform ML decoding in a binary symmetric channel, one has to look-up a precomputed table of size $2^{n-k}$ , mapping $He$ to $e$ .

Note that this is already of significantly less complexity than that of a standard array decoding.

However, under the assumption that no more than $t$ errors were made during transmission, the receiver can look up the value $He$ in a further reduced table of size

: $\begin{matrix}
\sum_{i=0}^t \binom{n}{i}\\
\end{matrix}$

List decoding

Information set decoding

This is a family of Las Vegas-probabilistic methods all based on the observation that it is easier to guess enough error-free positions, than it is to guess all the error-positions.

The simplest form is due to Prange: Let $G$ be the $k \times n$ generator matrix of $C$ used for encoding. Select $k$ columns of $G$ at random, and denote by $G'$ the corresponding submatrix of $G$ . With reasonable probability $G'$ will have full rank, which means that if we let $c'$ be the sub-vector for the corresponding positions of any codeword $c = mG$ of $C$ for a message $m$ , we can recover $m$ as $m = c' G'^{-1}$ . Hence, if we were lucky that these $k$ positions of the received word $y$ contained no errors, and hence equalled the positions of the sent codeword, then we may decode.

If $t$ errors occurred, the probability of such a fortunate selection of columns is given by $\textstyle\binom{n-t}{k}/\binom{n}{k}$ .

This method has been improved in various ways, e.g. by Stern and Canteaut and Sendrier.

Partial response maximum likelihood

Partial response maximum likelihood (PRML) is a method for converting the weak analog signal from the head of a magnetic disk or tape drive into a digital signal.

Viterbi decoder

A Viterbi decoder uses the Viterbi algorithm for decoding a bitstream that has been encoded using forward error correction based on a convolutional code.

The Hamming distance is used as a metric for hard decision Viterbi decoders. The squared Euclidean distance is used as a metric for soft decision decoders.

Optimal decision decoding algorithm (ODDA)

Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system.{{Clarify|date=January 2023}}{{Citation |title= Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system; |author1=Siamack Ghadimi|publisher=Universal Journal of Electrical and Electronic Engineering|date=2020}}

References

{{reflist|refs=

{{cite journal |title=Using Linear Programming to Decode Binary Linear Codes |first1=Jon |last1=Feldman |first2=Martin J. |last2=Wainwright |first3=David R. |last3=Karger |journal=IEEE Transactions on Information Theory |volume=51 |issue=3 |pages=954–972 |date=March 2005 |doi=10.1109/TIT.2004.842696|s2cid=3120399 |citeseerx=10.1.1.111.6585 }}

{{cite book |author-first1=Albrecht |author-last1=Beutelspacher |author-link1=Albrecht Beutelspacher |author-first2=Ute |author-last2=Rosenbaum |date=1998 |title=Projective Geometry |page=190 |publisher=Cambridge University Press |isbn=0-521-48277-1}}

{{cite journal |last1=Aji |first1=Srinivas M. |last2=McEliece |first2=Robert J. |title=The Generalized Distributive Law |journal=IEEE Transactions on Information Theory |date=March 2000 |volume=46 |issue=2 |pages=325–343 |doi=10.1109/18.825794 |url=https://authors.library.caltech.edu/1541/1/AJIieeetit00.pdf}}

{{cite book |author-first=Jacques |author-last=Stern |date=1989 |chapter=A method for finding codewords of small weight |title=Coding Theory and Applications |series=Lecture Notes in Computer Science |publisher=Springer-Verlag |volume=388 |pages=106–113 |doi=10.1007/BFb0019850 |isbn=978-3-540-51643-9}}

{{cite book |date=1998 |editor-last1=Ohta |editor-first1=Kazuo |editor-first2=Dingyi |editor-last2=Pei |series=Lecture Notes in Computer Science |volume=1514 |pages=187–199 |doi=10.1007/3-540-49649-1 |isbn=978-3-540-65109-3 |s2cid=37257901 |title=Advances in Cryptology — ASIACRYPT'98 }}

}}