Skip to main content
Engineering LibreTexts

6.28: Error-Correcting Codes - Channel Decoding

  • Page ID
    1880
  • \( \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
    • Channel decoding must be coordinated with coding for accurate results.

    Because the idea of channel coding has merit (so long as the code is efficient), let's develop a systematic procedure for performing channel decoding. One way of checking for errors is to try recreating the error correction bits from the data portion of the received block \[\hat{c} \nonumber \] Using matrix notation, we make this calculation by multiplying the received block \[\hat{c} \nonumber \] by the matrix H known as the parity check matrix. It is formed from the generator matrix G by taking the bottom, error-correction portion of G and attaching to it an identity matrix. For our (7,4) code,

    \[H=\begin{bmatrix} 1 & 1 & 1 & 0 &\; \; \; \; \; 1 & 0 & 0\\ 0 & 1 & 1 & 1 & \; \; \; \; \; 0 & 1 & 0\\ 1 & 1 & 0 & 1 & \; \; \; \; \; 0& 0 & 1\\ \end{bmatrix} \nonumber \]

    \[\; \; \;Lower\: portion\: of\: G\; \;Identity \nonumber \]

    The parity check matrix thus has size (N-K)×N, and the result of multiplying this matrix with a received word is a length- (N-K) binary vector. If no digital channel errors occur—we receive a codeword so that

    \[\hat{c}=c \nonumber \]

    then

    \[H\hat{c}=0 \nonumber \]

    For example, the first column of

    \[G,(1,0,0,0,1,0,1)^{T} \nonumber \]

    is a codeword. Simple calculations show that multiplying this vector by H results in a length- (N-K) zero-valued vector.

    Exercise \(\PageIndex{1}\)

    Show that HC = 0 for all the columns of G. In other words, show that HG = 0 an (N-K)×N matrix of zeroes. Does this property guarantee that all codewords also satisfy HC = 0?

    Solution

    When we multiply the parity-check matrix times any codeword equal to a column of G, the result consists of the sum of an entry from the lower portion of G and itself that, by the laws of binary arithmetic, is always zero.

    Because the code is linear—sum of any two codewords is a codeword—we can generate all codewords as sums of columns of G. Since multiplying by H is also linear,

    HC = 0.

    When the received bits \[\hat{c} \nonumber \] do not form a codeword, \[H\hat{c} \nonumber \] does not equal zero, indicating the presence of one or more errors induced by the digital channel. Because the presence of an error can be mathematically written as

    \[\hat{c}=c\oplus e \nonumber \]

    with e a vector of binary values having a 1 in those positions where a bit error occurred.

    Exercise \(\PageIndex{1}\)

    Show that adding the error vector (1,0,...,0)T to a codeword flips the codeword's leading bit and leaves the rest unaffected.

    Solution

    In binary arithmetic see this table, adding 0 to a binary value results in that binary value while adding 1 results in the opposite binary value.

    Consequently,

    \[H\hat{c}=Hc\oplus e=He \nonumber \]

    Because the result of the product is a length- (N-K) vector of binary values, we can have 2N-K - 1 non-zero values that correspond to non-zero error patterns e. To perform our channel decoding,

    • compute (conceptually at least) \[H\hat{c} \nonumber \]
    • if this result is zero, no detectable or correctable error occurred
    • if non-zero, consult a table of length- (N-K) binary vectors to associate them with the minimal error pattern that could have resulted in the non-zero result
    • then add the error vector thus obtained to the received vector \[\hat{c} \nonumber \] to correct the error because \[c\oplus e\oplus e=c \nonumber \]
    • select the data bits from the corrected word to produce the received bit sequence \[\hat{b}(n) \nonumber \]

    The phrase minimal in the third item raises the point that a double (or triple or quadruple …) error occurring during the transmission/reception of one codeword can create the same received word as a single-bit error or no error in another codeword.

    For example, (1,0,0,0,1,0,1)T and (0,1,0,0,1,1,1)T are both codewords in the example (7,4) code. The second results when the first one experiences three bit errors (first, second, and sixth bits). Such an error pattern cannot be detected by our coding strategy, but such multiple error patterns are very unlikely to occur. Our receiver uses the principle of maximum probability: An error-free transmission is much more likely than one with three errors if the bit-error probability pe is small enough.

    Exercise \(\PageIndex{1}\)

    How small must pe be so that a single-bit error is more likely to occur than a triple-bit error?

    Solution

    The probability of a single-bit error in a length-N block is

    \[Np_{e}(1-p_{e})^{N-1} \nonumber \]

    and a triple-bit error has probability

    \[\binom{N}{3}p_{e}^{3}(1-p_{e})^{N-3} \nonumber \]

    For the first to be greater than the second, we must have

    \[p_{e}< \frac{1}{\sqrt{\frac{(N-1)(N-2)}{6}}+1} \nonumber \]

    \[For \; N=7,\; p_{e}< 0.31 \nonumber \]


    This page titled 6.28: Error-Correcting Codes - Channel Decoding 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.