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


Reed-Solomon codes: recovering lost and corrupted symbols (1960)
================================================================

Reed and Solomon treated ``k`` symbols of data as a polynomial of degree
below ``k`` over a finite field, and sent its values at ``n`` points.
Two such polynomials agree on at most ``k - 1`` points, so any ``k`` of the
``n`` values determine all the others. The code survives the loss of up to
``n - k`` symbols, and up to ``(n - k) / 2`` symbols that arrive wrong:

.. math::

   2\,(\text{errors}) + (\text{erasures}) \le n - k.

The same code protects CDs and QR codes, and, on blockchains, lets a block
be rebuilt from any half of its extended shares.

.. GENERATED FROM PYTHON SOURCE LINES 20-28

.. code-block:: Python

    from contextlib import suppress
    from random import Random

    import matplotlib.pyplot as plt

    import blockchainkit as bk
    from blockchainkit.channels.visualizers import plot_shares








.. GENERATED FROM PYTHON SOURCE LINES 29-33

Five letters, eleven shares
---------------------------
The data are the polynomial's values at 0, ..., 4; the extension adds its
values at 5, ..., 10.

.. GENERATED FROM PYTHON SOURCE LINES 33-45

.. code-block:: Python


    message = b"HELLO"
    k, n = len(message), 11
    codeword = bk.channels.rs_encode(list(message), n)
    assert codeword[:k] == tuple(message)

    rng = Random(1)
    kept = sorted(rng.sample(range(n), k))
    print("kept shares at", kept)
    recovered = bk.channels.rs_recover({i: codeword[i] for i in kept}, k, n)
    assert bytes(recovered[:k]) == message





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

 .. code-block:: none

    kept shares at [0, 1, 2, 4, 9]




.. GENERATED FROM PYTHON SOURCE LINES 46-50

Correcting errors with Berlekamp and Welch
------------------------------------------
With no erasures, n - k = 6 spare symbols correct 3 wrong ones. For each
number of errors, corrupt random positions and try to decode.

.. GENERATED FROM PYTHON SOURCE LINES 50-77

.. code-block:: Python


    trials, rates = 40, []
    error_counts = range(0, 7)
    for errors in error_counts:
        decoded = 0
        for _ in range(trials):
            received = list(codeword)
            for i in rng.sample(range(n), errors):
                received[i] = (received[i] + rng.randrange(1, 65_537)) % 65_537
            with suppress(ValueError):  # Too many errors to correct.
                decoded += bk.channels.rs_decode(received, k) == tuple(message)
        rates.append(decoded / trials)
    print("decoding success by number of errors:", rates)
    assert rates[:4] == [1.0] * 4 and max(rates[4:]) < 1

    fig, (left, right) = plt.subplots(1, 2, figsize=(11, 4))
    plot_shares(bk.channels.commit_shares(k, codeword), withheld=set(range(n)) - set(kept), ax=left)
    left.set_title("Any 5 of the 11 shares rebuild the rest")
    right.bar(error_counts, rates, color=["#16a34a" if e <= 3 else "#dc2626" for e in error_counts])
    right.axvline(3.5, color="black", linestyle="--", label="(n - k) / 2")
    right.set(xlabel="symbols corrupted", ylabel="fraction decoded correctly")
    right.set_title("Errors are corrected up to half the redundancy")
    right.legend()
    fig.tight_layout()

    plt.show()




.. image-sg:: /api/gallery/channels/coding/images/sphx_glr_plot_01_reed_solomon_001.png
   :alt: Any 5 of the 11 shares rebuild the rest, Errors are corrected up to half the redundancy
   :srcset: /api/gallery/channels/coding/images/sphx_glr_plot_01_reed_solomon_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    decoding success by number of errors: [1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0]




.. GENERATED FROM PYTHON SOURCE LINES 78-85

Exercise
--------
Combine erasures and errors: with ``n = 11`` and ``k = 5``, erase two
symbols (pass ``None``) and corrupt some others. How many corruptions can
:func:`~blockchainkit.channels.systems.reed_solomon.rs_decode` still
correct, and does it match the bound above?
A worked solution is in :doc:`/exercises/channels`.


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

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


.. _sphx_glr_download_api_gallery_channels_coding_plot_01_reed_solomon.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/channels/coding/plot_01_reed_solomon.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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