Majority logic decoding

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 a binary alphabet made of ${\displaystyle 0,1}${\displaystyle 0,1}, if a ${\displaystyle (n,1)}${\displaystyle (n,1)} repetition code is used, then each input bit is mapped to the code word as a string of ${\displaystyle n}${\displaystyle n}-replicated input bits. Generally ${\displaystyle n=2t+1}${\displaystyle n=2t+1}, an odd number.

The repetition codes can detect up to ${\displaystyle [n/2]}${\displaystyle [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 ${\displaystyle P_{e}=\sum _{k={\frac {n+1}{2}}}^{n}{n \choose k}\epsilon ^{k}(1-\epsilon )^{(n-k)}}${\displaystyle P_{e}=\sum _{k={\frac {n+1}{2}}}^{n}{n \choose k}\epsilon ^{k}(1-\epsilon )^{(n-k)}}, where ${\displaystyle \epsilon }${\displaystyle \epsilon } is the error over the transmission channel.

Assumption: the code word is ${\displaystyle (n,1)}${\displaystyle (n,1)}, where ${\displaystyle n=2t+1}${\displaystyle n=2t+1}, an odd number.

• Calculate the ${\displaystyle d_{H}}${\displaystyle d_{H}} Hamming weight of the repetition code.
• if ${\displaystyle d_{H}\leq t}${\displaystyle d_{H}\leq t}, decode code word to be all 0's
• if ${\displaystyle d_{H}\geq t+1}${\displaystyle d_{H}\geq t+1}, decode code word to be all 1's

This algorithm is a boolean function in its own right, the majority function.

In a ${\displaystyle (n,1)}${\displaystyle (n,1)} code, if R=[1 0 1 1 0], then it would be decoded as,

• ${\displaystyle n=5,t=2}${\displaystyle n=5,t=2}, ${\displaystyle d_{H}=3}${\displaystyle d_{H}=3}, so R'=[1 1 1 1 1]
• Hence the transmitted message bit was 1.

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

• Error detection and correction