8
$\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,

Fig. 8-5 enter image description 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:

$$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?

Improve this question
$\endgroup$
1
  • $\begingroup$ What's the link to the question posted there? $\endgroup$ Commented Apr 1, 2017 at 20:17

4 Answers 4

Reset to default
6
$\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).

Improve this answer
$\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 } $.

Improve this answer
$\endgroup$
0
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).

Improve this answer
$\endgroup$
1
  • 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$ Commented Apr 1, 2017 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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.