Bài giảng Xử lý số tín hiệu - Chương 8: Biến đổi DFT và FFT

Xử lý số tín hiệu

Chương 8: Biến đổi DFT và FFT

Các phép biến đổi Fourier

Miền thời gian

Miền tần số

2.5

2

1.5

1

T

0.5

0

1

−jkω t

Periodic

(period T)

^ck^{= }^s(t)e

dt

0

1

2

3

4

5

6

7

8

FS

Discrete

time, t

T

0

Continuous

2.5

2

−j2 π f t

+

−

1.5

1

S(f) =

s(t)e

dt

Aperiodic FT

Continuous



0.5

0

2

4

6

8

10

12

time, t

2πkn

2.5

2

N−1

_N_n₌₀

−j

1

~

1.5

1

N

c =

s[n] e

k

Periodic DFS

(period T)

Discrete

0.5

0

1

2

3

4

5

6

7

8

time, t

k

+

−j2πfn

Discrete

S(f) =

s[n] e



DTFT Continuous

2.5

2

1.5

1

n=−

N−1

Aperiodic

2πkn

0.5

0

−j

1

~

N

DFT

0

2

4

6

8

10

12

c =

s[n] e

_N_n₌₀

k

time, t

Discrete

k

Chuỗi Fourier (Fourier series-FS)

⚫ Tín hiệu x(t) tuần hoàn, chu kỳ T_p, tần số F₀= 1/T_p

+

x(t) = c e ^{j2kF t}

0



k

k=−

1

c_k= x(t)e^{− j2kF}⁰^tdt

T_p



T_p

X(f)

x(t)

τ

f

t

-F₀F₀

0

T_p

-T_p

Biến đổi Fourier (Fourier transform-FT)

⚫ Tín hiệu x(t) không tuần hoàn

+

(

F

)

e^j2ftdf

^{x(t) =} ^X

+

−

− j2ft

( ) ( )

^{X f =}^{x t e dt}

−

X(ω)

x(t)

ω

t

-τ/2 τ/2

-2π/τ

2π/τ

Biến đổi Fourier của một số tín hiệu cơ bản

Biến đổi Fourier thời gian rời rạc

Discrete – Time Fourier Transform (DTFT)

⚫ Tín hiệu x(n) rời rạc, không tuần hoàn

1

2

jn

( )

x(n) = X  e d



2

+

jn

( ) ( )

X  = x n e



n=−

Chuỗi Fourier rời rạc

Discrete Fourier Sequence (DFS)

⚫ Tín hiệu x(n) rời rạc, tuần hoàn với chu kỳ N

N −1

x(n) = c e ^{j2kn / N}



k

k=0

N −1

1

− j2kn / N

( )

c = x n e

_N

k

n=0

Biến đổi Fourier rời rạc

Discrete Fourier Transform (DFT)

⚫ Tín hiệu x(n) rời rạc, không tuần hoàn, chiều dài L hữu

hạn ➔ Biến đổi DTFT cho phổ liên tục X(ω)

|X(ω)|

x(n)

0

L-1

n

-π

π ω

Biến đổi Fourier rời rạc

Discrete Fourier Transform (DFT)

⚫ Lặp lại tín hiệu x(n) với chu kỳ N ≥ L ➔ Tín hiệu x_p(n)

tuần hoàn chu kỳ N

x_p(n)

N-1 N

0

L-1

n

Biến đổi Fourier rời rạc

Discrete Fourier Transform (DFT)

⚫ x_p(n) tuần hoàn chu kỳ N ➔ Tính DFS của x_p(n) → X_p(k)

x_p(n)

L-1

N-1

N

0

n

|X_p(k)|

-N

0

N

k

Biến đổi Fourier rời rạc

Discrete Fourier Transform (DFT)

X_p(k) tuần hoàn chu kỳ N ➔ Đặt X(k) = X_p(k), k = 0,..,N-1

x(n)

0

L-1

n

|X(k)|

DFT

0

N-1

k

Biến đổi Fourier rời rạc

Discrete Fourier Transform (DFT)

Công thức biến đổi DFT N-điểm cho chuỗi chiều dài L:

L−1

DFT

− j2kn / N

( )

X (k) = x n e

, k = 0,1,2,..., N −1

, n = 0,1,2,..., N −1



n=0

N −1

1

j2kn / N

IDFT

( )

x n =

( )

X k e

_N

k=0

Giải thuật biến đổi Fourier nhanh

Fast Fourier Transform (FFT)

⚫ Tính trực tiếp DFT N – điểm của x(n):

Tổng quát: X(k) và x(n) là số phức:

^{N −1}



2kn

( )

X k = x n cos + x n sin

_

R

I





N

_n=0

^{N −1}

2kn



( )

− x_In cos

X k = − x n sin

_

I

R





N

_n=0

Tính trực tiếp cần:

• 2N²phép tính hàm lượng giác

• 4N²phép nhân thực

Chi phí tí nh

toán lớn

• 4N(N-1) phép cộng thực

Giải thuật biến đổi Fourier nhanh

Fast Fourier Transform (FFT)

W_N= e^{− j2 / N}

⚫ Đặt

N −1

nk

( )

X k = x(n)W

➔



N

n=0

W_M^{k+N /2}= −W_N^k

⚫ Tính đối xứng:

⚫ Tính tuần hoàn:

k+N

k

W_M=W_N

Giải thuật biến đổi Fourier nhanh

Fast Fourier Transform (FFT)

⚫ Xét chuỗi x(n) = {x(0), x(1)}

➔ FFT 2 điểm của x(n):

X(0) = x(0)W₂⁰+ x(1)W₂⁰= x(0) + x(1)

X(1) = x(0)W₂⁰+ x(1)W₂¹= x(0) − x(1)

=

(Lưu ý: W₂1)

x(0)

X(0)

1 Bướm

(Butterfly)

x(1)

X(1)

-1

Giải thuật FFT phân chia theo thời gian

(Decimation in time – DIT)

⚫ Xét chuỗi x(n) có chiều dài N = 2^K

⚫ Đặt g(n) = x(2n) → g(n) = {x(0), x(2), … }

⚫ Đặt h(n) = x(2n + 1) → h(n) = {x(1), x(3), …}

⚫ DFT N điểm của x(n):

N

k

X (k) = G(k) +W _NH(k) , k = 0,1,..., −1

2

N

k−

N

2

N

X (k) = G(k − ) −W H(k − ) , k = ,..., N −1

2

⚫ G(k), H(k) : DFT N/2 điểm của g(n), h(n)

Giải thuật FFT phân chia theo thời gian

g(0)

g(1)

G(0)

G(1)

X(0)

X(1)

W_N⁰

W_N¹

k =0

→

N/2 -1

FFT N/2

điểm

g(N/2 -1)

G(N/2 -1)

X(N/2-1)

X(N/2)

W_N^{N / 2−1}

−W_N⁰

−W_N¹

h(0)

h(1)

H(0)

H(1)

X(N/2 + 1) k = N/2

→

N - 1

FFT N/2

điểm

−W_N^{N / 2−1}

h(N/2 -1)

H(N/2 -1)

X(N – 1)

Chi phí tí nh toá n

⚫ So với tính trực tiếp: chi phí tính toán thấp hơn

2000

1500

1000

500

0

DFT  N²

FFT  N log₂N

0

10

20

30

40

Number of samples, N

Ví dụ

⚫ FFT 8 điểm phân chia theo thời gian

Ví dụ

⚫ FFT 8 điểm phân chia theo thời gian