View source for Applets:Discrete Fouriertransform and Inverse

{{LntAppletLinkEnDe|dft_en|dft}}

 
==Applet Description==
<br>
The conventional Fourier Transform&nbsp; $\rm (FT)$&nbsp; allows the calculation of the spectral function&nbsp; $X(f)$&nbsp; of a time-continuous signal&nbsp; $x(t)$.&nbsp; 

In contrast, the Discrete Fourier Transform&nbsp; $\rm (DFT)$&nbsp; is limited to a time discrete signal, represented by&nbsp; $N$&nbsp; time domain coefficients &nbsp; $d(\nu)$&nbsp; with indices&nbsp; $\nu = 0, \text{...} , N\hspace{-0.1cm}-\hspace{-0.1cm}1$, which can be interpreted as equidistant samples of the time continuous signal&nbsp; $x(t)$.

If the&nbsp; [[Signal_Representation/Discrete-Time_Signal_Representation#Sampling_theorem|"sampling theorem"]]&nbsp;  is fulfilled, the DFT algorithm likewise allows the calculation of&nbsp; $N$&nbsp; frequency domain coefficients&nbsp; $D(\mu)$&nbsp; with indices&nbsp; $\mu = 0, \text{...} , N\hspace{-0.1cm}-\hspace{-0.1cm}1$.&nbsp;  These are equidistant samples of the frequency continuous spectrum&nbsp; $X(f)$.

*The applet illustrates the properties of the&nbsp; $\text{DFT:}\hspace{0.3cm}d(\nu)\hspace{0.1cm} \Rightarrow \hspace{0.1cm} D(\mu)$&nbsp; by using the example&nbsp; $N=16$.&nbsp; The default &nbsp; $d(\nu)$ assignments  for the DFT are: 

:(a)&nbsp; According to the input field,&nbsp; (b)&nbsp; Constant signal,&nbsp; (c)&nbsp;  Complex exponential function (of time),&nbsp; (d)&nbsp;  Harmonic oscillation (with &nbsp;$($Phase &nbsp;$\varphi = 45^\circ)$,
:(e)&nbsp; Cosine signal (one period),&nbsp; (f)&nbsp; Sinusoidal signal (one period),&nbsp; (g)&nbsp;  Cosine signal (two periods),&nbsp;(h)&nbsp;  Alternating time coefficients, (i)&nbsp; Dirac delta impulse,&nbsp;
: (j)&nbsp; Rectangular pulse ,&nbsp; (k)&nbsp;  Triangular pulse,&nbsp; (l)&nbsp;  Gaussian pulse.
  
*Possible &nbsp;$D(\mu)$ assignments  for the Inverse Discrete Fourier Transform &nbsp; &rArr; &nbsp; $\text{IDFT:}\hspace{0.3cm}D(\mu)\hspace{0.1cm} \Rightarrow \hspace{0.1cm} d(\nu)$&nbsp;  are:

:(A)&nbsp; According to the input field,&nbsp; (B)&nbsp; Constant spectrum,&nbsp; (C)&nbsp;  Complex exponential function (of frequency),&nbsp; (D)&nbsp;  Equivalent to setting (d) in the time domain,
:(E)&nbsp; Cosine spectrum (one frequency period),&nbsp; (F)&nbsp; Sinusoidal spectrum (one frequency period),&nbsp; (G)&nbsp;  Cosine spectrum (two frequency periods),&nbsp; 
:(H)&nbsp;  Alternating spectral coefficients, (I)&nbsp; Dirac delta spectrum,&nbsp; (J)&nbsp; Rectangular spectrum,&nbsp; (K)&nbsp;  Triangular spectrum,&nbsp; (L)&nbsp;  Gaussian spectrum. 

The applet uses the framework  &nbsp;[https://en.wikipedia.org/wiki/Plotly "Plot.ly"].


  
==Theoretical Background==
<br>
===Arguments for the discrete realization of the Fourier transform===

The&nbsp; '''Fourier transform'''&nbsp; according to the conventional description for continuous-time signals has an infinitely high selectivity due to the unlimited extension of the integration interval and is therefore an ideal theoretical tool for spectral analysis.

If the spectral components&nbsp; $X(f)$&nbsp; of a time function&nbsp; $x(t)$&nbsp; are to be determined numerically, the general transformation equations 
 
:$$\begin{align*}X(f) & =  \int_{-\infty
 }^{+\infty}x(t) \cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi f t}\hspace{0.1cm} {\rm d}t\hspace{0.5cm} \Rightarrow\hspace{0.5cm} \text{Forward transformation}\hspace{0.7cm} \Rightarrow\hspace{0.5cm} \text{First Fourier integral}
 \hspace{0.05cm},\\
x(t) & =  \int_{-\infty
 }^{+\infty}\hspace{-0.15cm}X(f) \cdot {\rm e}^{\hspace{0.05cm}+{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi f t}\hspace{0.1cm} {\rm d}f\hspace{0.35cm} \Rightarrow\hspace{0.5cm}
\text{Backward transformation}\hspace{0.4cm} \Rightarrow\hspace{0.5cm} \text{Second Fourier integral}
 \hspace{0.05cm}\end{align*}$$

are unsuitable for two reasons:
*The equations apply exclusively to continuous-time signals. With digital computers or signal processors, however, only discrete-time signals can be processed.
*For a numerical evaluation of the two Fourier integrals it is necessary to limit the respective integration interval to a finite value.


{{BlaueBox|TEXT=
$\text{This results in the following consequence:}$&nbsp;

A&nbsp; '''continuous signal'''&nbsp; must undergo two processes before the numerical determination of its spectral properties, viz.
*&nbsp; '''sampling'''&nbsp; for discretization, and
*&nbsp; '''windowing'''&nbsp; to limit the integration interval.}}


In the following, starting from an aperiodic time function&nbsp; $x(t)$&nbsp; and the corresponding Fourier spectrum&nbsp; $X(f)$,&nbsp; a discrete-time and discrete-frequency description suitable for computer processing is presented.


===Time discretization &ndash; periodization in the frequency domain===

The following graphs uniformly show the time domain on the left and the frequency domain on the right. Without restriction of generality,&nbsp; $x(t)$&nbsp; and&nbsp; $X(f)$&nbsp; are real and Gaussian, respectively.

[[File:P_ID1132__Sig_T_5_1_S2_neu.png|center|frame|Discretization in the time domain – periodization in the frequency domain]]

One can describe the sampling of the time signal&nbsp; $x(t)$&nbsp; by multiplication with a Dirac delta pulse&nbsp; $p_{\delta}(t)$.&nbsp; This results in the time signal sampled at distance&nbsp; $T_{\rm A}$&nbsp; 
 
:$${\rm A}\{x(t)\} =  \sum_{\nu = - \infty }^{+\infty} T_{\rm A} \cdot x(\nu \cdot T_{\rm A})\cdot
 \delta (t- \nu \cdot T_{\rm A}
 )\hspace{0.05cm}.$$

We now transform this sampled signal&nbsp; $\text{A}\{ x(t)\}$&nbsp; into the frequency domain. The multiplication of the Dirac delta pulse&nbsp; $p_{\delta}(t)$&nbsp; with&nbsp; $x(t)$&nbsp; corresponds in the frequency domain to the convolution of&nbsp; $P_{\delta}(f)$&nbsp; with&nbsp; $X(f)$. The periodized spectrum&nbsp; $\text{P}\{ X(f)\}$ is obtained, where&nbsp; $f_{\rm P}$&nbsp; is the frequency period of the function&nbsp; $\text{P}\{ X(f)\}$:&nbsp; 
 
:$${\rm A}\{x(t)\} \hspace{0.2cm}\circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\, \hspace{0.2cm} {\rm P}\{X(f)\} =  \sum_{\mu = - \infty }^{+\infty}
 X (f- \mu \cdot f_{\rm P} )\hspace{0.5cm} {\rm with }\hspace{0.5cm}f_{\rm
 P}= {1}/{T_{\rm A}}\hspace{0.05cm}.$$

*We call the sampled signal&nbsp; $\text{A}\{ x(t)\}$.
*The&nbsp; '''frequency period'''&nbsp; is denoted by&nbsp; $f_{\rm P}$ = $1/T_{\rm A}$.&nbsp; 


The graph above shows the functional relationship described here. It should be noted:
*The frequency period&nbsp; $f_{\rm P}$&nbsp; was deliberately chosen small here so that the overlap of the spectra to be summed can be clearly seen.
*In practice, due to the sampling theorem,&nbsp; $f_{\rm P}$&nbsp; should be at least twice as large as the largest frequency contained in the signal&nbsp; $x(t)$.&nbsp; 
*If this is not fulfilled,&nbsp; '''aliasing'''&nbsp; must be expected.



===Frequency discretization &ndash; periodization in the time domain===

The discretization of&nbsp; $X(f)$&nbsp; can also be described by a multiplication with a Dirac delta pulse. The result is the spectrum sampled at distance&nbsp; $f_{\rm A}$:&nbsp; 
 
:$${\rm A}\{X(f)\} =  X(f) \cdot   \sum_{\mu = - \infty }^{+\infty}
 f_{\rm A} \cdot \delta (f- \mu \cdot f_{\rm A } ) =  \sum_{\mu = - \infty }^{+\infty}
 f_{\rm A} \cdot X(\mu \cdot f_{\rm A } ) \cdot\delta (f- \mu \cdot f_{\rm A } )\hspace{0.05cm}.$$

Transforming the frequency Dirac delta pulse used here $($with pulse weights&nbsp; $f_{\rm A})$&nbsp; into the time domain, we obtain with&nbsp; $T_{\rm P} = 1/f_{\rm A}$:
 
:$$\sum_{\mu = - \infty }^{+\infty}
 f_{\rm A} \cdot \delta (f- \mu \cdot f_{\rm A } ) \hspace{0.2cm}\bullet\!\!-\!\!\!-\!\!\!-\!\!\circ\, \hspace{0.2cm}
 \sum_{\nu = - \infty }^{+\infty}
  \delta (t- \nu \cdot T_{\rm P } ) \hspace{0.05cm}.$$

The multiplication with&nbsp; $X(f)$&nbsp; corresponds in the time domain to the convolution with&nbsp; $x(t)$. The signal&nbsp; $\text{P}\{ x(t)\}$ periodized at distance&nbsp; $T_{\rm P}$&nbsp; is obtained:
 
:$${\rm A}\{X(f)\} \hspace{0.2cm}\bullet\!\!-\!\!\!-\!\!\!-\!\!\circ\, \hspace{0.2cm}
 {\rm P}\{x(t)\} = x(t) \star \sum_{\nu = - \infty }^{+\infty}
  \delta (t- \nu \cdot T_{\rm P } )= \sum_{\nu = - \infty }^{+\infty}
  x (t- \nu \cdot T_{\rm P } ) \hspace{0.05cm}.$$

[[File:P_ID1134__Sig_T_5_1_S3_neu.png|right|frame|Discretization in the frequency domain – periodization in the time domain]]
{{GraueBox|TEXT=
$\text{Example 1:}$&nbsp;
This relationship is illustrated in the graphic:
*Due to the coarse frequency rastering, this example results in a relatively small value for the time period&nbsp; $T_{\rm P}$.&nbsp; 


*Therefore, the (blue) periodized time signal&nbsp; $\text{P}\{ x(t)\}$&nbsp; differs significantly from&nbsp; $x(t)$ due to overlaps.}}


===Finite signal representation===

[[File:P_ID1135__Sig_T_5_1_S4_neu.png|right|frame|Finite signals of the Discrete Fourier Transform]]
One arrives at the so-called&nbsp; ''finite signal representation''&nbsp;  
*when both the time function&nbsp; $x(t)$ and
*the spectral function&nbsp; $X(f)$ 


are specified exclusively by their sample values.
<br clear=all>
The graph is to be interpreted as follows:
*In the left picture the function&nbsp; $\text{A}\{ \text{P}\{ x(t)\}\}$ is drawn in blue. It is obtained by sampling the periodized time function&nbsp; $\text{P}\{ x(t)\}$&nbsp; with equidistant Dirac delta pulses in the distance&nbsp; $T_{\rm A} = 1/f_{\rm P}$.
*In the right picture the function&nbsp; $\text{P}\{ \text{A}\{ X(f)\}\}$ is drawn in green. This results from periodization $($with&nbsp; $f_{\rm P})$&nbsp; of the sampled spectral function&nbsp; $\{ \text{A}\{ X(f)\}\}$. 
*There is also a Fourier correspondence between the blue finite signal and the green finite signal, as follows:
 
:$${\rm A}\{{\rm P}\{x(t)\}\} \hspace{0.2cm}\circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\, \hspace{0.2cm} {\rm P}\{{\rm A}\{X(f)\}\} \hspace{0.05cm}.$$

{{BlaueBox|TEXT=
However, the Dirac delta lines of the periodic continuation&nbsp; $\text{P}\{ \text{A}\{ X(f)\}\}$&nbsp; of the sampled spectral function fall into the same frequency grid as those of&nbsp; $\text{A}\{ X(f)\}$ only if the frequency period&nbsp; $f_{\rm P}$&nbsp; is an integer multiple&nbsp; $(N)$&nbsp; of the frequency sampling interval&nbsp; $f_{\rm A}$.&nbsp; 

*When using the finite signal representation, the following condition must always be fulfilled, where in practice a power of two is usually used for the natural number&nbsp; $N$&nbsp; (the graph above is based on the value&nbsp; $N = 8$&nbsp;):
 
:$$f_{\rm P} = N \cdot f_{\rm A} \hspace{0.5cm} \Rightarrow\hspace{0.5cm} {1}/{T_{\rm A} }= N \cdot f_{\rm A} \hspace{0.5cm} \Rightarrow\hspace{0.5cm}
 N \cdot f_{\rm A}\cdot T_{\rm A} = 1\hspace{0.05cm}.$$}}


If the condition&nbsp; $N \cdot f_{\rm A} \cdot T_{\rm A} = 1$&nbsp; is satisfied, the order of periodization and sampling can be interchanged. Thus:
 
:$${\rm A}\{{\rm P}\{x(t)\}\} = {\rm P}\{{\rm A}\{x(t)\}\}\hspace{0.2cm}\circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\, \hspace{0.2cm}
 {\rm P}\{{\rm A}\{X(f)\}\} = {\rm A}\{{\rm P}\{X(f)\}\}\hspace{0.05cm}.$$

{{BlaueBox|TEXT=
$\text{Conclusion:}$&nbsp;
*The time function&nbsp; $\text{P}\{ \text{A}\{ x(t)\}\}$&nbsp; has the period&nbsp; $T_{\rm P} = N \cdot T_{\rm A}$. 
*The period in the frequency domain is&nbsp; $f_{\rm P} = N \cdot f_{\rm A}$. 
*For the description of the discretized time and frequency course&nbsp; $N$&nbsp; '''complex numerical values''' in the form of pulse weights are sufficient in each case.}}


{{GraueBox|TEXT=
$\text{Example 2:}$&nbsp;
A time-limited (pulse-like) signal&nbsp; $x(t)$&nbsp; is present in sampled form, where the distance between two samples is&nbsp; $T_{\rm A} = 1\, {\rm &micro; s}$:&nbsp; 
*After a discrete Fourier transformation with&nbsp; $N = 512$&nbsp; the spectrum&nbsp; $X(f)$&nbsp; is available as samples with the distance&nbsp; $f_{\rm A} = (N \cdot T_{\rm A})^{–1} \approx 1.953\,\text{kHz} $.&nbsp; 
*Increasing the DFT parameter to&nbsp;  $N= 2048$ results in a finer frequency grid with&nbsp; $f_{\rm A} \approx 488\,\text{Hz}$.}}



===Discrete Fourier Transform===

From the conventional&nbsp; "first Fourier integral"
 
:$$X(f) =\int_{-\infty
 }^{+\infty}x(t) \cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi \hspace{0.05cm}\cdot \hspace{0.05cm} f  \hspace{0.05cm}\cdot \hspace{0.05cm}t}\hspace{0.1cm} {\rm d}t$$

discretization&nbsp; $(\text{d}t \to T_{\rm A}$,&nbsp;  $t \to \nu \cdot T_{\rm A}$,&nbsp;  $f \to \mu \cdot f_{\rm A}$,&nbsp;  $T_{\rm A} \cdot f_{\rm A} = 1/N)$&nbsp; yields the sampled and periodized spectral function
 
:$${\rm P}\{X(\mu \cdot f_{\rm A})\} = T_{\rm A} \cdot \sum_{\nu = 0 }^{N-1}
  {\rm P}\{x(\nu \cdot T_{\rm A})\}\cdot  {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi \hspace{0.05cm} \cdot \hspace{0.05cm}\nu \hspace{0.05cm}
 \cdot \hspace{0.05cm}\mu /N} \hspace{0.05cm}.$$

It is taken into account that due to the discretization the periodized functions have to be used in each case. 

For reasons of a simplified notation we now make the following substitutions:
*Let the&nbsp; $N$&nbsp; '''time-domain coefficients'''&nbsp; be associated with the indexing variable&nbsp; $\nu = 0$, ... , $N - 1$:
:$$d(\nu) =
  {\rm P}\left\{x(t)\right\}{\big|}_{t \hspace{0.05cm}= \hspace{0.05cm}\nu \hspace{0.05cm}\cdot \hspace{0.05cm}T_{\rm A}}\hspace{0.05cm}.$$
*Let the&nbsp; $N$&nbsp; '''frequency-domain coefficients'''&nbsp; be associated with the indexing variable&nbsp; $\mu = 0,$ ... , $N$ – 1:
:$$D(\mu) = f_{\rm A} \cdot
  {\rm P}\left\{X(f)\right\}{\big|}_{f \hspace{0.05cm}= \hspace{0.05cm}\mu \hspace{0.05cm}\cdot \hspace{0.05cm}f_{\rm A}}\hspace{0.05cm}.$$
*Abbreviation for the&nbsp;  '''complex rotation factor'''&nbsp; depending on&nbsp; $N$&nbsp; is written:
:$$w  = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi /N}
 = \cos \left(  {2 \pi}/{N}\right)-{\rm j} \cdot \sin \left(  {2 \pi}/{N}\right)
 \hspace{0.05cm}.$$ 

[[File:P_ID2730__Sig_T_5_1_S5_neu.png|right|frame|On the definition of the Discrete Fourier Transform (DFT) with&nbsp; $N=8$]]
{{BlaueBox|TEXT=
$\text{Definition:}$&nbsp;

The term&nbsp;  '''Discrete Fourier Transform'''&nbsp; ('''DFT''' for short)&nbsp; means the calculation of the&nbsp; $N$&nbsp; spectral coefficients&nbsp; $D(\mu)$&nbsp; from the&nbsp; $N$&nbsp; signal coefficients&nbsp; $d(\nu)$:
 
:$$D(\mu) = \frac{1}{N} \cdot \sum_{\nu = 0 }^{N-1}
  d(\nu)\cdot  {w}^{\hspace{0.05cm}\nu \hspace{0.03cm} \cdot \hspace{0.05cm}\mu} \hspace{0.05cm}. $$

In the graph you can see in an example 
*the&nbsp; $N = 8$&nbsp; signal coefficients&nbsp; $d(\nu)$&nbsp; at the blue filling,
*the&nbsp; $N = 8$&nbsp; spectral coefficients&nbsp; $D(\mu)$&nbsp; at the green filling.}}


===Inverse Discrete Fourier Transform===

The Inverse Discrete Fourier Transform (IDFT) describes the&nbsp; "second Fourier integral"
 
:$$\begin{align*}x(t) & =  \int_{-\infty
 }^{+\infty}X(f) \cdot {\rm e}^{\hspace{0.05cm}{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi \hspace{0.05cm}\cdot \hspace{0.05cm} f \hspace{0.05cm}\cdot \hspace{0.05cm}
 t}\hspace{0.1cm} {\rm d}f\end{align*}$$

in discretized form: &nbsp; $d(\nu) =
  {\rm P}\left\{x(t)\right\}{\big|}_{t \hspace{0.05cm}= \hspace{0.05cm}\nu \hspace{0.05cm}\cdot \hspace{0.05cm}T_{\rm
  A}}\hspace{0.01cm}.$

[[File:P_ID2731__Sig_T_5_1_S6_neu.png|right|frame|For the definition of the IDFT with&nbsp; $N=8$]]
{{BlaueBox|TEXT=
$\text{Definition:}$&nbsp;

The term&nbsp;  '''Inverse Discrete Fourier Transform'''&nbsp; ('''IDFT''' for short)&nbsp; refers to the calculation of the signal coefficients&nbsp; $d(\nu)$&nbsp; from the spectral coefficients&nbsp; $D(\mu)$:
 
:$$d(\nu) =  \sum_{\mu = 0 }^{N-1}
 D(\mu) \cdot  {w}^{-\nu \hspace{0.03cm} \cdot \hspace{0.05cm}\mu} \hspace{0.05cm}.$$

With the indexing variables&nbsp; $\nu = 0,  \hspace{0.05cm}\text{...} \hspace{0.05cm}, N-1$&nbsp; und&nbsp; $\mu = 0,  \hspace{0.05cm}\text{...} \hspace{0.05cm}, N-1$&nbsp; also holds here:
:$$d(\nu) =
  {\rm P}\left\{x(t)\right\}{\big \vert}_{t \hspace{0.05cm}= \hspace{0.05cm}\nu \hspace{0.05cm}\cdot \hspace{0.05cm}T_{\rm
  A} }\hspace{0.01cm},$$
 
:$$D(\mu) = f_{\rm A} \cdot
  {\rm P}\left\{X(f)\right\}{\big \vert}_{f \hspace{0.05cm}= \hspace{0.05cm}\mu \hspace{0.05cm}\cdot \hspace{0.05cm}f_{\rm A} }
  \hspace{0.01cm},$$

:$$w  = {\rm e}^{- {\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi /N}
 \hspace{0.01cm}.$$}}

 
A comparison between DFT and IDFT shows that exactly the same algorithm can be used. The only differences of the IDFT compared to the DFT are:
*The exponent of the rotation factor must be applied with a different sign.
*With the IDFT the division by&nbsp; $N$ is omitted.


===Interpretation of DFT and IDFT===
<br>
The graph shows the discrete coefficients in the time and frequency domain together with the periodized continuous-time functions.

[[File:P_ID1136__Sig_T_5_1_S7_neu.png|center|frame|Time and frequency domain coefficients of the DFT]]

When using DFT or IDFT, it should be noted:
*According to the above definitions, the DFT coefficients&nbsp; $d(ν)$&nbsp; and&nbsp; $D(\mu)$&nbsp; always have the unit of the time function.
*Dividing&nbsp; $D(\mu)$&nbsp; by&nbsp; $f_{\rm A}$ gives the spectral value&nbsp; $X(\mu \cdot f_{\rm A})$.
*The spectral coefficients&nbsp; $D(\mu)$&nbsp; must always be set complex to be able to consider also odd time functions.
*In order to be able to transform band&ndash;pass signals in the equivalent lown&dash;pass range, complex time coefficients&nbsp; $d(\nu)$ are usually used.
*The basic interval for&nbsp; $\nu$&nbsp; and&nbsp;  $\mu$&nbsp; is usually defined as the range from&nbsp; $0$&nbsp; to&nbsp; $N - 1$, as in the above diagram.
*With the complex-valued number sequences&nbsp; $\langle \hspace{0.1cm}d(\nu)\hspace{0.1cm}\rangle  = \langle \hspace{0.1cm}d(0), \hspace{0.05cm}\text{...} \hspace{0.05cm} , d(N-1) \hspace{0.1cm}\rangle$  &nbsp; as well as &nbsp; $\langle \hspace{0.1cm}D(\mu)\hspace{0.1cm}\rangle  =   \langle \hspace{0.1cm}D(0), \hspace{0.05cm}\text{...} \hspace{0.05cm} , D(N-1) \hspace{0.1cm}\rangle$&nbsp; DFT and IDFT are symbolized similar to the conventional Fourier transform:
:$$\langle \hspace{0.1cm} D(\mu)\hspace{0.1cm}\rangle \hspace{0.2cm}\bullet\!\!-\!\!\!-(N)\!-\!\!\!-\!\!\hspace{0.05cm}\circ\, \hspace{0.2cm} \langle \hspace{0.1cm} d(\nu) \hspace{0.1cm}\rangle  \hspace{0.05cm}.$$ 
*If the time function&nbsp; $x(t)$&nbsp; is already limited to the range&nbsp; $0 \le t \lt N \cdot T_{\rm A}$,&nbsp; then the time coefficients output by the IDFT directly indicate the samples of the time function:  &nbsp; $d(\nu) = x(\nu \cdot T_{\rm A}).$
*If&nbsp; $x(t)$&nbsp; is shifted with respect to the basic interval, one has to choose the assignment between&nbsp; $x(t)$&nbsp; and the coefficients&nbsp; $d(\nu)$&nbsp; shown in&nbsp; $\text{Example 3}$.&nbsp; 


{{GraueBox|TEXT=
$\text{Example 3:}$&nbsp;
The upper graph shows the asymmetric triangular pulse&nbsp; $x(t)$ whose absolute width is smaller than&nbsp; $T_{\rm P} = N \cdot T_{\rm A}$. 

[[File:P_ID1139__Sig_T_5_1_S7b_neu.png|right|frame|For the assignment of the DFT coefficients with&nbsp; $N=8$]]

The sketch below shows the assigned DFT coefficients valid for&nbsp;  $N = 8$

*For&nbsp;  $\nu = 0,\hspace{0.05cm}\text{...} \hspace{0.05cm} , N/2 = 4$,&nbsp; &nbsp; $d(\nu) = x(\nu \cdot T_{\rm A})$ is valid:

:$$d(0) = x (0)\hspace{0.05cm}, \hspace{0.15cm}
d(1) = x (T_{\rm A})\hspace{0.05cm}, \hspace{0.15cm}
d(2) = x (2T_{\rm A})\hspace{0.05cm}, $$
:$$d(3) = x (3T_{\rm A})\hspace{0.05cm}, \hspace{0.15cm}
d(4) = x (4T_{\rm A})\hspace{0.05cm}.$$ 
*On the other hand, the coefficients&nbsp; $d(5)$,&nbsp; $d(6)$&nbsp; and&nbsp; d$(7)$&nbsp; are to be set as follows:

:$$d(\nu) = x \big ((\nu\hspace{-0.05cm} - \hspace{-0.05cm} N ) \cdot T_{\rm   A}\big )  $$

:$$ \Rightarrow \hspace{0.2cm}d(5) = x (-3T_{\rm A})\hspace{0.05cm}, \hspace{0.35cm}
d(6) = x (-2T_{\rm A})\hspace{0.05cm}, \hspace{0.35cm}
d(7) = x (-T_{\rm A})\hspace{0.05cm}.$$ }}



<br><br>

==Exercises==
<br>
[[File:Aufgaben_2D-Gauss.png|right]]
* First select the number (1,...) of the exercise. <br>
* A description of the exercise will be displayed.
*The parameter values are adjusted. <br>
*Solution after pressing "Show solution". <br>
*The number 0 corresponds to a "Reset":
:Same setting as at program start.
:Output of a "reset text" with further explanations about the applet.


{{BlaueBox|TEXT=
'''(1)'''&nbsp; New setting:&nbsp; DFT of signal&nbsp; $\rm (b)$:&nbsp; Constant signal.&nbsp; Interpret the result in the frequency domain.&nbsp; What is the analogon of the conventional Fourier transform?}}

:*&nbsp;All coefficients in the time domain are&nbsp; $d(\nu)=1$.&nbsp; Thus all&nbsp; $D(\mu)=0$&nbsp; with the exception of&nbsp; $\textrm{Re}[D(0)]=1$.  <br>
:*&nbsp;This corresponds to the conventional (time-continuous) Fourier Transform:&nbsp; $x(t)=A\hspace{0.15cm} \circ\!\!\!-\!\!\!-\!\!\!-\!\!\bullet\hspace{0.15cm} X(f)=A\cdot \delta (f=0)$&nbsp; with&nbsp; $A=1$.

{{BlaueBox|TEXT=
'''(2)'''&nbsp; Assume the obtained&nbsp; $D(\mu)$&nbsp; field and shift all coefficients one entry down.&nbsp; Which time function does the IDFT provide?
}}

:*&nbsp;Now all&nbsp; $D(\mu)=0$,&nbsp; except for&nbsp; $\textrm{Re}[D(1)]=1$.&nbsp; The result in the time domain is a complex exponential function.
:*&nbsp;The real part of  the&nbsp; $d(\nu)$&nbsp; field  shows a cosine and the imaginary part a sine function.&nbsp; For each function one can see one period respectively.

{{BlaueBox|TEXT=
'''(3)'''&nbsp; Add the following coefficient to the current&nbsp; $D(\mu)$ field:&nbsp; $\textrm{Im}[D(1)]=1$.&nbsp; What are the differences compared to&nbsp; '''(2)'''&nbsp; in the time domain?
&nbsp;}}
:*&nbsp;On the one hand, a phase shift of two support values can now be detected for the real and the imaginary parts.&nbsp; This corresponds to the phase&nbsp; $\varphi = 45^\circ$.
:*&nbsp;On the other hand, the amplitudes of the real and the imaginary part were each increased by the factor&nbsp; $\sqrt{2}$.

{{BlaueBox|TEXT=
'''(4)'''&nbsp; Set the&nbsp; $D(\mu)$ field&nbsp; to zero except for&nbsp; $\textrm{Re}[D(1)]=1$.&nbsp; Which additional&nbsp; $D(\mu)$&nbsp; coefficient yields a real&nbsp; $d(\nu)$&nbsp; field?
}}

:*&nbsp;By trial and error, one can see that&nbsp; $\textrm{Re}[D(15)]=1$&nbsp; must apply additionally.&nbsp; Then the&nbsp; $d(\nu)$&nbsp; field describes a cosine.
:*&nbsp;The following applies to the conventional (time continuous) Fourier Transform:&nbsp; $x(t)=2\cdot \cos(2\pi \cdot f_0 \cdot t)\hspace{0.15cm}\circ\!\!\!-\!\!\!-\!\!\!-\!\!\bullet\hspace{0.15cm}
X(f)=\delta (f-f_0)+\delta (f+f_0)$.
:*&nbsp;The entry&nbsp; $D(1)$&nbsp; is representative of the frequency&nbsp; $f_0$&nbsp; and due to the periodicity with&nbsp; $N=16$&nbsp; the frequency&nbsp; $-f_0$&nbsp; is expressed by&nbsp; $D(15)=D(-1)$. 

{{BlaueBox|TEXT=
'''(5)'''&nbsp; According to the IDFT in the&nbsp; $d(\nu)$&nbsp; field, by which&nbsp; $D(\mu)$&nbsp; field does one obtain a real cosine function  with the amplitude&nbsp; $A=1$?}}

:*&nbsp;Like the conventional Fourier transform the discrete Fourier Transform is linear&nbsp; &rArr; &nbsp;  $D(1)=D(15)=0.5$.

{{BlaueBox|TEXT=
'''(6)'''&nbsp; New setting:&nbsp; DFT of signal&nbsp; $\rm (e)$:&nbsp; Cosine signal and subsequent signal shifts.&nbsp; What are the effects of these shifts in the frequency domain?
}}

:*&nbsp;A shift in the time domain changes the cosine signal to a&nbsp; "harmonic oscillation"&nbsp; with arbitrary phase.
:*&nbsp;The&nbsp; $D(\mu)$&nbsp; field is still zero except for&nbsp; $D(1)$&nbsp; and&nbsp; $D(15)$.&nbsp; The absolute values&nbsp; $|D(1)|$&nbsp; and&nbsp; $|D(15)|$&nbsp; also remain the same.
:*&nbsp;The only change concerns the phase,&nbsp; i.e. the different distribution of the absolute values between the real and imaginary part. 

{{BlaueBox|TEXT=
'''(7)'''&nbsp; New setting:&nbsp; DFT of signal&nbsp; $\rm (f)$:&nbsp; Sinusoidal signal.&nbsp; Interpret the result in the frequency domain.&nbsp; What is the analogon of the conventional Fourier Transform?
}}

:*&nbsp;The sine signal results from the cosine signal by applying four time shifts.&nbsp; Therefore all statements of&nbsp; '''(6)'''&nbsp; are still valid.
:*&nbsp;For the conventional (time continuous) Fourier transform it holds that&nbsp; $x(t)= \sin(2\pi \cdot f_0 \cdot t)\hspace{0.15cm}\circ\!\!\!-\!\!\!-\!\!\!-\!\!\bullet\hspace{0.15cm}
X(f)=j/2 \cdot [\delta (f+f_0)-\delta (f-f_0)]$. 
:*&nbsp;The coefficient&nbsp; $D(1)$ &nbsp; $\Rightarrow$ &nbsp;$($frequency:&nbsp; $+f_0)$&nbsp; is imaginary and has the imaginary part&nbsp; $-0.5$.&nbsp; Accordingly,&nbsp; $\textrm{Im}[D(15)]=+0.5$ &nbsp; &rArr; &nbsp; $($frequency:&nbsp; $-f_0)$&nbsp; applies.

{{BlaueBox|TEXT=
'''(8)'''&nbsp; New setting:&nbsp; DFT of signal&nbsp; $\rm (g)$:&nbsp; Cosine signal (two periods).&nbsp; Interpret the result in comparison to exercise&nbsp; '''(5)'''.
}}

:*&nbsp;Here the time continuous Fourier transform reads&nbsp; $x(t)=\cos(2\pi \cdot (2 f_0) \cdot t)\hspace{0.15cm}\circ\!\!\!-\!\!\!-\!\!\!-\!\!\bullet\hspace{0.15cm}X(f)=0.5 \cdot \delta (f- 2 f_0)+0.5 \cdot \delta (f+ 2 f_0)$.
:*&nbsp;$D(2)$&nbsp; is representative of the frequency&nbsp; $2 f_0$.&nbsp; Due to the periodicity,&nbsp; $D(14)=D(-2)$: &nbsp; $D(2)=D(14)=0.5$ is representative of the frequency&nbsp; $-2 f_0$.

{{BlaueBox|TEXT=
'''(9)'''&nbsp; Now examine the case DFT of a sinodial signal (two periods).&nbsp; Which modifications do you need to make in the time domain?&nbsp; Interpret the result.
}}

:*&nbsp;The desired signal can be obtained from the DFT of signal&nbsp; $\rm (g)$:&nbsp; Cosine signal (two periods) with two shifts.&nbsp; With the result of&nbsp; '''(7)''':&nbsp; Four shifts. 
:*&nbsp;The DFT result is accordingly&nbsp; $\textrm{Im}[D(2)]=-0.5$&nbsp; and&nbsp; $\textrm{Im}[D(14)]=+0.5$.

{{BlaueBox|TEXT=
'''(10)'''&nbsp; New setting: DFT of signal&nbsp; $\rm (h)$:&nbsp; Alternating time coefficients.&nbsp; Interpret the DFT result.}}

:*&nbsp;Here, the time continuous Fourier transform is given by:&nbsp; $x(t)=\cos(2\pi \cdot (8 f_0) \cdot t)\hspace{0.15cm}\circ\!\!\!-\!\!\!-\!\!\!-\!\!\bullet\hspace{0.15cm}
X(f)=0.5 \cdot \delta (f- 8 f_0)+0.5 \cdot \delta (f+ 8 f_0)$.
:*&nbsp;$8 f_0$ is the highest frequency that can be displayed with&nbsp; $N=16$&nbsp; in the DFT.&nbsp; There are only two sampled values per period, namely $+1$ and $-1$.
:*&nbsp;Difference to exercise&nbsp; '''(5)''':&nbsp; $D(1)=0.5$&nbsp; now becomes&nbsp; $D(8)=0.5$.&nbsp; Likewise,&nbsp; $D(15)=0.5$&nbsp; is shifted to&nbsp; $D(8)=0.5$.&nbsp; Final result:&nbsp; $D(8)=1$.

{{BlaueBox|TEXT=
'''(11)'''&nbsp; What are the differences between the two settings DFT from signal&nbsp; $\rm (i)$:&nbsp; Dirac delta impulse  and &nbsp;  IDFT from spectrum&nbsp; $\rm (I)$:&nbsp; Dirac delta spectrum?
}}

:*&nbsp;None! In the first case, all coefficients are&nbsp; $D(\mu)=1$ (real);&nbsp; in the second case, however, equivalently&nbsp; $d(\nu)=1$ (real).

{{BlaueBox|TEXT=
'''(12)'''&nbsp; Are there differences in shifting the real&nbsp; "$1$"&nbsp; in the according input fields by one place at a time, that is for&nbsp; $d(\nu = 1)=1$&nbsp; and&nbsp; $D(\mu = 1)=1$?
}}

:*&nbsp;The first case &nbsp;$\Rightarrow$&nbsp; $\textrm{Re}[d(\nu = 1)]=1$&nbsp; results in the complex exponential function in the frequency domain given by&nbsp; $X(f)= \textrm{e}^{-{\rm j}\hspace{0.05cm}\cdot\hspace{0.05cm} 2 \pi\hspace{0.05cm}\cdot\hspace{0.05cm} f/f_0}$&nbsp; with negative sign.
:*&nbsp;The second case&nbsp; $\Rightarrow$&nbsp; $\textrm{Re}[D(\mu = 1)]=1$ results in the complex exponential function in the time domain given by&nbsp;  $x(t)= \textrm{e}^{+{\rm j}\hspace{0.05cm}\cdot\hspace{0.05cm} 2 \pi\hspace{0.05cm}\cdot\hspace{0.05cm} f_0\cdot t}$&nbsp; with positive sign.
:*&nbsp;<i>Note:</i>&nbsp; With&nbsp; $\textrm{Re}[D(\mu=15)]=1$&nbsp; the result in the time domain would also be a complex exponential function&nbsp;  $x(t)= \textrm{e}^{-{\rm j}\hspace{0.05cm}\cdot\hspace{0.05cm} 2 \pi\hspace{0.05cm}\cdot\hspace{0.05cm} f_0\hspace{0.05cm}\cdot\hspace{0.05cm} t}$ with negative sign.

{{BlaueBox|TEXT=
'''(13)'''&nbsp; New setting: DFT of signal&nbsp; $\rm (k)$:&nbsp; Triangle pulse.&nbsp; Interpret the&nbsp; $d(\nu)$&nbsp; assignment under the assumption&nbsp; $T_\textrm{A} = 1$ ms.}}

:*&nbsp;Change the display to "absolute value".&nbsp; $x(t)$ is symmetrical around&nbsp; $t=0$&nbsp; and extends from&nbsp; $-8 \cdot T_\textrm{A} = -8$&nbsp; ms to&nbsp; $+8 \cdot T_\textrm{A}= +8$&nbsp; ms. 
:*&nbsp;$d(\nu)$&nbsp; assignment:&nbsp; $d(0)=x(0)=1$,&nbsp; $d(1)=x(T_\textrm{A})=0.875$, ... ,&nbsp; $d(8)=x(8 T_\textrm{A})=0$,&nbsp; $d(9)=x(-7 T_\textrm{A})=0.125$, ... ,&nbsp; $d(15)=x(-T_\textrm{A})=0.875$.

{{BlaueBox|TEXT=
'''(14)'''&nbsp; Same setting as&nbsp;  '''(13)'''.&nbsp; Interpret the DFT result, especially the coefficients&nbsp; $D(0)$,&nbsp; $D(1)$,&nbsp; $D(2)$&nbsp; and&nbsp; $D(15)$.}}

:* In the frequency range&nbsp; $D(0)$&nbsp; stands for the frequency&nbsp; $f=0$&nbsp; and&nbsp; $D(1)$&nbsp; and&nbsp; $D(15)$&nbsp; for the frequencies&nbsp; $\pm f_\textrm{A}$.&nbsp; It holds that&nbsp; $f_\textrm{A}= 1/ (N\cdot T_\textrm{A})=62.5$&nbsp; Hz.
:* For the value of the continuous spectrum at $f=0$ the following applies: &nbsp; $X(f=0)=D(0)/f_\textrm{A} = 0.5/ (0.0625$ kHz$)=8\cdot \textrm{kHz}^{-1}$.
:* The first zero of the&nbsp; $\textrm{si}^2$&ndash;shaped spectrum&nbsp; $X(f)$&nbsp; occurs at&nbsp; $2\cdot f_\textrm{A} = 125$ Hz.&nbsp; The other zeros are equidistant.

{{BlaueBox|TEXT=
'''(15)'''&nbsp; New setting: DFT of signal&nbsp; $\rm (i)$:&nbsp; Rectangular pulse.&nbsp; Interpret the displayed results.}}
:*&nbsp;The set (symmetrical) rectangle extends over&nbsp; $\pm 4 \cdot T_\textrm{A}$.&nbsp; At the edges, the time coefficients are only half as large:&nbsp; $d(4)=d(12)=0.5$.
:* The further statements of&nbsp; '''(14)'''&nbsp; also apply to this&nbsp; $\textrm{si}$&ndash;shaped spectrum&nbsp; $X(f)$.

{{BlaueBox|TEXT=
'''(16)'''&nbsp; Same setting as for&nbsp;  '''(15)'''.&nbsp; Which modifications need to be made in the&nbsp; $d(\nu)$&nbsp; field,
to have the duration of the rectangle &nbsp; $\Rightarrow$ &nbsp; $\pm 2 \cdot T_\textrm{A}$.
}}
:*&nbsp;$d(0) = d(1) = d(15) =1, \ d(2) = d(14) = 0.5$. All other time coefficients zero&nbsp; &rArr; &nbsp; first zero of the &nbsp;${\rm si}$ spectrum at &nbsp;$4 \cdot f_{\rm A}= 250\text{ Hz}$.

{{BlaueBox|TEXT=
'''(17)'''&nbsp; New setting:&nbsp;  IDFT of spectrum&nbsp; $\rm (L)$:&nbsp; Gaussian spectrum.&nbsp; Interpret the result in the time domain.}}
:*&nbsp;Here, the time function&nbsp; $x(t)$&nbsp; is Gaussian with the maximum&nbsp; $x(t=0)=4$.&nbsp; For the spectrum the following applies:&nbsp; $X(f=0)=D(0)/f_\textrm{A} = 16 \cdot \textrm{kHz}^{-1}$.
:*&nbsp;The equivalent duration of the pulse  is&nbsp; $\Delta t = X(f=0)/x(t=0)=4\text{ ms}$.&nbsp; The inverse value gives the equivalent bandwidth&nbsp; $\Delta f = 1/\Delta t = 250\text{ Hz}$.







==Applet Manual==
<br>
[[File:Anleitung_DFT_endgültig.png|left|600px|frame|Screenshot of the German version]]
&nbsp; &nbsp; '''(A)''' &nbsp; &nbsp; Time domain (input and result field) 

&nbsp; &nbsp; '''(B)''' &nbsp; &nbsp; '''(A)''' representation numerical, graphical, magnitude

&nbsp; &nbsp; '''(C)''' &nbsp; &nbsp; frequency domain (input and result field)

&nbsp; &nbsp; '''(D)''' &nbsp; &nbsp; '''(C)''' representation numerical, graphical, magnitude

&nbsp; &nbsp; '''(E)''' &nbsp; &nbsp; Selection: DFT &nbsp;$(t \to f)$&nbsp; or IDFT &nbsp;$(f \to t)$

&nbsp; &nbsp; '''(F)''' &nbsp; &nbsp; Given &nbsp;$d(\nu)$ assignments (if DFT), or

&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  &nbsp; &nbsp; Given &nbsp;$D(\mu)$ assignments (if IDFT)

&nbsp; &nbsp; '''(G)''' &nbsp; &nbsp; Set input field to zero

&nbsp; &nbsp; '''(H)''' &nbsp; &nbsp; Move input field cyclically down (or up)

&nbsp; &nbsp; '''( I )''' &nbsp; &nbsp; Range for experiment execution: &nbsp;  exercise selection  

&nbsp; &nbsp; '''(J)''' &nbsp; &nbsp; Range for experiment execution: &nbsp;  exercise definition

&nbsp; &nbsp; '''(K)''' &nbsp; &nbsp; Range for experiment execution: &nbsp;  show sample solution
<br clear=all>
*Given  &nbsp;$d(\nu)$ assignments (for DFT):

:(a)&nbsp; corresponding number field,&nbsp; (b)&nbsp; DC signal,&nbsp; (c)&nbsp;  Complex exponential function of time,&nbsp; (d)&nbsp;  Harmonic oscillation &nbsp;$($phase &nbsp;$\varphi = 45^\circ)$,
:(e)&nbsp; Cosine signal (one period),&nbsp; (f)&nbsp; Sine signal (one period),&nbsp; (g)&nbsp;  Cosine signal (two periods),&nbsp;(h)&nbsp;  Alternating time coefficients,  
:&nbsp; (i)&nbsp; Dirac delta pulse,&nbsp; (j)&nbsp; Rectangular pulse,&nbsp; (k)&nbsp;  Triangular pulse,&nbsp; (l)&nbsp;  Gaussian pulse.

*Given &nbsp;$D(\mu)$ assignments (for IDFT):

:(A)&nbsp; corresponding number field,&nbsp; (B)&nbsp; Constant spectrum,&nbsp; (C)&nbsp;  Complex exponential function of frequency,&nbsp; (D)&nbsp;  equivalent to setting (d) in time domain ,
:(E)&nbsp; Cosine signal (one frequency period),&nbsp; (F)&nbsp; Sine signal (one frequency period),&nbsp; (G)&nbsp;  Cosine signal (two frequency periods),&nbsp; (H)&nbsp;  Alternating spectral coefficients,
:(I)&nbsp; Dirac delta spectrum,&nbsp; (J)&nbsp; Rectangular spectrum,&nbsp; (K)&nbsp;  Triangular spectrum,&nbsp; (L)&nbsp;  Gaussian spectrum.   


==About the Authors==

This interactive calculation tool was designed and implemented at the&nbsp; [https://www.ei.tum.de/en/lnt/home/ Institute for Communications Engineering]&nbsp; at the&nbsp; [https://www.tum.de/en Technical University of Munich]. 
*The first version was created in 2008 by [[Biografien_und_Bibliografien/An_LNTwww_beteiligte_Studierende#Thomas_Gro.C3.9Fer_.28Diplomarbeit_LB_2006.2C_danach_freie_Mitarbeit_bis_2010.29|&raquo;Thomas Großer&laquo;]]&nbsp; as part of his diploma thesis with “FlashMX – Actionscript” (Supervisor: [[Biographies_and_Bibliographies/An_LNTwww_beteiligte_Mitarbeiter_und_Dozenten#Prof._Dr.-Ing._habil._G.C3.BCnter_S.C3.B6der_.28am_LNT_seit_1974.29|Günter Söder]]). 

*Last revision and English version 2020/2021 by&nbsp; [[Biografien_und_Bibliografien/An_LNTwww_beteiligte_Studierende#Carolin_Mirschina_.28Ingenieurspraxis_Math_2019.2C_danach_Werkstudentin.29|&raquo;Carolin Mirschina&laquo;]]&nbsp; in the context of a working student activity.&nbsp; 


The conversion of this applet to HTML 5 was financially supported by&nbsp; [https://www.ei.tum.de/studium/studienzuschuesse/ Studienzuschüsse]&nbsp; ("study grants") of the TUM Faculty EI. We thank them.



==Once again: Open Applet in new Tab==

{{LntAppletLinkEnDe|dft_en|dft}}