# Discrete Fourier transform symmetry

I was reading the chapter on discrete Fourier transforms in Lyons' book -- Understanding Digital Signal Processing -- and could not understand the last paragraph about symmetry.

There’s an additional symmetry property of the DFT that deserves mention at this point. In practice, we’re occasionally required to determine the DFT of real input functions where the input index $n$ is defined over both positive and negative values. If that real input function is even, then $X(m)$ is always real and even; that is, if the real $x(n) = x(−n)$, then, $X_{\textrm{real}}(m)$ is in general nonzero and $X_{\textrm{imag}}(m)$ is zero. Conversely, if the real input function is odd, $x(n) = −x(−n)$, then $X_{\textrm{real}}(m)$ is always zero and $X_{\textrm{imag}}(m)$ is, in general, nonzero.

Note: $X(m) = X_{\textrm{real}}(m) + jX_{\textrm{imag}}(m)$

• Firstly, what is meant by "odd" and "even"? I suspect it's the number of samples in the input signal, but that leads me to my second question,
• Why is $X_{\textrm{imag}}(m)$ zero with real input functions that are even, and why, with real input functions that are odd, is $X_{\textrm{real}}(m)$ zero and $X_{\textrm{imag}}(m)$ generally non-zero?

Even & odd refer to the symmetry around $n = 0$.

Even means $x[n] = x[-n]$; you can get the part for $n < 0$ by simply mirroring the part for $n > 0$ at the $n=0$ line.

Odd means $x[n] = -x[-n]$; you can get the part for $n < 0$ by simply mirroring the part for $n > 0$ at the $n=0$ line and multiplying it by $-1$.

A cosine wave is even, sine wave is odd.

These are all just special cases of the general symmetry that says

if it's real in one domain, it's conjugate symmetric in the other.

Conjugate symmetric means that the real part is even and the imaginary part is odd. Most people know that a real time domain signal as a conjugate symmetric spectrum, but it also goers the other way around: a conjugate symmetric time domain signal has a real valued spectrum.

• Ah, picturing a cosine wave and sine wave helped me understand odd and even input functions. Thank you. – someguy Jun 5 '12 at 13:03

Hilmar's answer is of course perfectly correct, but I think there there are several points that Lyons did not address in the statement quoted by the OP (or maybe he talked about them previously and chose not to repeat himself in the paragraph quoted by the OP).

The Discrete Fourier Transform (DFT) is commonly described as a transformation of a sequence $(x[0], x[1], \ldots, x[N-1])$ of finite length $N$ into another sequence $(X[0], X[1], \ldots, X[N-1])$ of length $N$ where \begin{align*} X[m] &= \sum_{k=0}^{N-1} x[k]\exp\left(\frac{-j2\pi mk}{N}\right), ~ m = 0, 1, \ldots, N-1,\\ x[n] &= \frac{1}{N}\sum_{m=0}^{N-1} X[m]\exp\left(\frac{j2\pi nm}{N}\right), ~ n = 0, 1, \ldots, N-1. \end{align*} But these formulas can also be used when $m, n$ are outside the range $[0, N-1]$ and if we do so, we come to the conclusion that the length-$N$ DFT can be viewed as a transformation from a periodic sequence $x[\cdot]$ to another periodic sequence $X[\cdot]$, both extending to infinity in both directions, and that $(x[0], x[1], \ldots, x[N-1])$ and $(X[0], X[1], \ldots, X[N-1])$ are just one period of these infinitely long sequences. Note that we are insisting that $x[n+iN] = x[n]$ and $X[m+iN] = X[m]$ for all $m, n,$ and $i$.

This is, of course, not how data are often handled in practice. We may have a very long sequence of samples, and we break them up into blocks of suitable length $N$. We calculate the DFT of $(x[0], x[1], \ldots, x[N-1])$ as $$X^{(0)}[m] = \sum_{k=0}^{N-1} x[k]\exp\left(\frac{-j2\pi mk}{N}\right), ~ m = 0, 1, \ldots, N-1,$$ the DFT of the next chunk $(x[N], x[N+1], \ldots, x[2N-1])$ as $$X^{(1)}[m] = \sum_{k=0}^{N-1} x[k+N]\exp\left(\frac{-j2\pi mk}{N}\right), ~ m = 0, 1, \ldots, N-1,$$ the DFT of the previous chunk $(x[-N], x[-N+1], \ldots, x[-1])$ as $$X^{(-1)}[m] = \sum_{k=0}^{N-1} x[k-N]\exp\left(\frac{-j2\pi mk}{N}\right), ~ m = 0, 1, \ldots, N-1,$$ etc. and then we play with these various DFTs of the various chunks into which we have subdivided our data. Of course, if the data are in fact periodic with period $N$, all these DFTs will be the same.

Now, when Lyons talks of ...where the input index n is defined over both positive and negative values... he is talking of the periodic case, and when he says that a (real) even function has the property $x[n] = x[-n]$, this property must hold for all integers $n$. Since periodicity also applies, we have not only that $x[-1] = x[1]$ but $x[-1] = x[-1+N] = x[N-1]$, and similarly, $x[-n] = x[n] = x[N-n]$. In other words, the real even sequence $(x[0], x[1], \ldots, x[N-1])$ whose DFT is a real even sequence (as stated by Lyons and explained very nicely by Hilmar) is necessarily of the form $$(x[0], x[1], \ldots, x[N-1]) = (x[0], x[1], x[2], x[3], \ldots, x[3], x[2], x[1])$$ which is (apart from the leading $x[0]$) a palindromic sequence. If you are partitioning your data into blocks of length $N$ and computing the DFT of each block separately, then these separate DFTs will not have the symmetry properties described above unless the DFT is of a block with this palindromic property.

Just for even and odd function clarification,

Even : symmetric with respect to y axis Odd: symmetric with respect to origin

And without going into mathematical details, DFT of real valued function is symmetric, i.e. resultant Fourier function has both real and imaginary parts which are mirror images with respect to 0 frequency component. This doesn't happen in case where you take DFT of a complex function.

• >Even : symmetric with respect to y axis Odd: symmetric with respect to origin. Could you explain just a little bit more what this means, perhaps giving examples of functions that you consider to be even function and odd respectively? I get the feeling that maybe your definition allows a function to be both even and odd. Is that so? – Dilip Sarwate Jun 7 '12 at 10:59
• Hi Dilip, If a function is mirror image with respect to y axis, its even. For example, cosine is mirror image with respect to Y axis. Its an even function. For odd function, its a reflection with respect to origin. Means you take reflection with respect to both X and Y. Like sine function. You can just look at the plot and tell if its an even or odd function. – Naresh Jun 8 '12 at 13:20