Prerequisites
To better understand this post, it is recommended to have knowledge about the following topics:
Discrete-Time Fourier Transform (DTFT)
Discrete-Time Fourier Transform is a Fourier analysis method applied to discrete signals, unlike Continuous-Time Fourier Transform which is applied to continuous signals.
The idea of deriving DTFT is similar to CTFT, where the size of the period N is made infinitely large. If the size of N approaches infinity, it becomes possible to decompose a non-periodic discrete signal.
Derivation of Discrete-Time Fourier Transform
Let’s directly substitute the values of $a_k$ into the expression of $x[n]$ for DTFS, as shown below.
\[x[n] = \sum_{k=0}^{N-1}{a_k \space \exp\left(j \frac{2\pi k}{N}n\right)}\]Taking the limit as N approaches infinity, we can obtain the following equation (3).
\[\lim_{N\rightarrow\infty}x[n] = \lim_{N\rightarrow \infty}\sum_{k=N_1}^{N_2}\left( \frac{1}{N}\sum_{n=N_1}^{N_2}x[n]\exp\left(-j\frac{2\pi n}{N}k\right) \right)\exp\left(j\frac{2\pi k}{N}n\right)\]Rearranging equation (3) and moving $\frac{1}{N}$ to the rightmost side, we get the following.
\[\lim_{N\rightarrow\infty}x[n] = \lim_{N\rightarrow \infty}\sum_{k=N_1}^{N_2}\left( \sum_{n=N_1}^{N_2}x[n]\exp\left(-j\frac{2\pi n}{N}k\right) \right)\exp\left(j\frac{2\pi k}{N}n \right)\frac{1}{N}\]Here, $N_1$ and $N_2$ are integers that satisfy the relationship $N_2-N_1+1=N$.
Due to the periodic nature of periodic signals, the shape of the signal remains the same regardless of the starting point as long as the period (here, N) is maintained.
Also, during the derivation process of equation (3) and (4), $\frac{1}{N}$ and $\frac{k}{N}$ can be replaced with $df$ and $f$ respectively as follows, as N approaches infinity.
\[as \space N \rightarrow \infty,\space\frac{1}{N}\rightarrow df\space \& \space\frac{k}{N}\rightarrow f\]I will expand equation (4), and for convenience, let’s first calculate the expression inside the parentheses: $\sum_{n=N_1}^{N_2}x[n]\exp\left(-j\frac{2\pi n}{N}k\right)$.
Here, given that $N_2-N_1+1=N$, the following equation holds:
\[N_2=N+N_1-1\] \[\Rightarrow N_1=N_2-N+1\] \[\therefore\quad as\quad N\rightarrow\infty,\quad N_1\rightarrow -\infty,\quad N_2 \rightarrow\infty\]Therefore, the expression inside the parentheses in equation (4) can be written as follows:
\[\lim_{N\rightarrow\infty} \sum_{n=N_1}^{N_2}x[n] \exp\left(-j \frac{2\pi n}{N}k\right)\] \[=\sum_{n=-\infty}^{\infty}x[n]\exp(-j2\pi f n) = X_{DTFT}(f)\]Thus, using equation (10), equation (4) can be rewritten as:
\[\lim_{N\rightarrow \infty}\sum_{k=N_1}^{N_2}X_{DTFT}(f) \exp\left(j\frac{2\pi k}{N}n\right)\frac{1}{N}\]By the definition of the definite integral and equations (5) and (8), the result of equation (7) is as follows:
\[\Rightarrow \int_{-\infty}^{\infty}X_{DTFT}(f)\exp\left(j 2\pi f n\right) df\]At this point, as mentioned in the Discrete Time Fourier Series article, the digital frequency $f$ can have a maximum range of [0,1].
Therefore, equation (12) can be written as follows:
\[\Rightarrow \int_{0}^{1}X_{DTFT}(f) \exp\left(j 2\pi fn\right)df = x[n]\]Furthermore, in general, we can consider negative frequencies as well, so it doesn’t matter if we shift the integration range from [0,1] to [-0.5, 0.5]. Therefore, we can express DTFT as follows:
For a discrete signal $x[n]$,
\[x[n] = \int_{-0.5}^{0.5}X_{DTFT}(f) \exp\left(j2\pi fn\right)df\]where
\[X_{DTFT}(f) = \sum_{n=-\infty}^{\infty}{x[n]\exp\left(-j2\pi fn\right)}\]Just like CTFT, DTFT also requires convergence conditions for $X_{DTFT}(f)$.
Since the magnitude of $\exp(-j2\pi fn)$ is 1, the convergence condition for $X_{DTFT}(f)$ is as follows:
\[|X_{DTFT}(f)| = \left|\sum_{n=-\infty}^{\infty} x[n]\exp\left(-j2\pi fn\right)\right|\leq\left|\sum_{n=-\infty}^{\infty}x[n]\right|< \infty\]