1
$\begingroup$

I am aware that the FFT of a real signal is Hermitian, i.e. $\text{FFT}(f)[i] = \text{FFT}(f)[-i]^*$, where $\text{FFT}(f)[i]$ is the i-th component of the FFT of $f$.

The logical consequence of this is that $\text{FFT}(f)[0]$ is real. Another way of seeing this is that the coefficient with index 0 is the "DC" component, or the "mean", and that this is of course real for a real signal.

Another consequence of course is that one needs to know only "half" the FFT to know it in full (i.e., it should be enough to know the coefficients number $0..N/2$, where N is the number of samples).

I was looking for a "real FFT" algorithm for my microcontroller and found the "official" ARM FFT. Of course they do it effectively, using an output of size N real numbers rather than N complex numbers, and outputing "only half the complex FFT" instead of the full (redundantly hermitian) FFT. This saves 50% space.

However I was surprised to see (in the discussion here https://github.com/ARM-software/CMSIS_5/issues/1091 ) that the FFT of the real signal actually has 2 purely real output values (at least, this is how they pack the output): the coefficient of index 0 (as expected) and also the coefficient of index N/2. I do not understand why the coefficient of index N/2 is real. Any hint why?

Details from the discussion there: "Except the first complex number that contains the two real numbers X[0] and X[N/2] all the data is complex. In other words, the first complex sample contains two real values packed."


As pointed out in comments, what I am interested in is actually some DFT properties. So that should be something like ($l$ and $k$ the DFT and function indexes, [] the "index slicing"):

$ DFT(f)[l] = \frac{1}{N} \sum_{k=0}^{N-1} f[k] e^{i 2 \pi k l / N}$

$\endgroup$
8
  • $\begingroup$ Ahh, I think I understand; is this because aliasing makes that any signal of the form $a*cos(\omega_{nyquist} * t + phi)$ will just appear as a signal $b*cos(\omega_{nyquist} * t)$ in practise, i.e. aliasing will make it look like an usual cosine but with reduced amplitude? $\endgroup$
    – Zorglub29
    May 14 at 14:56
  • $\begingroup$ Cannot edit the comment, but should be $b*cos(\omega_{nyquist}*t) + c$ I think. $\endgroup$
    – Zorglub29
    May 14 at 15:12
  • $\begingroup$ you need to deal with complex sinusoids, not just with $\cos$ when understanding the DFT. Could you please add the DFT formula you refer to to your question, so that we can base answers on the same notation? It's really easy once you've written down the DFT formula, honestly. $\endgroup$ May 14 at 15:15
  • $\begingroup$ Well, a cos with arbitrary phase is a any sinusoid / cosinusoid, right? :) . $\endgroup$
    – Zorglub29
    May 14 at 15:30
  • $\begingroup$ yes, but you'll not get the DFT that way. Please add the DFT formula that you're using to your question, or we'll be stumbling around in the dark here. This is really not meant to annoy you – just that it's easier to understand someone explaining something when they use the same terminology. And if you've got an incorrect idea of the DFT formula, then no matter what we explain would help you. $\endgroup$ May 14 at 15:32
3
$\begingroup$

First, "why (at least) 2 points of the FFT is real" is incorrect. It is why one or two points of the FFT is real.

Each point of a discrete Fourier transform (which the FFT is just an algorithm to compute quickly) is the complex coefficient for its corresponding frequency. In other words, the DFT starts with the assertion that the signal in question can be fully described by $$x_k = \sum_N a_k e^{\frac{2\pi}{N}k} \tag 1$$

For $x_k \in \mathbb R$, (1) just carries the constraint that $a_k = (a_{N - k})^*$, where $x^*$ is complex conjugation.

From this, we can show that $a_0$ (and $a_{N/2}$ for $N$ even) are constrained to be real:

Start with the rule I mentioned that in order for $x_k$ to be real, $a_k = (a_{N - k})^*$. Another property of the DFT is that it's only uniquely defined over an interval $N$ points long, and then it repeats. So $a_{k + N} = a_k$. This means that for $k=0$, $a_{N - k} = a_{N} = a_0$. Applying the conjugate property, this means that $a_0 = a_0^*$ -- so $a_0$ must be real.

For $N$ even, $a_{N/2} = a_{N - N/2}$. So, again, $a_{N/2} = a_{N/2}^*$, so $a_{N/2}$ must be real.

So -- one (or two, in the case of an even number of points) arguments must be real.

$\endgroup$
2
$\begingroup$

Let's look at the two special cases $l=0$ and $l=\frac N2$ for $$\operatorname{DFT}(f)[l] = \frac{1}{N} \sum_{k=0}^{N-1} f[k] e^{i 2 \pi k l / N}\text:$$

$l=0$

\begin{align*} \operatorname{DFT}(f)[0] &= \frac{1}{N} \sum_{k=0}^{N-1} f[k] \cdot e^{i 2 \pi k 0 / N}\\ &=\frac{1}{N} \sum_{k=0}^{N-1} f[k] \cdot e^{0}\\ &=\frac{1}{N} \sum_{k=0}^{N-1} f[k] \cdot 1\\ &=\frac{1}{N} \sum_{k=0}^{N-1} f[k]\\ \end{align*}

That's just the average of $f$! If all elements of $f$ were real, there's no imaginary part "appearing" anywhere.

$l=\frac N2$

\begin{align*} \operatorname{DFT}(f)\left[\frac N2\right] &= \frac{1}{N} \sum_{k=0}^{N-1} f[k] \cdot e^{i 2 \pi k \frac N2 / N}\\ &= \frac{1}{N} \sum_{k=0}^{N-1} f[k] \cdot e^{i \pi k }\tag{🐱}\label{eq:cplxexp}\\\ \end{align*}

Remember that $e^{ix}$ is just "the point in the complex plane on the unit cycle at (radian) angle $x$", and we're inserting integer multiples of $\pi$ into $\eqref{eq:cplxexp}$; at multiples of $\pi$, the sine $\sin(x)$ is always zero, but the $\cos$ only takes one of the values $+1, -1$. So, this alternatively adding, and subtracting values from $f[k]$; no imaginary part appears anywhere.

Source:wikipedia article "Euler's Identity", wikimedia user Wereon

$\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.