content

  • to explore application of Fourier analysis to the three different classes of signals,
    • finite-length signals,
    • periodic signals and
    • infinite-length signals

DFT

  • we have already looked in details at the case of finite-length signals where the DFT is the Fourier tool of choice

  • an interesting property of the DFT:
    • if we let the DFT synthesis run beyond \( N-1 \), we obtain a \( N \)-periodic signal \( x[n + N] = x[n]x[n+N]=x[n] \)
  • likewise, the analysis formula produces also a \( N \)-periodic series of Fourier coefficients
    • the concept of DFT naturally extends to periodic sequences
  • discrete Fourier series (DFS) will be addressed in the case of periodic sequences
    • the Karplus-Strong algorithm will be revisited to illustrate a key point of this Fourier Representation

DFS (Discrete Fourier Series)

  • DFS = DFT with periodicity explicit

  • DFS maps:
    • an \(N\)-periodic signal onto
    • an \(N\)-periodic sequence of Fourier coefficients
  • inverse DFS maps an:
    • \(N\)-periodic sequence of Fourier coefficients
    • a set onto an \(N\)-periodic signals
  • the DFS of an \(N\)-periodic signal is mathematically equivalent to the DFT of one period

finite-length time shifts

  • DFS helps us understand how to define time shifts for finite-length signals

  • for an \(N\)-periodic sequence \( \tilde{x}[n] \)
    • \( \tilde{x}[n - M] \) is well-defined for all \(M \in N \)
  • DFS: \( \{ \tilde{x}[n - M] \} = e^{-j\frac{2\pi}{N}Mk}\tilde{X}[k] \)
  • Inverse DFS: \( \{ e^{-j\frac{2\pi}{N}Mk}\tilde{X}[k] \} = \tilde{x}[n-M] \)
    • \( e^{-j\frac{2\pi}{N}Mk} \): delay factor in frequency domain
  • for an \(N\)-point signal \( x[n]\):
    • \( x[n-M] \) is not well-defined
    • build \( \tilde{x}[n] = x[n \text{ mod } N] \Rightarrow \tilde{X}[k] = X[k]\)
    • mathematically, DFS of this signal is equal to the DFT of the original signal
  • so, inverse DFT is the same as the inverse DFS of the same quantity
    • IDFT\( \{ e^{-j\frac{2\pi}{N}Mk} X[k] \} = \) IDFS \( \{ e^{-j\frac{2\pi}{N}Mk} X[k] \} \)
    • \( \tilde{x}[n - M] = x[(n - M)] \text{ mod } N \)
  • shifts for finite-length signals are naturally circular
    • circular shifts are natural extension of shift operator
    • underlying fourier representation is the same as the one used for a periodic signal built on the finite-length signal

periodic-sequences

  • \(N\)-periodic sequence: \( N \) degrees of freedom

  • DFS: only \(N\) fourier coefficients capture all the information

  • Karplus-Strong algorithm

    ks-algo

    fig: Karplus-Strong algorithm

    • this can be used to generate a simple periodic signal
    • choose a finite-support signal \( \bar{x}[n] \) that is non-zero only for \( 0 \leq n < M \)
    • choose \(\alpha = 1\): no attenuation in loop
      • \( y[n] = \bar{x}[0],\bar{x}[1],\ldots,\bar{x}[M-1],\bar{x}[0],\bar{x}[1],\ldots,\bar{x}[M-1],\bar{x}[0],\bar{x}[1],\ldots\)
      • \(1^{st}\) period, \(2^{nd}\) period

    ks-algo

    fig: 32-tap sawtooth-wave input to Karplus-Strong algorithm

    • the output of the Karplus-Strong algorithm will be a period saw-tooth signal wave with the input saw-tooth as the input

    ks-algo

    fig: DFT of output of Karplus-Strong algorithm

spectral information

  • all the spectral information of a periodic signal is contained in the DFT of a single period
    • so a DFS is used for a periodic signal
  • if we take the DFT of L repetitions of a finite length sequence of length \(N\), we obtain a series which is non-zero only at multiple integers of L
  • these non-zero coefficients are just scaled versions of the DFT coefficients of the original finite-length sequence
    • all the spectral information of an \(N\)-periodic sequence is entirely captured by the DFT coefficients of one period

discrete-time fourier transform (DTFT)

  • the Fourier tool of choice for infinite length sequences
  • derive an intuition from the Karplus-Strong algorithm
  • we will then consider the DTFT more formally, in particular, studying conditions related to its existence and its properties
  • it is a special type of basis expansion in the space of infinite sequences

fourier representation for signal classes

  • \(N\)-point finite-length: DFT
  • \(N\)-point periodic: DFS

  • infinite length (non-periodic): DTFT

  • Karplus-Strong to generate infinite-length:
    • set \(\alpha < 1\)
    • generated signal is infinite-length but not periodic
    • \( y[n] = \bar{x}[0],\bar{x}[1],\ldots,\bar{x}[M-1], \); \(1^{st}\) period
      • \( \alpha \bar{x}[0], \alpha \bar{x}[1],\ldots,\alpha \bar{x}[M-1], \) \(2^{nd}\) period
      • \( \alpha^2 \bar{x}[0], \alpha^2 \bar{x}[1],\ldots \)
  • what is a good spectral representation for infinite-length signals?
    • start with DFT and asses what happens when the signal length grows towards \( \infty \)
      • \( \frac{2\pi}{N}k \text{ becomes denser in } [0,2\pi] \)
    • in the limit \( \frac{2\pi}{N}k \rightarrow \omega \):
      • \( \sum_{n}x[n]e^{-j\omega n}\), \( \omega \in \mathbb{R}\)

dtft - formally

  • \( x[n] \in \ell_2(\mathbb{Z}) \): square-summable i.e. finite energy
  • define the function of \( \omega \in \mathbb{R} \) (not the series itself)
    • \( F(\omega) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n} \)
  • inversion (when \(F(\omega) \) exists:
    • \( x[n] = \frac{1}{2\pi} \int_{-\pi}^{\pi} F(\omega)e^{j \omega n} d\omega \); \( n \in \mathbb{Z} \)

dtft periodicity and notation

  • \( F(\omega) \) is \(2\pi\)-periodic
  • to stress periodicity, it is written so:
    • \( X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n]e^{-j\omega n} \)
  • by convention, \( X(e^{j\omega}) \) is represented over \( [-\pi,\pi] \) for DTFT

dtft examples

exponentially decaying sequence

  • consider a exponentially decaying example

    exp-decay

    fig: exponentially decaying sequence - \(x[n] = \alpha^n u[n], \vert\alpha\vert < 1 \)

    • this sequence is infinite and non-periodic

  • applying DTFT to this: \[ X(e^{j \omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j \omega n} \] \[ = \sum_{n=0}^{\infty} \alpha^n e^{-j \omega n} \] \[ = \sum_{n=0}^{\infty} (\alpha e^{-j \omega})^{n} \] \[ = \frac{1}{1-\alpha e ^ {(-j \omega)}} \]

  • magnitude of the fourier transform: \[ \vert X(e^{j \omega}) \vert ^2 = \frac{1}{1 + \alpha^2 - 2 \alpha \cos \omega} \]

  • plotting DTFT:

    dtft-03

    fig: dtft of \(x[n] = \alpha^n u[n], \vert\alpha\vert < 1\)

  • most energy is consolidated around the low-frequencies
    • it moves slowly to zero
    • remember the inherent fourier transform
    • if the frequency axis is expanded out of the \( [-\pi,\pi] \) range, the signal repeats with a periodicity of \( 2\pi \)

    dtft-04

    fig: periodicity of dtft

  • DTFT frequency distributions

    dtft-00

    fig: positive frequencies

    dtft-01

    fig: negative frequencies

    dtft-02

    fig: slow and fast frequencies

infinite-support sawtooth

  • generate first an infinite-support non-periodic signal
    • then compute spectrum with DTFT paradigm
  • the Karplus-Strong algorithm will be used to generate the non-periodic infinite length signal
    • a sawtooth input is used as the initial data

dtft-05

fig: input signal for Karplus-Strong algorithm

  • the output of the Karplus-Strong algorithm is shown below

dtft-06

fig: output of the Karplus-Strong algorithm (exponentially-decaying saw-tooth wave), \( \alpha < 1\)

  • DTFT of this exponentially-decaying saw-tooth wave

\( \begin{equation} Y(e^{j\omega}) = \sum_{n=-\infty}^{\infty} y[n] e^{-j \omega n} \
= \sum_{p=0}^{\infty} \sum_{n=0}^{M-1} \alpha^{p} \bar{x}[n] e^{-j \omega (pM + n)} \
= \sum_{p=0}^{\infty} \alpha^{p} e^{-j \omega Mp} \sum_{n=0}^{M-1} \bar{x}[n] e^{-j \omega (pM + n)} \
= A(e^{j\omega M}) \bar{X}(e^{j \omega}) \end{equation} \)

  • this indicates a rescaling of the frequency axis

  • DTFT of the exponential decay output of the Karplus-Strong algorithm

    • the first and the second term of the product are dealt with separately

    • first term: \( A(e^{j\omega M})\):

    dtft-07

    fig: DTFT of KS-algorithm output; M = 1; first term of product

    dtft-08

    fig: DTFT of KS-algorithm output; M = 2; first term of product

    dtft-09

    fig: DTFT of KS-algorithm output; M = 3; first term of product

    dtft-10

    fig: DTFT of KS-algorithm output; M = 12; first term of product

    • second term: \( \bar{X}(e^{j \omega}) \)
      • \( = e^{j \omega} \Big( \frac{M + 1}{M - 1} \Big) \frac{1 - e ^{-j (M-1) \omega }}{(1-e^{-j \omega})^2} - \frac{1 - e^{-j(M+1)\omega}}{(1 - e ^{-j\omega})^2}\)

    dtft-11

    fig: DTFT of KS-algorithm output - second term of product

    • final spectrum: \( Y(e^{j\omega}) = A(e^{j\omega M}) \bar{X}(e^{j \omega}) \)

    dtft-12

    fig: DTFT of KS-algorithm output - second term of product

    • this is the DTFT (spectrum) of an infinite non-periodic signal that is not trivial
    • peaks of the first term in the product slim down the lobes of the second term

  • here DTFT is treated as a signal operator

    • it is a function of a real variable \( \omega \)
    • DTFT is NOT an extension of the DFT for finite-length signals
      • it is it’s own paradigm for infinite-length signals
    • DTFT is \(2 \pi \) periodic, hence it is written as a function of \( e^{j\omega} \)

existence and properties of DTFT

  • existence simply means the sum that defines the dtft does not blow up

    • easy to prove for absolutely summable sequences

      \( \begin{equation} \vert X(e^{j\omega}) \vert = \vert \sum_{n=-\infty}^{\infty} x[n] e^{-j \omega n} \vert \
      \leq \sum_{n= -\infty }^{\infty} \vert x[n] e^{-j \omega n} \vert \
      = \sum_{n= -\infty}^{\infty} \vert x[n] \vert \
      < \infty \end{equation} \)

  • if we assume absolute summability of the underlying sequence
    • we can invert the DTFT

    • begin with the inversion formula on LHS

      \( \begin{equation} \frac{1}{2\pi} \int_{\pi}^{pi} X(e^{j \omega}) e^{j\omega n}d\omega \
      = \frac{1}{2\pi} \int_{\pi}^{\pi} \Big( \sum_{k=-\infty}^{\infty} x[k]e^{-j\omega k} \Big) e^{j\omega n}d\omega \
      = \sum_{k=-\infty}^{\infty} x[k] \int_{\pi}^{\pi} \frac{e^{j\omega (n-k)}}{2\pi}d\omega \
      = x[n] \end{equation} \)

a formal change of basis

  • a DTFT looks exactly like an inner-product in \( \mathbb{C}^{\infty} \) space \[ \sum_{n = -\infty}^{\infty} x[n] e^{-j \omega n} = \langle e^{j\omega n},x[n]\rangle\]

  • \( \mathbb{C}^{\infty} \) is not a well-defined vector space
    • there are many sequences that do not converge in this space
  • but, if a formal parallel between a change of basis and the DTFT is established
    • then everything discovered about the DFT (which is well defined) will apply to the DTFT as well
  • here, the DTFT basis is not really a basis, because it is an infinite and uncountable set of vectors
    • indexed by a real values variable \( \omega \)
    • \( \{ e^{j \omega n} \}_{\omega \in \mathbb{R}} \)
  • something breaks down
    • start with sequences but the transformation is a function
    • DTFT exists for all square-summable sequences (larger set of sequences)
      • but absolutely summable sequences was used

review

  • comparison of DFT, DFS and DTFT
    • change of basis
    • basis vector set
    • inversion
    • time and frequency domains

DFT

  • for finite-length signals

    dft-13

    fig: DFT: change of basis from original sequence in time domain to frequency domain and back via inversion

  • here, the time domain sequence and the corresponding frequency domain entity after change of basis lives in \( \mathbb{C}^N\)
  • the basis which allows going from time domain to frequency domain is the DFT basis
    • this is a countable set for \(N \) fourier basis vectors

DFS

  • for periodic signals

    dfs-14

    fig: DFS: change of basis from a periodic in time domain to frequency domain and back via inversion

  • the expansion and reconstruction formulas are the same
  • except in this case we assume everything is periodic

DTFT

  • for infinite-length signals

    dtft-15

    *fig: DTFT: change *

  • start from space of square-summable sequences \( \ell_2(\mathbb{Z}) \), through a “formal” change of basis,

    • the original sequence is projected onto a space of square integrable functions \(L_2[-\pi,\pi]\)
    • on the interval \( [-\pi,\pi] \)

DTFT properties

  • linearity follows from the properties of the inner-product \[ DTFT\{\alpha x[n] + \beta y[n] \} = \alpha X(e^{j \omega}) + \beta Y(e^{j\omega}) \]
    • DTFT of a linear combination of two sequences will be linear combination of the DTFT of the sequences
  • time-shift: \[ DTFT\{ x[n-M] \} = e^{-j \omega M} X( e^{j \omega} ) \]
    • the DTFT of a sequence shifted by \( M \) is the DTFT of the original sequence scaled by a delay factor
      • delay factor: \( e^{-j \omega M} \)
  • modulation: \[ DTFT\{ e^{j \omega_0 n} x[n] \} = X( e^{j (\omega - \omega_o)} ) \]
    • if we take a sequence and multiply it with a complex exponential at frequency \( \omega_0 \) and take the DTFT of that,
      • that is same as applying a shift of \( \omega_0 \) to the spectrum obtained by DTFT
  • time-reversal \[ DTFT\{ x[-n] \} = X(e^{-j \omega}) \]
    • fourier transform of a time reversed sequence (values flipped about the origin) is equal to a frequency reversed Fourier Transform
  • conjugation \[ DTFT\{ x^*[n] \} = X^*(e^{-j \omega}) \]
    • if every value of the sequence is conjugated, the fourier transform will be both conjugated and frequency reversed

useful particular cases

  • if a signal sequence \(x[n]\) is symmetric, the DTFT is symmetric \[ x[n] = x[-n] \Leftrightarrow X(e^{j\omega}) = X(e^{-j\omega}) \]

  • if sequence \(x[n]\) is real, DTFT is Hermitian-symmetric \[ x[n] = x^*[n] \Leftrightarrow X(e^{j\omega}) = X^*(e^{-j\omega}) \]
    • reality of the sequence can be expressed mathematically by \(x[n] = x^*[n]\)
    • this in frequency domain implies that fourier transform of the sequence is equal to the conjugate and frequency reversed version of the fourier transform
  • special case (corollary) of above:
    • if \(x[n]\) is real, the magnitude of the DTFT is symmetric \[ x[n] \in \mathbb{R} \Rightarrow \vert X(e^{j\omega}) \vert = X(e^{-j\omega}) \]
  • a more special case of above:
    • if \(x[n]\) is real and symmetric,
    • \( X(e^{j\omega}) \) is also real and symmetric
  • this mostly looks like a full-fledged basis expansion
    • so DTFT is just another version of the DFT
    • considering all the particular cases

DTFT as a change of basis

  • comparing DFT and DTFT, some operations are acceptable
    • \(DFT \{ \delta[n]\} = 1 \)
    • \(DTFT \{ \delta[n]\} = \langle e^{j\omega n}, \delta[n] \rangle = 1 \)
  • other operations don’t work;
    • \(DFT \{ 1\} = N \delta[k] \)
    • \(DTFT \{ 1\} = \sum_{n = -\infty}^{\infty} e^{-j\omega n} = ? \)
  • a lot of interesting sequences are not square summable
    • this is addressed by introducing the Dirac-delta functional

dirac-delta functional

  • “sifting” property: \[ \int_{-\infty}^{\infty} \delta(t - s)f(t)dt = f(s) \] for all functions of \( t \in \mathbb{R} \)

    • \(s \in \mathbb{R} \) along axis of \(t\)

    • dirac-delta is a function which is an upward pointing arrow at \(t = s \)
    • consider any function \(f(t)\), multiply this dirac-delta with \(f(t)\)
    • integrate the multiplied function from \( -\infty \) to \( \infty \)
      • this yields the value of \(f(t)\) @ \( t = s\)


  • to develop intuition for the dirac-delta function
    • consider a family of localizing functions \(r_k(t) \) with \( k \in \mathbb{N} \) and \( t \in \mathbb{R}\)
  • the properties of these functions are:
    • support of each function is inversely proportional to it’s index \(k\)
    • integral of each function from \( -\infty \) to \( \infty \) is constant
      • i.e. the area under each function is constant, regardless of index \(k\)
  • \( rect(t) = \Bigg \{ \begin{matrix} 1 & \text{for } \vert t \vert < \frac{1}{2}\\ 0 & \text{otherwise } \end{matrix} \)
  • consider the localizing family \(r_k(t) = k \text{ rect}(kt) \):
    • nonzero over \( [-\frac{1}{2k}, \frac{1}{2k} ] \) i.e. support is \( \frac{1}{k} \)
    • area is \(1\)

    supp-k1

    fig: k = 1, rect function

    supp-k5

    fig: k = 5, rect function

    supp-k15

    fig: k = 15, rect function

    supp-k40

    fig: k = 40, rect function

  • extracting a point value:
    • consider the integral of the product of one of these rect functions and any function of real time

    \[ \begin{equation} \int_{-\infty}^{\infty} r_k(t) f(t) dt = k \int_{-\frac{1}{2k}}^{\frac{1}{2k}}f(t)dt \
    = f(\gamma)\vert_{\gamma \in [-\frac{1}{2k},\frac{1}{2k}]} \
    \end{equation}\]

    • \(r_k(t)\) is non-zero only between \([-\frac{1}{2k},\frac{1}{2k}]\)
    • so, integration bounds change from \( [-\infty,\infty]\) to \([-\frac{1}{2k},\frac{1}{2k}]\)
    • then apply mean-value theorem to get \( = f(\gamma)\vert_{\gamma \in [-\frac{1}{2k},\frac{1}{2k}]} \)
      • value of \(\gamma \) is not known, but it is known to exist
    • as \(k \rightarrow \infty\), the support of the \( r_k \) gets smaller and smaller \[ \lim_{k \rightarrow \infty} \int_{-\infty}^{\infty} r_k(t)f(t)dt = f(0) \]
    • see above plots to get an intuitive feel
    • as \(k\) increases, the width of the support shrinks to an infinitesimal width
      • so, at the limit, the limit value is \(f(0)\)
    • the dirac-delta function is the shorthand for this limiting operation
      • it uses the concept of narrowing support functions as height of the support function increases to obtain the value of a function at a point in time
    • the delta functional is a shorthand: \[ \lim_{k \rightarrow \infty} \int_{-\infty}^{\infty} r_k(t - s)f(t) dt \]
      • is instead written as \[ \int_{-\infty}^{\infty} \delta(t - s)f(t) dt \]
      • as if \( \lim_{k \rightarrow \infty} r_k(t) = \delta(t) \)
  • the “pulse train”
    • the dirac-delta functional will be used in the frequency domain
    • all DTFT spectra are \(2\pi\) periodic
    • to be able to use the dirac-delta functional in the frequency domain, it has be periodized
      • this periodized version of the dirac-delta functional is called the “pulse train”
    • this done by placing copies of the dirac-delta functional every \(2\pi\) and scaling the whole thing by \(2\pi\) \[ \tilde{\delta}(\omega) = 2\pi \sum_{k=-\infty}^{\infty} \delta(\omega - 2\pi k) \]

    pulse-train

    fig: dirac delta pulse-train in frequency domain

  • consider the inverse DTFT of the pulse train: \[ \begin{equation} IDTFT \{ \tilde{\delta}(\omega) \} = \frac{1}{2\pi} \int_{-\pi}^{\pi} \tilde{\delta}{(\omega)} e^{j\omega n} d\omega \
    = \int_{-\pi}^{\pi} \tilde{\delta}{(\omega)} e^{j\omega n} d\omega \
    = e^{j\omega n} \vert_{\omega=0} \
    = 1 \end{equation} \]

  • comparing with IDFT:
    • \( IDFT\{N\delta[k]\} = 1\)

  • so, \( DTFT\{1\} = \tilde{\delta}(\omega)\)

  • more identities using dirac-delta pulse train results

    • \( IDTFT\{ \tilde{\delta}(\omega - \omega_0) \} = e^{j\omega_0 n} \)

    • \( DTFT \{1\} = \tilde{\delta}(\omega) \)
    • \( DTFT \{e^{j\omega_0 n}\} = \tilde{\delta}(\omega - \omega_0) \)
    • \( DTFT \{\cos(\omega_0 n)\} = \frac{[\tilde{\delta}(\omega - \omega_0) + \tilde{\delta}(\omega + \omega_0)]}{2}\)
    • \( DTFT \{\sin(\omega_0 n)\} = -j \frac{[\tilde{\delta}(\omega - \omega_0) - \tilde{\delta}(\omega + \omega_0)]}{2}\)

summary

  • the fourier tool of choice for infinite-length sequences, called the discrete-time fourier transform (DTFT) has been explored
  • Karplus-Strong algorithm was used to derive intuition; an infinite sequence was generated by repeating a finite length sequence and scaling each repetition by an exponential decay factor
    • as the number of repetitions increased, the fundamental frequencies \( \frac{2\pi}{N}k \) become denser and denser
    • this can be replaced in the DFT formula with a real frequency \( \omega \in \mathbb{R} \)
    • this leads to the definition of the DTFT analysis and synthesis formulas

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

\[ x[n] = \frac{1}{2\pi} \int_{-\infty}^{+\infty} X(e^{j\omega}) e^{j \omega n} d\omega \]

  • the DTFT thus maps an infinite length sequence \(x[n]\) onto a function of real variable \(\omega \)
  • the DTFT is \(2\pi\)-periodic
    • is expressed as\( X(e^{j\omega}) \) to stress this, although only \( \omega \) is the variable
    • this is standard convention in the DTFT literature
    • so, furthermore, by convention, DTFT is represented on the \([-\pi, \pi]\) interval
  • frequencies between 0 and \( \pi \) (resp. \(-\pi\) and 0) are the positive (resp. negative) frequencies, corresponding to counterclockwise (resp. clockwise) rotations

  • low (resp. high) frequencies are those close to 0 (resp. \(-\pi\) and \(\pi\) )

  • the question of existence is essential to ensure that the sum of the analysis formula does not blow up

  • tt can be shown that the DTFT converges for all square summable sequences

  • DTFT can be interpreted as a change of basis in the space \( \mathbb{C}^\infty\) where the uncountable set of functions \(e^{jωn} \omega \in \mathbb{R}\) forms an orthogonal basis
  • this space is not a proper vector space and a mathematical adjustment is needed to reconcile this intuition
  • hence the concept of the dirac-delta function is introduced
    • \(\delta(t)\) of real variable \(t\) is defined by the “sifting property” \[ \int_{-\infty}^{\infty} \delta(t-s) f(t) dt = f(s); \text{ } \forall f(t), t \in \mathbb{R} \]
  • with this adjustment, the DTFT can be defined for certain interesting non square summable sequences, such as

\[ \text{DTFT}(1) = 2\pi \sum_{k=-\infty}^{\infty} \delta(w - 2\pi k)\]

references