Majority logic decoding

From Wikipedia, the free encyclopedia

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

Assumption: 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}\leq t$ , decode code word to be all 0's
if $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)$ 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

Related Articles

Wikiwand AI