Majority logic decoding

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In error detection and correction, majority logic decoding is a method to decode repetition codes, based on the assumption that the largest number of occurrences of a symbol was the transmitted symbol.

In error detection and correction, majority logic decoding is a method to decode repetition codes, based on the assumption that the largest number of occurrences of a symbol was the transmitted symbol.

Theory

In a binary alphabet made of 0,1 , if a (n,1) repetition code is used, then each input bit is mapped to the code word as a string of n -replicated input bits. Generally n=2t + 1 , an odd number. The repetition codes can detect up to [n/2] transmission errors. Decoding errors occur when more than these transmission errors occur. Thus, assuming bit-transmission errors are independent, the probability of error for a repetition code is given by P_e = \sum_{k=\frac{n+1}{2}}^{n} {n \choose k} \epsilon^{k} (1-\epsilon)^{(n-k)} , where \epsilon is the error over the transmission channel.

Algorithm

Assumption: the code word is (n,1) , where n=2t+1 , an odd number. Calculate the d_H Hamming weight of the repetition code. if d_H \le t , decode code word to be all 0's if d_H \ge t+1 , decode code word to be all 1's This algorithm is a boolean function in its own right, the majority function.

Example

In a (n,1) code, if R=[1 0 1 1 0], then it would be decoded as, n=5, t=2 , d_H = 3 , so R'=[1 1 1 1 1] Hence the transmitted message bit was 1.

References

Rice University, https://web.archive.org/web/20051205194451/http://cnx.rice.edu/content/m0071/latest/

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375543013 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001375543013 · captured 1789728757.0 · version history

Cite this page as: encyclopegia.org, “Majority logic decoding”, snapshot enwiki-001375543013. https://encyclopegia.org/a/majority-logic-decoding

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.