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 {\displaystyle 0,1} , if a ( n , 1 ) {\displaystyle (n,1)} repetition code is used, then each input bit is mapped to the code word as a string of n {\displaystyle n} -replicated input bits. Generally n = 2 t + 1 {\displaystyle n=2t+1} , an odd number.
The repetition codes can detect up to [ 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 P e = ∑ k = n + 1 2 n ( n k ) ϵ k ( 1 − ϵ ) ( n − k ) {\displaystyle P_{e}=\sum _{k={\frac {n+1}{2}}}^{n}{n \choose k}\epsilon ^{k}(1-\epsilon )^{(n-k)}} , where ϵ {\displaystyle \epsilon } is the error over the transmission channel.
Algorithm
Assumption: the code word is ( n , 1 ) {\displaystyle (n,1)} , where n = 2 t + 1 {\displaystyle n=2t+1} , an odd number.
- Calculate the d H {\displaystyle d_{H}} Hamming weight of the repetition code.
- if d H ≤ t {\displaystyle d_{H}\leq t} , decode code word to be all 0's
- if d H ≥ 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.
Example
In a ( n , 1 ) {\displaystyle (n,1)} code, if R=[1 0 1 1 0], then it would be decoded as,
- n = 5 , t = 2 {\displaystyle n=5,t=2} , d H = 3 {\displaystyle d_{H}=3} , so R'=[1 1 1 1 1]
- Hence the transmitted message bit was 1.