Repetition code

<h2 id="code-parameters">Code parameters</h2>
<p>In the case of a binary repetition code, there exist two code words - all ones and all zeros - which have a length of 
  
    
      
        n
      
    
    {\displaystyle n}
  
. Therefore, the minimum <a href="/facts/Hamming_distance/MgdtbYPo">Hamming distance</a> of the code equals its length 
  
    
      
        n
      
    
    {\displaystyle n}
  
. This gives the repetition code an error correcting capacity of 
  
    
      
        
          
            
              
                n
                −
                1
              
              2
            
          
        
      
    
    {\displaystyle {\tfrac {n-1}{2}}}
  
 (i.e. it will correct up to 
  
    
      
        
          
            
              
                n
                −
                1
              
              2
            
          
        
      
    
    {\displaystyle {\tfrac {n-1}{2}}}
  
 errors in any code word).
</p><p>If the length of a binary repetition code is odd, then it's a <a href="/facts/Perfect_code/3P8HVgGF">perfect code</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> The binary repetition code of length <i>n</i> is equivalent to the (<i>n</i>, 1)-<a href="/facts/Hamming_code/zsI8cTRC">Hamming code</a>. A (<i>n</i>, 1) <a href="/facts/BCH_code/1KelJGxF">BCH code</a> is also a repetition code.
</p>
<h2 id="example">Example</h2>
<p>Consider a binary repetition code of length 3. The user wants to transmit the information bits 101. Then the encoding maps each bit either to the all ones or all zeros code word, so we get the 111 000 111, which will be transmitted.
</p><p>Let's say three errors corrupt the transmitted bits and the received sequence is 111 010 100. Decoding is usually done by a simple <a href="/facts/Majority_logic_decoding/wbjw65sc">majority decision</a> for each code word. That lead us to 100 as the decoded information bits, because in the first and second code word occurred less than two errors, so the majority of the bits are correct. But in the third code word two bits are corrupted, which results in an erroneous information bit, since two errors lie above the error correcting capacity.
</p>
<h2 id="applications">Applications</h2>
<p>Despite their poor performance as stand-alone codes, use in <a href="/facts/Turbo_code/F3nmelu0">Turbo code</a>-like iteratively decoded <a href="/facts/Concatenated_error_correction_codes/kMtLmN80">concatenated coding</a> schemes, such as <a href="/facts/Repeat-accumulate_code/5uJXar4K">repeat-accumulate</a> (RA) and accumulate-repeat-accumulate (ARA) codes, allows for surprisingly good error correction performance.
</p><p>Repetition codes are one of the few known codes whose <a href="/facts/Code_rate/xPrLLTwt">code rate</a> can be automatically adjusted to varying <a href="/facts/Channel_capacity/55wJYsS6">channel capacity</a>, by sending more or less parity information as required to overcome the channel noise, and it is the only such code known for non-<a href="/facts/Binary_erasure_channel/qJnFRvl9">erasure channels</a>. Practical adaptive codes for erasure channels have been invented only recently, and are known as <a href="/facts/Fountain_code/st95SSf8">fountain codes</a>.
</p><p>Some <a href="/facts/UART/xMntJcsI">UARTs</a>, such as the ones used in the <a href="/facts/FlexRay/rQtVC5J5">FlexRay</a> protocol, use a majority filter to ignore brief noise spikes. This spike-rejection filter can be seen as a kind of repetition decoder.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Block_code/QVuqpGga">Block code</a></li>
<li><a href="/facts/Turbo_code/F3nmelu0">Turbo code</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Bossert, Martin (1999). Channel Coding for Telecommunications. Wiley. ISBN 9780471982777. <a href="9780471982777" target="_blank">9780471982777</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Repetition code open-in-new

Repetition code