2
$\begingroup$

I know one of the properties of DFT for real-valued time series is conjugate symmetry.

But what does it imply? In the textbook it says that for a DFT of the length M, this makes M/2-1 spectral coefficients redundant. Could someone please explain this to me? How do we conclude this?

$\endgroup$
  • $\begingroup$ the sign of the imaginary part of a complex number is equally significant as the sign of the real component. can one say conjugate symmetry is purely redundant? or we only transform real sequences? $\endgroup$ – Stanley Pawlukiewicz Nov 27 '18 at 21:50
2
$\begingroup$

There is a different conceptual way to think about this. Imagine that you have a necklace made up of beads of different weights. Imagine also that you have a wheel with a circumference the same length as the necklace. Now, attach the necklace at the 3 o'clock position on the wheel and wrap it counter-clockwise around the wheel. Next, wrap the necklace in a clockwise direction. By symmetry, it is obvious that the center of masses in the two cases are going to be mirror imaged on the horizontal center line of the wheel. The same is true if you stretch the necklace by a factor of two and wrap it twice around the wheel. Same for 3, same for 4, etc. If there are $N$ evenly spaced beads, and you are stretching the necklace $N-1$ times, it is easy to see the beads end up as if you were wrapping the necklace in the reverse direction once.

This is precisely how a $1/N$ normalized DFT of a real valued signal works and one way to look at what it means. (See my blog article DFT Graphical Interpretation: Centroids of Weighted Roots of Unity for a more mathematical description.)

The center of mass (bin value) will be in the mirror image position (complex conjugate) when you wrap the necklace (DFT of signal) in the reverse (negative) direction.

$$ X[k] = X^*[-k] $$

So, this pertains to real valued signals. Suppose you have $M$ bins, and assume that $M$ is even, then bins $1$ through $M/2-1$ are the complex conjugates of bins $M-1$ through $M/2+1$, so those are your redundant spectral coefficients. Furthermore, the DC bin ($0$) and the Nyquist bin ($M/2$) have to be real valued, that is the imaginary component is zero.

$\endgroup$
2
$\begingroup$

The textbook probably even has the proof; but it's not hard to do: Simply write down the sum that gives you the $k$th bin of the transforf $X[k]$ of the time series $x[n]$. Then, flip $k$'s sign and apply the conjugate to finish your proof.

To show:

\begin{align} X[k] &\overset{\text{claim}}= X^*[-k]\\ X[k] &= \sum_{n=0}^{N-1}x[n]e^{-j2\pi k\frac nN}\\ X^*[-k] &= \left(\sum_{n=0}^{N-1}x[n]e^{-j2\pi (-k)\frac nN}\right)^*\\ &= \sum_{n=0}^{N-1}\left(x[n]e^{-j2\pi (-k)\frac nN}\right)^*&\text{Sum operator linear}\\ &= \sum_{n=0}^{N-1}x[n]\left(e^{-j2\pi (-k)\frac nN}\right)^*&x[n]=x^*[n]\text{ since real}\\ &= \sum_{n=0}^{N-1}x[n]e^{-(-j2\pi (-k)\frac nN)}\\ &= \sum_{n=0}^{N-1}x[n]e^{-j2\pi k\frac nN}\\ &=X[k] &\rule{1ex}{1ex} \end{align}

Now, having showed that half of the coefficients are just the conjugate of the others: It's obviously sufficient to only consider one half; the other can be directly calculated from that.

$\endgroup$
  • 3
    $\begingroup$ this is good, but i think you wanna remind people that $$X[-k] = X[N-k]$$ in case some folks insist that $0 \le k < N$. $\endgroup$ – robert bristow-johnson Nov 27 '18 at 22:14
  • $\begingroup$ Yep, I honestly keep forgetting that just because I see the $2\pi$ periodicity of $e^{jx}$ doesn't mean it's self-explanatory in a formula if I just work $\mod N$. $\endgroup$ – Marcus Müller Nov 27 '18 at 22:49
  • $\begingroup$ I think you should have also explicitly mentioned that $$x^*[n]=x[n]$$ because the signal is real valued. $\endgroup$ – Cedron Dawg Nov 29 '18 at 15:43
  • 1
    $\begingroup$ @CedronDawg made that amendment. $\endgroup$ – Marcus Müller Nov 29 '18 at 17:02

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.