Lecture 1

Lecture 2

Lecture 3

Lecture 4

Lecture 5

Lecture 6

Lecture 7

GPT help

Fourier Transform & Sampling Formula Sheet

1. Continuous Fourier Transform (CFT / CTFT)

1-D CFT

Xc(Ω)=∫−∞∞xc(t)e−jΩt,dt

Inverse:

xc(t)=12π∫−∞∞Xc(Ω)ejΩt,dΩ

2-D CFT

Xc(Ω1,Ω2)=∫−∞∞∫−∞∞xc(t1,t2)e−j(Ω1t1+Ω2t2)dt1dt2

Inverse:

xc(t1,t2)=1(2π)2∫∫Xc(Ω1,Ω2)ej(Ω1t1+Ω2t2)dΩ1dΩ2


2. Discrete-Time Fourier Transform (DTFT)

1-D DTFT

X(ω)=∑n=−∞∞x[n]e−jωn

Inverse:

x[n]=12π∫−ππX(ω)ejωndω

Periodicity

X(ω+2π)=X(ω)

2-D DTFT

X(ω1,ω2)=∑n1=−∞∞∑n2=−∞∞x[n1,n2]e−j(ω1n1+ω2n2)

Inverse:

x[n1,n2]=1(2π)2∫−ππ∫−ππX(ω1,ω2)ej(ω1n1+ω2n2)dω1dω2

Periodicity:

X(ω1+2πk1,ω2+2πk2)=X(ω1,ω2)


3. Discrete Fourier Transform (DFT)

1-D N-Point DFT

X[k]=∑n=0N−1x[n]e−j2πkn/N

Inverse:

x[n]=1N∑k=0N−1X[k]ej2πkn/N

where:

n,k=0,…,N−1

DFT as Samples of the DTFT

X[k]=X(ω)|ω=2πk/N

2-D DFT

X[k1,k2]=∑n1=0N1−1∑n2=0N2−1x[n1,n2]e−j2π(k1n1N1+k2n2N2)

Inverse:

x[n1,n2]=1N1N2∑k1=0N1−1∑k2=0N2−1X[k1,k2]ej2π(k1n1N1+k2n2N2)


4. Important Fourier Transform Pairs

Constant

1-D

FTC=2πCδ(ω)

2-D

FTC=(2π)2Cδ(ω1,ω2)

Constant signal → impulse at zero frequency (DC).


Impulse

1-D

FTδ[n]=1

Shifted:

FTδ[n−n0]=e−jωn0

2-D

FTδ[n1,n2]=1

Shifted:

FTδ[n1−a,n2−b]=e−j(ω1a+ω2b)

Shifted impulse → complex exponential.


5. Complex Exponential

1-D

FTejγn=2πδ(ω−γ)

2-D

FTej(γ1n1+γ2n2)=(2π)2δ(ω1−γ1,ω2−γ2)

Complex exponential → one frequency impulse.


6. Cosine

Euler's identity:

cos⁡(θ)=12(ejθ+e−jθ)

1-D

FTAcos⁡(γn)=Aπ[δ(ω−γ)+δ(ω+γ)]

2-D

FTAcos⁡(γ1n1+γ2n2)=A(2π)22[δ(ω1−γ1,ω2−γ2)+δ(ω1+γ1,ω2+γ2)]

Cosine → two impulses at ±(γ1,γ2).


7. Sine

Euler's identity:

sin⁡(θ)=ejθ−e−jθ2j

1-D

FTAsin⁡(γn)=Aπj[δ(ω−γ)−δ(ω+γ)]

Sine → two impulses with opposite signs/phases.


8. Gaussian

e−αt2↔παe−Ω2/(4α)

2-D:

e−α(t12+t22)↔παe−(Ω12+Ω22)/(4α)

Gaussian ↔ Gaussian.


9. 45-Degree Impulse Line

δ[n1−n2]↔2πδ(ω1+ω2)

Spatial line:

n1=n2

Frequency line:

ω1=−ω2


10. Linearity

If:

x1↔X1

x2↔X2

then:

ax1+bx2↔aX1+bX2

Transform each term separately and add the results.


11. Time/Spatial Shift

1-D

x[n−n0]↔e−jωn0X(ω)

2-D

x[n1−a,n2−b]↔e−j(ω1a+ω2b)X(ω1,ω2)

Shift in time/space → phase change in frequency.


12. Frequency Shift

1-D

ejω0nx[n]↔X(ω−ω0)

2-D

ej(γ1n1+γ2n2)x[n1,n2]↔X(ω1−γ1,ω2−γ2)

Multiply by complex exponential → shift spectrum.


13. Convolution

x∗h↔XH

For an LSI system:

y=x∗h

Therefore:

Y=XH

and:

H=YX

Convolution in time/space ↔ multiplication in frequency.


14. Multiplication

1-D

x[n]h[n]↔12π(X∗H)(ω)

2-D

x[n1,n2]h[n1,n2]↔1(2π)2(X∗H)(ω1,ω2)

Multiplication in time/space → convolution in frequency.


15. Complex Conjugation

x^_[n_1,n_2]\leftrightarrow X^_(-\omega_1,-\omega_2)

For a real signal:

X(−ω1,−ω2)=X∗(ω1,ω2)


16. Sampling

Continuous → Discrete

x[n]=xc(nT)

2-D:

x[n1,n2]=xc(n1T1,n2T2)

Sampling Frequency

fs=1T

Angular Sampling Frequency

Ωs=2πT

Continuous Frequency → Discrete Frequency

ω=ΩT

2-D:

ω1=Ω1T1

ω2=Ω2T2


17. Nyquist / Aliasing

Nyquist criterion:

fs>2fmax

Angular frequency:

Ωs>2Ωmax

Since Ωs=2πT:

Ωmax<πT

2-D

Ωc1<πT1

Ωc2<πT2

If both conditions hold → no aliasing.

If spectral copies overlap → aliasing.


18. Sampling Creates Spectral Copies

For T=1:

X(ω)=∑k=−∞∞Xc(ω−2πk)

General sampling period:

X(ω)=1T∑k=−∞∞Xc(ω−2πkT)

Spectral copies are separated by:

Ωs=2πT

Sampling in time/space → periodic copies in frequency.


19. Reconstruction

Ideal sinc reconstruction:

xc(t)=∑n=−∞∞x[n]sinc(t−nTT)

where:

sinc(x)=sin⁡(πx)πx

Important properties:

sinc(0)=1

sinc(k)=0,k=±1,±2,…

Therefore:

xc(nT)=x[n]

Perfect Reconstruction Condition

Ωmax<πT⇒No aliasing⇒Perfect reconstruction possible


20. Unit Impulse

δ[n]={1,n=0,n≠0

2-D:

δ[n1,n2]=1 only at (n1,n2)=(0,0).

Shifted:

δ[n−n0] is located at n=n0.


21. Unit Step

u[n]={1,n≥0/0,n<0

Useful rectangular signal:

u[n]−u[n−N]={1,0≤n≤N−1/0,otherwise


22. Delta Selection Property

∑nx[n]δ[n−n0]=x[n0]

2-D:

∑n1∑n2x[n1,n2]δ[n1−a]δ[n2−b]=x[a,b]

Delta "selects" the value at its location.


23. Important DFT Pairs

All Ones

x[n]=1↔X[k]=Nδ[k]

Impulse

δ[n]↔1

Shifted Impulse

δ[n−n0]↔e−j2πkn0/N

Complex Exponential

ej2πk0n/N↔Nδ[(k−k0)modN]


24. Geometric Sum

∑n=0N−1rn=1−rN1−r

Important DFT version:

∑n=0N−1e−j2πkn/N={N,k=0(modN)/0,otherwise


25. Spatial Aliasing

Sampling an N1×N2 DTFT grid and taking the IDFT gives:

s^[n1,n2]=∑r1=−∞∞∑r2=−∞∞s[n1+r1N1,n2+r2N2]

For a 256×256 DFT:

s^[n1,n2]=∑r1=−∞∞∑r2=−∞∞s[n1+256r1,n2+256r2]

Sampling in frequency → periodic repetition/summing in space.


⭐ Highest Priority Formulas to Memorize

X(ω1,ω2)=∑n1∑n2x[n1,n2]e−j(ω1n1+ω2n2)

x[n1,n2]=1(2π)2∫−ππ∫−ππX(ω1,ω2)ej(ω1n1+ω2n2)dω1dω2

FTC=(2π)2Cδ(ω1,ω2)

FTδ[n1,n2]=1

FTδ[n1−a,n2−b]=e−j(ω1a+ω2b)

FTej(γ1n1+γ2n2)=(2π)2δ(ω1−γ1,ω2−γ2)

cos⁡(θ)=12(ejθ+e−jθ)

x∗h↔XH

x[n1,n2]↔X(−ω1,−ω2)

x[n]=xc(nT)

ω=ΩT

Ωs=2πT

Ωmax<πT

X(ω)=∑kXc(ω−2πk)(T=1)

xc(t)=∑nx[n]sinc(t−nTT)

X[k]=∑n=0N−1x[n]e−j2πkn/N

x[n]=1N∑k=0N−1X[k]ej2πkn/N


⭐ Fast Recognition Rules