86
Hình 6.4 Bước đầu tiên của lưu đồ FFT.
Hình 6.5 giới thiệu sơ đồ thuật toán FFT cho N = 16. Chú ý rằng do yêu cầu
ban đầu của chương trình mà dãy vào được sắp xếp lại và chứa ở X(k), ví dụ
x(q) X(k)
k = 0 đến 15
Bạn sẽ chú ý trên sơ đồ rằng q là giá trị bit của k.
Cho N = 24 = 16 chúng ta phải có bốn bước trong lưu đồ. Trong mỗi bước cần
phải có tám bướm. Trong mỗi bướm chỉ có một phép nhân phức, hai phép cộng
hoặc trừ phức. Tổng số phép nhân phức là 8/2 . 4. Tổng quát cho N = 2r số phép
nhân phức là (N/2) . r = (N/2 ) log2 N và số phép cộng là Nlog2N. Chú ý, thực tế
số phép nhân sẽ giảm xuống một ít, vì trong bước đầu tiên hệ số xoay W0 = 1 và
trong các bước còn lại chúng ta cũng có các bướm với hệ số xoay = 1.
Xem xét trường hợp N = 1024 = 210. Số phép nhân cần dùng cho FFT là
(N/2).10 = 1024 5 = 5120 so với 1 triệu phép nhân cho tính trực tiếp biến đổi
DFT, đây là phương pháp tiết kiệm thực sự cho tính toán.
Bây giờ, chúng ta sẽ vạch ra thuật toán FFT. Đó không đơn thuần chỉ là sự phát
triển một chương trình từ lưu đồ. Tuy nhiên, chúng ta có thể nghiên cứu lưu đồ và
vạch ra các bước có thể dùng để phát triển một chương trình. Từ lưu đồ của hình
6.5 chúng ta có thể viết:
Bước thứ nhất. Trong bước này ta có tám bướm với trọng lượng (hệ số xoay)
W0 = 1. Chúng ta có thể viết (xem hình 6.6)
for (j=0 đến 15 với bước tăng 2)
{
T=X(j+1);
X(j+1)=X(j) - T;
X(j)=X(j) + T;
}
Bước thứ hai. Chúng ta có:
1.Bốn bướm với trọng lượng bằng 1.
for (j=0 đến 15 với bước tăng 4)
87
{
T=X(j);
X(j+2)=X(j) - T;
X(j)=X(j) + T;
}
2. Bốn bướm với trọng lượng W4 = W(3). Chú ý rằng chúng ta coi rằng các hệ
số xoay W, W2 , ... , W7 đã được tính và được chứa trong W(0), W(1), ...W(6).
for (j=0 đến 15 với bước tăng 4)
{
T=X(j)W(3);X(j+2)=X(j) - T;
X(j)=X(j) + T;
}
Bước thứ ba. Chúng ta có :
1. Hai bướm với trọng lượng bằng 1.
for (j=0 đến 15 với bước tăng 8)
{
T=X(j);
X(j+4)=X(j) - T;
X(j)=X(j) + T;
}
88
Hình 6.5 Lưu đồ thuật toán thuật toán phân chia miền thời gian.
2. Hai bướm với trọng lượng bằng W (1) = W2.
for (j=1 đến 15 với bước tăng 8)
{
T=X(j)W(1);
X(j+4)=X(j) - T;
X(j)=X(j) + T;
}
0
1
2
3
4
5
6
7
0
2
4
6
0
2
4
6
0
4
0
4
0
4
0
4
0
0
0
0
0
0
0
0
0
8
4
12
2
10
6
14
1
9
5
13
3
11
7
15
0000
1000
0100
1100
0010
1010
0110
1110
0001
1001
0101
1101
0011
1011
0111
1111
0
8
4
12
2
10
6
14
1
9
5
13
3
11
7
15
0
4
8
12
2
6
12
14
1
5
9
13
3
7
11
15
0
2
4
6
8
10
12
14
1
3
5
7
9
11
13
15
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
n=0 n=0 ®Õn 1 n=0 ®Õn 3 n=0 ®Õn 7
n
W8n
W4n
W2n
W
BËc cña d·y vµo biÓu diÔn
d¹ng nhÞ ph©n
BËc cña d·y ra biÓu diÔn
d¹ng nhÞ ph©n
bíc 0 bíc 1 bíc 2 bíc 3
89
3. Hai bướm với trọng lượng bằng W(3) = W4.
for (j=2 đến 15 với bước tăng 8)
{
T=X(j)W(3);
X(j+4)=X(j) - T;
X(j)=X(j) + T;
}
Hình 6.6 (a) Bướm cho thuật toán phân chia miền tần số;(b) Một bướm đơn giản.
4. Hai bướm với trọng lượng bằng W (5) = W6 .
for (j=3 đến 15 với bước tăng 8)
{
T=X(j)W(5);
X(j+4)=X(j) - T;
X(j)=X(j) + T;
}
Bước thứ tư và là bước cuối cùng.
1.Một bướm với trọng lượng bằng 1.
T = X(0)
X(8)= X(0) - T
X(0) = X(8) +T
F(2n)
F(2n+1)
)(
10 kf
)(
11 kf
(a)
F(2n)
F(2n+1)
)(
10 kf
)(
11 kf
(b)
90
2. Một bướm với trọng lượng bằng W (0) = W.
T = X(1)W(0)
X(1+8)= X(1) - T
X(1) = X(1) +T
3. Một bướm với trọng lượng bằng W (1) = W2.
T = X(1)W(1)
X(2+8)= X(0) - T
X(2) = X(2) +T
.
.
.
8. Một bướm với trọng lượng bằng W (6) = W7.
T = X(7)W(6)
X(7+8)= X(7)-T
X(7) = X(7) +T
Các bước dẫn chúng ta đến thuật toán với N = 16.
Thuật toán
ip=1
kk=8
incr=2
cho iter=0 đến 3 trong các bước của 1
{
cho j=0 đến 15 trong các bước của incr
{
i = j + ip
T = X(j)
X(i) = X(j) - T
X(j) = X(j) +T
nếu (iter không bằng 0) thì
{
cho k=1 đến ip-1 trong các bước của 1
{
r = k*kk - 1
cho j=k đến 15 trong các bước của 15
{