Transforms I: Fourier transform for discrete-time signals

Alternative expression pulse train

In the module sampling and reconstruction we have seen that the continuous time signal $x\left(t\right)$ can be represented by samples $x\left[n\right]$ when these samples are obtained by using an ideal C-to-D convertor which runs at a sampling frequency $f_s$ which is larger than 2 times the maximum frequency $f_{\text{max}}$ of the continuous time signal $x\left(t\right)$. Here we will assume that this is the case, so there is no aliasing.

In the development of the FTD we will use the model of an ideal C-to-D convertor as depicted in Fig. 1. In this model we first represent the discrete-time samples $x\left[n\right]$ by the continuous time signal $x_s\left(t\right)$, which is obtained by multiplying the continuous time signal $x\left(t\right)$ by a continuous-time signal $s\left(t\right)$ which is an infinite train of continuous-time delta pulses with an inter-pulse distance of $T_s=1/f_s$ seconds.

Although this intermediate continuous-time signal $x_s\left(t\right)$ can never be realized in practice, it is very useful in the following conceptual derivation of the FTD.

In the module Fourier Transform for Continuous-time signals we have derived the following alternative expression for this infinite train of continuous-time delta pulses $s\left(t\right)$ as an infinite sum of phasors: $$s\left(t\right)=\sum _{n=-\infty }^{\infty }\delta (t-n\cdot T_s)\widehat{=}\frac{1}{T_s}\sum _{k=-\infty }^{\infty }{e}^{j\frac{2\pi }{T_s}kt}$$ The reasoning behind this equality can be shown by Fig. 2. The figure at the left hand side indicates an example of the phasor terms of the summation for any continuous time variable $t$ which is not equal to $n\times T_s$.

In such cases, the phasors terms in the summation, which are unit length vectors, can have any angle. There will be an infinite amount of these unit length vectors with positive imaginary part, colored in blue, and with negative imaginary part, colored in red. As a result of this infinite amount of vectors, for each blue vector there will be a red vector in opposite direction which cancel each other and the result is that the summation of all these phasors will add up to zero. Only for values of the continuous-time variable $t\ne n\times T_s$, all phasor terms of the summation are equal to one and are all on top of each other. The result of the summation for this case is infinite, which is indicated at the right hand side of the figure. Thus the infinite summation of phasors can indeed be represented by an infinite train of delta pulses with an inter distance of $T_s$ seconds, as depicted in the equation above.

In the following subsection we will use this equality in the derivation of the FTD.

FTD concept

In this subsection we will derive the FTD by using frequency domain descriptions of signals $x\left(t\right),x_s\left(t\right)$ and $x\left[n\right]$, as indicated in Fig. 1 of the mathematical model of the ideal C-to-D convertor.

Assume we are given a continuous time signal $x\left(t\right)$ and its FTC $X\left(\omega \right)$. The maximum radian frequency of $x\left(t\right)$ is ${\omega }_m$, as depicted in the top figure Fig. 3.

As a result of the definition of an impulse train we can write the intermediate continuous-time signal $x_s\left(t\right)$ as follows: $$x_s\left(t\right)=x\left(t\right)\cdot \frac{1}{T_s}\sum _{k=-\infty }^{\infty }{e}^{j\frac{2\pi }{T_s}kt}=\frac{1}{T_s}\sum _{k=-\infty }^{\infty }x\left(t\right)\cdot e^{j{\omega }_{s}kt}\text{with}{\omega }_s=\frac{2\pi }{T_s}$$ This equation allows us to apply the frequency shift property to obtain the FTC of $x_s\left(t\right)$: $$X_s\left(\omega \right)=\frac{1}{T_s}\cdot \sum _{k=-\infty }^{\infty }X(\omega -k\cdot {\omega }_s),$$ which is a periodic function of $\omega$ with period ${\omega }_s=\frac{2\pi }{T_s}$. As depicted in the middle figure of Fig. 3, $X_s\left(\omega \right)$ (in green) gives the spectral representation of $x_s\left(t\right)$ in terms of shifted copies of $X\left(\omega \right)$, the FTC of the continuous-time signal $x\left(t\right)$. On the other hand if we express $x_s\left(t\right)$ as an infinite train of continuous-time delta pulses $x_s\left(t\right)=x\left(t\right)\cdot {\sum }_{n=-\infty }^{\infty }\delta (t-n\cdot T_s)$ and using the delay property of the FTC, it follows that an equivalent relation for $X_s\left(\omega \right)$ can be given by the following equation: $$X_s\left(\omega \right)=\sum _{n=-\infty }^{\infty }x\left(t\right){|}_{t=n{T}_s}{e}^{-j\omega n{T}_s}$$ which expresses $X_s\left(\omega \right)$ in terms of the sampled values $x\left(t\right){\mid }_{t=n{T}_s}$ of the continuous-time signal $x\left(t\right)$. Because of the exponential functions, as well as the description of $X_s\left(\omega \right)$ this form of $X_s\left(\omega \right)$ is periodic in $\omega$ with period ${\omega }_s=\frac{2\pi }{T_s}$. Furthermore by representing the sampled values $x\left(t\right){\mid }_{t=n{T}_s}$ by the samples $x\left[n\right]$ and using the relative frequency $\theta =\omega \cdot T_s$ we can rewrite the above equation as: $$X\left(e^{j\theta }\right)=\sum _{n=-\infty }^{\infty }x\left[n\right]e^{-jn\theta }$$ in which the periodicity of this function is denoted by expressing the continuous function variable $\theta$ as an exponent. This equation transforms the discrete-time samples $x\left[n\right]$ into a continuous periodic relative frequency domain function $X\left(e^{j\theta }\right)$ and as such it represents the Fourier Transform of Discrete-time signals (FTD). From the equivalence of the spectra $X_s\left(\omega \right)$ and $X\left(e^{j\theta }\right)$ it follows that the FTD can be viewed in terms of shifted copies of $X\left(\omega \right)$. Finally, as depicted in the lower figure of Fig. 3, it follows from $\theta =\omega \cdot T_s$ that the period of $X\left(e^{j\theta }\right)$ is equal to $2\pi$. Only one period is necessary to represent $X\left(e^{j\theta }\right)$, which is called the Fundamental Interval (FI). In most cases we will use for the FI the period in between $-\pi$ and $+\pi$.

Inverse FTD

By using the fact that $X\left(e^{j\theta }\right)$ is a periodic function we can use the Fourier Series (FS) representation to find inverse of the FTD expression. For this reason we recall the FS definition which implies that any periodic function $x_p\left(t\right)$, with period $T_0=1/F_0$, can be represented as an infinite sum of weighted phasors while in the inverse case the weights ${\alpha }_k$ can be evaluated by an integral over one period, as denoted in the following equations: $$x_p\left(t\right)=\sum _{k=-\infty }^{\infty }{\alpha }_k{e}^{j2\pi k{F}_{0}t}\circ -\circ {\alpha }_k=\frac{1}{T_0}{\int }_{-T_0/2}^{T_0/2}{x}_p\left(t\right)e^{-j2\pi k{F}_{0}t}dt$$

In our case we change time and frequency dimensions of the FS equations. Furthermore the periodic function is $X\left(e^{j\theta }\right)$ with period $2\pi$ and the ‘weights’ are represented by the samples $x\left[n\right]$. Now by using the FS equation for the ‘weights’ $x\left[n\right]$ this results in the following expression for the Inverse FTD: $$x\left[n\right]=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }X\left(e^{j\theta }\right)e^{jn\theta }\text{d}\theta$$ Given the periodic expression $X\left(e^{j\theta }\right)$ as a function of the continuous relative frequency $\theta$ this equation defines the way to compute the discrete-time samples $x\left[n\right]$.

Differences FTC and FTD

Both FTC and FTD have similarities but are different. That is why the most important aspects of both transformations are summarized here.

Based on absolute frequency $f$ in Hertz, the FTC and IFTC equations are: $$\begin{array}{ccc}FTC:X\left(f\right)={\int }_{-\infty }^{\infty }x\left(t\right)e^{-j2\pi ft}dt& \circ -\circ & x\left(t\right)={\int }_{-\infty }^{\infty }X\left(f\right)e^{j2\pi ft}df\end{array}$$ which alternatively can be expressed based on the absolute radian frequency $\omega$ in radians per second as follows: $$\begin{array}{ccc}FTC:X\left(\omega \right)={\int }_{-\infty }^{\infty }x\left(t\right)e^{-j\omega t}dt& \circ -\circ & x\left(t\right)=\frac{1}{2\pi }{\int }_{-\infty }^{\infty }X\left(\omega \right)e^{j\omega t}d\omega \end{array}$$

Important aspects of these transforms are:

• The continuous time signal $x\left(t\right)$ is not periodic,
• The frequency representation $X\left(\omega \right)$ is a continuous function and not periodic,
• Both FTC and IFTC are evaluated by an integral,
• Finally we will use these notations for the FTC and IFTC: $$X\left(\omega \right)=F\left\{x\right(t\left)\right\}\text{and}x\left(t\right)=F^{-1}\left\{X\right(\omega \left)\right\}$$

The FTD and IFTD equations are as follows: $$\begin{array}{ccc}FTD:X\left(e^{j\theta }\right)=\sum _{n=-\infty }^{\infty }x\left[n\right]e^{-jn\theta }& \circ -\circ & x\left[n\right]=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }X\left(e^{j\theta }\right)e^{jn\theta }d\theta \end{array}$$ Important aspects of these transforms, which differ from the FTC and IFTC equations, are:

• The signal samples $x\left[n\right]$ are discrete in time and not periodic,
• The normalized frequency $\theta =\omega \cdot T_s$,
• The Fundamental Interval is usually chosen as: $-\pi \le \theta <\pi$,
• The frequency representation $X\left(e^{j\theta }\right)$ is a continuous function and periodic,
• The FTD is evaluated over an infinite summation of samples $x\left[n\right]$,
• The IFTD is evaluated by an integral over one period of the frequency representation $X\left(e^{j\theta }\right)$.
• Finally, to make a clear distinction we will use the following notations for the FTD and IFTD: $$X\left(e^{j\theta }\right)=F\left\{x\right[n\left]\right\}\text{and}x\left[n\right]=F^{-1}\left\{X\right(e^{j\theta }\left)\right\}$$