# Basis signals for the discrete-time Fourier Series

I am using Alan Oppenheim's Signals and Systems and I am a bit confused by the notion of discrete-time periodic exponentials as basis signals for the discrete-time Fourier Series (and later the DTFT). For the discrete-time Fourier Series we use the basis signals $$\phi_k [n] = e^{jk\frac{2\pi}{N}n} = e^{jk\Omega_0n} ,$$ where $\Omega_0 = \frac{2\pi}{N}$, to build general discrete-time periodic signals. Unlike the continuous-time case where we use complex exponentials as basis functions for the Fourier Series representation, in this case the fundamental frequency of the $k$th basis signal is not $k\Omega_0$. This is because it can be shown that for a discrete-time periodic complex exponential signal $e^{jk\frac{2\pi}{N}n}$, the fundamental period $N_0$ is not $N$, but rather $$N_0 = \frac{N}{\gcd(k,N)},$$ where $\gcd(k,N)$ is the greatest common divisor of the integers $k$ and $N$. From that we conclude that the fundamental frequency of the $k$th basis signal $\phi_k[n]$ is not $k\frac{2\pi}{N}$, but rather $\gcd(k,N) \frac{2\pi}{N}$. So it is still an integral multiple of the frequency $\Omega_0$, except $\Omega_0$ is multiplied by the greatest common divisor of $k$ and $N$, rather than $k$. Of course in the case where $k$ divides $N$ the frequency would be $k \Omega_0$, but we cannot know a priori whether that's the case. Am I correct in my understanding?

Assuming that what I said above is true, when we look at the discrete-time Fourier Series representation of the sequence $x[n]$, we have $$x[n] = \sum_{k = <N>} a_k \phi_k[n],$$

which is a linear combination of the basis signals I defined above (and what the author means by the notation above is that the sum is over any $N$ values of $k$). Now given the fact the fundamental frequency of the $k$th component in this sum is $\gcd(k,N) \Omega_0$, it might turn out that $k$ and $N$ have no common factors at all, in which case the fundamental frequency of the $k$th basis signal is simply $\Omega_0$, which is the same as the fundamental frequency of the first basis signal. Therefore, those two basis signals seemingly have the same fundamental frequency and period (within the range of values of $k$ defined earlier). Does that make those signals identical, or are they different? Are the signals guaranteed to be different? And if they are not, doesn't that make the set of basis signals $\{\phi_k\}$ linearly dependent? And does the Fourier Series representation break down in this case?

The complex exponentials

$$\phi_k[n]=e^{j\frac{2\pi k}{N}n},\qquad k=0,1,\ldots, N-1\tag{1}$$

form an orthogonal basis, i.e.

$$\sum_{n=0}^{N-1}\phi_k[n]\phi_l^*[n]=0,\qquad k\neq l\tag{2}$$

So clearly they are all different, and they are even orthogonal (and hence not linearly dependent).

It's straightforward to show that Eq. $(2)$ is true:

$$\sum_{n=0}^{N-1}\phi_k[n]\phi_l^*[n]=\sum_{n=0}^{N-1}e^{j\frac{2\pi (k-l)}{N}n}= \begin{cases} \sum_{n=0}^{N-1}e^{j\frac{2\pi (0)}{N}n}=\sum_{n=0}^{N-1}1=N,\qquad & k = l \\ \\ \frac{1-e^{j2\pi (k-l)}}{1-e^{j\frac{2\pi (k-l)}{N}}}=\frac{1-1}{1-e^{j\frac{2\pi (k-l)}{N}}}=0,\qquad & k\neq l \\ \end{cases}\tag{3}$$

• But is it true that although they are different they could potentially have the same fundamental frequency and period, and that the frequency of the $k$th basis signal is $\gcd(k,N) \Omega_0$ not $k \Omega_0$? – user33568 Feb 5 '18 at 17:50
• You have shown that the basis is orthogonal (and the functions are all different) in the case of complex exponentials. What about discrete-time sinusoids? If we look at $\cos (\frac{\pi n}{4})$ and $\cos (\frac{7 \pi n}{4})$ for example, these two signals seem to be identical when plotted. Does that mean they are not orthogonal? Is it different from using complex exponentials? What am I missing here? – user33568 Feb 5 '18 at 19:15
• @0MW: All $\phi_k[n]$ have period $N$. For some of them this might not be the smallest period if $N/k$ is an integer. The two cosine functions in your comment are indeed identical, but the corresponding complex exponentials are not (because their imaginary parts have opposite signs). – Matt L. Feb 5 '18 at 22:18