Majority logic decoding

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

If we have a binary alphabet made of $0,1$ and we use an $(n,1)$ repetition code, then we have each input bit mapped to the codeword as a string of $n$-replicated input bits. We generally choose $n=2t+1$, an odd number.

The repetition codes can correct 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

You have a $(n,1)$ code word, where $n=2t+1$ an odd number.

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

Example

If you had a $(n,1)$ code, with R=[1 0 1 1 0], then you would decode it 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/