<commit_before>Fourier Transforms (:mod:`scipy.fftpack`)
=========================================

.. sectionauthor:: Scipy Developers

.. currentmodule:: scipy.fftpack

.. contents::


Fourier analysis is a method for expressing a function as a sum of periodic
components, and for recovering the signal from those components.  When both
the function and its Fourier transform are replaced with discretized
counterparts, it is called the discrete Fourier transform (DFT).  The DFT has
become a mainstay of numerical computing in part because of a very fast
algorithm for computing it, called the Fast Fourier Transform (FFT), which was
known to Gauss (1805) and was brought to light in its current form by Cooley
and Tukey [CT65]_.  Press et al. [NR07]_ provide an accessible introduction to
Fourier analysis and its applications.

.. note::

   PyFFTW_ provides a way to replace a number of functions in `scipy.fftpack`
   with its own functions, which are usually significantly faster, via
   pyfftw.interfaces_.  Because PyFFTW_ relies on the GPL-licensed FFTW_ it
   cannot be included in Scipy.  Users for whom the speed of FFT routines is
   critical should consider installing PyFFTW_.


Fast Fourier transforms
-----------------------

One dimensional discrete Fourier transforms
___________________________________________

The FFT `y[k]` of length :math:`N` of the length-:math:`N` sequence `x[n]` is
defined as

.. math::

    y[k] = \sum_{n=0}^{N-1} e^{-2 \pi j \frac{k n}{N} } x[n] \, ,

and the inverse transform is defined as follows

.. math::

    x[n] = \frac{1}{N} \sum_{k=0}^{N-1} e^{2 \pi j \frac{k n}{N} } y[k] \, .

These transforms can be calculated by means of :func:`fft` and :func:`ifft`,
respectively as shown in the following example.

>>> from scipy.fftpack import fft, ifft
>>> x = np.array([1.0, 2.0, 1.0, -1.0, 1.5])
>>> y = fft(x)
>>> y
array([ 4.5       +0.j        ,  2.08155948-1.65109876j,
       -1.83155948+1.60822041j, -1.83155948-1.60822041j,
        2.08155948+1.65109876j])
>>> yinv = ifft(y)
>>> yinv
array([ 1.0+0.j,  2.0+0.j,  1.0+0.j, -1.0+0.j,  1.5+0.j])


From the definition of the FFT it can be seen that

.. math::

    y[0] = \sum_{n=0}^{N-1} x[n] \, .

In the example

>>> np.sum(x)
4.5

which corresponds to :math:`y[0]`. For N even, the elements
:math:`y[1]...y[N/2-1]` contain the positive-frequency terms, and the elements
:math:`y[N/2]...y[N-1]` contain the negative-frequency terms, in order of
decreasingly negative frequency. For N odd, the elements
:math:`y[1]...y[(N-1)/2]` contain the positive- frequency terms, and the
elements :math:`y[(N+1)/2]...y[N-1]` contain the negative- frequency terms, in
order of decreasingly negative frequency.

In case the sequence x is real-valued, the values of :math:`y[n]` for positive
frequencies is the conjugate of the values :math:`y[n]` for negative
frequencies (because the spectrum is symmetric). Typically, only the FFT
corresponding to positive frequencies is plotted.

The example plots the FFT of the sum of two sines.

.. plot::

    >>> from scipy.fftpack import fft
    >>> # Number of sample points
    >>> N = 600
    >>> # sample spacing
    >>> T = 1.0 / 800.0
    >>> x = np.linspace(0.0, N*T, N)
    >>> y = np.sin(50.0 * 2.0*np.pi*x) + 0.5*np.sin(80.0 * 2.0*np.pi*x)
    >>> yf = fft(y)
    >>> xf = np.linspace(0.0, 1.0/(2.0*T), N//2)
    >>> import matplotlib.pyplot as plt
    >>> plt.plot(xf, 2.0/N * np.abs(yf[0:N//2]))
    >>> plt.grid()
    >>> plt.show()


The FFT input signal is inherently truncated. This truncation can be modelled
as multiplication of an infinite signal with a rectangular window function. In
the spectral domain this multiplication becomes convolution of the signal
spectrum with the window function spectrum, being of form :math:`\sin(x)/x`.
This convolution is the cause of an effect called spectral leakage (see
[WPW]_). Windowing the signal with a dedicated window function helps mitigate
spectral leakage. The example below uses a Blackman window from scipy.signal
and shows the effect of windowing (the zero component of the FFT has been
truncated for illustrative purposes).

.. plot::

    >>> from scipy.fftpack import fft
    >>> # Number of sample points
    >>> N = 600
    >>> # sample spacing
    >>> T = 1.0 / 800.0
    >>> x = np.linspace(0.0, N*T, N)
    >>> y = np.sin(50.0 * 2.0*np.pi*x) + 0.5*np.sin(80.0 * 2.0*np.pi*x)
    >>> yf = fft(y)
    >>> from scipy.signal import blackman
    >>> w = blackman(N)
    >>> ywf = fft(y*w)
    >>> xf = np.linspace(0.0, 1.0/(2.0*T), N/2)
    >>> import matplotlib.pyplot as plt
    >>> plt.semilogy(xf[1:N//2], 2.0/N * np.abs(yf[1:N//2]), '-b')
    >>> plt.semilogy(xf[1:N//2], 2.0/N * np.abs(ywf[1:N//2]), '-r')
    >>> plt.legend(['FFT', 'FFT w. window'])
    >>> plt.grid()
    >>> plt.show()


In case the sequence x is complex-valued, the spectrum is no longer symmetric.
To simplify working wit the FFT functions, scipy provides the following two<commit_msg>Fix typo in fftpack.rst<commit_after>Fourier Transforms (:mod:`scipy.fftpack`)
=========================================

.. sectionauthor:: Scipy Developers

.. currentmodule:: scipy.fftpack

.. contents::


Fourier analysis is a method for expressing a function as a sum of periodic
components, and for recovering the signal from those components.  When both
the function and its Fourier transform are replaced with discretized
counterparts, it is called the discrete Fourier transform (DFT).  The DFT has
become a mainstay of numerical computing in part because of a very fast
algorithm for computing it, called the Fast Fourier Transform (FFT), which was
known to Gauss (1805) and was brought to light in its current form by Cooley
and Tukey [CT65]_.  Press et al. [NR07]_ provide an accessible introduction to
Fourier analysis and its applications.

.. note::

   PyFFTW_ provides a way to replace a number of functions in `scipy.fftpack`
   with its own functions, which are usually significantly faster, via
   pyfftw.interfaces_.  Because PyFFTW_ relies on the GPL-licensed FFTW_ it
   cannot be included in Scipy.  Users for whom the speed of FFT routines is
   critical should consider installing PyFFTW_.


Fast Fourier transforms
-----------------------

One dimensional discrete Fourier transforms
___________________________________________

The FFT `y[k]` of length :math:`N` of the length-:math:`N` sequence `x[n]` is
defined as

.. math::

    y[k] = \sum_{n=0}^{N-1} e^{-2 \pi j \frac{k n}{N} } x[n] \, ,

and the inverse transform is defined as follows

.. math::

    x[n] = \frac{1}{N} \sum_{k=0}^{N-1} e^{2 \pi j \frac{k n}{N} } y[k] \, .

These transforms can be calculated by means of :func:`fft` and :func:`ifft`,
respectively as shown in the following example.

>>> from scipy.fftpack import fft, ifft
>>> x = np.array([1.0, 2.0, 1.0, -1.0, 1.5])
>>> y = fft(x)
>>> y
array([ 4.5       +0.j        ,  2.08155948-1.65109876j,
       -1.83155948+1.60822041j, -1.83155948-1.60822041j,
        2.08155948+1.65109876j])
>>> yinv = ifft(y)
>>> yinv
array([ 1.0+0.j,  2.0+0.j,  1.0+0.j, -1.0+0.j,  1.5+0.j])


From the definition of the FFT it can be seen that

.. math::

    y[0] = \sum_{n=0}^{N-1} x[n] \, .

In the example

>>> np.sum(x)
4.5

which corresponds to :math:`y[0]`. For N even, the elements
:math:`y[1]...y[N/2-1]` contain the positive-frequency terms, and the elements
:math:`y[N/2]...y[N-1]` contain the negative-frequency terms, in order of
decreasingly negative frequency. For N odd, the elements
:math:`y[1]...y[(N-1)/2]` contain the positive- frequency terms, and the
elements :math:`y[(N+1)/2]...y[N-1]` contain the negative- frequency terms, in
order of decreasingly negative frequency.

In case the sequence x is real-valued, the values of :math:`y[n]` for positive
frequencies is the conjugate of the values :math:`y[n]` for negative
frequencies (because the spectrum is symmetric). Typically, only the FFT
corresponding to positive frequencies is plotted.

The example plots the FFT of the sum of two sines.

.. plot::

    >>> from scipy.fftpack import fft
    >>> # Number of sample points
    >>> N = 600
    >>> # sample spacing
    >>> T = 1.0 / 800.0
    >>> x = np.linspace(0.0, N*T, N)
    >>> y = np.sin(50.0 * 2.0*np.pi*x) + 0.5*np.sin(80.0 * 2.0*np.pi*x)
    >>> yf = fft(y)
    >>> xf = np.linspace(0.0, 1.0/(2.0*T), N//2)
    >>> import matplotlib.pyplot as plt
    >>> plt.plot(xf, 2.0/N * np.abs(yf[0:N//2]))
    >>> plt.grid()
    >>> plt.show()


The FFT input signal is inherently truncated. This truncation can be modelled
as multiplication of an infinite signal with a rectangular window function. In
the spectral domain this multiplication becomes convolution of the signal
spectrum with the window function spectrum, being of form :math:`\sin(x)/x`.
This convolution is the cause of an effect called spectral leakage (see
[WPW]_). Windowing the signal with a dedicated window function helps mitigate
spectral leakage. The example below uses a Blackman window from scipy.signal
and shows the effect of windowing (the zero component of the FFT has been
truncated for illustrative purposes).

.. plot::

    >>> from scipy.fftpack import fft
    >>> # Number of sample points
    >>> N = 600
    >>> # sample spacing
    >>> T = 1.0 / 800.0
    >>> x = np.linspace(0.0, N*T, N)
    >>> y = np.sin(50.0 * 2.0*np.pi*x) + 0.5*np.sin(80.0 * 2.0*np.pi*x)
    >>> yf = fft(y)
    >>> from scipy.signal import blackman
    >>> w = blackman(N)
    >>> ywf = fft(y*w)
    >>> xf = np.linspace(0.0, 1.0/(2.0*T), N/2)
    >>> import matplotlib.pyplot as plt
    >>> plt.semilogy(xf[1:N//2], 2.0/N * np.abs(yf[1:N//2]), '-b')
    >>> plt.semilogy(xf[1:N//2], 2.0/N * np.abs(ywf[1:N//2]), '-r')
    >>> plt.legend(['FFT', 'FFT w. window'])
    >>> plt.grid()
    >>> plt.show()


In case the sequence x is complex-valued, the spectrum is no longer symmetric.
To simplify working with the FFT functions, scipy provides the following two
{'fraction_non_alphanumeric': 0.15246411723376493, 'fraction_numerical': 0.041754491618990267, 'mean_word_length': 3.34161220043573, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 231, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7126229', 'n_tokens_mistral': 3679, 'n_tokens_neox': 3406, 'n_words': 1210}