.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/abstract_algebra/codes/plot_01_reed_solomon_erasures.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_abstract_algebra_codes_plot_01_reed_solomon_erasures.py>`
        to download the full example code.

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

.. _sphx_glr_api_gallery_abstract_algebra_codes_plot_01_reed_solomon_erasures.py:


Reed-Solomon codes: recovering from erasures
==================================================

Encodes a short message as the values of a polynomial over GF(929),
erases symbols at random, and recovers the message from any k surviving
values.

.. GENERATED FROM PYTHON SOURCE LINES 11-18

.. code-block:: Python

    import contextlib

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.abstract_algebra import rs_decode_erasures, rs_encode








.. GENERATED FROM PYTHON SOURCE LINES 19-21

Encode a message
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 21-28

.. code-block:: Python


    p, n = 929, 12
    message = [ord(c) for c in "MATH"]  # k = 4 symbols
    codeword = rs_encode(message, n, p)
    print(f"message  {message}")
    print(f"codeword {codeword}")





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

 .. code-block:: none

    message  [77, 65, 84, 72]
    codeword [77, 298, 190, 185, 715, 354, 463, 545, 103, 498, 304, 882]




.. GENERATED FROM PYTHON SOURCE LINES 29-31

Erase n - k symbols and decode
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 31-39

.. code-block:: Python


    rng = np.random.default_rng(0)
    erased = set(rng.choice(n, size=n - len(message), replace=False).tolist())
    received = [None if i in erased else c for i, c in enumerate(codeword)]
    decoded = rs_decode_erasures(received, k=len(message), p=p)
    print(f"received {received}")
    print(f"decoded  {''.join(map(chr, decoded))}")





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

 .. code-block:: none

    received [None, 298, None, None, None, 354, None, 545, None, 498, None, None]
    decoded  MATH




.. GENERATED FROM PYTHON SOURCE LINES 40-42

Success rate against the number of erasures
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 42-60

.. code-block:: Python


    trials = 200
    rates = []
    for e in range(n + 1):
        ok = 0
        for _ in range(trials):
            lost = set(rng.choice(n, size=e, replace=False).tolist())
            with contextlib.suppress(ValueError):
                ok += rs_decode_erasures([None if i in lost else c for i, c in enumerate(codeword)], len(message), p) == message
        rates.append(ok / trials)

    fig, ax = plt.subplots()
    ax.step(range(n + 1), rates, where="mid")
    ax.axvline(n - len(message), color="tab:red", ls="--", label="n - k")
    ax.set_xlabel("erased symbols")
    ax.set_ylabel("fraction decoded correctly")
    ax.legend()
    ax.set_title("Reed-Solomon (n=12, k=4): any 8 erasures are recoverable")



.. image-sg:: /api/gallery/abstract_algebra/codes/images/sphx_glr_plot_01_reed_solomon_erasures_001.png
   :alt: Reed-Solomon (n=12, k=4): any 8 erasures are recoverable
   :srcset: /api/gallery/abstract_algebra/codes/images/sphx_glr_plot_01_reed_solomon_erasures_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none


    Text(0.5, 1.0, 'Reed-Solomon (n=12, k=4): any 8 erasures are recoverable')




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

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


.. _sphx_glr_download_api_gallery_abstract_algebra_codes_plot_01_reed_solomon_erasures.py:

.. only:: html

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

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

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

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

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

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

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


.. only:: html

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

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