Bài giảng Xử lý số tín hiệu - Chương 4: Biểu diễn tín hiệu và hệ thống trong miền tần số rời rạc

BIỂU DIỄN TÍN HIỆU VÀ HỆ THỐNG TRONG MIỀN 
TẦN SỐ RỜI RẠC
4.1 KHÁI NIỆM
4.2 CHUỖI FOURIER RỜI RẠC (DFS)
4.3 BIẾN ĐỔI FOURIER RỜI RẠC (DFT)
4.4 BIẾN ĐỔI FOURIER NHANH (FFT)
Chương 4:
1
4.1 KHÁI NIỆM
 X(ej) có các hạn chế khi xử lý trên thiết bị, máy tính:
Tần số  liên tục 
Độ dài x(n) là vô hạn: n biến thiên -∞ đến ∞
Biến đổi Fourier dãy x(n): j j n
n
X ( e ) x( n )e 
 
Khi xử lý X(ej) trên thiết bị, máy tính cần:
 Rời rạc tần số  -> K
 Độ dài x(n) hữu hạn là N: n = 0  N -1
 Biến đổi Fourier của dãy có độ dài hữu hạn theo tần
số rời rạc, gọi tắt là biến đổi Fourier rời rạc – DFT
(Discrete Fourier Transform)
2
4.2 CHUỖI FOURIER RỜI RẠC CỦA TÍN HIỆU 
TUẦN HOÀN (DFS)
x( n ) x( n lN )  
 Xét tín hiệu tuần hoàn với chu kỳ N:x( n )
 Xét hàm mũ phức tuần hoàn với chu kỳ N:
2 2
2 2
j ( n rN )k j nk
N N
k k
j ( k lN )n j nk
N N
k lN k
e ( n rN ) e e e ( n )
e ( n ) e e e ( n )
2
j nk
N
ke ( n ) e
Khi đó tín hiệu tuần hoàn được biểu diễn bởi tổng các 
hàm mũ phức. 
x( n )
3
 Tín hiệu tuần hoàn có thể biểu diễn bởi một chuỗi 
Fourier dưới dạng:
21
0
1 N j nk
N
k
x( n ) X ( k )e
N
  
x( n )
2 2 21
0
1
Nj mn j nk j mn
N N N
k
x( n )e X( k )e e
N
  
2 21 1 1
0 0 0
1
N N Nj mn j k m n
N N
n n k
x( n )e X ( k )e
N
    
2 21 1 1
0 0 0
1
N N Nj mn j k m n
N N
n k n
x( n )e X( k ) e
N
  
4
 Do:
21
0
1 : 1
0 : 
N j k m n
N
k
k m
e
N k m

2 21 1 1
0 0 0
1N N Nj mn j k m n
N N
n k n
x( n )e X( k ) e X(m )
N
   
21
0
21
0
1
N j kn
N
n
N j kn
N
n
X ( k ) x( n )e
x( n ) X ( k )e
N


 

 Hay ta có cặp phân tích và tổng hợp của chuỗi :x( n )
5
4.3 BIẾN ĐỔI FOURIER RỜI RẠC (DFT)
 DFT của x(n) có độ dài N định nghĩa:
21
0
0 1
0 : 
N j kn
N
n
x( n )e : k N
X( k )
k

còn lại
2 2
j ( r mN ) j r
( r mN ) rN N
N NW e e W
1
0
0 1
0 : 
N
kn
N
n
x( n )W : k N
X( k )
k

còn lại
2
j
N
NW e
 WN tuần hoàn với độ dài N:
4.3.1 ĐỊNH NGHĨA BIẾN ĐỔI FOURIER RỜI RẠC
6
• X(k) biểu diễn dưới dạng modun & argument:
j ( k )X (k ) X ( k ) e 
Trong đó:
X( k ) - phổ rời rạc biên độ
( k ) arg[ X( k )] - phổ rời rạc pha
 IDFT:
21
0
1
0 1
0 : 
N j kn
N
k
X ( k )e : n N
x( n ) N
n

còn lại
1
0
1
0
 0 1
1
 0 1
N
kn
N
n
N
kn
N
k
X ( k ) x( n )W : k N
x( n ) X ( k )W : n N
N


 Cặp biến đổi Fourier rời rạc: 
7
Ví dụ 4.3.1: Tìm DFT của dãy: 4,3,2,1 )(

 nx
3
4
0
kn
n
X ( k ) x( n )W
 
2
1 2 34
4 4 41
j
W e j;W ;W j
3
0
4
0
0 0 1 2 3 10
n
X ( ) x( n )W x( ) x( ) x( ) x( )
 
3
1 2 3
4 4 4 4
0
1 0 1 2 3 2 2n
n
X ( ) x( n )W x( ) x( )W x( )W x( )W j
 
3
2 2 4 6
4 4 4 4
0
2 0 1 2 3 2n
n
X ( ) x( n )W x( ) x( )W x( )W x( )W
 
3
3 3 6 9
4 4 4 4
0
3 0 1 2 3 2 2n
n
X ( ) x( n )W x( ) x( )W x( )W x( )W j
 
8
Ví dụ: 4.3.2:
a) Tìm FT của dãy x(n)=an u(n), với /a/<1
b) Tìm DFT của dãy x(n)=an rectN(n)
c) Vẽ phổ biên độ & pha của FT và DFT với a=3/4, N=16
 Biến đổi FT của x(n):
1
1
j
j
X ( e )
ae

 
2
1
1 2
jX ( e )
a cos a


1
j a sinarg X( e ) arctg
a cos
 

9
 Biến đổi DFT của x(n):
1 1
0 0
1
1
NN N n
n kn k
N N k
n n N
a
X ( k ) a W aW
aW
 
2
1
2
1 2
Na
X( k )
a cos k a
N
 
2
2
1
a sin k
Narg X( k ) arctg
a cos k
N
10
80 8 16 k
4
/X(k)/
a=3/4
N=16
0 2 
4
/X(ej)/
a=3/4
11
8
0 8 16 k
arg[X(k)]
a=3/4
N=16
8
0 2 
 /2
arg[X(ej)]
- /2
a=3/4
12
4.3.2 CÁC TÍNH CHẤT CỦA DFT
a. Tuyến tính
1 1
DFT
N Nx (n) X (k ) 
1 1 2 2 1 1 2 2
DFT
N N N Na x (n) a x (n) a X (k ) a X (k )  
 Nếu:
 Thì:
2 2
DFT
N Nx (n) X (k ) 
b. Dịch vòng
 DFTN Nx(n) X(k )  Nếu:
0
0 
knDFT
N N Nx(n n ) W X(k )   Thì:
Với: 0 0 Nrect (n) N Nx(n n ) x(n n ) 
gọi là dịch vòng của 
x(n)N đi n0 đơn vị
1 21 2x x
L N N L Nếu: Chọn:
1 2N max{ N ,N } 
13
Ví dụ 4.3.1: Cho:
a) Tìm dịch tuyến tính: x(n+3), x(n-2)
b)Tìm dịch vòng: x(n+3)4, x(n-2)4
 4,3,2,1 )(

 nx
x(n)
n
0 1 2 3
4
3
2
1
a)
n
x(n-2)
0 1 2 3 4 5
4
3
2
1n
x(n+3)
-3 -2 -1 0
4
3
2
1
14
b)
x(n)
n
0 1 2 3
4
3
2
1
N
x(n-1)4
n
0 1 2 3
4
3
2
1
x(n+1)4
n
0 1 2 3
4
3
2
1
 42 3 4 1 2x( n ) , , ,

 43 4 1 2 3x( n ) , , ,

15
c. Chập vòng
1 1
DFT
N Nx(n) X(k) 
1 2 1 2
DFT
N N N Nx (n ) x (n ) X (k ) X (k )  
 Nếu:
 Thì:
2 2
DFT
N Nx (n) X (k) 
1
1 2 1 2
0
N
N N N N
m
x (n) x (n) x (m) x (n m)
 Với:
Chập vòng 2 dãy 
x1(n) & x2(n)
1 21 2x x
L N N L Nếu: Chọn:
1 2N max{ N ,N } 
Chập vòng có tính giao hoán:
1 2 2 1N N N Nx (n) x (n) x (n) x (n) 
2 2N N Nx (n m ) x (n m ) rect ( n ) Và:
Dịch vòng dãy 
x2(-m) đi n đ/vị
16
Ví dụ 4.3.2: Tìm chập vòng 2 dãy 4,3,2,1 )(2

 nx
3
3 4 1 4 2 4 1 4 2 4
0
0 3
m
x ( n ) x ( n ) x ( n ) x (m ) x ( n m ) : n
  
 4,3,2 )(1

 nx
1 2 1 23 4 4N ,N N max{ N ,N } 
 Đổi biến n->m: 2 1 2 3 4x (m ) , , ,

 1 2 3 4 0x (m ) , , ,

 Xác định x2(-m)4: 2 4 2 4 4 1 4 3 2x ( m ) x ( m ) rect (n ) , , ,

 
 Chọn độ dài N:
1
3 1 2 1 2
0
N
N N N N N
m
x (n) x (n) x (n) x (m) x (n m)
   với N-1 n 0
17
m-3 -2 -1 0 1 2 3 4 
4
3
2
1
2x ( m ) 
x2(m)
m
0 1 2 3
4
3
2
1
x2(-m)
m
-3 -2 -1 0
4
3
2
1
m
0 1 2 3 
4
3
2
1
2 4 2 4x ( m ) x ( m )rect ( n ) 
18
 Xác định x2(n-m) là dịch vòng của x2(-m) đi n đơn vị
với 3 n 0
x2(1-m)4
m
0 1 2 3
4
3
2
1
x2(2-m)4
m
0 1 2 3
4
3
2
1 m
0 1 2 3
4
3
2
1
x2(3-m)4
m
0 1 2 3 
4
3
2
1
x2(-m)4
19
33 4 1 4 2 4
0
0 3
m
x ( n ) x (m ) x ( n m ) : n
 
 n=0:
 Nhân các mẫu 
x1(m) & x2(n-m)
và cộng lại:
3
3 4 1 4 2 4
0
0 0 26
m
x ( ) x (m ) x ( m )
 
 n=1:
3
3 4 1 4 2 4
0
1 1 23
m
x ( ) x (m ) x ( m )
 
 n=2:
3
3 4 1 4 2 4
0
2 2 16
m
x ( ) x (m ) x ( m )
 
 n=3:
3
3 4 1 4 2 4
0
3 3 25
m
x ( ) x (m ) x ( m )
 
Vậy: 3 4 1 4 2 4 26 23 16 25x (n ) x (n ) x (n ) , , ,

  
20
Ví dụ 4.3.3: Tìm chập vòng 2 dãy x1(n)=x2(n)=rectN(n)
1 1
1 2 1
0 0
N N
kn kn
N
n n
X ( k ) X ( k ) x ( n )W W
   Biến đổi DFT 2 dãy:
1
0
1
0
0 0
N
n
k : X ( ) W N
 
1
1
0
1
0 0
1
kNN
kn N
N k
n N
W
k : X ( k ) W
W

1
 0
0 
N : k
X (k )
: k
2
3 1 2
 0
0 
N : k
X ( k ) X ( k )X ( k )
: k
1
3 1 2 3
0
 n 01
0 n
N
kn
N
k
N :
x ( n ) x ( n ) x ( n ) X ( k )W
N :
  

21
d. Tính đối xứng
DFT
N Nx(n) X(k ) 
DFT
N Nx (n) X ( k )
  
 Nếu:
 Thì:
e. Quan hệ Parseval
DFT
N Nx(n) X(k ) 
1 1
2 2
0 0
1N N
N N
n k
x(n) X(k )
N
  
 Nếu:
 Thì:
22
f. Chập tuyến tính sử dụng DFT
 Kết quả phép chập tuyến tính của 2 dãy x1(n)N1 và x2(n)N2
sẽ giống với chập vòng nếu thêm các mẫu 0 vào sau các
dãy x1(n) và x2(n) để có chiều dài tối thiểu là N1+N2 - 1:
x1(n)N1 * x2(n)N2 = x1(n)N1+N2 -1  x2(n) N1+N2 -1
 Lưu đồ phép chập tuyến tính thông qua DFT được mô tả:
DFT
DFT
x IDFT
x1(n)N1+N2 -1
x2(n)N1+N2 -1
x3(n)N1+N2 -1
X1(k)
X2(k)
X3(k)
23
Ví dụ 4.3.4: Cho 2 dãy x1(n)=x2(n)=rect3(n)
Hãy tìm x3(n)=x1(n)*x2(n) và x3(n)=x1(n)5  x2(n)5
 Chập tuyến tính của 2 dãy:
3 1 2 1 2 3 2 1x ( n ) x ( n ) x ( n ) { , , , , }

 Kết quả sẽ tương tự đối với phép chập vòng nếu thêm
vài mẫu 0 vào sau 2 dãy x1(n) và x2(n) để có độ dài tối
thiểu là 5:
3 5 1 5 2 5 1 2 3 2 1x ( n ) x ( n ) x ( n ) { , , , , }

  
1 5 2 51 1 1 0 0 1 1 1 0 0x ( n ) { , , , , } và x ( n ) { , , , , }
 
24
4.3.3 KHÔI PHỤC BIẾN ĐỔI Z & FT TỪ DFT
1
0
N
n
n
X ( z ) x( n )z
 
a. Khôi phục biến đổi Z
 Biến đổi Z của dãy x(n)N:
 Biến đổi IDFT của X(k) là:
1
0
1 N kn
N
k
x( n ) X ( k )W
N
 
1
0
N
n
n
X ( z ) x( n )z
 
1 1
0 0
1N N kn n
N
n k
X ( k )W z
N
 
 11 1 11
1
0 0 0
11 1
1
N
k
N N Nn Nk
N N N k
k n k N
W z
X( z ) X ( k ) W z X( k )
N N W z
  

1
0
1)1(
)()1(
)(
N
k
k
N
N
N
zW
kX
N
z
zX
25
b. Khôi phục biến đổi Fourier
 Mối quan hệ giữa biến đổi Z & FT: j
j
z e
X ( e ) X ( z ) 

 Theo mối quan hệ giữa ZT & DFT:
1
1
0
1
1
N N
k
k N
( z ) X ( k )
X ( z )
N ( W z )

1
2
0
1
1
j N N
j N
j( k )k N
X ( k )( e )
X ( e )
N
( e )




 Do: 2 2 2 21 2
2
x x x x
j j j j
jx xe e ( e e ) j e sin

k
N
N
jN
k
N
j e
k
N
N
kX
N
eX


 

2
11
0 )
2
sin(
2
sin
)(
1
)(
26
4.4 BiẾN ĐỔI FOURIER NHANH FFT
1
0
 0 1
N
kn
N
n
X ( k ) x( n )W : k N
 
4.4.1 KHÁI NiỆM BiẾN ĐỔI FOURIER NHANH FFT
 Vào những năm thập kỷ 60, khi công nghệ vi xử lý phát
triển chưa mạnh thì thời gian xử lý phép tóan DFT trên
máy tương đối chậm, do số phép nhân phức tương đối
lớn.
 DFT của x(n) có độ dài N:
 Để tính X(k), ứng với mỗi giá trị k cần có N phép nhân và 
(N-1) phép cộng, vậy với N giá trị k thì cần có N2 phép 
nhân và N(N-1) phép cộng.
 Để khắc phục về mặt tốc độ xử lý của phép tính DFT,
nhiều tác giả đã đưa ra các thuật tóan riêng dựa trên DFT
gọi là FFT (Fast Fourier Transform).
27
4.4.2 THUẬT TOÁN FFT CƠ SỐ 2 
a. Thuật toán FFT cơ số 2 phân chia theo thời gian
 Thuật tóan dựa trên sự phân chia dãy vào x(n) thành các
dãy nhỏ, do biến n biểu thị cho trục thời gian nên gọi là
phân chia theo thời gian.
1
0
N
kn
N
n
X ( k ) x( n )W
 
1 1
n 0 2,4... n 1 3,5...
N N
kn kn
N N
, ,
x( n )W x( n )W
  
2 1 2 1
2 2 1
r 0 r 0
2 2 1
( N / ) ( N / )
kr k ( r )
N NX ( k ) x( r )W x( r )W
  
 Thay n=2r với n chẵn và n=2r+1 với n lẽ:
 Giả thiết dãy x(n) có độ dài N=2M, nếu không có dạng lũy
thừa 2 thì thêm vài mẫu 0 vào sau dãy x(n).
28
 X0(k) – DFT của N/2 điểm ứng với chỉ số n chẵn
 X1(k) – DFT của N/2 điểm ứng với chỉ số n lẽ
2 1
0 2
r 0
2
( N / )
kr
N /X ( k ) x( r )W
 
2 1
1 2
r 0
2 1
( N / )
kr
N /X (k ) x( r )W
 Đặt:
0 1
k
NX ( k ) X ( k ) W .X ( k ) 
 Lấy ví dụ minh họa cho x(n) với N=8
2 1 2 1
2 2
r 0 r 0
2 2 1
( N / ) ( N / )
kr k kr
N / N N /X ( k ) x( r )W W . x( r )W
  
22
2
2 2
2
j krj k r
k r krN /N
N N /W e e W
 Do:
29
DFT
N/2
điểm
x(0)
x(2)
x(4)
x(6)
X(0)
X(1)
X(2)
X(3)
DFT
N/2
điểm
x(1)
x(3)
x(5)
x(7)
X(4)
X(5)
X(6)
X(7)
W0
W1
W2
W3
W4
W5
W6
W7
X0(0)
X0(1)
X0(2)
X0(3)
X1(0)
X1(1)
X1(2)
X1(3)
n chẵn
n lẽ
 Phân chia DFT- N điểm -> 2 DFT- N/2 điểm;
 Qui ước cách tính X(k) theo lưu đồ:
- Nhánh ra của 1 nút bằng tổng các nhánh vào nút đó
- Giá trị mỗi nhánh bằng giá trị nút xuất phát nhân hệ số
30
 Sau đó đánh lại chỉ số theo thứ tự các mẫu x(n), tiếp tục
phân chia DFT của N/2 điểm thành 2 DFT của N/4 điểm
theo chỉ số n chẵn và lẽ và cứ thế tiếp tục phân chia cho
đến khi nào còn DFT 2 điểm thì dừng lại.
 Ví dụ X0(k) được phân chia:
2 1 2 1
0 2 2
r 0 r 0
2
( N / ) ( N / )
kr kr
N / N /X ( k ) x( r )W g( r )W
  
2 1 2 1
2 2
r 0 2 4 r 1 3 5
( N / ) ( N / )
kr kr
N / N /
, , ... , , ...
g( r )W g( r )W
  
4 1 4 1
4 2 4
l 0 l 0
2 2 1
( N / ) ( N / )
kl k kl
N / N / N /g( l )W W g( l )W
  
0 00 2 01
k
N /X ( k ) X ( k ) W .X ( k ) 
31
 Phân chia DFT- N/2 điểm -> 2 DFT- N/4 điểm của X0(k)
DFT
N/4
x(0)
x(4)
W0N/2
W1N/2
X00(0)
X00(1)
X0(0)
X0(1)
DFT
N/4
x(2)
x(6)
X0(2)
X0(3)
X01(0)
X01(1)
W2N/2
W3N/2
 Phân chia X1(k) tương tự: 1 10 2 11
k
N /X ( k ) X ( k ) W .X ( k ) 
DFT
N/4
x(1)
x(5)
W0N/2
W1N/2
X10(0)
X10(1)
X1(0)
X1(1)
DFT
N/4
x(3)
x(7)
X1(2)
X1(3)
X11(0)
X11(1)
W2N/2
W3N/2
32
 Lưu đồ DFT dãy x(n) sau 2 lần phân chia với N=8
DFT
N/4
x(0)
x(4)
x(2)
x(6)
X(0)
X(1)
X(2)
X(3)
x(1)
x(5)
x(3)
x(7)
X(4)
X(5)
X(6)
X(7)
W0
W1
W2
W3
W4
W5
W6
W7
DFT
N/4
DFT
N/4
DFT
N/4
W0
W2
W4
W6
X00(0)
X00(1)
X01(0)
X01(1)
X10(0)
X10(1)
X11(0)
X11(1)
W0
W2
W4
W6
x(0)
x(4)
W0N = 1
WN
N/2 =-1
X00(0)
X00(1)
 Lưu đồ DFT 
2 điểm: 
33
 Lưu đồ DFT dãy x(n) sau 3 lần phân chia với N=8
x(0)
x(4)
x(2)
x(6)
X(0)
X(1)
X(2)
X(3)
x(1)
x(5)
x(3)
x(7)
X(4)
X(5)
X(6)
X(7)
W0
W1
W2
W3
W4
W5
W6
W7
W0
W2
W4
W6
W0
W2
W4
W6
-1
-1
-1
-1
Xm(p)
Xm(q)
-1
Xm+1(p)
Xm+1(q)
WrN
Xm(p)
Xm(q)
Xm+1(p)
Xm+1(q)
WrN
WN
(r+N/2) = - WN
r
34
 Lưu đồ DFT dãy x(n) sau 3 lần phân chia với N=8
x(0)
x(4)
x(2)
x(6)
X(0)
X(1)
X(2)
X(3)
x(1)
x(5)
x(3)
x(7)
X(4)
X(5)
X(6)
X(7)
W0
W1
W2
W3
-1
-1
-1
-1
W0
W2
-1
-1
-1
-1
W0
W2
-1
-1
-1
-1
Đảo 
bít 
 Với N=2M -> M lần phân chia
 Số phép nhân = số phép cộng = NM/2=(N/2)log2N
35
Chỉ số 
tự nhiên
Số nhị phân chưa đảo 
(n2,n1,n0)
Số nhị phân đảo
(n0,n1,n2)
Chỉ số 
đảo
0 0 0 0 0 0 0 0
1 0 0 1 1 0 0 4
2 0 1 0 0 1 0 2
3 0 1 1 1 1 0 6
4 1 0 0 0 0 1 1
5 1 0 1 1 0 1 5
6 1 1 0 0 1 1 3
7 1 1 1 1 1 1 7
 Bảng mô tả qui luật đảo bít:
36
Ví dụ 4.4.1: Hãy vẽ lưu đồ và tính FFT cơ số 2 phân theo t/g
 4,3,2,1 )(

 nx
x(0)
x(2)
x(1)
x(3)
X(0)
X(1)
X(2)
X(3)
W0
W1
-1
-1 -1
-1
 k=0: X(0) = [x(0) + x(2)] + W0[x(1) + x(3)] = 10.
 k=1: X(1) = [x(0) - x(2)] + W1[x(1) - x(3)] = - 2 + 
j2.
 k=2: X(2) = [x(0) + x(2)] - W0[x(1) + x(3)] = - 2.
 k=3: X(3) = [x(0) - x(2)] - W1[x(1) - x(3)] = - 2 - j2.37
b. Thuật toán FFT cơ số 2 phân chia theo tần số
 Thuật tóan dựa trên sự phân chia dãy ra X(k) thành các
dãy nhỏ, do biến k biểu thị cho trục tần số nên gọi là
phân chia theo tần số.
1
0
N
kn
N
n
X( k ) x( n )W
 
2 1 1
n 0 n 2
( N / ) N
kn kn
N N
N /
x( n )W x( n )W
  
2 1 2 1
2
n 0 n 0
2
( N / ) ( N / )
kn k( n N / )
N Nx( n )W x( n N / )W
  
2 1 2 1
2
n 0 n 0
2
( N / ) ( N / )
kn kN / kn
N N Nx( n )W W x( n N / )W
  
2 1
n 0
1 2
( N / )
k kn
Nx( n ) ( ) x( n N / ) W
 
38
 Với k chẵn, thay k=2r:
 
2 1
2
n 0
2 2
( N / )
rn
N /X ( r ) x( n ) x( n N / ) W
 
 Với k lẽ, thay k=2r+1
  
2 1
2
n 0
2 1 2
( N / )
n rn
N N /X ( r ) x( n ) x( n N / ) W W
 
2 2g(n) x(n) x(n N / ); h(n) x(n) x(n N / )  Đặt:
2 1
2
n 0
2
( N / )
rn
N /X ( r ) g( n )W
 
2 1
2
n 0
2 1
( N / )
n rn
N N /X ( r ) h( n )W W
 
 X(2r) – DFT của N/2 điểm ứng với chỉ số k chẵn
 X(2r+1) – DFT của N/2 điểm ứng với chỉ số k lẽ
39
 Phân chia DFT N=8 điểm -> 2 DFT N/2= 4 điểm
k chẵn
k lẽ
DFT
N/2
điểm
x(0)
x(1)
x(2)
x(3)
X(0)
X(2)
X(4)
X(6)
DFT
N/2
điểm
x(4)
x(5)
x(6)
x(7)
X(1)
X(3)
X(5)
X(7)
W0
W1
W2
W3
g(0)
g(1)
g(2)
g(3)
h(0)
h(1)
h(2)
h(3)
-1
-1
-1
-1
40
 Sau đó đánh lại chỉ số theo thứ tự các mẫu X(k), tiếp tục
phân chia DFT của N/2 điểm thành 2 DFT của N/4 điểm
theo chỉ số k chẵn và lẽ. Tiếp tục phân chia cho đến khi
nào còn DFT 2 điểm thì dừng lại.
 Dữ liệu ra X(k) được sắp xếp theo thứ tự đảo bít, còn
dữ liệu vào được sắp theo thứ tự tự nhiên.
 Số phép nhân và phép cộng trong lưu đồ phân theo tần
số bằng với số phép nhân và cộng trong lưu đồ phân
theo thời gian.
41
 Lưu đồ DFT dãy x(n) sau 3 lần phân chia với N=8
x(0)
x(1)
x(2)
x(3)
X(0)
X(4)
X(2)
X(6)
x(4)
x(5)
x(6)
x(7)
X(1)
X(5)
X(3)
X(7)
W0
W1
W2
W3
-1
-1
-1
-1
W0
W2
-1
-1
-1
-1
W0
W2
-1
-1
-1
-1
Đảo 
bít 
42
 k=0: X(0) = [x(0) + x(2)] + [x(1) + x(3)] = 10.
 k=2: X(2) = [x(0) + x(2)] - [x(1) + x(3)] = - 2.
 k=1: X(1) = [x(0) - x(2)] + W1[x(1) - x(3)] = - 2 + 
j2.
 k=3: X(3) = [x(0) - x(2)] - W1[x(1) - x(3)] = - 2 - j2.
Ví dụ 4.4.2: Hãy vẽ lưu đồ và tính FFT cơ số 2 phân theo t/s
 4,3,2,1 )(

 nx
x(0)
x(1)
x(2)
x(3)
X(0)
X(2)
X(1)
X(3)
W0
W1
-1
-1-1
-1
43
4.4.3 THUẬT TOÁN FFT VỚI N=N1N2
n2 n1 0 1  N1-1
0 x(0) x(N2)  x[N2(N1-1)]
1 x(1) x(N2+1)  x[N2(N2-1)+1]
N2-1 x(N2-1) x(2N2-1)  x[N1N2-1]
 Giả thiết dữ liệu vào được sắp xếp vào trong mảng theo
thứ tự từng cột với số cột N1 và số hàng N2:
 Giả thiết độ dài dãy x(n) có thể phân tích N=N1N2, nếu
độ dài không thể biểu diễn dưới dạng trên thì thêm vài
mẫu 0 vào sau dãy x(n).
44
 Lấy ví dụ sắp xếp dãy x(n) với N=12, chọn N1=3 và N2=4
n2 n1 0 1 2
0 x(0) x(4) x(8)
1 x(1) x(5) x(9)
2 x(2) x(6) x(10)
3 x(3) x(7) x(11)
 Các chỉ số n của x(n), k của X(k) xác định:
 n = n1N2 + n2
0 n1 N1
0 n2 N2
 k = k1 + k2N1
0 k1 N1
0 k2 N2
45
 DFT N điểm dãy x(n) được phân tích:
2 1
1 2 1 2 1 2
2 1
1 1
1 2 1 2 1 2
0 0
N N
( k k N )( n n N )
N
n n
X( k ) X( k k N ) x( n n N )W
  
2 1
1 1 1 2 2 2 1 1 2 1 2
2 1
1 1
2
2 1 2
0 0
N N
n k n k N n k N n k N N
N N N N
n n
x( n n N )W W W W
  
1 1 2 1 1 2 2 1 2 2 1 2 1 2
1 2
Do: 1n k N n k n k N n k n k N NN N NN NW W ;W W ;W 
2 1
1 1 2 1 2 2
1 2
2 1
1 1
2 1 2
0 0
N N
n k n k n k
NN N
n n
X ( k ) x( n n N )W W W
  
  
 
 
46

1
0
12
2
2
22
2
),()(
N
n
kn
NWknGkX
1
1 1
1
1
1
2 1 2 1 2
0
N
n k
N
n
F( n ,k ) x( n n N )W
 
2 1
2 1 2 1
n k
NG( n ,k ) F( n ,k ).W 
 Đặt:
Các bước tiến hành theo thuật tóan:
 Sắp xếp dữ liệu vào theo thứ tự từng cột, mảng x
 Tính DFT theo từng hàng mảng x, được F(n2,k1)
 Tính mảng hệ số WN
n2k1
 Nhân mảng F(n2,k1) với WN
n2k1, được G(n2,k1)
 Tính DFT theo từng cột mảng G(n2,k1), được X(k)
 Đọc dữ liệu ra theo thứ tự từng hàng X(k).
47
Ví dụ 4.4.3: Nêu các bước tính và vẽ lưu đồ thuật tóan FFT 
dãy x(n) với N=N1N2=12, chọn N1=3 và N2=4 
 Sắp xếp dữ liệu vào theo thứ tự từng cột như bảng:
n2 n1 0 1 2
0 x(0) x(4) x(8)
1 x(1) x(5) x(9)
2 x(2) x(6) x(10)
3 x(3) x(7) x(11)
48
 Tính DFT theo từng hàng mảng x, được F(n2,k1):
n2 k1 0 1 2
0 F(0,0) F(0,1) F(0,2)
1 F(1,0) F(1,1) F(1,2)
2 F(2,0) F(2,1) F(2,2)
3 F(3,0) F(3,1) F(3,2)
1
1 1
1
1
1
2 1 2 1 2
0
N
n k
N
n
F( n ,k ) x( n n N )W
 
49
 Tính mảng hệ số WN
n2k1
n2 k1 0 1 2
0 WN
0 WN
0 WN
0
1 WN
0 WN
1 WN
2
2 WN
0 WN
2 WN
4
3 WN
0 WN
3 WN
6
50
 Nhân các phần tử mảng F(n2,k1) với các hệ số của 
mảng WN
n2k1 tương ứng, được G(n2,k1) :
n2 k1 0 1 2
0 G(0,0) G(0,1) G(0,2)
1 G(1,0) G(1,1) G(1,2)
2 G(2,0) G(2,1) G(2,2)
3 G(3,0) G(3,1) G(3,2)
Phần tử: G(ni,kj) = F(ni,kj). WN
nikj
51
 Tính DFT theo từng cột mảng G(n2,k1), được X(k):
k2 k1 0 1 2
0 X(0) X(1) X(2)
1 X(3) X(4) X(5)
2 X(6) X(7) X(8)
3 X(9) X(10) X(11)
2
2 2
2
2
1
1 1 2 2 1
0
N
n k
N
n
X( k ) X( k N k ) G( n ,k )W
 
 Đọc dữ liệu ra theo thứ tự từng hàng X(k)
52
 Lưu đồ FFT dãy x(n) N=N1N2, với N1=3, N2=4:
DFT
N1
điểm
x(0)
x(4)
x(8)
W0
W1
W2
DFT
N1
điểm
x(1)
x(5)
x(9)
DFT
N1
điểm
x(2)
x(6)
x(10)
DFT
N1
điểm
x(3)
x(7)
x(11)
W0
W2
W4
W0
W3
W6
DFT
N2
điểm
DFT
N2
điểm
DFT
N2
điểm
X(0)
X(3)
X(6)
X(9)
X(1)
X(4)
X(7)
X(10)
X(2)
X(5)
X(8)
X(11)
53