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.
Theory
In a binary alphabet made of [math]\displaystyle{ 0,1 }[/math], if a [math]\displaystyle{ (n,1) }[/math] repetition code is used, then each input bit is mapped to the code word as a string of [math]\displaystyle{ n }[/math]-replicated input bits. Generally [math]\displaystyle{ n=2t + 1 }[/math], an odd number.
The repetition codes can detect up to [math]\displaystyle{ [n/2] }[/math] 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 [math]\displaystyle{ P_e = \sum_{k=\frac{n+1}{2}}^{n} {n \choose k} \epsilon^{k} (1-\epsilon)^{(n-k)} }[/math], where [math]\displaystyle{ \epsilon }[/math] is the error over the transmission channel.
Algorithm
Assumption: the code word is [math]\displaystyle{ (n,1) }[/math], where [math]\displaystyle{ n=2t+1 }[/math], an odd number.
- Calculate the [math]\displaystyle{ d_H }[/math] Hamming weight of the repetition code.
- if [math]\displaystyle{ d_H \le t }[/math], decode code word to be all 0's
- if [math]\displaystyle{ d_H \ge t+1 }[/math], decode code word to be all 1's
This algorithm is a boolean function in its own right, the majority function.
Example
In a [math]\displaystyle{ (n,1) }[/math] code, if R=[1 0 1 1 0], then it would be decoded as,
- [math]\displaystyle{ n=5, t=2 }[/math], [math]\displaystyle{ d_H = 3 }[/math], 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/
 |  |
