Bài giảng Xử lý tín hiệu số - Chương 6: Biến đổi fourier nhanh (FFT) - Đinh Đức Anh Vũ

n (a,b)
Î Chỉ cần N ô nhớ phức (2N ô nhớ thực)
Î Tính toán tại chỗ
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 14
FFT cơ số 2
z Thứ tự chuỗi dữ liệu vào sau khi phân (v-1) lần
– Biểu diễn các chỉ số ở dạng nhị phân
– Chuỗi sau khi phân chia sẽ là lấy theo thứ tự đảo các bit
x(7)x(7)x(7)
x(3)x(5)x(6)
x(5)x(3)x(5)
x(1)x(1)x(4)
x(6)x(6)x(3)
x(2)x(4)x(2)
x(4)x(2)x(1)
x(0)x(0)x(0)
Bộ nhớPhân chiaBộ nhớ
Phân 
chiaBộ nhớ
111111111
011101110
101011101
001001100
110110011
010100010
100010001
000000000
Địa 
chỉ
Địa 
chỉ
Địa 
chỉ
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 15
FFT cơ số 2
z Phân chia theo tần số
– Phương pháp chia và trị
– M = 2, L = N/2
– Chuỗi dữ liệu nhập được sắp xếp theo cột
– Phân chia X(k) thành X(2k) và X(2k+1)
– Sau đó có thể phân chia tiếp tục mỗi X(k chẵn) và X(k lẻ) 
a
b
A = (a+b) WN’
B = (a–b)WN’-1 W N’
X(0)
X(3)
X(6)
X(5)
X(2)
X(1)
X(4)
X(7)
1
8W
2
8W
3
8W
0
8W
-1
-1
-1
-1
DFT
4 điểm
DFT
4 điểm
x(0)
x(5)
x(3)
x(6)
x(1)
x(4)
x(2)
x(7)
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 16
FFT cơ số 4
x(0)
x(1)
x(2)
x(3)
x(4)
x(5)
x(6)
x(7)
x(N-4)
x(N-3)
x(N-2)
x(N-1)
x(0) x(2) x(4)    x(N-1)
L = 4, M = N/4
N = 4v
x(4n)
x(4n+1)
x(4n+2)
x(4n+3)
l=0
l=1
l=2
l=3
m=0 m=1 m=(N/4)-1
n = 4m + l
k = (N/4)p + q
n = 0,1,,N/4-1
l,p = 0,1,2,3
m,q = 0,1,,N/4 – 1
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 17
FFT cơ số 4
[ ]


+=
+=


−=
==
==
∑
∑
=
=
)(),(
)4(),(
)1(,..,1,0
3,2,1,0
),(),(
3,2,1,0),(),(
4
4
4/
0
4/
3
0
4
qpXqpX
lmxmlx
q
l
WmlxqlF
pWqlFWqpX
N
N
N
m
mq
N
l
lplq
N
DFT N/4 điểm


















−−
−−
−−=








),3(
),2(
),1(
),0(
11
1111
11
1111
),3(
),2(
),1(
),0(
3
2
0
qFW
qFW
qFW
qFW
jj
jj
qX
qX
qX
qX
q
N
q
N
q
N
N
lp
L
L
l
M
m
mq
M
lq
N WWmlxWqpX ∑ ∑−
=
−
= 





=
1
0
1
0
),(),(
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 18
FFT cơ số 4
0
q
2q
3q
Dạng rút gọn
0
NW
q
NW
q
NW
2
q
NW
3
-j
-1
j
-1
1
-1
j
-1
-j
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 19
FFT cơ số 4
Độ phức tạp: 1 khối tính toán cần
+ 3 nhân phức
+ 12 cộng phức
N=4v
+ Tầng tính toán : v = log4N 
+ Mỗi tầng có : N/4 khối tính toán


















−
−








−
−=








),0(
),0(
),0(
),0(
1010
1010
0101
0101
010
0101
010
0101
),3(
),2(
),1(
),0(
3
2
0
qFW
qFW
qFW
qFW
j
j
qX
qX
qX
qX
q
N
q
N
q
N
N
Biểu diễn lại nhân ma trận
(3N/8)log2N : Nhân phức (giảm 25% vs FFT2)
Nlog2N : Cộng phức (bằng FFT2)
3vN/4 = (3N/8)log2N : Nhân phức (giảm 25% vs FFT2)
12vN/4 = (3N/2)log2N : Cộng phức (tăng 50% vs FFT2)
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 21
Hiện thực các giải thuật FFT
z FFT cơ số 2
– Tính toán hình bướm: (N/2)log2N lần
– Hệ số quay WNk: được tính một lần và lưu trong bảng
– Bộ nhớ: 2N nếu muốn việc tính toán được thực hiện tại chỗ
z 4N nếu muốn đơn giản hóa các tác vụ chỉ số và điều khiển; đồng thời cho phép 
chuỗi nhập và xuất theo đúng thứ tự
z IDFT
– Khác nhau cơ bản giữa việc tính DFT và IDFT là hệ số 1/N và dấu của hệ số 
pha WN
z Đảo chiều sơ đồ tính DFT, đổi dấu hệ số pha, và chia kết quả cuối cùng cho N 
→ IDFT
z DFT với số điểm khác 2v hoặc 4v → đệm thêm các số 0
z Độ phức tạp
– Tác vụ số học (nhân phức, cộng phức)
– Cấu trúc hiện thực của giải thuật (qui tắc vs bất qui tắc)
– Kiến trúc của các bộ DSPs (xử lý song song các tác vụ)
10)(1)(
1
0
−≤≤= ∑−
=
− NnWkX
N
nx
N
k
kn
N
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 22
Ứng dụng của các giải thuật FFT
z Tính DFT của 2 chuỗi thực
– x1(n) và x2(n): chuỗi thực độ dài N cần tính DFT
– Định nghĩa chuỗi x(n) = x1(n) + jx2(n) 0 ≤ n ≤ N-1
– X(k) = X1(k) + jX2(k) (tính tuyến tính của DFT)
j
nxnxnx
nxnxnx
2
)()()(
2
)()()(
*
2
*
1
−=
+= [ ] [ ]{ }
[ ] [ ]{ })()(
2
1)(
)()(
2
1)(
*
2
*
1
nxDFTnxDFTkX
nxDFTnxDFTkX
−=
+=
[ ]
[ ])()()(
)()()(
*
2
1
2
*
2
1
1
kNXkXkX
kNXkXkX
−−=
−+=
)()( ** kNXnx NDFT − →←
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 23
Ứng dụng của các giải thuật FFT
z Tính DFT của chuỗi thực 2N điểm
– g(n): chuỗi thực độ dài 2N cần tính DFT
– Tách thành 2 chuỗi x1(n) = g(2n) và x2(n) = g(2n+1) 0 ≤ n ≤ N-1
– Định nghĩa chuỗi x(n) = x1(n) + jx2(n) 0 ≤ n ≤ N-1
– X(k) = X1(k) + jX2(k) (tính tuyến tính của DFT)
[ ]
[ ])()()(
)()()(
*
2
1
2
*
2
1
1
kNXkXkX
kNXkXkX
−−=
−+=
∑∑
∑∑
−
=
−
=
−
=
+−
=
+=
++=
1
0
22
1
0
1
1
0
)12(
2
1
0
2
2
)()(
)12()2()(
N
n
nk
N
k
N
N
n
nk
N
N
n
kn
N
N
n
nk
N
WnxWWnx
WngWngkG
1,,1,0)()()(
1,,1,0)()()(
221
221
−=−=+
−=+=
NkkXWkXNkG
NkkXWkXkG
k
N
k
N
K
K
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 24
Ứng dụng của các giải thuật FFT
z Lọc tuyến tính các chuỗi dữ liệu dài
– Overlap-add
– Overlap-save
z Phương pháp
– h(n) – Đáp ứng xung đơn vị của bộ lọc (chiều dài M) 
z Được đệm thêm L-1 số không sao cho N = L + M – 1 = 2v
z H(k): DFT N điểm của h(n), theo thứ tự đảo nếu h(n) được sắp theo thứ tự thuận 
(Giải thuật FFT suy giảm theo tần số)
– xm(n) – khối dữ liệu chiều dài L (đã được phân cắt)
z Được đệm thêm M–1 điểm (giá trị tùy theo PP lọc được dùng)
z Xm(k): DFT N điểm của xm(n), cũng theo thứ tự đảo (Giải thuật FFT suy giảm 
theo tần số)
– Ym(k) = H(k)Xm(k)
z H(k) và Xm(k) cùng có thứ tự đảo → Ym(k) theo thứ tự đảo
z ym(n) = IDFTN{Ym(k)} sẽ đúng theo thứ tự thuận nếu dùng giải thuật FFT suy 
giảm theo thời gian
– Không cần thiết đảo vị trí các dữ liệu trong việc tính DFT và IDFT
z Tính tương quan (tương tự)
+ FFTDFT
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 25
Phương pháp lọc tuyến tính
z FFT không hiệu quả khi tính DFT (IDFT) tại một số điểm (< log2N) → tính trực tiếp
z Giải thuật Goertzel
– Dựa vào tính chu kỳ của WNk và biểu diễn việc tính toán DFT như lọc tuyến tính
Nnk
kn
Nk
k
N
m
mnk
Nk
N
m
mNk
N
N
m
km
N
kN
N
nykX
nuWnhvói
nhnxWmxnyĐăt
WmxWmxWkX
=
−
−
=
−−
−
=
−−−
=
−
=⇒
=
==
==
∑
∑∑
)()(
)()(
)(*)()()(
)()()(
1
0
)(
1
0
)(
1
0
11
1)( −−−= zWzH kNk
Một pole trên vòng tròn đơn vị 
tại tần số ωk=2πk/N
0)1()()1()( =−+−= − kkkNk ynxnyWny
Thay vì tính tổng chập trực tiếp, ta có thể dùng PTSP
Việc tính DFT tại một điểm k có thể 
được thực hiện bằng cách cho t/h 
đi vào bộ cộng hưởng một pole 
tại tần số ωk=2πk/N
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 26
Giải thuật Goertzel
z Kết hợp từng cặp các bộ cộng hưởng có pole liên hợp phức
z Hiện thực bằng dạng chuẩn tắc (dạng II)
– Với đ/k đầu
z vk(n) được lặp lại cho n = 0, 1, , N
– Mỗi vòng cần 1 phép nhân thực
z yk(n) được tính duy nhất một lần cho n = N
z Nếu x(n) là t/h thực, cần N+1 phép nhân thực để tính X(k) và X(N-k) {do tính 
đối xứng}
z Giải thuật Goertzel chỉ thích hợp khi số giá trị DFT cần tính khá nhỏ (≤ log2N)
NnnvWnvny
Nnnxnvnvnv
k
k
Nkk
kkN
k
k
=−−=
=+−−−=
)1()()(
,...,1,0)()2()1(cos2)( 2π
0)2()1( =−=− kk vv
21
1
)/2cos(21
1)( −−
−−
+−
−=
zzNk
zWzH
k
N
k π
+
+
)cos(2 2Nkπ
z-1
z-1
+
k
nW
-1
yk(n)x(n) –
vk(n)
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 27
Giải thuật BĐ Chirp-z
z DFT N điểm ~ X(zk) với zk = ej2πkn/N , k=0,1,,N-1 (các điểm cách đều trên 
vòng tròn đơn vị)
z BĐ Z của x(n) tại các điểm zk
z Nếu zk = rej2πkn/N (zk là N điểm cách đều nhau trên vòng tròn bk r)
– Việc tính DFT có thể được thực hiện bằng giải thuật FFT cho chuỗi x(n)r-n
z Tổng quát, zk nằm trên cung xoắn ốc bắt đầu từ điểm (đi vào hoặc 
đi ra gốc tọa độ)
1,...,1,0)()(
1
0
−==∑−
=
− LkznxzX
N
n
n
kk
1,...,1,0])([)(
1
0
/2 −==∑−
=
−− NkernxzX
N
n
Nknjn
k
π
0
00
θjerz =
1,,1,0)( 00 00 −== LkeRerz kjjk Kφθ
R0 = r0 = 1
Φ0 = θ0 = 0
Vòng tròn
đơn vị
Im(z)
Re(z)
r0
R0 = 1, r0 < 1
Φ0 = θ0 = 0
Im(z)
Re(z)
R0 > 1
Im(z)
Re(z)
R0 < 1
Im(z)
Re(z)
θ0
r0
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 28
Giải thuật BĐ Chirp-z
1,,1,0)()()(
))(()(
)(
1,,1,0
)(
)()(
1
0
2/
0
2/
0
2
0
2
0
−=−=
=
=
=
−==
∑−
=
−−
Lknkhngky
Vernxng
Vnh
eRV
Lk
kh
kyzX
N
n
nnj
n
j
k
K
K
θ
φ
njnnjnj eeenhR ωφφ ≡==⇒= )2/(2/0 020)(1
2/0φω n= Tần số của t/h mũ phức h(n), tăng tuyến tính theo thời gian
→ h(n): chirp signal
BĐ chirp-z
Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM
Bài Giảng Môn: Xử Lý Tín Hiệu Số
Slide 29
Giải thuật BĐ Chirp-z
z Xác định tổng chập vòng của chuỗi g(n) N điểm và chuỗi h(n) M điểm (M > N)
– N-1 điểm đầu là các điểm lặp lại
– M-(N-1) điểm còn lại chứa kết quả
z Giả sử M = L + (N-1)
z M điểm của chuỗi h(n) được xác định –(N–1) ≤ n ≤ (L–1)
z Định nghĩa chuỗi M điểm h1(n) = h(n–N+1) n = 0,1,,M–1
z H1(k) = DFTM{h1(n)}
z G(k) = DFTM{g(n)} (sau khi đã đệm thêm vào g(n) L-1 số 0)
z Y1(k) = G(k)H(k) → y1(n) = IDFT{Y1(k)} n = 0,1,,M–1
z N-1 điểm đầu tiên của y1(n) là các điểm lặp → loại bỏ chúng
z Các điểm kết quả là giá trị của y1(n) khi N-1 ≤ n ≤ M–1
– y(n) = y1(n+N-1) n = 0,1,,L-1
z X(zk)= y(k)/h(k) k = 0,1,,L-1
1,,1,0)()()(
1
0
−=−=∑−
=
Lknkhngky
N
n
K