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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 0,1} , if a Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle [n/2]} transmission errors. Decoding errors occur when the more than these transmission errors occur. Thus, assuming bit-transmission errors are independent, the probability of error for a repetition code is given by Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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

Assumptions

The code word is Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (n,1)} , where $n=2t+1$, an odd number.

• Calculate the $d_{H}$ Hamming weight of the repetition code.
• if Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d_{H}\leq t} , decode code word to be all 0's
• if Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d_{H}\geq t+1} , decode code word to be all 1's

Example

In a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (n,1)} code, if R=[1 0 1 1 0], then it would be decoded as,

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=5, t=2} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_H = 3 } , so R'=[1 1 1 1 1]
• Hence the transmitted message bit was 1.

Source

http://wikipedia.org/

See Also on BitcoinWiki

• Xriba
• Bitlumens
• Õpet Foundation
• Travelertoken
• HELIX Orange