error detection and correction In information theory and coding theory with applications in computer science and telecommunication, error detection and correction (EDAC) or error control are techniques that enable reliable delivery of digital data over unreliable communi ...

, majority logic decoding is a method to decode

repetition code In coding theory, the repetition code is one of the most basic error-correcting codes. In order to transmit a message over a noisy channel that may corrupt the transmission in a few places, the idea of the repetition code is to just repeat the mess ...

s, 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 In communication, a code word is an element of a standardized code or protocol. Each code word is assembled in accordance with the specific rules of the code and assigned a unique meaning. Code words are typically used for reasons of reliability, ...

as a string of

n

-replicated input bits. Generally

n=2t + 1

, an odd number. The repetition codes can detect up to

/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 P_e = \sum_^ 

\epsilon^ (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 The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string o ...

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 In Boolean logic, the majority function (also called the median operator) is the Boolean function that evaluates to false when half or more arguments are false and true otherwise, i.e. the value of the function equals the value of the majority of t ...

Example

In a

(n,1)

code, if R= 0 1 1 0 then it would be decoded as, *

n=5, t=2

d_H = 3

, so R'= 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/ Error detection and correction