View source for Signal Representation/Possible Errors when using DFT

 
{{Header
|Untermenü=Time and Frequency-Discrete Signal Representation
|Vorherige Seite=Discrete Fourier Transform (DFT)
|Nächste Seite=Spectrum Analysis
}}

==The mean square error as a quality criteria==
<br>
In the following,&nbsp; we briefly discuss some error possibilities when applying the DFT,&nbsp; whereby we restrict ourselves to the transformation from the time to the frequency domain.&nbsp; Even in its samples,&nbsp; the spectrum&nbsp; $D(\mu )/f_{\rm A}$&nbsp; determined via the DFT will generally differ from the actual spectrum&nbsp; $X(\mu \cdot f_{\rm A})$&nbsp; due to two processes:
*the&nbsp; &raquo;sampling&laquo;,&nbsp; that is,&nbsp; the reduction of information about&nbsp; $x(t)$&nbsp; to&nbsp; $N$&nbsp; numerical values,

*the&nbsp; &raquo;windowing&raquo; that may falsely limit the signal&nbsp; $x(t)$.


{{BlaueBox|TEXT=
$\text{Definition:}$&nbsp;
A quality criteria that takes both error types into account is the&nbsp; &raquo;'''mean square error'''&laquo;&nbsp; $($German:&nbsp; "mittlerer quadratischer Fehler" &nbsp; &rArr; &nbsp;$\rm MQF)$:
 
:$${\rm MQF} =  \frac{1}{N}\cdot \sum_{\mu = 0 }^{N-1}
 \left\vert X(\mu \cdot f_{\rm A})-\frac{D(\mu)}{f_{\rm A} }\right \vert^2 \hspace{0.05cm}.$$

It is always&nbsp; ${\rm MQF} \ne 0$,&nbsp; since with finite&nbsp; $N$&nbsp; the degradation due to sampling and due to windowing cannot be made zero at the same time.}} 


The magnitude of this evaluation quantity&nbsp; ${\rm MQF}$&nbsp; depends on the following parameters:
#The properties of the present signal&nbsp; $x(t)$&nbsp; and of its spectrum&nbsp; $X(f)$,
#the DFT parameter&nbsp; $N$; &nbsp; the larger&nbsp; $N$&nbsp; is chosen,&nbsp; the smaller&nbsp; ${\rm MQF}$&nbsp; becomes,
#one of the four further DFT parameters,&nbsp; e.g.&nbsp; $f_{\rm A}$. 


For a given&nbsp; $N$&nbsp; the other DFT parameters are determined via the equations&nbsp; 
:$$f_{\rm P} = N \cdot f_{\rm A},$$
:$$T_{\rm P} = 1/f_{\rm A},$$
:$$T_{\rm A} = T_{\rm P}/N.$$

We refer you already here to the following&nbsp; $($German language$)$&nbsp; learning video,&nbsp; which clarifies the content of this chapter:<br>&nbsp; &nbsp; [[Fehlermöglichkeiten_bei_Anwendung_der_DFT_(Lernvideo)|&raquo;Fehlermöglichkeiten bei Anwendung der DFT&laquo;]] &nbsp; &rArr; &nbsp; "Possible errors when using the DFT".

{{GraueBox|TEXT=
$\text{Example 1:}$&nbsp;
As an example,&nbsp; we consider a Gaussian pulse with equivalent pulse duration&nbsp; $\Delta t = T$,&nbsp; where&nbsp; $T$&nbsp; is simultaneously used as a normalization parameter:
[[File:EN_Sig_T_5_1_S1.png|right|frame|Quasi error-free DFT  with &nbsp; $N = 16$; &nbsp; &nbsp; ${\rm MQF}$: &nbsp; mean square error &nbsp; &nbsp; <u>Note:</u><br>The given&nbsp; $\text{MQF}$ values apply to a&nbsp; 16 bit processor.&nbsp; For a 32 bit processor&nbsp; $($smaller quantization errors of the computer$)$&nbsp; $\text{MQF}$&nbsp; would be even smaller,&nbsp; but never zero.]]
 
:$$x(t) = {\rm e}^{- \pi (t/T)^2} \hspace{0.05cm}.$$

The Gaussian pulse is very suitable for the application of the  DFT due to its fast&nbsp; $($exponential$)$&nbsp; decay in both time and frequency domain. 

The graph below shows the DFT result
*for&nbsp; $N = 16$&nbsp; and 
*$T_{\rm A}/T = 0.25$ &nbsp; &rArr; &nbsp; $f_{\rm A} \cdot T = 0.25$ &nbsp; &rArr; &nbsp; $T_{\rm P}/T = 4$.


The following should be noted about this plot:
#The considered samples of&nbsp; $x(t)$&nbsp; are in the range&nbsp; $\vert t/T \vert≤ 2$.&nbsp; Since&nbsp; $x(\pm 2T)$&nbsp; is very small,&nbsp; periodization in time domain with&nbsp; $T_{\rm P}/T = N \cdot T_{\rm A}/T = 4$&nbsp; does not lead to serious errors.
#With&nbsp; $f_{\rm A} \cdot T = 0.25$&nbsp; and&nbsp; $N = 16$&nbsp; the&nbsp; $($normalized$)$&nbsp; DFT parameter is&nbsp; $f_{\rm P} \cdot T = 4$.&nbsp; The discrete spectral lines thus lie in the range&nbsp; $-2/T ≤ f < +2/T$.
#The mean squared error is relatively small&nbsp; $\text{(MQF} \approx 10^{-12})$,&nbsp; which is due to the favourable choice of&nbsp; $f_{\rm A} \cdot T = 0.25$&nbsp; $($for the given&nbsp; $N = 16)$&nbsp;.
#The DFT accuracy can be improved by increasing&nbsp; $N$&nbsp;: 
#For&nbsp; $N = 1024$&nbsp; the minimum value&nbsp; $\text{MQF} \approx 8 \cdot 10^{-17}$&nbsp;  is obtained,&nbsp; if&nbsp; $f_{\rm A} \cdot T = 0.125$&nbsp; is chosen. 
#The following then applies to the other DFT parameters:
:: $$f_{\rm P} \cdot T = 128, \hspace{0.5cm}T_{\rm A}/T = 1/128, \hspace{0.5cm} T_{\rm P}/T = N \cdot T_{\rm A}/T= 8.$$ }}


==DFT falsification due to windowing &ndash; Truncation error==
<br>
A typical error when using the DFT is due to&nbsp; &raquo;windowing&laquo;.&nbsp; This falsification, known&nbsp; as&nbsp; &raquo;'''truncation error'''&laquo;&nbsp; can be explained as follows:
#The windowing implicit in the DFT algorithm corresponds to the multiplication of the signal&nbsp; $x(t)$&nbsp; by&nbsp; a rectangular function of height&nbsp; $1$&nbsp; and duration&nbsp; $T_{\rm P} = N \cdot T_{\rm A}$.
#If the signal&nbsp; $x(t)$&nbsp; is not limited to the range&nbsp; $T_{\rm P}$&nbsp; the DFT result does not coincide with the actual spectrum&nbsp; $X(f)$&nbsp; but is obtained from it by convolution with the spectral function&nbsp; $T_{\rm P} \cdot \text{sinc}(f\cdot T_{\rm P})$.
#In the limiting case&nbsp; $T_{\rm P} \to \infty$,&nbsp; which for a given distance&nbsp; $T_{\rm A}$&nbsp; of the samples would also mean an infinitely large number&nbsp; $N$&nbsp; of interpolation points,&nbsp; $T_{\rm P} \cdot \text{sinc}(f\cdot T_{\rm P})$ degenerates&nbsp; to a Dirac delta function and the original spectrum&nbsp; $X(f)$&nbsp; would remain.
#The DFT of an unlimited signal in time &ndash; for example a periodic signal &ndash; will always cause a truncation error which can only be kept within limits by special measures.&nbsp; This is discussed in more detail in the chapter&nbsp; [[Signal_Representation/Spectrum_Analysis|&raquo;Spectrum Analysis&laquo;]].
#For time-limited signals &nbsp; &rArr; &nbsp; &raquo;pulses&laquo;,&nbsp; the truncation error can be avoided by choosing&nbsp; $T_{\rm P}$&nbsp; sufficiently large.&nbsp; By further enlarging the window into areas with&nbsp; $x(t) \equiv 0$&nbsp; no additional information gain results &nbsp; ⇒ &nbsp; $\text{MQF}$&nbsp; does not become smaller.
#By this addition of zeros called&nbsp; &raquo;'''zero-padding'''&laquo;&nbsp; the&nbsp; $X(f)$&nbsp; samples now occur at a smaller distance&nbsp; $f_{\rm A} = 1/T_{\rm A}$.&nbsp; By doubling&nbsp; $T_{\rm P}$&nbsp; one achieves an interpolation of the frequency samples exactly in the middle between two previous grid points.


The following example shows a&nbsp; &raquo;truncation error&laquo;&nbsp; due to unfavourably chosen DFT parameters.&nbsp; Again,&nbsp; we refer to the learning video&nbsp; $($in German language$)$&nbsp; <br>&nbsp; &nbsp; [[Fehlermöglichkeiten_bei_Anwendung_der_DFT_(Lernvideo)|&raquo;Fehlermöglichkeiten bei Anwendung der DFT&laquo;]] &nbsp; &rArr; &nbsp; "Possible errors when using the DFT".

{{GraueBox|TEXT=
$\text{Example 2:}$&nbsp;
The graph shows the DFT result for the same&nbsp; $x(t)$&nbsp; and&nbsp; $X(f)$&nbsp; as well as the same&nbsp; $N = 16$&nbsp; as in&nbsp; [[Signal_Representation/Possible_Errors_when_using_DFT#The_mean_square_error_as_a_quality_criteria|$\text{Example 1}$]],&nbsp; but now with finer sampling in the time domain by a factor of&nbsp; $2$ &nbsp; &rArr; &nbsp; $T_{\rm A}/T = 0.125$
[[File:EN_Sig_T_5_1_S2.png|right|frame|Truncation error for a DFT with&nbsp; $N = 16$; &nbsp; &nbsp; ${\rm MQF}$: &nbsp; Mean square error]]
 
The comparison with&nbsp; [[Signal_Representation/Possible_Errors_when_using_DFT#The_mean_square_error_as_a_quality_criteria|$\text{Example 1}$]]&nbsp; shows:
*The spacing of the frequency samples increases from&nbsp; $f_{\rm A} \cdot T = 0.25$&nbsp; to&nbsp; $f_{\rm A} \cdot T = 0.5$ .

*At the same time,&nbsp; $T_{\rm P}/T$&nbsp; decreases from&nbsp; $4$&nbsp; to&nbsp; $2$.

*With this,&nbsp; only the signal components in the range&nbsp; $\vert t \vert < T$&nbsp; are now captured by the DFT.




&rArr; &nbsp; With these parameters,&nbsp; a&nbsp; &raquo;truncation error&laquo; or&nbsp; &raquo;termination error&laquo; arises,&nbsp; by which the mean square error&nbsp; is significantly increased from&nbsp; $\rm MQF= 10^{-12}$&nbsp; to&nbsp; $\rm MQF= 4 \cdot 10^{-5}$. 
 }}



==DFT falsification due to sampling &ndash; Aliasing error==
<br>

An unsuitable sampling of the time function&nbsp; $x(t)$&nbsp; can also significantly falsify the DFT result.&nbsp; This so-called&nbsp; &raquo;'''aliasing error'''&laquo;&nbsp; can be explained as follows:
*Sampling&nbsp; $x(t)$&nbsp; at a distance&nbsp; $T_{\rm A}$&nbsp; causes a periodic continuation of the spectrum at multiples of the periodization frequency&nbsp; $f_{\rm P} = 1/T_{\rm A}$.

*If&nbsp; $X(f)$&nbsp; has spectral components at&nbsp; $|f| > f_{\rm P}/2$,&nbsp; the sampling theorem is not fulfilled and overlaps of the shifted frequency components to be added occur.

*Only with a band-limited signal the aliasing error can be avoided by suitable DFT parameters.&nbsp; In contrast,&nbsp; this error is unavoidable with time-limited signals &nbsp; &rArr; &nbsp; &raquo;pulses&laquo;,&nbsp; since time-limited signals cannot be band-limited at the same time.

*The aliasing error is reduced by finer sampling&nbsp; $($smaller&nbsp; $T_{\rm A} = 1/f_{\rm P})$.&nbsp; This can only be achieved with a constant&nbsp; $T_{\rm A}$&nbsp; &ndash; in order not to let the truncation error increase &ndash; by a larger&nbsp; $N$&nbsp; and thus a greater computational effort.


The following&nbsp; $\text{Example 3}$&nbsp; shows such an aliasing error due to wrongly chosen DFT parameters: 
*Compared to the&nbsp; comparison system&nbsp; according to&nbsp; [[Signal_Representation/Possible_Errors_when_using_DFT#The_mean_square_error_as_a_quality_criteria|$\text{Example 1}$]]: &nbsp; &nbsp;   $T_{\rm A}$&nbsp; is too large and&nbsp; $f_{\rm A}$&nbsp; is too small dimensioned.
 
*The number of interpolation points is in both cases:&nbsp; $N = 16$.


{{GraueBox|TEXT=
$\text{Example 3:}$&nbsp;
Let the DFT parameters be&nbsp; $N = 16$&nbsp; and&nbsp; $f_{\rm A} \cdot T= 0.125$. Thus,&nbsp;  we get for the other three DFT parameters:
[[File:EN_Sig_T_5_1_S3._neu.png|right|frame|Aliasing error of a DFT with&nbsp; $N = 16$; &nbsp; &nbsp; ${\rm MQF}$: &nbsp; mean square error]]
* $T_{\rm P}/T = 8 \hspace{0.8cm} \text{(Example 1:} \ \ T_{\rm P}/T = 4)$,
* $f_{\rm P} \cdot T = 2 \hspace{0.75cm} \text{(Example 1:} \ \ f_{\rm P} \cdot T = 4)$,
* $T_{\rm A}/T = 0.5\hspace{0.45cm} \text{(Example 1:} \ \ T_{\rm A}/T = 0.25)$.


This results in the following consequences:
#The truncation error continues to play no role because of&nbsp; $T_{\rm P} /T = 8$&nbsp; $($already&nbsp; $T_{\rm P} /T = 4$&nbsp; was sufficient$)$.
#However,&nbsp; aliasing now arises,&nbsp; because the DFT is derived from many Gaussian functions at distance&nbsp; $f_{\rm P}  \cdot T = 2$&nbsp; $($thin dashed curves in the graph$)$. 
#The DFT coefficients are falsified differently: &nbsp; The mean DFT coefficient&nbsp; $($for&nbsp; $f = 0)$&nbsp; is almost correct, while the errors of the DFT coefficients increase significantly towards the edges.
#Here,&nbsp; the DFT coefficient for&nbsp; $f \cdot T = -1$&nbsp; is twice as large as it should be,&nbsp; since the Gaussian function with the center at&nbsp; $f \cdot T = -2$&nbsp; gives the same contribution as the Gaussian function around&nbsp; $f \cdot T = 0$&nbsp; (see yellow background).


Thus,&nbsp; here with&nbsp; $\text{MQF} \approx 2 \cdot 10^{-4}$&nbsp; an error value four times larger than that caused by the truncation error in&nbsp; [[Signal_Representation/Possible_Errors_when_using_DFT#DFT_falsification_due_to_windowing_.E2.80.93_Truncation_error|$\text{Example 2}$]]. 

Again,&nbsp; we refer to the&nbsp; $($German language$)$&nbsp; learning video:<br> &nbsp; &nbsp;[[Fehlermöglichkeiten_bei_Anwendung_der_DFT_(Lernvideo)|&raquo;Fehlermöglichkeiten bei Anwendung der DFT&laquo;]] &nbsp; &rArr; &nbsp; "Possible errors when using the DFT". }}


==Exercises for the chapter== 
<br>
[[Aufgaben:Exercise 5.3: Mean Square Error|Exercise 5.3: Mean Square Error]]

[[Aufgaben:Exercise 5.3Z: Zero-Padding|Exercise 5.3Z: Zero-Padding]]


{{Display}}