.. _sphx_glr_api_gallery_information_theory_channel_codes:

Channel codes
-------------

Error-correcting codes and their decoders.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Tired of weekend jobs on the Bell Labs relay computers stopping at every error, Hamming designed codes that correct them. The (7,4) code adds three parity bits so that the syndrome -- which checks fail -- spells out the position of a single flipped bit in binary. Over a binary symmetric channel it trades rate 4/7 for a much lower bit error rate when errors are rare.">

.. only:: html

  .. image:: /api/gallery/information_theory/channel_codes/images/thumb/sphx_glr_plot_01_hamming_codes_thumb.png
    :alt:

  :doc:`/api/gallery/information_theory/channel_codes/plot_01_hamming_codes`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Hamming codes (1950)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Elias proposed encoding a bit stream continuously instead of in blocks: each output pair is the parity of a sliding window of input bits. The rate-1/2 code with generators (7, 5)_8 and constraint length 3 spreads every input bit over six output bits, and its free distance -- the lightest nonzero output -- is 5.">

.. only:: html

  .. image:: /api/gallery/information_theory/channel_codes/images/thumb/sphx_glr_plot_02_convolutional_codes_thumb.png
    :alt:

  :doc:`/api/gallery/information_theory/channel_codes/plot_02_convolutional_codes`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Convolutional codes (1955)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Viterbi decoded convolutional codes by dynamic programming on the trellis of encoder states: at every step each state keeps only its best incoming path, so maximum-likelihood decoding costs time linear in the message length instead of exponential. It went on to decode deep-space probes, mobile phones, and hidden Markov models.">

.. only:: html

  .. image:: /api/gallery/information_theory/channel_codes/images/thumb/sphx_glr_plot_03_viterbi_decoding_thumb.png
    :alt:

  :doc:`/api/gallery/information_theory/channel_codes/plot_03_viterbi_decoding`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">The Viterbi algorithm (1967)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Gallager&#x27;s thesis proposed codes defined by a sparse random parity-check matrix, decoded iteratively: flip the bits that sit in the most failed checks, and repeat. Too costly for the computers of the time, LDPC codes were forgotten until MacKay and Neal rediscovered them in 1996; they now operate close to capacity in Wi-Fi, 5G, and satellite television.">

.. only:: html

  .. image:: /api/gallery/information_theory/channel_codes/images/thumb/sphx_glr_plot_04_gallager_ldpc_bit_flipping_thumb.png
    :alt:

  :doc:`/api/gallery/information_theory/channel_codes/plot_04_gallager_ldpc_bit_flipping`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Gallager's low-density parity-check codes (1962-1963)</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/information_theory/channel_codes/plot_01_hamming_codes
   /api/gallery/information_theory/channel_codes/plot_02_convolutional_codes
   /api/gallery/information_theory/channel_codes/plot_03_viterbi_decoding
   /api/gallery/information_theory/channel_codes/plot_04_gallager_ldpc_bit_flipping