0
$\begingroup$

I'm learning DSP on my own. Found a free online book. Currently reading a chapter on Discrete Fourier Transform. Right out of the gate I can't understand several things. I'm pretty good with math and have a decent understanding of complex numbers and their representation with the help of $e^{j\phi}$. But this got me stumbled.

Below is the paragraph I can't understand and the questions pertaining to it.

We now develop a Fourier representation for finite-length signals; to do so, we need to find a set of oscillatory signals of length $N$ which contain a whole number of periods over their support. We start by considering a family of finite-length sinusoidal signals (indexed by an integer $k$) of the form

$$ w_k[n]=e^{j \omega_k n}, \space n = 0,...,N-1 $$ where all the $\omega_k$’s are distinct frequencies which fulfill our requirements. To determine these frequency values, note that, in order for $w_k[n]$ to contain a whole number of periods over $N$ samples, it must conform to

$$ w_k[N]=w_k[0]=1 $$ which translates to $$ (e^{j \omega_k})^N = 1 $$

The above equation has $N$ distinct solutions which are the $N$ roots of unity $e^{j\frac{2\pi m}{N}}$, $m = 0,…,N - 1$

  1. which contain a whole number of periods over their support. What does "periods of their support" mean?
  2. note that, in order for $w_k[n]$ to contain a whole number of periods over $N$ samples. Why does $w_k[n]$ must contain a whole number of periods over $N$ samples? Where does this requirement come from?
  3. it must conform to $w_k[N]=w_k[0]=1$. Why? Where does this requirement come from? I do understand $w_k[N]=w_k[0]$, that's because it is periodic, what I don't understand is $=1$ portion. Why at sample $0$ and sample $N$ it must be equal to 1?
  4. which translates to $(e^{j \omega_k})^N = 1$. How does $w_k[N]=w_k[0]=1$ translate to $(e^{j \omega_k})^N = 1$?
  5. The above equation has $N$ distinct solutions which are the $N$ roots of unity $e^{j\frac{2\pi m}{N}}$, $m = 0,…,N - 1$. Can someone demonstrate the finding of these roots?
Improve this question
$\endgroup$
1
  • $\begingroup$ if you know how to do Fourier Series (discrete or continuous), particularly the form with complex exponentials and coefficients as with: $$ x(t+P)=x(t) \qquad \forall t \in \mathbb{R} $$ for some period $P>0$, then $$ x(t) = \sum\limits_{k=-\infty}^{+\infty} c_k \, e^{j 2 \pi (k/P) t} $$ where $$ c_k = \frac{1}{P}\int\limits_{t_0}^{t_0+P} x(t) \, e^{-j 2 \pi (k/P) t} \, dt \qquad \forall t_0 \in \mathbb{R}$$ if you understand that math, then the DFT is a piece of cake. $\endgroup$
    – robert bristow-johnson
    Jan 13, 2018 at 6:07

2 Answers 2

Reset to default
3
$\begingroup$

The Discrete Fourier Transform is one-and-the-same as the Discrete Fourier Series. The DFT (and explicitly DFS) maps one periodic sequence, $x[n]$ of period $N$:

$$ x[n+N] = x[n] \qquad \forall n \in \mathbb{Z} $$

to another periodic sequence, $X[k]$, having the same period $N$:

$$ X[k+N] = X[k] \qquad \forall k \in \mathbb{Z} $$

and the inverse DFT (or "iDFT") maps it back.

I have a pretty rigid Nazi-like position about it (see the other answer), but I don't think that the math cares. Now if you wanna connect this to the more common (but often misinterpreted) derivation, you can look at a previous answer of mine.

The term "support of $x[n]$" simply means the domain of values of $n$ in which $x[n]$ (presumed to be non-periodic and to have "finite support") is potentially non-zero. It could also mean the duration of $x[n]$. But when you periodically extend $x[n]$, then that sequence has no finite support. $x[n]$ is defined and potentially non-zero everywhere (or all integers).

Improve this answer
$\endgroup$
2
$\begingroup$

1) I would say that "periods of their support" is a poorly worded phrase which is equivalent to the $N$ sample points of the time domain that comprise your sample frame.

2) This is easier to explain if you understand Linear Algebra. Technically it is not a requirement, but it is inherent in the DFT definition. The reason has to do with the fact that the set of whole integer sinusoidal functions over a fixed length sample frame form an orthogonal basis. This makes coefficient determinations trivial. If you have a completely non-orthogonal basis, then coefficient calculations become a system of $N$ equations with $N$ unknowns.

3) $w_k[N]=w_k[0]$ is the same as have a whole number of cycles per frame. That it equals 1 comes from $w_k[n]=e^{j \omega_k n}$ not having a phase value included.

4) Again, this follow straight from the definition. $w_k[n]=e^{j \omega_k n}$

5) My first, and most popular blog article, was written mainly to lay the foundation of what the Roots of Unity mean, as they are the primary foundation of the DFT. "The Exponential Nature of the Complex Unit Circle" can be found here:

https://www.dsprelated.com/showarticle/754.php

Of course, I recommend that you read all my articles, especially the second one which give a intuitive graphical interpretation of the meaning of the DFT for a real valued signal.

Hope this helps.

Ced

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.