數位訊號處理 Digital Signal Processing

Mathematics   Yoshio    Jan 2nd, 2026 at 8:00 PM    8    0   

Digital Signal Processing

DSP


Fourier Series Expansion

For a periodic signal with period \(T\)
\(x(t)=\underbrace{a_0}_{DC}+\sum_{n=1}^\infty a_n\cos(n\Omega_0t)+\sum_{n=1}^\infty b_n\sin(n\Omega_0t)\)
\(\Omega_0=\frac{2\pi}T\;(rad/sec)\) fundamental frequency
\(f_0=\frac1T,\;T\rightarrow period\)



\(a_0=\frac1T\int_Tx(t)\operatorname dt\)
\(a_n=\frac2T\int_Tx(t)\cdot\cos(n\Omega_0t)\operatorname dt\)
\(b_n=\frac2T\int_Tx(t)\cdot\sin(n\Omega_0t)\operatorname dt\)

\(a_n=\frac2T\int_Tx(t)\cdot\cos(n\Omega_0t)\operatorname dt=\frac2T\int_T\lbrack a_0+\sum_{k=1}^\infty a_n\cos(k\Omega_0t)+\sum_{k=1}^\infty b_k\sin(k\Omega_0t)\rbrack\cdot\cos(n\Omega_0t)\operatorname dt\)
\(=\frac2T\int_Ta_0\cos(n\Omega_0t)\operatorname dt+\frac2T\int_T\sum_{k=1}^\infty a_n\cos(k\Omega_0t)\cos(n\Omega_0t)\operatorname dt+\frac2T\int_T\sum_{k=1}^\infty b_n\sin(k\Omega_0t)\cos(n\Omega_0t)\operatorname dt\)
\(\int_T\cos(n\Omega_0t)\operatorname dt=0\)
\(\cos(A)\cdot\cos(B)=\frac12\lbrack\cos(A+B)+\cos(A-B)\rbrack\)
\(\sin(A)\cdot\cos(B)=\frac12\lbrack\sin(A+B)+\sin(A-B)\rbrack\)
\({\frac2T\int_T}\sum_{k=1}^\infty a_n\cos(k\Omega_0t)\cos(n\Omega_0t)\operatorname dt=\frac2T\int_Ta_n\cos^2(n\Omega_0t)\operatorname dt,\;when\;k=n\)
\(=\frac2T\int_Ta_n\cdot\frac12\lbrack\cos(2n\Omega_0t)+1\rbrack\operatorname dt\)
\(=\frac2T\int_Ta_n\frac12\operatorname dt=a_n\)
\(\frac2T\int_T\sum_{k=1}^\infty b_n\sin(k\Omega_0t)\cos(n\Omega_0t)\operatorname dt=0\;\because\int_T\sin(\beta\Omega_0t)\operatorname dt=0\)

\(\left\{\begin{array}{l}e^{j\theta}=\cos\theta+j\sin\theta\\e^{-j\theta}=\cos\theta-j\sin\theta\end{array}\right.\)
\(\left\{\begin{array}{l}\cos\theta=\frac{e^{j\theta}+e^{-j\theta}}2\\\sin\theta=\frac{e^{j\theta}-e^{-j\theta}}{2j}\end{array}\right.\)

\(x(t)=a_0+\sum_{n=1}^\infty a_n\cos(n\Omega_0t)+\sum_{n=1}^\infty b_n\sin(n\Omega_0t)\)
\(=a_0+\sum_{n=1}^\infty\frac{a_n}2(e^{jn\Omega_0t}+e^{-jn\Omega_0t})+\sum_{n=1}^\infty\frac{b_n}{2j}(e^{jn\Omega_0t}-e^{-jn\Omega_0t})\)
\(=a_0+\sum_{n=1}^\infty(\frac{a_n}2e^{jn\Omega_0t}+\frac{b_n}{2j}e^{jn\Omega_0t})+\sum_{n=1}^\infty(\frac{a_n}2e^{-jn\Omega_0t}-\frac{b_n}{2j}e^{-jn\Omega_0t})\)
\(=a_0+\sum_{n=1}^\infty(\frac{a_n}2+\frac{b_n}{2j})e^{jn\Omega_0t}+\sum_{n=-\infty}^{-1}(\frac{a_{-n}}2e^{jn\Omega_0t}-\frac{b_{-n}}{2j}e^{jn\Omega_0t})\)
\(=a_0e^{j\cdot0\cdot\Omega_0t}+\sum_{n=1}^\infty\frac12(a_n-jb_n)e^{jn\Omega_0t}+\sum_{n=-\infty}^{-1}\frac12(a_{-n}+jb_{-n})e^{jn\Omega_0t}\)
\(=\sum_{n=-\infty}^\infty X_ne^{jn\Omega_0t},\;F.S.\)

\(X_n=\frac1T\int_Tx(t)e^{-jn\Omega_0t}\operatorname dt\)



Dirac comb

[Ex] impulse train
\(x(t)=\sum_{m=-\infty}^\infty\delta(t-mT)\)
\(=\sum_{k=-\infty}^\infty X_ke^{jk\Omega_0t},\;\Omega_0=\frac{2\pi}T\)
\(X_k=\frac1T\int_T\delta(t-mT)e^{-jk\Omega_0t}\operatorname dt\)
\(\delta(t-mT)=1\;when\;t=mT,\;e^{-jk\Omega_0t}=e^{-jk\cdot\frac{2\pi}T\cdot mT}=e^{-jkm\cdot2\mathrm\pi}=1\)
\(X_k=\frac1T\cdot1=\frac1T,\;k=(-\infty,\infty)\)

\(\sum \limits_{n=-\infty}^{\infty}\delta(t-nT_s) ~~~\underset{\mathcal{F}}\longleftrightarrow ~~~\Omega_s \sum \limits_{n=-\infty}^{\infty}\delta(\Omega-n\Omega_s)\)
where \(\Omega_s = \frac{2\pi}{T_s}\)



\(\displaystyle P(t) = \sum_{n=-\infty}^\infty (-1)^n\delta(t-n\Delta)\)
If \(\displaystyle Q(t) = \sum_{n=-\infty}^\infty \delta(t-2n\Delta)\) is a periodic impulse train of period \(2Δ\), then \(Q(t)−Q(t−Δ)\) is a periodic impulse train of period \(2Δ\) in which the impulses alternate in polarity, that is, it is the \(P(t)\)



[Ex] pulse train
\(x(t)=\sum_{m=-\infty}^\infty\Pi(t-mT)\)
\(=\sum_{k=-\infty}^\infty X_ke^{jk\Omega_0t}\)

\(X_k=\frac1T\int_T\Pi(t-mT)e^{-jk\Omega_0t}\operatorname dt\)
\(=\frac1T\int_{-½}^½1\cdot e^{-jk\Omega_0t}\operatorname dt\)
\(=\frac1T\cdot\left.\frac1{-jk\Omega_0}e^{-jk\Omega_0t}\right|_{-½}^½=\frac1{-jk\cdot2\mathrm\pi}(e^{-½jk\Omega_0}-e^{½jk\Omega_0})\;\because\Omega_0=\frac{2\mathrm\pi}T\)
\(=\frac1{-jk\cdot2\mathrm\pi}(e^{-\cancel½jk\frac{\cancel2\mathrm\pi}T}-e^{\cancel½jk\frac{\cancel2\mathrm\pi}T})\)
\(=\frac1{2T}\frac1{-jk{\frac{\mathrm\pi}T}}(e^{-jk\frac{\mathrm\pi}T}-e^{jk\frac{\mathrm\pi}T})\)
\(=\frac1{2T}\frac1{-jk\frac{\mathrm\pi}T}\lbrack-2j\sin(k\frac{\mathrm\pi}T)\rbrack=\frac1T\cdot\frac1{\frac{\mathrm{kπ}}T}\sin(\frac{\mathrm{kπ}}T)\)
\(=\frac1T{sinc}(\frac kT)\)




For an aperiodic signal \(x(t)=\lim_{T\rightarrow\infty}x_T(t+T)\)

\(x(t)=\lim_{T\rightarrow\infty}\sum_{k=-\infty}^\infty X_ke^{jk\Omega_0t}=\sum_{k=-\infty}^\infty X_ke^{jk\frac{2\mathrm\pi}Tt}\)

Fourier Transform (FT)

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

\(X(j\Omega)=\int_{-\infty}^\infty x(t)e^{-j\Omega t}dt\)




Intuitive Guide to Convolution

Convolution

Convolution is usually introduced with its formal definition:
\((f*g)(t):=\int _{-\infty }^{\infty }f(\tau )g(t-\tau )\,d\tau\)







Intuition For Convolution

Let's say the disease mutates and requires a multi-day treatment. You create a new plan: Plan: [3 2 1]

That means 3 units of the cure on the first day, 2 on the second, and 1 on the third. Ok. Given the same patient schedule [1 2 3 4 5], what's our medicine usage each day?

Uh... shoot. It's not a quick multiplication:

  • On Monday, 1 patient comes in. It's her first day, so she gets 3 units.
  • On Tuesday, the Monday gal gets 2 units (her second day), but two new patients arrive, who get 3 each (2 * 3 = 6). The total is 2 + (2 * 3) = 8 units.
  • On Wednesday, it's trickier: The Monday gal finishes (1 unit, her last day), the Tuesday people get 2 units (2 * 2), and there are 3 new Wednesday people... argh.

The patients are overlapping and it's hard to track. How can we organize this calculation?

An idea: imagine flipping the patient list, so the first patient is on the right:

           Start of line
 5 4 3 2 1

Next, imagine we have 3 separate rooms where we apply the proper dose:

 Rooms     3 2 1  

On your first day, you walk into the first room and get 3 units of medicine. The next day, you walk into room #2 and get 2 units. On the last day, you walk into room #3 and get 1 unit. There's no rooms afterwards, and your treatment is done.

To calculate the total medicine usage, line up the patients and walk them through the rooms:

 Monday
 ----------------------------
 Rooms                  3 2 1                                      
 Patients       5 4 3 2 1

 Usage                  3

On Monday (our first day), we have a single patient in the first room. She gets 3 units, for a total usage of 3. Makes sense, right?

On Tuesday, everyone takes a step forward:

 Tuesday
 ----------------------------
 Rooms                  3 2 1              
 Patients ->      5 4 3 2 1

 Usage                  6 2      = 8

The first patient is now in the second room, and there's 2 new patients in the first room. We multiply each room's dose by the patient count, then combine.

Every day we just walk the list forward:

 Wednesday
 ----------------------------
 Rooms                  3 2 1              
 Patients ->        5 4 3 2 1

 Usage                  9 4 1    = 14


 Thursday
 -----------------------------
 Rooms                  3 2 1              
 Patients ->          5 4 3 2 1

 Usage                 12 6 2    = 20


 Friday
 -----------------------------
 Rooms                  3 2 1              
 Patients ->            5 4 3 2 1

 Usage                 15 8 3    = 26

Whoa! It's intricate, but we figured it out, right? We can find the usage for any day by reversing the list, sliding it to the desired day, and combining the doses.

The total day-by-day usage looks like this (don't forget Sat and Sun, since some patients began on Friday):

Plan      *  Patient List   = Total Daily Usage
[3 2 1]   *  [1 2 3 4 5]    = [3 8 14 20 26 14 5]
              M T W T F        M T W  T  F  S  S

This calculation is the convolution of the plan and patient list. It's a fancy multiplication between a list of input numbers and a "program".



The integral of the convolution

When all treatments are finished, what was the total medicine usage? This is the integral of the convolution. (A few minutes ago, that phrase would have you jumping out of a window.)

But it's a simple calculation. Our plan gives each patient sum([3 2 1]) = 6 units of medicine. And we have sum([1 2 3 4 5]) = 15 patients. The total usage is just 6 x 15 = 90 units.

Wow, that was easy: the usage for the entire convolution is just the product of the subtotals!

\[\int (f * g) = \int f \cdot \int g\]

I hope this clicks intuitively. Note that this trick works for convolution, but not integrals in general. For example:

\[\int (x \cdot x) \ne \int x \cdot \int x\]

If we separate \(x \cdot x\) into two integrals we get:

  • \( \int (x \cdot x) = \int x^2 = \frac{1}{3} x^3 \)
  • \(\int x \cdot \int x = \frac{1}{2}x^2 \cdot \frac{1}{2}x^2 = \frac{1}{4}x^4\)

and those aren't the same. (Calculus would be much easier if we could split integrals like this.) It's strange, but \(\int (f * g)\) is probably easier to solve than \(\int (fg)\).


Application: COVID Ventilator Usage

Let's use convolution to estimate ventilator usage for incoming patients.

  • Set \(f(x)\) as the percent of patients needing ventilators. For example, [.05 .03 .01] means 5% of patients need ventilators the first week, 3% the second week, and 1% the third week.
  • Set \(g(x)\) as the weekly incoming patients, in thousands.
  • The convolution \(c(t) = f * g\), shows how many ventilators are needed each week (in thousands). \(c(5)\) is how many ventilators are needed 5 weeks from now.

Let's try it out:

  • F = [.05, .03, .01] is the ventilator use percentage by week
  • G = [10, 20, 30, 20, 10, 10, 10], is the incoming hospitalized patients. It starts at 10k per week, rises to 30k, then decays to 10k.

With these numbers, we expect a max ventilator use of 2.2k in 2 weeks:




Blurring / unblurring images

An image blur is essentially a convolution of your image with some "blurring kernel":

\[\text{blurred} = \text{image} * \text{blur}\]

Can we undo the blur? Yep! With our friend the Convolution Theorem, we can do:

\(\text{blurred} = \text{image} * \text{blur}\)
\(\mathscr{F} \lbrace \text{blurred} \rbrace = \mathscr{F} \lbrace \text{image} * \text{blur} \rbrace\)
\(\mathscr{F} \lbrace \text{blurred} \rbrace = \mathscr{F} \lbrace \text{image} \rbrace \mathscr{F} \lbrace \text{blur} \rbrace\)
\(\frac{ \mathscr{F} \lbrace \text{blurred} \rbrace }{\mathscr{F} \lbrace \text{blur} \rbrace} = \mathscr{F} \lbrace \text{image} \rbrace\)
\(\mathscr{F}^{-1} \lbrace \frac{ \mathscr{F} \lbrace \text{blurred} \rbrace }{\mathscr{F} \lbrace \text{blur} \rbrace} \rbrace = \text{image}\)


Convolution Examples







Time domain Typical Signals





\({sinc}^2(t)={\lbrack\frac{\sin(\pi t)}{\pi t}\rbrack}^2\)




Discrete Convolution

The Convolution Sum or Superposition Sum Representation of LTI Systems

The convolution allows us to find the output signal from any LTI processor in response to any input signal. We can find the output signal \(y(n)\) from an LTI processor by convolving its input signal \(x(n)\) with a second function representing the impulse response \(h(n)\) of the processor. The convolution sum or superposition sum of the sequences \(x(n)\) and \(h(n)\) can be represented by
\[y\lbrack n\rbrack=x\lbrack n\rbrack\ast h\lbrack n\rbrack=\sum_{k=-\infty}^{+\infty}x\lbrack k\rbrack h\lbrack n-k\rbrack=\sum_{k=-\infty}^{+\infty}x\lbrack n-k\rbrack h\lbrack k\rbrack\]
If an input signal, \(x[n]\), has a length of \(L\) samples and the impulse response (filter kernel), \(h[n]\), has a length of \(M\) samples, the resulting output signal, \(y[n]\), will have a length of \(N\) samples, calculated as:
\[N=L+M-1\]

Properties of Convolution

1. Commutativilty
\(x(n)\ast h(n)=h(n)\ast x(n)\)
\(\sum_{k=-\infty}^{+\infty}x\lbrack k\rbrack h\lbrack n-k\rbrack=\sum_{k=-\infty}^{+\infty}h\lbrack k\rbrack x\lbrack n-k\rbrack\)

2. Associativity (Cascaded Connection)
\((x(n)\ast h(n))\ast g(n)=x(n)\ast(h(n)\ast g(n))\)
\(y(n)=\left\{\begin{array}{l}x(n)\ast\lbrack h_1(n)\ast h_2(n)\rbrack\\x(n)\ast\lbrack h_2(n)\ast h_1(n)\rbrack\\x(n)\ast h_1(n)\ast h_2(n)\end{array}\right.\)

3. Distributivity (Parallel Connection)
\(x(n)\ast\lbrack h(n)\ast g(n)\rbrack=x(n)\ast h(n)+(x(n)\ast g(n)\)


Convolution Method

Graphical Method





\((f * g)[n] = \sum_{m=-\inf}^{\inf} f[m]g[n-m]\)

For example assuming \(a\) is the function \(f\) and \(b\) is the convolution function \(g\)



To solve this we can use the equation first we flip the function \(b\) vertically, due to the \(−m\) that appears in the equation. Then we will calculate the summation for each value of \(n\). Whilst changing \(n\), the original function does not move, however the convolution function is shifted accordingly. Starting at \(n=0\),
\(c[0] = \sum_m a[m]b[0-m] = 0 * 0.25 + 0 * 0.5 + 1 * 1 + 0.5 * 0 + 1 * 0 + 1 * 0 = 1\)
\(c[1] = \sum_m a[m]b[1-m] = 0 * 0.25 + 1 * 0.5 + 0.5 * 1 + 1 * 0 + 1 * 0 = 1\)
\(c[2] = \sum_m a[m]b[2-m] = 1 * 0.25 + 0.5 * 0.5 + 1 * 1 + 1 * 0 + 1 * 0 = 1.5\)
\(c[3] = \sum_m a[m]b[3-m] = 1 * 0 + 0.5 * 0.25 + 1 * 0.5 + 1 * 1 = 1.625\)
\(c[4] = \sum_m a[m]b[4-m] = 1 * 0 + 0.5 * 0 + 1 * 0.25 + 1 * 0.5 + 0 * 1 = 0.75\)
\(c[5] = \sum_m a[m]b[5-m] = 1 * 0 + 0.5 * 0 + 1 * 0 + 1 * 0.25 + 0 * 0.5 * 0 * 1 = 0.25\)
As you can see that is exactly what we get on the plot \(c[n]\). So we shifted around the function \(b[n]\) over the function \(a[n]\).




Table Lookup Method

\(x\lbrack n\rbrack=\{1,\;½,\;⅓\},\;h\lbrack n\rbrack=\{1,\;2\}\)

\(\begin{array}{ccccc}&&&x\lbrack n\rbrack&\\&&1&½&⅓\\&1&1&½&⅓\\h\lbrack n\rbrack&2&2&1&⅔\\&1&2½&1⅓&⅔\\&y\lbrack0\rbrack&y\lbrack1\rbrack&y\lbrack2\rbrack&y\lbrack3\rbrack\end{array}\)




Matrix by Vector Method


The convolution operation can be constructed as a matrix multiplication, where one of the inputs is converted into a Toeplitz matrix. For example, the convolution of \(\displaystyle h\) and \(\displaystyle x\) can be formulated as:
\[\displaystyle y=h\ast x={\begin{bmatrix}h_{1}&0&\cdots &0&0\\h_{2}&h_{1}&&\vdots &\vdots \\h_{3}&h_{2}&\cdots &0&0\\\vdots &h_{3}&\cdots &h_{1}&0\\h_{m-1}&\vdots &\ddots &h_{2}&h_{1}\\h_{m}&h_{m-1}&&\vdots &h_{2}\\0&h_{m}&\ddots &h_{m-2}&\vdots \\0&0&\cdots &h_{m-1}&h_{m-2}\\\vdots &\vdots &&h_{m}&h_{m-1}\\0&0&0&\cdots &h_{m}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\vdots \\x_{n}\end{bmatrix}}\]
\[\displaystyle y^{T}={\begin{bmatrix}h_{1}&h_{2}&h_{3}&\cdots &h_{m-1}&h_{m}\end{bmatrix}}{\begin{bmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}&0&0&0&\cdots &0\\0&x_{1}&x_{2}&x_{3}&\cdots &x_{n}&0&0&\cdots &0\\0&0&x_{1}&x_{2}&x_{3}&\ldots &x_{n}&0&\cdots &0\\\vdots &&\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\cdots &0&0&x_{1}&\cdots &x_{n-2}&x_{n-1}&x_{n}&0\\0&\cdots &0&0&0&x_{1}&\cdots &x_{n-2}&x_{n-1}&x_{n}\end{bmatrix}}\]



Echo Method

Let:
Signal \(x[n]=a\delta [n-n_{1}]\) (A delta at \(n_{1}\) with amplitude \(a\))
Signal \(h[n]=b\delta [n-n_{2}]\) (A delta at \(n_{2}\) with amplitude \(b\))
The convolution \(y[n]=x[n]*h[n]\) is:
\(y\lbrack n\rbrack=(ab)\delta\lbrack n-(n_1+n_2)\rbrack\)


If 𝑥[𝑛] or ℎ[𝑛] is pretty short we can represent \(𝑥[𝑛]\) or \(ℎ[𝑛]\) with a linear combination of discrete impulses:

\(\operatorname{𝑥}\lbrack\operatorname{𝑛}\rbrack=1,\;\;\;\;\;0\;\leq\operatorname{𝑛}\leq4\)
\(\operatorname{𝑥}\lbrack\operatorname{𝑛}\rbrack\;=\operatorname{𝛿}\lbrack\operatorname{𝑛}\rbrack\;+\operatorname{𝛿}\lbrack\operatorname{𝑛}-1\rbrack\;+\operatorname{𝛿}\lbrack\operatorname{𝑛}-2\rbrack\;+\operatorname{𝛿}\lbrack\operatorname{𝑛}-3\rbrack\;+\operatorname{𝛿}\lbrack\operatorname{𝑛}-4\rbrack\)

\(h\lbrack\operatorname{𝑛}\rbrack=1,\;\;\;-2\;\leq\operatorname{𝑛}\leq2\)
\(h\lbrack\operatorname{𝑛}\rbrack=\operatorname{𝛿}\lbrack\operatorname{𝑛}+2\rbrack\;+\operatorname{𝛿}\lbrack\operatorname{𝑛}+1\rbrack\;+\operatorname{𝛿}\lbrack\operatorname{𝑛}\rbrack\;+\operatorname{𝛿}\lbrack\operatorname{𝑛}-1\rbrack\;+\operatorname{𝛿}\lbrack\operatorname{𝑛}-2\rbrack\)

\(\operatorname{𝑦}\lbrack\operatorname{𝑛}\rbrack=\operatorname{𝛿}\lbrack\operatorname{𝑛}+2\rbrack+2\operatorname{𝛿}\lbrack\operatorname{𝑛}+1\rbrack+3\operatorname{𝛿}\lbrack\operatorname{𝑛}\rbrack+4\operatorname{𝛿}\lbrack\operatorname{𝑛}-1\rbrack+5\operatorname{𝛿}\lbrack\operatorname{𝑛}-2\rbrack+4\operatorname{𝛿}\lbrack\operatorname{𝑛}-3\rbrack+3\operatorname{𝛿}\lbrack\operatorname{𝑛}-4\rbrack+2\operatorname{𝛿}\lbrack\operatorname{𝑛}-5\rbrack+\operatorname{𝛿}\lbrack\operatorname{𝑛}-6\rbrack\)


\(\left\{\begin{array}{l}\delta\lbrack n\rbrack\ast x\lbrack n\rbrack=x\lbrack n\rbrack\\\delta\lbrack n-n_0\rbrack\ast x\lbrack n\rbrack={\left.x\lbrack n\rbrack\right|}_{n=n_0}\end{array}\right.\)

\(x\lbrack n\rbrack=\{1,\;½,\;⅓\},\;h\lbrack n\rbrack=\{1,\;2\}\)

\(y\lbrack n\rbrack=x\lbrack n\rbrack\ast h\lbrack n\rbrack=(\delta\lbrack n\rbrack+½\delta\lbrack n-1\rbrack+⅓\delta\lbrack n-2\rbrack)\ast(\delta\lbrack n\rbrack+2\delta\lbrack n-1\rbrack)\)
\(=\delta\lbrack n\rbrack\ast\delta\lbrack n\rbrack+2\delta\lbrack n\rbrack\ast\delta\lbrack n-1\rbrack+½\delta\lbrack n-1\rbrack\ast\delta\lbrack n\rbrack+2\cdot½\delta\lbrack n-1\rbrack\ast\delta\lbrack n-1\rbrack+⅓\delta\lbrack n-2\rbrack\ast\delta\lbrack n\rbrack+2\cdot⅓\delta\lbrack n-2\rbrack\ast\delta\lbrack n-1\rbrack\)
\(=\delta\lbrack n\rbrack+2\delta\lbrack n-1\rbrack+½\delta\lbrack n-1\rbrack+\delta\lbrack n-2\rbrack+⅓\delta\lbrack n-2\rbrack+⅔\delta\lbrack n-3\rbrack\)
\(=\delta\lbrack n\rbrack+2½\delta\lbrack n-1\rbrack+1⅓\delta\lbrack n-2\rbrack+⅔\delta\lbrack n-3\rbrack\)


[Ex] \((\delta\lbrack n\rbrack+\delta\lbrack n-2\rbrack+\delta\lbrack n-10000\rbrack+2\delta\lbrack n-10005\rbrack)\ast(\delta\lbrack n-1\rbrack+\delta\lbrack n-1000\rbrack)\)
\(=\delta\lbrack n-1\rbrack+\delta\lbrack n-1000\rbrack+\delta\lbrack n-3\rbrack+\delta\lbrack n-1002\rbrack+\delta\lbrack n-10001\rbrack+\delta\lbrack n-11000\rbrack+2\delta\lbrack n-10006\rbrack+2\delta\lbrack n-11005\rbrack\)
\(=\delta\lbrack n-1\rbrack+\delta\lbrack n-3\rbrack+\delta\lbrack n-1000\rbrack+\delta\lbrack n-1002\rbrack+\delta\lbrack n-10001\rbrack+2\delta\lbrack n-10006\rbrack+\delta\lbrack n-11000\rbrack+2\delta\lbrack n-11005\rbrack\)


Unit Step Signal

[Ex] \(y\lbrack n\rbrack=(u\lbrack n\rbrack-u\lbrack n-2\rbrack)\ast(u\lbrack n+1\rbrack-u\lbrack n-1\rbrack)\)
\(=(\delta\lbrack n\rbrack+\delta\lbrack n-1\rbrack)\ast(\delta\lbrack n+1\rbrack+\delta\lbrack n\rbrack)\)
\(=\delta\lbrack n+1\rbrack+\delta\lbrack n\rbrack+\delta\lbrack n\rbrack+\delta\lbrack n-1\rbrack\)
\(=\delta\lbrack n+1\rbrack+2\delta\lbrack n\rbrack+\delta\lbrack n-1\rbrack\)

2D Convolution

Spatial Convolution

The kernel is flipped horizontally and vertically before the sliding multiplication.

\(f(x,y)\ast g(x,y)=\int_{\tau_2=-\infty}^{+\infty}\int_{\tau_1=-\infty}^{+\infty}f(\tau_1,\tau_2)\cdot g(x-\tau_1,y-\tau_2)\operatorname d\tau_1\operatorname d\tau_2\)

\(f\lbrack x,y\rbrack\ast g\lbrack x,y\rbrack=\sum_{n_2=-\infty}^{+\infty}\sum_{n_1=-\infty}^{+\infty}f\lbrack n_1,n_2\rbrack\cdot g\lbrack x-n_1,y-n_2\rbrack\)

\(y\lbrack m,n\rbrack=x\lbrack m,n\rbrack\ast h\lbrack m,n\rbrack=\sum_{j=-\infty}^{+\infty}\sum_{i=-\infty}^{+\infty}x\lbrack i,j\rbrack\cdot h\lbrack m-i,n-j\rbrack\)






















Discrete-time Fourier Transform (DTFT)

DTFT
Discrete-time Fourier Transform (DTFT)

The discrete signals coverted to its continuous time domain frequencies.

\(X(e^{j\omega})=\sum_{n=-\infty}^\infty x\lbrack n\rbrack e^{-j\omega n}\)

compared to analog signals
\(X(j\Omega)=\int_{-\infty}^\infty x(t)e^{-j\Omega t}\operatorname dt\)


Typical Usage (Oppenheim-Schafer convention)

\(\Omega \) (Capital Omega): Used for continuous-time frequency, usually measured in radians per second (\(rad/s\)). \(\Omega =2\pi f\)
\(\omega \) (Lowercase omega): Used for discrete-time frequency (DTFT), usually measured in radians per sample.

\(\left\{\begin{array}{lc}DTFT&X(e^{j\omega})=\sum_{n=-\infty}^\infty x\lbrack n\rbrack e^{-j\omega n}\\IDTFT&x\lbrack n\rbrack=\frac1{2\pi}\int_{-\pi}^\pi{X(e^{j\omega n})}\operatorname d\omega\end{array}\right.,\;\omega:digital,\;\omega\in(-\pi,\;\pi)\)

\(e^{j\omega n}=e^{j(\omega+2\pi k)n}\)

\(x\lbrack n\rbrack=\delta\lbrack n\rbrack\xrightarrow{DTFT}X(e^{j\omega})=\sum_{n=-\infty}^\infty\delta\lbrack n\rbrack e^{-j\omega n}=1\)

\(x\lbrack n\rbrack=a^nu\lbrack n\rbrack\xrightarrow{DTFT}X(e^{j\omega})=\sum_{n=-\infty}^\infty a^nu\lbrack n\rbrack e^{-j\omega n}=\sum_{n=0}^\infty a^ne^{-j\omega n}=\sum_{n=0}^\infty{(ae^{-j\omega})}^n\)
\(=\frac1{1-ae^{-j\omega}},\;\left|ae^{-j\omega}\right|<1\Rightarrow\left|a\right|<1\)

Fourier Series Expansion & Discrete time Signals

Fourier Series Expansion

\(x(t)=\sum_{k=-\infty}^{+\infty}X_ke^{jk\Omega_0t}\)
\(X_k=\frac1T\int_Tx(t)e^{-jk\Omega_0t}\operatorname dt\)

Fourier Transform

\(x(t)=\frac1{2\pi}\int_{-\infty}^{+\infty}X(j\Omega)e^{j\Omega t}\operatorname d\Omega\)
\(X(j\Omega)=\int_{-\infty}^{+\infty}x(t)e^{-j\Omega t}\operatorname dt\)

Laplace Transform

\(x(t)=\frac1{2\pi i}\lim_{T\rightarrow\infty}\int_{\gamma-iT}^{r+iT}X(s)e^{st}\operatorname ds\)
\(X(s)=\int_{-\infty}^{+\infty}x(t)e^{-st}\operatorname dt\)

the inverse Laplace transform \(f(t)=\mathcal{L}^{-1}\{F(s)\}\) and the Laplace transform \(F(s)=\mathcal{L}\{f(t)\}\) are fundamentally linked by the same Region of Convergence (ROC) in the \(s\)-plane.



(I) \(x(t)=\delta(t)\xrightarrow{\mathcal L}\int_{-\infty}^{+\infty}\delta(t)e^{-st}\operatorname dt=1\)

(II) \(x(t)=u(t)\xrightarrow{\mathcal L}\int_{-\infty}^{+\infty}u(t)e^{-st}\operatorname dt=\int_0^{+\infty}1\cdot e^{-st}\operatorname dt\)
\(=\left.\frac1{-s}e^{-st}\right|_0^\infty=\frac1{-s}(e^{-\infty}-e^0)=\frac1s\)

(III) \(x(t)=e^{at}u(t)\xrightarrow{\mathcal L}\int_{-\infty}^{+\infty}e^{at}u(t)e^{-st}\operatorname dt=\int_0^{+\infty}e^{at}e^{-st}\operatorname dt\)
\(=\int_0^{+\infty}e^{-(s-a)t}\operatorname dt=\left.\frac1{-(s-a)}e^{-(s-a)t}\right|_0^\infty=\frac1{-(s-a)}(e^{-\infty}-e^0)=\frac1{s-a}\)


Discrete-time Signals




\(analog\;x_a(t)\;\xrightarrow{sampling}x\lbrack n\rbrack=x_a(nT),\;sequence\)


Typical Signals

unit impulse
\(\delta\lbrack n\rbrack=\left\{\begin{array}{lc}1&if\;n=0\\0&if\;n\neq0\end{array}\right.\)

unit step
\(u\lbrack n\rbrack=\left\{\begin{array}{lc}1&if\;n\geq0\\0&otherwise\end{array}\right.\)
\(=\sum_{m=0}^\infty\delta\lbrack n-m\rbrack\)
\(=\sum_{m=-\infty}^n\delta\lbrack m\rbrack=\left\{\begin{array}{lc}1&if\;n\geq0\\0&otherwise\end{array}\right.\)



\(\delta[n]=u[n]-u[n-1]\)




Sinusoidal Sequence

\(x\lbrack n\rbrack=A\cos(\omega_0n+\theta)\) is NOT necessary periodic

\(x\lbrack n\rbrack=x\lbrack n+N\rbrack,\;n\nmid\pi\)




Analog Signals, Signal operation, Basic functions

Analog Signals

\(x(\underbrace{t}_{\text{time}})\)
[Ex] \(x(t) = \sin(3\pi t)\)

Deterministic Signals \(f(x)\) \(\Leftrightarrow\) Random Signals (e.g., noise)

Periodic Signals vs. Aperiodic Signals
\(x(t)=x(t+T)\), \(T\): constant, period




Signal operation
Time Shifting, Time Scaling, Time Reversal


The order of operations for signal transformation

The recommended order of operations for signal transformation is 1) Time Shifting, 2) Time Scaling/Reversal, and 3) Amplitude Scaling, often summarized as shifting before scaling to avoid errors in mapping the independent variable. Applying transformations in this sequence ensures that time shifts are not improperly scaled

Key Takeaway: If the transformation is given in the form \( x(at - b) \), it is often safer to rewrite it as \( x\left(a\left(t - \frac{b}{a}\right)\right) \), indicating a shift by \( \frac{b}{a} \) after the scaling \( a \), or to follow the "shift then scale" rule strictly to avoid confusion.

Example 1: Horizontal Scaling and Shifting

Let the base function be \( x(t) \). We want to graph \( y(t) = x(2t - 4) \).

  • Common Mistake: Thinking the shift is 4 units right.
  • Correct Approach (Factor out 'a'): Rewrite \( 2t - 4 \) as \( 2(t - 2) \).
  • Transformation:
    • Scale: Horizontal compression by a factor of 2 (\( t \to 2t \)).
    • Shift: Horizontal shift to the right by 2 (\( t \to t - 2 \)).
  • Verification: If \( x(t) \) has a feature at \( t = 2 \), \( x(2t - 4) \) has that feature when \( 2t - 4 = 2 \), which means \( 2t = 6 \), or \( t = 3 \). Using \( x(2(t - 2)) \), shifting 2 units right (\( t - 2 \)) and then compressing means \( 2 \to 4 \), then \( 4 \to 2 \) is wrong. The factored form \( x(a(t - b/a)) \) shows the shift happens after the compression relative to the original shape.
Example 2: Horizontal Scaling and Negative Shift

Let the base function be \( x(t) \). We want to graph \( y(t) = x(3t + 6) \).

  • Rewrite: \( x(3(t + 2)) \) or \( x(3(t - (-2))) \).
  • Transformation:
    • Scale: Horizontal compression by a factor of 3 (\( t \to 3t \)).
    • Shift: Horizontal shift to the left by 2 (\( t \to t + 2 \)).
Example 3: Negative Scaling (Reflection) and Shift

Let the base function be \( x(t) \). We want to graph \( y(t) = x(4 - t) \), which is \( x(-t + 4) \).

  • Rewrite: \( x(-(t - 4)) \).
  • Transformation:
    • Reflection: Horizontal reflection across the vertical axis (\( t \to -t \)).
    • Shift: Horizontal shift to the right by 4 (\( t \to t - 4 \)).
  • Why Factor? Without factoring, \( x(4 - t) \) looks like a left shift. By factoring out the negative, the \( t - 4 \) clearly indicates a shift to the right.
Common Signal Transformation Sequence:
  • Time Shifting (\(x(t \pm t_0)\)): Shift the signal horizontally, adding/subtracting from the time axis, before applying other time-based changes.
  • Time Scaling/Reversal (\(x(at)\) or \(x(-t)\)): Compress, expand, or flip the signal around the vertical axis.
  • Amplitude Scaling/Transformation (\(Ax(t) + B\)): Scale or shift the signal's vertical amplitude last.

[Ex] To convert \( x(t) = 3 - t \) into \( y(t) = -x(-2t + 4) \), the order of operations for the time transformations (the parts inside the parentheses) is critical. There are two standard ways to do this correctly: Shift then Scale or Scale then Shift.

Method 1: Shift then Scale (The "Inside-Out" Method)

When you shift first, you apply the constant \(+4\) directly to \(t\), and then apply the scaling factor \(-2\) only to the \(t\) variable itself.

1. Horizontal Shift: Replace \(t\) with \((t + 4)\). This shifts \(x(t)\) to the left by 4 units.
\[ x_1(t) = x(t + 4) = 3 - (t + 4) = -t - 1 \]

2. Time Scaling & Reflection: Replace \(t\) with \(-2t\). This reflects the graph and compresses it by 2.
\[ x_2(t) = x_1(-2t) = x(-2t + 4) = -(-2t) - 1 = 2t - 1 \]

3. Amplitude Reversal: Multiply the entire function by \(-1\).
\[ y(t) = -x_2(t) = -(2t - 1) = -2t + 1 \]

Method 2: Scale then Shift (The Factored Method)

If you scale first, you must factor the inside of the function to see the "true" shift: \( x(-2(t - 2)) \).

1. Time Scaling & Reflection: Replace \(t\) with \(-2t\).
\[ x_a(t) = x(-2t) = 3 - (-2t) = 3 + 2t \]

2. Horizontal Shift: Replace \(t\) with \((t - 2)\). Since it is \((t - 2)\), this is a shift to the right by 2 units.
\[ x_b(t) = x(-2(t - 2)) = x(-2t + 4) = 3 + 2(t - 2) = 2t - 1 \]

3. Amplitude Reversal: Multiply the entire function by \(-1\).
\[ y(t) = -x_b(t) = -(2t - 1) = -2t + 1 \]



We study them with an example. For that, consider a signal \( x(t) \) as follows:
\(x(t) = \begin{cases} 1, & 0 \le t \le 1, \\ 2 - t, & 1 \le t \le 2, \\ 0, & \text{otherwise}. \end{cases}\)

A graphical representation of this signal is shown below.



Now, we have a signal transformation given by \(x(-2t + 3)\). The resulting signal can be obtained in two ways which we see one by one.


Method 1: Right Hand Side (RHS) to Left Hand Side (LHS)

In this method, we carry out transformation \((-2t + 3)\) by moving from RHS to LHS, symbolically \((-2t + 3_{\leftarrow})\). So, we will have these steps:

  • Step 1: Time advance by 3 to obtain \(x(t + 3)\)
  • Step 2: Scaling by 2 to obtain \(x(2t + 3)\)
  • Step 3: Time reversal to get finally \(x(-2t + 3)\)


Method 2: LHS to RHS

This method is performed from LHS to RHS, symbolically \((\rightarrow -2t + 3)\). However, it has an additional step than method 1, which we see next.

  • Step 1: Write the transformation in a factored form such that the variable \(t\) has a unit coefficient. For that, take out common factor \((-2)\) from the equation to obtain \(-2(t - \frac{3}{2})\).
  • Step 2: Time reversal to get \(x(-t)\)
  • Step 3: Time scaling by 2 to get \(x(-2t)\)
  • Step 4: Time delay by \(\frac{3}{2}\) to finally get \(x\left(-2\left(t - \frac{3}{2}\right)\right)\)


We can observe that both methods result in the same result. Hence, we can use any of the methods depending on our individual preference.


Elementary signal models

Some of the basic signals like unit step, impulse and exponential are needed to build other signals. Unit impulse is a rectangular pulse with a width that has become infinitesimally small, a height that has become infinitely large and overall area is unity.

1. Unit Impulse
\(\delta(t) = \begin{cases} 1, & t = 0 \\ 0, & t \neq 0 \end{cases}\)

t 0 1

2. Unit Step
\(u(t) = \begin{cases} 1, & t \geq 0 \\ 0, & \text{otherwise} \end{cases}\)

t 0 1

3. Unit pulse
\(\Pi(t) = \begin{cases} 1, & -\frac{1}{2} \leq t \leq \frac{1}{2} \\ 0, & \text{otherwise} \end{cases}\)
\(=u(t+½)-u(t-½)\)

t ½ 1

4. Sinc function
\(Sinc(t) = \frac{\sin(\pi t)}{\pi t}\)




L'Hôpital's rule

\(\begin{aligned} \text{Sinc}(0) &= \left. \frac{\frac{d}{dt} \sin(\pi t)}{\frac{d}{dt} (\pi t)} \right|_{t=0} \\ &= \left. \frac{\pi \cos(\pi t)}{\pi} \right|_{t=0} \\ &= \cos(0) = 1 \end{aligned}\)

5. Signum function
\(\text{sgn}(t) = \begin{cases} 1 & t > 0 \\ 0 & t = 0 \\ -1 & t < 0 \end{cases}\)
\( \text{sgn}(t) = -1 + 2u(t) \)




6. Unit ramp function
\(r(t)\operatorname{:=}{\{{\textstyle\begin{array}{ll}t,&t\geq0;\\0,&t<0\end{array}}}\)




7. Unit parabolic function
\(\text{P}(t) = \begin{cases} \frac{t^2}{2} & \text{for } t \ge 0 \\ 0 & \text{for } t < 0 \end{cases}\)
or \( \text{P}(t) = \frac{t^2}{2}u(t) \)




Discrete Fourier Transform (DFT)

Discrete Time Fourier Transform (DTFT)

\(X(e^{j\omega})=\sum_{n=-\infty}^\infty x\lbrack n\rbrack e^{-j\omega n}\)
\(\omega_k=\frac{2\pi}Nk\)



Discrete Fourier Transform (DFT)

General DFT Formula

\( X[k] = \sum_{n=0}^{N-1} x[n]e^{-j\frac{2\pi}{N}kn}, \quad k = 0, 1, \dots, N-1 \)


[Ex] 4-pt DFT
Using \( x = \{1, 2, 3, 4\} \):



\( X[0] = \sum_{n=0}^{3} xe^{-j\frac{2\pi}{4} \cdot 0 \cdot n} = x[0] + x[1] + x[2] + x[3] = 1 + 2 + 3 + 4 = 10 \)

\( X[1] = \sum_{n=0}^{3} xe^{-j\frac{2\pi}{4} \cdot 1 \cdot n} = x[0] + x[1] \cdot e^{-j\frac{2\pi}{4} \cdot 1 \cdot 1} + x[2] \cdot e^{-j\frac{2\pi}{4} \cdot 1 \cdot 2} + x[3] \cdot e^{-j\frac{2\pi}{4} \cdot 1 \cdot 3} \)
\( = 1 + 2(-j) + 3(-1) + 4(j) = (1 - 3) + j(4 - 2) = -2 + 2j \)

\( X[2] = \sum_{n=0}^{3} xe^{-j\frac{2\pi}{4} \cdot 2 \cdot n} = x[0] + x[1] \cdot e^{-j\frac{2\pi}{4} \cdot 2 \cdot 1} + x[2] \cdot e^{-j\frac{2\pi}{4} \cdot 2 \cdot 2} + x[3] \cdot e^{-j\frac{2\pi}{4} \cdot 2 \cdot 3} \)
\( = 1 + 2(-1) + 3(1) + 4(-1) = 1 - 2 + 3 - 4 = -2 \)

\( X[3] = \sum_{n=0}^{3} xe^{-j\frac{2\pi}{4} \cdot 3 \cdot n} = x[0] + x[1] \cdot e^{-j\frac{2\pi}{4} \cdot 3 \cdot 1} + x[2] \cdot e^{-j\frac{2\pi}{4} \cdot 3 \cdot 2} + x[3] \cdot e^{-j\frac{2\pi}{4} \cdot 3 \cdot 3} \)
\( = 1 + 2(j) + 3(-1) + 4(-j) = (1 - 3) + j(2 - 4) = -2 - 2j \)

Final DFT Sequence: \( X[k] = \{10, -2+2j, -2, -2-2j\} \)



\( \begin{bmatrix} X[0] \\ X[1] \\ X[2] \\ X[3] \end{bmatrix} = \begin{bmatrix} e^{-j\frac{2\pi}{4} \cdot 0 \cdot 0} & e^{-j\frac{2\pi}{4} \cdot 0 \cdot 1} & e^{-j\frac{2\pi}{4} \cdot 0 \cdot 2} & e^{-j\frac{2\pi}{4} \cdot 0 \cdot 3} \\ e^{-j\frac{2\pi}{4} \cdot 1 \cdot 0} & e^{-j\frac{2\pi}{4} \cdot 1 \cdot 1} & e^{-j\frac{2\pi}{4} \cdot 1 \cdot 2} & e^{-j\frac{2\pi}{4} \cdot 1 \cdot 3} \\ e^{-j\frac{2\pi}{4} \cdot 2 \cdot 0} & e^{-j\frac{2\pi}{4} \cdot 2 \cdot 1} & e^{-j\frac{2\pi}{4} \cdot 2 \cdot 2} & e^{-j\frac{2\pi}{4} \cdot 2 \cdot 3} \\ e^{-j\frac{2\pi}{4} \cdot 3 \cdot 0} & e^{-j\frac{2\pi}{4} \cdot 3 \cdot 1} & e^{-j\frac{2\pi}{4} \cdot 3 \cdot 2} & e^{-j\frac{2\pi}{4} \cdot 3 \cdot 3} \end{bmatrix} \begin{bmatrix} x[0] \\ x[1] \\ x[2] \\ x[3] \end{bmatrix} \)

If \( x \) is real, i.e., \( x = x^* \)
then \( X[k] = X^*[N - k] \)

  • \( X[0] = X^*[4] = X^*[0] \) (Must be Purely Real)
  • \( X[1] = X^*[3] \) (Conjugate Pair)
  • \( X[2] = X^*[2] \) (Must be Purely Real)
  • \( X[3] = X^*[1] \) (Conjugate Pair)

  • \( X[0] = X^*[0] \) (Purely Real)
  • \( X[1] = X^*[7] \)
  • \( X[2] = X^*[6] \)
  • \( X[3] = X^*[5] \)
  • \( X[4] = X^*[4] \) (Purely Real - Nyquist)
  • \( X[5] = X^*[3] \)
  • \( X[6] = X^*[2] \)
  • \( X[7] = X^*[1] \)

Property: Conjugate Symmetry for Real Signals \( x \in \mathbb{R} \)
\( X^*[N-k]\)
\( = \left( \sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi}{N}(N-k)n} \right)^* \) // Start with the definition at index \( N-k \)
\( = \sum_{n=0}^{N-1} x^*[n] e^{j\frac{2\pi}{N}(N-k)n} \) // Conjugate changes \( -j \) to \( +j \) and \( x \) to \( x^* \)
\( = \sum_{n=0}^{N-1} x[n] e^{j2\pi n} \cdot e^{-j\frac{2\pi}{N}kn} \) // Assumes \( x^* = x \) (Real Signal)
\( = \sum_{n=0}^{N-1} x[n] \cdot (1) \cdot e^{-j\frac{2\pi}{N}kn} = X[k] \) // Since \( e^{j2\pi n} = 1 \) for all integer \( n \)
Result: \( X^*[N-k] = X[k] \)   or   \( X[N-k] = X^*[k] \)


\( X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} kn}, \quad k = 0, 1, \dots, N-1 \quad (\text{DFT})\)

\( x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j \frac{2\pi}{N} kn}, \quad n = 0, 1, \dots, N-1 \quad (\text{IDFT}) \)


4-Point IDFT Matrix Representation

\( \begin{bmatrix} x(0) \\ x(1) \\ x(2) \\ x(3) \end{bmatrix} = \frac{1}{4} \begin{bmatrix} e^{j \frac{2\pi}{4} \cdot 0 \cdot 0} & e^{j \frac{2\pi}{4} \cdot 0 \cdot 1} & e^{j \frac{2\pi}{4} \cdot 0 \cdot 2} & e^{j \frac{2\pi}{4} \cdot 0 \cdot 3} \\ e^{j \frac{2\pi}{4} \cdot 1 \cdot 0} & e^{j \frac{2\pi}{4} \cdot 1 \cdot 1} & e^{j \frac{2\pi}{4} \cdot 1 \cdot 2} & e^{j \frac{2\pi}{4} \cdot 1 \cdot 3} \\ e^{j \frac{2\pi}{4} \cdot 2 \cdot 0} & e^{j \frac{2\pi}{4} \cdot 2 \cdot 1} & e^{j \frac{2\pi}{4} \cdot 2 \cdot 2} & e^{j \frac{2\pi}{4} \cdot 2 \cdot 3} \\ e^{j \frac{2\pi}{4} \cdot 3 \cdot 0} & e^{j \frac{2\pi}{4} \cdot 3 \cdot 1} & e^{j \frac{2\pi}{4} \cdot 3 \cdot 2} & e^{j \frac{2\pi}{4} \cdot 3 \cdot 3} \end{bmatrix} \begin{bmatrix} X[0] \\ X[1] \\ X[2] \\ X[3] \end{bmatrix} \)


\( = \frac{1}{4} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & j & -1 & -j \\ 1 & -1 & 1 & -1 \\ 1 & -j & -1 & j \end{bmatrix} \begin{bmatrix} 10 \\ -2+2j \\ -2 \\ -2-2j \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix} \)



[Ex] \(x[n] = \begin{cases} 1, & 0 \le n \le N-1 \\ 0, & \text{otherwise} \end{cases}\)



DTFT Calculation
\( X(e^{j\omega})\)
\(= \sum_{n=0}^{N-1} 1 \cdot e^{-j\omega n} \)
\( = \frac{1 - e^{-j\omega N}}{1 - e^{-j\omega}} \)

\( |X(e^{j\omega})| \)



DFT of a Constant Sequence

\( N\text{-pt DFT}:\) \(X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} kn} \)
\( = \sum_{n=0}^{N-1} 1 \cdot e^{-j \frac{2\pi}{N} kn} \)
\( = \frac{1 - e^{-j \frac{2\pi}{N} kN}}{1 - e^{-j \frac{2\pi}{N} k}} \)
\( = \frac{1 - e^{-j 2\pi k}}{1 - e^{-j \frac{2\pi}{N} k}} \)
\( = 0 \)

Note: This result holds for all values of \( k \) where the denominator is not zero (i.e., \( k \neq 0, \pm N, \pm 2N, \dots \)).
For \( k=0 \), the sum is simply \( \sum_{n=0}^{N-1} 1 = N \).

\( N\text{-pt DFT} : X[k] = \sum_{n=0}^{N-1} x(n) e^{-j \frac{2\pi}{N} kn} \)
\( = \sum_{n=0}^{N-1} 1 \cdot e^{-j \frac{2\pi}{N} kn} \)
\( = \begin{cases} \frac{1 - e^{-j \frac{2\pi}{N} kN}}{1 - e^{-j \frac{2\pi}{N} k}}, & k \neq 0 \\ N, & k = 0 \end{cases} \)
\( = \begin{cases} 0, & k \neq 0 \\ N, & k = 0 \end{cases} \)



Zero padding

M-point DFT Calculation (\( M > N \))

\( X(k) = \sum_{n=0}^{M-1} x[n] \cdot e^{-j \frac{2\pi}{M} kn} \)
\( = \sum_{n=0}^{N-1} 1 \cdot e^{-j \frac{2\pi}{M} kn} \)
\( = \begin{cases} \frac{1 - e^{-j \frac{2\pi}{M} kN}}{1 - e^{-j \frac{2\pi}{M} k}}, & k \neq 0 \\ N, & k = 0 \end{cases} \)



DFT vs DTFT

Discrete Fourier Transform vs Discrete Time Fourier Transform
Discrete Fourier Transform (DFT)
Discrete-Time Fourier Transform (DTFT)

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

DFT: (N-pt) \( X[k] = \sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi}{N} kn} \)
IDFT: \(x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2\pi}{N} kn}\)

The DFT is obtained by sampling the DTFT at \( \omega_k = \frac{2\pi}{N} k \) periodic
\( X(k) = \sum_{n=0}^{N-1} x(n) e^{-j\frac{2\pi}{N} kn} \)
For \( 0 \le k \le N-1 \)



Fourier Series Expansion

For a periodic signal \(\tilde{x}(t) = \tilde{x}(t + T_0)\), where \(T_0\) is the period
Fourier Series Expansion \(\tilde{x}(t) = \sum_{k=-\infty}^{\infty} \tilde{X}_k e^{j k \Omega_0 t}\), where \(\Omega_0 = \frac{2\pi}{T_0}\)
\(\tilde{x}[n] = \tilde{x}(nT)\), where \(T\) is the sampling period, \(NT=T_0\)
\(= \sum_{k=-\infty}^{\infty} \tilde{X}_k e^{j k \frac{2\pi}{T_0} nT}\)
\(= \sum_{k=-\infty}^{\infty} \tilde{X}_k e^{j k \frac{2\pi}{NT} nT}\) \(\because NT=T_0\)
\(= \sum_{k=-\infty}^{\infty} \tilde{X}_k e^{j \frac{2\pi}{N} kn}\)
\(= \sum_{k=0}^{N-1} \tilde{X}_k e^{j \frac{2\pi}{N} kn}\) \(\because e^{j\frac{2\pi}Nkn}=e^{j\frac{2\pi}N(k+N)n}\)



Discrete Fourier Series (DFS)

\( \tilde{X}[k] = \sum_{n=0}^{N-1} \tilde{x}[n] e^{-j \frac{2\pi}{N} kn} \)
\( \tilde{x}[n] = \frac{1}{N} \sum_{k=0}^{N-1} \tilde{X}[k] e^{j \frac{2\pi}{N} kn} \)

\(x\lbrack n\rbrack=\tilde x\lbrack n\rbrack\;\;\;0\leq n\leq N-1\)


F.S. (Fourier Series)

Synthesis: \( \tilde{x}(t) = \sum_{k=-\infty}^{\infty} \tilde{X}_k e^{j k \Omega_0 t} \)
Analysis: discrete \( \tilde{X}_k = \frac{1}{T} \int_{T} \tilde{x}(t) e^{-j k \Omega_0 t} dt \)

F.T. (Fourier Transform)

Synthesis (Inverse): \( x(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} X(j\Omega) e^{j \Omega t} d\Omega \)
Analysis (Forward): continuous \( X(j\Omega) = \int_{-\infty}^{\infty} x(t) e^{-j \Omega t} dt \)



\(\begin{array}{l|l|l} \text{\textbf{Category}} & \text{\textbf{Time domain}} & \text{\textbf{Frequency domain}} \\ \hline \text{CTFT} & x(t) = \int_{-\infty}^{+\infty} X(f)e^{j2\pi ft} df & X(f) = \int_{-\infty}^{+\infty} x(t)e^{-j2\pi ft} dt \\[15pt] \text{CTFS} & x(t) = \sum_{m=-\infty}^{\infty} X[m]e^{j2\pi m \frac{t}{T}} & X[m] = \frac{1}{T} \int_{-T/2}^{T/2} x(t)e^{-j2\pi m \frac{t}{T}} dt \\[15pt] \text{DTFT} & x[n] = \int_{-1/2}^{1/2} \tilde{X}(\varphi)e^{j2\pi \varphi n} d\varphi & \tilde{X}(\varphi) = \sum_{n=-\infty}^{\infty} x[n]e^{-j2\pi \varphi n} \\[15pt] \text{DTFS} & x[n] = \sum_{m=0}^{N-1} \tilde{X}[m]e^{j2\pi \frac{mn}{N}} & \tilde{X}[m] = \frac{1}{N} \sum_{n=0}^{N-1} x[n]e^{-j2\pi \frac{mn}{N}} \end{array}\)


Aperiodic Analysis

\( x(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} X(j\Omega) e^{j\Omega t} d\Omega \)
\( X(j\Omega) = \int_{-\infty}^{\infty} x(t) e^{-j\Omega t} dt \)

Sampling (periodic \( T \)), \( x[n] = x(nT) \)

\( N \)-pt DFT

\( X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} kn} , \quad 0 \leq k \leq N-1 \)
\( x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j \frac{2\pi}{N} kn} , \quad 0 \leq n \leq N-1 \)


Periodic analog

\( \tilde{x}(t) = \sum_{k=-\infty}^{\infty} \tilde{X}_k e^{jk\Omega_0 t} \)
\( \tilde{X}_k = \frac{1}{T_0} \int_{T_0} \tilde{x}(t) e^{-jk\Omega_0 t} dt \)

Sampling at period \( T \), \( \tilde{x}[n] = \tilde{x}(nT) \)

\( N \)-pt DFS

\( \tilde{X}[k] = \sum_{n=0}^{N-1} \tilde{x}[n] e^{-j \frac{2\pi}{N} kn} \)
\( \tilde{x}[n] = \frac{1}{N} \sum_{k=0}^{N-1} \tilde{X}[k] e^{j \frac{2\pi}{N} kn} \)


Aperiodic Analysis DTFT DFT

\( x(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} X(j\Omega) e^{j\Omega t} d\Omega \)
\( X(j\Omega) = \int_{-\infty}^{\infty} x(t) e^{-j\Omega t} dt \)

Sampling periodic T

\( x[n] = x(nT) \)

DTFT

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

Let \( \omega_k = \frac{2\pi}{N} k \)

DFT

\( \tilde{X}[k] = \sum_{n=0}^{N-1} \tilde{x}[n] e^{-j \frac{2\pi}{N} kn} \)
\( \tilde{x}[n] = \frac{1}{N} \sum_{k=0}^{N-1} \tilde{X}[k] e^{j \frac{2\pi}{N} kn} \)


\(\left\{\begin{array}{l}\tilde X\lbrack k\rbrack=\sum_{n=0}^{N-1}\tilde x\lbrack n\rbrack e^{-j\frac{2\pi}Nkn}\\\tilde x\lbrack n\rbrack=\frac1N\sum_{k=0}^{N-1}\tilde X\lbrack k\rbrack e^{j\frac{2\pi}Nkn}\end{array}\right.\xrightarrow[\left\{\begin{array}{l}x\lbrack n\rbrack=\tilde x\lbrack n\rbrack,\quad0\leq n\leq N-1\\X\lbrack k\rbrack=\tilde X\lbrack k\rbrack,\quad0\leq k\leq N-1\end{array}\right.]{Taking\;one\;periodic}\left\{\begin{array}{l}X\lbrack k\rbrack=\sum_{n=0}^{N-1}x\lbrack n\rbrack e^{-j\frac{2\pi}Nkn},\quad0\leq k\leq N-1\\x\lbrack n\rbrack=\frac1N\sum_{k=0}^{N-1}X\lbrack k\rbrack e^{j\frac{2\pi}Nkn},\quad0\leq n\leq N-1\end{array}\right.\)


\(\left\{\begin{array}{l}x(t)=\frac1{2\pi}\int_{-\infty}^\infty X(j\Omega)e^{j\Omega t}d\Omega\\X(j\Omega)=\int_{-\infty}^\infty x(t)e^{-j\Omega t}dt\end{array}\right.\xleftarrow[{0\leq t\leq T_0}]{x(t)=\tilde x(t)}\left\{\begin{array}{l}\tilde x(t)=\sum_{k=-\infty}^\infty{\tilde X}_ke^{jk\Omega_0t}\\{\tilde X}_k=\frac1{T_0}\int_{T_0}\tilde x(t)e^{-jk\Omega_0t}dt\end{array}\right.\)






Signal Processing: Analog to Discrete Transforms

Aperiodic Analog (CTFT)
\( x(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} X(j\Omega) e^{j\Omega t} d\Omega \)
\( X(j\Omega) = \int_{-\infty}^{\infty} x(t) e^{-j\Omega t} dt \)

Periodic Analog (Fourier Series)
\( \tilde{x}(t) = \sum_{k=-\infty}^{\infty} \tilde{X}_k e^{jk\Omega_0 t} \)
\( \tilde{X}_k = \frac{1}{T_0} \int_{T_0} \tilde{x}(t) e^{-jk\Omega_0 t} dt \)

Relationship: \( x(t) = \tilde{x}(t) \) for \( 0 \le t \le T_0 \)


↓ Sampling at period T ↓


N-pt DFT
\( x[n] = x(nT) \)
\( X[k] = \sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi}{N} kn}, \quad 0 \le k \le N-1 \)
\( x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2\pi}{N} kn}, \quad 0 \le n \le N-1 \)

N-pt DFS
\( \tilde{x}[n] = \tilde{x}(nT) \)
\( \tilde{X}[k] = \sum_{n=0}^{N-1} \tilde{x}[n] e^{-j\frac{2\pi}{N} kn} \)
\( \tilde{x}[n] = \frac{1}{N} \sum_{k=0}^{N-1} \tilde{X}[k] e^{j\frac{2\pi}{N} kn} \)


Taking one period \(\leftarrow\)
Note: \( X\lbrack k\rbrack=\widetilde X\lbrack k\rbrack,\;0\leq k\leq N-1 \) and \( x\lbrack n\rbrack=\widetilde x\lbrack n\rbrack,\;0\leq n\leq N-1 \) for one period.


DTFT (Aperiodic Discrete)
\( x[n] = x(nT) \)
\( X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n} \)
\( x[n] = \frac{1}{2\pi} \int_{-\pi}^{\pi} X(e^{j\omega}) e^{j\omega n} d\omega \)

↓ Finite Duration / Frequency Sampling ↓

sampling in frequency
\(\omega_k=\frac{2\pi}Nk\downarrow\)
\( \tilde{X}[k] = \sum_{n=0}^{N-1} \tilde{x}[n] e^{-j\frac{2\pi}{N} kn} \)
\( \tilde{x}[n] = \frac{1}{N} \sum_{k=0}^{N-1} \tilde{X}[k] e^{j\frac{2\pi}{N} kn} \)











Shift Discrete Fourier Series

\( x[n] = \tilde{x}[n], \quad 0 \le n \le N-1 \)
\( \tilde{x}[n] = \sum_{r=-\infty}^{\infty} x[n+rN] = x[((n))_N] \)


\(periodic:\;\widetilde x(t),\;aperiodic:\;x(t),\;\widetilde x(t)=\sum_{r=-\infty}^\infty x(t+rT)\)


\(periodic:\;\widetilde x\lbrack n\rbrack,\;aperiodic:\;x\lbrack n\rbrack,\;\widetilde x\lbrack n\rbrack=x\lbrack({(n))}_N\rbrack=\sum_{r=-\infty}^\infty x\lbrack n+rN\rbrack\)



\(\begin{aligned} x &= \tilde{x}, \quad 0 \leq n \leq N-1 \\ \\ \tilde{x} &= \sum_{r=-\infty}^{\infty} x[n+rN] = x[((n))_N] \\ &= x + x[n+N] + x[n-N] \\ &\quad + x[n+2N] + x[n-2N] \\ &\quad + \dots \end{aligned}\)


Shift

\( x[n] \xrightarrow{\text{DTFT}} X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n]e^{-j\omega n} \)
\( x[n-M] \xrightarrow{\text{DTFT}} X(e^{j\omega}) \cdot e^{-j\omega M} \)
\( \tilde{x}[n] \xrightarrow{\text{DFS}} \tilde{X}[k] = \sum_{n=0}^{N-1} \tilde{x}[n]e^{-j\frac{2\pi}{N}kn} \)
\( \tilde{x}[n-M] \xrightarrow{\text{DFS}} \tilde{X}[k] \cdot e^{-j\frac{2\pi}{N}k \color{red}{M}} \)
\( x[n] \xrightarrow{\text{DFT}} X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} kn} \)
\( \xcancel{x[n-M]} \xrightarrow{\text{DFT}} X[k] \cdot e^{-j \frac{2\pi}{N} kM} \)

DFS Shift Property Derivation

Step 1: Define the DFS of the shifted sequence
\( DFS\left( \tilde{x}[n-M] \right) \)
Step 2: Apply the DFS formula and define substitution
\( = \sum_{n=0}^{N-1} \tilde{x}[n-M] e^{-j \frac{2\pi}{N} kn} \quad \text{Let } m = n - M \)
Step 3: Substitute 'm' and update summation limits (in red)
\( = \sum_{m=\color{red}{-M}}^{\color{red}{N-M-1}} \tilde{x}[m] e^{-j \frac{2\pi}{N} k(m+M)} \)
Step 4: Factor out the constant phase shift
\( = e^{-j \frac{2\pi}{N} kM} \left( \sum_{m=-M}^{N-M-1} \tilde{x}[m] e^{-j \frac{2\pi}{N} km} \right) \quad \because \tilde{x} = \tilde{x}[n+N] \)
Step 5: Split the summation into two parts
\( = e^{-j \frac{2\pi}{N} kM} \left( \sum_{m=-M}^{-1} \tilde{x}[m] e^{-j \frac{2\pi}{N} km} + \sum_{m=0}^{N-M-1} \tilde{x}[m] e^{-j \frac{2\pi}{N} km} \right)\)
Step 6: Apply periodicity property (\(\tilde{x}[m]\) is periodic)
\( = e^{-j \frac{2\pi}{N} kM} \cdot \left( \sum_{m=-M}^{-1} \tilde{x}[m + \color{red}{N}] e^{-j \frac{2\pi}{N} km} + \sum_{m=0}^{N-M-1} \tilde{x}[m] e^{-j \frac{2\pi}{N} km} \right)\)
\(=e^{-j\frac{2\pi}NkM}\cdot\left(\sum_{m=N-M}^{N-1}\widetilde x\lbrack m{\color[rgb]{1.0, 0.0, 0.0}{\rbrack e^{-j\frac{2\pi}Nkm}+\sum_{m=0}^{N-M-1}\widetilde x\lbrack m\rbrack e^{-j\frac{2\pi}Nkm}}}\right)\)
\(=e^{-j\frac{2\pi}NkM}(\sum_{m=0}^{N-1}\widetilde x\lbrack m\rbrack e^{-j\frac{2\pi}Nkm})\)
\(=\tilde{X}[k] \cdot e^{-j\frac{2\pi}{N}k \color{red}{M}}\)


\( \xcancel{x[n-M]} \xrightarrow{\text{DFT}} X[k] \cdot e^{-j \frac{2\pi}{N} kM} \)

\( \quad \quad n = \quad \begin{matrix} 0 & 1 & 2 & 3 \end{matrix} \)
\( x[n] \quad \quad \quad \begin{array}{|c|c|c|c|} \hline 1 & 2 & 4 & 3 \\ \hline \end{array} \)
\( x[n-2] \quad \begin{array}{|c|c|c|c|} \hline 0 & 0 & 1 & 2 \\ \hline \end{array} \)
\( x[n-4] \quad \begin{array}{|c|c|c|c|} \hline 0 & 0 & 0 & 0 \\ \hline \end{array} \)

Circular Shift

\( \color{red}{x[((n-M))_N], \ 0 \leq n \leq N-1} \xrightarrow{\text{DFT}} X[k] \cdot e^{-j \frac{2\pi}{N} kM} \)






DFT Matrix Calculation: \( x = [1, 2, 3, 4] \)

\( \begin{bmatrix} X(0) \\ X(1) \\ X(2) \\ X(3) \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 10 \\ -2+2j \\ -2 \\ -2-2j \end{bmatrix} \)

Circular Shift: \( x_1 = [3, 4, 1, 2] \) (Shifted by 2)

\( \begin{bmatrix} X_1(0) \\ X_1(1) \\ X_1(2) \\ X_1(3) \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \begin{bmatrix} 3 \\ 4 \\ 1 \\ 2 \end{bmatrix} = \begin{bmatrix} 10 \\ 2-2j \\ -2 \\ 2+2j \end{bmatrix} \)

\( X_1(k)=X(k)\cdot e^{-j\frac{2\pi}42k}=X(k)\cdot e^{-j\pi k} \)

\(\begin{bmatrix}10\\2-2j\\-2\\2+2j\end{bmatrix}=\begin{bmatrix}10\cdot(1)\\(-2+2j)\cdot(-1)\\(-2)\cdot(1)\\(-2-2j)\cdot(-1)\end{bmatrix}\)


[Ex] \( x_2(n) = x[((n-1))_4] \)
\( 0 \le n \le 3 \)
\( -j \frac{2\pi}{4} \cdot 1k \)
\( X_2(k) = X(k) \cdot e^{-j \frac{2\pi}{4} \cdot 1k} \)

\(\begin{bmatrix}10\cdot(1)\\(-2+2j)\cdot(-j)\\(-2)\cdot(-1)\\(-2-2j)\cdot(j)\end{bmatrix}=\begin{bmatrix}10\\2+2j\\2\\2-2j\end{bmatrix}\)

Spectrum Leakage

Spectrum Leakage caused by Windowing

This diagram illustrates how spectral leakage occurs in signal processing when a continuous signal is observed through a finite window, comparing rectangular windowing and its effect on the Discrete Fourier Transform (DFT). It highlights how energy smears into side lobes (leakage) in the frequency domain, with red traces showing significant leakage for non-integer cycles, while blue traces demonstrate the "hidden" leakage of integer cycles.



Windowing a sinusoid causes spectral leakage, even if the sinusoid has an integer number of cycles within a rectangular window. The leakage is evident in the 2nd row, blue trace. It is the same amount as the red trace, which represents a slightly higher frequency that does not have an integer number of cycles. When the sinusoid is sampled and windowed, its discrete-time Fourier transform also exhibits the same leakage pattern (rows 3 and 4). But when the DTFT is only sparsely sampled, at a certain interval, it is possible (depending on your point of view) to: (1) avoid the leakage, or (2) create the illusion of no leakage. For the case of the blue sinusoid DTFT (3rd row of plots, right-hand side), those samples are the outputs of the discrete Fourier transform (DFT). The red sinusoid DTFT (4th row) has the same interval of zero-crossings, but the DFT samples fall in-between them, and the leakage is revealed.




DTFT DFT DFS

Time Shifting
DTFT

\(linear\;shift\;\left\{\begin{array}{l}x\lbrack n\rbrack\xrightarrow{DTFT}X(e^{j\omega})\\x\lbrack n-M\rbrack\xrightarrow{DTFT}X(e^{j\omega})\cdot e^{-j\omega M}\end{array}\right.\)

DFS

\(linear\;shift\;\left\{\begin{array}{l}\tilde x\lbrack n\rbrack\xrightarrow{DFS}\tilde X\lbrack k\rbrack=\sum_{n=0}^{N-1}\tilde x\lbrack n\rbrack e^{-j\frac{2\pi}Nkn}\\\tilde x\lbrack n-M\rbrack\xrightarrow{DFS}\tilde X\lbrack k\rbrack e^{-j\frac{2\pi}NkM}\end{array}\right.\)

DFT

\(circular\;shift\;\left\{\begin{array}{l}x\lbrack n\rbrack\xrightarrow[{N-pt}]{DFT}X\lbrack k\rbrack=\sum_{n=0}^{N-1}x\lbrack n\rbrack e^{-j\frac{2\pi}Nkn}\\\underset{0\leq n\leq N-1}{x\lbrack((n-M))_N\rbrack}\xrightarrow{DFT}X\lbrack k\rbrack e^{-j\frac{2\pi}NkM}\end{array}\right.\)


Let \( X_1[k] = X[k] e^{-j \frac{2\pi}{N} kM} \)
Let \( \tilde{X}_1[k] = X_1[((k))_N] = X[((k))_N] \cdot e^{-j \frac{2\pi}{N} ((k))_N M} = \tilde{X}[k] e^{-j \frac{2\pi}{N} kM}\)

\(\sum_{r=-\infty}^\infty e^{-j\frac{2\pi}N(k+rN)M}=\sum_{r=-\infty}^\infty e^{-j\frac{2\pi}NkM}\)
By IDFS     \( \tilde{x}_1[n] = \tilde{x}[n - M] \)


Then \( X_1[k] = \tilde{X}_1[k], \quad 0 \leq k \leq N-1 \)
\( \therefore x_1[n] = \tilde{x}_1[n], \quad 0 \leq n \leq N-1 \)
\( = \tilde{x}[n-M], \quad 0 \leq n \leq N-1 \)
\( = x[((n-M))_N], \quad 0 \leq n \leq N-1 \)

Convolution

\( x_1[n] \xrightarrow{DTFT} X_1(e^{j\omega}) \)
\( x_2[n] \xrightarrow{DTFT} X_2(e^{j\omega}) \)
Then, ↓ linear convolution
\( x_1[n] * x_2[n] \xrightarrow{DTFT} X_1(e^{j\omega}) X_2(e^{j\omega}) \)
\( = \sum_{k=-\infty}^{\infty} x_1[k] x_2[n-k] \)
\( = \sum_{k=-\infty}^{\infty} x_1[n-k] x_2[k] \)

\( \tilde{x}_1[n] \xrightarrow{DFS} \tilde{X}_1[k] \)
\( \tilde{x}_2[n] \xrightarrow{DFS} \tilde{X}_2[k] \)
Then, ↓ periodic convolution
\( \tilde{x}_1[n] \circledast \tilde{x}_2[n] \xrightarrow{DFS} \tilde{X}_1[k] \cdot \tilde{X}_2[k] \)

\( = \sum_{k=-\infty}^{\infty} \tilde{x}_1[k] \tilde{x}_2[n-k] \)
\( = \sum_{k=-\infty}^{\infty} \tilde{x}_1[n-k] \tilde{x}_2[k] \)

\( x_1[n] \xrightarrow{DFT} X_1[k] \)
\( x_2[n] \xrightarrow{DFT} X_2[k] \)
Then, ↙ circular convolution
\( x_1[n] \text{Ⓝ} x_2[n] \xrightarrow{DFT} X_1[k] \cdot X_2[k] \)
\( \parallel \)
\( \sum_{k=-\infty}^{\infty} x_1[k] x_2[((n-k))_N] \)


[Ex]


\( x_1[n] \), \( x_2[n] \)



\( x_3[n] = x_1[n] \text{ ⓹ } x_2[n] = \sum_{k=-\infty}^{\infty} x_1[((n-k))_5] \cdot x_2[n] \)

\( x_3[-2] = \sum_{k=-\infty}^{\infty} x_1[((-2-k))_5] \cdot x_2[n] = \sum_{k=-\infty}^{\infty} x_1[((3-k))_5] \cdot x_2[n] = 3 \cdot 1 = 3 \)
\( x_3[-1] = \sum_{k=-\infty}^{\infty} x_1[((-1-k))_5] \cdot x_2[n] = \sum_{k=-\infty}^{\infty} x_1[((4-k))_5] \cdot x_2[n] = 2 \cdot 1 = 2 \)
\( x_3[0] = \sum_{k=-\infty}^{\infty} x_1[((0-k))_5] \cdot x_2[n] = 1 \cdot 1 = 1 \)
\( x_3[1] = \sum_{k=-\infty}^{\infty} x_1[((1-k))_5] \cdot x_2[n] = 5 \cdot 1 = 5 \)
\( x_3[2] = \sum_{k=-\infty}^{\infty} x_1[((2-k))_5] \cdot x_2[n] = 4 \cdot 1 = 4 \)
\( x_3[3] = \sum_{k=-\infty}^{\infty} x_1[((3-k))_5] \cdot x_2[n] = 3 \cdot 1 = 3 \)
\( x_3[4] = \sum_{k=-\infty}^{\infty} x_1[((4-k))_5] \cdot x_2[n] = 2 \cdot 1 = 2 \)

\( \begin{array}{|c|c|c|c|c|} \hline 0 & 1 & 2 & 3 & 4 \\ \hline \end{array} \)

\( \begin{array}{c|ccccccccccccc} & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & \dots \\ \hline 5 & 0 & 5 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0 & 0 & 5 & 0 & \dots \\ 4 & 0 & 4 & 0 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 0 & 4 & 0 & \dots \\ 3 & 0 & 3 & 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 & 0 & 3 & 0 & \dots \\ 2 & 0 & 2 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 2 & 0 & \dots \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & \dots \\ \end{array} \)

\(\begin{array}{r|ccccccccccccccc}x_1\lbrack((n))_5\rbrack\rightarrow&0&1&0&0&0&0&1&0&0&0&0&1&0&0&\dots\\\hline5&0&5&0&0&0&0&5&0&0&0&0&5&0&0&\\4&0&4&0&0&0&0&4&0&0&0&0&4&0&0&\\x_2(n)\;\;3&0&3&0&0&0&0&3&0&0&0&0&3&0&0&\\2&0&2&0&0&0&0&2&0&0&0&0&2&0&0&\\1&0&1&0&0&0&0&1&0&0&0&0&1&0&0&\\\hline&&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&&&&&&&&\\&&1&5&4&3&2&1&&&&&&&&\end{array}\)

\( \begin{array}{c|cccccccccccccc} & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & \dots \\ \hline 5 & 5 & 0 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0 & 0 \\ 4 & 4 & 0 & 0 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 0 \\ x_2(n) \ \ 3 & 3 & 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 & 0 \\ 2 & 2 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ \hline & {\;} & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow \\ & {\;} & 0 & 5 & 4 & 3 & 2 & 1 \end{array} \)
6-pt

\( \begin{array}{c|cc} & 0 & 1 \\ \hline 5 & 0 & 5 \\ 4 & 0 & 4 \\ 3 & 0 & 3 \\ 2 & 0 & 2 \\ 1 & 0 & 1 \\ \hline & \swarrow & \swarrow \swarrow \swarrow & \downarrow \\ & 5 & 4 \ 3 \ 2 & 1 \end{array} \)

\(\delta\lbrack n-1\rbrack\qquad5\delta\lbrack n\rbrack+4\delta\lbrack n-1\rbrack+3\delta\lbrack n-2\rbrack+2\delta\lbrack n-3\rbrack+\delta\lbrack n-4\rbrack\)

\( N \geq L + P - 1 \)

Discrete time Fourier Transform DTFT

Circular Convolution

Fast Fourier Transform FFT

Circular Convolution

\( x_1\lbrack n\rbrackⓃx_2\lbrack n\rbrack=\sum_{k=0}^{N-1}x_1\lbrack k\rbrack x_2\lbrack((n-k))_N\rbrack \)
\( x[((n))_N] = \sum_{r=-\infty}^{\infty} x[n+rN] \)


\( \boldsymbol a = \begin{bmatrix} 3 \\ 1 \\ 2 \\ 1 \end{bmatrix} \), \( \boldsymbol b = \begin{bmatrix} 5 \\ 4 \\ 3 \\ 4 \end{bmatrix} \)

\( \boldsymbol c=\boldsymbol a④\boldsymbol b=\begin{bmatrix}29\\28\\27\\28\end{bmatrix} \)



\( \begin{array}{cc|cccccccccc} & b & 5 & 4 & 3 & 4 & \overset{\downarrow}{5} & 4 & 3 & 4 & 5 & 4 & \cdots \\ \hline & 3 & 15 & 12 & 9 & 12 & 15 & 12 & 9 & 12 & 15 & 12 & \\ a & 1 & 5 & 4 & 3 & 4 & 5 & 4 & 3 & 4 & 5 & 4 & \\ & 2 & 10 & 8 & 6 & 8 & 10 & 8 & 6 & 8 & 10 & 8 & \\ & 1 & 5 & 4 & 3 & 4 & 5 & 4 & 3 & 4 & 5 & 4 & \\ \hline & & & \underset{\uparrow}{29} & \underset{\uparrow}{28} & \underset{\uparrow}{27} & \underset{\uparrow}{28} & & & & & & \end{array} \)

DFT
\( X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} kn} \)

\( A = \begin{bmatrix} A[0] \\ A[1] \\ A[2] \\ A[3] \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \begin{bmatrix} 3 \\ 1 \\ 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 7 \\ 1 \\ 3 \\ 1 \end{bmatrix} \)

\( B = \begin{bmatrix} B[0] \\ B[1] \\ B[2] \\ B[3] \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \begin{bmatrix} 5 \\ 4 \\ 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 16 \\ 2 \\ 0 \\ 2 \end{bmatrix} \)


\( \begin{array}{ccc} % Top Row: Time Domain Vector definitions & Circular Convolution a = \begin{bmatrix} 3 \\ 1 \\ 2 \\ 1 \end{bmatrix} & b = \begin{bmatrix} 5 \\ 4 \\ 3 \\ 4 \end{bmatrix} & c = a ④ b = \begin{bmatrix} 29 \\ 28 \\ 27 \\ 28 \end{bmatrix} \\ % Middle Row: Vertical 4-pt DFT arrows \begin{array}{c} \color{#ff9999}{\downarrow \text{DFT}} \\ \color{#ff9999}{\text{4-pt}} \end{array} & \begin{array}{c} \color{#ff9999}{\downarrow \text{DFT}} \\ \color{#ff9999}{\text{4-pt}} \end{array} & \begin{array}{c} \color{#0000FF}{\downarrow \text{DFT}} \\ \color{#0000FF}{\text{4-pt}} \end{array} & \\ % Bottom Row: Frequency Domain DFT Vectors and Element-wise Product {A = \begin{bmatrix} 7 \\ 1 \\ 3 \\ 1 \end{bmatrix}} & {B = \begin{bmatrix} 16 \\ 2 \\ 0 \\ 2 \end{bmatrix}} & \operatorname{𝑄}=\operatorname{𝐴}\underbrace⋅_{\uparrow dot}\operatorname{𝐵}=\;\begin{bmatrix}112\\2\\0\\2\end{bmatrix} \\ \end{array} \)


\( Q = \begin{bmatrix} Q[0] \\ Q[1] \\ Q[2] \\ Q[3] \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \begin{bmatrix} 29 \\ 28 \\ 27 \\ 28 \end{bmatrix} = \begin{bmatrix} 112 \\ 2 \\ 0 \\ 2 \end{bmatrix} \)


Circular Convolution

\( x_1[n] Ⓝ x_2[n] = \sum_{k=0}^{N-1} x_1[k] x_2[((n-k))_N] \)
\( x_1(n) \xrightarrow{\text{N-pt DFT}} X_1[k] \)
\( x_2(n) \xrightarrow{\text{N-pt DFT}} X_2[k] \)
\( x_1(n) Ⓝ x_2(n) \xrightarrow{\text{N-pt DFT}} X_1[k] \cdot X_2[k] \)

\( \begin{array}{ccc} % Top Row: Vector Definitions a = \begin{bmatrix} 3 \\ 1 \\ 2 \\ 1 \end{bmatrix} & b = \begin{bmatrix} 5 \\ 4 \\ 3 \\ 4 \\ 5 \\ 4 \\ 3 \\ 4 \end{bmatrix} & c = a \bigcirc b \\ % Middle Row: Vertical DFT arrows \begin{array}{c} \downarrow \\ \text{DFT} \\ \downarrow \end{array} & \begin{array}{c} \downarrow \\ \text{DFT} \\ \downarrow \end{array} & \\ % Bottom Row: Frequency Domain Mappings A & B & Q = A \cdot B \end{array} \)


\( \begin{array}{ccc} % Top Row: Time Domain Vectors & Circular Convolution a = \begin{bmatrix} 3 \\ 1 \\ 2 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} & b = \begin{bmatrix} 5 \\ 4 \\ 3 \\ 4 \\ 5 \\ 4 \\ 3 \\ 4 \end{bmatrix} & c = a ⑧ b = \left[ \begin{array}{c} \ \\ \ \\ \ \\ \ \\ \ \\ \ \\ \ \\ \ \end{array} \right]_{8 \times 1} \\ % Middle Row: Vertical 8-pt DFT arrows \begin{array}{c} \downarrow \\ \text{8-pt} \\ \text{DFT} \\ \downarrow \end{array} & \begin{array}{c} \downarrow \\ \text{8-pt} \\ \text{DFT} \\ \downarrow \end{array} & \begin{array}{c} \uparrow \\ \text{8-pt} \\ \text{DFT} \\ \mid \end{array} \\ % Bottom Row: Frequency Domain Mappings A = \left[ \begin{array}{c} \ \\ \ \\ \ \\ \ \\ \ \\ \ \\ \ \\ \ \end{array} \right]_{8 \times 1} & B = \left[ \begin{array}{c} \ \\ \ \\ \ \\ \ \\ \ \\ \ \\ \ \\ \ \end{array} \right]_{8 \times 1} & Q = A \cdot B = \left[ \begin{array}{c} \ \\ \ \\ \ \\ \ \\ \ \\ \ \\ \ \\ \ \end{array} \right]_{8 \times 1} \end{array} \)


DTFT

\( x(n) = \begin{cases} 1, & 0 \le n \le N-1 \\ 0, & \text{otherwise} \end{cases} \)
\( X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x(n) e^{-j\omega n} \)
\( \phantom{X(e^{j\omega})} = \sum_{n=0}^{N-1} 1 \cdot e^{-j\omega n} \)
\( \phantom{X(e^{j\omega})} = \frac{1 - e^{-j\omega N}}{1 - e^{-j\omega}} \)
\(=0\)

\( \overbrace{1 + r + r^2 + \cdots + r^{N-1}}^{N} = \frac{1 - r^N}{1 - r} \)



\( \begin{align*} X[k] &= \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} kn} \\ &= \sum_{n=0}^{N-1} 1 \cdot e^{-j \frac{2\pi}{N} kn} \\ &= \begin{cases} \dfrac{1 - {\underbrace{e^{-j \frac{2\pi}{N} kN}}_{=1}}}{1 - e^{-j \frac{2\pi}{N} k}} = 0, & k \neq 0 \\ \\ N, & k = 0 \end{cases} \end{align*} \)




M-pt DFT, \( M > N \)


DTFT

M-pt DFT, \( M > N \)
\( \begin{align*} X[k] &= \sum_{n=0}^{{M-1}} x[n] e^{-j \frac{2\pi}{M} kn} \\ &= \sum_{n=0}^{N-1} 1 \cdot e^{-j \frac{2\pi}{M} kn} \\ &= \begin{cases} \dfrac{1 - e^{-j \frac{2\pi}{M} kN}}{1 - e^{-j \frac{2\pi}{M} k}}, & k \neq 0 \\ \\ N, & k = 0 \end{cases} \end{align*} \)




\( \begin{array}{c} 2^v \\ 16 \\ 32 \\ 64 \\ 128 \\ 256 \\ 512 \\ 1024 \\ 2048 \\ 4096 \\ \vdots \end{array} \)




Fast Fourier Transform (FFT)

DFT
\( X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} kn} \)
\( \begin{bmatrix} X(0) \\ X(1) \\ X(2) \\ X(3) \end{bmatrix} = \left[ \begin{array}{cccc} \ & \ & \ & \ \\ \ & \ & \ & \ \\ \ & \ & \ & \ \\ \ & \ & \ & \ \end{array} \right]_{4 \times 4} \cdot \begin{bmatrix} x(0) \\ x(1) \\ x(2) \\ x(3) \end{bmatrix} \)

\( 4 \times 4 = 4^2 \quad \text{`x'} \)
\( N^2 \)

\( \begin{align*} \text{DFT } \quad X[k] &= \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} kn} \\ &= \sum_{n \in \text{even}} x[n] e^{-j \frac{2\pi}{N} kn} + \sum_{n \in \text{odd}} x[n] e^{-j \frac{2\pi}{N} kn} \\ \\ \text{Let } n = 2r \quad \implies &= \color{#ff9999}{\boxed{ {\sum_{r=0}^{N/2-1} x[2r] \left( e^{-j \frac{2\pi}{N} k(2r)} \right) } }} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \downarrow \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ e^{-j \frac{2\pi}{N/2} kr} \end{align*} \)

\( \text{N-pt DFT} \longrightarrow O(N^2) \)
\( \frac{N}{2}\text{-pt } , \frac{N}{2}\text{-pt} \longrightarrow O\left((\frac{N}{2})^2 \cdot 2\right) = O\left(\frac{N^2}{2}\right) \)
\( (\frac{N}{4})^2 \cdot 4 = (\frac{N^2}{4}) \)


Cooley-Tukey algorithm

In its simplest incarnation this algorithm re-expresses the DFT of size \( N = 2M \) in terms of two DFTs of size \( M \),

\( \begin{align*} c_k &= \sum_{n=0}^{N-1} x_n e^{-2\pi i \frac{nk}{N}} \\ &= \sum_{m=0}^{M-1} x_{2m} e^{-2\pi i \frac{mk}{M}} + e^{-2\pi i \frac{k}{N}} \sum_{m=0}^{M-1} x_{2m+1} e^{-2\pi i \frac{mk}{M}} \\ &= \begin{cases} c_k^{(\text{even})} + e^{-2\pi i \frac{k}{N}} c_k^{(\text{odd})} &, k < M \\ c_{k-M}^{(\text{even})} - e^{-2\pi i \frac{k-M}{N}} c_{k-M}^{(\text{odd})} &, k \ge M \end{cases} \end{align*} \)

where \( c^{(\text{even})} \) and \( c^{(\text{odd})} \) are the DFTs of the even- and odd-numbered sub-sets of \( x \).

This re-expression of a size-\( N \) DFT as two size-\( \frac{N}{2} \) DFTs is sometimes called the Danielson-Lanczos lemma. The exponents \( e^{-2\pi i \frac{k}{N}} \) are called twiddle factors.

The operation count by application of the lemma is reduced from the original \( N^2 \) down to \( 2(N/2)^2 + N/2 = N^2/2 + N/2 < N^2 \).

For \( N = 2^p \) Danielson-Lanczos lemma can be applied recursively until the data sets are reduced to one datum each. The number of operations is then reduced to \( O(N \ln N) \) compared to the original \( O(N^2) \). The established library FFT routines, like FFTW and GSL, further reduce the operation count (by a constant factor) using advanced programming techniques like precomputing the twiddle factors, effective memory management and others.


In digital signal processing (DSP), IIR (Infinite Impulse Response) and FIR (Finite Impulse Response) are the two primary types of digital filters used to filter out unwanted signals and shape frequency spectra.



Here is how they compare at a glance:

Feature FIR (\(\text{Finite Impulse Response}\)) IIR (\(\text{Infinite Impulse Response}\))
Feedback None (feed-forward only) Yes (uses output values as inputs)
Impulse Response Zero after \(N\) samples (finite) Continues indefinitely (infinite)
Stability Always stable Can become unstable if not designed correctly
Phase Can achieve linear phase (no delay distortion) Non-linear phase (causes phase distortion)
Computational Cost Higher (requires more taps/coefficients) Lower (needs fewer coefficients for sharp cutoffs)

FIR Filter IIR Filter
FIR filter stands for finite impulse response filter. IIR filter stands for infinite impulse response filter.
A FIR filter provides impulse responses for a finite duration of time. An IIR filter gives impulse responses for an infinite duration of time.
Feedback system is not present in FIR filters. Feedback system is available in IIR filters.
The FIR filter is non-recursive in nature. The IIR filter is recursive.
FIR filters do not contain any poles. Hence the FIR filter is always stable and the stability is more than that of IIR filter. IIR filters are less stable than that of FIR filters due to the presence of poles.
The transfer function of FIR filter contains only zeros. The transfer function of IIR filter contains both poles and zeros.
Due to the absence of feedback path in the FIR filters, it needs more memory to keep the more number of coefficients even for a single function. The memory requirements of an IIR filter is less than that of FIR filter as it contains feedback path.
The computational efficiency of a FIR filter is less. The computational efficiency of an IIR filter is more than that of a FIR filter.
Differentiator, Hilbert transformer, etc. Butterworth filter, Chebyshev type I filter, Chebyshev type II filter, etc.
The uses of FIR Filters are found in audio system, control system, medical devices, etc. In biomedical sensor, telecommunication, audio equalization, the IIR filters are used.




System Structure

\( y[n] = 3y[n-1] - 2y[n-2] + 5x[n] + 7x[n-1] - 6x[n-2] \)



\( \Rightarrow Y(z) = 3Y(z)z^{-1} - 2Y(z)z^{-2} + 5X(z) + 7X(z)z^{-1} - 6X(z)z^{-2} \)
\( (1 - 3z^{-1} + 2z^{-2})Y(z) = (5 + 7z^{-1} - 6z^{-2})X(z) \)
\( \Rightarrow H(z) = \frac{Y(z)}{X(z)} = \frac{5 + 7z^{-1} - 6z^{-2}}{1 - 3z^{-1} + 2z^{-2}} \)



\( H(z) = \frac{8 - z^{-1} + 6z^{-2}}{1 + 4z^{-1} - 3z^{-2}} \)



\( H(z) = \frac{5 - 2z^{-1}}{1 - 3z^{-1} + 8z^{-2}} \)



\(y[n] = x[n] + 3x[n-1]\)
\(H(z) = 1 + 3z^{-1}\)



\( H(z) = \frac{\sum_{k=0}^{M} b_k z^{-k}}{1 + \sum_{k=1}^{N} a_k z^{-k}} = H_1(z)H_2(z) \)

\( H_1(z) = \sum_{k=0}^{M} b_k z^{-k} , \)
all - zero system

\( H_2(z) = \frac{1}{1 + \sum_{k=1}^{N} a_k z^{-k}} , \)
all - pole system




\( H(z) = \frac{4 + 5z^{-1} + z^{-2}}{1 + 2z^{-1} - 3z^{-2}} \)
\( = \frac{(4 + z^{-1})(1 + z^{-1})}{(1 + 3z^{-1})(1 - z^{-1})} \)



\( H(z) = \frac{4 + 5z^{-1} + z^{-2}}{1 + 2z^{-1} - 3z^{-2}} \)
\( = \frac{4 + z^{-1}}{1 + 3z^{-1}} \cdot \frac{1 + z^{-1}}{1 - z^{-1}} \)



\( \begin{array}{r} -\frac{1}{3} \\ \hline -3z^{-2} + 2z^{-1} + 1 \ \big) \ z^{-2} + 5z^{-1} + 4 \\ z^{-2} - \frac{2}{3}z^{-1} - \frac{1}{3} \\ \hline \frac{17}{3}z^{-1} + \frac{13}{3} \end{array} \)

\( H(z) = \frac{4 + 5z^{-1} + z^{-2}}{1 + 2z^{-1} - 3z^{-2}} \)
\( = \frac{4 + z^{-1}}{1 + 3z^{-1}} \cdot \frac{1 + z^{-1}}{1 - z^{-1}} \)
\( = -\frac{1}{3} + \frac{\frac{17}{3}z^{-1} + \frac{13}{3}}{1 + 2z^{-1} - 3z^{-2}} \)
\( = -\frac{1}{3} + \frac{A}{1 + 3z^{-1}} + \frac{B}{1 - z^{-1}} \)






loop and can NOT determinate the relations



Transpose Rules

\( \text{Transpose} \quad \begin{cases} \text{① reverse all the arrows} \\ \text{② interchange the input and output.} \end{cases} \)



[Ex]


System Structure

Causal



\[ \frac{5 + 6z^{-1} + z^{-2}}{1 + 2z^{-1} - 3z^{-2}} \]
\[\frac{1 + 4z^{-1} + 5z^{-2}}{1 + 2z^{-1} - 8z^{-2}} \]

\[\Rightarrow {\frac{5 + 6z^{-1} + z^{-2}}{1 + 2z^{-1} - 3z^{-2}}} + {\frac{1 + 4z^{-1} + 5z^{-2}}{1 + 2z^{-1} - 8z^{-2}}} \]

\( H(z) = \left( \frac{5 + 6z^{-1} + z^{-2}}{1 + 2z^{-1} - 3z^{-2}} + \frac{1 + 4z^{-1} + 5z^{-2}}{1 + 2z^{-1} - 8z^{-2}} \right) \cdot \left( 1 + 9z^{-1} + z^{-2} \right) \)

\( h(0) = \lim_{z \to \infty} H(z) = 6 \cdot 1 = 6 \)



\( y(n) = 9y(n-1) + y(n-2) + bx(n) \)
\( Y(z) = 9Y(z)z^{-1} + Y(z)z^{-2} + B(z) \)
\( \Rightarrow \frac{Y(z)}{B(z)} = \frac{1}{1 - 9z^{-1} - z^{-2}} \)

Moving terms to the left gives \( Y(z)(1 - 9z^{-1} - z^{-2}) = B(z) \), so the transfer function should actually be:
\( \Rightarrow \frac{Y(z)}{B(z)} = \frac{1}{1 - 9z^{-1} - z^{-2}} \)

time shifting and time folding

Precedence rules for time shifting and time folding
Order of shifting and folding operations Output signal
1. Folding → Shift to the right \(x[n] \xrightarrow{\text{FO}} x[-n] \xrightarrow{\text{SO}_R} x[-(n-p)] = x[-n+p]\)
2. Shift to the left → Folding \(x[n] \xrightarrow{\text{SO}_L} x[n+p] \xrightarrow{\text{FO}} x[-n+p]\)
3. Folding → Shift to the left \(x[n] \xrightarrow{\text{FO}} x[-n] \xrightarrow{\text{SO}_L} x[-(n+p)] = x[-n-p]\)
4. Shift to the right → Folding \(x[n] \xrightarrow{\text{SO}_R} x[n-p] \xrightarrow{\text{FO}} x[-n-p]\)

Transformation performed on amplitude
Operation D-T signals C-T signals Physical device
1. Amplitude scaling \( y[n] = cx[n] \) \( y(t) = cx(t) \) Electronic
amplifier
\( c \) - scaling factor
2. Addition \( y[n] = x_1[n] + x_2[n] \) \( y(t) = x_1(t) + x_2(t) \) Audio mixer
3. Multiplication \( y[n] = x_1[n] \cdot x_2[n] \) \( y(t) = x_1(t) \cdot x_2(t) \) Modulator
4. Differentiation Difference equation \( y(t) = d\frac{x(t)}{dt} \) Inductor
5. Integration Summation \( y(t) = \int_{-\infty}^{t} x(\tau) d\tau \) Capacitor

Sampling Theorem

Digital Versus Analog Filtering
Digital Filters Analog Filters
High Accuracy Less Accuracy - Component Tolerances
Linear Phase (\( \text{FIR} \) Filters) Non-Linear Phase
No Drift Due to Component Variations Drift Due to Component Variations
Flexible, Adaptive Filtering Possible Adaptive Filters Difficult
Easy to Simulate and Design Difficult to Simulate and Design
Computation Must be Completed in Sampling Period - Limits Real Time Operation Analog Filters Required at High Frequencies and for Anti-Aliasing Filters
Requires High Performance \( \text{ADC} \), \( \text{DAC} \) & \( \text{DSP} \) No \( \text{ADC} \), \( \text{DAC} \), or \( \text{DSP} \) Required




In DSP, \( x[n - 1] \) represents a one-sample time delay. It means the signal evaluated at the current "time" step n is actually the value that arrived one sampling period earlier. In a mathematical context, it shifts the entire signal sequence one position to the right along the time axis.

In a digital circuit or hardware architecture (like an FPGA or ASIC), this minus 1 operation is physically implemented using a memory element or a register (typically a D flip-flop).

  • In Software/Algorithms: It is just an index pointer or a location in a buffer, where the processor reads the sample stored during the previous clock cycle.
  • In Circuit Logic (Z-transform): It is represented as the operator \( z^{-1} \), where z denotes advancing and \( z^{-1} \) denotes a single-unit delay.
  • Physical Implementation: The circuit continuously loads the digital input into a register, and on the next clock tick (the next sample time n), that previously stored value is outputted while a new sample is brought in.

These delay elements are the fundamental building blocks used in hardware to create feedback loops and design digital filters (like FIR or IIR filters), allowing the system to use "past" data to process current signals.




\(\begin{array}{ccc}x_c(t)&\rightarrow Sampling\rightarrow&x\lbrack n\rbrack=x_c(nT)\\\downarrow FT&&\downarrow DTFT\\X_c(j\Omega)=\int_{-\infty}^\infty x_c(t)e^{-j\Omega t}dt&&X(e^{j\omega})=\sum_{n=-\infty}^\infty x\lbrack n\rbrack e^{-j\omega n}\end{array}\)



\( x(t) * h(t) \xrightarrow{\text{F.T.}} X(j\Omega) \cdot H(j\Omega) \)
\( x(t) \cdot h(t) \xrightarrow{\text{F.T.}} \frac{1}{2\pi} X(j\Omega) * H(j\Omega) \)

\( x_s(t) = x_c(t) \cdot s(t) = x_c(t) \cdot \sum_{n=-\infty}^{\infty} \delta(t - nT) \)
\( X_s(j\Omega) = \frac{1}{2\pi} X_c(j\Omega) * S(j\Omega) \text{ , where } S(j\Omega) = \mathcal{F}\{s(t)\} \)

\( \text{Since } s(t) = \sum_{n=-\infty}^{\infty} \delta(t - nT) \xrightarrow{\text{(F.S.)}} \sum_{k=-\infty}^{\infty} S_k e^{j k \Omega_s t} \text{ , where } \Omega_s = \frac{2\pi}{T} \text{ and } S_k = \frac{1}{T} \int_{-T/2}^{T/2} s(t) e^{-j k \Omega_s t} dt \)

\( S_k = \frac{1}{T} \int_{-T/2}^{T/2} s(t) e^{-j k \Omega_s t} dt \)
\( = \frac{1}{T} \int_{-T/2}^{T/2} \delta(t) \cdot e^{-j k \Omega_s t} dt \)
\( = \frac{1}{T} \)

\( S(j\Omega) = \mathcal{F}\{s(t)\} = \mathcal{F}\{\sum_{k=-\infty}^{\infty} S_k e^{j k \Omega_s t}\} \)
\( = \frac{1}{T} \mathcal{F}\{\sum_{k=-\infty}^{\infty} e^{j k \Omega_s t}\}\)


\( \delta(t) \xrightarrow{\text{F.T.}} 1 \)
\( \delta(t - t_0) \xrightarrow{\text{F.T.}} e^{-j \Omega t_0} \)
\( 1 \xrightarrow{\text{F.T.}} 2\pi \delta(\Omega) \)
\( e^{j \Omega_0 t} \xrightarrow{\text{F.T.}} 2\pi \delta(\Omega - \Omega_0) \)

\( S(j\Omega) = \mathcal{F}\{s(t)\} \)
\( = \mathcal{F}\left\{ \frac{1}{T} \sum_{k=-\infty}^{\infty} e^{j k \Omega_s t} \right\} \)
\( = \frac{1}{T} \sum_{k=-\infty}^{\infty} 2\pi \delta(\Omega - k \Omega_s) \)

\( X_s(j\Omega) = \frac{1}{2\pi} X_c(j\Omega) * S(j\Omega) \)
\( = \frac{1}{2\pi} X_c(j\Omega) * \frac{2\pi}{T} \sum_{k=-\infty}^{\infty} \delta(\Omega - k \Omega_s) \)
\( = \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c(j(\Omega - k \Omega_s)) \)

\( X_c(j\Omega) \longrightarrow X_s(j\Omega) \)

\( x_s(t) = x_c(t) \cdot s(t) = x_c(t) \cdot \sum_{n=-\infty}^{\infty} \delta(t - nT) \)
\( = \sum_{n=-\infty}^{\infty} x_c(nT) \cdot \delta(t - nT) = \sum_{n=-\infty}^{\infty} x[n] \delta(t - nT) \)

Then \( X_s(j\Omega) = \mathcal{F}\left\{ \sum_{n=-\infty}^{\infty} x[n] \delta(t - nT) \right\} = \sum_{n=-\infty}^{\infty} x[n] e^{-j\Omega nT} \)


\( X_s(j\Omega) = \sum_{n=-\infty}^{\infty} x(n) e^{-j\Omega nT} \)
\( \because X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x(n) e^{-j\omega n} \quad \text{(DTFT)} \)
\( \therefore X_s(j\Omega) = \left. X(e^{j\omega}) \right|_{\omega = \Omega T} \)

or \( X(e^{j\omega}) = \left. X_s(j\Omega) \right|_{\Omega = \frac{\omega}{T}} \)
\( = \left. \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c(j(\Omega - k\Omega_s)) \right|_{\Omega = \frac{\omega}{T}} \)
\( = \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c\left( j\left( \frac{\omega}{T} - k\Omega_s \right) \right) \)
\( = \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c\left( j\left( \frac{\omega}{T} - k\frac{2\pi}{T} \right) \right) \)
\( = \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c\left( j \frac{1}{T} (\omega - 2\pi k) \right) \)

\( X_c(j\Omega) = \int_{-\infty}^{\infty} x_c(t) e^{-j\Omega t} dt \qquad X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n} \)
\( X(e^{j\omega}) = \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c\left( j \frac{1}{T} (\omega - 2\pi k) \right) \)


\( X(e^{j\omega}) = X_s\left( j\frac{\omega}{T_s} \right) \)

This formula relates the Discrete-Time Fourier Transform (DTFT), \( X(e^{j\omega}) \), of a sampled signal to the Continuous-Time Fourier Transform (CTFT), \( X_s(j\Omega) \), of the sampled signal.

  • \( X(e^{j\omega}) \): Represents the DTFT of the discrete signal \( x[n] \).
  • \( X_s\left( j\frac{\omega}{T_s} \right) \): Represents the CTFT of the sampled signal, scaled by the sampling period \( T_s \).
DTFT and CTFT Relationship

This formula represents the frequency-scaling relationship between the Discrete-Time Fourier Transform (DTFT) and the Continuous-Time Fourier Transform (CTFT) during the sampling process.

It maps the continuous physical frequency (\(\Omega\)) to the normalized discrete digital frequency (\(\omega\)).

Key Components Broken Down
  • \(X(e^{j\omega})\): The DTFT of the discrete sequence \(x[n]\). Its frequency variable \(\omega\) is periodic with a period of \(2\pi\) radians.
  • \(X_s(j\Omega)\): The CTFT of the ideally sampled continuous signal \(x_s(t)\).
  • \(\omega = \Omega T_s\): The fundamental relationship mapping continuous frequency \(\Omega\) (in rad/s) to discrete frequency \(\omega\) (in rad/sample) based on the sampling period \(T_s\).
What This Formula Tells You
  • Frequency Scaling: Sampling stretches or compresses the frequency axis. The continuous frequency at the sampling frequency \(\Omega_s = \frac{2\pi}{T_s}\) maps directly to the discrete frequency \(\omega = 2\pi\).
  • Periodic Repetition: Because the DTFT \(X(e^{j\omega})\) must be periodic every \(2\pi\), this mapping inherently reflects how the continuous spectrum repeats every \(\Omega_s\) due to impulse sampling.

IIR and FIR

In Digital Signal Processing (DSP), "IIR filter structures (I, II, III, IV, and V)" typically refer to the classical filter implementation topologies—most notably the fundamental Direct Forms and the Cascade/Parallel Forms.

In Digital Signal Processing (DSP), an FIR (Finite Impulse Response) filter can be implemented using several hardware and software architectures. The term "Direct Form" refers to the most fundamental implementation derived directly from a filter's difference equation.

IIR
Direct form I

\(H(z) = \frac{Y(z)}{X(z)} = \frac{b_0 + b_1 z^{-1} + b_2 z^{-2}}{1 + a_1 z^{-1} + a_2 z^{-2}}\)



Direct form II

\(H(z) = \frac{Y(z)}{X(z)} = \frac{b_0 + b_1 z^{-1} + b_2 z^{-2}}{1 + a_1 z^{-1} + a_2 z^{-2}}\)



the 3rd-order transfer function
\( H(z) = p_0 \left( \frac{1 + \beta_{11} z^{-1}}{1 + \alpha_{11} z^{-1}} \right) \left( \frac{1 + \beta_{12} z^{-1} + \beta_{22} z^{-2}}{1 + \alpha_{12} z^{-1} + \alpha_{22} z^{-2}} \right) \)



[Ex]
\( \begin{aligned} H(z) &= \frac{0.44z^{-1} + 0.362z^{-2} + 0.02z^{-3}}{1 + 0.4z^{-1} + 0.18z^{-2} - 0.2z^{-3}} \\[10pt] &= \left( \frac{0.44 + 0.362z^{-1} + 0.02z^{-2}}{1 + 0.8z^{-1} + 0.5z^{-2}} \right) \left( \frac{z^{-1}}{1 - 0.4z^{-1}} \right) \end{aligned} \)



[Ex]
\( \begin{aligned} H(z) &= \frac{0.44z^{-1} + 0.362z^{-2} + 0.02z^{-3}}{1 + 0.4z^{-1} + 0.18z^{-2} - 0.2z^{-3}} \\[12pt] H(z) &= -0.1 + \frac{0.6}{1 - 0.4z^{-1}} + \frac{-0.5 - 0.2z^{-1}}{1 + 0.8z^{-1} + 0.5z^{-2}} \end{aligned} \)



FIR

\( H(z) = \frac{Y(z)}{X(z)} = \sum_{k=0}^{4} h[k]z^{-k} = h[0] + h[1]z^{-1} + h[2]z^{-2} + h[3]z^{-3} + h[4]z^{-4} \)



The transpose of the direct form



\( H(z) = \frac{Y(z)}{X(z)} = b_0 + b_1 z^{-1} + b_2 z^{-2} + \dots + b_M z^{-M} \)



Cascade

  • A higher-order FIR transfer function can also be realized as a cascade of second-order FIR sections and possibly a first-order section
  • To this end we express \( H(z) \) as
    \( H(z) = h[0] \prod_{k=1}^{K} (1 + \beta_{1k}z^{-1} + \beta_{2k}z^{-2}) \)
    where \( K = \frac{N}{2} \) if \( N \) is even, and \( K = \frac{N+1}{2} \) if \( N \) is odd, with \( \beta_{2K} = 0 \)

\(H(z) = h[0] \left(1 + \beta_{11}z^{-1} + \beta_{21}z^{-2}\right) \left(1 + \beta_{12}z^{-1} + \beta_{22}z^{-2}\right) \left(1 + \beta_{13}z^{-1} + \beta_{23}z^{-2}\right)\)



[Ex] Linear Phase FIR Filter (Symmetric Coefficients)
\( H(z) = h[0](1 + z^{-6}) + h[1](z^{-1} + z^{-5}) \) \( \quad \quad + h[2](z^{-2} + z^{-4}) + h[3]z^{-3} \)




Cascade form: \( H(z) = \prod_{p=1}^{P} \frac{b_{p0} + b_{p1} z^{-1} + b_{p2} z^{-2}}{1 + a_{p1} z^{-1} + a_{p2} z^{-2}} \)
Parallel form: \( H(z) = A_0 + \sum_{p=1}^{P} \frac{c_{p0} + c_{p1} z^{-1}}{1 + a_{p1} z^{-1} + a_{p2} z^{-2}} \)

Undersampling



The top 2 graphs depict Fourier transforms of 2 different functions that produce the same results when sampled at a particular rate. The baseband function is sampled faster than its Nyquist rate, and the bandpass function is undersampled, effectively converting it to baseband. The lower graphs indicate how identical spectral results are created by the aliases of the sampling process.




Single-sideband modulation




Sampling Sampling Frequency Change

In signal processing, undersampling or bandpass sampling is a technique where one samples a bandpass-filtered signal at a sample rate below its Nyquist rate (twice the upper cutoff frequency), but is still able to reconstruct the signal.

When one undersamples a bandpass signal, the samples are indistinguishable from the samples of a low-frequency alias of the high-frequency signal. Such sampling is also known as bandpass sampling, harmonic sampling, IF sampling, and direct IF-to-digital conversion.


Sampling

\( x[n] = x_c(nT) \)
\( X(e^{j\omega}) = \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c\left( j \frac{1}{T} (\omega - 2\pi k) \right) \)



\( \Omega_N T = \pi \)
\( \Omega_N = \frac{\pi}{T} = \frac{\Omega_s}{2} \)
\( \Rightarrow \Omega_s = 2\Omega_N \)
Nyquist rate

\( X_r(j\Omega) = X(e^{j\omega}) \cdot H_r(e^{j\omega}) , \quad \text{where } H_r(e^{j\omega}) = \begin{cases} T, & \left|\omega\right|\leq\mathrm\pi \\ 0, & \text{otherwise} \end{cases} \)
\( = X(e^{j\Omega T}) \cdot H_r(e^{j\Omega T}) \)
\( = X(e^{j\Omega T}) \cdot H_r(j\Omega) \)

\( H_r(e^{j\omega}) = \begin{cases} T, & |\omega| \leq \pi \\ 0, & \text{otherwise} \end{cases} \)
\( H_r(j\Omega) = \begin{cases} T, & |\Omega| \leq \frac{\pi}{T} \\ 0, & \text{otherwise} \end{cases} \)
\( h_r(t) = \frac{1}{2\pi} \int_{-\frac{\pi}{T}}^{\frac{\pi}{T}} T \cdot e^{j\Omega t} \, d\Omega \)
\( = \frac{T}{2\pi} \cdot \frac{1}{jt} \left( e^{j\frac{\pi}{T}t} - e^{-j\frac{\pi}{T}t} \right) \)
\( = \frac{\sin\left(\frac{\pi}{T}t\right)}{\frac{\pi t}{T}} \)
\( = \text{sinc}\left(\frac{t}{T}\right) \)

\( X_r(j\Omega) = X(e^{j\omega}) \cdot H_r(e^{j\omega}) \)
\( = X_s(j\Omega) \cdot H_r(j\Omega) \)

reconstructed signal
\( x_r(t) = x_s(t) * \text{sinc}\left(\frac{t}{T}\right) \)
\( = \sum_{\tau=-\infty}^{\infty} x_s(\tau) \cdot \text{sinc}\left(\frac{t-\tau}{T}\right) \)




interpolation








[Ex]





Sampling frequency change


\(\Omega_S\geq2\Omega_N?\)

\( x[n] = x_c(nT) \)
Let \( x_d[n] = x[2n] \equiv x_c(2nT) \)
\( x_d[0] = x[0] \)
\( x_d[1] = x[2] \quad \cancel{x[1]} \)
\( x_d[2] = x[4] \quad \cancel{x[3]} \)
\( x_d[3] = x[6] \quad \cancel{x[5]} \)

\( X_d(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x_d[n] e^{-j\omega n} = \sum_{n=-\infty}^{\infty} x[2n] e^{-j\omega n} \)
(Let \( m=2n \))
\( = \sum_{m \in \text{even}} x[m] e^{-j\omega \frac{m}{2}} \)
\( = \sum_{m=-\infty}^{\infty} \frac{1}{2} \left\{ x[m] + (-1)^m x[m] \right\} e^{-j\omega \frac{m}{2}} \)
\( = \frac{1}{2} \sum_{m=-\infty}^{\infty} x[m] e^{-j\omega m/2} + \frac{1}{2} \sum_{m=-\infty}^{\infty} x[m] (-1)^m e^{-j\omega m/2} \)
as \( (-1)^m = e^{j\pi m} \),
\( \Rightarrow (-1)^m e^{-j\omega m/2} = e^{-j(\omega - 2\pi) m/2} \)
\( = \frac{1}{2} X(e^{j\omega/2}) + \frac{1}{2} \sum_{m=-\infty}^{\infty} x[m] e^{-j(\omega - 2\pi)m/2} \)
\( = \frac{1}{2} X(e^{j\omega/2}) + \frac{1}{2} X(e^{j(\omega - 2\pi)/2}) \)

\( X_d(e^{j\omega}) = \frac{1}{2} X(e^{j\omega/2}) + \frac{1}{2} X(e^{j(\omega - 2\pi)/2}) \)


\(\Rightarrow \underbrace{\frac{1}{2} X(e^{j\omega/2})}_{X_1(e^{j\omega})} + \underbrace{\frac{1}{2} X(e^{j(\omega-2\pi)/2})}_{X_2(e^{j\omega})} \)
\( X_2(e^{j\omega}) = X_1(e^{j(\omega-2\pi)}) \)



Decimation


Linear Phase Filters

Types of Linear Phase FIR Filters

\(\begin{array}{cc}Type&Classification\\I&Even-order,\;symmetric\\II&Odd-order,\;symmetric\\III&Even-order,\;antisymmetric\\IV&Odd-order,\;antisymmetric\end{array}\)

Linear phase digital filters allow all the frequency components of an input signal to pass through the filter with the same delay, which means that the group delay through the filter is a constant value independent of the frequency. Linear phase filters are useful in filtering applications in which you want to minimize signal distortion and spreading over time.

Nonlinear phase response, or dispersion, can be harmless in audio and other applications in which mild phase distortion is often imperceptible to humans. However, phase distortion can be harmful in some applications. For example, in digital communications applications, signal spreading caused by phase distortion can cause interference between time concentrated information symbols.

A minimum phase filter is a type of nonlinear phase filter that optimally minimizes the group delay at all frequencies for a given magnitude response at the expense of phase distortion. Minimum phase filters can be useful in control applications in which minimizing delay is more important than minimizing signal spreading.


Types of Linear Phase FIR Filters

The following table lists the four types of linear phase FIR filters and the characteristics of each type.


Linear Phase FIR Filter Types and Their Corresponding Frequency Characteristics
Type Classification Frequency Characteristics
I Even-order, symmetric
  • \(A(f)\) is symmetric about \(f = 0\) and \(f = 0.5\)
  • \(A(f)\) is periodic with period 1
II Odd-order, symmetric
  • \(A(f)\) is symmetric about \(f = 0\) and antisymmetric about \(f = 0.5\)
  • \(A(f)\) is constrained to 0 at \(f = 0.5\)
  • \(A(f)\) is periodic with period 2
III Even-order, antisymmetric
  • \(A(f)\) is antisymmetric about \(f = 0\) and \(f = 0.5\)
  • \(A(f)\) is constrained to 0 at both \(f = 0\) and \(f = 0.5\)
  • \(A(f)\) is periodic with period 1
IV Odd-order, antisymmetric
  • \(A(f)\) is antisymmetric about \(f = 0\) and symmetric about \(f = 0.5\)
  • \(A(f)\) is constrained to 0 at \(f = 0\)
  • \(A(f)\) is periodic with period 2

Core Summary of the 4 FIR Filter Types
Filter Type Symmetry of Impulse Response \(h[n]\) Filter Order (\(N\)) / Length (\(M = N + 1\)) Key Frequency Constraints Common Use Cases
Type I Symmetric (\(h[n] = h[N - n]\)) Even order /
Odd length
No mandatory zeros at \(f = 0\) or \(f = 0.5\). Lowpass, Highpass, Bandpass, Bandstop
Type II Symmetric (\(h[n] = h[N - n]\)) Odd order /
Even length
Zero at Nyquist (\(f = 0.5\)). Lowpass, Bandpass
(No Highpass)
Type III Antisymmetric (\(h[n] = -h[N - n]\)) Even order /
Odd length
Zero at both \(f = 0\) and \(f = 0.5\). Differentiators, Hilbert Transformers
Type IV Antisymmetric (\(h[n] = -h[N - n]\)) Odd order /
Even length
Zero at \(f = 0\). Highpass, Bandpass, Differentiators


Use the following guidelines to determine the type of linear phase FIR filter you design:
Type III and IV cannot be lowpass-like filters.
Type II and III cannot be highpass-like filters.
Type III and IV work well for differentiators or Hilbert transformers because they can give a constant 90° phase shift.


Experiment with different types. More than one type might produce an acceptable result for some target filter responses, but only one type can meet the target specifications. Select the filter type that has the smoothest frequency response. For example, the following figure illustrates the types of frequency response symmetry for each type of linear phase FIR filter, assuming a sampling frequency of fs = 1. Notice that in this example, a Type I or Type II filter has glitches, or rapid changes, at the frequency point of 1. A Type III or Type IV filter yields the smoothest frequency response because they do not contain glitches.










Filter type \( h_{\text{D}}[n], \, n \neq 0 \) \( h_{\text{D}}[n], \, n = 1 \)
Low-pass \( 2F_c \frac{\sin(n\Omega_c)}{n\Omega_c} \) \( 2F_c \)
High-pass \( 1 - 2F_c \frac{\sin(n\Omega_c)}{n\Omega_c} \) \( 1 - 2F_c \)
Band-pass \( 2F_2 \frac{\sin(n\Omega_2)}{n\Omega_2} - 2F_1 \frac{\sin(n\Omega_1)}{n\Omega_1} \) \( 2F_2 - 2F_1 \)
Band-stop \( 1 - \left[ 2F_2 \frac{\sin(n\Omega_1)}{n\Omega_1} - 2F_1 \frac{\sin(n\Omega_2)}{n\Omega_2} \right] \) \( 1 - [2F_2 - 2F_1] \)
Ideal impulse responses for various FIR filter types.

IIR

An autoregressive filter is also known as an infinite impulse response (IIR) filter, because h[n] is infinitely long (never ends).
A difference equation with only feedforward terms is called a finite impulse response (FIR) filter, because h[n] has finite length.




Sampling and Recovery

Discrete Time Processing

To more easily distinguish between signal frequencies and Fourier Transforms, one can use \(\omega\) in continuous time and \(\Omega\) in discrete time. In other words, a signal may have frequency component \(\omega\) in the time domain and \(\Omega\) when sampled. \(\Omega\) can be considered the “normalized” frequency relative to each sample in the discrete domain.

\(T\) is the sampling period such that \(\omega_s = 2 \pi / T\).

Continuous to Discrete Conversion

we can represent the Fourier Transform of a continuous time sampled signal in the \(\omega\) domain as

\[
\begin{align}
x_p(t) = \sum_{n=-\infty}^{\infty} x_c(nT) \delta(t-nT) &\stackrel{\mathcal{F}}{\leftrightarrow} X_p(j \omega) = \sum_{n=-\infty}^{\infty} x_c(nT) e^{-j \omega n T} \\
\end{align}
\]

A generic discrete time signal has the Fourier Transform in the \(\Omega\) domain as

\[
\begin{align}
x_d[n] &\stackrel{\mathcal{F}}{\leftrightarrow}
X_d(e^{j \Omega}) = \sum_{n=-\infty}^{\infty} x_d[n] e^{- j \Omega n} \\
\end{align}
\]

If we assert that this discrete time signal that relates to the continuous time signal by \(x_d[n] = x_c(nT)\) we may rewrite the Fourier Transform as

\[
\begin{align}
x_d[n] = x_c(nT) &\stackrel{\mathcal{F}}{\leftrightarrow}
X_d(e^{j \Omega}) = \sum_{n=-\infty}^{\infty} x_c(nT) e^{- j \Omega n} \\
\end{align}
\]

Note that if we substitute the relationship \(\omega = \Omega / T\) into the continuous time sampled signal \(X_p(j \omega)\), we get

\[
\begin{align}
X_p(j \Omega / T) &= \sum_{n=-\infty}^{\infty} x_c(nT) e^{-j (\Omega / T) n T} &&\omega = \Omega / T \\ \Rightarrow
X_p(j \Omega / T) &= \sum_{n=-\infty}^{\infty} x_c(nT) e^{-j \Omega n} &&\omega = \Omega / T \\
\end{align}
\]

and so, the continuous and the discrete sampled cases can be compared with

\[
\begin{align}
X_d(e^{j \Omega}) = X_p(j \Omega / T) \\
\end{align}
\]

In other words, the frequency response in the continuous case at frequency \(\omega\) will correspond to the discrete frequency \(\Omega = \omega T\), and the resulting frequency response is scaled by \(T\) in the frequency axis. This relationship \(\Omega = \omega T\) is used quite frequently in subsequent analysis, and it implies the following additional relationships of note:

\((\omega)\;\frac{radians}{second}\times(T)\;seconds\;=\;(\Omega)\;radians\)

\[
\begin{align}
\omega &= \frac{\Omega}{T} \\
\omega &= \Omega f_s \\
2 \pi f &= \Omega f_s \\
\frac{f}{f_s} &= \frac{\Omega}{2 \pi} \\
\frac{\omega}{\omega_s} &= \frac{\Omega}{2 \pi} \\
\\
T &= \frac{\Omega}{\omega} \\
f_s &= \frac{\omega}{\Omega} \\
\end{align}
\]

Comparing Continuous and Sampled Discrete Frequency Response

The continuous sampled signal can also be represented as a the scaled frequency response copied every \(\omega_s\), and defined by

\[
\begin{align}
x_p(t) = \sum_{n=-\infty}^{\infty} x_c(nT) \delta(t-nT) &\stackrel{\mathcal{F}}{\leftrightarrow} X_p(j \omega) = \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c(j(\omega – k \omega_s)) \\
\end{align}
\]

Using the substitution \(\omega = \Omega / T\) we can also rewrite the frequency response as

\[
\begin{align}
X_p(j \Omega / T) = \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c\left( j \left(\frac{\Omega}{T} – k \omega_s \right) \right) \\
\end{align}
\]

which we just found to be equivalent to \(X_d(e^{j \Omega})\) or

\[
\begin{align}

X_d(e^{j \Omega}) &= \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c\left( j \left(\frac{\Omega}{T} – k \omega_s \right) \right) \\

X_d(e^{j \Omega}) &= \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c\left( j \left(\frac{\Omega}{T} – k \frac{2 \pi}{T} \right) \right) \\

X_d(e^{j \Omega}) &= \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c\left( j \frac{\Omega – 2 \pi k}{T}\right) \\

\end{align}
\]

In other words, the frequency response of the discrete time sampled signal \(X_d(e^{j \Omega})\) maintains the same profile as the original continuous time sampled signal with some frequency and amplitude scaling and with periodic repetition in the \(\Omega\) domain.


To determine the periodicity of the frequency response, recall that in order to be periodic, the function must satisfy

\[
\begin{align}
\forall \Omega, \exists \Omega_0:&& X_d(e^{j \Omega}) &= X_d(e^{j(\Omega + \Omega_0)}) \\

&&\frac{1}{T} \sum_{k=-\infty}^{\infty} X_c\left( j \frac{\Omega – 2 \pi k}{T}\right) &= \frac{1}{T} \sum_{l=-\infty}^{\infty} X_c\left( j \frac{(\Omega + \Omega_0) – 2 \pi l}{T}\right) \\

&&\frac{\Omega – 2 \pi k}{T} &= \frac{(\Omega + \Omega_0) – 2 \pi l}{T} \\

&&\Omega – 2 \pi k &= \Omega + \Omega_0 – 2 \pi l \\

&&\Omega_0 &= 2 \pi (l – k)
\end{align}
\]

Because \(l,k \in \mathbb{Z}\), the period in the \(\Omega\) domain is \(2 \pi\). This matches our expectations for discrete signals. In summary, sampling a signal in the continuous time and representing it in discrete time is represented by the transform

\[
\begin{align}
x_d[n] = x_c(nT) &\stackrel{\mathcal{F}}{\leftrightarrow}
X_d(e^{j \Omega}) = \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c\left( j \frac{\Omega – 2 \pi k}{T}\right) \\
\end{align}
\]

Impulse Invariance: Continuous to Discrete Time System Equivalence

If the impulse response of a continuous time system is sampled, the discrete impulse response is represented by

\[
\begin{align}
h_d[n] = h_c(nT) &\stackrel{\mathcal{F}}{\leftrightarrow} H_d(e^{j \Omega}) = \frac{1}{T} \sum_{k=-\infty}^{\infty} H_c\left( j \frac{\Omega – 2 \pi k}{T}\right) \\
\end{align}
\]

so that the system output is

\[
\begin{align}
y_d[n] &\stackrel{\mathcal{F}}{\leftrightarrow} Y_d(e^{j \Omega}) = H_d (e^{j \Omega}) X_d(e^{j \Omega}) \\

y_d[n] &\stackrel{\mathcal{F}}{\leftrightarrow} Y_d(e^{j \Omega}) = H_d (e^{j \Omega}) \left[ \frac{1}{T} \sum_{k=-\infty}^{\infty} X_c\left( j \frac{\Omega – 2 \pi k}{T}\right) \right] \\

y_d[n] &\stackrel{\mathcal{F}}{\leftrightarrow} Y_d(e^{j \Omega}) = \frac{1}{T} \sum_{k=-\infty}^{\infty} H_d (e^{j \Omega}) X_c\left( j \frac{\Omega – 2 \pi k}{T}\right) \\
\end{align}
\]

Note that if we were to scale the sampled impulse response by \(T\) to generate a new discrete system \(h[n]\), we would have

\[
\begin{align}
h[n] = T h_d[n] = T h_c(nT) &\stackrel{\mathcal{F}}{\leftrightarrow} H(e^{j \Omega}) = T H_d(e^{j \Omega}) = \sum_{k=-\infty}^{\infty} H_c\left( j \frac{\Omega – 2 \pi k}{T}\right) \\
\end{align}
\]

which eliminates the scaling factor in the discrete output

\[
\begin{align}
y_d[n] &\stackrel{\mathcal{F}}{\leftrightarrow} Y_d(e^{j \Omega}) = H (e^{j \Omega}) X_d(e^{j \Omega}) \\

y_d[n] &\stackrel{\mathcal{F}}{\leftrightarrow} Y_d(e^{j \Omega}) = \frac{1}{T} \sum_{k=-\infty}^{\infty} H (e^{j \Omega}) X_c\left( j \frac{\Omega – 2 \pi k}{T}\right) \\

y_d[n] &\stackrel{\mathcal{F}}{\leftrightarrow} Y_d(e^{j \Omega}) = \frac{1}{T} \sum_{k=-\infty}^{\infty} T H_d (e^{j \Omega}) X_c\left( j \frac{\Omega – 2 \pi k}{T}\right) \\

y_d[n] &\stackrel{\mathcal{F}}{\leftrightarrow} Y_d(e^{j \Omega}) = \sum_{k=-\infty}^{\infty} H_d (e^{j \Omega}) X_c\left( j \frac{\Omega – 2 \pi k}{T}\right) \\
\end{align}
\]

Assuming we are only concerned with \(|\Omega| < \pi \implies k = 0\)

\[
\begin{align}
y_d[n] &\stackrel{\mathcal{F}}{\leftrightarrow} Y_d(e^{j \Omega}) = H_d (e^{j \Omega}) X_c \left( j \frac{\Omega}{T}\right) \\
\end{align}
\]

which appears very similar to the LTI output (convolving impulse response leads to pure multiplication in the frequency domain).

The method of scaling the impulse response to emulate a desired continuous time filter is known as impulse invariance. In other words, when

\[
\begin{align}
h[n] = T h_c(nT)
\end{align}
\]

then \(h[n]\) is said to be an impulse invariant version of \(h_c(t)\).


Signal Recovery

The process described for sampling a signal is effectively reversed when going from discrete to continuous time, and we first focus on generating an idealized continuous time sampled signal (weighted pulses spaced by \(T\)) from the discrete time sampled signal (sequence in \(n\)). The continuous time sampled signal then can be fed through continuous time Low pass filters (LPF) that represent various real-world interpolation methods to generate the re-created signal.



Discrete to Continuous Conversion


The impulse train can then be recreated for each discrete sample. That is

\[
\begin{align}
y_p(t) = \sum_{n=-\infty}^{\infty} y_d[n] \delta(t-nT)
&\stackrel{\mathcal{F}}{\leftrightarrow}
Y_p(j \omega) = \sum_{n=-\infty}^{\infty} y_d[n] e^{-j \omega n T} \\
\end{align}
\]

The discrete sample signal frequency response \(Y_d\) will repeat every \(2\pi\) in the \(\Omega\) domain as any discrete signal would. We also know that the output continuous signal frequency response \(Y_p(j \omega)\) will repeat in the \(\omega\) domain relative to the output sampling frequency \(\omega_s = 2 \pi / T\), and so \(\Omega = \omega T\) still holds as a viable comparison between \(\Omega\) and \(\omega\) domains.

This pulsed output signal \(Y_p(j \omega)\) contains information of the single desired result we want in the continuous domain, which we can denote as the idealized \(Y_c\) which is repeated every \(\omega_s\) in the \(\omega\) domain and scaled.

\[
\begin{align}
Y_p(j \omega) &= \frac{1}{T} \sum_{k=-\infty}^{\infty} Y_c(j(\omega – k \omega_s)) \\
\end{align}
\]

From this, we can see that to accurately recreate \(Y_d\) in continuous time, the ideal filter applied to \(Y_p\) scales all signals \(0 < |\omega| < \omega_s / 2\) by \(T\), and all other frequency information is removed. This idealized interpolation method is explored further below.

Note that the following discussion reverts back to using signal \(x\) instead of signal \(y\) for generality.


Interpolation

An interpolation formula describes how to fit a continuous curve between sample points \(x(nT)\) using a filter \(h(t)\mathop{\leftrightarrow}\limits^{{\mathcal{F}}}H(j\omega )\). Note that the shape of the filter impulse response \(h(t)\) is convolved with the idealized continuous sample pulse \(x_p(t)\) to represent the recovered signal.

\[
\begin{align}
x_r(t) &= x_p(t) * h(t) \\
x_r(t) &= \left[ \sum_{n=-\infty}^{\infty} x(nT) \delta(t-nT) \right] * h(t) \\
x_r(t) &= \sum_{n=-\infty}^{\infty} x(nT) h(t – nT) \\
\\
X_r(j \omega) &= X_p(j \omega) H(j \omega) \\
\end{align}
\]

The analysis does not need to be limited to the idealized continuous time sampled signal, and the same result appears if using discrete sampled values and the discrete frequency response.

\[
\begin{align}
x_r(t) &= \sum_{n=-\infty}^{\infty} x_d[n] * h(t – nT) \\
\\
X_r(j \omega) &= \sum_{n=-\infty}^{\infty} x_d[n] H(j \omega) e^{-j \omega T n} \\
X_r(j \omega) &= H(j \omega) \sum_{n=-\infty}^{\infty} x_d[n] e^{-j \omega T n} \\
X_r(j \omega) &= H(j \omega) \sum_{n=-\infty}^{\infty} x_d[n] e^{-j \Omega n} \\
X_r(j \omega) &= H(j \omega) X_d(e^{j \Omega}) \\
\end{align}
\]


Ideal Signal Recreation Filter / Ideal Low-Pass Filter

This filter recreates the original signal perfectly such that \(x_r(t) = x(t)\) It is difficult to implement in real-life, but provides a useful foundation of analysis.

A unity-gain low-pass filter is described by

\[H_u(j\omega)=\left\{\begin{array}{lc}1&\left|\omega\right|<\omega_c\\0&\left|\omega\right|\geq\omega_c\end{array}\right.\]

Which can be found to have a frequency response of

\[
\begin{align}
h_u(t) &= \frac{\sin(\omega_c t)}{\pi t} \\
\end{align}
\]

Recall that the magnitude of \(X_p(j \omega)\) is \(X(j \omega)\) scaled by \(1/T\), so in order to get the recovered signal spectrum \(X_r(j \omega)\), we would need to scale the filter by the sampling period, \(T\). That is, the ideal signal recovery interpolation filter is described by

\[H(j\omega)=\left\{\begin{array}{lc}T&\left|\omega\right|<\omega_c\\0&\left|\omega\right|\geq\omega_c\end{array}\right.\]

\[
\begin{align}
H(j \omega) = T H_u (j \omega)
\end{align}
\]

\[
\begin{align}
h(t) &= T \frac{\sin(\omega_c t)}{\pi t} \\
h(t) &= \frac{\omega_c T}{\pi} \frac{\sin(\omega_c t)}{\omega_c t} \\
h(t) &= \frac{\omega_c T}{\pi} sinc(\omega_c t) \\
\end{align}
\]

So the recovered signal becomes
\[
\begin{align}
x_r(t) &= \sum_{n=-\infty}^{\infty} x(nT) \frac{\omega_c T}{\pi} \frac{\sin(\omega_c (t-nT))}{\omega_c (t-nT)} \\
\end{align}
\]

In the case where we assume the signal is band-limited and no aliasing occurs, we can use \(\omega_c = \omega_s/2 = \pi/T\) to get

\[
\begin{align}
h(t) &= \frac{\sin(\pi t / T)}{\pi t / T} \\
h(t) &= sinc(\pi t / T) \\
\end{align}
\]

The reconstructed signal is then described by

\[
\begin{align}
x_r(t) &= \sum_{n=-\infty}^{\infty} x(nT) h(t – nT) \\
x_r(t) &= \sum_{n=-\infty}^{\infty} x(nT) \frac{\sin[\pi (t – nT) / T]}{\pi (t – nT) / T} \\
x_r(t) &= \sum_{n=-\infty}^{\infty} x[n] \frac{\sin[\pi (t – nT) / T]}{\pi (t – nT) / T} \\
\end{align}
\]

In other words, the summation of sinc functions at each time step scaled by the original signal exactly replicates the original signal.



Zero-Order Hold (ZOH)

More common in practice than multiplying input signal by generated impulses. Output is equivalent to convolving \(x_p(t)\) (same as above) with a filter, \(H_0(j \omega)\), that has impulse response, \(h_0(t)\), that is unity between \(t=0\) and \(t=T\).






Note that \(H_0(j \omega)\) is very similar to the rectangular pulse, but shifted in time.

\[
\begin{align}
H_{sq} (j \omega) &= \frac{2 sin(\omega T/2)}{\omega}
&& \text{Square of width }T\text{, centered at }t=0 \\
H_0 (j \omega) &= e^{-j \omega T/2} \frac{2 sin(\omega T/2)}{\omega}
&& \text{Square of width }T\text{, delayed by }t=T/2 \\
\end{align}
\]

If the effects of the Zero-Order hold are desired to be reversed, an ideal reconstruction filter \(H_r(j \omega)\) would be

\[
\begin{align}
H_0(j \omega) H_r(j \omega) &= 1 \\
H_r(j \omega) &= \frac{1}{H_0(j \omega)} \\
H_r(j \omega) &= \frac{1}{e^{-j \omega T/2} \frac{2 sin(\omega T/2)}{\omega}} \\
H_r(j \omega) &= \frac{e^{j \omega T/2}}{\frac{2 sin(\omega T/2)}{\omega}} \\
\end{align}
\]



First-Order Hold/Linear Interpolation

Consider \(x_p(t)\), the series of impulses weighted by \(x(t)\)

\[
\begin{align}
x_p(t) &= \sum_{n=-\infty}^{\infty} x(nT) \delta(t-nT) \\
\end{align}
\]

An interpolating filter \(h(t)\) would then generate a recreated signal, \(x_r(t)\) be described as

\[
\begin{align}

x_r(t) &= x_p(t) * h(t) \\

x_r(t) &= \left[ \sum_{n=-\infty}^{\infty} x(nT) \delta(t-nT) \right] * h(t) \\

x_r(t) &= [ \cdots + x(-2T)\delta(t+2T) + x(-T)\delta(t+T) + x(0)\delta(t) + \\
&x(T)\delta(t-T) + x(2T)\delta(t-2T) + \cdots] * h(t) \\

x_r(t) &= \cdots + x(-2T)h(t+2T) + x(-T)h(t+T) + x(0)h(t) + \\
&x(T)h(t-T) + x(2T)h(t-2T) + \cdots \\
\end{align}
\]

Alternatively, one can find more simply that

\[
\begin{align}
x_r(t) &= x_p(t) * h(t) \\
x_r(t) &= \left[ \sum_{n=-\infty}^{\infty} x(nT) \delta(t-nT) \right] * h(t) \\
x_r(t) &= \sum_{n=-\infty}^{\infty} x(nT) \left[ \delta(t-nT) * h(t) \right] \\
x_r(t) &= \sum_{n=-\infty}^{\infty} x(nT) h(t-nT) \\
\end{align}
\]

If we confine our focus to the region between two impulses of \(x_p(t)\), say at some \(t_0\), we can make some conceptual simplifications to determine the interpolation function. Note that in this case, all impulses of \(x_p(t)\) where \(t > t_0\) are weighted by the acausal side of \(h(t)\) (\(t < 0\)) whereas all the impulses of \(x_p(t)\) where \(t \leq t_0\) are weighted by the causal half of \(h(t)\) (\(t \geq 0\)). Graphically, we can split \(h(t)\) into two functions where

\[ h(t) = h_{pre}(t) + h_{post}(t) \]



Now with knowledge of what we want as the output, we can define the interpolation function. For example if we know that we want

\[
\begin{align}
x_r(t_0) = x(t_0) && { t_0 | t_0=nT, n \in \mathbb{Z}} \\
\end{align}
\]

then

\[
\begin{align}
x_r(0) &= \cdots + x(-2T)h(2T) + x(-T)h(T) + x(0)h(0) + \\
&x(T)h(-T) + x(2T)h(-2T) + \cdots \\
\\
&= x(0)\\
\end{align}
\]

and

\[
\begin{align}
x_r(T) &= \cdots + x(-2T)h(T+2T) + x(-T)h(T+T) + x(0)h(T) + \\
&x(T)h(T-T) + x(2T)h(T-2T) + \cdots \\
&= \cdots + x(-2T)h(3T) + x(-T)h(2T) + x(0)h(T) + \\
&x(T)h(0) + x(2T)h(-T) + \cdots \\
&= x(T)\\
\end{align}
\]

then to be agnostic of the input function, \(x(t)\), we must set

\[
\begin{align}
h(0) = 1 \\

h(t) = 0 && \forall |t| \geq T
\end{align}
\]

Now, let’s pick \(t_0 \in [0,T]\) and only look at this interval. In this case we can rewrite \(x_r(t)\) as

\[
\begin{align}
x_r(t_0) &= \cdots + x(-2T)h_{post}(t_0+2T) + x(-T)h_{post}(t_0+T) + x(0)h_{post}(t_0) + \\
&x(T)h_{pre}(t_0-T) + x(2T)h_{pre}(t_0-2T) + \cdots && t_0 \in [0,T] \\
\end{align}
\]

Applying these constraints, \(x_r(t)\) has many terms that become 0 and it simplifies to

\[
\begin{align}
x_r(t_0) &= x(0)h_{post}(t_0) + x(T)h_{pre}(t_0-T) && t_0 \in [0,T] \\
\end{align}
\]

Additionally, if we want \(x_r(t_0)\) to resemble a line between the two samples (first-order hold/linear interpolation), we set the equation of that line equal to \(x_r(t)\) then solve for the impulse response function that makes that possible.

\[
\begin{align}
x(0)h_{post}(t_0) + x(T)h_{pre}(t_0-T) &= x(0) + \frac{x(T) – x(0)}{T} t_0 && t_0 \in [0,T] \\
x(0)h_{post}(t_0) + x(T)h_{pre}(t_0-T) &= x(0) + \frac{1}{T} x(T) t_0 – \frac{1}{T}x(0) t_0 && t_0 \in [0,T] \\
x(0)h_{post}(t_0) + x(T)h_{pre}(t_0-T) &= x(0)\left[1 – \frac{t_0}{T} \right] + x(T) \frac{t_0}{T} && t_0 \in [0,T] \\
\end{align}
\]

The impulse response function can then be isolated such that

\[
\begin{align}
h_{post}(t) = 1 – \frac{t}{T} \\
h_{post}(t) = \frac{T – t}{T} \\
\\
h_{pre}(t-T) = \frac{t}{T} \\
h_{pre}(t) = \frac{t+T}{T} \\
\end{align}
\]

and so the final impulse response is

\[h(t)=\left\{\begin{array}{lc}\frac{t+T}T&-T<t<0\\\frac{T-t}T&0\leq t<T\\0&otherwise\end{array}\right.\]



Note that the impulse response is acausal, but \(h(t) = 0 \;\;\; \forall t > T\), so one can effectively achieve linear interpolation with a latency of \(T\).

Transfer function is determined by taking derivatives

\[h'(t)=\left\{\begin{array}{lc}\frac1T&-T<t<0\\\frac{-1}T&0\leq t<T\\0&otherwise\end{array}\right.\]

\[
h”(t) = \frac{1}{T} \delta(t+T) – \frac{2}{T} \delta(t) + \frac{1}{T} \delta(t-T)
\]

\[
\begin{align}
H”(j \omega) = \frac{1}{T} e^{j \omega T} – \frac{2}{T} + \frac{1}{T} e^{-j \omega T} \\
H”(j \omega) = \frac{1}{T} \left[ e^{j \omega T} + e^{-j \omega T} -2 \right] \\
\end{align}
\]

\[
\begin{align}
H(j \omega) = \frac{1}{(j \omega)^2 T} \left[2 \cos(\omega T) -2 \right] &&\omega \neq 0 \\
H(j \omega) = \frac{2}{(j \omega)^2 T} \left[\cos(\omega T) – 1 \right] &&\omega \neq 0 \\
\end{align}
\]

Half Angle Formula

\[
\begin{array}{ll}
sin^2(x) = \frac{1 – cos(2x)}{2} \\
2 sin^2(x) = 1 – cos(2x) \\
cos(2x) – 1 = – 2 sin^2(x)
\end{array}
\]

\[
\begin{align}
2x = \omega T \\
x = \frac{\omega T}{2} \\
\end{align}
\]

\[
\begin{align}
H(j \omega) = \frac{2}{(j \omega)^2 T} \left[ -2 \sin^2 \left( \frac{\omega T}{2} \right) \right] &&\omega \neq 0 \\
H(j \omega) = \frac{-4 \sin^2 (\omega T/2)}{(j \omega)^2 T} &&\omega \neq 0 \\
H(j \omega) = \frac{1}{T} \frac{4 \sin^2 (\omega T/2)}{ \omega^2} &&\omega \neq 0 \\
H(j \omega) = \frac{1}{T} \frac{\sin^2 (\omega T/2)}{ (\omega / 2)^2} &&\omega \neq 0 \\
H(j \omega) = T \frac{\sin^2 (\omega T/2)}{ (\omega T / 2)^2} &&\omega \neq 0 \\
H(j \omega) = T sinc^2 (\omega T/2) &&\omega \neq 0 \\
H(j \omega) = \frac{2 \pi}{\omega_s} sinc^2 \left(\pi \frac{\omega}{\omega_s} \right) &&\omega \neq 0 \\
\end{align}
\]



DSP Filter



Butterworth

Consider the n-th order signal transfer function

\[
\begin{align}
H(j \omega) &= \frac{1}{1 + j( \omega / \omega_0 )^{n}} \\
\end{align}
\]

Signal magnitude can then be determined by

\[
\begin{align}
H(j \omega) H^*(j \omega) &=\frac{1}{1 + j( \omega / \omega_0 )^{n}} \frac{1}{1 – j( \omega / \omega_0 )^{n}} \\
H(j \omega) H^*(j \omega) &=\frac{1}{1 + ( \omega / \omega_0 )^{2n}} \\
|H(j \omega)|^2 &=\frac{1}{1 + ( \omega / \omega_0 )^{2n}} \\
|H(j \omega)| &=\frac{1}{ \sqrt{1 + ( \omega / \omega_0 )^{2n} } } \\
\end{align}
\]

This magnitude response defines the n-th order Butterworth Filter.

Magnitude at Critical Frequency is

\[
\begin{align}
|H(j \omega_0)| &=\frac{1}{ \sqrt{1 + ( \omega_0 / \omega_0 )^{2n} } } \\
|H(j \omega_0)| &=\frac{1}{ \sqrt{ 2 } } \\
\\
|H(j \omega_0)|^2 &=\frac{1}{ 2 } \\
10 \log_{10} |H(j \omega_0)|^2 &\approx -3 dB \\
\end{align}
\]



Maximal Flatness

The goal of the Butterworth filter is to create a filter that is “maximally flat” at some known frequency. This is achieved by maximizing the number of derivatives of the frequency response with respect to frequency that are 0.

To get a better understanding, let’s first consider the equation \(X_1(\omega) = a + \omega^4, a \in \mathbb{Z}\). Taking successive derivatives, we have

\[
\begin{align}
X_1(\omega) &= a + \omega^4 \\
\frac{d}{d \omega} X_1(\omega) &= 4 \cdot \omega^3 &&\text{1st Derivative} \\
\frac{d^2}{d \omega^2} X_1(\omega) &= 4 \cdot 3 \cdot \omega^2 &&\text{2nd Derivative} \\
\frac{d^3}{d \omega^3} X_1(\omega) &= 4 \cdot 3 \cdot 2 \cdot \omega &&\text{3rd Derivative} \\
\frac{d^4}{d \omega^4} X_1(\omega) &= 4 \cdot 3 \cdot 2 \cdot 1 &&\text{4th Derivative} \\
\frac{d^5}{d \omega^5} X_1(\omega) &= 0 &&\text{5th Derivative} \\
\end{align}
\]

Generalizing the pattern, we can consider the generalized equation

\[
\begin{align}
X_1(\omega) &= a + \omega^n \\
\end{align}
\]

The kth derivative can then be described as

\[ (k \in \mathbb{Z}) \wedge (k > 0) \implies \frac{d^k}{d\omega^k}X_1(\omega) = \begin{cases} \frac{n!}{(n - k)!} \omega^{n - k} & 0 < k < n \\ n! & k=n \\ 0 & k> n \end{cases} \]

Note that if we are evaluating the derivatives at \(\omega=0\), then the above simplifies to

\[ \left[ \frac{d^k}{d\omega^k} X_1(\omega) \right]_{\omega = 0} = \begin{cases} 0 & 0 < k < n \\ n! & k=n \\ 0 & k> n \end{cases} \]

and the derivatives are only nonzero in the nth derivative. This result becomes useful in the achieving maximal flatness in that the first n-1 derivatives are all 0.

Now, if we define a new frequency response \(X_2(\omega) = \frac{1}{a + \omega^4} = [a + \omega^4]^{-1}\), we have

\[
\begin{align}
X_2(\omega) =& \frac{1}{a + \omega^4} \\
X_2(\omega) =& [a + \omega^4]^{-1} \\
\\
\frac{d}{d \omega} X_2(\omega) =& (-1) [a + \omega^4]^{-2} \cdot \frac{d}{d \omega} X_1(\omega) &&\text{1st Derivative} \\
\\
\frac{d^2}{d \omega^2} X_2(\omega) =
&(-1)(-2) [a + \omega^4]^{-3} \cdot \frac{d}{d \omega} X_1(\omega) + &&\text{2nd Derivative}\\
&(-1) [a + \omega^4]^{-2} \cdot \frac{d^2}{d \omega^2} X_1(\omega) \\
\\
\frac{d^3}{d \omega^3} X_2(\omega) =
&(-1)(-2)(-3) [a + \omega^4]^{-4} \cdot \frac{d}{d \omega} X_1(\omega) + &&\text{3rd Derivative}\\
&(-1)(-2) [a + \omega^4]^{-3} \cdot \frac{d^2}{d \omega^2} X_1(\omega) + \\
&(-1)(-2) [a + \omega^4]^{-3} \cdot \frac{d^2}{d \omega^2} X_1(\omega) + \\
&(-1) [a + \omega^4]^{-2} \cdot \frac{d^3}{d \omega^3} X_1(\omega) \\
=
&(-1)(-2)(-3) [a + \omega^4]^{-4} \cdot \frac{d}{d \omega} X_1(\omega) + \\
&2(-1)(-2) [a + \omega^4]^{-3} \cdot \frac{d^2}{d \omega^2} X_1(\omega) + \\
&(-1) [a + \omega^4]^{-2} \cdot \frac{d^3}{d \omega^3} X_1(\omega) \\
\\

\frac{d^4}{d \omega^4} X_2(\omega) =
&(-1)(-2)(-3)(-4) [a + \omega^4]^{-5} \cdot \frac{d}{d \omega} X_1(\omega) + &&\text{4th Derivative}\\
&(-1)(-2)(-3) [a + \omega^4]^{-4} \cdot \frac{d^2}{d \omega^2} X_1(\omega) + \\
&2(-1)(-2)(-3) [a + \omega^4]^{-4} \cdot \frac{d^2}{d \omega^2} X_1(\omega) + \\
&2(-1)(-2) [a + \omega^4]^{-3} \cdot \frac{d^3}{d \omega^3} X_1(\omega) + \\
&(-1)(-2) [a + \omega^4]^{-3} \cdot \frac{d^3}{d \omega^3} X_1(\omega) + \\
&(-1) [a + \omega^4]^{-2} \cdot \frac{d^4}{d \omega^4} X_1(\omega) \\
=
&(-1)(-2)(-3)(-4) [a + \omega^4]^{-5} \cdot \frac{d}{d \omega} X_1(\omega) + \\
&3(-1)(-2)(-3) [a + \omega^4]^{-4} \cdot \frac{d^2}{d \omega^2} X_1(\omega) + \\
&3(-1)(-2) [a + \omega^4]^{-3} \cdot \frac{d^3}{d \omega^3} X_1(\omega) + \\
&(-1) [a + \omega^4]^{-2} \cdot \frac{d^4}{d \omega^4} X_1(\omega) \\
\end{align}
\]

Noting the pattern as combinatorial in nature, we may summarize the kth derivative as a sum of k terms where

\[
\frac{d^k}{d \omega^k} \frac{1}{a + \omega^n} = \sum_{l=1}^k \binom{k}{l} (-1)^l (k-l+1)! [a + \omega^n]^{-(k-l+2)} \left[ \frac{d^l}{d \omega^l} (a + \omega^n) \right]
\]

More importantly, note however that from our previous analysis, the evaluation of \(\frac{d^l}{d \omega^l} (a + \omega^n)\) at \(\omega=0\) will always be 0 except when \(l=k=n\). In short, we have a similar result as before where

\[ \left[ \frac{d^k}{d\omega^k} \frac{1}{a + \omega^n} \right]_{\omega = 0} = \begin{cases} 0 & 0 < k < n \\ C \neq 0 & k=n \\ 0 & k> n \end{cases} \]

which achieves our goal to maximize flatness.

Reviewing the previous analysis, one can also readily claim (again without rigorous proof) that the following statement is also true, which we will use in the next section.

\[ \left[ \frac{d^k}{d\omega^k} \frac{1}{1 + \left( \frac{\omega}{\omega_0} \right)^n} \right]_{\omega = 0} = \begin{cases} 0 & 0 < k < n \\ C \neq 0 & k=n \\ 0 & k> n \end{cases} \]



Coefficients

Up until now, we have determined the desired frequency response for maximal flatness. However, this does not necessarily indicate what the transfer function actually is, and where the poles are. Now, consider the transfer function when substituting the previous frequency, \(\omega \in \mathbb{R}\), for any complex frequency, \(s \in \mathbb{C}\).

\[
\begin{align}
X_3(s) &= \frac{1}{1 + \left( \frac{s}{\omega_0} \right)^n}
\end{align}
\]

To determine the poles, we first examine the denominator to determine when it equates to 0.

\[
\begin{align}
1 + \left( \frac{s_p}{\omega_0} \right)^n &= 0 \\
\left( \frac{s_p}{\omega_0} \right)^n &= -1 \\
s_p^n &= -1 \cdot \omega_0^n \\
\end{align}
\]

For an nth degree polynomial (the rightmost t, the Fundamental Theorem of Algebra dictates that there must be n roots in the complex plane. Additionally, any complex number may be represented using polar coordinates.

\[
\begin{align}
(r_p e^{\theta_p})^n &= -1 \cdot \omega_0^n \\
\end{align}
\]

Note that the right side is real (\(\theta = 0 \pm k \pi\)), and the magnitude is known, so the poles must satisfy

\[
\begin{align}

\end{align}
\]

Butterworth fourth order bandpass filter


Butterworth fourth order low-pass filter


the Second Order IIR Butterworth Band Pass Filter


4th Order Low-pass Filter with 1 Op Amp




Bessel

In electronics and signal processing, a Bessel filter is a type of analog linear filter with a maximally flat group delay (i.e., maximally linear phase response), which preserves the wave shape of filtered signals in the passband. Bessel filters are often used in audio crossover systems.

Transfer function

A Bessel low-pass filter is characterized by its transfer function:
\[ H(s) = \frac{\theta_n(0)}{\theta_n(s/\omega_0)} \]

where \( \theta_n(s) \) is a reverse Bessel polynomial from which the filter gets its name and \( \omega_0 \) is a frequency chosen to give the desired cut-off frequency. The filter has a low-frequency group delay of \( 1/\omega_0 \). Since \( \theta_n(0) \) is indeterminate by the definition of reverse Bessel polynomials, but is a removable singularity, it is defined that \( \theta_n(0) = \lim_{x \to 0} \theta_n(x) \).

Bessel polynomials

The transfer function of the Bessel filter is a rational function whose denominator is a reverse Bessel polynomial, such as the following:

\( n = 1: \quad s + 1 \)
\( n = 2: \quad s^2 + 3s + 3 \)
\( n = 3: \quad s^3 + 6s^2 + 15s + 15 \)
\( n = 4: \quad s^4 + 10s^3 + 45s^2 + 105s + 105 \)
\( n = 5: \quad s^5 + 15s^4 + 105s^3 + 420s^2 + 945s + 945 \)

The reverse Bessel polynomials are given by:
\[ \theta_n(s) = \sum_{k=0}^{n} a_k s^k, \]

where
\[ a_k = \frac{(2n - k)!}{2^{n-k} k! (n - k)!} \quad k = 0, 1, \dots, n. \]

Setting the cutoff attenuation

There is no standard set attenuation value for Bessel filters. However, \(-3.0103\text{ dB}\) is a common choice. Some applications may use a higher or lower attenuation such as \(-1\text{ dB}\) or \(-20\text{ dB}\). Setting the cut-off attenuation frequency involves first finding the frequency that achieves the desired attenuation, which will be referred to as \(\omega_c\), and then scaling the \(H(s)\) polynomials to the inverse of that frequency. To scale the polynomials, simply append \(\omega_c\) to the \(s\) term in each coefficient, as shown in the 3-pole Bessel filter example below.

\[ H(s) = \frac{15}{s^3 + 6s^2 + 15s + 15} \]
\[ H(s)' = H(s)_{\text{desired dB at } \omega=1} = \frac{15}{(\omega_c s)^3 + 6(\omega_c s)^2 + 15\omega_c s + 15} \]

\(\omega_c\) may be found with Newton's method, or with root finding.


Pole Locations:

The three poles are located entirely in the stable Left Half-Plane (LHP) of the \(s\)-plane:
Real Pole:
\( s_1 \approx -2.3222 \)
Complex Conjugate Pole Pair:
\( s_{2,3} \approx -1.8389 \pm 1.7544j \)



Chebyshev Filter

Chebyshev filters are analog or digital filters that have a steeper roll-off than Butterworth filters, and have either passband ripple (type I) or stopband ripple (type II). Chebyshev filters have the property that they minimize the error between the idealized and the actual filter characteristic over the operating frequency range of the filter, but they achieve this with ripples in the frequency response.

Chebyshev Type I
Chebyshev Type II
Elliptic

\(\Delta \)\(\Sigma \) modulator

Delta-sigma modulation

Delta-sigma ADC basics



  • The number \(0\), the additive identity.
  • The number \(1\), the multiplicative identity.
  • The \(\pi\) The number \(\pi\) \((\pi = 3.1415...)\), the fundamental circle constant.
  • The number \(e\) \((e = 2.718...)\), also known as Euler's number, which occurs widely in mathematical analysis.
  • The number \(i\), the imaginary unit of the complex numbers.

a5

ABCD

a8

ABCD

a9

ABCD

a10

ABCD

Third-order Low-Pass Butterworth filter
Bessel Low-Pass filter
Chebyshev filter

good material : https://www.scribd.com/document/644301294/1-b-pdf