76





1
0
¦)()(
N
n
nk
N
WkfnF
(6.6)
ở đây f(k) = f(kT) và W
N
= e
- j2 /N
.
W
N
được gọi là hạt nhân của phép biến đổi.
Tổng quát, F(n) có dạng

)(
)()(

(6.8)
Chứng minh: Từ định nghĩa của DFT

 
 




















1
0
1
0
)(

Wmf
N
WWmf
N
WnF
N
(6.9)
Đặt





1
0
)(
N
n
mkn
N
WS

Nếu (k = m) thì S = N.
Nếu (k

m), chúng ta có thể viết:
S = 1 + W
N

(k -m )









Khi e
j2

(k-m)
= 1 và e
j2

/N. (k-m)
 1 với (k  m), vì vậy S = 0 với (k  m ).

Vì vậy, biểu thức (6. 9) có thể rút gọn thành

77

f(k).N
1
)(
1
1
0
N
WnF

2
kf
enF
N
enF
N
N
n
nk
N
j
N
n
Nkn
N
j












(6.10)
Mặc dù f(k) được xác định trên miền k


nk
N
j
N
k
nk
N
j
N
k
N
N
j
N
k
nNk
N
eekf
eekf
WkfnNF










Nếu f(k) là thực thì

















)()()(
1
0
.
2
nFekfnNF
N
k
nk
N
j


kn
N
WkfnF
)()(
1
0
2222
2
22





N
k
kn
N
WkfnF
và tại các vị trí n
1
= n
2
= n

Đặt f
3
(k) = IDFT của F
1
(n).F













  














1
0
)(

nk
N
N
n
N
k
N
k
kkn
N
3
W
N
kfkf
WWkfkf
N
(k)f W =
.=
2
n-
N
2
1
11
1
2
22

Wkfkf
WkfWkfnFnF














79

Chú ý là









0
1

theo biểu thức trên là 2N - 1. Kết quả này chứng minh rằng trong DFT, tín hiệu có
số mẫu lớn hơn N sẽ được biến đổi thành dãy tuần hoàn có chu kỳ N. Khi dùng
DFT cho một tín hiệu không có chu kỳ, mà kết quả thu được từ tích hai dãy, ta sẽ
phạm một sai lầm gọi là lỗi wraparound. Đó là lý do ta phải làm cho cả hai dãy
có chu kỳ bằng nhau. Để sửa lỗi này, một số số 0 cần phải thêm vào cả hai dãy để
chiều dài hai dãy bằng nhau. Ví dụ, nếu một dãy có chiều dài A, một dãy có chiều
dài B, kết quả ta phải thêm các số 0 cho cả hai dãy có chiều dài ít nhất là A
+ B - 1.

Bài tập 6.1
Cho hai dãy sau





0
1
)(
1
kf




0
1


k
1

4
các trường hợp còn lại.
0

k
1

5
các trường hợp còn lại.

80

6.3 Thuật toán biến đổi nhanh Fourier
Tính trực tiếp giá trị của DFT bao gồm N phép nhân phức và N - 1 phép cộng
phức cho mỗi giá trị của F(n). Khi N giá trị được tính toán thì N
2
phép nhân và
N(N - 1) phép cộng được tính toán. Cũng như vậy, cho N có giá trị rất lớn, tính
trực tiếp giá trị của DFT sẽ đòi hỏi một số phép tính lớn đến mức không thể chấp
nhận được. Để ví dụ, cho N = 1024 = 2
10
ta sẽ phải tính 2
20
= 1,048,576 phép
nhân số phức và một số gần bằng như vậy các phép cộng.
Hoàn thiện có nghĩa là phải giảm số phép tính trong biến đổi Fourier xuống.






15
0
16
15
0
16
)()()(
k
nk
k
nk
WkfWkfnF

k chẵn k lẻ
Chúng có thể viết thành








8
.
8
2
)2(.
16
2
)2(
16


vì thế






7
0
816
7
0
8
)12()2()(
k
nkn
k
nk
WkfWWkfnF





7
0
81010
)()(
k
nk
WkfnF
(6.17)





7
0
81111
)()(
k
nk
WkfnF
(6.18)
Viết lại biểu thức (6.16) chúng ta được
(n)FW (n)F F(n)
11
-n
1610







7
0
4108
3
0
41010
)12()2()(
k
nkn
k
nk
WkfWWkfnF82

Dễ thấy

-2n
16
-n
8
WW 

F
11
(n) F(n+8)
F
10
(n) F(n)

F
11
(n) F(n+8)
1
W
16

21
-2n
162010
 (6.21)
(n)FW - (n)F 4)(nF
21
-2n
162010
 (6.22)
ở đây




3
0
42020
)()(
k
nk
WkfnF (6.23)





3
0
42121
)()(

2
3
4
5
6
7
0
1
2
3
4
5
6
7

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14


1)(2kf (k)f
1123

Biểu thức (6.21), (6.22), (6.25) và (6.26) có thể biểu diễn bằng sơ đồ hình 6.3.
Biểu thức (6.23), (6.24), (6.27) và (6.28) có thể tiếp tục chia nhỏ ra như các bước
đã làm ở trên như sau:
(n)FW (n)F (n)F
31
-4n
163020
 (6.29)
(n)FW - (n)F 2)(nF
31
-4n
163020
 (6.30)
(n)FW (n)F (n)F
33
-4n
163221
 (6.31)
(n)FW - (n)F 2)(nF
33
-4n
163221
 (6.32)
(n)FW (n)F (n)F
35
-4n

F n f k W
nk
k
31 31 2
0
3
( ) ( )



(6.38)
, vv.

Các biểu thức từ (6.29) đến (6.36) cho kết quả trong bước thứ ba của thuật toán
và biểu diễn trong lưu đồ hình 6.4.Mỗi phần tử từ F
30
(n) đến F
37
(n) có thể chia
tiếp thành hai phần tử nữa và bước này tạo thành sơ đồ cuối cùng (bước đầu tiên)
trong lưu đồ.
0
1
2
3
0
1


85 Hình 6.3 Bước thứ hai sau bước cuối cùng trong thuật toán FFT.


0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0

0
F
30
(n)
F
31