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

Trong toán học, phép biến đổi Fourier rời rạc (DFT), đôi khi còn được gọi là biến đổi Fourier hữu hạn, là một biến đổi trong giải tích Fourier cho các tín hiệu thời gian rời rạc. Đầu vào của biến đổi này là một chuỗi hữu hạn các số thực hoặc số phức, làm biến đổi này là một công cụ lý tưởng để xử lý thông tin trên các máy tính. Đặc biệt, biến đổi này được sử dụng rộng rãi trong xử lý tín hiệu và các ngành liên quan đến phân tích tần số chứa trong một tín hiệu, để giải phương trình đạo hàm riêng, và để làm các phép như tích chập. Biến đổi này có thể được tính nhanh bởi thuật toán biến đổi Fourier nhanh (FFT). Dãy của N số phức: x 0 , . . . , x N − 1 {\displaystyle x_{0},...,x_{N-1}} được biến đổi thành chuỗi của N số phức X0,..., XN−1 bởi công thức sau đây: X k = ∑ n = 0 N − 1 x n e − 2 π i N k n k = 0 , … , N − 1 {\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}kn}\quad \quad k=0,\dots ,N-1} với e là cơ số của lôgarit tự nhiên, i {\displaystyle i\,} là đơn vị ảo ( i 2 = − 1 {\displaystyle i^{2}=-1} ), và π là pi. Phép biến đổi đôi khi được ký hiệu bởi F {\displaystyle {\mathcal {F}}} , như sau X = F { x } {\displaystyle \mathbf {X} ={\mathcal {F}}\left\{\mathbf {x} \right\}} hoặc F ( x ) {\displaystyle {\mathcal {F}}\left(\mathbf {x} \right)} hoặc F x {\displaystyle {\mathcal {F}}\mathbf {x} } . Phép biến đổi Fourier rời rạc ngược (IDFT) được cho bởi công thức sau x n = 1 N ∑ k = 0 N − 1 X k e 2 π i N k n n = 0 , … , N − 1. {\displaystyle x_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}e^{{\frac {2\pi i}{N}}kn}\quad \quad n=0,\dots ,N-1.} Những phương trình này có thể được mô tả đơn giản như sau: các số phức Xk đại diện cho biên độ và pha ở các bước sóng khác nhau của "tín hiệu vào" xn. Phép biến đổi DFT tính các giá trị Xk từ các giá trị xn, trong khi IDFT tính xn bằng tổng của các sóng thành phần 1 N X k e 2 π i N k n {\displaystyle {\frac {1}{N}}X_{k}e^{{\frac {2\pi i}{N}}kn}} với tần số k / N. Khi viết các phương trình dưới dạng như trên, ta đã sử dụng công thức Euler để biểu diễn các hàm lượng giác dưới dạng lũy thừa số phức để biến đổi được dễ dàng. Khi viết Xk dưới dạng tọa độ cực, ta thu được biên độ Ak / N và pha φk từ modulus và argument của Xk: A k = | X k | = Re ⁡ ( X k ) 2 + Im ⁡ ( X k ) 2 , {\displaystyle A_{k}=|X_{k}|={\sqrt {\operatorname {Re} (X_{k})^{2}+\operatorname {Im} (X_{k})^{2}}},} φ k = arg ⁡ ( X k ) = atan2 ⁡ ( Im ⁡ ( X k ) , Re ⁡ ( X k ) ) , {\displaystyle \varphi _{k}=\arg(X_{k})=\operatorname {atan2} {\big (}\operatorname {Im} (X_{k}),\operatorname {Re} (X_{k}){\big )},} trong đó atan2 là dạng hai đối số của hàm arctan. Cần ghi chú rằng các thừa số chuẩn hóa của DFT và IDFT (ở đây là 1 và 1/N) và 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 có dấu ngược nhau ở các số mũ và tích của hai thừa số chuẩn hóa phải là 1/N. Phép biến đổi Fourier rời rạc là một biến đổi tuyến tính khả nghịch F : C N → C N {\displaystyle {\mathcal {F}}\colon \mathbb {C} ^{N}\to \mathbb {C} ^{N}} trong đó C ký hiệu tập các số phức. Nói cách khác, với mọi N > 0, mọi vectơ phức N chiều đều có một DFT và một IDFT, và chúng đều là các vectơ phức N chiều. Các vectơ e 2 π i N k n {\displaystyle e^{{\frac {2\pi i}{N}}kn}} tạo thành một cơ sở trực giao của tập các vectơ phức N chiều: ∑ n = 0 N − 1 ( e 2 π i N k n ) ( e − 2 π i N k ′ n ) = N   δ k k ′ {\displaystyle \sum _{n=0}^{N-1}\left(e^{{\frac {2\pi i}{N}}kn}\right)\left(e^{-{\frac {2\pi i}{N}}k'n}\right)=N~\delta _{kk'}} trong đó δ k k ′ {\displaystyle \delta _{kk'}} là hàm delta Kronecker. Có thể dùng điều kiện trực giao để suy ra công thức cho IDFT từ định nghĩa của DFT, và điều kiện này tương đương với điều kiện unita dưới đây. Nếu Xk và Yk là các DFT của xn và yn thì theo định lý Plancherel: ∑ n = 0 N − 1 x n y n ∗ = 1 N ∑ k = 0 N − 1 X k Y k ∗ {\displaystyle \sum _{n=0}^{N-1}x_{n}y_{n}^{*}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}Y_{k}^{*}} trong đó dấu sao ký hiệu số phức liên hợp. Định lý Parseval là một trường hợp đặc biệt của định lý Plancherel: ∑ n = 0 N − 1 | x n | 2 = 1 N ∑ k = 0 N − 1 | X k | 2 . {\displaystyle \sum _{n=0}^{N-1}|x_{n}|^{2}={\frac {1}{N}}\sum _{k=0}^{N-1}|X_{k}|^{2}.} Các định lý này tương đương với điều kiện unita dưới đây. Nếu như ta tính biểu thức định nghĩa DFT tại mọi số nguyên k thay vì chỉ cho k=0,..., N-1, thì dãy số nhận được là một mở rộng tuần hoàn của DFT, và có chu kì N. Tính tuần hoàn có được chứng minh trực tiếp từ định nghĩa: X k + N   = 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ự như vậy, biểu thức của IDFT cũng cho một dãy mở rộng tuần hoàn. Việc nhân các số xn với một pha tuyến tính e 2 π i N n m {\displaystyle e^{{\frac {2\pi i}{N}}nm}} (m là một số nguyên bất kì) tương ứng với việc dịch vòng tròn các số Xk: Xk được thay bằng Xk-m, trong đó các chỉ số được tính theo mô đun N. Tương tự như vậy, việc dịch vòng tròn các số xn tương ứng với việc nhân các số Xk với một pha tuyến tính. Dưới dạng công thức, nếu {xn} đại diện cho vectơ x thì nếu F ( { x n } ) k = X k {\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}} thì F ( { x n ⋅ e 2 π i N n m } ) k = X k − m {\displaystyle {\mathcal {F}}(\{x_{n}\cdot e^{{\frac {2\pi i}{N}}nm}\})_{k}=X_{k-m}} và F ( { x n − m } ) k = X k ⋅ e − 2 π i N k m {\displaystyle {\mathcal {F}}(\{x_{n-m}\})_{k}=X_{k}\cdot e^{-{\frac {2\pi i}{N}}km}} Có thể nhận thấy theo mô tả ở trên, toán tử DFT có thể được biểu diễn dưới dạng một ma trận Vandermonde: F = [ ω N 0 ⋅ 0 ω N 0 ⋅ 1 … ω N 0 ⋅ ( N − 1 ) ω N 1 ⋅ 0 ω N 1 ⋅ 1 … ω N 1 ⋅ ( N − 1 ) ⋮ ⋮ ⋱ ⋮ ω N ( N − 1 ) ⋅ 0 ω N ( N − 1 ) ⋅ 1 … ω N ( N − 1 ) ⋅ ( N − 1 ) ] {\displaystyle \mathbf {F} ={\begin{bmatrix}\omega _{N}^{0\cdot 0}&\omega _{N}^{0\cdot 1}&\ldots &\omega _{N}^{0\cdot (N-1)}\\\omega _{N}^{1\cdot 0}&\omega _{N}^{1\cdot 1}&\ldots &\omega _{N}^{1\cdot (N-1)}\\\vdots &\vdots &\ddots &\vdots \\\omega _{N}^{(N-1)\cdot 0}&\omega _{N}^{(N-1)\cdot 1}&\ldots &\omega _{N}^{(N-1)\cdot (N-1)}\\\end{bmatrix}}} trong đó ω N = e − 2 π i / N {\displaystyle \omega _{N}=e^{-2\pi i/N}\,} là một căn nguyên thủy bậc N của đơn vị. Phép biến đổi ngược chính là ma trận nghịch đảo của ma trận trên: F − 1 = 1 N F ∗ {\displaystyle \mathbf {F} ^{-1}={\frac {1}{N}}\mathbf {F} ^{*}} Với hằng số chuẩn hóa unita 1 / N {\displaystyle 1/{\sqrt {N}}} , DFT trở thành một biến đổi unita, định nghĩa bởi một ma trận unita: U = F / N {\displaystyle \mathbf {U} =\mathbf {F} /{\sqrt {N}}} U − 1 = U ∗ {\displaystyle \mathbf {U} ^{-1}=\mathbf {U} ^{*}} | det ( U ) | = 1 {\displaystyle |\det(\mathbf {U} )|=1} trong đó det() là hàm tính định thức. Định thức là tích của các giá trị riêng (luôn là ± 1 {\displaystyle \pm 1} hoặc ± i {\displaystyle \pm i} như mô tả dưới đây). Trong không gian vectơ thực, một biến đổi unita có thể xem là phép quay vật rắn của hệ tọa độ, và tất cả các tính chất của phép quay vật rắn đều đúng cho toán tử unita DFT. Tính trực giao của DFT nay có thể viết dưới dạng điều kiện trực chuẩn: ∑ m = 0 N − 1 U k m U m n ∗ = δ k n {\displaystyle \sum _{m=0}^{N-1}U_{km}U_{mn}^{*}=\delta _{kn}} Nếu X được định nghĩa là unita DFT của vectơ x thì X k = ∑ n = 0 N − 1 U k n x n {\displaystyle X_{k}=\sum _{n=0}^{N-1}U_{kn}x_{n}} và định lý Plancherel có thể viết dưới dạng: ∑ n = 0 N − 1 x n y n ∗ = ∑ k = 0 N − 1 X k Y k ∗ {\displaystyle \sum _{n=0}^{N-1}x_{n}y_{n}^{*}=\sum _{k=0}^{N-1}X_{k}Y_{k}^{*}} Nếu ta coi DFT chỉ là một phép biến đổi tọa độ trong đó chỉ cần chỉ ra các thành phần của vectơ trong hệ tọa độ mới, thì mệnh đề trên chỉ nói rằng tích vô hướng của hai vectơ được giữ nguyên trong phép biến đổi unita DFT. Trong trường hợp đặc biệt khi x=y, điều này có nghĩa là độ dài vectơ cũng được giữ nguyên—đây chính là định lý Parseval: ∑ n = 0 N − 1 | x n | 2 = ∑ k = 0 N − 1 | X k | 2 {\displaystyle \sum _{n=0}^{N-1}|x_{n}|^{2}=\sum _{k=0}^{N-1}|X_{k}|^{2}} DFT có nhiều ứng dụng rộng rãi trong nhiều ngành khác nhau. Ở đây chỉ mô tả một số ví dụ (tham khảo thêm các tài liệu ở cuối trang). Tất cả các ứng dụng của DFT đều dựa trên một tính chất quan trọng là DFT và IDFT đều có thể được tính nhanh chóng bằng thuật toán biến đổi Fourier nhanh. Khi sử dụng DFT để phân tích phổ, dãy {x_n} thường đại diện cho một dãy hữu hạn các mẫu tại các thời điểm cách đều nhau của một tín hiệu x(t), trong đó t để chỉ thời gian. Việc chuyển từ thời gian liên tục sang mẫu (thời gian rời rạc) chuyển 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ệu ứng răng cưa. Việc chọn lựa tần số lấy mẫu thích hợp (xem tần số Nyquist) là vô cùng quan trọng cho việc giảm thiểu hiệu ứng này. 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.; and 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, and Clifford Stein . MIT Press and McGraw-Hill. tr. 822–848. ISBN 0-262-03293-7. esp. section 30.2: The DFT and FFT, pp. 830–838. P. Duhamel, B. Piron, and J. M. Etcheto (1988). “On computing the inverse DFT”. 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 and T. W. Parks (1972). “Eigenvalues and eigenvectors of the discrete Fourier transformation”. IEEE Trans. Audio Electroacoust. 20 (1): 66–74. Bradley W. Dickinson and Kenneth Steiglitz (1982). “Eigenvectors and functions of the discrete Fourier transform”. IEEE Trans. Acoust., Speech and Sig. Processing. 30 (1): 25–31. F. A. Grünbaum (1982). “The eigenvectors of the discrete Fourier transform”. J. Math. Anal. Appl. 88 (2): 355–363. Natig M. Atakishiyev and Kurt Bernardo Wolf (1997). “Fractional Fourier-Kravchuk transform”. J. Opt. Soc. Am. A. 14 (7): 1467–1477. C. Candan, M. A. Kutay and H. M.Ozaktas (2000). “The discrete fractional Fourier transform”. IEEE Trans. On Signal Processing. 48 (5): 1329–1337. Magdy Tawfik Hanna, Nabila Philip Attalla Seif, and Waleed Abd El Maguid Ahmed (2004). “Hermite-Gaussian-like eigenvectors of the discrete Fourier transform matrix based on the singular-value decomposition of its orthogonal projection matrices”. 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 and Balu Santhanam (2005). “On the multiangle centered discrete fractional Fourier transform”. IEEE Sig. Proc. Lett. 12 (4): 273–276. J. Cooley, P. Lewis, and P. Welch (1969). “The finite Fourier transform”. 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) Mathematics of the Discrete Fourier Transform by Julius O. Smith III Fast implementation of the DFT - coded in C and under General Public License (GPL)