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}\)

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

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-½)\)

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.

a1

ABCD

a2

ABCD

a3

ABCD

a4

ABCD

a5

ABCD

a6

ABCD

a7

ABCD

a8

yahoo

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

\(\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.

Mathematical Constant \(e\)

Euler's formula illustrated in the complex plane

Trigonometric function	Equation
\(\large Sine\)	\(\large \sin(\theta)\;=\;\;\frac{opposite}{hypotenuse}\)
\(\large Cosine\)	\(\large \cos(\theta)\;=\;\frac{adjacent}{hypotenuse}\)
\(\large Tangent\)	\(\large \tan(\theta)\;=\;\frac{opposite}{adjacent}\)
\(\large Cosecant\)	\(\large \csc(\theta)\;=\;\;\frac{hypotenuse}{opposite}\)
\(\large Secant\)	\(\large \sec(\theta)\;=\;\frac{hypotenuse}{adjacent}\)
\(\large Cotangent\)	\(\large \cot(\theta)\;=\;\frac{adjacent}{opposite}\)

a6

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}\)

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