Editing Discrete Fourier transform (section)

== Applications ==
The DFT has seen wide usage across a large number of fields; we only sketch a few examples below (see also the references at the end). All applications of the DFT depend crucially on the availability of a fast algorithm to compute discrete Fourier transforms and their inverses, a [[fast Fourier transform]].

=== Spectral analysis ===

When the DFT is used for [[signal spectral analysis]], the <math>\{x_n\}</math> sequence usually represents a finite set of uniformly spaced time-samples of some signal <math>x(t)\,</math>, where <math>t</math> represents time.  The conversion from continuous time to samples (discrete-time) changes the underlying [[continuous Fourier transform|Fourier transform]] of <math>x(t)</math> into a [[discrete-time Fourier transform]] (DTFT), which generally entails a type of distortion called [[aliasing]].  Choice of an appropriate sample-rate (see ''[[Nyquist rate]]'') is the key to minimizing that distortion.  Similarly, the conversion from a very long (or infinite) sequence to a manageable size entails a type of distortion called ''[[Spectral leakage|leakage]]'', which is manifested as a loss of detail (a.k.a. resolution) in the DTFT.  Choice of an appropriate sub-sequence length is the primary key to minimizing that effect.  When the available data (and time to process it) is more than the amount needed to attain the desired frequency resolution, a standard technique is to perform multiple DFTs, for example to create a [[spectrogram]].  If the desired result is a power spectrum and noise or randomness is present in the data, averaging the magnitude components of the multiple DFTs is a useful procedure to reduce the [[variance]] of the spectrum (also called a [[periodogram]] in this context); two examples of such techniques are the [[Welch method]] and the [[Bartlett method]]; the general subject of estimating the power spectrum of a noisy signal is called [[spectral estimation]].

A final source of distortion (or perhaps ''illusion'') is the DFT itself, because it is just a discrete sampling of the DTFT, which is a function of a continuous frequency domain.  That can be mitigated by increasing the resolution of the DFT.  That procedure is illustrated at {{slink|Discrete-time Fourier transform|Sampling the DTFT|nopage=y}}.
* The procedure is sometimes referred to as ''zero-padding'', which is a particular implementation used in conjunction with the [[fast Fourier transform]] (FFT) algorithm.  The inefficiency of performing multiplications and additions with zero-valued "samples" is more than offset by the inherent efficiency of the FFT.
* As already stated, leakage imposes a limit on the inherent resolution of the DTFT, so there is a practical limit to the benefit that can be obtained from a fine-grained DFT.
'''Steps to Perform Spectral Analysis of Audio Signal'''

'''1.Recording and Pre-Processing the Audio Signal'''

Begin by recording the audio signal, which could be a spoken password, [[music]], or any other [[sound]]. Once recorded, the audio signal is denoted as x[n], where n represents the discrete time index. To enhance the accuracy of spectral analysis, any unwanted noise should be reduced using appropriate [[Filter design|filtering techniques.]]

'''2.Plotting the Original Time-Domain Signal'''

After [[noise]] reduction, the audio signal is plotted in the time domain to visualize its characteristics over time. This helps in understanding the amplitude variations of the signal as a [[function of time]], which provides an initial insight into the signal's behavior.

'''3.Transforming the Signal from Time Domain to Frequency Domain'''

The next step is to transform the audio signal from the time domain to the frequency domain using the Discrete Fourier Transform (DFT). The DFT is defined as:

<math>X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-j \frac{2 \pi}{N}kn}</math>

where N is the total number of samples, k represents the frequency index, and X[k] is the complex-valued frequency spectrum of the signal. The DFT allows for decomposing the signal into its constituent frequency components, providing a representation that indicates which frequencies are present and their respective magnitudes.

'''4.Plotting the Magnitude Spectrum'''

The magnitude of the frequency-domain representation X[k] is plotted to analyze the spectral content. The magnitude spectrum shows how the energy of the signal is distributed across different frequencies, which is useful for identifying prominent frequency components. It is calculated as:

<math>|X[k]| = \sqrt{\text{Re}(X[k])^2 + \text{Im}(X[k])^2}</math>

=== Example ===
Analyze a discrete-time audio signal in the frequency domain using the DFT to identify its frequency components

==== Given Data ====
Let's consider a simple discrete-time audio signal represented as:

<math>x[n] = \{ 1, 0.5, -0.5, -1 \}</math>

where n represents discrete time samples of the signal.

'''1.Time-Domain Signal Representation'''

The given time-domain signal is:

<math display="inline">x[0] = 1, \quad x[1] = 0.5, \quad x[2] = -0.5, \quad x[3] = -1
</math>

===== 2.DFT Calculation =====
The DFT is calculated using the formula:

<math>X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-j \frac{2 \pi}{N}kn}</math>

where N is the number of samples (in this case, N=4).

Let's compute X[k] for k=0,1,2,3

For k=0:

<math>X[0] = 1 \cdot e^{-j \frac{2\pi}{4} \cdot 0 \cdot 0} + 0.5 \cdot e^{-j \frac{2\pi}{4} \cdot 0 \cdot 1} + (-0.5) \cdot e^{-j \frac{2\pi}{4} \cdot 0 \cdot 2} + (-1) \cdot e^{-j \frac{2\pi}{4} \cdot 0 \cdot 3}</math>

<math>X[0] = 1 + 0.5 - 0.5 - 1 = 0</math>

For k=1:

<math>X[1] = 1 \cdot e^{-j \frac{2\pi}{4} \cdot 1 \cdot 0} + 0.5 \cdot e^{-j \frac{2\pi}{4} \cdot 1 \cdot 1} + (-0.5) \cdot e^{-j \frac{2\pi}{4} \cdot 1 \cdot 2} + (-1) \cdot e^{-j \frac{2\pi}{4} \cdot 1 \cdot 3}
</math>

<math>X[1] = 1 + 0.5(-j) + (-0.5)(-1) + (-1)(j)
</math>

<math>X[1] = 1 - 0.5j + 0.5 - j = 1.5 - 1.5j
</math>

For k=2:

<math>X[2] = 1 \cdot e^{-j \frac{2\pi}{4} \cdot 2 \cdot 0} + 0.5 \cdot e^{-j \frac{2\pi}{4} \cdot 2 \cdot 1} + (-0.5) \cdot e^{-j \frac{2\pi}{4} \cdot 2 \cdot 2} + (-1) \cdot e^{-j \frac{2\pi}{4} \cdot 2 \cdot 3}</math>

<math>X[2] = 1 + 0.5(-1) + (-0.5)(1) + (-1)(-1)
</math>

<math>X[2] = 1 - 0.5 - 0.5 + 1 = 1

</math>

For k=3:

<math>X[3] = 1 \cdot e^{-j \frac{2\pi}{4} \cdot 3 \cdot 0} + 0.5 \cdot e^{-j \frac{2\pi}{4} \cdot 3 \cdot 1} + (-0.5) \cdot e^{-j \frac{2\pi}{4} \cdot 3 \cdot 2} + (-1) \cdot e^{-j \frac{2\pi}{4} \cdot 3 \cdot 3}
</math>

<math>X[3] = 1 + 0.5j + (-0.5)(-1) + (-1)(-j)
</math>

<math>X[3] = 1 + 0.5j + 0.5 + j = 1.5 + 1.5j

</math>

===== 3.Magnitude Spectrum =====
The magnitude of X[k] represents the strength of each frequency component:

<math>|X[0]| = 0, \quad |X[1]| = \sqrt{(1.5)^2 + (-1.5)^2} = \sqrt{4.5} \approx 2.12
</math>

<math>|X[2]| = 1, \quad |X[3]| = \sqrt{(1.5)^2 + (1.5)^2} = \sqrt{4.5} \approx 2.12</math>

The resulting frequency components indicate the distribution of signal energy at different frequencies. The peaks in the magnitude spectrum correspond to dominant frequencies in the original signal.

=== Optics, diffraction, and tomography ===

The discrete Fourier transform is widely used with spatial frequencies in modeling the way that light, electrons, and other probes travel through optical systems and scatter from objects in two and three dimensions. The dual (direct/reciprocal) vector space of three dimensional objects further makes available a three dimensional reciprocal lattice, whose construction from translucent object shadows (via the [[Projection-slice theorem|Fourier slice theorem]]) allows tomographic reconstruction of three dimensional objects with a wide range of applications e.g. in modern medicine.

=== Filter bank ===
See {{slink|Filter bank|FFT filter banks|nopage=y}} and {{slink|Discrete-time Fourier transform|Sampling the DTFT|nopage=y}}.

===Data compression===
The field of digital signal processing relies heavily on operations in the frequency domain (i.e. on the Fourier transform). For example, several [[lossy compression|lossy]] image and sound compression methods employ the discrete Fourier transform: the signal is cut into short segments, each is transformed, and then the Fourier coefficients of high frequencies, which are assumed to be unnoticeable, are discarded. The decompressor computes the inverse transform based on this reduced number of Fourier coefficients. (Compression applications often use a specialized form of the DFT, the [[discrete cosine transform]] or sometimes the [[modified discrete cosine transform]].)
Some relatively recent compression algorithms, however, use [[wavelet transform]]s, which give a more uniform compromise between time and frequency domain than obtained by chopping data into segments and transforming each segment.  In the case of [[JPEG2000]], this avoids the spurious image features that appear when images are highly compressed with the original [[JPEG]].

===Partial differential equations===
Discrete Fourier transforms are often used to solve [[partial differential equations]], where again the DFT is used as an approximation for the [[Fourier series]] (which is recovered in the limit of infinite ''N''). The advantage of this approach is that it expands the signal in complex exponentials <math>e^{inx}</math>, which are eigenfunctions of differentiation: <math>{\text{d} \big( e^{inx} \big) }/\text{d}x = in e^{inx}</math>. Thus, in the Fourier representation, differentiation is simple—we just multiply by <math>in</math>.  (However, the choice of <math>n</math> is not unique due to aliasing; for the method to be convergent, a choice similar to that in the [[#Trigonometric interpolation polynomial|trigonometric interpolation]] section above should be used.) A [[linear differential equation]] with constant coefficients is transformed into an easily solvable algebraic equation. One then uses the inverse DFT to transform the result back into the ordinary spatial representation. Such an approach is called a [[spectral method]].

===Polynomial multiplication===

Suppose we wish to compute the polynomial product ''c''(''x'') = ''a''(''x'') · ''b''(''x'').  The ordinary product expression for the coefficients of ''c'' involves a linear (acyclic) convolution, where indices do not "wrap around."  This can be rewritten as a cyclic convolution by taking the coefficient vectors for ''a''(''x'') and ''b''(''x'') with constant term first, then appending zeros so that the resultant coefficient vectors '''a''' and '''b''' have dimension {{Nowrap|''d'' > deg(''a''(''x'')) + deg(''b''(''x''))}}.  Then,

:<math>\mathbf{c} = \mathbf{a} * \mathbf{b}</math>

Where '''c''' is the vector of coefficients for ''c''(''x''), and the convolution operator <math>*\,</math> is defined so

:<math>c_n = \sum_{m=0}^{d-1}a_m b_{n-m\ \mathrm{mod}\ d} \qquad\qquad\qquad n=0,1\dots,d-1</math>

But convolution becomes multiplication under the DFT:

:<math>\mathcal{F}(\mathbf{c}) = \mathcal{F}(\mathbf{a})\mathcal{F}(\mathbf{b})</math>

Here the vector product is taken elementwise.  Thus the coefficients of the product polynomial ''c''(''x'') are just the terms 0, ..., deg(''a''(''x'')) + deg(''b''(''x'')) of the coefficient vector

:<math>\mathbf{c} = \mathcal{F}^{-1}(\mathcal{F}(\mathbf{a})\mathcal{F}(\mathbf{b})).</math>

With a [[fast Fourier transform]], the resulting algorithm takes ''O''(''N''&nbsp;log&nbsp;''N'') arithmetic operations.  Due to its simplicity and speed, the [[Cooley–Tukey FFT algorithm]], which is limited to [[composite number|composite]] sizes, is often chosen for the transform operation.  In this case, ''d'' should be chosen as the smallest integer greater than the sum of the input polynomial degrees that is factorizable into small prime factors (e.g. 2, 3, and 5, depending upon the FFT implementation).

====Multiplication of large integers====

The fastest known [[multiplication algorithms|algorithms]] for the multiplication of very large [[integer]]s use the polynomial multiplication method outlined above.  Integers can be treated as the value of a polynomial evaluated specifically at the number base, with the coefficients of the polynomial corresponding to the digits in that base (ex. <math>123 = 1 \cdot 10^2 + 2 \cdot 10^1 + 3 \cdot 10^0</math>).  After polynomial multiplication, a relatively low-complexity carry-propagation step completes the multiplication.

==== Convolution ====
When data is [[Convolution|convolved]] with a function with wide support, such as for downsampling by a large sampling ratio, because of the [[Convolution theorem]] and the FFT algorithm, it may be faster to transform it, multiply pointwise by the transform of the filter and then reverse transform it.  Alternatively, a good filter is obtained by simply truncating the transformed data and re-transforming the shortened data set.