Majority logic decoding explained

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 =2 t + 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 ^{n} _{k = (n +1)/(2)} {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 =2 t +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

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

1. Rice University, https://web.archive.org/web/20051205194451/http://cnx.rice.edu/content/m0071/latest/