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 <math>0,1</math>, if a <math>(n,1)</math> repetition code is used, then each input bit is mapped to the code word as a string of <math>n</math>-replicated input bits. Generally <math>n=2t + 1</math>, an odd number.
The repetition codes can detect up to <math>[n/2]</math> 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 <math> P_e = \sum_{k=\frac{n+1}{2}}^{n} {n \choose k} \epsilon^{k} (1-\epsilon)^{(n-k)}</math>, where <math>\epsilon</math> is the error over the transmission channel.
==Algorithm== Assumption: the code word is <math>(n,1)</math>, where <math>n=2t+1</math>, an odd number.
* Calculate the <math>d_H</math> Hamming weight of the repetition code. * if <math>d_H \le t </math>, decode code word to be all 0's * if <math>d_H \ge t+1 </math>, decode code word to be all 1's
This algorithm is a boolean function in its own right, the majority function.
==Example== In a <math>(n,1)</math> code, if R=[1 0 1 1 0], then it would be decoded as, * <math>n=5, t=2</math>, <math>d_H = 3 </math>, so R'=[1 1 1 1 1] * Hence the transmitted message bit was 1.
==References== #Rice University, https://web.archive.org/web/20051205194451/http://cnx.rice.edu/content/m0071/latest/
Category:Error detection and correction