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


Goertzel's algorithm (1958)
===========================

Gerald Goertzel (1958) evaluated a single term of a Fourier series with a
second-order recursion that needs one real multiplication per sample
(:func:`~engineeringkit.signal_processing.goertzel`). When only a handful
of frequencies matter, it is cheaper than a full FFT and needs no buffer
of samples. Its classic use is the touch-tone (DTMF) telephone keypad,
where each key sends two tones, one from a low group and one from a high
group, and the receiver has to measure only eight frequencies.

.. GENERATED FROM PYTHON SOURCE LINES 15-20

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from engineeringkit.signal_processing import dft, goertzel








.. GENERATED FROM PYTHON SOURCE LINES 21-26

One bin of the DFT
------------------

At a frequency :math:`kf_s/N` the recursion returns exactly DFT bin
:math:`k`.

.. GENERATED FROM PYTHON SOURCE LINES 26-34

.. code-block:: Python


    rng = np.random.default_rng(1958)
    fs, n = 8000.0, 205  # the classic DTMF block length
    x = rng.normal(size=n)
    for k in (3, 18, 40):
        assert np.isclose(goertzel(x, k * fs / n, fs), dft(x)[k])
    print("Goertzel agrees with the DFT at bins 3, 18 and 40")





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

 .. code-block:: none

    Goertzel agrees with the DFT at bins 3, 18 and 40




.. GENERATED FROM PYTHON SOURCE LINES 35-37

Decoding a phone number
-----------------------

.. GENERATED FROM PYTHON SOURCE LINES 37-54

.. code-block:: Python


    low, high = [697.0, 770.0, 852.0, 941.0], [1209.0, 1336.0, 1477.0]
    keys = ["123", "456", "789", "*0#"]
    number = "5550123"
    t = np.arange(n) / fs
    decoded = ""
    energies = []
    for key in number:
        row = next(i for i, r in enumerate(keys) if key in r)
        column = keys[row].index(key)
        tone = np.sin(2 * np.pi * low[row] * t) + np.sin(2 * np.pi * high[column] * t) + rng.normal(0, 0.5, n)
        power = abs(goertzel(tone, low + high, fs)) ** 2
        energies.append(power)
        decoded += keys[int(np.argmax(power[:4]))][int(np.argmax(power[4:]))]
    print(f"sent {number}, decoded {decoded}")
    assert decoded == number





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

 .. code-block:: none

    sent 5550123, decoded 5550123




.. GENERATED FROM PYTHON SOURCE LINES 55-62

Cost: eight Goertzel filters against one FFT
--------------------------------------------

Eight filters over 205 samples take about :math:`8 \times 205` real
multiplications. A 256-point radix-2 FFT takes
:math:`(N/2)\log_2 N = 1024` complex multiplications, about 4096 real ones,
to compute every bin when only eight are needed.

.. GENERATED FROM PYTHON SOURCE LINES 62-75

.. code-block:: Python


    goertzel_cost = 8 * n
    fft_cost = 4 * 256 // 2 * 8
    print(f"Goertzel: {goertzel_cost} real multiplications; FFT: {fft_cost}")
    assert goertzel_cost < fft_cost

    fig, ax = plt.subplots(figsize=(7, 3.5))
    ax.imshow(np.array(energies).T, aspect="auto", cmap="viridis")
    ax.set(xticks=range(len(number)), xticklabels=list(number), yticks=range(7), yticklabels=[f"{f:.0f} Hz" for f in low + high])
    ax.set(xlabel="key pressed", title="Goertzel power at the eight DTMF frequencies")
    fig.tight_layout()

    plt.show()



.. image-sg:: /api/gallery/signal_processing/spectral/images/sphx_glr_plot_05_goertzel_001.png
   :alt: Goertzel power at the eight DTMF frequencies
   :srcset: /api/gallery/signal_processing/spectral/images/sphx_glr_plot_05_goertzel_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    Goertzel: 1640 real multiplications; FFT: 4096





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

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


.. _sphx_glr_download_api_gallery_signal_processing_spectral_plot_05_goertzel.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/signal_processing/spectral/plot_05_goertzel.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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