.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/communications/coding/plot_01_hamming_code.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_01_hamming_code.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_01_hamming_code.py:


Hamming's single-error-correcting code
======================================

Frustrated by weekend computer runs aborted by a single bad relay, Richard
Hamming (1950) designed codes that *correct* errors rather than merely
detect them. In the (7,4) code three parity bits sit at positions 1, 2 and 4.
When one bit flips, the failing parity checks, read as a binary number, give
its position (:func:`~engineeringkit.communications.hamming74_encode`,
:func:`~engineeringkit.communications.hamming74_decode`). Any two codewords
differ in at least three places (:func:`~engineeringkit.communications.hamming_distance`),
which is what makes single-error correction possible.

.. GENERATED FROM PYTHON SOURCE LINES 16-21

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from engineeringkit.communications import hamming74_decode, hamming74_encode, hamming_distance








.. GENERATED FROM PYTHON SOURCE LINES 22-24

The syndrome points at the error
--------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 24-38

.. code-block:: Python


    word = hamming74_encode([1, 0, 1, 1])
    print("codeword:", word.tolist())
    for position in range(7):
        corrupted = word.copy()
        corrupted[position] ^= 1
        result = hamming74_decode(corrupted)
        print(f"flip bit {position + 1}: syndrome {result.syndromes[0]} -> data {result.data.tolist()}")
        assert result.syndromes[0] == position + 1 and result.data.tolist() == [1, 0, 1, 1]

    codebook = [hamming74_encode([(k >> i) & 1 for i in range(4)]) for k in range(16)]
    distances = np.array([[hamming_distance(a, b) for b in codebook] for a in codebook])
    print("minimum distance:", distances[~np.eye(16, dtype=bool)].min())





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

 .. code-block:: none

    codeword: [0, 1, 1, 0, 0, 1, 1]
    flip bit 1: syndrome 1 -> data [1, 0, 1, 1]
    flip bit 2: syndrome 2 -> data [1, 0, 1, 1]
    flip bit 3: syndrome 3 -> data [1, 0, 1, 1]
    flip bit 4: syndrome 4 -> data [1, 0, 1, 1]
    flip bit 5: syndrome 5 -> data [1, 0, 1, 1]
    flip bit 6: syndrome 6 -> data [1, 0, 1, 1]
    flip bit 7: syndrome 7 -> data [1, 0, 1, 1]
    minimum distance: 3




.. GENERATED FROM PYTHON SOURCE LINES 39-44

Coded versus uncoded error rate on a bit-flipping channel
---------------------------------------------------------

A block fails only if two or more of its seven bits flip:
:math:`1 - (1-p)^7 - 7p(1-p)^6`, compared with :math:`1-(1-p)^4` uncoded.

.. GENERATED FROM PYTHON SOURCE LINES 44-66

.. code-block:: Python


    rng = np.random.default_rng(1950)
    p = np.logspace(-3, -1, 7)
    simulated = []
    for flip in p:
        data = rng.integers(0, 2, 4 * 50_000)
        received = hamming74_encode(data) ^ (rng.random(7 * 50_000) < flip)
        blocks_wrong = np.any((hamming74_decode(received).data != data).reshape(-1, 4), axis=1)
        simulated.append(blocks_wrong.mean())
    coded = 1 - (1 - p) ** 7 - 7 * p * (1 - p) ** 6
    assert np.allclose(simulated[3:], coded[3:], rtol=0.15)
    fig, axes = plt.subplots(1, 2, figsize=(10, 3.8))
    axes[0].imshow(distances, cmap="viridis")
    axes[0].set(title="Distances between the 16 codewords", xlabel="codeword", ylabel="codeword")
    axes[1].loglog(p, 1 - (1 - p) ** 4, label="uncoded 4-bit block")
    axes[1].loglog(p, coded, label="Hamming(7,4), theory")
    axes[1].loglog(p, np.maximum(simulated, 1e-6), "o", label="Hamming(7,4), simulation")
    axes[1].set(xlabel="bit-flip probability", ylabel="block error rate")
    axes[1].legend()
    fig.tight_layout()

    plt.show()



.. image-sg:: /api/gallery/communications/coding/images/sphx_glr_plot_01_hamming_code_001.png
   :alt: Distances between the 16 codewords
   :srcset: /api/gallery/communications/coding/images/sphx_glr_plot_01_hamming_code_001.png
   :class: sphx-glr-single-img






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

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


.. _sphx_glr_download_api_gallery_communications_coding_plot_01_hamming_code.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_01_hamming_code.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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