Bài giảng Chương 8: Biến đổi fourier rời rạc và biến đổi fourier nhanh

1 Chương 8 BIẾN ĐỔI FOURIER RỜI RẠC VÀ BIẾN ĐỔI FOURIER NHANH Trong chương 3 ta thấy chuỗi Fourier liên tục thời gian (CTFS) liên hệ thời gian liên tục với tần số rời rạc, biến đổi Fourier liên tục thời gian (CTFT) liên hệ thời gian rời rạc với tần số rời rạc. Sự biểu diễn hai hình thức Fourier trên là CTFS và CTFT, là không tuần hoàn trong miền tần số nhưng hai phép biến đổi DTFS và DTFT thì toàn hoàn trong miền tần số đó là kết quả của sự lấy mẫu thời gian. Trong chương này, biến đổi Fourier rời rạc (DFT) và biến đổi Fourier nhanh được xét đến như sự trình bày Fourier thứ ba mà áp dụng cho tín hiệu không tuần hoàn rời rạc thời gian có chu kỳ giới hạn. DFT và FFT thì rất hữu ích trong sự phân tích và xử lý nhiều vấn đề của hệ thống và tín hiệu biến biến thời gian LTI. Chúng cho phép xử lý bằng máy tính và vi xử lý tín hiệu số. Thật ra, DFT và FTT đã được nói đến trong chương 3 (phần 3.9) Hình 8.1: minh họa biến đổi thời gian-tần số cho sự phân tích Fourier khác nhau 8.1 BIẾN ĐỔI FOURIER RỜI RẠC (DFT) Với tín hiệu không tần hoàn, x(n) nhìn chung nó tồn tại ở mọi thời điểm, biến đổi Fourier rời rạc thời gian (DTFT) được định nghĩa (phần 3.5) như Tín hiệu tương tự tuần hoàn Phổ rời rạc không tuần hoàn Tín hiệu tương tự không tuần hoàn Phổ liên tục không tuần hoàn Rời rạc và tuần hoàn Rời rạc và tuần hoàn Rời rạc và không tuần hoàn Phổ liên tục tuần hoàn spectrum 2     n njenxX  )()( (DFFT) (8.1) Tín hiệu thời gian được phục hồi bằng cách lấy tích phân liên tục      2 )( 2 1 )( deXnx nj (IDFT) (8.2) Chú ý rằng tín hiệu thời gian x(n) thì rời rạc nhưng DFT của nó )(X thì liên tục theo tần số, và cũng giống như vậy với DTFT. Sự biến đổi áp dụng cho hệ thống là     n njenhH  )()( (Đáp ứng tần số) (8.3)   deHnh nj    2 )( 2 1 )( (Đáp ứng xung) (8.4) 8.1.1 Rời rạc tần số liên tục  Một số vấn đề của DTFT, đó là vấn đề của sự tính toán số (bằng máy tính hoặc vi xử lý số). Đầu tiên, tổng vô hạn (8.1) và (8.3) không thể xử lý được, trong thực tế cả chuỗi x(n) cũng được giới hạn về chiều dài hoặc cắt cụt đi, để giảm sự vô hạn của nó. Mặc khác frequency  thì liên tục và theo nguyên tắc ta phải tính (8.1) và (8.3) tại những giá trị vô hạn của  dù tổng thì giới hạn về mặt thời gian. Vì vậy tần số  phải được rời rạc hóa. Thứ hai, như biến đổi )(X và )(H là những giá trị liên tục, vì vậy ở đây vấn đề tính tích phân cần được xét đến. Điều này cũng dẫn đến sự cần thiết để rời răc hoặc lấy mẫu tần . Với tín hiệu không tuần hoàn x(n) và đáp ứng xung h(n), cách chúng ta lấy mẫu chúng? Càng nhiều mẫu được lấy, những mẫu sẽ diễn tả tín hiệu tốt hơn nhưng lại tốn nhiều thời gian cho sự tính toán. Trả lời cho câu hỏi quan trọng này nằm ở định lý lấy mẫu miền tần sô, đó là một dạng khác của định lý lấy mẫu ở miền thời gian (phần 1.3.2). Định lý phát biểu như sau: Phổ tần số liên tục của tín hiệu tồn tại trong một chu kỳ thời gian hữu hạn T0 giây có thẻ trình bày một cách hoàn toàn bằng những mẫu tần số mà được lấy tại những khoảng tần số ít hơn 1/H0 Hz (mẫu/giây). Phổ tần số có thể được phục hồi từ những mẫu tần số. (hình 8.2) 8.1.2 DFT và đảo của nó Đầu tiên, biến đổi Fourier rời rạc (DFT) cũng như biến đổi Fourier rời rạc thời gian (DTFT) được lấy mẫu tại những khoảng bằng nhau. Xét một tín hiệu nhân quả x(n) DTFT của nó có được từ (4.1) với ngưỡng dưới của tổng là không. )(H 0 /2   0 1 H  Hình 8.2: Lấy mẫu đáp ứng tần số 3     0 )()( n njenxX  (8.5) Kế đến xét một tín hiệu hữu hạn thời gian có N mẫu (từ n=0 đến n=N-1) thì biến đổi trên trở thành     1 0 )()( N n njenxX  (8.6) Bây giờ tính )(X tại N giá trị rời rạc bằng nhau của  trong chu kỳ 2: 1,...2,1,0,2  Nkk Nk  (8.7a) Hoặc 2 k k k f N     (8.7b) và DFT của tín hiệu có N mẫu từ n = 0 đến n = N -1 là )1(,...,2,1,0,)()( 1 0 )/2(     NkenxkX N n knNj  (DFT) (8.8) k được gọi là hệ số phổ và X(k) gọi là tần số lấy mẫu. Chuỗi x(n) có giá trị thực hoặc phức Biến đổi ngược, tín hiệu x(n) được phục hồi như )1(,...,2,1,0,)()( )/2(1   NnekXnx knNjN  (IDFT) (8.9) Ta thấy DFT và IDFT thì giống như chuỗi Fourier rời rạc thời gian của x(n) tại chu kỳ N (phần 3.4). Từ sự định nghĩa của DFT, ta dễ dàng thấy rằng X(0) là thực nếu x(n) thực. DFT áp dụng cho hệ thống. 1,...,2,1,0,)()( 1 0 )/2(     NkenhkH N n knNj  (DFT) (8.10) 1,...,2,1,0,)( 1 )( 1 0 )/2(     NnekH N nh N k knNj  (IDFT) (8.11) Sự định nghĩa ở (8.8), (8.9), (8.10) và (8.11) là DFT N điểm. Nếu ta tính X(k) từ (8.8) ở ngoài dải 10  Nk , ví dụ với 12  NkN hoặc 012  kN , ta sẽ thấy giá trị được lặp lại, nghĩa là, X(k) tuần hoàn với chu kỳ N giống như vây, Nếu ta tính x(n) từ (8.9) ta sẽ thấy giá trị lập lại nghĩa là x(n) tuần hoàn với chu kỳ N (tại thời điểm ban đầu ta xét x(n) là một chuỗi có chiều dài N từ 10  Nnton ). Vì vậy, hình 8.1 chỉ tín hiệu rời rạc và tuần hoàn được biến đổi DFT thành phổ rời rạc và tuần hoàn. Thường số N được lấy như là số nguyên mũ của 2 (đó là, 32, 64, 128). Khi số mẫu x(n) không có chiều dài như trên ta cộng thêm mẫu không để có chiều dài bằng với N (ví dụ nếu x(n) có 120 mẫu ta sẽ cộng thêm 8 mẫu không để có 128 mẫu). Đây là thêm không hoặc padding không. Để thuận tiện ta chú thích )/( Nj N eW 2 (8.12a) Vì vậy knNjkn N eW )/( 2 (8.12b) knNjkn N eW )/( 2 (8.12c) 1 NN WW * (8.12d) Với dấu sao chú thích là liên hiệp phức. Cũng như vậy, thay vì viết (2 /N) biểu thức như trên ta cso thể viết để rõ ràng hơn. Ví dụ 8.1.1 Tìm DFT N điểm của tín hiệu 4 (a) )()(1 nnx  (b) 1)(2 nx (c) Nnnnnx  003 0),()(  (d) Nnnx n  0,2)(4 (e) Nnnnnnx  005 0),(4)(4)( (f) 00006 )/2()1(0,cos)( kNandNnnnx   Giải (a) Từ sự định nghĩa của DFT 1,...,1,0,11)()( 0)/2( 1 0 )/2( 1      NkeenkX kNj N n knNj  (b) Từ sự định nghĩa của DFT     1 0 )/2( 2 1)( N n knNjekX  Tổng có giá trị là N với k= 0, và 0 khi 0k . Vì vậy )()(2 kNkX  (c) Từ sự định nghĩa của DFT 1,...,1,01)()( 1 0 ,)/2()/2()/2( 03 00     NkeeennkX N n knNjknNjknNj  (d) Từ sự định nghĩa của DFT          1 0 )/2( 1 0 )/2( 4 )( N n nkNj N n knNjn eekX   Sử dụng công thức chuỗi hình học hữu hạn( ), ta có   1,...,1,0, 1 1 )( )/2( )/2( 4       Nk e e kX kNj NkNj     (e) Chú ý rằng )(5 nx là xung chữ nhật số (thấy ) có độ rộng không mẫu. Như trong (4.10a) và (4.10b), ta viết )/2( Nj N eW  knNjkn N knNjkn N eWeW )/2()/2( ,    Vì vậy, từ định nghĩa của DFT và sử dụng công thức chuỗi hình học hữu hạn ( ), ta có K N kn N n n kn N W W WkX      1 1 )( 00 1 0 5 Tử số, lấy 2/0kn NW làm thừa số chung, và mẫu số lấy 2/k NW làm thừa số chung, biến đổi trên trở thành 1,...,1,0, )/sin( )/sin( )( 02/)1()/2(( 2/2/ 2/2/ 2/)1( 5 0 00 0         Nk Nk Nkn e WW WW WkX nkNj k N k N kn N kn Nnk N   Ta có thể kiểm tra trường hợp 00 n (kết quả là 0) và trường hợp 10 n (kết quả như trong1 (b)). (f) Diễn tả cosin trong thành phần của mũ phức. 00 2 1 2 1 0cos)(  jnjn eennx  5 Vì vậy nkj N n nkj NN eekX )( 2 1 1 0 )( 2 1 0 2 0 2 )(         Với 00 )/2( kN          1 0 )( 2 1 1 0 )( 2 1 0 2 0 2 )( N n nkkj N n nkkj NN eekX  Tổng thứ nhất bằng không với 0kk  , và bằng N với 0kk  . Tổng thứ hai bằn không với )( 0kNk  , và bằng N với )( 0kNk  . Vì vậy biến đổi là 002 1 ,)( kNkandkkNkX  otherwise,0 Ta có thể hiểu kN)/2(  là tần số DFT và viết 1,...,1,0,/2  Nksampleradk Nk  Nếu, đôi biến đổi có thể đặt trong dạng 1,...,1,0,)()( 1 0     NkenxX W n nj k k (DFT) (8.13) 1,...,1,0,)()( 1 0 1     NneXnx nj N k kN k (DFT) (8.14) Vì vậy ta có thể tính )( kX  thay vì như thông thường X(k). Ví dụ 8.1.2 (cũng thấy trong ví dụ 3.9.2) (a) Tín đáp ứng tần số DFT )( kH  của một lọc FIR mà có đáp ứng xung là h(0) = 0, h(1) = 1, h(2) = 2, h(3) = 3, otherwise h(n) = 0. (b) Chứng mình rằng từ 4 giá trị của )( kH  đáp ứng xung có thể phục hồi một cách hoàn toàn Giải (a) Đáp ứng xung có 4 giá trị, vì vậy N = 4 và 4/2 k . Cũng chú ý rằng dải 30  n thì h(n) = n. Đáp ứng tần số )( kH  là 3,2,1,0,)()()( 3 0 )2/( 3 0 )4/2( 4 2       kenhenhkH n knj n knj  Bây giờ 6321)0(,0 3 0 01)2/(     n jneHk  2232)(,1 2/32/ 3 0 1)2/( 2 jeeeneHk jjj n nj      2322)(,2 32 3 0 2)2/(      jjj n nj eeeeHk 22323)(,3 2/932/3 3 0 3)2/( 2 3 jeeeeHk jjj n nj      Kết quả vẽ trong hình 8.3 H() 6 22 22 2 6 (b) Trong hình 8.3 ta có thể tưởng tượng rằng đáp ứng tần số liên tục (đường chấm) được lấy mẫu đồng nhất tại 4 điểm. Bây giờ ta muốn biết liệu đáp ứng xung có phục hồi một cách đầy đủ từ những mẫu này hay không Đầu tiên, DFT đảo được cho bởi 1,...,1,0,)( 4 1 )( 3 0 )2/( 2    NkekHnh k knj  Bây giờ   0)22(2)22(6 4 1 )( 4 1 )0(:0 0)2/( 2   jjekHhn kj    1)22(2)22(6 4 1 )( 4 1 )1(:1 3)2/(2)2/(1)2/(0)2/( 1)2/( 3 0 2       jjjj kj k ejeeje ekHhn Ta lấy giá trị đầu của h(2) và h(3). Bên cạnh đó, nếu ta tính h(4), h(5)ta sẽ thấy chúng là h(0), h(1)vì vậy DFT là tuần hòan ở chu kỳ N. Ví dụ 8.1.3 Một tín hiệu audio băng thông hạn giới hạn tại 8kHz được lấy mẫu tại 20kHz và sau đó DFT được tính tại 1000 điểm. (a) Tìm khoảng cách giữa những mẫu tần số (b) Đáp ứng tương tự với hệ số k = 200 ? Giải (a) Với tốc độ lấy mẫu kHzf s 20 và DFT lấy tại 100N điểm, khoảng lấy mẫu tần số là Hz N f f s 20 1000 20000  (b) Tần số gốc tương tự  rad/sec liên hệ với tần số số  rd/sample bằng ( 1.39), nhưng ở đây ta viết s k f k  DFT N điểm nghĩa rằng DTFT được lấy mẫu tại N điểm tần số. Vì vậy tần số DFT 1,..,1,0, 1000 22  Nkkk N k   Vì vậy tần số gốc tương tự được cho bởi sradkkf ksk /4020000 1000 2    Và tần số tuyến tính tương tự là 2/ 0  2/3 k Hình 8.3: Ví dụ 8.1.2 Đáp ứng tần số DFT 1 2 3 k 0 7 kHzf kk 20 2     Vì vậy hệ số phổ k = 200 tương ứng với tần số tương tự Hzf 400020020  Tổng quát X(k) phức. Và ta có thể diễn tả những thành phần của phần thực và ảo hoặc phổ biên độ và phổ pha cho CTFT (phần 3.2.2) và DTFT. (phần 3.5) )()()()()( kjIR ekXkjXkXkX  (8.15a) Với   2 1 )()()( 22 kXkXkX IR  (8.15b) và )( )( )(arg)( kX kX R IarctgkXk  (8.15c) Là phổ biên độ và phổ pha X(k), tương ứng Ví dụ 8.1.4 Chuỗi số được cho như  1,1,1,1,1,0,0)( nx Tìm phổ biên độ và phổ pha của DFT 10 điểm Giải Với DFT 10 điểm, N = 10 và chuỗi số bắt đầu từ n = 0 đến 91 Nn . Vì vậy chuỗi được cho có 7 mẫu, ta cộng thêm 2 mẫu không tại phần cuối của nó để bậc tổng số là 10 mẫu. Vì vậy chuỗi được thêm không vào là  0,0,1,1,1,1,1,0,0)( nx DFT là       6 2 9 0 )/2()()( n kn n knNj WenxkX  Bằng cách sử dụng công thức chuỗi hình học hữu hạn, ta có 9,...,1,0, )0/sin( )2/sin( 1 )( 5/4 72        k k k e W WW kX kj k kk   Từ điều này ta có thể tính phổ biên độ và phổ pha, tương ứng )10/sin( )2/sin( )( k k kX    0 )10/sin( )2/sin( , 5 4 0 )10/sin( )2/sin( , 5 4 )(   k k k k k kk      Ví dụ 8.1.5 Một xung chữ nhật có chiều dài L otherwise LLnx ,0 1...,,1,0,)(  (a) Tìm DFT của nó (b) Dẫn xuất ra số điểm DFT với LN  8 Giải (a) Từ(8.1) DFT được cho bởi 2/)1( 1 0 1 0 )2/sin( )2/sin( 1 1 )()(                Lj j Lj L n nj L n nj e L e e eenxX        Phổ biên độ và pha của )(X có được từ kết quả trên với chiều dài L (ví dụ 3.5.1) (b) DFT N điểm )(kX của x(n) là DTFT )(X tính tại N khoảng tần số đồng nhất (8.7): 1,...,1,0, )/sin( )/sin( 1 1 )( /2 /2       Nk Nk NkL e e kX Nkj NkLj     Nếu số điểm DFT gần bằng với chiều dài tín hiệu L thì 1,...,2,1,0 0,)(   Lk kLkX Điều này giống với ví dụ 8.1.1b và 8.1.1e. Dù DTFT )(X trình bày tuần tự x(n) trong miền tần số vì  liên tục, nhưng L điểm DFT không cung cấp đủ chi tiết đặc tính phổ của x(n) vì khoảng tần số giữa những điểm tần số không đủ gần. Giải pháp cho vấn đề này là lấy N điểm DFT với N > L, điều này đồng nghĩa với việc tăng chiều dài của chuỗi tín hiệu L đển N bằng cách cộng thêm N-L mẫu không. (đây là cách thêm không như trên). Ví dụ 8.1.6 [Trích từ A. Antoniou, 2006] (a) Tìm phổ DFT của chuỗi tuần hoàn với chu kỳ N = 10 (b) Bây giờ chuỗi được thêm không vào cuối để chiều dài từ 10 thành 20. Tìm phổ DFT sau khi thêm không. Giải (a) DFT của chuỗi tuần hoàn là Bằng cách sử dụng chuỗi hình học ta có Phổ biên độ Và phổ pha 0 , Otherwise Phổ được vẽ trong hình 8.4a 9 (b) Với sự thêm không để tăng từ 10 đến 20 mẫu. Tính toán giống như trong (a) ta có phổ được vẽ trong hình 8.4b Hình 8.4a:Ví dụ 8.15 (tín hiệu và phổ) Hình.8.4b: tiếp ví dụ 8.15 continued (tín hiệu và phổ) 10 8.1.3Dạng ma trận của DFT Ta viết chuỗi tín hiệu vào x(n) và hệ số phổ ngõ ra X(k) trong dạng vector như sau:    T T NXXX Nxxx )1(),...,1(),0( )1(),...,1(),0(   X x Thật ra, x và X là những vector cột 1N nhưng được viết ở dạng chuyển vị. Đầu tiên ta định nghĩa ma trận N×N W là thừa số kn NW :                     2)1(1 11 1,0 ...1 ...1 1...11 N N N N N NN Nnk kn N WW WW W  W (8.17) Ví dụ, với N = 5 ma trận là                  1612840 12963 8642 4321 0000 0 0 0 0 NNNNN NNNN NNNN NNNN NNNN N N N N WWWWW WWWW WWWW WWWW WWWW W W W W W Vì DFT là sự biến đổi tuyến tính mẫu vào x thành phổ ngõ ra X, nên nó có thể diễn tả dạng ma trận như sau: xWX  (8.18a) Từ điều này XWx 1 . Thật ra, ở đây không cần tính nghịch đảo 1W của W , vì tính chất định nghĩa DFT và IDFT, N/*1 WW  . Vì vậy ma trận IDFT là XW N 1 x * (8.18b) Ví dụ 8.1.6 Cho một chuỗi ]0,0,1,[)( 1nx , tìm 4 điểm DFT, sau đó lấy IDFT để phục hồi lại x(n). Giải Sự biến đổi là xX              9 4 6 4 3 4 6 4 4 4 2 4 3 4 2 4 1 4 1 1 1 1111 WWW WWW WWW Từ thuộc tính đối xứng và tuần hoàn (phần 8.2) ta có ,1,,1 6 4 2 4 9 4 1 4 4 4 0 4  WWjWWWW jWand  3 4 . Vì vậy                                            j j jj jj 1 0 1 2 0 0 1 1 11 1111 11 1111 X Đó là (8.16) 11  Tj 1 0, j, - 1 2,X  Bây giờ IDFT là Xx                 9 4 6 4 3 4 6 4 4 4 2 4 3 4 2 4 1 4 1 1 1 1111 4 1 WWW WWW WWW                                            0 0 1 1 1 0 1 2 11 1111 11 1111 4 1 j j jj jj Đây là ]0,0,1,[)( 1nx như mong đợi. 8.2 THUỘC TÍNH CỦA DFT DFT có nhiều thuộc tính giống với DTFT. Tuy nhiên, trong DFT dịch tần số và thời gian thì không tuyến tính nhưng vòng, điều này làm DFT có nhiều thuộc tính phức tạp. 8.2.4 Tuần hòan Tín hiệu x(n) (hoặc đáp ứng xung h(n)) có chiều dài hữu hạn N (có những mẫu n = 0 đến n = N - 1) DFT X(k) (hoặc đáp ứng tần số H(k) tuần hoàn với chu kỳ N, nghĩa là, sự biến đổi trong dải 10  Nk ) được lặp lại bên ngoài dải. Thuộc tính tuần hoàn có thể diễn tả về mặt toán học như    ,...,,i 21,X(k)iNkX (8.19) Ngược lại, khi X(k) có chiều dài hữu hạn, IDFT x(n) tuần hoàn với chu kỳ N. 8.2.4 Tuyến tính DFT là một toán hạng tuyến tính. Xét hai chuỗi số x1(n) và x2(n) có cùng chiều dài thì sự tuyến tính có nghĩa )(kbX(k)aX(n)bx(n)ax 2121  (8.20)Với a và a và b là những hằng số. Thuộc tính tuyến tính có thể diễn tả như: DFT là sự kết nối tuyến tính của nhiều tín hiệu cũng có DFT tuyến tính 8.2.4 Đối xứng (với tín hiệu thực) Xét trường hợp tín hiệu thực thì từ định nghĩa DFT là đối xứng 10,  Nk(k)Xk)X(N * (8.21) Từ định nghĩa của DFT ta có Nk N N n kn N N n nkN N WWnxWnxkNX         1 0 1 0 )( )()()(     1 0 )( N n kn NWnx Như ta biết từ (8.12d) 1*  NN WW , vì vậy nếu x(n) thực phần bên phải của công thức trên là )( * kX Nếu x(n) thực thì X(0) cũng thực vì vậy )0()( *XNX  cũng thực. Sự đối xứng này còn được gọi là liên hiệp phức đối xứng. 12 Quan trọng hơn, khi N chẵn, thường là mũ của 2, DFT X(k) sẽ là một hàm đối xứng của k qua điểm giữa N/2 ( nhìn lại ví dụ 8.1.2), đặc biệt, phổ biên độ đối xứng chẵn và phổ pha đối xứng lẻ qua điểm giữa. 2 0, 22 N kk N Xk N X              (8.22a) 2 0, 22 N kk N k N              (8.22b) Thật ra CTFT (3.16) và DTFT (3.44) cũng thể hiện thuộc tính đối xứng. Vì vậy với tín hiệu có giá trị thực ta chỉ cần tính nửa bên phải đầu tiên của X(k). Nếu N lẻ đối xứng có giá trị là một nửa số nguyên 0.5N. Hình 8.5 chỉ sự đối xứng của hai trường hợp trên. N chẵn và lẻ. Hình 8.6 minh họa phổ biên độ và pha của tín hiệu thực. Hình. 8.5: Đối xứng của DFT với tín hiệu thực Hình.8.6 : Phổ biên độ và pha DFT 256 điểm của tín hiệu 0 8 0 9 0 1 256( ) . ( . ) , , , ...,n nx n n    8.2.4 Dịch vòng 0 1 2 6 3 4 5 7 k 8 0 1 2 5 3 4 6 k 7 N/2 N-1 N N/2 N-1 N Đối xứng Đối xứng (a) N even (N = 8) (b) N odd (N = 7) 13 Dịch chuyển thời gian của chuỗi x(n), có cả trễ và tới trước, hoặc dịch chuyển tần số của phổ X(k), với k tăng hoặc giảm, là một dịch vòng, không phải dịch tuyến tính, vì x(n) và sự mở rộng tuần hoàn của nó và X(k) thì tuần hoàn tại chu kỳ N. Xét một chuỗi x(n) bao gồm những mẫu từ x(0) đến x(N-1). Một dịch tới trước nghĩa là dịch sang phải 1 mẫu, chuỗi mới sẽ bắt đầu từ x(1) đến x(N) với X(N) = x(0) vì sự tuần hoàn. Dịch tiếp tục cho chuỗi từ x(2) đến x(N+1 với x(N) = x(0), và x(N+1) = x(1)Sử dụng cánh minh họa dịch vòng để minh họa những mẫu được sắp xếp quanh một đường tròn với gốc thời gian (n = 0) cố định. Hình. 4minh họa điều này Xét x(n) là một chuỗi với chiều dài hữu hạn N trong khoảng ]1,0[ N và không bên ngoài. Một chuỗi tuần hoàn xp(n) được hình thành từ x(n) như sau xp(n) = x(n mod N) (Mở rộng tuần hoàn) (8.23) Với mod N là toán hạng module, mà được định nghĩa như ,...,,i 210 N,iNn0Nmodn (8.24) Với n dương, toán tử module là phần dư sau khi chia n cho N, ví du 0 mode 3 = 0 , 1 mod 3 = 1, 2 mod 3 = 2, 3 mod 3 = 0, 4 mod 3 = 1, 9 mod 3 = 0, 11 mod 3 = 2 Với n dương chọn dấu để NiNn 0 , ví dụ (for N = 3) 4 mod 3 = 4 – 3 = 1, 9 mod 3 = 9 – 3N = 0, 11 mod 3 = 11 – 3N = 2 Với n âm chọn dấu để 0 < n + iN < N, ví dụ (for N = 3) 4 mod 3 = 4 – 3 =1, 9 mod 3 = 9 – 3N = 0, 11 mod 3 = 11 – 3N = 2 Với n âm ta chọn dấu để NiNn 0 , ví dụ (for N = 3) (-1) mod 3 = -1 + N = 2, (-2) mod 3 = -2 + N = 1, (-3) mod 3 = -3 + N = 0 (-4) mod 3 = -4 + 2N = 2, (-5) mod 3 = -5 + 2N = 1, (-9) mod 3 = -9 + 3N = 0 Hình 8.8 minh họa sự hoạt động n mod 3. Chú ý rằng kết quả thì tuần hoàn với chu kỳ 3 x(2) 0 -1 x(3) x(2) x(0) x(1) x(2) x(1) x(3) x(0) x(n) 0 1 2 3 -1 0 1 2 3 4 n 0 1 2 x(n)