Skip to main content
Engineering LibreTexts

6.25: Repetition Codes

  • Page ID
    1877
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Learning Objectives
    • Explains the repetition code for error correction.

    Perhaps the simplest error correcting code is the repetition code.

    sys32.png
    Figure 6.25.1 The upper portion depicts the result of directly modulating the bit stream b(n) into a transmitted signal x(t) using a baseband BPSK signal set. R' is the datarate produced by the source coder. If that bit stream passes through a (3,1) channel coder to yield the bit stream c(l), the resulting transmitted signal requires a bit interval T three times smaller than the uncoded version. This reduction in the bit interval means that the transmitted energy/bit decreases by a factor of three, which results in an increased error probability in the receiver.

    Here, the transmitter sends the data bit several times, an odd number of times in fact. Because the error probability pe is always less than 1/2, we know that more of the bits should be correct rather than in error. Simple majority voting of the received bits (hence the reason for the odd number) determines the transmitted bit more accurately than sending it alone. For example, let's consider the three-fold repetition code: for every bit b(n) emerging from the source coder, the channel coder produces three. Thus, the bit stream emerging from the channel coder c(l) has a data rate three times higher than that of the original bit stream b(n). The coding table illustrates when errors can be corrected and when they can't by the majority-vote decoder.

    probability.png

    Thus, if one bit of the three bits is received in error, the receiver can correct the error; if more than one error occurs, the channel decoder announces the bit is 1 instead of transmitted value of 0. Using this repetition code, the probability of bˆ

    \[\hat{b}(n)\neq 0 \nonumber \]

    equals

    \[3p_{e}^{2}\times (1-p_{e})+p_{e}^{3} \nonumber \]

    This probability of a decoding error is always less than pe , the uncoded value, so long as

    \[p_{e}< \frac{1}{2} \nonumber \]

    Exercise \(\PageIndex{1}\)

    Demonstrate mathematically that this claim is indeed true.

    \[3p_{e}^{2}\times (1-p_{e})+p_{e}^{3}\leq p_{e} \nonumber \]

    Solution

    This question is equivalent to

    \[3p_{e}\times (1-p_{e})+p_{e}^{2}\leq 1\; or\; 2p_{e}^{2}-3p_{e}+1\geq 0 \nonumber \]

    Because this is an upward-going parabola, we need only check where its roots are. Using the quadratic formula, we find that they are located at 1/2 and 1. Consequently in the range

    \[0\leq p_{e}\leq \frac{1}{2} \nonumber \]

    the error rate produced by coding is smaller.


    This page titled 6.25: Repetition Codes is shared under a CC BY 1.0 license and was authored, remixed, and/or curated by Don H. Johnson via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.

    • Was this article helpful?