Bài giảng Digital signal processing - Chương 6: Giải thuật cho biến đổi Fourier (FFT) - Đinh Đức Anh Vũ

BK
TP.HCM
2011
dce
Chương 6
Giải thuật cho biến đổi Fourier 
(FFT)
©2011, TS. Đinh Đức Anh Vũ
2011
dce
2DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Nội dung
Tính
DFT & IDFT
Tính
trực tiếp
Biến đổi
WN
Chia-Trị
Cơ số 2 Cơ số 4 Tách cơ số
Lọc
tuyến tính
Goertzel Chirp-z
2011
dce
3DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
• Tính DFT: xác định chuỗi N giá trị phức {X(k)} khi biết trước chuỗi {x(n)} 
chiều dài N
– Giải thuật tính DFT cũng được áp dụng cho việc tính IDFT
• Tính trực tiếp
– N2 phép nhân phức
– N(N-1) phép cộng phức
→ Độ phức tạp : O(N2)
• Biến đổi WN
– 2N2 phép tính lượng giác
– 4N2 phép nhân số thực
– 4N(N-1) phép cộng số thực
– Một số phép toán chỉ số 
và địa chỉ để nạp x(n)
DFT & IDFT
10)()(
1
0
−≤≤=∑
−
=
NkWnxkX
N
n
kn
N
10)(1)(
1
0
−≤≤= ∑
−
=
− NnWkX
N
nx
N
k
kn
N
DFT
IDFT






−−=
+=
∑
∑
−
=
−
=
1
0
22
1
0
22
)]cos()()sin()([)(
)]sin()()cos()([)(
N
n
N
kn
IN
kn
RI
N
n
N
kn
IN
kn
RR
nxnxkX
nxnxkX
ππ
ππ
Giải thuật tính DFT tối ưu mỗi phép toán 
theo những cách khác nhau
/2k N k
N N
k N k
N N
W W
W W
+
+
= −
=
Doi xung
Tuan hoan
2011
dce
4DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Phương pháp chia-trị (1)
• Nguyên tắc: phân rã nhỏ việc tính DFT N điểm thành việc tính các DFT kích thước
nhỏ hơn → các giải thuật FFT
• Phương pháp
– Giả sử N=L.M
– Lưu trữ x(n) vào mảng 2 chiều L × M (l: chỉ số hàng, m: chỉ số cột)
– Cách lưu trữ
• Theo dòng n = Ml + m
• Theo cột n = l + mL
– Tương tự, các giá trị DFT X(k) tính được cũng sẽ được lưu trữ trong ma trận L × M 
(p: chỉ số hàng, q: chỉ số cột)
• Theo dòng k = Mp + q
• Theo cột k = p + qL
0 1 2  N-1
x(0) x(1) x(2)  x(N-1)
l
m 0 1  M-1
0 x(0,0) x(0,1)  x(0,M-1)
1 x(1,0) x(1,1)  x(1,M-1)
2 x(2,0) x(2,1)  x(2,M-1)
L-1 x(L-1,0) x(L-1,1)  x(L-1,M-1)
n →
2011
dce
5DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Phương pháp chia-trị (2)
∑∑
−
=
−
=
++=
1
0
1
0
))((),(),(
M
m
L
l
lmLqMp
NWmlxqpX
lq
N
Mpl
N
mLq
N
MLmp
N
lmLqMp
N WWWWW =
++ ))((
Với:
x(n) : theo cột
X(k) : theo hàng
pl
L
pl
MN
Mpl
N
mq
M
mq
LN
mqL
N
Nmp
N
WWW
WWW
W
==
==
=
/
/
1
lp
L
L
l
M
m
mq
M
lq
N WWmlxWqpX ∑ ∑
−
=
−
= 











=
1
0
1
0
),(),(
10)()(
1
0
−≤≤=∑
−
=
NkWnxkX
N
n
kn
N
DFT M điểm
F(l,q)
G(l,q)
DFT L điểm
X(p,q)
1
2
3
(1): Tính L DFT M điểm
Nhân phức : LM2
Cộng phức : LM(M-1)
(2): Tính G(l,q)
Nhân phức : LM 
(3): Tính X(p,q)
Nhân phức : ML2
Cộng phức : ML(L-1)
 Độ phức tạp 
Nhân phức : N(M+L+1)
Cộng phức : N(M+L-2)
2011
dce
6DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Phương pháp chia-trị (3)
• Hiệu quả
• PP chia-trị rất hiệu quả khi N= r1r2r3rv
– Phân rã nhỏ hơn đến (v-1) lần
• Giải thuật
PP tính trực tiếp
• Nhân phức : N2
• Cộng phức : N(N-1)
PP chia-trị
• Nhân phức : N(M+L+1)
• Cộng phức : N(M+L-2)
N=1000 → L=2, M=500
106 nhân phức → 503,000 (~ N/2)
1. Lưu trữ t/h theo hàng
2. Tính DFT L điểm của mỗi cột
3. Nhân ma trận kết quả với hệ số pha WNpm
4. Tính DFT M điểm của mỗi hàng
5. Đọc ma trận kết quả theo cột
Giải thuật 2
n = Ml + m
k = qL + p
1. Lưu trữ t/h theo cột
2. Tính DFT M điểm của mỗi hàng
3. Nhân ma trận kết quả với hệ số pha WNlq
4. Tính DFT L điểm của mỗi cột
5. Đọc ma trận kết quả theo hàng
Giải thuật 1
n = l + mL
k = Mp + q
2011
dce
7DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Phương pháp chia-trị (4)
• Mô hình tính toán DFT 6 điểm thông qua việc tính DFT 3 điểm và DFT 2 điểm
• Giải thuật tính FFT cơ số 2
– Nếu N = r1r2r3rv = rv → mô hình tính DFT có cấu trúc đều (chỉ dùng 1 DFT r điểm)
– r = 2 → FFT cơ số 2
– Chọn M = N/2 và L = 2
x(5)
x(3)
X(5)
X(4)
D
FT
 2
 đ
iể
m
x(0)
x(2)
x(4)
x(1)
W6lq
X(0)
X(1)
X(2)
X(3)
x(1) x(3) x(N-1)
x(0) x(1) x(2)  x(N-1)
x(0) x(2) x(N-2)l=0
l=1
m=0 m=1 m=M-1
f1(2n)
f2(2n+1)
n= 0,1, , N/2-1
Giải thuật 
chia theo thời gian
2011
dce
8DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
FFT cơ số 2 (1)
∑∑
∑∑
∑
−
=
+
−
=
−
=
++=
+=
−==
1)2/(
0
)12(
1)2/(
0
2
1
0
)12()2(
)()(
1,...,1,0)()(
N
m
mk
N
N
m
mk
N
oldn
kn
N
evenn
kn
N
N
n
kn
N
WmxWmx
WnxWnx
NkWnxkX
2/
2
NN WW =
1,...,1,0)()(
)()()(
21
2/
1)2/(
0
22/
1)2/(
0
1
−=+=
+= ∑∑
−
=
−
=
NkkFWkF
WmfWWmfkX
k
N
km
N
N
m
k
N
km
N
N
m
2/,...,1,0)()(
2/,...,1,0)()(
22
11
2/
2/
NkkFmf
NkkFmf
N
N
DFT
DFT
= →←
= →←
k
N
Nk
N WW −=
+ 2/
F1(k), F2(k) tuần hoàn 
chu kỳ N/2
F1(k+ N/2) = F1(k)
F2(k+ N/2) = F2(k)




−=−=+
−=+=
1,..,1,0)()()(
1,..,1,0)()()(
2212
221
Nk
N
N
Nk
N
kkFWkFkX
kkFWkFkX
2011
dce
9DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
FFT cơ số 2 (2)




−==
−==
1,..,1,0)()(
1,..,1,0)()(
222
211
Nk
N
N
kkFWkG
kkFkG



−=−=+
−=+=
1,...,1,0)()()(
1,...,1,0)()()(
2212
221
NN
N
kkGkGkX
kkGkGkX
DFT2
X(k)
G2(k)
G1(k)
k=0,1,,(N/2-1)
X(k+ N/2)
DFT 
2 điểm
DFT 
2 điểmDFT 
2 điểmDFT 
2 điểm
2011
dce
10DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
• Tiếp tục phân f1(n) và f2(n) thành các chuỗi N/4 điểm
• Hiệu quả
FFT cơ số 2 (3)







−=+=
−==
−=+=
−==
1,...,1,0)12()(
1,...,1,0)2()(
1,...,1,0)12()(
1,...,1,0)2()(
4222
4221
4112
4111
N
N
N
N
nnfnv
nnfnv
nnfnv
nnfnv







−=−=+
−=+=
−=−=+
−=+=
1,...,1,0)()()(
1,...,1,0)()()(
1,...,1,0)()()(
1,...,1,0)()()(
4222/2142
4222/212
4122/1141
4122/111
Nk
N
N
Nk
N
Nk
N
N
Nk
N
kkVWkVkF
kkVWkVkF
kkVWkVkF
kkVWkVkF
DFT 
N/4 điểm
vij(n) Vij(k)
DFT trực tiếp N=2v điểm
FFT cơ số 2
Các DFT 2 điểm
Nhân phức: N2
Cộng phức: N2 – N
Nhân phức: (N/2)log2N
Cộng phức: Nlog2N
2011
dce
11DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
FFT cơ số 2 (4)
• Ví dụ: tính DFT 8 điểm
x(0) x(2) x(4) x(6)
x(1) x(3) x(5) x(7)
x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7)
x(0)
x(2)
x(4)
x(6)
x(1)
x(3)
x(5)
x(7)
Phân theo thờ
i gian
[0,1,2,3,4,5,6,7]
[0,2,4,6] [1,3,5,7]
[0,4] [2,6] [1,5] [3,7]
2011
dce
12DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
FFT cơ số 2 (5)
• Khối tính toán cơ bản cho DFT 2 điểm (hình con bướm)
W N’
a
b
A = a+WN’b
B = a–WN’b
–1
Độ phức tạp
• 1 nhân phức
• 2 cộng phức
N= 2v:
+ Log2N : tầng tính toán
+ N/2 : khối tính toán cơ bản cho mỗi lớp
Bộ nhớ:
+ Vào : (a,b) – số phức
+ Ra : (A,B) – số phức
+ Có thể lưu (A,B) đè lên (a,b)
 Chỉ cần N ô nhớ phức (2N ô nhớ thực)
 Tính toán tại chỗ
2011
dce
13DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
0
8W
0
8W
0
8W
0
8W
-1
-1
-1
-1
0
8W
2
8W
0
8W
2
8W
-1
-1
-1
-1
0
8W
1
8W
2
8W
3
8W
-1
-1
-1
-1
X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
x(0)
x(4)
x(2)
x(6)
x(1)
x(5)
x(3)
x(7)
FFT cơ số 2 (6)
2011
dce
14DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Baseline Parallel Architecture
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Parallel FFT 
 Butterfly structure
 Removes redundant 
calculation
Size 16 8192 ∆
Pins 448 229K
Fly 32 53K
Mult
Add
Shift 0 0
2011
dce
15DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Parallel-Pipelined Architecture
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Size 16 8192 ∆
Pins 448 229K
Fly 32 53K
Mult 96 159K
Add 288 480K
Shift 0 0
A pipelined version 
 IO Bound
 100% Efficient
2011
dce
16DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Địa 
chỉ
Phân 
chia
Địa 
chỉ
Phân 
chia
Địa 
chỉ
000 000 000
001 010 100
010 100 010
011 110 110
100 001 001
101 011 101
110 101 011
111 111 111
FFT cơ số 2 (7)
• 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
Bộ
nhớ
Bộ 
nhớ
Bộ
nhớ
x(0) x(0) x(0)
x(1) x(2) x(4)
x(2) x(4) x(2)
x(3) x(6) x(6)
x(4) x(1) x(1)
x(5) x(3) x(5)
x(6) x(5) x(3)
x(7) x(7) x(7)
2011
dce
17DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
FFT cơ số 2 (8)
• 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)
2011
dce
18DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
FFT cơ số 4 (1)
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
2011
dce
19DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
FFT cơ số 4 (2)
[ ]



+=
+=



−=
=
=
==
∑
∑
=
=
)(),(
)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
),(),(
2011
dce
20DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
FFT cơ số 4 (3)
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
0
q
2q
3q
2011
dce
21DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
FFT cơ số 4 (4)


























−
−












−
−
=












),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
Độ 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
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)
2011
dce
22DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Hiện thực các giải thuật FFT
• 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ỗ
• 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ự
• 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
• Đả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
• DFT với số điểm khác 2v hoặc 4v → đệm thêm các số 0
• Độ 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
2011
dce
23DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Ứng dụng của các giải thuật FFT
• 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 − →←
2011
dce
24DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Ứng dụng của các giải thuật FFT
• 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


2011
dce
25DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Ứng dụng của các giải thuật FFT
• Lọc tuyến tính các chuỗi dữ liệu dài
– Overlap-add
– Overlap-save
• Phương pháp
– h(n) – Đáp ứng xung đơn vị của bộ lọc (chiều dài M) 
• Được đệm thêm L-1 số không sao cho N = L + M – 1 = 2v
• 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)
• Được đệm thêm M–1 điểm (giá trị tùy theo PP lọc được dùng)
• 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)
• H(k) và Xm(k) cùng có thứ tự đảo → Ym(k) theo thứ tự đảo
• 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
• Tính tương quan (tương tự)
+ FFTDFT
2011
dce
26DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Phương pháp lọc tuyến tính
• 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
• 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)( −−−
=
zW
zH k
N
k
Một pole trên vòng tròn đơn vị 
tại tần số ωk=2πk/N
0)1()()1()( =−+−= − kk
k
Nk 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
2011
dce
27DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Giải thuật Goertzel
• Kết hợp từng cặp các bộ cộng hưởng có pole liên hợp phức
• Hiện thực bằng dạng chuẩn tắc (dạng II)
– Với đ/k đầu
• 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
• yk(n) được tính duy nhất một lần cho n = N
• 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}
• 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)
2011
dce
28DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Giải thuật BĐ Chirp-z (1)
• 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ị)
• BĐ Z của x(n) tại các điểm zk
• 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
• 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 toạ độ)
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
kjj
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
2011
dce
29DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Giải thuật BĐ Chirp-z (2)
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


θ
φ
njnnjnj eeenhR ωφφ ≡==⇒= )2/(2/0 0
2
0)(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
2011
dce
30DSP – Giải thuật cho Biến đổi Fourier ©2011, Đinh Đức Anh Vũ
Giải thuật BĐ Chirp-z (3)
• 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ả
• Giả sử M = L + (N–1)
• M điểm của chuỗi h(n) được xác định –(N–1) ≤ n ≤ (L–1)
• Định nghĩa chuỗi M điểm h1(n) = h(n–N+1) n = 0,1,,M–1
• H1(k) = DFTM{h1(n)}
• G(k) = DFTM{g(n)} (sau khi đã đệm thêm vào g(n) L-1 số 0)
• Y1(k) = G(k)H(k) → y1(n) = IDFT{Y1(k)} n = 0,1,,M–1
• N-1 điểm đầu tiên của y1(n) là các điểm lặp → loại bỏ chúng
• 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
• X(zk)= y(k)/h(k) k = 0,1,,L–1
1,,1,0)()()(
1
0
−=−=∑
−
=
Lknkhngky
N
n
