.. _sphx_glr_api_gallery_information_theory_source_coding:

Source coding
-------------

Lossless compression: from the typical set to Huffman, arithmetic, and Lempel-Ziv codes.


.. 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="For long i.i.d. sequences, -\tfrac1n\log_2 p(x^n) concentrates at the entropy H (the asymptotic equipartition property). Almost all the probability then sits on about 2^{nH} &quot;typical&quot; sequences out of 2^n, so nH bits suffice to describe the source, and no lossless code can do better on average.">

.. only:: html

  .. image:: /api/gallery/information_theory/source_coding/images/thumb/sphx_glr_plot_01_source_coding_theorem_typical_set_thumb.png
    :alt:

  :doc:`/api/gallery/information_theory/source_coding/plot_01_source_coding_theorem_typical_set`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Shannon's source coding theorem: the typical set (1948)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Shannon gave each symbol \lceil -\log_2 p\rceil bits, read off the binary expansion of the cumulative probability; Fano split the sorted symbols into two halves of nearly equal probability, recursively. Both land within one bit of the entropy -- the first practical codes built on Shannon&#x27;s theory -- but neither is always optimal.">

.. only:: html

  .. image:: /api/gallery/information_theory/source_coding/images/thumb/sphx_glr_plot_02_shannon_fano_coding_thumb.png
    :alt:

  :doc:`/api/gallery/information_theory/source_coding/plot_02_shannon_fano_coding`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Shannon-Fano coding (1948-1949)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="A binary prefix code with codeword lengths \ell_i exists if and only if \sum_i 2^{-\ell_i} \le 1 (Kraft 1949); McMillan (1956) showed every uniquely decodable code obeys the same bound. Each codeword of length \ell claims a 2^{-\ell} share of the unit interval, and prefix-freeness means the shares cannot overlap.">

.. only:: html

  .. image:: /api/gallery/information_theory/source_coding/images/thumb/sphx_glr_plot_03_kraft_mcmillan_inequality_thumb.png
    :alt:

  :doc:`/api/gallery/information_theory/source_coding/plot_03_kraft_mcmillan_inequality`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">The Kraft-McMillan inequality (1949, 1956)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Huffman, then a student in Fano&#x27;s class, found the optimal prefix code by building the tree bottom-up: repeatedly merge the two least likely symbols. The resulting code has the smallest possible average length, between H and H+1 bits, and is never worse than Shannon-Fano.">

.. only:: html

  .. image:: /api/gallery/information_theory/source_coding/images/thumb/sphx_glr_plot_04_huffman_coding_thumb.png
    :alt:

  :doc:`/api/gallery/information_theory/source_coding/plot_04_huffman_coding`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Huffman coding (1952)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="To send a positive integer of unknown size, Elias&#x27; gamma code writes \lfloor\log_2 n\rfloor zeros, then n in binary: the zeros announce the length. It is a prefix code for all integers at once, at most twice the optimal length, and universal: on any decreasing distribution it codes within a constant factor of the entropy.">

.. only:: html

  .. image:: /api/gallery/information_theory/source_coding/images/thumb/sphx_glr_plot_05_elias_gamma_code_thumb.png
    :alt:

  :doc:`/api/gallery/information_theory/source_coding/plot_05_elias_gamma_code`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Elias' universal code for the integers (1975)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Rissanen and Pasco coded a whole message as a single number: each symbol narrows an interval in proportion to its probability, and the codeword is the shortest binary fraction inside the final interval. The length is within two bits of -\log_2 p(\text{message}), so unlike Huffman coding there is no rounding up to whole bits per symbol.">

.. only:: html

  .. image:: /api/gallery/information_theory/source_coding/images/thumb/sphx_glr_plot_06_arithmetic_coding_thumb.png
    :alt:

  :doc:`/api/gallery/information_theory/source_coding/plot_06_arithmetic_coding`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Arithmetic coding (1976)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Ziv and Lempel&#x27;s LZ78 parses a sequence into phrases, each the longest earlier phrase plus one new symbol, and sends (phrase index, symbol) pairs. It knows nothing about the source, yet for any stationary ergodic source its rate approaches the entropy rate: a universal code, the ancestor of LZW, GIF and zip.">

.. only:: html

  .. image:: /api/gallery/information_theory/source_coding/images/thumb/sphx_glr_plot_07_lempel_ziv_compression_thumb.png
    :alt:

  :doc:`/api/gallery/information_theory/source_coding/plot_07_lempel_ziv_compression`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Lempel-Ziv compression (1977-1978)</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/information_theory/source_coding/plot_01_source_coding_theorem_typical_set
   /api/gallery/information_theory/source_coding/plot_02_shannon_fano_coding
   /api/gallery/information_theory/source_coding/plot_03_kraft_mcmillan_inequality
   /api/gallery/information_theory/source_coding/plot_04_huffman_coding
   /api/gallery/information_theory/source_coding/plot_05_elias_gamma_code
   /api/gallery/information_theory/source_coding/plot_06_arithmetic_coding
   /api/gallery/information_theory/source_coding/plot_07_lempel_ziv_compression