2
$\begingroup$

This is bound to be an embarrassingly simple question, but here it goes...

I was reading the chapter on discrete Fourier transforms (DFT) of this really didactic online book, The Scientist and Engineer's Guide to Digital Signal Processing by Steven W. Smith and I got stuck thinking about the last sentence in the caption to this illustration:

enter image description here

The parameter, $k$, determines the frequency of the wave. In an $N$ point DFT, $k$ takes on values between $0$ and $\color{red}{\frac{N}{2}}.$

He goes on to say with regards to the $32$-point DFT,

For example, Fig. 8-5 [not included here] shows some of the $17$ sine and $17$ cosine waves used in an N = 32 point DFT.

So it seems to indicate $16$ sine waves, or $(N/2)$, plus the constant component, and a parallel split for cosine waves.

However, the DFT is defined as

The DFT is defined as:

$$X(k)\equiv \sum_{n=0}^{N-1} x(n)\; \exp\left(\mathbf-i\frac{2\pi}{N}kn\right), \quad k=0,1,\dots,\color{red}{N-1}$$

which is $\color{red}{N}$ values of $k$, not $\color{red}{\frac{N}{2}}.$

And given Euler's formula:

$$e^{-ix}=\cos x - i \sin x$$

it seems as though there should be an equal number of sine and cosine basis equations: one of each frequency parameter $k$ for a total of $N$ sine and $N$ cosine.

Of course, at some points, the sine or cosine components will be zero (as we move around the complex plane, and depending on $N$), but not necessarily $\frac{N}{2}$. For instance, the $4$-point DFT would indeed either fall on the $x$-axis (real - cosine), or $y$-axis (imaginary - sine), splitting the basis function in half. Yet this seems to be a very sweet and unique example.

What am I missing?

$\endgroup$
  • $\begingroup$ What's the link to the question posted there? $\endgroup$ – Royi Apr 1 '17 at 20:17
1
$\begingroup$

Here is another more formal way to look at it, starting with the definition of the DFT:

$$ \begin{align} X(k) &= \sum_{n=0}^{N-1} x[n] \exp\left(-i\frac{2\pi}{N} k n\right), & k=0,\dots,N-1 \end{align} $$ Assuming $N$ is even, you can rewrite the expression as:

$$ \begin{align} \begin{split} X(k) &= x[0] + \sum_{n=1}^{N/2-1} x[n] \exp\left(-i\frac{2\pi}{N} k n\right)\\ &\quad +x\left[\frac{N}{2}\right]\exp\left(-i\frac{2\pi}{N} k \frac{N}{2}\right) + \sum_{n=N/2+1}^{N-1} x[n] \exp\left(-i\frac{2\pi}{N} k n\right) \\ &= x[0] + (-1)^k x\left[\frac{N}{2}\right]\\ &\quad +\sum_{n=1}^{N/2-1} x[n] \exp\left(-i\frac{2\pi}{N} k n\right) + \sum_{n=N/2+1}^{N-1} x[n] \exp\left(-i\frac{2\pi}{N} k n\right) \\ \end{split} \end{align} $$ If we then perform the change of variable $n=N-n'$ on the second summation (and inverse the summation bounds), we get: $$ \begin{align} \begin{split} X(k) &= x[0] + (-1)^k x\left[\frac{N}{2}\right]\\ &\quad +\sum_{n=1}^{N/2-1} x[n] \exp\left(-i\frac{2\pi}{N} k n\right) + \sum_{n'=1}^{N/2-1} x[N-n'] \exp\left(-i\frac{2\pi}{N} k (N-n')\right) \\ &= x[0] + (-1)^k x\left[\frac{N}{2}\right]\\ &\quad +\sum_{n=1}^{N/2-1} x[n] \exp\left(-i\frac{2\pi}{N} k n\right) + \sum_{n'=1}^{N/2-1} x[N-n'] \exp\left(i\frac{2\pi}{N} k n'\right) \\ &= x[0] + (-1)^k x\left[\frac{N}{2}\right]\\ &\quad +\sum_{n=1}^{N/2-1} x[n] \left(\cos(2\pi k n/N)-i\sin(2\pi k n/N)\right) \\ &\quad +\sum_{n=1}^{N/2-1} x[N-n] \left(\cos(2\pi k n/N)+i\sin(2\pi k n/N)\right) \\ &= x[0] + (-1)^k x\left[\frac{N}{2}\right]\\ &\quad +\sum_{n=1}^{N/2-1} \left(x[n]+x[N-n]\right)\cos(2\pi k n/N) \\ &\quad -i\sum_{n=1}^{N/2-1} \left(x[n]-x[N-n]\right)\sin(2\pi k n/N) \end{split} \end{align} $$ Since $\cos(0)=1$ and $\cos(\pi k) = (-1)^k$, the first two terms could be rewritten as $$ \begin{align} x[0] &= x[0]\cos(0) \\ &= x[0]\cos(2\pi k\cdot 0/N) \\ (-1)^k x[N/2] &= x[N/2]\cos(\pi k) \\ &= x[N/2]\cos(2\pi k (N/2)/N) \end{align} $$ So you could write: $$ \begin{align} X(k) &= \sum_{n=0}^{N/2} a_n \cos(2\pi k n/N) + \sum_{n=1}^{N/2-1} b_n \sin(2\pi k n/N) \end{align} $$ where $$ \begin{align} a_n &= \begin{cases} x[n], & n&=0,N/2 \\ x[n]-x[N-n], & n&=1,\dots,N/2-1 \end{cases} \end{align} $$ and $$ \begin{align} b_n &= -i\left(x[n]-x[N-n]\right) &n=&1,\dots,N/2-1 \end{align} $$ So for even $N$ that gives you $N/2-1$ sine terms and $N/2+1$ cosine terms.

Now equation 8-1 claims sine and cosine coefficients for $n=0,\dots,N/2$. That's $N/2+1$ sine and $N/2+1$ cosine terms. It turns out that the sine terms for $n=0$ and $n=N/2$ are always zero since: $$ \begin{align} \sin(2\pi k n/N) &= \sin(0) = 0, & n&=0\\ \sin(2\pi k n/N) &= \sin(\pi n) = 0, & n&=N/2 \end{align} $$ You might notice that in the example with a $N=32$ in your linked reference, that figure 8-5 shows that $s_0[]$ (subfigure "b") and $s_{16}[]$ (subfigure "h") are indeed always zero.

Note that you can do the same exercise for odd $N$ and get a similar expression for $X(k)$: $$ \begin{align} X(k) &= \sum_{n=0}^{\lfloor N/2 \rfloor} a_n \cos(2\pi k n/N) + \sum_{n=1}^{\lceil N/2 \rceil -1 } b_n \sin(2\pi k n/N) \end{align} $$ So for odd $N$ you get $(N-1)/2$ sine and $(N-1)/2+1$ cosine terms.

In that case equation 8-1 would give you $(N-1)/2 + 1$ sine and $(N-1)/2 + 1$ cosine terms, with the sine term with $n=0$ always being zero (so you effectively have $(N-1)/2$ sine terms).

$\endgroup$
1
$\begingroup$

There is no contradiction.

Both cases you have information from $ -\frac{ Fs }{ 2 } $ to $ \frac{ Fs }{ 2 } $.

The representation using Cosine ans Sine functions is using Real Functions.
Those functions are symmetric as Real Valued functions.
Namely if you a coefficient for a Sine in a given frequency it is for sure have energy on the negative frequency as well (See the DFT / Fourier Transform of Sine and Cosine).
Namely using those functions all needed it to go from $ 0 $ to $ \frac{ Fs }{ 2 } $ as the negative value is implicit.

On the other end, for the Complex Exponent the energy is one sided.
Hence you must go from $ -\frac{ Fs }{ 2 } $ to $ \frac{ Fs }{ 2 } $.

$\endgroup$
1
$\begingroup$

You have $\lfloor N/2\rfloor+1$ cosine coefficients and $\lceil N/2\rceil-1$ sine coefficients for real-valued input (for complex-valued input, talking about sine and cosine instead of complex exponentials would be pointless). Why? Transformed complex coefficients $c_k$ and $c_{-k}$ of a real-valued original form conjugate pairs, with the imaginary parts indicating a sine function and the real parts indicating a cosine function.

Now $c_0 = c_{-0}$, and for even $N$, $c_{N/2} = c_{-N/2}$ (as coefficients wrap around after $N$ values). If they are complex conjugate pairs with themselves, they can only be real-valued, so for those coefficients, we only have cosine functions (one is for the DC component, one for the Nyquist frequency component).

$\endgroup$
  • 1
    $\begingroup$ i think it's more precise to say: You have $\lfloor N/2 \rfloor$ cosine coefficients (counting Nyquist if $N$ is even), $\lceil N/2 \rceil - 1$ sine coefficients, and one DC coefficient. that adds up to $N$ real coefficients. In the DFT, if $x[n]$ is real, you will have $\lceil N/2 \rceil - 1$ complex coefficients that have the same number of conjugates (so no new information there), one real coefficient at Nyquist (if $N$ is even), and one real DC coefficient. that should also add to $N$ real numbers. $\endgroup$ – robert bristow-johnson Apr 1 '17 at 22:53
1
$\begingroup$

Another way to look at it is to notice that a DFT only deals with samples, so only the sample points of the complex exponentials matter.

All the sample points of a cosine above N/2 alias to be identical with the sample points of a cosine below N/2, so those cosines are all redundant. Ignore. All the sample points of a sinewave at or above N/2 also alias to be identical to the inverse samples of a sinewave below N/2. Dump those as unneeded (multiplying by -1 shouldn't require a whole new basis vector). Add the DC term and you end up with N/2 cosines, N/2 - 1 sines, plus a DC term (call it cosine(0)), as the only non-redundant basis vectors. For strictly real input data to the DFT.

But if you like redundant basis vectors, the number can be infinite, a lot more than 2N.

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