.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/wallets/codes/plot_01_bch_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_wallets_codes_plot_01_bch_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_wallets_codes_plot_01_bch_codes.py:


BCH error-correcting codes (1959-1960)
======================================

Alexis Hocquenghem in 1959, and Raj Chandra Bose and Dijen Ray-Chaudhuri in
1960, found how to build binary codes that correct any chosen number t of
flipped bits. A word of n = 2**m - 1 bits is read as a polynomial, and the
codewords are the multiples of a generator g(x) that vanishes at
:math:`\alpha, \alpha^2, \dots, \alpha^{2t}` in GF(2**m). Any two codewords
then differ in at least

.. math::

   d \ge 2t + 1

bits, so a received word with at most t errors is nearer to its codeword
than to any other. The same construction over GF(32) gives Bech32's
checksum. Here a (15, 7) code corrects two errors, and three errors defeat
it.

.. GENERATED FROM PYTHON SOURCE LINES 23-29

.. code-block:: Python

    import random

    import matplotlib.pyplot as plt

    import blockchainkit as bk








.. GENERATED FROM PYTHON SOURCE LINES 30-32

Correcting two errors
---------------------

.. GENERATED FROM PYTHON SOURCE LINES 32-48

.. code-block:: Python


    code = bk.wallets.BCHCode(4, 2)
    print(f"n = {code.n}, k = {code.k}, designed distance {code.designed_distance}")
    print("generator g(x) =", bin(code.generator))
    message = [1, 0, 1, 1, 0, 0, 1]
    word = list(code.encode(message))
    received = list(word)
    for i in (2, 11):
        received[i] ^= 1
    print("sent    ", "".join(map(str, word)))
    print("received", "".join(map(str, received)))
    print("syndromes", code.syndromes(received))
    decoded = code.decode(received)
    print("corrected positions", decoded.errors)
    assert decoded.corrected and list(decoded.message) == message





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

 .. code-block:: none

    n = 15, k = 7, designed distance 5
    generator g(x) = 0b111010001
    sent     101100100011110
    received 100100100010110
    syndromes (7, 6, 6, 7)
    corrected positions (2, 11)




.. GENERATED FROM PYTHON SOURCE LINES 49-53

What each number of errors does
-------------------------------
For every count of flipped bits, the share of words decoded to the right
message, wrongly corrected, or refused.

.. GENERATED FROM PYTHON SOURCE LINES 53-88

.. code-block:: Python


    rng = random.Random(1960)
    outcomes = {"right": [], "wrong": [], "refused": []}
    counts = range(6)
    for errors in counts:
        tally = dict.fromkeys(outcomes, 0)
        for _ in range(300):
            sent = [rng.randrange(2) for _ in range(code.k)]
            noisy = list(code.encode(sent))
            for i in rng.sample(range(code.n), errors):
                noisy[i] ^= 1
            result = code.decode(noisy)
            if not result.corrected:
                tally["refused"] += 1
            elif list(result.message) == sent:
                tally["right"] += 1
            else:
                tally["wrong"] += 1
        for key, value in tally.items():
            outcomes[key].append(value / 300)
    assert outcomes["right"][:3] == [1.0, 1.0, 1.0]
    assert outcomes["right"][3] < 0.1

    fig, ax = plt.subplots(figsize=(6, 4))
    bottom = [0.0] * len(counts)
    for key, color in (("right", "#16a34a"), ("refused", "#64748b"), ("wrong", "#dc2626")):
        ax.bar(counts, outcomes[key], bottom=bottom, color=color, label=key)
        bottom = [b + v for b, v in zip(bottom, outcomes[key], strict=True)]
    ax.axvline(code.t + 0.5, color="black", linestyle="--")
    ax.set(xlabel="bits flipped", ylabel="share of words", xticks=list(counts))
    ax.set_title("BCH(15, 7): up to t = 2 errors are always corrected")
    ax.legend()
    fig.tight_layout()
    plt.show()




.. image-sg:: /api/gallery/wallets/codes/images/sphx_glr_plot_01_bch_codes_001.png
   :alt: BCH(15, 7): up to t = 2 errors are always corrected
   :srcset: /api/gallery/wallets/codes/images/sphx_glr_plot_01_bch_codes_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 89-94

Exercise
--------
How many message bits does a code of length 31 keep if it must correct
three errors?
A worked solution is in :doc:`/exercises/wallets`.


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

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


.. _sphx_glr_download_api_gallery_wallets_codes_plot_01_bch_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/wallets/codes/plot_01_bch_codes.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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