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 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 the 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

Assumptions

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

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

1. Rice University, http://cnx.rice.edu/content/m0071/latest/