.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/communications/coding/plot_02_elias_convolutional_codes.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_communications_coding_plot_02_elias_convolutional_codes.py>`
        to download the full example code or to run this example in your browser via JupyterLite.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_communications_coding_plot_02_elias_convolutional_codes.py:


Elias's convolutional codes (1955)
==================================

Peter Elias's "Coding for noisy channels" showed that a code need not cut
the data into blocks. A shift register of length :math:`K` slides along the
bit stream, and each input bit produces :math:`n` output bits, sums modulo
two of the register taps (:func:`~engineeringkit.communications.convolutional_encode`).
Elias proved that such codes are at least as good as block codes. Their
strength is the *free distance*, the least weight of any path that leaves
the all-zero state and returns to it
(:func:`~engineeringkit.communications.convolutional_free_distance`).
For the standard rate-1/2 codes it grows with the constraint length.

.. GENERATED FROM PYTHON SOURCE LINES 17-22

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from engineeringkit.communications import convolutional_encode, convolutional_free_distance








.. GENERATED FROM PYTHON SOURCE LINES 23-27

The (7, 5) encoder
------------------

Generators :math:`1 + D + D^2` and :math:`1 + D^2`, octal 7 and 5.

.. GENERATED FROM PYTHON SOURCE LINES 27-41

.. code-block:: Python


    data = [1, 0, 1, 1, 0, 0, 1]
    code = convolutional_encode(data)
    print("data:", data)
    print("code:", " ".join("".join(map(str, pair)) for pair in code.reshape(-1, 2)))
    impulse = convolutional_encode([1])
    print("impulse response:", impulse.tolist(), "weight", impulse.sum())
    assert impulse.sum() == convolutional_free_distance((0o7, 0o5)) == 5

    # The code is linear: the encoding of a sum is the sum of the encodings.
    rng = np.random.default_rng(1955)
    a, b = rng.integers(0, 2, 50), rng.integers(0, 2, 50)
    assert np.array_equal(convolutional_encode(a ^ b), convolutional_encode(a) ^ convolutional_encode(b))





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    data: [1, 0, 1, 1, 0, 0, 1]
    code: 11 10 00 01 01 11 11 10 11
    impulse response: [1, 1, 1, 0, 1, 1] weight 5




.. GENERATED FROM PYTHON SOURCE LINES 42-46

Free distance grows with the constraint length
----------------------------------------------

The best known rate-1/2 generators (Proakis, Table 8.3-1).

.. GENERATED FROM PYTHON SOURCE LINES 46-67

.. code-block:: Python


    best = {3: (0o5, 0o7), 4: (0o15, 0o17), 5: (0o23, 0o35), 6: (0o53, 0o75), 7: (0o133, 0o171)}
    known = {3: 5, 4: 6, 5: 7, 6: 8, 7: 10}
    distances = {K: convolutional_free_distance(g) for K, g in best.items()}
    for K, d in distances.items():
        print(f"K = {K}: generators {tuple(oct(g) for g in best[K])}, d_free = {d}")
    assert distances == known

    # Distances between codewords of 4-bit messages are never below d_free.
    words = [convolutional_encode([(k >> i) & 1 for i in range(4)]) for k in range(16)]
    pairwise = np.array([[np.count_nonzero(u != v) for v in words] for u in words])
    assert pairwise[~np.eye(16, dtype=bool)].min() == 5

    fig, axes = plt.subplots(1, 2, figsize=(11, 3.8))
    axes[0].stem(np.arange(impulse.size), impulse)
    axes[0].set(xlabel="code bit", title="Impulse response of the (7, 5) code: weight 5")
    axes[1].plot(list(distances), list(distances.values()), "o-")
    axes[1].set(xlabel="constraint length K", ylabel="free distance", title="Best rate-1/2 codes")
    fig.tight_layout()

    plt.show()



.. image-sg:: /api/gallery/communications/coding/images/sphx_glr_plot_02_elias_convolutional_codes_001.png
   :alt: Impulse response of the (7, 5) code: weight 5, Best rate-1/2 codes
   :srcset: /api/gallery/communications/coding/images/sphx_glr_plot_02_elias_convolutional_codes_001.png
   :class: sphx-glr-single-img


.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    K = 3: generators ('0o5', '0o7'), d_free = 5
    K = 4: generators ('0o15', '0o17'), d_free = 6
    K = 5: generators ('0o23', '0o35'), d_free = 7
    K = 6: generators ('0o53', '0o75'), d_free = 8
    K = 7: generators ('0o133', '0o171'), d_free = 10





.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.161 seconds)


.. _sphx_glr_download_api_gallery_communications_coding_plot_02_elias_convolutional_codes.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: lite-badge

      .. image:: images/jupyterlite_badge_logo.svg
        :target: ../../../../lite/lab/index.html?path=api/gallery/communications/coding/plot_02_elias_convolutional_codes.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_02_elias_convolutional_codes.ipynb <plot_02_elias_convolutional_codes.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_02_elias_convolutional_codes.py <plot_02_elias_convolutional_codes.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_02_elias_convolutional_codes.zip <plot_02_elias_convolutional_codes.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_