6
$\begingroup$

I'm someone just learning DSP, and want understand its essence. My transform is the simplest possible. Input signal is just one frequency: $256\textrm{ Hz}$. Sampling frequency is $2560\textrm{ samples/sec}$, so $10\textrm{ samples}$ correspond to one cycle (period). I correlate it with two testing frequencies: one equal to input and other double of it: $2\cdot 256\textrm{ Hz} = 512\textrm{ Hz}$. I correlate only $10\textrm{ samples}$ so correlation is not moving.

  • 1st correlation: Input samples are in first column and testing frequency's (equal) in second:

     0              x  0              = 0
     0.587785252292 x  0.587785252292 = 0.345491502812
     0.951056516295 x  0.951056516295 = 0.904508497187
     0.951056516295 x  0.951056516295 = 0.904508497187
     0.587785252292 x  0.587785252292 = 0.345491502812
     0              x  0              = 0
    -0.587785252292 x -0.587785252292 = 0.345491502812
    -0.951056516295 x -0.951056516295 = 0.904508497187
    -0.951056516295 x -0.951056516295 = 0.904508497187
    -0.587785252292 x -0.587785252292 = 0.345491502812
            Sum of products (squares) = 5
    
    Because square of every real number is positive, sum is big number. Divided by $10$ yields $0.5$. Given that it is mean of products of sines is significant number, so I conclude frequency $256\textrm{ Hz}$ does exist in the signal.

  • 2nd correlation. Input samples are in first column and testing frequency's in second:

     0              x  0              =  0
     0.587785252292 x  0.951056516295 =  0.559016994374
     0.951056516295 x  0.587785252292 =  0.559016994374
     0.951056516295 x -0.587785252292 = -0.559016994374
     0.587785252292 x -0.951056516295 = -0.559016994374
     0              x  0              =  0
    -0.587785252292 x  0.951056516295 = -0.559016994374
    -0.951056516295 x  0.587785252292 = -0.559016994374
    -0.951056516295 x -0.587785252292 =  0.559016994374
    -0.587785252292 x -0.951056516295 =  0.559016994374
                      Sum of products =  0
    
    Because half products are opposed to other half, sum is $0$. It means frequency $512\textrm{ Hz}$ does not exist in the signal.

My question: is that the essence of DFT?

$\endgroup$
  • 2
    $\begingroup$ In addition to the excellent answers provided so far, please note that this "pattern" of multiply-with-something-and-integrate is the "essence" of all integral transforms. Furthermore, you really need to lookup this complex exponential Matt.L talks about as well as even and odd functions because that's the reason behind certain sums working out as zero. Not only on the DFT. $\endgroup$ – A_A Jun 16 '16 at 18:21
5
$\begingroup$

I think you could say that in simple terms this is the essence of the DFT. Just note that the DFT correlates against complex exponentials:

$$X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2\pi nk/N}\tag{1}$$

You've just computed the (negative) imaginary part of $(1)$ (for $k=2$):

$$-X_I[k]=\sum_{n=0}^{N-1}x[n]\sin(2\pi nk/N)\tag{2}$$

For your example that's also sufficient because the real part is zero since your signal $x[n]$ is one full period of a sine wave. However, imagine you added a phase to your signal, then you would also need the real part of $(1)$. In the worst case you could choose a cosine for $x[n]$, which would give you a correlation of zero, even for the same frequency, if you just correlated with sine functions as in $(2)$.

$\endgroup$
  • $\begingroup$ Mr Matt L. as I have written in my question am just learning DSP, and want understand its essence. When I study complex exponential notation I study your suggestion. Regards. $\endgroup$ – George Theodosiou Jun 16 '16 at 14:48
  • $\begingroup$ Mr Matt L., you state: "You've just computed the (negative) imaginary part of (1) (for k=2)". Indeed you can consider any real number as imaginary part of complex numbers. However, real numbers properties are very different than complex's. For example, magnitude of complex number is the positive square root of the sum of squares of real and imaginary parts. Magnitude of real number is itself except sign. Similar is the difference between my poor transform and discrete Fourier transform. Regards. $\endgroup$ – George Theodosiou Aug 29 '16 at 6:41
  • $\begingroup$ @GeorgeTheodosiou: Compute the DFT and then evaluate its imaginary part for $k=2$, and you'll see that you get exactly the value of "your" transform (apart from the sign). This is all I said, and it's still true. $\endgroup$ – Matt L. Aug 29 '16 at 7:01
  • $\begingroup$ Mr. Matt. L., Important difference between my poor transform and discrete Fourier transform, is that mine works only on real zero-phased sinusoids. For this is impractical. However is of same essence with DFT as you, Mr Fat32 and mr A_A assert. I point out that nobody answered negative. Your suggestion prerequisites knowledge of DFT, while implementing my transform does not. Regards. $\endgroup$ – George Theodosiou Aug 29 '16 at 8:50
  • $\begingroup$ Mr Matt. L., please let me say you: yes this is all you said, and it's still true, but question is what you mean. Clear you mean that my transform is some special case of DFT. It is not, for, Fourier tranform is signal's correlation with cos(x)+isin(x), and nothing else. Regards. $\endgroup$ – George Theodosiou Aug 30 '16 at 8:25
2
$\begingroup$

Even though your understanding of the essence of the DFT as the: " ...process of computing correlations among a given sampled signal $x[n]$ and a set of (harmonic) family of test signals $e^{j\frac{2\pi}{N}kn}$... " , is true, your interpretation of its results may be slightly incomplete...

That's to say: when a DFT computation at a frequency of, say $256\textrm{ Hz}$ for your example, is nonzero, it does not mean that there is a pure sine wave at that frequency inside the signal being analyzed.

In order to clarify this, think about the following: There is a true spectrum of a sampled signal $x[n]$ (which we call DTFT - Discrete Time Fourier Transform): $$ X(e^{j\omega}) = \sum_{n=-\infty}^{\infty}{x[n]e^{-j\omega n}}$$

and there is the computed spectrum of the same (but taken as finite length of $N$) signal (which we call DFT - Discrete Fourier Transform). $$ X[k] = \sum_{n=0}^{N-1}{x[n]e^{-j\frac{2\pi}{N}kn}}$$

And as apparent: this computed spectrum, the DFT $X[k]$, is the samples of the true spectrum DTFT, $X(e^{j\omega})$, which itself is a continuous function in frequency domain (and therefore cannot in principle be represented inside any computer system)

And therefore as a result of this sampling of the true spectrum and windowing from infinite length to a finite length, some misinterpretations are possible.

As an example look at the following Matlab code:

Fs = 8000;              % sampling frequency, in Hz.
Ts = 1/Fs;              % sampling period Ts = 1/Fs.
M  = 128;               % number of signal samples to be obtained
N  = 1024;              % DFT analysis length (i.e. N-Point DFT applied)
n  = [0:M-1];           % sequence indice for x[n]
tn  = n*Ts;             % analog sampling times for xc(t)
fx  = 30*(Fs/N);        % analog signal frequency
x  = cos(2*pi*fx*tn);   % discrete time sampled signal x[n]

Now with the first value of $M=128$ and $N=1024$ one gets the following two plots of the sampled signal $x[n]$ and its DFT $X[k]$ magnitude: 128 samples of the analog signal plotted. enter image description here

and the corresponding DFT magnitude:: enter image description here

And for $M=1024$ (the same of $N$) shows first 128 samples of the longer signal: enter image description here

and the new spectrum now is: enter image description here

Looking at these plots for the same signal, sampled at the same rate, but with different durations, we clearly see the effect of windowing and assumed periodicity of DFT. For simplicity as you can see in the first spectrum there are nonzero samples of DFT which do not correspond to the signal being analyzed. And in fact those nonzero spectral samples are forced to be zero, in the second DFT plot, by a proper choice of signal duration and analysis window length. In fact in the second DFT plot, there is only one nonzero sample which is exactly at the signal frequency.

$\endgroup$
  • $\begingroup$ Mr Fat32, as long I understand sampling, when continuous spectra includes frequency lower than Nyquist's, it should be included in digital spectra too, and be detected by DFT, when equal freq. is testing. Regards. $\endgroup$ – George Theodosiou Jun 16 '16 at 14:25
  • $\begingroup$ Also please clarify first complex exponential notation for at the end there is " symbol. Thanks. $\endgroup$ – George Theodosiou Jun 16 '16 at 14:42
  • $\begingroup$ @GeorgeTheodosiou I'm now adding an example for possible misinterpretations... $\endgroup$ – Fat32 Jun 16 '16 at 15:04
  • $\begingroup$ Mr Fat32, I study DSP mainly from Mr Lyons book "understanding DSP" and up to now I have studied up to included section "3.1 UNDERSTANDING THE DFT EQUATION" and I just looking for the essence of DFT. So I hope later on be able understand your information as well Mr Matt L.'s. Regards. $\endgroup$ – George Theodosiou Jun 17 '16 at 7:27
  • $\begingroup$ @GeorgeTheodosiou That's a great book to learn DSP...Good Luck. $\endgroup$ – Fat32 Jun 17 '16 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.