Thus far we have been talking about continuous time signals. Let's now look at discrete time signals.
Discrete time signals are fundamentally different from countinuous time signals in that they only exist at discrete instances of time and are undefined elsewhere. This introduces some quirks that are present in analysis of CT signals.
But first let's see why expressing signals as linear combinations of exponentials is useful. The explanation below also holds for CT signals & systems , but is particularly easy to understand for DT systems.
Consider an linear shift-invariant (LSI) system with impulse response $h[n]$.
The output of the system to any input $s[n]$ can be written as
\[ y[n] = \sum_{k = -\infty}^{\infty} h[k] s [n-k]\]Let $s[n] = e^{j \omega n}$ -- a complex exponential
We can write: \[ \begin{align*} y[n] &= \sum_{k = -\infty}^{\infty} h[k] e^{j \omega (n - k)} \\ &= e^{j \omega n} \sum_{k = -\infty}^{\infty} h[k] e^{-j \omega k} \\ &= H(\omega) e^{j \omega n} \end{align*} \]
In other words an input $e^{j \omega n}$ simply comes out as exactly itself, only it is scaled by $H(\omega)$. $H(\omega)$ is not a function of n.
In other words $e^{j \omega n}$ is an EIGEN input to an LSI system which comes out as a scaled version of itself.
More generally, if $s[n] = z^n$ where $z$ is any complex term \[ \begin{align*} y[n] &= \sum_{k = -\infty}^{\infty} h[k]z^{n -k} \\ &= z^{n} \sum_{k = -\infty}^{\infty} h[k] z^{-k} \\ &= H(z) z^n \end{align*} \]
Any exponential signal is an eigen input to an LSI system. We have used the symbol "z" here because we will talk about $H(z)$ later when we discuss the z-transform.
What this means, however, is that if we can write $s[n]$ as a summation of exponentials: \[s[n] = \sum a_k e^{j \omega_k n} \text{ for some } \omega_k\] Then: \[y[n] = \sum [a_k H(\omega_k)] e^{j \omega_k n}\]
The output is easily obtained. To analyze the output we only need to analyze periodic discrete-time complex exponentials.
BackFirst let us consider some useful properties of discrete time complex exponentials which are periodic.
Recall that a complex exponential $e^{-j \omega n}$ is periodic iff $\omega$ is a rational multiple of $\pi$.
Consider a complex exponential with fundamental period N.
So $e^{\frac{j 2 \pi}{N}(n + mN)} = e^{\frac{j 2 \pi n}{N}}$ for $m = 1$
$e^{\frac{j 2 \pi n}{N}}$ is periodic and the period is N
$e^{j 2 \pi \frac{(k + N)}{N}n} = e^{\frac{j 2 \pi k n}{N}}$
For the LHS: \[ \begin{align*} e^{\frac{j 2 \pi k n}{N}} \cdot e^{\frac{j 2 \pi N n}{N}} &= e^{\frac{j2 \pi k n}{N}} \cdot e^{j2 \pi n} \\ &= e^{\frac{j 2 \pi k n}{N}} \end{align*} \]This implies that for ANY period N, there are no more than N unique harmonics. This property does not generalize to countinuous-time.
This is trivial to prove. Using the formula for summation of geometric serieis.
For $k \neq 0$ \[ \begin{align*} \sum_{n = 0}^{N-1} e^{\frac{j 2 \pi k n}{N}} &= \frac{1 - e^{\frac{j 2 \pi k N}{N}}}{1 - e^{\frac{j 2 \pi k}{N}}}, \\ &= \frac{1 - 1}{1 - e^{\frac{j 2 \pi k}{N}}} \\ &= 0 \end{align*} \]
For $k = mN$ \[e^{\frac{j 2 \pi k N}{N}} = e^{\frac{j 2 \pi m N n}{N}} = 1\] \[\sum_{n = 0}^{N-1} 1 = N\]
Note this property does not generalize to CT complex exponentials for $m \neq 0$ in "$k = mN$"
Harmonically-related complex exponential series are orthogonal
\[ \sum_{n = 0}^{N -1} e^{\frac{j 2 \pi k_1 n}{N}} e^{\frac{j 2 \pi k_2 n}{N}} = \begin{cases} 0, & k_1 \neq k_2 \\ N, & k_1 = m - Nk_2 \end{cases} \] \[ LHS = \sum_{n = 0}^{N-1}e^{j 2 \pi \frac{(k_1 +k_2)}{N}n} = \begin{cases} 0, & k_1 + k_2 \neq mN \\ N, & k_1 + k_2 = mN \Rightarrow k_1 = mN - k_2 \end{cases} \]Note that some of these properties are the results of the signal being discrete-time and do not apply to continuous-time complex exponentials.
For example $e^{j \omega_1 t} \neq e^{j \omega_2 t}$ if $\omega_1 \neq \omega_2$ in CT but we find that $e^{\frac{j 2 \pi n k}{N}} = e^{\frac{j 2 \pi n (k + mN)}{N}}$ in DT.
BackLet $x[n]$ be a discrete time signal that is periodic with period "N"
(a) We claim that $x[n]$ can be expressed EXACTLY as a linear combination of the complex exponential with fundamental period $N$.
As we noted earlier the complex exponential with fundamental period N is given by $e^{\frac{j 2 \pi n}{N}}$
It has exactly $N$ unique harmonics, $e^{\frac{j 2 \pi k n}{N}}, 0 \leq k \leq N$
(since $e^{j 2 \pi \frac{(k + N)}{N}n} = e^{j 2 \pi \frac{k}{N}n}$)
So claim (a) is equivalent to saying we can write \[x[n] = \sum_{k = 0}^{N-1} a_k e^{\frac{j 2 \pi k n}{N}}\]
(b) We claim that this represtentations is unique.
Let us write out the equations for every n: \[x[0] = a_o + a_1 + a_2 + ... + a_{N-1}\] \[x[1] = a_o + a_1 e^{\frac{j 2 \pi}{N}} + a_2 e^{\frac{j 2 \pi 2}{N}} + ... + a_{N-1} e^{\frac{j 2 \pi (N-1)}{N}}\] \[x[N-1] = a_o + a_1 e^{j 2 \pi \frac{(N-1)}{N}} + a_2 e^{j 2 \pi \frac{2(N-1)}{N}} + ... + a_{N-1} e^{j 2 \pi \frac{(N-1)(N-1)}{N}}\]
The representation exist if the above set of simultaneous equations can be exactly solved. We can write them in matrix for as:
\[ \left [ \begin{matrix} x[0] \\ x[1] \\ \vdots \\ x[N-1] \end{matrix} \right] = \left[ \begin{matrix} 1 & 1 & 1 & \ldots & 1\\ 1 & e^{\frac{j 2 \pi}{N}} & e^{\frac{j 2 \pi 2}{N}} & \ldots & a_{N-1} e^{\frac{j 2 \pi (N-1)}{N}}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & e^{j 2 \pi \frac{(N-1)}{N}} & e^{j 2 \pi \frac{2(N-1)}{N}} & \ldots & a_{N-1} e^{j 2 \pi \frac{(N-1)(N-1)}{N}} \end{matrix} \right] \cdot \left[ \begin{matrix} a_o \\ \vdots \\ \vdots \\ a[N-1] \end{matrix} \right] \]Writing: \[ X = \left [ \begin{matrix} x[0] \\ x[1] \\ \vdots \\ x[N-1] \end{matrix} \right] \] \[ A = \left[ \begin{matrix} a_o \\ \vdots \\ \vdots \\ a[N-1] \end{matrix} \right]\] \[ D = \left[ \begin{matrix} 1 & 1 & 1 & \ldots & 1\\ 1 & e^{\frac{j 2 \pi}{N}} & e^{\frac{j 2 \pi 2}{N}} & \ldots & a_{N-1} e^{\frac{j 2 \pi (N-1)}{N}}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & e^{j 2 \pi \frac{(N-1)}{N}} & e^{j 2 \pi \frac{2(N-1)}{N}} & \ldots & a_{N-1} e^{j 2 \pi \frac{(N-1)(N-1)}{N}} \end{matrix} \right] \]
We can write: \[X = DA\] where x is N x 1, A is N x 1, and D is N x N
This can be solved if $D^{-1}$ exists, i.e we can find a matrix B such that $B \cdot D = D \cdot B = I$
It is easy to show that $B = D^{-1} = \frac{1}{N} D^{H}$ \[ D^H = \left[ \begin{matrix} 1 & 1 & 1 & \ldots & 1\\ 1 & e^{-\frac{j 2 \pi}{N}} & e^{-\frac{j 2 \pi 2}{N}} & \ldots & a_{N-1} e^{-\frac{j 2 \pi (N-1)}{N}}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & e^{-j 2 \pi \frac{(N-1)}{N}} & e^{-j 2 \pi \frac{2(N-1)}{N}} & \ldots & a_{N-1} e^{-j 2 \pi \frac{(N-1)(N-1)}{N}} \end{matrix} \right] \]
\[D^H \cdot D = \sum_{n = 0}^{N-1} e^{\frac{j 2 \pi i n}{N}}e^{-\frac{j 2 \pi k n}{N}}\]
The $(i,k)^m$ term of the product: \[ \sum_{n = 0}^{N-1} e^{\frac{j 2 \pi (i) n}{N}}e^{-\frac{j 2 \pi (k) n}{N}} = \begin{cases} 0, & i \neq k \\ N, & i = k \end{cases} \] \[So \frac{1}{N} D^H D = I = D(\frac{1}{N} D^H) \] \[Since D^H = \frac{1}{N} D^H exists\]
$X = DA$ can be solved exactly
Let us now find the values of $a_k$: \[x[n] = \sum_{k = 0}^{N-1} a_k e^{\frac{j 2 \pi k n}{N}}\]
Multiplying both sides by $e^{-\frac{j 2 \pi l n}{N}}$ for an $0 \leq l < N$ and summing over $n$: \[ \begin{align*} \sum_{n = 0}^{N -1} x[n] e^{-\frac{j 2 \pi l n}{N}} &= \\ &= \sum_{n = 0}^{N-1} \sum_{k = 0}^{N-1} a_k e^{\frac{j 2 \pi k n}{N}}e^{-\frac{j 2 \pi l n}{N}} \\ &= \sum_{k =0}^{N-1} a_k \sum_{n=0}^{N-1}e^{\frac{j 2 \pi k n}{N}}e^{-\frac{j 2 \pi l n}{N}} \\ \end{align*} \] So: \[ \Rightarrow \sum_{n=0}^{N-1}x[k]e^{-\frac{j 2 \pi l n}{N}} = a_l \cdot N \] \[a_l = \frac{1}{N} \sum_{n=0}^{N-1}x[k]e^{-\frac{j 2 \pi l n}{N}} , 0 \leq l < N\]
Also \[a_{l+N} = a_l\]
The two equations: \[x[n] = \sum_{k = 0}^{k -1}a_k e^{\frac{j 2 \pi k N}{N}}\] \[a_k = \frac{1}{N} \sum_{n=0}^{N-1} x[n]e^{-\frac{j 2 \pi l n}{N}}\] are known as the Discrete Fourier Series pair.
Case 1 - $\Omega_o = \frac{2 \pi}{N}$ (Period $N$)
\[sin \frac{2 \pi n}{N} = \frac{1}{2j} (e^{\frac{j 2 \pi n}{N}} - e^{-\frac{j 2 \pi n}{N}})\] \[a_o = 0 , a_1 = \frac{1}{2j}, a_{-1} = -\frac{1}{2j}\] \[a_k = 0 \forall \neq \pm 1, k\] \[a_k = a_{k+N}\]Case 2 - $\Omega_o \neq$ rational multiple of $\pi$ so $sin (\Omega_o n)$ is not periodic therefore DTFS does not exist
$x[n] = sin( \Omega_o n)$, $\Omega_o = \frac{2 \pi m}{N}$
\[x[n] = \frac{1}{2j}e^{\frac{j 2 \pi m n}{N}} - \frac{1}{2j}e^{-\frac{j 2 \pi m n}{N}}\] \[a_m = \frac{1}{2j}, a_{-m} = -\frac{1}{2j}\] \[a_{m+lN} = \frac{1}{2j}, a_{-m + lN} = -\frac{1}{2j}\] \[a_k = 0, k \neq lN \pm m\]Plot this result. Note suprising location of frequency components.
We can write \[ \begin{align*} x[n] &= 1 + \frac{1}{2j}e^{\frac{j 2 \pi n}{N}} - \frac{1}{2j}e^{-\frac{j 2 \pi n}{N}} + \frac{3}{2}e^{\frac{j 2 \pi}{N}} + \frac{3}{2}e^{-\frac{-j 2 \pi n}{N}} + \frac{1}{2} e^{j(\frac{2 \pi}{N}(2n) + \phi)} + \frac{1}{2}e^{-j(\frac{2 \pi}{n}(2 n) + \phi)} \\ &= 1 + (\frac{3}{2} + \frac{1}{2j})e^{\frac{j 2 \pi n}{N}} + (\frac{3}{2} - \frac{1}{2j})e^{-\frac{j 2 \pi n}{N}} +\frac{e^{j \phi}}{2}e^{j \frac{2 \pi}{N} (2n)} + \frac{e^{-j \phi}}{2} e^{-j \frac{2 \pi}{n} (2n)} \end{align*} \] \[a_o = 1 \Rightarrow a_{mN} = 1\] \[a_1 = \frac{3}{2} + \frac{1}{2j} \Rightarrow a_{mN+1} = \frac{3}{2} + \frac{1}{2j} \] \[a_{-1} = \frac{3}{2} - \frac{1}{2j} \Rightarrow a_{m N-1} = \frac{3}{2} - \frac{1}{2j}\] \[a_2 = \frac{e^{j \phi}}{2} \Rightarrow a_{m N+2} = \frac{e^{j \phi}}{2}\] \[a_-2 = \frac{e^{-j \phi}}{2} \Rightarrow a_{m N-2} = \frac{e^{-j \phi}}{2}\]
Using the formula for summation of geometric series: \[ \begin{align*} a_k &= \frac{1}{N} e^{\frac{j 2 \pi N_1 k}{N}}(\frac{1 - e^{-\frac{j 2 \pi l (2N_1 +1)}{N}}}{1 - e^{-\frac{j k 2 \pi}{N}}}) \\ &= \frac{1}{N} \frac{e^{\frac{j 2 \pi N_1 k}{N} - e^{-\frac{j 2 \pi k (N_1 + 1)}{N}}}}{1 - e^{\frac{j 2 \pi k}{N}}} \\ &= \frac{1}{N} \frac{e^{-\frac{j 2 \pi k}{2N}}(e^{j \frac{2 \pi k}{N}(N_1 + \frac{1}{2})} - e^{-j \frac{2 \pi k}{N}(N_1 + \frac{1}{2})})}{e^{-\frac{j 2 \pi k}{2N}}(e^{j \frac{2 \pi k}{2N}} - e^{\frac{-j 2 \pi k}{2N}})} \end{align*} \] So \[a_k = \frac{1}{N} \frac{sin \frac{2 \pi k}{N}(N_1 + frac{1}{2})}{sin \frac{2 \pi k}{2N}}, k \neq 0, mN\] \[a_k = \frac{1}{N} \sum_{-N_1}^{N_1} e ^{\frac{j 2 \pi k n}{N}} = \frac{2N_1 + 1}{N}\]
Let's see how this behaves
To plot $a_k$ it is convenient to consider $\frac{2 \pi k}{N} = \Omega$ \[N a_\Omega = \frac{sin \Omega (N_1 + \frac{1}{2})}{sin \frac{\Omega}{2}}\]
This is a function of a continuous variable $\Omega$. $N a_{\Omega}$ will give us an envelope of the actual Fourier series
$N a_k$ values actually only occur at $\Omega = \frac{2 \pi k}{N}$
Lets consider $N_1 = 3$. The main lobe goes to zero at $ \Omega(N_1 + \frac{1}{2}) \Rightarrow \Omega = \frac{2 \pi}{2N_1 +1}$
This does not depend on period $N$
Unlike the CTFS the plot repeats after $2 \pi$. This is because $\frac{2 \pi k}{N} = \frac{2 \pi (k + N)}{N} = \frac{2 \pi k}{N} + 2 \pi$ as far as discrete-time signals are concerned: \[e^{j(\Omega + 2 \pi)n} = e^{j \Omega n} \cdot e^{j2 \pi n} = e^{j \Omega}\]
We only get more stems in the main lobe.
Increasing N further puts more and more stems in the main lobe but doesn't increase its width (ananlogously to the CT case) and the stems will get denser.
Let us now consider the other side: partial sums.
We have: \[x[n] = \sum_{k=0}^{N-1} a_k e^{\frac{j2 \pi k n}{N}}\] \[\hat{x}[n] = \sum_{k=0}^{0}a_k e^{\frac{j2 \pi k n}{N}} = a_0 \text{ for M = 1}\]
\[\hat{x}[n] = \sum_{k=1}^{1} a_k e^{\frac{j2 \pi k n}{N}} = a_o + 2a_1 cos \frac{2 \pi k n}{N} \text{ M = 2}\]
We are choosing a symmetric range of k to get a real signal. We'd get complex signals otherwise, but the overall results show the same logic
There is no Gibbs phenomenon!
We don't observe Gibbs phenonmenon in DT periodic signals because we have only a finite number of complex exponentials.
Back