Majority logic decoding

From Wikipedia, the free encyclopedia

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.

Contents

[edit] Theory

If we have a binary alphabet made of 0,1 and we use an (n,1) repetition code, then we have each input bit mapped to the codeword as a string of n-replicated input bits. We generally choose n = 2t + 1, an odd number.

The repetition codes can correct up to [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 P_e = \sum_{k=\frac{n+1}{2}}^{n} {n \choose k} P_e^{k} (1-P_e)^{(n-k)}.

[edit] Algorithm

[edit] Assumptions

You have a (n,1) code word, where n = 2t + 1 an odd number.

  • Calculate the dH 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

[edit] Example

If you had a (n,1) code, with R=[1 0 1 1 0], then you would decode it as,

  • n = 5,t = 2, dH = 3, so R'=[1 1 1 1 1]
  • Hence the transmitted message bit, was 1.

[edit] References

  1. Rice University, http://cnx.rice.edu/content/m0071/latest/
Languages