Majority logic decoding

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

In a binary alphabet made of , if a repetition code is used, then each input bit is mapped to the code word as a string of -replicated input bits. Generally , an odd number.

The repetition codes can detect up to 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 , where is the error over the transmission channel.

Algorithm[edit]

Assumptions[edit]

The code word is , where , an odd number.

  • Calculate the Hamming weight of the repetition code.
  • if , decode code word to be all 0's
  • if , decode code word to be all 1's

Example[edit]

In a code, if R=[1 0 1 1 0], then it would be decoded as,

  • , , so R'=[1 1 1 1 1]
  • Hence the transmitted message bit was 1.

References[edit]

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