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

edit

  is considered a binary code with the length  ;   shall be elements of  ; and   is the distance between those elements.

Ideal observer decoding

edit

One may be given the message  , then ideal observer decoding generates the codeword  . The process results in this solution:

 

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

Decoding conventions

edit

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:

  1. Request that the codeword be resent – automatic repeat-request.
  2. Choose any random codeword from the set of most likely codewords which is nearer to that.
  3. If another code follows, mark the ambiguous bits of the codeword as erasures and hope that the outer code disambiguates them
  4. Report a decoding failure to the system

Maximum likelihood decoding

edit

Given a received vector   maximum likelihood decoding picks a codeword   that maximizes

 ,

that is, the codeword   that maximizes the probability that   was received, given that   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,

 

Upon fixing  ,   is restructured and   is constant as all codewords are equally likely to be sent. Therefore,   is maximised as a function of the variable   precisely when   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.[1]

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

Minimum distance decoding

edit

Given a received codeword  , minimum distance decoding picks a codeword   to minimise the Hamming distance:

 

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

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

 

then:

 

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:

  1. The probability   that an error occurs is independent of the position of the symbol.
  2. Errors are independent events – 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

edit

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.[3]

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:

 

To perform ML decoding in a binary symmetric channel, one has to look-up a precomputed table of size  , mapping   to  .

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

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

 

List decoding

edit

Information set decoding

edit

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   be the   generator matrix of   used for encoding. Select   columns of   at random, and denote by   the corresponding submatrix of  . With reasonable probability   will have full rank, which means that if we let   be the sub-vector for the corresponding positions of any codeword   of   for a message  , we can recover   as  . Hence, if we were lucky that these   positions of the received word   contained no errors, and hence equalled the positions of the sent codeword, then we may decode.

If   errors occurred, the probability of such a fortunate selection of columns is given by  .

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

Partial response maximum likelihood

edit

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

edit

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)

edit

Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system.[clarification needed][6]

See also

edit

References

edit
  1. ^ Feldman, Jon; Wainwright, Martin J.; Karger, David R. (March 2005). "Using Linear Programming to Decode Binary Linear Codes". IEEE Transactions on Information Theory. 51 (3): 954–972. CiteSeerX 10.1.1.111.6585. doi:10.1109/TIT.2004.842696. S2CID 3120399.
  2. ^ Aji, Srinivas M.; McEliece, Robert J. (March 2000). "The Generalized Distributive Law" (PDF). IEEE Transactions on Information Theory. 46 (2): 325–343. doi:10.1109/18.825794.
  3. ^ Beutelspacher, Albrecht; Rosenbaum, Ute (1998). Projective Geometry. Cambridge University Press. p. 190. ISBN 0-521-48277-1.
  4. ^ Stern, Jacques (1989). "A method for finding codewords of small weight". Coding Theory and Applications. Lecture Notes in Computer Science. Vol. 388. Springer-Verlag. pp. 106–113. doi:10.1007/BFb0019850. ISBN 978-3-540-51643-9.
  5. ^ Ohta, Kazuo; Pei, Dingyi, eds. (1998). Advances in Cryptology — ASIACRYPT'98. Lecture Notes in Computer Science. Vol. 1514. pp. 187–199. doi:10.1007/3-540-49649-1. ISBN 978-3-540-65109-3. S2CID 37257901.
  6. ^ Siamack Ghadimi (2020), Optimal decision decoding algorithm (ODDA) for an asymmetric TWRC system;, Universal Journal of Electrical and Electronic Engineering

Further reading

edit