3
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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}} \tag{1} $$

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 most practical cases, for an exponentially decaying sequence, a truncated (windowed) finite length, long enough, portion of it can be used to approximate the infinite length sequence. One can always find a large enough finite $N$ that will reduce the error of the approximation down to an acceptable level. (There's also an exact relation even for finite $N$ as will be shown below.)

For infinite length aperiodic signals, such as the above $x[n]=a^n u[n]$, whose DTFT is $X(e^{j\omega})= \frac{1}{1-a e^{-j\omega}}$ for $|a|<1$, one can think about the following: according to the relation of DFT to DTFT, the DFT $X[k]$ is the uniform samples of the DTFT $X(e^{j\omega})$ of that sequence $x[n]$ :

$$ 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 \tag{2}$$

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 an $N$-point inverse DFT. Then what's the relation between the finite length sequence returned by the N-point IDFT (of the N uniform samples of the DTFT $X(e^{j\omega})$ of $x[n]$) and the infinite length sequence $x[n] = a^n u[n]$..?

It can be shown that, the returned sequence, I denote $x_a[n]$, will be a time-aliased version of the infinite length sequqence $x[n]$ defined with the following relation:

$$ x_a[n] = \sum_r { x[n+rN] } \tag{3} $$

Which can be viewed as the periodic extension of the infinite length sequence $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 $x[n] = a^n u[n]$ with $|a| <1$ .

Note that for the class of complex exponential sequences $x[n]=a^n u[n]$, this aliasing can be corrected, based on an explicit relation between $x_a[n]$ and the parameter $a$ of $x[n]$. The relation between $x[n]=a^n u[n]$ and the aliased sequence $x_a[n]$ indicated by Eq.(3) turns out to be:

$$ x_a[n] = \frac{1}{1-a^N} x[n] \tag{4} $$

For other classes of sequences, such a relation may or may not exist, and an inversion from the aliased sequence $x_a[n]$ into the infinite length sequence $x[n]$, in general is not possible.

From Eq.4, the parameter $a$ of the actual exponential sequence $x[n] = a^n u[n]$ whose DTFT was sampled to obtain the N-point DFT $X[k]$ can be found as :

$$ a^N = \frac{ x_a[0] - 1 }{x_a[0]} \tag{5}$$

Note, however, that it's not a practical attempt.

Another important note about the relation between the sequence $x[n]$, its DTFT $X(w)$, and the DFT $X[k]$ of $x[n]$, is about a practical issue that arise when DFT is computed through an FFT call within a program, such as MATLAB/Octave.

Basically it's about an implicit alignment of the data seqeunce $x[n]$ to begin at $n=0$. DFT assumes that $x[n]$ is a causal sequence and it considers samples of input only for $0 \le n \le N-1$. This will cause a phase error at the computed DFT samples of a non-causal sequence if the DFT input is not properly constructed to yield the expected DFT result.

Consider we want to compute DFT of an even symmetric sequence $h[n]$ with a region of support $-M \le n \le M$ . Let $M = 2$ for the example.

$$h[n]=\delta [n+2] +2 \delta[n+1] + 3\delta[n] +2\delta [n-1] +\delta[n-2] \tag{6} $$

$h[n]$ is not a causal sequence; but a standard FFT function (withing MATLAB/OCTAVE) cannot know this, and treats the first sample of its input to be at $n=0$. This will cause a phase shift on the computation and the resulting discrepancy between the true DFT values of the actual non-causal sequence $h[n]$ and the constructed causal equivalent $h_c[n]$, should be remebered and be explicitly taken care of by the user, if the phase information of the DFT is important (Magnitudes will not be affected).

Lets call the causal extension of the input $h[n]$ as $h_c[n]$. We can define it in two ways as :

$$ h_c[n] = h[n-2] ~~~,~~~ n=0,1,2,3,4,5 \tag{7}$$ or $$ h_c[(n-2)_N] = h[n-2] ~~~,~~~ n=0,1,2,4,5 \tag{8} $$

where $(n-2)_N$ indicates a modulus_N operation; i.e. $$(n-2)_N = \text{mod}(n-2,N) \tag{9}$$

Note that Eq.7 treats the sequences $h[n]$ and $h_c[n]$ defined for all $-\infty < n < \infty$, and performs a linear shift on the non-causal sequence to obtain $h_c[n]$. On the other hand, Eq.8 treats them as periodic sequences with a predefined period $N$ and performs a circular shift on $h[n]$ to obtain $h_c[n]$.

$h_c[n]$ according to Eq.7 becomes $h_c[n] = [1,2,3,2,1] $,whereas according to Eq.8 it is $h_c[n]= [3,2,1,1,2]$.

In a more general setting, when the non-causal sequence has its non-zero samples for $a \le n \le b$, $a<0$, and is zero when $n < a$ or $b<n$, the linear shifted causal sequence of length $N \ge b-a+1$ is obtained as:

$$ h_c[n] = h[n+a] ~~~,~~~ 0 \le n < N \tag{10} $$ and the circularly shifted causal sequence obtained as :

$$ h_c[(n+a)_N] = h[n+a] ~~~, ~~~ 0 \leq n < N \tag{11}$$ Eq.11 can be split into two pieces in the range $0\leq n < N$ as: $$ h_c[n] = h[n] ~~~,~~~ 0 \le n \le b \tag{11.a}$$ $$ h_c[n] = h[n-N] ~~~,~~~ N+a \leq n \le N-1 \tag{11.b}$$

Having defined the non-causal $h[n]$ and its N-point causal extensions according to Eqs. 10 & 11, the next step is to compute and relate their DTFTs:

For the linearly shifted sequence $h_c[n]$, it's easy to see that : $$ H_c(e^{j \omega}) = e^{ j\omega a } H(e^{j \omega}) \tag{12}$$ This follows directly from the DTFT properties of a linear shift.

For the circularly shifted sequence, $h_c[n]$, the relation is more complex at first, but it can be seen that at the DFT sampling frequencies $w_k = \frac{2\pi}{N} k$, the relation simplifies to : $$ H_c(e^{j \omega_k}) = H(e^{j \omega_k}) \tag{13}$$

This result in Eq.(13) may seem surprising at first but can be derived from splitting the DTFTs into two pieces as follows : $$ \begin{align} H_c(e^{j \omega}) &= \sum_{n=0}^{N-1} h_c[n] e^{-j \omega n} \\ &= \sum_{n=0}^{b} h_c[n] e^{-j \omega n} + \sum_{n=N+a}^{N-1} h_c[n] e^{-j \omega n} &\text{h_c[n] =0 for b< n < N+a} \\ &= \sum_{n=0}^{b} h[n] e^{-j \omega n} + \sum_{n=N+a}^{N-1} h[n-N] e^{-j \omega n} &\text{replace hc[] by h[] via Eq.11} \\ &= \sum_{n=0}^{b} h_c[n] e^{-j \omega n} + \sum_{n=a}^{-1} h[n] e^{-j \omega (n+N)} &\text{substitude n-N} \\ &= e^{-j\omega N} \big( \sum_{n=a}^{-1} h[n] e^{-j \omega n} \big) + \sum_{n=0}^{b} h[n] e^{-j \omega n} &\text{reorder the sums} \\ H_c(e^{j\omega_k})&= e^{-j\omega_k N} \big( \sum_{n=a}^{-1} h[n] e^{-j \omega_k n} \big) + \sum_{n=0}^{b} h[n] e^{-j \omega_k n} &\text{w_k =2pi k/N} \\ H_c(e^{j\omega_k})&= \sum_{n=a}^{-1} h[n] e^{-j \omega_k n} + \sum_{n=0}^{b} h[n] e^{-j \omega_k n} &\text{e^(-j\omega_k N)= 1} \\ H_c(e^{j\omega_k})&= \sum_{n=a}^{b} h[n] e^{-j \omega_k n} &\text{merge the sums} \\ H_c(e^{j\omega_k})&= H(e^{j \omega_k}) &\text{RHS: DTFT of h[n] at wk} \\ \end{align} $$

Hence we see that eventhough the DTFTs of circularly shifted causal sequence $h_c[n]$ and non-causal sequence $h[n]$ are not the same for arbitrary $\omega$, when evaluated at the DFT frequencies $\omega_k = \frac{2\pi}{N}k$ , they become equal :

$$ H_c(e^{j\frac{2\pi}{N}k}) = H(e^{j\frac{2\pi}{N}k}) ~~~,~~~ k=0,1,...,N-1 \tag{14}$$

Now, we can compute N-point DFTs by sampling the corresponding DTFTs at the DFT frequencies. Which indicates the following.

For the linearly shifted causal sequence $h_x[n]$ of Eq.10, we have

$$ H_c[k] = H_c(e^{j\frac{2\pi}{N}k}) = e^{j\frac{2\pi}{N}k a} \cdot H(e^{j\frac{2\pi}{N}k}) = e^{j\frac{2\pi}{N}k a} H[k] \tag{15} $$

and for the cirularly shifted causal sequence $h_c[n]$ according to Eq.11, we simply have $$ H_c[k] = H_c(e^{j\frac{2\pi}{N}k}) = H(e^{j\frac{2\pi}{N}k}) = H[k] \tag{16} $$

Now in the Eq. 15 &16 above, the quantitiy $H[k]$ on the RHS is the desired DFT of the non-causal sequence $h[n]$, whereas the quantity $H_c[k]$ on LHS is the actually computed DFT by MATLAB/OCTAVE fft() function when feeded with linearly or circularly shifted sequences $h_c[n]$ respectively.

From Eq. 15 it's seen that for the linearly shifted sequence we have a phase error by $e^{j\frac{2\pi}{N}k a}$ and to get the correct (desired) DFT samples of $H[k]$ we have to reverse it; i.e.,

$$ H[k] = e^{-j\frac{2\pi}{N}k a} H_c[k] ~~~, ~~~k=0,1,...,N-1 \tag{17}$$

From Eq.16 we see that the DFT samples $H_c[k]$ of the circularly shifted causal sequence (Eq.11) $h_c[n]$ is exactly identical to the samples of the desired DFT $H[k]$ of $h[n]$. Hence we get the desired DFT result without error, if we feed the fft() function with the samples of the circularly shifted causal sequence.

Below is a MATLAB demonstration of the above discussion based on the given even symmetric sequence $h[n]$. DTFT of such an even symmetric real sequence will be real and even (hence will have zero phase) as given by:

$$H(e^{j\omega}) = \sum_{n=-2}^{2} {H[n] e^{-j\omega n}} = 3 + 4 \cos(\omega ) + 2 \cos(2\omega)$$

Therefore its $N=5$-point DFT $H[k]$ will also be a real, even, and zero-phase sequence as give below : $$ H[k] = [9.0000, 2.6180, 0.3820, 0.3820, 2.6180] $$

Lets compute the desired DFT $H[k]$ using MATLAB :

hc = [1 2 3 2 1];   % linearly shifted causal sequence hc[n] acc to Eq 10
fft(hc,5)           % Hc[k] = 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. MATLAB computes not the DFT of the original sequence $h[n]$ but the DFT of the linearly shifted verison $h_c[n]$

To recover $H[k]$ from $H_c[k]$ : $$ H[k] = e^{ j~ 2 \frac{2\pi}{5} k} ~ H_c[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

This final desired result could be obtained directly (without correction) by using the circularly shifted causal sequence $h_c[n] = [3,2,1,1,2]$ as the input to the fft() :

H = fft([3 2 1 1 2],5)
9.0000    2.6180    0.3820    0.3820    2.6180
| improve this answer | |
$\endgroup$
  • $\begingroup$ I really like this answer, until the part about suggesting the FFT and Matlab and other programs introduce a shift that really isn't part of the DFT- which I found confusing. I thought the DFT was defined as starting from M=0, as it assumes causal time functions--- such as en.wikipedia.org/wiki/Discrete_Fourier_transform --- Do you disagree? (Especially for someone reading it less familiar it seems confusing) The underlying phase shift is the DFT itself and is a good point but n in time and k in frequency typically always start at 0 and seemed to defined as such. $\endgroup$ – Dan Boschen Apr 16 at 3:19
  • 1
    $\begingroup$ @DanBoschen Yes it is not clear. In fact you should consider circular shift to compansate the nonzero phase computation of the DFT... $\endgroup$ – Fat32 Apr 16 at 18:21
1
$\begingroup$

Let $x(t)$ be an infinite analog signal, and $w$ be a rectangular window function non-zero on $[-T,T]$. Let us fix the sampling rate $F_s$ and let $N$ be the DFT size.

The DFT of $x(t)w(t)$ limits to the DTFT as $N\rightarrow\infty$ i.e. increasing interpolating the DTFT (note since $F_s$ is fixed we must be sampling where $w$ is zero also).

Now let $F_s\rightarrow\infty$. The DTFT of $x(t)w(t)$ will approach the CTFT (the DTFT is a periodic approximation of the CTFT with period $F_s$).

Now let $T\rightarrow\infty$. The CTFT of $x(t)w(t)$ will approach that of $x(t)$.

| improve this answer | |
$\endgroup$

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.