傅立葉轉換(Fourier Transform)

Mathematics   Yoshio    Sep 8th, 2023 at 8:00 PM    8    0   

泰勒展開式(Taylor Expansion)

泰勒級數 Taylor Series

A Taylor series is a series expansion of a function about a point. A one-dimensional Taylor series is an expansion of a real function \(f(x)\) about a point \(x=a\) is given by


where \(n!\) denotes the factorial of \(f(n)\). In the more compact sigma notation, this can be written as






傅立葉級數(Fourier Series)

Fourier Series

Fourier series is used to describe a periodic signal in terms of cosine and sine waves. In other other words, it allows us to model any arbitrary periodic signal with a combination of sines and cosines.

Consider expressing the Fourier series as

\[f(x)=\sum_{n=-\infty}^{+\infty}(a_n\cos\;nx+b_n\sin\;nx)\]

where \[a_n=\frac1{2\pi}\int_{-\pi}^{+\pi}f(t)cos\;nxt\;dt\]

and \[b_n=\frac1{2\pi}\int_{-\pi}^{+\pi}f(t)\sin\;nxt\;dt\]


The usual Fourier series involving sines and cosines is obtained by taking \(f_{1}(x) = cosx\) and \(f_2(x)=sinx\). Since these functions form a complete orthogonal system over \([-π,π]\), the Fourier series of a function \(f(x)\) is given by

where

\(a_{0} = \)

\(a_{n} = \)

\(b_{n} = \)

and \(n=1, 2, 3, ....\) Note that the coefficient of the constant term \(a_0\) has been written in a special form compared to the general form for a generalized Fourier series in order to preserve symmetry with the definitions of \(a_n\) and \(b_n\).

Note that \(cosϕ\) is an even function, i.e. \(cos(−ϕ)=cosϕ\), and therefore \(a_{-n} = a_n\). Similarly, \(sinϕ\) is an odd function, i.e. \(sin(-ϕ)=-sinϕ\), and therefore \(b_{-n} =-b_n\) . Thus, we can combine the terms with the positive and negative \(n\) of the same absolute value, which will result in doubled coefficients \(2a_n\) and \(2b_n\) for \(n > 0\), while the terms with \(n < 0\) will be dropped. Since the terms with \(n = 0\) do not have a pair, they will not be doubled, so \(a_0\) will remain the same, and \(b_0\) can be omitted since \(b_0 = 0\).


傅立葉轉換(Fourier Transform)

Fourier Transform

The Fourier transform (FT) is a transform that converts a function into a form that describes the frequencies present in the original function. The output of the transform is a complex-valued function of frequency. The Fourier transform can also be generalized to functions of several variables on Euclidean space, sending a function of 3-dimensional 'position space' to a function of 3-dimensional momentum (or a function of space and time to a function of 4-momentum).

傅立葉轉換介紹

The Fourier transform of the expression \(f = f(x)\) with respect to the variable \(x\) at the point \(w\) is

\[F{(w)}=c\int\limits_{-\infty}^\infty f{(x)}e^{iswx}dx\]

\(c\) and \(s\) are parameters of the Fourier transform. The fourier function uses \(c = 1, s = -1\).

\[F(m,n)=\sum_{x=0}^{M-1}\sum_{y=0}^{N-1}{f(x,y)e^{-j\frac{2\pi mx}M}}e^{-j\frac{2\pi ny}N}\]

where \(0\leq m\leq M-1\) and \(0\leq n\leq N-1\)



Properties of Continuous-Time Fourier Transform (CTFT)

Fourier Transform

The Fourier transform of a continuous-time function \(x(t)\) is defined as,

\[\mathrm X(\omega)=\int_{-\infty}^\infty\mathrm x(\mathrm t)\mathrm e^{-\mathrm j\omega\mathrm t}\mathrm d\mathrm t\]


Inverse Fourier Transform

The inverse Fourier transform of a continuous-time function is defined as,

\[\mathrm x(\mathrm t)=\frac1{2\pi}\int_{-\infty}^\infty\mathrm X(\omega)\mathrm e^{\mathrm j\omega\mathrm t}\mathrm d\omega\]




Short-Time Fourier Transform (STFT)

Short-time Fourier transform (STFT), is a Fourier-related transform used to determine the sinusoidal frequency and phase content of local sections of a signal as it changes over time.

STFT is a method of analysis used for analyzing non-stationary signals. It extracts several frames of signals with a window that moves with time. If the time window is sufficiently narrow, each frame extracted can be viewed as stationary so that Fourier transform can be used. With the window moving along the time axis, the relation between the variance of frequency and time can be identified.




Fourier Transform (FT)

Time domain signals transfer to Frequency domain signals

\[F{(\omega)}=\int\limits_{-\infty}^\infty f{(t)}e^{-i\omega t}dt\]



Short-Time Fourier Transform (STFT)

\[F{(\tau,\omega)}=\int\limits_{-\infty}^\infty f{(t)}w{(t-\tau)}e^{-i\omega t}dt\]

where \(\omega (t)\) represents the sliding window that emphasizes local frequency components within it. The size of the window is related to the time resolution and frequency resolution of STFT. The shorter the window, the higher the time resolution. However, this is usually accompanied by poor frequency resolution. For a long window, the frequency resolution is high, but the time resolution is low. This phenomenon reflects Heisenberg's uncertainty principle.

Different window shapes produce different results, and Origin provides up to nine different windows for addressing specific needs: Rectangle, Welch, Triangular, Bartlett, Hanning, Hamming, Blackman, Gaussian and Kaiser.

The window function, is commonly a Hann window or Gaussian window centered around zero.


Discrete-time Fourier transform (DTFT)

離散時間傅立葉轉換

The discrete-time Fourier transform (DTFT) is analogous to a Fourier series, except instead of starting with a periodic function of time and producing discrete sequence over frequency, it starts with a discrete sequence in time and produces a periodic function in frequency. It is the transform-pair relationship between a discrete-time signal and its continuous-frequency transform. The utility of this frequency domain function is rooted in the Poisson summation formula.

The DTFT is often used to analyze samples of a continuous function. The term discrete-time refers to the fact that the transform operates on discrete data, often samples whose interval has units of time. From uniformly spaced samples it produces a function of frequency that is a periodic summation of the continuous Fourier transform of the original continuous function.

Periodic Function in Frequency



Inverse Discrete-Time Fourier Transform (IDTFT)

The inverse discrete-time Fourier transform (IDTFT) is defined as the process of finding the discrete-time sequence \(x(n)\) from its frequency response \(X(ω)\).




\(\mathrm{\mathit{x}\mathrm{\left(\mathit{n}\right)}\:\mathrm{=}\: \frac{1}{2\pi}\int_{-\pi}^{\pi}\mathit{X}\mathrm{\left(\mathit{\omega}\right)}\mathit{e}^{\mathit{j\omega n}}\:\mathit{d\omega}}\)

\(\)








Discrete Fourier transform (DFT)

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency.


The discrete Fourier transform (DFT) is a method for converting a sequence of \(N\) complex numbers \(x_0, x_1, ..., x_{N-1}\)

\[ X_k = \sum_{n=0}^{N-1} x_n e^{-2\pi i kn/N}, \]

for \( 0 \le k \le N-1.\)

The \(x_i\) are thought of as the values of a function, or signal, at equally spaced times \(t=0,1,…,N−1\). he output \(X_k\) is a complex number which encodes the amplitude and phase of a sinusoidal wave with frequency \(\frac kN\) cycles per time unit. (This comes from Euler's formula: \(e^{2\pi ikn/N}=\cos(2\pi kn/N)+i\sin(2\pi kn/N)\)) The effect of computing the \(X_k\) is to find the coefficients of an approximation of the signal by a linear combination of such waves. Since each wave has an integer number of cycles per \(N\) time units, the approximation will be periodic with period \(N\). This approximation is given by the inverse Fourier transform

\[x_n=\frac1N\;\sum_{k=0}^{N-1}X_ke^{2\mathrm{πikn}/\mathrm N}\]

It is a consequence of orthogonality with respect to the complex dot product.


The DFT is useful in many applications, including the simple signal spectral analysis outlined above. Knowing how a signal can be expressed as a combination of waves allows for manipulation of that signal and comparisons of different signals:

Digital files (jpg, mp3, etc.) can be shrunk by eliminating contributions from the least important waves in the combination.

Different sound files can be compared by comparing the coefficients \(X_k\) of the DFT.

Radio waves can be filtered to avoid "noise" and listen to the important components of the signal.

DFT example A

Find the DFT of \((x_0,x_1,x_2,x_3) = (0,1,0,0).\)


In this case, \[ X_k = \sum_{n=0}^3 x_n e^{-2\pi i kn/4} = e^{-2\pi i k/4}. \] So \( X_0 = 1, X_1 = -i, X_2 = -1, X_3 = i.\) The answer is \( (1,-i,-1,i).\)

Proceeding as in the previous example, this gives the expansion \[ x_n = 1 - i e^{2\pi i n/4} - e^{4\pi i n/4} + i e^{6\pi i n/4}. \] Converting the complex coefficients to complex exponentials gives \[ \begin{align} x_n &= 1 + e^{6\pi i/4} e^{2\pi i n/4} + e^{4\pi i/4} e^{4\pi i n/4} + e^{2\pi i/4} e^{6 \pi i n/4} \\ &= 1 + e^{2\pi i(n+3)/4} + e^{2\pi i (2n+2)/4} + e^{2\pi i (3n+1)/4}. \end{align} \] This is an example of phase shifting occurring in the sum. Taking the real parts of both sides gives a sum of cosine waves: \[ x_n = 1 + \cos(2\pi n/4 + 3\pi/2) + \cos(4\pi n/4 + \pi) + \cos(6\pi n/4 + \pi/2), \] where the addition of \(3\pi/2, \pi, \pi/2\) has the effect of shifting the waves forward by \( 270^\circ, 180^\circ, 90^\circ,\) respectively.



Discrete Fourier Transform is with real and imaginary parts - \(ReX(i)\) cosine wave amplitudes and \(ImX(i)\) sine wave amplitudes.


DFT example B

Determine the 8-point DFT of the sequence x(n)={1,1,1,1,1,1,0,0}


\[X(\mathrm{k})=\sum_{n=0}^{N-1} x(\mathrm{n}) \mathrm{e}^{-j 2 \pi k n / N} k=0,1, \ldots N-1\]

for \(N = 8\)

\[X(\mathrm{k})=\sum_{n=0}^7 x(\mathrm{n}) \mathrm{e}^{-j \pi k n / 4} k=0,1,2 \ldots . . N-1\\\]

for \(N = 0\)

\(\begin{aligned} X(0) & =\sum_{n=0}^7 x(n) \\\\ \mathrm{X}(0) & =\mathrm{x}(0)+\mathrm{x}(1)+\mathrm{x}(2)+\mathrm{x}(3)+\mathrm{x}(4)+\mathrm{x}(5)+\mathrm{x}(6)+\mathrm{x}(7) \\\\ & =1+1+1+1+1+1+0+0 \\\\ & =6 \end{aligned}\)

for \(N = 1\)

\(\begin{aligned} X(1) & =\sum_{n=0}^7 x(n) \mathrm{e}^{-j \pi n / 4} \\\\ \mathrm{X}(1) & =\mathrm{x}(0)+\mathrm{x}(1) \mathrm{e}^{-\mathrm{j} \pi / 4}+\mathrm{x}(2) \mathrm{e}^{-\mathrm{j} \pi / 2}+\mathrm{x}(3) \mathrm{e}^{-\mathrm{j} 3 \pi / 4}+\mathrm{x}(4) \mathrm{e}^{-\mathrm{j} \pi}+\mathrm{x}(5) \mathrm{e}^{-\mathrm{j} 5 \pi / 4}+\mathrm{x}(6) \mathrm{e}^{-\mathrm{j} 3 \pi / 2}+\mathrm{x}(7) \mathrm{e}^{-\mathrm{j} 7 \pi / 4} \\\\ & =1+0.707-\mathrm{j} 0.707-\mathrm{j}-0.707-\mathrm{j} 0.707-1-0.707+\mathrm{j} 0.707 \quad=-0.707-\mathrm{j} 1.707\\ \end{aligned}\)

for \(N = 2\)

\begin{aligned} X(2) & =\sum_{n=0}^7 x(n) e^{-j \pi n / 2} \\\\ X(2) & =x(0)+\mathrm{x}(1) \mathrm{e}^{-\mathrm{j} \pi / 2}+\mathrm{x}(2) \mathrm{e}^{-\mathrm{j} \pi}+\mathrm{x}(3) \mathrm{e}^{-\mathrm{j} 3 \pi / 2}+\mathrm{x}(4) \mathrm{e}^{-\mathrm{j} 2 \pi}+\mathrm{x}(5) \mathrm{e}^{-\mathrm{j} 5 \pi / 2}+\mathrm{x}(6) \mathrm{e}^{-\mathrm{j} 3 \pi}+\mathrm{x}(7) \mathrm{e}^{-\mathrm{j} 7 \pi / 2} \\\\ & =1-\mathrm{j}-1+\mathrm{j}+1-\mathrm{j} \\\\ & =1-\mathrm{j}\\ \end{aligned}

for \(N = 3\)

\(\begin{aligned} X(3) & =\sum_{n=0}^7 x(n) e^{-j 3 \pi n / 4} \\\\ X(3) & =x(0)+x(1) e^{-j 3 \pi / 4}+\mathrm{x}(2) \mathrm{e}^{-\mathrm{j} \pi / 2}+\mathrm{x}(3) \mathrm{e}^{-\mathrm{j} 9 \pi / 4}+\mathrm{x}(4) \mathrm{e}^{-\mathrm{j} 3 \pi}+\mathrm{x}(5) \mathrm{e}^{-\mathrm{j} 15 \pi / 4}+\mathrm{x}(6) \mathrm{e}^{-\mathrm{j} 9 / / 4}+\mathrm{x}(7) \mathrm{e}^{-\mathrm{j} 21 \pi / 4} \\\\ & =1-0.707-\mathrm{j} 0.707+\mathrm{j}+0.707-\mathrm{j} 0.707-1+0.707+\mathrm{j} 0.707 \\\\ & =0.707+\mathrm{j} 0.293\\ \end{aligned}\)

for \(N = 4\)

\(\begin{aligned} X(4) & =\sum_{n=0}^7 x(n) \mathrm{e}^{-j \pi n}\\ \\ X(4) & =\mathrm{x}(0)+\mathrm{x}(1) \mathrm{e}^{-j \pi}+\mathrm{x}(2) \mathrm{e}^{-j \pi 2}+\mathrm{x}(3) \mathrm{e}^{-j \pi 3}+\mathrm{x}(4) \mathrm{e}^{-\mathrm{j} \pi 4}+\mathrm{x}(5) \mathrm{e}^{-\mathrm{j} \pi 5}+\mathrm{x}(6) \mathrm{e}^{-j \pi 6}+\mathrm{x}(7) \mathrm{e}^{-\mathrm{j} \pi 7} \\\\ & =1-1+1-1+1-1=0 \end{aligned}\\\)

for \(N = 5\)

\(\begin{aligned} X(5) & =\sum_{n=0}^7 x(n) e^{-j 5 \pi n / 4} \\\\ X(5) & =x(0)+\mathrm{x}(1) \mathrm{e}^{-\mathrm{j} 5 \pi / 4}+\mathrm{x}(2) \mathrm{e}^{-\mathrm{j} 5 \pi / 2}+\mathrm{x}(3) \mathrm{e}^{-\mathrm{j} 5 \pi n / 4}+\mathrm{x}(4) \mathrm{e}^{-\mathrm{j} 5 \pi}+\mathrm{x}(5) \mathrm{e}^{-\mathrm{j} 25 \pi / 4}+\mathrm{x}(6) \mathrm{e}^{-\mathrm{j} 15 \pi / 2}+\mathrm{x}(7) \mathrm{e}^{-\mathrm{j} 35 \pi / 4} \\\\ & =1-0.707+\mathrm{j} 0.707-\mathrm{j}+0.707+\mathrm{j} 0.707-1+0.707-\mathrm{j} 0.707 \\\\ & =0.707-\mathrm{j} 0.293\\ \end{aligned}\)

for \(N = 6\)

\(\begin{aligned} X(6) & =\sum_{n=0}^7 x(n) e^{-j 3 \pi n / 2} \\\\ \mathrm{X}(6) & =\mathrm{x}(0)+\mathrm{x}(1) \mathrm{e}^{-\mathrm{j} 3 \pi / 2}+\mathrm{x}(2) \mathrm{e}^{-\mathrm{j} 3 \pi}+\mathrm{x}(3) \mathrm{e}^{-\mathrm{j} 9 \pi / 2}+\mathrm{x}(4) \mathrm{e}^{-\mathrm{j} 6 \pi}+\mathrm{x}(5) \mathrm{e}^{-\mathrm{j} 15 \pi}+\mathrm{x}(6) \mathrm{e}^{-\mathrm{j} 9 \pi}+\mathrm{x}(7) \mathrm{e}^{-\mathrm{j} 21 \pi / 2} \\\\ & =1+\mathrm{j}-1-\mathrm{j}+1+\mathrm{j} \Rightarrow \quad=1+\mathrm{j}\\ \end{aligned}\)

for \(N = 7\)

\(\begin{aligned} \mathrm{X}(7) & =\mathrm{x}(0)+\mathrm{x}(1) \mathrm{e}^{-\mathrm{j} 7 \pi / 4}+\mathrm{x}(2) \mathrm{e}^{-\mathrm{j} 7 \pi / 2}+\mathrm{x}(3) \mathrm{e}^{-\mathrm{j} 21 \pi / 4}+\mathrm{x}(4) \mathrm{e}^{-\mathrm{j} 7 \pi}+\mathrm{x}(5) \mathrm{e}^{-\mathrm{j} 35 \pi / 4}+\mathrm{x}(6) \mathrm{e}^{-\mathrm{j} 21 \pi / 2}+\mathrm{x}(7) \mathrm{e}^{-\mathrm{j} 49 \pi / 4} \\\\ & =1+0.707+\mathrm{j} 0.707+\mathrm{j}-0.707+\mathrm{j} 0.707-1-0.707-\mathrm{j} 0.707 \\\\ = & -0.707+\mathrm{j} 1.707 \\\\ & \mathrm{X}(\mathrm{K})=\{6,0.707-\mathrm{j} 1.707,1-\mathrm{j}, 0.707+\mathrm{j} 0.293,0,0.707-\mathrm{j} 0.293,1+\mathrm{j},-0.707+\mathrm{j} 1.707\}\\ \end{aligned}\)


Fast Fourier Transform (FFT)


Discrete cosine transform (DCT)
Laplace transform
Hilbert Transform
Gabor Transform
Riesz transform
wavelet transform
Markov chain
Z-transform
Advanced z-transform
Matched Z-transform method
Bilinear transform
Constant-Q transform
Impulse invariance Integral transform
Post's inversion formula Starred transform
Zak transform
Kirchhoff's Law, Junction & Loop Rule, Ohm's Law

Fourier transform


The Fourier transform is a widely used mathematical tool for converting signals from time to frequency domains. It decomposes a signal into a sum of sinusoidal functions with different frequencies, amplitudes, and phases.


The red and blue sinusoids have a phase difference of \(θ\)

The red sinusoid can be described by peak amplitude (1), peak-to-peak (2), RMS (3), and wavelength (4).


The two sinusoid signals cross product is not zero if they are not orthognal.





The Convolution Property

Why is convolution in time domain equivalent to frequency multiplication?

\(x(t)\ast h(t)\leftrightarrow X(\omega)H(\omega)\)

Let us show that. To start, let

\(y(t)=\int_{-\infty}^\infty x(\tau)h(t-\tau)d\tau=x(t)\ast h(t)\)

Then we can take the Fourier Transform of \(y(t)\) and plug in the convolution integral for \(y(t)\) (notice how we've marked the integrals with \(dt\) and \(d\tau\) to keep track of them):

\(Y(\omega)=\int_{-\infty,dt}^\infty y(t)e^{-j\omega t}dt=\int_{-\infty,dt}^\infty\int_{-\infty,d\tau}^\infty x(\tau)h(t-\tau)d\tau e^{-j\omega t}dt\)

Now, let's switch the order of the two integrals (this is valid in all but the most pathological cases):

\(Y(\omega)=\int_{-\infty,d\tau}^\infty x(\tau)\int_{-\infty,dt}^\infty h(t-\tau)e^{-j\omega t}dtd\tau\;\;\;\;let\;u=t-\tau\)

\(=\int_{-\infty,d\tau}^\infty x(\tau)\int_{-\infty,du}^\infty h(u)e^{-j\omega(u+\tau)}dud\tau\)

\(=\int_{-\infty,d\tau}^\infty x(\tau)e^{-j\omega\tau}d\tau\int_{-\infty,du}^\infty h(u)e^{-j\omega u}du\)

\(=X(\omega)H(\omega)\)

Therefore,

\(y(t)=x(t)\ast h(t)\leftrightarrow Y(\omega)=X(\omega)H(\omega)\)

We've just shown that the Fourier Transform of the convolution of two functions is simply the product of the Fourier Transforms of the functions. This means that for linear, time-invariant systems, where the input/output relationship is described by a convolution, you can avoid convolution by using Fourier Transforms. This is a very powerful result.

Multiplication of Signals

Our next property is the Multiplication Property. It states that the Fourier Transform of the product of two signals in time is the convolution of the two Fourier Transforms.

\(x_1(t)x_2(t)\leftrightarrow\frac1{2\pi}X_1(\omega)\ast X_2(\omega)\)

\(x_1(t)x_2(t)\leftrightarrow\frac1{2\pi}\int_{-\infty}^\infty X_1(u)X_2(\omega-u)du\)


Proof: \(F\lbrack x_1(t)x_2(t)\rbrack=\int_{-\infty}^\infty x_1(t)x_2(t)e^{-j\omega t}dt\)


Now, write \(x_1 (t)\) as an inverse Fourier Transform.

\(F\lbrack x_1(t)x_2(t)\rbrack=\int_{-\infty,dt}^\infty\left[\frac1{2\pi}\int_{-\infty,da}^\infty X_1(a)e^{-jat}da\right]x_2(t)e^{-j\omega t}dt\)

\(=\frac1{2\pi}\int_{-\infty,da}^\infty X_1(a)\int_{-\infty,dt}^\infty x_2(t)e^{-j(\omega-a)t}dtda\)

\(=\frac1{2\pi}\int_{-\infty,da}^\infty X_1(a)X_2(\omega-a)da\)

\(=\frac1{2\pi}X_1(\omega)\ast X_2(\omega)\)


Frequency Shifting or Modulation

\(F\left[e^{j\omega_0t}x(t)\right]=\int_{-\infty}^\infty e^{j\omega_0t}x(t)e^{-j\omega t}dt\)

\(=\int_{-\infty}^\infty x(t)e^{-j(\omega-\omega_0)t}dt\)

\(=X(\omega-\omega_0)\)

\(x(t)e^{j\omega_0t}\leftrightarrow X(\omega-\omega_0)\)


What is "Convolution"?

Digital Signal Processing: How do you explain (without doing any calculation), that convolution in time domain should imply multiplication in frequency domain?


Multiplying two periodic signals means adding their frequencies.

A periodic signal is \(e^{i\omega_1t}\) and if you multiply it to some other signal \(e^{i\omega_2t}\) you get \(e^{i(\omega_1+\omega_2)t}\).

The point of the frequency domain is you make a signal up out of a bunch of different frequencies, i.e.

\(f(t)={\textstyle\sum_m}a_me^{i\omega_mt}\)

But to take a simple example, let's have

\(f(t)=a_1e^{i\omega_0t}+a_2e^{i2\omega_0t}\)

\(g(t)=b_1e^{i\omega_0t}+b_2e^{i2\omega_0t}\)

If you want to multiply them, you have

\(\left(a_1e^{i\omega_0t}+a_2e^{i2\omega_0t}\right)\left(b_1e^{i\omega_0t}+b_2e^{i2\omega_0t}\right)\)

\(=a_1b_1e^{i2\omega_0t}+(a_1b_2+a_2b_1)e^{i3\omega_0t}+a_2b_2e^{i4\omega_0t}\)

But this is just what is meant by the convolution of \(a\) and \(b\).



Convolution vs. cross-correlation ?!

Understanding Discrete Convolution as Polynomial Multiplication

Multiplication of polynomials and convolution

suppose you had two polynomials \(f\) and \(g\) given by

\(f(x) = \sum_{i=0}^m a_i x^i, \quad g(x) = \sum_{j=0}^n b_j x^j.\)

Then their product is

\(f(x)g(x) = \sum_{i=0}^m \sum_{j=0}^n a_i b_j x^i x^j.\)

If we wish to write this in standard form (i.e. as a sum of single powers of \(x\)), then we need to consider powers of degree \(i+j=k\). Rewriting slightly,

\(f(x)g(x) = \sum_{i=0}^m \sum_{j=0}^n a_{k-j} b_j x^k.\)

\(k\) ranges from \(0\) to \(m+n\), but now our sums are coupled since \(j\) depends on \(k\). This dependence is exactly that \(j\) ranges from \(0\) to \(k\). The easy way to see this is just by writing out a few cases, but logically it follows because \(a_0x^0b_kx^k\) results in a power of \(k\). Thus

\(f(x)g(x) = \sum_{k=0}^{m+n}\left( \sum_{j=0}^k a_{k-j} b_j\right) x^k.\)

The term inside the parentheses is the discrete convolution of the coefficients.

The fact that convolution shows up when doing products of polynomials is pretty closely tied to group theory and is actually very important for the theory of locally compact abelian groups. It provides a direct avenue of generalization from discrete groups to continuous groups. The discrete convolution is a very important aspect of \(ℓ^1\), which makes it clear that a lot of the setting for LCA groups is in \(L^1\).


Periodic Convolution (aka Circular Convolution)

same as FIR

\[\begin{align} y[n] &=x[n] * h[n] \nonumber \\ &=\sum_{k=-\infty}^{\infty} x[k] h[n-k] \end{align} \nonumber\]

\(x(n)=\{1,2,3,1\}\)

\(y(n)=\{4,3,2,2\}\)

\(h(n)=x(n)\ast y(n)\)

\(\begin{array}{cccc}1&2&3&1\\4&3&2&2\end{array}\)

\(\begin{array}{ccccccc}4&8&12&4&&&\\&3&6&9&3&&\\&&2&4&6&2&\\&&&2&4&6&2\end{array}\)

\(\begin{array}{ccccccc}4&11&20&19&13&8&2\\13&8&2&&<&<&<\\17&19&22&19&&&\end{array}\)

Proof:

\(DFT\lbrack x(n)\rbrack=X(k)=(7,\;-2-j,1,-2+j)\)

\(DFT\lbrack y(n)\rbrack=Y(k)=(11,\;2-j,1,2+j)\)

\(DFT\lbrack h(n)\rbrack=H(k)=X(k)\times Y(k)\)

\(H(k)=(77,-5,1,-5)\)

\(h(n)=IDFT\lbrack H(k)\rbrack=(17,19,22,19)\)

\(x(n)\ast y(n)=X(k)\times Y(k)\)

Fast Fourier Transform (FFT)

FFT

The output of the FFT is a complex vector containing information about the frequency content of the signal. The magnitude tells you the strength of the frequency components relative to other components. The phase tells you how all the frequency components align in time.

The Fast Fourier Transform (FFT) is a way to reduce the complexity of the Fourier transform computation from \(O(n^2)\) to \(O(n\;log\;n)\) which is a dramatic improvement.


Illustration of the FFT process. The colors indicate if an element is treated as an even array (red) or an odd array (green). The geometrical shapes allow to associate the elements which are in the same subarray. The multiplicative coefficients applied to the odd elements are also represented. This somewhat complicated diagram is the key to what follows. Feel free to spend some time to understand it.


\(k\) Binary representation of \(k\) Reverse binary representation Index of \(\widehat f\lbrack k\rbrack\)
0 000 000 0
1 001 100 4
2 010 010 2
3 011 110 6
4 100 001 1
5 101 101 5
6 110 011 3
7 111 111 7

Diagram of the FFT with a permuted input. The colors and symbols are the same as in the first illustration

Eight-point

where \(\omega=e^{-\frac{2\mathrm{πi}}8}=\frac{1-i}{\sqrt2}\)

note that \(\omega^{8+n}=\omega^n\)

DFT and its IDFT

DFT maxtrix \(\widetilde S_N^\ast\) and the corresponding normalized inverse DFT matrix \({\widetilde S}_N\) implies \(\;\;\widetilde S_N^\ast{\widetilde S}_N=I\). Such a complex matrix IDFT is said to be unitary. Reverse elements order of each column except first row.

Conversion in system matrices of DFT and IDFT obtained by replacing i by -i.


Butterfly Diagram for an 8-Point DIT FFT (Decimation in Time)


Butterfly Diagram for an 8-Point DIF FFT (Decimation in Frequency)




\[\tiny \begin{bmatrix} {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{0}}} & {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{0}}} & {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{0}}} & {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{0}}} \\ {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{1}}} & {\color{blue}{\omega^{2}}} & {\color{red}{\omega^{3}}} & {\color{blue}{\omega^{4}}} & {\color{red}{\omega^{5}}} & {\color{blue}{\omega^{6}}} & {\color{red}{\omega^{7}}} \\ {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{2}}} & {\color{blue}{\omega^{4}}} & {\color{red}{\omega^{6}}} & {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{2}}} & {\color{blue}{\omega^{4}}} & {\color{red}{\omega^{6}}} \\ {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{3}}} & {\color{blue}{\omega^{6}}} & {\color{red}{\omega^{1}}} & {\color{blue}{\omega^{4}}} & {\color{red}{\omega^{7}}} & {\color{blue}{\omega^{2}}} & {\color{red}{\omega^{5}}} \\ {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{4}}} & {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{4}}} & {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{4}}} & {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{4}}} \\ {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{5}}} & {\color{blue}{\omega^{2}}} & {\color{red}{\omega^{7}}} & {\color{blue}{\omega^{4}}} & {\color{red}{\omega^{1}}} & {\color{blue}{\omega^{6}}} & {\color{red}{\omega^{3}}} \\ {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{6}}} & {\color{blue}{\omega^{4}}} & {\color{red}{\omega^{2}}} & {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{6}}} & {\color{blue}{\omega^{4}}} & {\color{red}{\omega^{2}}} \\ {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{7}}} & {\color{blue}{\omega^{6}}} & {\color{red}{\omega^{5}}} & {\color{blue}{\omega^{4}}} & {\color{red}{\omega^{3}}} & {\color{blue}{\omega^{2}}} & {\color{red}{\omega^{1}}} \\ \end{bmatrix} \begin{bmatrix} {\color{blue}{a_0}} \\ {\color{red}{a_1}} \\ {\color{blue}{a_2}} \\ {\color{red}{a_3}} \\ {\color{blue}{a_4}} \\ {\color{red}{a_5}} \\ {\color{blue}{a_6}} \\ {\color{red}{a_7}} \end{bmatrix}. \]

\[\tiny \left[ \begin{array}{cccc|cccc} {\color{blue}{\omega^{0}}} & {\color{blue}{\omega^{0}}} & {\color{blue}{\omega^{0}}} & {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{0}}} & {\color{red}{\omega^{0}}} & {\color{red}{\omega^{0}}} & {\color{red}{\omega^{0}}} \\ {\color{blue}{\omega^{0}}} & {\color{blue}{\omega^{2}}} & {\color{blue}{\omega^{4}}} & {\color{blue}{\omega^{6}}} & {\color{red}{\omega^{1}}} & {\color{red}{\omega^{3}}} & {\color{red}{\omega^{5}}} & {\color{red}{\omega^{7}}} \\ {\color{blue}{\omega^{0}}} & {\color{blue}{\omega^{4}}} & {\color{blue}{\omega^{0}}} & {\color{blue}{\omega^{4}}} & {\color{red}{\omega^{2}}} & {\color{red}{\omega^{6}}} & {\color{red}{\omega^{2}}} & {\color{red}{\omega^{6}}} \\ {\color{blue}{\omega^{0}}} & {\color{blue}{\omega^{6}}} & {\color{blue}{\omega^{4}}} & {\color{blue}{\omega^{2}}} & {\color{red}{\omega^{3}}} & {\color{red}{\omega^{1}}} & {\color{red}{\omega^{7}}} & {\color{red}{\omega^{5}}} \\ \hline {\color{blue}{\omega^{0}}} & {\color{blue}{\omega^{0}}} & {\color{blue}{\omega^{0}}} & {\color{blue}{\omega^{0}}} & {\color{red}{\omega^{4}}} & {\color{red}{\omega^{4}}} & {\color{red}{\omega^{4}}} & {\color{red}{\omega^{4}}} \\ {\color{blue}{\omega^{0}}} & {\color{blue}{\omega^{2}}} & {\color{blue}{\omega^{4}}} & {\color{blue}{\omega^{6}}} & {\color{red}{\omega^{5}}} & {\color{red}{\omega^{7}}} & {\color{red}{\omega^{1}}} & {\color{red}{\omega^{3}}} \\ {\color{blue}{\omega^{0}}} & {\color{blue}{\omega^{4}}} & {\color{blue}{\omega^{0}}} & {\color{blue}{\omega^{4}}} & {\color{red}{\omega^{6}}} & {\color{red}{\omega^{2}}} & {\color{red}{\omega^{6}}} & {\color{red}{\omega^{2}}} \\ {\color{blue}{\omega^{0}}} & {\color{blue}{\omega^{6}}} & {\color{blue}{\omega^{4}}} & {\color{blue}{\omega^{2}}} & {\color{red}{\omega^{7}}} & {\color{red}{\omega^{5}}} & {\color{red}{\omega^{3}}} & {\color{red}{\omega^{1}}} \\ \end{array} \right] \begin{bmatrix} {\color{blue}{a_0}} \\ {\color{blue}{a_2}} \\ {\color{blue}{a_4}} \\ {\color{blue}{a_6}} \\ {\color{red}{a_1}} \\ {\color{red}{a_3}} \\ {\color{red}{a_5}} \\ {\color{red}{a_7}} \end{bmatrix} \]

\[\tiny \begin{bmatrix} \omega^0 & \omega^0 & \omega^0 & \omega^0 \\ \omega^0 & \omega^2 & \omega^4 & \omega^6 \\ \omega^0 & \omega^4 & \omega^0 & \omega^4 \\ \omega^0 & \omega^6 & \omega^4 & \omega^2 \end{bmatrix} \begin{bmatrix} a_0 \\ a_2 \\ a_4 \\ a_6 \end{bmatrix}, \begin{bmatrix} \omega^0 & \omega^0 & \omega^0 & \omega^0 \\ \omega^1 & \omega^3 & \omega^5 & \omega^7 \\ \omega^2 & \omega^6 & \omega^2 & \omega^6 \\ \omega^3 & \omega^1 & \omega^7 & \omega^5 \\ \end{bmatrix} \begin{bmatrix} a_1 \\ a_3 \\ a_5 \\ a_7 \end{bmatrix}, \begin{bmatrix} \omega^4 & \omega^4 & \omega^4 & \omega^4 \\ \omega^5 & \omega^7 & \omega^1 & \omega^3 \\ \omega^6 & \omega^2 & \omega^6 & \omega^2 \\ \omega^7 & \omega^5 & \omega^3 & \omega^1 \end{bmatrix} \begin{bmatrix} a_1 \\ a_3 \\ a_5 \\ a_7 \end{bmatrix}. \]

\[\tiny \begin{align*} \begin{bmatrix} \omega^0 & \omega^0 & \omega^0 & \omega^0 \\ \omega^1 & \omega^3 & \omega^5 & \omega^7 \\ \omega^2 & \omega^6 & \omega^2 & \omega^6 \\ \omega^3 & \omega^1 & \omega^7 & \omega^5 \\ \end{bmatrix} \begin{bmatrix} a_1 \\ a_3 \\ a_5 \\ a_7 \end{bmatrix} &= \begin{bmatrix} \omega^0 & & & \\ & \omega^1 & & \\ & & \omega^2 & \\ & & & \omega^3 \end{bmatrix} \begin{bmatrix} \omega^0 & \omega^0 & \omega^0 & \omega^0 \\ \omega^0 & \omega^2 & \omega^4 & \omega^6 \\ \omega^0 & \omega^4 & \omega^0 & \omega^4 \\ \omega^0 & \omega^6 & \omega^4 & \omega^2 \end{bmatrix} \begin{bmatrix} a_1 \\ a_3 \\ a_5 \\ a_7 \end{bmatrix} \\ \begin{bmatrix} \omega^4 & \omega^4 & \omega^4 & \omega^4 \\ \omega^5 & \omega^7 & \omega^1 & \omega^3 \\ \omega^6 & \omega^2 & \omega^6 & \omega^2 \\ \omega^7 & \omega^5 & \omega^3 & \omega^1 \end{bmatrix} \begin{bmatrix} a_1 \\ a_3 \\ a_5 \\ a_7 \end{bmatrix} &= \begin{bmatrix} \omega^4 & & & \\ & \omega^5 & & \\ & & \omega^6 & \\ & & & \omega^7 \end{bmatrix} \begin{bmatrix} \omega^0 & \omega^0 & \omega^0 & \omega^0 \\ \omega^0 & \omega^2 & \omega^4 & \omega^6 \\ \omega^0 & \omega^4 & \omega^0 & \omega^4 \\ \omega^0 & \omega^6 & \omega^4 & \omega^2 \end{bmatrix} \begin{bmatrix} a_1 \\ a_3 \\ a_5 \\ a_7 \end{bmatrix} \end{align*} \]








Fourier Signal Sifter

The method to retrieve signal frequency

One Question, if the sifter signal and sampling signal are different by a phase of angle 90 degrees?

DEFINING THE ENERGY OF THE SIGNAL AT A PARTICULAR FREQUENCY

The goal is to define a metric that can be used to help assess the prevalence of a particular frequency in our signal. This is achieved through the last step of the Fourier Transform with the summation and normalization step. In this case we are adding up all the points along the signal (k = 1 to k= N) and dividing though by the total number of points (N). This is equivalent to finding the average value across all the points on our wound up graph.

The center of mass concept is a physical analogy used to explain the Fourier transform. Just as the center of mass of an object represents its overall distribution of mass, the center of mass of a signal represents its overall distribution of frequencies.


Sifting Process

The spectral centroid is a measure used in digital signal processing to characterise a spectrum. It indicates where the center of mass of the spectrum is located. Perceptually, it has a robust connection with the impression of brightness of a sound. It is sometimes called center of spectral mass.






You will get 5% for each correct answer for single choice questions. In multiple choice question it might be up to 5%. At the end of the Quiz, your total score will be displayed. Maximum score is 100%.


FFT examples


How to compute frequency of data using FFT ?

calculate the magnitude of each DFT output bin: magnitude = sqrt(re*re+im*im)
find the bin with the largest magnitude, call its index i_max.
calculate the equivalent frequency of this bin: freq = i_max * Fs / N, here Fs = sample rate (Hz) and N = no of points in FFT.

The first bin in the FFT is DC (0 Hz), the second bin is Fs / N, where Fs is the sample rate and N is the size of the FFT. The next bin is 2 * Fs / N. To express this in general terms, the nth bin is n * Fs / N.

So if your sample rate, Fs is say 44.1 kHz and your FFT size, N is 1024, then the FFT output bins are at:


  0:   0 * 44100 / 1024 =     0.0 Hz
  1:   1 * 44100 / 1024 =    43.1 Hz
  2:   2 * 44100 / 1024 =    86.1 Hz
  3:   3 * 44100 / 1024 =   129.2 Hz
  4: ...
  5: ...
     ...
511: 511 * 44100 / 1024 = 22006.9 Hz
								

Note that for a real input signal (imaginary parts all zero) the second half of the FFT (bins from N / 2 + 1 to N - 1) contain no useful additional information (they have complex conjugate symmetry with the first N / 2 - 1 bins). The last useful bin (for practical aplications) is at N / 2 - 1, which corresponds to 22006.9 Hz in the above example. The bin at N / 2 represents energy at the Nyquist frequency, i.e. Fs / 2 ( = 22050 Hz in this example), but this is in general not of any practical use, since anti-aliasing filters will typically attenuate any signals at and above Fs / 2.

Nyquist frequency

In signal processing, the Nyquist frequency (or folding frequency), named after Harry Nyquist, is a characteristic of a sampler, which converts a continuous function or signal into a discrete sequence.

For example, audio CDs have a sampling rate of 44100 samples/second. At 0.5 cycle/sample, the corresponding Nyquist frequency is 22050 cycles/second (Hz). Conversely, the Nyquist rate for sampling a 22050 Hz signal is 44100 samples/second.

Humans can detect sounds in a frequency range from about 20 Hz to 20 kHz. (Human infants can actually hear frequencies slightly higher than 20 kHz, but lose some high-frequency sensitivity as they mature; the upper limit in average adults is often closer to 15–17 kHz.)


Discrete cosine transform

DCT