3
$\begingroup$

As I understand, the DFT of a signal $x$ is a representation of this signal in the basis

$$ \{ e^{j2\pi kn/N} \}_{k = 0, 1, \dots, N-1}$$

Is it possible to form a base of such discrete complex exponentials but with different frequencies ? ($\{ e^{j2\pi f_i n} \}$)

Why did we choose these $\frac{k}{N}$ frequencies ?

In fact, my question is more about why we evaluate the DFT at these specific frequencies and not others.

$\endgroup$
2
  • 3
    $\begingroup$ The DFT basis consists of all possible complex exponentials which have period N. $\endgroup$
    – Juancho
    Apr 10, 2022 at 16:42
  • $\begingroup$ IIRC the frequencies you choose will not be orthogonal. $\endgroup$
    – user253751
    Apr 11, 2022 at 11:08

1 Answer 1

7
$\begingroup$

$k/N$ with $N$ bases is the only basis which is all of:

  1. Orthogonal & invertible. Means we don't lose any information. Invertibility can be seen to follow from the DFT being a square (N x N) matrix of rank N (orthogonal = all columns independent), so we can solve $Ax = y$ with $x = A^{-1}y$.
  2. $N$-periodic. Every basis will repeat after $N$ uniform samples. This makes the DFT a uniform & $N$-periodic sampling of one period of DTFT which yields many useful properties, and enables circular convolution.
  3. Minimal. Maps out the greatest continuous-time bandwidth per unit sample, meaning it's max information-dense. This follows the sampling theorem, which demands a minimum of $N$ samples to capture a bandwidth up to (but not including) $N/2$ (in physical terms, sampling at rate of $f_s$ to capture $f_s/2$). Other bases will take $N$ or more samples (if succeeding at all, see example).

$2k/N$ with $N$ bases is orthogonal and $N$-periodic, but not minimal, nor invertible. In fact it's not invertible for any number of bases, ironically due to periodicity. $Gk/N$, where $G$ is non-integer, is none of those things with $N$ bases. I'll also informally add,

  1. Exact. Follows from 1. Non-orthogonality implies a base has non-zero correlation with other bases, meaning e.g. frequency of 1.5 means "1.5, and a bit of 2.5, and a bit of 0.5, and ...". Though, the part in quotes is a bit tricky depending on interpretation, since it happens no matter what for a realistic input (e.g. spectral leakage).
$\endgroup$
2
  • 1
    $\begingroup$ It would be great if you could include the proof, or cite a proof, that there is no other basis that satisfies all the four properties. $\endgroup$
    – AlexTP
    Apr 11, 2022 at 7:34
  • $\begingroup$ @AlexTP Fair, wouldn't know from top of my head though. Think it could be shown by considering every possible $N$-base cisoid basis that's orthogonal and $N$-periodic, then checking which also meets sampling theorem criteria, so a sort of system of equations. $\endgroup$ Apr 11, 2022 at 17:24

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.