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, if a repetition code is used, then each input bit is mapped to the code word as a string of -replicated input bits. Generally, an odd number.
The repetition codes can detect up to 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, where is the error over the transmission channel.

Algorithm

Assumption: the code word is, where, an odd number.
  • Calculate the Hamming weight of the repetition code.
  • if, decode code word to be all 0's
  • if, decode code word to be all 1's
This algorithm is a boolean function in its own right, the majority function.

Example

In a code, if R=, then
it would be decoded as,
  • ,, so R'=
  • Hence the transmitted message bit was 1.