# Link between DFS, DFT, DTFT

My understanding of DFT is as follows

For a signal $x[n]$ of finite-length, the DFT is DFS of the periodic extension, $\tilde{x}[n]$, of that signal $x[n]$ and also another way to view DFT is that it’s a sampling of continuous DTFT.

Given that it is possible to reconstruct a original signal from sampled signal, provided the sampling is greater than Nyquist frequency. We know that the DTFT for sampled signal is a series of replications of the spectrum of the original signal at frequencies spaced by the sampling frequency. Now, since DTFT is continuous and periodic, we can further breakdown DTFT at intervals and still be possible to reconstruct the DTFT and consequently the original signal. This act of breaking down or sampling the DTFT is called DFT.

Is my interpretation of DFT correct? I would welcome any (true) facts or implications to test my understanding

Yes your understanding is basically correct.

The 1st paragraph (2 lines) expresses the fundamental relation between the DFS and the DFT of a finite-length sequence $x[n]$ while the 2nd paragraph tries to put down the relation between the DFT $X[k]$ of a sequence and the DTFT $X(e^{j\omega})$ of it (assuming it exists).

However this 2nd paragraph shall better be rephrased like this: given a finite length sequence $x[n]$ of length $N$ whose DTFT is:

$$X(e^{j\omega}) = \sum_{n=0}^{N-1} {x[n] e^{-j\omega n}}$$

it will have its $N$-point DFT $X[k]$ defined and computed as the uniform samples of its DTFT $X(e^{j\omega})$ taken at $N$ frequency points $\omega_k = \frac{2 \pi}{N} k$ for $k=0,1,...,N-1$ .

It's important to recognise that some important class of aperiodic signals which are of infinite length, such as $x[n] = a^n u[n]$, will not have a valid $N$-point DFT representation for any (finite) $N$, nor will it have a valid finite DFS representation as it's not a periodic signal. Such a signal requires infinitely many samples for its DFT to exactly represent it.

In practice, for the above sequence, a truncated (windowed) exponential can be used to approximate the infinite length sequence. For practical applications one can always find a large enough finite $N$ that will reduce the error of the approximation down to an acceptable level.

In addition, for infinite length aperiodic signals such as the above $x[n]=a^n u[n]$, whose DTFT $X(e^{j\omega})$ exists and is given by $X(e^{j\omega})= \frac{1}{1-a e^{-j\omega}}$ for some suitable $a$, one can think of the following scenerio: Relying on the alternate definition of DFT, $X[k]$ of a sequence as being the uniform samples of the DTFT $X(e^{j\omega})$ of that sequence $x[n]$ what happens when we take $N$ uniform samples of $X(e^{j\omega})$ as:

$$X[k] = X(e^{j\frac{2\pi k}{N}})= \frac{1}{1-a e^{-j\frac{2\pi}{N}k}} ~,~ k=0,1,...,N-1$$

And by assuming that these N-samples of DTFT, constitude a proper (valid) DFT representation of some N-point finite length sequence $x_a[n]$, we convert those $N$ DFT samples back into time domain using the $N$-point inverse DFT.

What's the relation between the finite length sequence $x_a[n]$ (that's returned by the N-point IDFT of the N uniform samples of DTFT $X(e^{j\omega})$ of the sequence $x[n] = a^n u[n]$) and the infinite length sequence $x[n] = a^n u[n]$...?

It can be shown that, $x_a[n]$ will be a time-aliased version of the infinite length signal $x[n]=a^n u[n]$ defined with the following relation:

$$\tilde{x}_a[n] = \sum_r { x[n-rN] }$$

Which can be viewed as the periodic extension of the infinite length signal $x[n]$ by N, however, the tails of $x[n]$ should sum up to finite values (converge) for $x_a[n]$ to exist. This will be the case , for example, when $|a| <1$ for the above exponential...

Furthermore, there is an important practical issue that arise when DFT is computed through an FFT using a computer program such as MATLAB/Octave. Consider the case when an even symmetric sequence h[n] has a region of support from $-M$ to $M$, lets go concrete and put $M = 2$ for simplicty and assume

$$h[n]=\delta [n+2] +2 \delta[n+1] + 3\delta[n] +2\delta [n-1] +1\delta[n-2]$$

The DTFT of such an even symmetric real sequence h[n] will be real and even (hence will have zero phase) as given by:

$$X(e^{j\omega}) = \sum_{n=-2}^{2} {x[n] e^{-j\omega n}}$$

Therefore we can conclude that its $5$-point DFT $H[k]$ will also be a real, even, zero-phase sequence. Lets compute its DFT using MATLAB :

h = [1 2 3 2 1];   % The row-vector as 1x5 matrix to hold the sequence h[n]
fft(h,5)           % DFT of h[n] ?


The output is :

9.0000  ,  -2.1180 - 1.5388i ,  0.1180 + 0.3633i ,  0.1180 - 0.3633i , -2.1180 + 1.5388i


This is not the expected result. And the reason is here MATLAB computes not the DFT of the original sequence $h[n]$ but the DFT of a shifted verison $b[n] = h[n-2]$ so that $b[n]$ is a causal sequence that begins from the index $n=0$. Using a little DTFT properties one can show that :

$$B(e^{j\omega}) = e^{-j 2\omega} H(e^{j\omega})$$

and the DFT therefore will be:

$$B[k] = e^{-j 2 \frac{2\pi}{5} k} H[k] ~,~ k=0,1,2,3,4$$

Where $H[k]$ is the samples of the zero phase DFT corresponding to even-symmetric sequence h[n] , and $B[k]$ corresponding to what MATLAB computes.

If for some reasons you have to recover $H[k]$ from $B[k]$ then you would compute: $$H[k] = e^{j 2 \frac{2\pi}{5} k} B[k] ~,~ k=0,1,2,3,4$$

as the following line of code reveals:

exp(j*2*pi*[0:4]*2/5).*fft([1 2 3 2 1],5)   % output is :
9.0000    2.6180    0.3820    0.3820    2.6180


The same result could also be obtained by the input shifting as well:

fft([3 2 1 1 2],5)