0
$\begingroup$

I have been reading chapter 8 - The Discrete Fourier Transform of the book The Scientist and Engineer's Guide to Digital Signal Processing and chapter 12 - Discrete Fourier transform of the book Continuous and Discrete Time Signals and Systems. I'm not sure if I have understood real DFT properly.

From what I understood, in real DFT, if the samples in time domain have size $N$, then the output is consist of $\frac{N}{2} + 1$ complex number. Denote the output as X[ ], then Re X[ ] (real part of the complex numbers) is a list of amplitudes of cosine wave, and Im X[ ] (imaginary part of the complex numbers) is a list of amplitudes of sine wave. As is illustrated in the image:

enter image description here

And all of these waves have phase equal to $0$.

Yet if we use the forward DFT formula $$ X[r] = {\sum}_{k=0}^{N-1} x[k]e^{-j(2 \pi k r / M)} $$ to compute ($M$ is usually considered to be equal to $N$), the output is a sequence consisting of $N$ complex numbers, for a input sample with size $N$. And each of those complex numbers represents a frequency component. Denote a complex number in the list as $a + bi$.

Is it the case that the frequency components have amplitude $A = \sqrt{a^2 + b^2}$, phase $\varphi = \arccos{(\frac{a}{A})}$ and they are shifted sine waves?

$\endgroup$
  • $\begingroup$ if $x[n]$ is real, then there is this Hermitian symmetry which results in the imaginary parts of both $X[0]$ and $X[\frac{N}2]$ are zero. so in both cases there are $N$ different real numbers that can be independently controlled. $\endgroup$ – robert bristow-johnson Jun 20 at 22:31
  • $\begingroup$ Most of what you wrote is correct, but I think it is a mistake to consider the DFT of any $n$-sample signal as anything but a vector with $n$ complex entries. I am certainly biased, but I believe that many readers will gain something by looking at an answer I gave that takes a linear algebraic point of the view of the DFT. $\endgroup$ – Joe Mack Jun 20 at 23:09
1
$\begingroup$

And all of these waves have phase equal to 0.

No. The phase will be zero for $X[0]$ (DC -zero frequency component) but the phase is given by $arctan(Im[i]/Rx[i])$, which usually doesn't result in zero.

Yet if we use the forward DFT formula

$$X[r] = {\sum}_{k=0}^{N-1} x[k]e^{-j(2 \pi k r / M)} $$

to compute ($M$ is usually considered to be equal to $N$), the output is a sequence consisting of $N$ complex numbers, for a input sample with size $N$.

N output complex numbers requires just as many input complex numbers (which means you need N real numbers and N imaginary numbers (all zeros) as input, which together make up the complex input). If, the input is ,however, purely real (N real numbers), and you don't provide an imaginary part, your real fft algorithm will simply treat your input as complex (for instance, the even numbers will be treated as real and odd as imaginary) but now you'll get only $N/2+1$ complex numbers at the output.

I

s it the case that the frequency components have amplitude $A = > \sqrt{a^2 + b^2}$, phase $\varphi = \arccos{(\frac{a}{A})}$ and they are shifted sine waves?

Yes, but the the phase fomula is actually $\varphi = \arctan{(\frac{b}{a})}$

EDIT: As mentioned in a comment below, one generally needs to use $atan2$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Note that $\phi=\arccos(a/A)$ is as (in)valid a formula for computing the phase as is $\phi=\arctan(b/a)$. They give the same correct value for $0\le\phi<\pi/2$, otherwise they give different values and at least one of them is wrong. None of them works in the complete interval $\phi\in [-\pi,\pi]$. In general one needs to use the atan2 function. $\endgroup$ – Matt L. Jun 21 at 11:33
  • $\begingroup$ @Matt L., thanks for clarifying that. I'm using $atan2$ in my own code but the book OP referenced mentions $arctan$ only. The book also goes to some length explaining how to handle incorrect values produced by it so I didn't think it was necessary to emphasize that (corrected now). $\endgroup$ – dsp_user Jun 21 at 12:32
  • $\begingroup$ OK, thanks for editing. I just wanted to point out that $\arccos()$ is not necessarily wrong, as your answer seemed to imply (or at least not worse than the naive use of $\arctan()$). $\endgroup$ – Matt L. Jun 21 at 12:59
  • $\begingroup$ Currently in my implementation I'm using $arccos$ to compute the phase as described in Polar system. atan2 function in C returns $-\pi$, but if the range of $\varphi$ is $(-\pi, \pi]$, it should be $\pi$ , and if we use $arccos$, in this case $\pi$ is returned. Therefore $arccos$ should be a better choice, isn't it? (if the amplitude is already calculated). $\endgroup$ – Xichu Jun 21 at 18:30
  • $\begingroup$ @Xichu, no, $atan2$ should be used but when using $atan2$, no magnitude has to be computed first -- it's just $atan2(Im[i], Re[i])$; $\endgroup$ – dsp_user Jun 21 at 19:58
0
$\begingroup$

You're kind of missing a step in your fine diagram.

Forward is:

 
       DFT                            Ignore 
x[n] ------>  Re( X[k] ), Im( X[k] )  ----->  Re( X[k] ), Im( X[k] )
                  k = 0..(N-1)                    k = 0..(N/2)

The the reverse becomes:

 
       iDFT                          Replicate
x[n] <------  Re( X[k] ), Im( X[k] )  <-----  Re( X[k] ), Im( X[k] )
                  k = 0..(N-1)                    k = 0..(N/2)

The latter steps only work with real valued signals as it relies on the fact that they have conjugate symmetric spectrums.

For a pure real tone on a whole number of cycles, the amplitude of the tone will be half the magnitude of a 1/N normalized DFT bin. This is because the signal is a combination of a pair of conjugate bins.

Thd phase should be determined using the "atan2(b,a)" function. The acos or atan solutions have ambiguous results similar to taking a square root, +/-.

| improve this answer | |
$\endgroup$

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.