描述

FFT或快速傅里葉變換是信號處理中最重要的工具之一。這可用于以良好的速度檢測頻率。然而，這是一個計算密集型過程，需要大量的處理能力和內存，尤其是在 Arduino 上。這使得它很難用于每秒需要多個 FFT 結果的實時應用程序。

在本教程中，介紹了在 Arduino 上執行 FFT 的最快程序。我將其命名為 ApproxFFT，因為在多個階段采取了如此多的近似值。然而，幾乎沒有妥協的不準確性，我能夠達到大約 3 倍的速度。

如果您只想知道如何使用它，請直接轉到 5。

整個項目也在半小時長的解釋視頻中進行了解釋。您可以選擇閱讀或閱讀本教程。

我之前為同一個應用程序準備了兩個代碼，可以在此處訪問：EasyFFT ：此代碼為 FFT 提供準確的輸出，但是，它相對較慢并且消耗大量內存。建議先閱讀本教程以了解 FFT 的背景知識到本教程。

QuickFFT ：此代碼提供了非常快速的輸出。然而，幅度相距甚遠，不能用于大多數應用。它還給出了可能誤導結果的多個峰。

1：ApproxFFT函數的需要

如果您參考附圖，很明顯 QuickFFT 與傳統方法相比具有一些顯著優勢（使用 EasyFFT 的內置正弦/余弦函數計算速度）。它幾乎快 4 倍，但缺乏準確性。從第二張圖中可以看出，幅度相差甚遠。這背后的主要原因是我們使用了由多個頻率（諧波）組成的方波（近似正弦波！！！）。結果中存在多個波，這使得各種應用程序變得困難。

1 / 2 ?比較

在這里，我們假設正弦/余弦波為方波。如果我們對這些波進行更好的近似，我們可以接近精確的輸出。在此代碼中，為這些波考慮了更好的近似值。我們也有一些規定來控制這些波的準確性。通過調整此設置，我們還可以使用各種精度/速度關系。

2：快速正弦和余弦函數

如果您參考之前的 EasyFFT 函數，我們有兩個選項可用。其中之一是準確的利用內置的正弦/余弦函數，這些函數準確但速度慢。如果我們使用另一種使用查找表的方法，速度會略有提高，損失不準確。

1 / 2

這里使用完全不同的方法來計算這個值，比傳統方法快 10-12 倍。這些函數集中使用僅移位操作進行乘法和（近似）除法。這些操作比正常的除法或乘法快得多。但是，這些可能會導致我們需要以某種方式處理的精度損失。

下面兩行是使 EasyFFT 和 QuickFFT 之間的速度差異的行。通常首先我們必須計算給定值的正弦/余弦。一旦該值可用，就需要乘以另一個浮點值。這兩個過程都很慢并且需要太多時間。

?

tr=c*out_r[i10+n1]-s*out_im[i10+n1];
ti=s*out_r[i10+n1]+c*out_im[i10+n1];  // c is cosine and s is sine of some value

?

在這里，我們使用了類似于二進制支撐算法的東西。它將直接給出 A*sin(θ) 的近似輸出，我們不需要進行乘法運算。在第一個圖中，顯示了 ArcsinX 與 X 的圖。一個類似的情節是一個商店作為 Arduino 中的桌子。其中角度從 0-1024 映射，相當于 0-360 度。反正弦值也被視為 128 的倍數。

這就是計算流程的工作方式：這里我們忽略負值，只考慮 0-90。（即 500*sin 50（度數））

1. 對于任何值（即 500），正弦倍數可以是 0（對于 0 度）到該值（對于 90 度）（即 0-500）。我們將檢查中點的角度值。我們將輸入值的一半 (500) 并檢查 0.5 的角度。基于此，我們可以檢查輸出將是 0-mid point 或 midpoint-max（在我們的情況下，0.5 的角度將是 30 度，低于 50，因此我們可以得出結論，輸出將在 250-500 之間）。此時，我們已將可能范圍的大小減半。（以前的 0-500 到 250-500 ）

2.新定義的范圍我們將再次做類似的步驟重復。在我們的示例中，中點為 375，我們將檢查角度為 75，即 48 度。所以我們的答案將在 375 到 500 之間。

類似的步驟需要重復多次才能準確輸出。如第二張圖片（圖表）所示。我們進入的級別越多，輸出將越接近精確值。

在這里，我們可以只通過位移來執行所有操作，并且我們還消除了浮點乘法。

3：平方和的快速根（FastRSS）

這個函數對 RSS 值做了一些近似。它對整體速度的影響不是很顯著。但是，它節省了幾毫秒的時間。

如果我們假設平方和輸出與較大值相同，則所附圖表顯示了誤差值。與此假設相關的誤差隨著比率的增加而減小。在此代碼中，如果比率超過它只是假設一個較大的值作為輸出以節省時間。如果該比率低于該比率，則基于該值設置一些預定義的縮放比例，該比例通過執行一些重復來應用。所有這些值都存儲為 RSSdata。

4：整體計算流程：

整體計算流程如下。

1.輸入數據縮放到+512到-512：這一步對于保持數據的精度很重要。由于我們使用的是位移操作，所以在奇數的情況下會有精度損失。數字越大，損失越小。

2. 位逆序生成，

3. 輸入數據按照生成的位倒序排列。

4.進行頻率變換。需要時使用快速正弦和余弦。每次循環后，所有整數的值檢查幅度是否高于 15000，實數和虛數數組均除以 2。

無論在何處執行縮放，都會記錄縮放值。

5. 使用 FastRSS 函數計算平方和的根。

6. 檢測最大值并作為輸出返回。

5：應用

1.查找數據需要聲明為全局變量。我們只需將以下數據粘貼到代碼頂部即可。

?

//---------------------------------lookup data------------------------------------//
byte isin_data[128]=
{0,  1,   3,   4,   5,   6,   8,   9,   10,  11,  13,  14,  15,  17,  18,  19,  20, 
22,  23,  24,  26,  27,  28,  29,  31,  32,  33,  35,  36,  37,  39,  40,  41,  42, 
44,  45,  46,  48,  49,  50,  52,  53,  54,  56,  57,  59,  60,  61,  63,  64,  65, 
67,  68,  70,  71,  72,  74,  75,  77,  78,  80,  81,  82,  84,  85,  87,  88,  90, 
91,  93,  94,  96,  97,  99,  100, 102, 104, 105, 107, 108, 110, 112, 113, 115, 117, 
118, 120, 122, 124, 125, 127, 129, 131, 133, 134, 136, 138, 140, 142, 144, 146, 148, 
150, 152, 155, 157, 159, 161, 164, 166, 169, 171, 174, 176, 179, 182, 185, 188, 191, 
195, 198, 202, 206, 210, 215, 221, 227, 236};
unsigned int Pow2[14]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096};
byte RSSdata[20]={7,6,6,5,5,5,4,4,4,4,3,3,3,3,3,3,3,2,2,2};
//---------------------------------------------------------------------------------//

?

2、ApproxFFT、fast_sine、fast_cosine、fastRSS函數需要貼在代碼末尾。

3、使用功能：

?

float f=Approx_FFT(data,sample,sampling_rate);

?

該函數默認返回最大振幅的頻率值。這與 EasyFFT 和 QuickFFT 函數完全相同。

首先是我們需要執行 FFT 的數組，

第二個是樣本數：理想情況下，它應該是 2^n，可以是 2、4、8、16、32、64、128，..這里的最大樣本數受可用內存的限制

第三個輸入是采樣率。

4.精度設置：

該值可以設置為 1 到 7。數字越高，精度越高。這里提高精度將提高我們近似正弦波的擬合度。默認情況下，精度值設置為 5。在大多數情況下，此值效果很好。所有結果和速度聲明均基于此值。可以通過更改此值來調整速度和準確性。

?

int fast_sine(int Amp, int th)
{
int temp3,m1,m2;
byte temp1,temp2, test,quad,accuracy;
accuracy=5;    // set it value from 1 to 7, where 7 being most accurate but slowest
               // accuracy value of 5 recommended for typical applicaiton
while(th>1024){th=th-1024;}   // here 1024 = 2*pi or 360 deg
while(th<0){th=th+1024;}
.
.
.

?

5. 可以修改此代碼以顯示（和使用）各種頻率的原始輸出或幅度。輸出將是 2^n 的倍數。由于整數最多只能容納 +-32000 個值，因此輸出表示為倍數。

六，結論

1 / 2

上圖中顯示的所有測試都是在 Arduino mega 上完成的，精度為 5。以下是測試中的一些重要觀察結果：

速度比傳統FFT快3倍以上，

內存消耗低（幾乎一半），

輸出與精確值相當（低誤差），

希望這段代碼對項目有用。如有任何疑問或反饋，請通過評論或電子郵件告訴我。