Majority logic decoding

<h2 id="theory">Theory</h2>
<p>In a binary alphabet made of 
  
    
      
        0
        ,
        1
      
    
    {\displaystyle 0,1}
  
, if a 
  
    
      
        (
        n
        ,
        1
        )
      
    
    {\displaystyle (n,1)}
  
 repetition code is used, then each input bit is mapped to the <a href="/facts/Code_word_(communication)/sASREopJ">code word</a> as a string of 
  
    
      
        n
      
    
    {\displaystyle n}
  
-replicated input bits. Generally 
  
    
      
        n
        =
        2
        t
        +
        1
      
    
    {\displaystyle n=2t+1}
  
, an odd number.
</p><p>The repetition codes can detect up to 
  
    
      
        [
        n
        
          /
        
        2
        ]
      
    
    {\displaystyle [n/2]}
  
 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
          
        
        =
        
          ∑
          
            k
            =
            
              
                
                  n
                  +
                  1
                
                2
              
            
          
          
            n
          
        
        
          
            
              (
            
            
              n
              k
            
            
              )
            
          
        
        
          ϵ
          
            k
          
        
        (
        1
        −
        ϵ
        
          )
          
            (
            n
            −
            k
            )
          
        
      
    
    {\displaystyle P_{e}=\sum _{k={\frac {n+1}{2}}}^{n}{n \choose k}\epsilon ^{k}(1-\epsilon )^{(n-k)}}
  
, where 
  
    
      
        ϵ
      
    
    {\displaystyle \epsilon }
  
 is the error over the transmission channel.
</p>
<h2 id="algorithm">Algorithm</h2>
<p>Assumption: the code word is 
  
    
      
        (
        n
        ,
        1
        )
      
    
    {\displaystyle (n,1)}
  
, where 
  
    
      
        n
        =
        2
        t
        +
        1
      
    
    {\displaystyle n=2t+1}
  
, an odd number.
</p>
<ul><li>Calculate the 
  
    
      
        
          d
          
            H
          
        
      
    
    {\displaystyle d_{H}}
  
 <a href="/facts/Hamming_weight/dJIW7qg4">Hamming weight</a> of the repetition code.</li>
<li>if 
  
    
      
        
          d
          
            H
          
        
        ≤
        t
      
    
    {\displaystyle d_{H}\leq t}
  
, decode code word to be all 0's</li>
<li>if 
  
    
      
        
          d
          
            H
          
        
        ≥
        t
        +
        1
      
    
    {\displaystyle d_{H}\geq t+1}
  
, decode code word to be all 1's</li></ul>
<p>This algorithm is a boolean function in its own right, the <a href="/facts/Majority_function/Ntpb4wDr">majority function</a>.
</p>
<h2 id="example">Example</h2>
<p>In a 
  
    
      
        (
        n
        ,
        1
        )
      
    
    {\displaystyle (n,1)}
  
 code, if R=[1 0 1 1 0], then 
it would be decoded as, 
</p>
<ul><li>
  
    
      
        n
        =
        5
        ,
        t
        =
        2
      
    
    {\displaystyle n=5,t=2}
  
, 
  
    
      
        
          d
          
            H
          
        
        =
        3
      
    
    {\displaystyle d_{H}=3}
  
, so R'=[1 1 1 1 1]</li>
<li>Hence the transmitted message bit was 1.</li></ul>

<ol><li>Rice University, <a href="https://web.archive.org/web/20051205194451/http://cnx.rice.edu/content/m0071/latest/">https://web.archive.org/web/20051205194451/http://cnx.rice.edu/content/m0071/latest/</a></li></ol>

Majority logic decoding open-in-new

Majority logic decoding