Biến đổi Fourier rời rạc

Trong lĩnh vực toán học, biến đổi Fourier rời rạc (DFT), đôi khi gọi là biến đổi Fourier có giới hạn, là một công cụ trong phân tích Fourier được áp dụng cho các tín hiệu rời rạc về mặt thời gian. Phép biến đổi này nhận đầu vào là một chuỗi có số lượng hữu hạn các số thực hoặc số phức, làm cho nó trở thành công cụ lý tưởng cho xử lý thông tin trên máy tính. Đặc biệt, biến đổi này rất phổ biến trong xử lý tín hiệu và các ứng dụng phân tích tần số trong tín hiệu, để giải phương trình đạo hàm riêng và thực hiện các phép toán như tích chập. Biến đổi này có thể được tính toán nhanh chóng bằng thuật toán biến đổi Fourier nhanh (FFT).

Khái niệm cơ bản

Một dãy gồm N số phức: $x_0,...,x_{N-<!--\; -\; -->1}$ sẽ được chuyển đổi thành một chuỗi gồm N số phức X₀,..., X_N−1 theo công thức dưới đây:

với e là cơ số của lôgarit tự nhiên, $i$ là đơn vị ảo ($i^2=-<!--\; -\; -->1$), và π là số pi. Phép biến đổi đôi khi được ký hiệu bởi $F$, như sau $X=F\left\{x\right\}$ hoặc $F\left(x\right)$ hoặc $Fx$.

Công thức của phép biến đổi Fourier rời rạc ngược (IDFT) được trình bày như sau

Các phương trình này có thể được mô tả đơn giản như sau: các số phức Xk thể hiện biên độ và pha ở các bước sóng khác nhau của 'tín hiệu đầu vào' xn. Phép biến đổi DFT tính toán các giá trị Xk từ các giá trị xn, trong khi IDFT tính xn bằng cách tổng hợp các sóng thành phần với tần số k / N. Bằng cách viết các phương trình theo dạng này, ta đã sử dụng công thức Euler để chuyển các hàm lượng giác thành các số phức lũy thừa để dễ dàng thực hiện biến đổi. Khi biểu diễn Xk dưới dạng tọa độ cực, ta có được biên độ Ak / N và pha φk từ modulus và argument của Xk:

$A_k=|X_k|=\sqrt{\mathrm{Re}<!--\; \; -->(X_k{)}^2+\mathrm{Im}<!--\; \; -->(X_k{)}^2},$

Trong đó, hàm atan2 là phiên bản hai đối số của hàm arctan. Cần lưu ý rằng các hệ số chuẩn hóa trong DFT và IDFT (ở đây là 1 và 1/N) cũng như dấu của các số mũ chỉ là quy ước, và có thể khác nhau trong các tài liệu khác nhau. Điều kiện duy nhất cho các quy ước này là DFT và IDFT phải có dấu ngược nhau ở các số mũ và tích của hai hệ số chuẩn hóa phải là 1/N.

Các đặc tính

Toàn diện

Biến đổi Fourier rời rạc là một phép biến đổi tuyến tính có thể đảo ngược

$F:<!--\; :\; -->C^N\to <!--\; \to \; -->C^N$

Trong đó, C là tập hợp các số phức. Nói cách khác, với mọi N lớn hơn 0, mọi vectơ phức có chiều dài N đều có thể được chuyển đổi bằng DFT và IDFT, và kết quả cũng sẽ là các vectơ phức có chiều dài N.

Trực giao

Các vectơ tạo nên một cơ sở trực giao cho không gian các vectơ phức chiều N:

Trong đó, ${\mathrm{\delta <!--\; \delta \; -->}}_{k{k}^{\prime }}$ là hàm delta Kronecker. Điều kiện trực giao này cho phép suy ra công thức cho IDFT từ định nghĩa của DFT, và cũng tương đương với điều kiện đơn vị dưới đây.

Định lý Plancherel và định lý Parseval

Nếu X_k và Y_k là các biến đổi Fourier rời rạc (DFT) của x_n và y_n, thì theo định lý Plancherel:

với ký hiệu dấu sao chỉ số phức liên hợp. Định lý Parseval là một dạng đặc biệt của định lý Plancherel:

Các định lý dưới đây tương đương với điều kiện unita.

Chu kỳ

Nếu chúng ta tính biểu thức định nghĩa DFT cho mọi số nguyên k, không chỉ cho k=0,..., N-1, thì dãy số thu được sẽ là một mở rộng tuần hoàn của DFT với chu kỳ N.

Sự tuần hoàn có thể được chứng minh trực tiếp từ định nghĩa:

$X_{k+N}\stackrel{}{=}$

d e f   ∑ n = 0 N − 1 x n e − 2 π i N ( k + N ) n = ∑ n = 0 N − 1 x n e − 2 π i N k n e − 2 π i n ⏟ 1 = ∑ n = 0 N − 1 x n e − 2 π i N k n = X k . {\displaystyle X_{k+N}\ {\stackrel {\mathrm {def} }{=}}\ \sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}(k+N)n}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}kn}\underbrace {e^{-2\pi in}} _{1}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}kn}=X_{k}.}

Tương tự, biểu thức của IDFT cũng tạo ra một dãy số tuần hoàn mở rộng.

Định lý dịch pha

Việc nhân các giá trị xn với một pha tuyến tính $e^{\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}nm}$ (với m là một số nguyên) tương đương với việc dịch các số Xk: Xk được thay bằng Xk-m, với các chỉ số được tính theo mô đun N. Ngược lại, dịch vòng tròn các giá trị xn sẽ dẫn đến việc nhân các số Xk với một pha tuyến tính. Nếu {xn} đại diện cho vectơ x thì

nếu $F\left(\right\{x_n\}{)}_k=X_k$

thì $F\left(\right\{x_n\cdot <!--\; \cdot \; -->e^{\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}nm}\}{)}_k=X_{k-<!--\; -\; -->m}$

và $F\left(\right\{x_{n-<!--\; -\; -->m}\}{)}_k=X_k\cdot <!--\; \cdot \; -->e^{-<!--\; -\; -->\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}km}$

Đơn vị

Như đã nêu ở trên, toán tử DFT có thể được biểu diễn dưới dạng một ma trận Vandermonde.

và

${\mathrm{\omega <!--\; \omega \; -->}}_N=e^{-<!--\; -\; -->2\mathrm{\pi <!--\; \pi \; -->}i/N}$

là căn nguyên bậc N của đơn vị. Ma trận nghịch đảo của phép biến đổi này chính là ma trận của phép biến đổi ngược:

$F^{-<!--\; -\; -->1}=\frac{1}{N}{F}^{\ast <!--\; \ast \; -->}$

Với hằng số chuẩn hóa unita $1/\sqrt{N}$, DFT trở thành một phép biến đổi unita, được định nghĩa bởi ma trận unita:

$U=F/\sqrt{N}$

$U^{-<!--\; -\; -->1}=U^{\ast <!--\; \ast \; -->}$

$|det\left(U\right)|=1$

Trong đó, det() là hàm tính định thức. Định thức được tính bằng tích của các giá trị riêng, có thể là $\pm <!--\; \pm \; -->1$ hoặc $\pm <!--\; \pm \; -->i$, như được mô tả dưới đây. Trong không gian vectơ thực, phép biến đổi unita có thể coi là một phép quay không thay đổi hệ tọa độ, và tất cả các đặc tính của phép quay vật rắn đều áp dụng cho toán tử unita DFT.

Tính chất trực giao của DFT giờ có thể được diễn đạt bằng điều kiện trực chuẩn:

$\underset{m=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{U}_{km}{U}_{mn}^{\ast <!--\; \ast \; -->}={\mathrm{\delta <!--\; \delta \; -->}}_{kn}$

Nếu X được xác định là DFT unita của vectơ x, thì

$X_k=\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{U}_{kn}{x}_n$

Định lý Plancherel có thể được biểu diễn dưới dạng sau:

$\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{x}_n{y}_n^{\ast <!--\; \ast \; -->}=\underset{k=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{X}_k{Y}_k^{\ast <!--\; \ast \; -->}$

Khi coi DFT chỉ là một phép biến đổi tọa độ, mệnh đề này cho thấy rằng tích vô hướng của hai vectơ không thay đổi trong biến đổi unita DFT. Đặc biệt, nếu x=y, thì độ dài của vectơ cũng được bảo toàn—đây chính là định lý Parseval:

$\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}|x_n{|}^2=\underset{k=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}|X_k{|}^2$

Ứng dụng

DFT được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau. Dưới đây là một số ví dụ tiêu biểu (xem thêm tài liệu tham khảo ở cuối trang). Tất cả các ứng dụng của DFT đều dựa trên tính chất quan trọng là cả DFT và IDFT đều có thể được tính toán nhanh chóng nhờ thuật toán biến đổi Fourier nhanh.

Phân tích phổ

Khi sử dụng DFT để phân tích phổ, dãy {x_n} thường biểu thị một chuỗi hữu hạn các mẫu tại những thời điểm đều đặn của tín hiệu x(t), trong đó t là thời gian. Việc chuyển đổi từ thời gian liên tục sang mẫu (thời gian rời rạc) biến đổi Fourier liên tục của x(t) thành biến đổi Fourier thời gian rời rạc (DTFT), và thường gây ra hiện tượng răng cưa. Việc chọn tần số lấy mẫu phù hợp (xem tần số Nyquist) là rất quan trọng để giảm thiểu hiện tượng này.

Một số tài liệu về biến đổi Fourier rời rạc

• Brigham, E. Oran (1988). The fast Fourier transform and its applications. Englewood Cliffs, N.J.: Prentice Hall. ISBN 0-13-307505-2.
• Oppenheim, Alan V.; Schafer, R. W.; và Buck, J. R. (1999). Discrete-time signal processing. Upper Saddle River, N.J.: Prentice Hall. ISBN 0-13-754920-2.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)
• Smith, Steven W. (1997). The Scientist and Engineer's Guide to Digital Signal Processing. San Diego, Calif.: California Technical Publishing. ISBN 0-9660176-3-3.
• Cormen, Thomas H. (2001). “Chapter 30: Polynomials and the FFT”. Introduction to Algorithms. Charles E. Leiserson, Ronald L. Rivest, và Clifford Stein . MIT Press và McGraw-Hill. tr. 822–848. ISBN 0-262-03293-7. đặc biệt là mục 30.2: DFT và FFT, tr. 830–838.
• P. Duhamel, B. Piron, và J. M. Etcheto (1988). “Về việc tính toán DFT ngược”. IEEE Trans. Acoust., Speech and Sig. Processing. 36 (2): 285–286.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)
• J. H. McClellan và T. W. Parks (1972). “Giá trị riêng và vectơ riêng của biến đổi Fourier rời rạc”. IEEE Trans. Audio Electroacoust. 20 (1): 66–74.
• Bradley W. Dickinson và Kenneth Steiglitz (1982). “Vectơ riêng và hàm số của biến đổi Fourier rời rạc”. IEEE Trans. Acoust., Speech and Sig. Processing. 30 (1): 25–31.
• F. A. Grünbaum (1982). “Các vectơ riêng của biến đổi Fourier rời rạc”. J. Math. Anal. Appl. 88 (2): 355–363.
• Natig M. Atakishiyev và Kurt Bernardo Wolf (1997). “Biến đổi Fourier-Kravchuk phân số”. J. Opt. Soc. Am. A. 14 (7): 1467–1477.
• C. Candan, M. A. Kutay và H. M.Ozaktas (2000). “Biến đổi Fourier phân số rời rạc”. IEEE Trans. On Signal Processing. 48 (5): 1329–1337.
• Magdy Tawfik Hanna, Nabila Philip Attalla Seif, và Waleed Abd El Maguid Ahmed (2004). “Các vectơ riêng kiểu Hermite-Gaussian của ma trận biến đổi Fourier rời rạc dựa trên phân rã giá trị kỳ dị của các ma trận chiếu trực giao của nó”. IEEE Trans. Circ. Syst. I. 51 (11): 2245–2254.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)
• Juan G. Vargas-Rubio và Balu Santhanam (2005). “Về biến đổi Fourier phân số tại nhiều góc trung tâm”. IEEE Sig. Proc. Lett. 12 (4): 273–276.
• J. Cooley, P. Lewis, và P. Welch (1969). “Biến đổi Fourier hữu hạn”. IEEE Trans. Audio Electroacoustics. 17 (2): 77–85.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)

Các liên kết hữu ích

• Sách 'Mathematics of the Discrete Fourier Transform' của Julius O. Smith III
• Triển khai nhanh DFT - mã nguồn viết bằng C và dưới Giấy phép Công cộng Tổng quát (GPL)