Thuật toán FFT Python

FFT y[k] có độ dài \[N\] có độ dài- \ sequence x[n] is defined as

\[y[k] = \sum_{n=0}^{N-1} e^{-2 \pi j \frac{k n}{N} } x[n] \, ,\]

và phép biến đổi nghịch đảo được định nghĩa như sau

\[x[n] = \frac{1}{N} \sum_{k=0}^{N-1} e^{2 \pi j \frac{k n}{N} } y[k] \,. \]

Các phép biến đổi này có thể được tính bằng và , tương ứng, như minh họa trong ví dụ sau

>>> from scipy.fft import fft, ifft
>>> import numpy as np
>>> x = np.array[[1.0, 2.0, 1.0, -1.0, 1.5]]
>>> y = fft[x]
>>> y
array[[ 4.5       +0.j        ,  2.08155948-1.65109876j,
       -1.83155948+1.60822041j, -1.83155948-1.60822041j,
        2.08155948+1.65109876j]]
>>> yinv = ifft[y]
>>> yinv
array[[ 1.0+0.j,  2.0+0.j,  1.0+0.j, -1.0+0.j,  1.5+0.j]]

Từ định nghĩa của FFT có thể thấy rằng

\[y[0] = \sum_{n=0}^{N-1} x[n] \,. \]

trong ví dụ

>>> np.sum[x]
4.5

tương ứng với \[y[0]\] . Đối với N chẵn, các phần tử \[y[1]. y[N/2-1]\] chứa các số hạng có tần suất dương và các phần tử \[y[N/2]. y[N-1]\] chứa các thuật ngữ có tần suất âm, theo thứ tự tần suất âm giảm dần. Đối với N lẻ, các phần tử \[y[1]. y[[N-1]/2]\] chứa các số hạng tần số dương và các phần tử \[y[[N+1]/ . y[N-1]\] chứa các thuật ngữ có tần suất âm, theo thứ tự tần suất âm giảm dần.

Trong trường hợp dãy x có giá trị thực, các giá trị của \[y[n]\] cho tần số dương là liên hợp . Thông thường, chỉ FFT tương ứng với tần số dương được vẽ. \[y[n]\] for negative frequencies [because the spectrum is symmetric]. Typically, only the FFT corresponding to positive frequencies is plotted.

Ví dụ vẽ đồ thị FFT của tổng hai sin

>>> from scipy.fft import fft, fftfreq
>>> import numpy as np
>>> # Number of sample points
>>> N = 600
>>> # sample spacing
>>> T = 1.0 / 800.0
>>> x = np.linspace[0.0, N*T, N, endpoint=False]
>>> y = np.sin[50.0 * 2.0*np.pi*x] + 0.5*np.sin[80.0 * 2.0*np.pi*x]
>>> yf = fft[y]
>>> xf = fftfreq[N, T][:N//2]
>>> import matplotlib.pyplot as plt
>>> plt.plot[xf, 2.0/N * np.abs[yf[0:N//2]]]
>>> plt.grid[]
>>> plt.show[]

Tín hiệu đầu vào FFT vốn đã bị cắt bớt. Việc cắt bớt này có thể được mô hình hóa như phép nhân của một tín hiệu vô hạn với hàm cửa sổ hình chữ nhật. Trong miền phổ, phép nhân này trở thành tích chập của phổ tín hiệu với phổ hàm cửa sổ, có dạng \[\sin[x]/x\] . Sự tích chập này là nguyên nhân của một hiệu ứng gọi là rò rỉ quang phổ [xem ]. Tạo cửa sổ tín hiệu bằng chức năng cửa sổ chuyên dụng giúp giảm thiểu rò rỉ quang phổ. Ví dụ bên dưới sử dụng cửa sổ Blackman từ scipy. tín hiệu và hiển thị hiệu ứng của cửa sổ [thành phần 0 của FFT đã bị cắt bớt nhằm mục đích minh họa].

>>> from scipy.fft import fft, fftfreq
>>> import numpy as np
>>> # Number of sample points
>>> N = 600
>>> # sample spacing
>>> T = 1.0 / 800.0
>>> x = np.linspace[0.0, N*T, N, endpoint=False]
>>> y = np.sin[50.0 * 2.0*np.pi*x] + 0.5*np.sin[80.0 * 2.0*np.pi*x]
>>> yf = fft[y]
>>> from scipy.signal import blackman
>>> w = blackman[N]
>>> ywf = fft[y*w]
>>> xf = fftfreq[N, T][:N//2]
>>> import matplotlib.pyplot as plt
>>> plt.semilogy[xf[1:N//2], 2.0/N * np.abs[yf[1:N//2]], '-b']
>>> plt.semilogy[xf[1:N//2], 2.0/N * np.abs[ywf[1:N//2]], '-r']
>>> plt.legend[['FFT', 'FFT w. window']]
>>> plt.grid[]
>>> plt.show[]

Trường hợp dãy x có giá trị phức thì phổ không còn đối xứng. Để đơn giản hóa việc làm việc với các hàm FFT, scipy cung cấp hai hàm trợ giúp sau

Hàm trả về các điểm tần số mẫu FFT

>>> from scipy.fft import fftfreq
>>> freq = fftfreq[8, 0.125]
>>> freq
array[[ 0., 1., 2., 3., -4., -3., -2., -1.]]

Theo tinh thần tương tự, chức năng này cho phép hoán đổi nửa dưới và nửa trên của vectơ để nó trở nên phù hợp để hiển thị

>>> from scipy.fft import fftshift
>>> x = np.arange[8]
>>> fftshift[x]
array[[4, 5, 6, 7, 0, 1, 2, 3]]

Ví dụ dưới đây vẽ biểu đồ FFT của hai cấp số nhân phức tạp;

>>> from scipy.fft import fft, fftfreq, fftshift
>>> import numpy as np
>>> # number of signal points
>>> N = 400
>>> # sample spacing
>>> T = 1.0 / 800.0
>>> x = np.linspace[0.0, N*T, N, endpoint=False]
>>> y = np.exp[50.0 * 1.j * 2.0*np.pi*x] + 0.5*np.exp[-80.0 * 1.j * 2.0*np.pi*x]
>>> yf = fft[y]
>>> xf = fftfreq[N, T]
>>> xf = fftshift[xf]
>>> yplot = fftshift[yf]
>>> import matplotlib.pyplot as plt
>>> plt.plot[xf, 1.0/N * np.abs[yplot]]
>>> plt.grid[]
>>> plt.show[]

Hàm tính toán FFT của một chuỗi thực và xuất các hệ số FFT phức tạp \[y[n]\] chỉ cho một nửa . Các thành phần tần số âm còn lại được ngụ ý bởi tính đối xứng Hermiti của FFT đối với đầu vào thực [

>>> from scipy.fft import fft, fftfreq
>>> import numpy as np
>>> # Number of sample points
>>> N = 600
>>> # sample spacing
>>> T = 1.0 / 800.0
>>> x = np.linspace[0.0, N*T, N, endpoint=False]
>>> y = np.sin[50.0 * 2.0*np.pi*x] + 0.5*np.sin[80.0 * 2.0*np.pi*x]
>>> yf = fft[y]
>>> from scipy.signal import blackman
>>> w = blackman[N]
>>> ywf = fft[y*w]
>>> xf = fftfreq[N, T][:N//2]
>>> import matplotlib.pyplot as plt
>>> plt.semilogy[xf[1:N//2], 2.0/N * np.abs[yf[1:N//2]], '-b']
>>> plt.semilogy[xf[1:N//2], 2.0/N * np.abs[ywf[1:N//2]], '-r']
>>> plt.legend[['FFT', 'FFT w. window']]
>>> plt.grid[]
>>> plt.show[]

Hàm tương ứng tính toán IFFT của các hệ số FFT với thứ tự đặc biệt này

________số 8

Lưu ý rằng các tín hiệu có độ dài lẻ và chẵn có cùng hình dạng. Theo mặc định, giả sử tín hiệu đầu ra phải có độ dài bằng nhau. Và như vậy đối với các tín hiệu lẻ sẽ cho kết quả sai

>>> irfft[yr]
array[[ 1.70788987,  2.40843925, -0.37366961,  0.75734049]]

Để khôi phục tín hiệu có độ dài lẻ ban đầu, chúng ta phải chuyển hình dạng đầu ra theo tham số n

>>> np.sum[x]
4.5

Các chức năng và cung cấp 2-D FFT và IFFT tương ứng. Tương tự và cung cấp ND FFT và IFFT tương ứng

Đối với các tín hiệu đầu vào thực, tương tự như , chúng ta có các hàm và đối với các phép biến đổi thực 2-D;

Ví dụ bên dưới minh họa một IFFT 2-D và biểu thị các tín hiệu miền thời gian [2-D] kết quả

>>> np.sum[x]
4.5

SciPy sử dụng định nghĩa sau về DCT-I không chuẩn hóa [

>>> from scipy.fft import fftfreq
>>> freq = fftfreq[8, 0.125]
>>> freq
array[[ 0., 1., 2., 3., -4., -3., -2., -1.]]

\[y[k] = x_0 + [-1]^k x_{N-1} + 2\sum_{n=1}^{N-2} x[n] \cos\left[\frac{\pi . \]

Lưu ý rằng DCT-I chỉ được hỗ trợ cho kích thước đầu vào > 1

SciPy sử dụng định nghĩa sau về DCT-II không chuẩn hóa [

>>> from scipy.fft import fftfreq
>>> freq = fftfreq[8, 0.125]
>>> freq
array[[ 0., 1., 2., 3., -4., -3., -2., -1.]]

\[y[k] = 2 \sum_{n=0}^{N-1} x[n] \cos \left[{\pi[2n+1]k \over 2N} \right] \qquad 0 \ . \]

Trong trường hợp DCT được chuẩn hóa [

>>> from scipy.fft import fftshift
>>> x = np.arange[8]
>>> fftshift[x]
array[[4, 5, 6, 7, 0, 1, 2, 3]]

\[\begin{split}f = \begin{cases} \sqrt{1/[4N]}, & \text{if $k = 0$} \\ \sqrt{1/[2N]}, & \text . \end{split}\]

Trong trường hợp này, “các hàm cơ sở” DCT \[\phi_k[n] = 2 f \cos \left[{\pi[2n+1]k \over . become orthonormal:

\[\sum_{n=0}^{N-1} \phi_k[n] \phi_l[n] = \delta_{lk}. \]

SciPy sử dụng định nghĩa sau về DCT-III không chuẩn hóa [

>>> from scipy.fft import fftfreq
>>> freq = fftfreq[8, 0.125]
>>> freq
array[[ 0., 1., 2., 3., -4., -3., -2., -1.]]

\[y[k] = x_0 + 2 \sum_{n=1}^{N-1} x[n] \cos\left[{\pi n[2k+1] \over 2N}\right] \qquad

hoặc, cho

>>> from scipy.fft import fftshift
>>> x = np.arange[8]
>>> fftshift[x]
array[[4, 5, 6, 7, 0, 1, 2, 3]]

\[y[k] = {x_0\over\sqrt{N}} + {2\over\sqrt{N}} \sum_{n=1}^{N-1} x[n] \cos\left[ . \]

SciPy sử dụng định nghĩa sau về DCT-IV không chuẩn hóa [

>>> from scipy.fft import fftfreq
>>> freq = fftfreq[8, 0.125]
>>> freq
array[[ 0., 1., 2., 3., -4., -3., -2., -1.]]

\[y[k] = 2 \sum_{n=0}^{N-1} x[n] \cos\left[{\pi [2n+1][2k+1] \over 4N}\right]

hoặc, cho

>>> from scipy.fft import fftshift
>>> x = np.arange[8]
>>> fftshift[x]
array[[4, 5, 6, 7, 0, 1, 2, 3]]

\[y[k] = \sqrt{2\over N}\sum_{n=0}^{N-1} x[n] \cos\left[{\pi [2n+1][2k+1]

DCT-III [không chuẩn hóa] là nghịch đảo của DCT-II [không chuẩn hóa], lên đến hệ số 2N. DCT-III trực giao chính xác là nghịch đảo của DCT-II trực giao. Hàm thực hiện ánh xạ giữa các loại DCT và IDCT, cũng như chuẩn hóa chính xác

Ví dụ sau đây cho thấy mối quan hệ giữa DCT và IDCT đối với các loại và chuẩn hóa khác nhau

>>> np.sum[x]
4.5

DCT-II và DCT-III là nghịch đảo của nhau, vì vậy đối với phép biến đổi trực giao, chúng tôi quay trở lại tín hiệu ban đầu

>>> np.sum[x]
4.5

Tuy nhiên, thực hiện tương tự theo chuẩn hóa mặc định, chúng tôi chọn một hệ số tỷ lệ bổ sung là \[2N=10\] kể từ chuyển tiếp .

>>> np.sum[x]
4.5

Vì lý do này, chúng ta nên sử dụng hàm sử dụng cùng loại cho cả hai, cho kết quả chuẩn hóa chính xác

>>> np.sum[x]
4.5

Có thể thấy các kết quả tương tự đối với DCT-I, kết quả này ngược lại với hệ số của \[2[N-1]\].

>>> np.sum[x]
4.5

Và đối với DCT-IV, cũng là nghịch đảo của chính nó với hệ số \[2N\] .

>>> np.sum[x]
4.5

DCT thể hiện “thuộc tính nén năng lượng”, nghĩa là đối với nhiều tín hiệu, chỉ một vài hệ số DCT đầu tiên có cường độ đáng kể. Loại bỏ các hệ số khác dẫn đến một lỗi tái tạo nhỏ, một thực tế được khai thác trong quá trình nén tín hiệu bị mất [e. g. nén JPEG]

Ví dụ dưới đây cho thấy tín hiệu x và hai lần tái tạo [ \[x_{20}\] và \[x_{15}\]] from the signal’s DCT coefficients. The signal \[x_{20}\] được tạo lại từ 20 hệ số DCT đầu tiên, \[x_{ . Có thể thấy sai số tương đối khi sử dụng 20 hệ số vẫn rất nhỏ [~0. 1%], nhưng cung cấp tỷ lệ nén gấp năm lần. is reconstructed from the first 15 DCT coefficients. It can be seen that the relative error of using 20 coefficients is still very small [~0.1%], but provides a five-fold compression rate.

>>> np.sum[x]
4.5

DST-I giả sử đầu vào là số lẻ khoảng n=-1 và n=N. SciPy sử dụng định nghĩa sau về DST-I không chuẩn hóa [

>>> from scipy.fft import fftfreq
>>> freq = fftfreq[8, 0.125]
>>> freq
array[[ 0., 1., 2., 3., -4., -3., -2., -1.]]

\[y[k] = 2\sum_{n=0}^{N-1} x[n] \sin\left[ \pi {[n+1] [k+1]}\over{N+1 . \]

Cũng lưu ý rằng DST-I chỉ được hỗ trợ cho kích thước đầu vào > 1. DST-I [không chuẩn hóa] là nghịch đảo của chính nó, lên đến hệ số 2[N+1]

DST-II giả sử đầu vào là số lẻ khoảng n=-1/2 và chẵn khoảng n=N. SciPy sử dụng định nghĩa sau về DST-II không chuẩn hóa [

>>> from scipy.fft import fftfreq
>>> freq = fftfreq[8, 0.125]
>>> freq
array[[ 0., 1., 2., 3., -4., -3., -2., -1.]]

\[y[k] = 2 \sum_{n=0}^{N-1} x[n] \sin\left[ {\pi [n+1/2][k+1]} \over N \ . \]

DST-III giả sử đầu vào là số lẻ khoảng n=-1 và chẵn khoảng n=N-1. SciPy sử dụng định nghĩa sau về DST-III không chuẩn hóa [

>>> from scipy.fft import fftfreq
>>> freq = fftfreq[8, 0.125]
>>> freq
array[[ 0., 1., 2., 3., -4., -3., -2., -1.]]

\[y[k] = [-1]^k x[N-1] + 2 \sum_{n=0}^{N-2} x[n] \sin \left[ {\pi [n+1] . \]

SciPy sử dụng định nghĩa sau về DST-IV không chuẩn hóa [

>>> from scipy.fft import fftfreq
>>> freq = fftfreq[8, 0.125]
>>> freq
array[[ 0., 1., 2., 3., -4., -3., -2., -1.]]

\[y[k] = 2 \sum_{n=0}^{N-1} x[n] \sin\left[{\pi [2n+1][2k+1] \over 4N}\right]

hoặc, cho

>>> from scipy.fft import fftshift
>>> x = np.arange[8]
>>> fftshift[x]
array[[4, 5, 6, 7, 0, 1, 2, 3]]

\[y[k] = \sqrt{2\over N}\sum_{n=0}^{N-1} x[n] \sin\left[{\pi [2n+1][2k+1]

Ví dụ sau đây cho thấy mối quan hệ giữa DST và IDST đối với các loại và chuẩn hóa khác nhau

>>> np.sum[x]
4.5

DST-II và DST-III là nghịch đảo của nhau, vì vậy đối với phép biến đổi trực giao, chúng tôi quay trở lại tín hiệu ban đầu

>>> np.sum[x]
4.5

Tuy nhiên, thực hiện tương tự theo chuẩn hóa mặc định, chúng tôi chọn một hệ số tỷ lệ bổ sung là \[2N=10\] kể từ chuyển tiếp .

>>> from scipy.fft import fft, fftfreq
>>> import numpy as np
>>> # Number of sample points
>>> N = 600
>>> # sample spacing
>>> T = 1.0 / 800.0
>>> x = np.linspace[0.0, N*T, N, endpoint=False]
>>> y = np.sin[50.0 * 2.0*np.pi*x] + 0.5*np.sin[80.0 * 2.0*np.pi*x]
>>> yf = fft[y]
>>> xf = fftfreq[N, T][:N//2]
>>> import matplotlib.pyplot as plt
>>> plt.plot[xf, 2.0/N * np.abs[yf[0:N//2]]]
>>> plt.grid[]
>>> plt.show[]

Vì lý do này, chúng ta nên sử dụng hàm sử dụng cùng loại cho cả hai, cho kết quả chuẩn hóa chính xác

>>> from scipy.fft import fft, fftfreq
>>> import numpy as np
>>> # Number of sample points
>>> N = 600
>>> # sample spacing
>>> T = 1.0 / 800.0
>>> x = np.linspace[0.0, N*T, N, endpoint=False]
>>> y = np.sin[50.0 * 2.0*np.pi*x] + 0.5*np.sin[80.0 * 2.0*np.pi*x]
>>> yf = fft[y]
>>> xf = fftfreq[N, T][:N//2]
>>> import matplotlib.pyplot as plt
>>> plt.plot[xf, 2.0/N * np.abs[yf[0:N//2]]]
>>> plt.grid[]
>>> plt.show[]

Có thể thấy các kết quả tương tự đối với DST-I, kết quả này ngược lại với hệ số của \[2[N-1]\].

>>> from scipy.fft import fft, fftfreq
>>> import numpy as np
>>> # Number of sample points
>>> N = 600
>>> # sample spacing
>>> T = 1.0 / 800.0
>>> x = np.linspace[0.0, N*T, N, endpoint=False]
>>> y = np.sin[50.0 * 2.0*np.pi*x] + 0.5*np.sin[80.0 * 2.0*np.pi*x]
>>> yf = fft[y]
>>> xf = fftfreq[N, T][:N//2]
>>> import matplotlib.pyplot as plt
>>> plt.plot[xf, 2.0/N * np.abs[yf[0:N//2]]]
>>> plt.grid[]
>>> plt.show[]

Và đối với DST-IV, cũng là nghịch đảo của chính nó với hệ số \[2N\] .

>>> from scipy.fft import fft, fftfreq
>>> import numpy as np
>>> # Number of sample points
>>> N = 600
>>> # sample spacing
>>> T = 1.0 / 800.0
>>> x = np.linspace[0.0, N*T, N, endpoint=False]
>>> y = np.sin[50.0 * 2.0*np.pi*x] + 0.5*np.sin[80.0 * 2.0*np.pi*x]
>>> yf = fft[y]
>>> xf = fftfreq[N, T][:N//2]
>>> import matplotlib.pyplot as plt
>>> plt.plot[xf, 2.0/N * np.abs[yf[0:N//2]]]
>>> plt.grid[]
>>> plt.show[]