Hàm này tính toán Biến đổi Fourier rời rạc n điểm (DFT) một chiều bằng thuật toán Biến đổi Fourier nhanh (FFT) hiệu quả [CT] Show
Mảng đầu vào, có thể phức tạp n int, tùy chọnChiều dài của trục biến đổi của đầu ra. Nếu n nhỏ hơn độ dài của đầu vào, đầu vào sẽ bị cắt. Nếu nó lớn hơn, đầu vào được đệm bằng số không. Nếu n không được cung cấp, độ dài của đầu vào dọc theo trục được chỉ định bởi axis được sử dụng trục int, tùy chọnTrục để tính toán FFT. Nếu không được cung cấp, trục cuối cùng được sử dụng chuẩn {"lùi", "ortho", "chuyển tiếp"}, tùy chọnMới trong phiên bản 1. 10. 0 Chế độ chuẩn hóa (xem ). Mặc định là "lùi". Cho biết hướng nào của cặp biến đổi tiến/lùi được chia tỷ lệ và với hệ số chuẩn hóa nào Mới trong phiên bản 1. 20. 0. Các giá trị “lùi”, “chuyển tiếp” đã được thêm vào. Trả về . ra ndarray phức tạpĐầu vào bị cắt bớt hoặc không đệm, được chuyển đổi dọc theo trục được chỉ định bởi trục hoặc đầu vào cuối cùng nếu trục không được chỉ định Tăng . Chỉ mụcLỗiNếu trục không phải là trục hợp lệ của một Xem thêm để biết định nghĩa về DFT và các quy ước được sử dụng nghịch đảo của FFT hai chiều FFT n chiều FFT n chiều của đầu vào thực Ngăn tần số cho các tham số FFT đã cho ghi chú FFT (Biến đổi Fourier nhanh) đề cập đến cách có thể tính toán Biến đổi Fourier rời rạc (DFT) một cách hiệu quả, bằng cách sử dụng các phép đối xứng trong các thuật ngữ được tính toán. Tính đối xứng cao nhất khi n là lũy thừa của 2 và do đó phép biến đổi hiệu quả nhất đối với các kích thước này DFT được xác định, với các quy ước được sử dụng trong quá trình triển khai này, trong tài liệu dành cho mô-đun Người giới thiệu [ CT ] Cooley, James W. , và John W. Tukey, 1965, “Một thuật toán để tính toán bằng máy các chuỗi Fourier phức,” Math. máy tính. 19. 297-301 ví dụ >>> np.fft.fft(np.exp(2j * np.pi * np.arange(8) / 8)) array([-2.33486982e-16+1.14423775e-17j, 8.00000000e+00-1.25557246e-15j, 2.33486982e-16+2.33486982e-16j, 0.00000000e+00+1.22464680e-16j, -1.14423775e-17+2.33486982e-16j, 0.00000000e+00+5.20784380e-16j, 1.14423775e-17+1.14423775e-17j, 0.00000000e+00+1.22464680e-16j]) Trong ví dụ này, đầu vào thực có FFT là Hermiti, i. e. , đối xứng trong phần thực và phản đối xứng trong phần ảo, như được mô tả trong tài liệu Biến đổi Fourier nhanh (FFT) là một trong những thuật toán quan trọng nhất trong xử lý tín hiệu và phân tích dữ liệu. Tôi đã sử dụng nó trong nhiều năm, nhưng không có kiến thức cơ bản về khoa học máy tính, tuần này tôi chợt nhận ra rằng tôi chưa bao giờ nghĩ sẽ hỏi làm thế nào FFT tính toán biến đổi Fourier rời rạc nhanh như vậy. Tôi phủi bụi một cuốn sách thuật toán cũ và xem xét nó, đồng thời rất thích đọc về thủ thuật tính toán tưởng chừng đơn giản mà JW Cooley và John Tukey đã vạch ra trong bài báo cổ điển năm 1965 của họ giới thiệu về chủ đề này. Mục tiêu của bài đăng này là đi sâu vào thuật toán Cooley-Tukey FFT, giải thích các đối xứng dẫn đến thuật toán này và chỉ ra một số triển khai Python đơn giản đưa lý thuyết vào thực tế. Tôi hy vọng rằng khám phá này sẽ cung cấp cho các nhà khoa học dữ liệu như tôi một bức tranh hoàn chỉnh hơn về những gì đang diễn ra trong nền tảng của các thuật toán mà chúng tôi sử dụng Biến đổi Fourier rời rạcFFT là một thuật toán $\mathcal{O}[N\log N]$ nhanh, để tính toán Biến đổi Fourier rời rạc (DFT), vốn là một phép tính $\mathcal{O}[N^2]$. DFT, giống như phiên bản liên tục quen thuộc hơn của biến đổi Fourier, có dạng thuận và nghịch được định nghĩa như sau Biến đổi Fourier rời rạc chuyển tiếp (DFT). $$X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i~2\pi~k~n~/~N}$$ Biến đổi Fourier rời rạc nghịch đảo (IDFT). $$x_n = \frac{1}{N}\sum_{k=0}^{N-1} X_k e^{i~2\pi~k~n~/~N}$$ Phép biến đổi từ $x_n \sang X_k$ là phép dịch từ không gian cấu hình sang không gian tần số và có thể rất hữu ích trong cả việc khám phá phổ công suất của tín hiệu và cũng để chuyển đổi một số vấn đề nhất định để tính toán hiệu quả hơn. Để biết một số ví dụ về thực tế này, bạn có thể xem Chương 10 của cuốn sách Thiên văn học/Thống kê sắp ra mắt của chúng tôi, với các số liệu và mã nguồn Python có sẵn tại đây. Để biết ví dụ về FFT được sử dụng để đơn giản hóa việc tích hợp phương trình vi phân khó khăn khác, hãy xem bài đăng của tôi về Giải phương trình Schrodinger bằng Python Do tầm quan trọng của FFT trong rất nhiều lĩnh vực, Python chứa nhiều công cụ và trình bao bọc tiêu chuẩn để tính toán điều này. Cả NumPy và SciPy đều có các trình bao bọc của thư viện FFTPACK đã được thử nghiệm cực kỳ tốt, được tìm thấy trong các mô-đun con x = np.random.random(1024) np.allclose(DFT_slow(x), np.fft.fft(x))5 và x = np.random.random(1024) np.allclose(DFT_slow(x), np.fft.fft(x))6 tương ứng. FFT nhanh nhất mà tôi biết là trong gói FFTW, cũng có sẵn trong Python thông qua gói PyFFTW Tuy nhiên, hiện tại, chúng ta hãy tạm gác những triển khai này sang một bên và hỏi cách chúng ta có thể tính toán FFT trong Python từ đầu Tính toán biến đổi Fourier rời rạcĐể đơn giản, chúng ta sẽ chỉ quan tâm đến phép biến đổi thuận, vì phép biến đổi nghịch đảo có thể được thực hiện theo cách rất giống nhau. Nhìn vào biểu thức DFT ở trên, chúng ta thấy rằng nó không gì khác hơn là một phép toán tuyến tính đơn giản. phép nhân vectơ-ma trận của $\vec{x}$, $$\vec{X} = M \cdot \vec{x}$$ với ma trận $M$ được cho bởi $$M_{kn} = e^{-i~2\pi~k~n~/~N}. $$ Với suy nghĩ này, chúng ta có thể tính toán DFT bằng cách sử dụng phép nhân ma trận đơn giản như sau Trong 1] import numpy as np def DFT_slow(x): """Compute the discrete Fourier Transform of the 1D array x""" x = np.asarray(x, dtype=float) N = x.shape[0] n = np.arange(N) k = n.reshape((N, 1)) M = np.exp(-2j * np.pi * k * n / N) return np.dot(M, x) Chúng ta có thể kiểm tra lại kết quả bằng cách so sánh với chức năng FFT tích hợp của numpy Trong 2] x = np.random.random(1024) np.allclose(DFT_slow(x), np.fft.fft(x)) Ra[2] True Chỉ để xác nhận sự chậm chạp của thuật toán của chúng tôi, chúng tôi có thể so sánh thời gian thực hiện của hai phương pháp này Trong 3] %timeit DFT_slow(x) %timeit np.fft.fft(x) 10 loops, best of 3: 75.4 ms per loop 10000 loops, best of 3: 25.5 µs per loop Chúng tôi chậm hơn 1000 lần, điều này được mong đợi đối với việc triển khai đơn giản như vậy. Nhưng đó không phải là điều tồi tệ nhất của nó. Đối với vectơ đầu vào có độ dài $N$, thuật toán FFT chia tỷ lệ thành $\mathcal{O}[N\log N]$, trong khi thuật toán chậm của chúng tôi chia tỷ lệ thành $\mathcal{O}[N^2]$. Điều đó có nghĩa là đối với các phần tử $N=10^6$, chúng tôi hy vọng FFT sẽ hoàn thành trong khoảng 50 ms, trong khi thuật toán chậm của chúng tôi sẽ mất gần 20 giờ Vậy FFT thực hiện việc tăng tốc này như thế nào? Đối xứng trong biến đổi Fourier rời rạcMột trong những công cụ quan trọng nhất của người xây dựng thuật toán là khai thác tính đối xứng của một bài toán. Nếu bạn có thể chỉ ra một cách phân tích rằng một phần của vấn đề chỉ liên quan đến phần khác, bạn có thể tính kết quả con chỉ một lần và tiết kiệm chi phí tính toán đó. Cooley và Tukey đã sử dụng chính xác cách tiếp cận này để tạo ra FFT Chúng ta sẽ bắt đầu bằng cách hỏi giá trị của $X_{N+k}$ là bao nhiêu. Từ biểu thức trên của chúng tôi $$ \begin{align*} X_{N + k} &= \sum_{n=0}^{N-1} x_n \cdot e^{-i~2\pi~(N + k)~n~ nơi chúng tôi đã sử dụng danh tính $\exp[2\pi~i~n] = 1$ giữ cho bất kỳ số nguyên nào $n$ Dòng cuối cùng hiển thị một thuộc tính đối xứng đẹp của DFT $$X_{N+k} = X_k. $$ Bằng một phần mở rộng đơn giản, $$X_{k + i \cdot N} = X_k$$ với mọi số nguyên $i$. Như chúng ta sẽ thấy bên dưới, tính đối xứng này có thể được khai thác để tính toán DFT nhanh hơn nhiều DFT sang FFT. Khai thác tính đối xứngCooley và Tukey đã chỉ ra rằng có thể chia phép tính DFT thành hai phần nhỏ hơn. Từ định nghĩa của DFT, chúng ta có $$ \begin{align} X_k &= \sum_{n=0}^{N-1} x_n \cdot e^{-i~2\pi~k~n~/~N} \\ &= \sum_ Chúng ta đã chia biến đổi Fourier rời rạc đơn lẻ thành hai thuật ngữ mà bản thân chúng trông rất giống với Biến đổi Fourier rời rạc nhỏ hơn, một trên các giá trị được đánh số lẻ và một trên các giá trị được đánh số chẵn. Tuy nhiên, cho đến nay, chúng tôi chưa lưu bất kỳ chu trình tính toán nào. Mỗi thuật ngữ bao gồm các phép tính $(N/2)*N$, với tổng số $N^2$ Bí quyết đến từ việc sử dụng các đối xứng trong mỗi thuật ngữ này. Bởi vì phạm vi của $k$ là $0 \le k < N$, trong khi phạm vi của $n$ là $0 \le n < M \equiv N/2$, nên từ tính chất đối xứng ở trên, chúng ta thấy rằng chúng ta chỉ cần thực hiện một nửa . Tính toán $\mathcal{O}[N^2]$ của chúng tôi đã trở thành $\mathcal{O}[M^2]$, với $M$ bằng một nửa kích thước của $N$ Nhưng không có lý do gì để dừng lại ở đó. miễn là các biến đổi Fourier nhỏ hơn của chúng tôi có $M$ có giá trị chẵn, chúng tôi có thể áp dụng lại phương pháp chia để trị này, giảm một nửa chi phí tính toán mỗi lần, cho đến khi các mảng của chúng tôi đủ nhỏ để chiến lược này không còn có lợi nữa. Trong giới hạn tiệm cận, cách tiếp cận đệ quy này chia tỷ lệ thành $\mathcal{O}[N\log N]$ Thuật toán đệ quy này có thể được triển khai rất nhanh trong Python, dựa trên mã DFT chậm của chúng tôi khi kích thước của vấn đề phụ trở nên nhỏ phù hợp Trong [4] ________số 8_______ Ở đây chúng tôi sẽ kiểm tra nhanh xem thuật toán của chúng tôi có tạo ra kết quả chính xác không Trong [5] x = np.random.random(1024) np.allclose(FFT(x), np.fft.fft(x)) Ra[5] True Và chúng ta sẽ tính thời gian cho thuật toán này so với phiên bản chậm của chúng ta Trong [6] %timeit DFT_slow(x) %timeit FFT(x) %timeit np.fft.fft(x) 10 loops, best of 3: 77.6 ms per loop 100 loops, best of 3: 4.07 ms per loop 10000 loops, best of 3: 24.7 µs per loop Tính toán của chúng tôi nhanh hơn phiên bản ngây thơ hơn một bậc độ lớn. Hơn nữa, thuật toán đệ quy của chúng ta tiệm cận $\mathcal{O}[N\log N]$. chúng tôi đã triển khai Biến đổi Fourier nhanh Lưu ý rằng chúng tôi vẫn chưa tiến gần đến tốc độ của thuật toán FFT tích hợp sẵn và điều này nằm trong dự kiến. Thuật toán FFTPACK đằng sau numpy's x = np.random.random(1024) np.allclose(DFT_slow(x), np.fft.fft(x))7 là một triển khai của Fortran đã nhận được nhiều năm điều chỉnh và tối ưu hóa. Hơn nữa, giải pháp NumPy của chúng tôi liên quan đến cả đệ quy ngăn xếp Python và phân bổ nhiều mảng tạm thời, điều này làm tăng thêm thời gian tính toán đáng kể Một chiến lược tốt để tăng tốc mã khi làm việc với Python/NumPy là vector hóa các phép tính lặp đi lặp lại nếu có thể. Chúng tôi có thể làm điều này và trong quá trình này, hãy loại bỏ các lệnh gọi hàm đệ quy của chúng tôi và làm cho FFT Python của chúng tôi hiệu quả hơn nữa Vectorized Numpy Phiên bảnLưu ý rằng trong triển khai FFT đệ quy ở trên, ở mức đệ quy thấp nhất, chúng tôi thực hiện $N~/~32$ tích ma trận-vectơ giống hệt nhau. Hiệu quả của thuật toán của chúng tôi sẽ được hưởng lợi bằng cách tính toán tất cả các sản phẩm ma trận-vector này cùng một lúc dưới dạng một sản phẩm ma trận-ma trận duy nhất. Ở mỗi cấp độ đệ quy tiếp theo, chúng tôi cũng thực hiện các hoạt động trùng lặp có thể được vector hóa. NumPy vượt trội ở loại hoạt động này và chúng tôi có thể tận dụng thực tế đó để tạo phiên bản véc tơ này của Biến đổi Fourier nhanh Trong [7] x = np.random.random(1024) np.allclose(DFT_slow(x), np.fft.fft(x))0 Mặc dù thuật toán mờ hơn một chút, nhưng nó chỉ đơn giản là sự sắp xếp lại các hoạt động được sử dụng trong phiên bản đệ quy với một ngoại lệ. chúng tôi khai thác tính đối xứng trong tính toán x = np.random.random(1024) np.allclose(DFT_slow(x), np.fft.fft(x))8 và chỉ xây dựng một nửa mảng. Một lần nữa, chúng tôi sẽ xác nhận rằng chức năng của chúng tôi mang lại kết quả chính xác Trong [8] x = np.random.random(1024) np.allclose(DFT_slow(x), np.fft.fft(x))1 Ra[8] True Bởi vì các thuật toán của chúng tôi đang trở nên hiệu quả hơn nhiều, nên chúng tôi có thể sử dụng một mảng lớn hơn để so sánh thời gian, loại bỏ x = np.random.random(1024) np.allclose(DFT_slow(x), np.fft.fft(x))9 Trong [9] x = np.random.random(1024) np.allclose(DFT_slow(x), np.fft.fft(x))3 x = np.random.random(1024) np.allclose(DFT_slow(x), np.fft.fft(x))4 Chúng tôi đã cải thiện việc triển khai của mình theo một mức độ khác. Hiện tại, chúng tôi đang ở trong khoảng 10 lần so với tiêu chuẩn FFTPACK, chỉ sử dụng vài chục dòng Python + NumPy thuần túy. Mặc dù nói về mặt tính toán, nó vẫn không khớp, nhưng về khả năng đọc, phiên bản Python vượt trội hơn nhiều so với nguồn FFTPACK, bạn có thể duyệt qua tại đây Vậy làm thế nào để FFTPACK đạt được chút tăng tốc cuối cùng này? . FFTPACK dành nhiều thời gian để đảm bảo sử dụng lại bất kỳ tính toán phụ nào có thể được sử dụng lại. Phiên bản gọn gàng của chúng tôi vẫn liên quan đến việc phân bổ và sao chép bộ nhớ quá mức; . Ngoài ra, thuật toán Cooley-Tukey có thể được mở rộng để sử dụng các phần chia có kích thước khác 2 (những gì chúng tôi đã triển khai ở đây được gọi là FFT Cooley-Tukey cơ số 2). Ngoài ra, các thuật toán FFT phức tạp hơn khác có thể được sử dụng, bao gồm các cách tiếp cận cơ bản khác biệt dựa trên các phép chập (xem, e. g. Thuật toán Bluestein và thuật toán Rader). Sự kết hợp của các phần mở rộng và kỹ thuật trên có thể dẫn đến các FFT rất nhanh ngay cả trên các mảng có kích thước không phải là lũy thừa của hai Mặc dù các hàm Python thuần túy có thể không hữu ích trong thực tế, nhưng tôi hy vọng chúng đã cung cấp một chút trực giác về những gì đang diễn ra trong nền phân tích dữ liệu dựa trên FFT. Với tư cách là nhà khoa học dữ liệu, chúng ta có thể thực hiện việc triển khai hộp đen của các công cụ cơ bản do các đồng nghiệp có đầu óc thuật toán hơn xây dựng, nhưng tôi tin chắc rằng chúng ta càng hiểu rõ hơn về các thuật toán cấp thấp mà chúng ta đang áp dụng cho Bài đăng trên blog này được viết hoàn toàn trong IPython Notebook. Toàn bộ sổ ghi chép có thể được tải xuống tại đây hoặc xem tĩnh tại đây Biến đổi Fourier nhanh được sử dụng để làm gì?FFT được sử dụng để xử lý dữ liệu trong thế giới kỹ thuật số, được kết nối mạng cao ngày nay . Nó cho phép máy tính tính toán hiệu quả các thành phần tần số khác nhau trong các tín hiệu thay đổi theo thời gian—đồng thời tái tạo lại các tín hiệu đó từ một tập hợp các thành phần tần số.
Tại sao Biến đổi Fourier được sử dụng trong Python?Sử dụng Biến đổi Fourier để xóa dữ liệu chuỗi thời gian trong mã Python ngắn nhất. Biến đổi Fourier là một cách mạnh mẽ để xem dữ liệu từ một góc độ hoàn toàn khác. Từ miền thời gian sang miền tần số.
Làm cách nào để triển khai FFT trong Python?VÍ DỤ. Sử dụng hàm fft và ifft từ scipy để tính phổ biên độ FFT và FFT nghịch đảo để thu được tín hiệu ban đầu . Vẽ cả hai kết quả. Thời gian hàm fft sử dụng tín hiệu độ dài 2000 này. Bây giờ chúng ta có thể thấy rằng các hàm fft tích hợp nhanh hơn và dễ sử dụng hơn nhiều, đặc biệt là đối với phiên bản scipy.
Sự khác biệt giữa Numpy FFT và RFFT là gì?fft trả về một mảng hình dạng 2 chiều (number_of_frames, fft_length) chứa các số phức. Đối với np. fft. rfft trả về một mảng hình dạng 2 chiều (number_of_frames, ((fft_length/2) + 1)) chứa các số phức |
