ApproxFFT：Arduino最快的FFT函數(shù)

描述

FFT或快速傅里葉變換是信號(hào)處理中最重要的工具之一。這可用于以良好的速度檢測(cè)頻率。然而，這是一個(gè)計(jì)算密集型過程，需要大量的處理能力和內(nèi)存，尤其是在 Arduino 上。這使得它很難用于每秒需要多個(gè) FFT 結(jié)果的實(shí)時(shí)應(yīng)用程序。

在本教程中，介紹了在 Arduino 上執(zhí)行 FFT 的最快程序。我將其命名為 ApproxFFT，因?yàn)樵诙鄠€(gè)階段采取了如此多的近似值。然而，幾乎沒有妥協(xié)的不準(zhǔn)確性，我能夠達(dá)到大約 3 倍的速度。

如果您只想知道如何使用它，請(qǐng)直接轉(zhuǎn)到 5。

整個(gè)項(xiàng)目也在半小時(shí)長(zhǎng)的解釋視頻中進(jìn)行了解釋。您可以選擇閱讀或閱讀本教程。

我之前為同一個(gè)應(yīng)用程序準(zhǔn)備了兩個(gè)代碼，可以在此處訪問：EasyFFT ：此代碼為 FFT 提供準(zhǔn)確的輸出，但是，它相對(duì)較慢并且消耗大量?jī)?nèi)存。建議先閱讀本教程以了解 FFT 的背景知識(shí)到本教程。

QuickFFT ：此代碼提供了非?？焖俚妮敵?。然而，幅度相距甚遠(yuǎn)，不能用于大多數(shù)應(yīng)用。它還給出了可能誤導(dǎo)結(jié)果的多個(gè)峰。

1：ApproxFFT函數(shù)的需要

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

1 / 2 ?比較

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

2：快速正弦和余弦函數(shù)

如果您參考之前的 EasyFFT 函數(shù)，我們有兩個(gè)選項(xiàng)可用。其中之一是準(zhǔn)確的利用內(nèi)置的正弦/余弦函數(shù)，這些函數(shù)準(zhǔn)確但速度慢。如果我們使用另一種使用查找表的方法，速度會(huì)略有提高，損失不準(zhǔn)確。

1 / 2

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

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

?

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

?

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

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

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

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

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

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

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

這個(gè)函數(shù)對(duì) RSS 值做了一些近似。它對(duì)整體速度的影響不是很顯著。但是，它節(jié)省了幾毫秒的時(shí)間。

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

4：整體計(jì)算流程：

整體計(jì)算流程如下。

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

2. 位逆序生成，

3. 輸入數(shù)據(jù)按照生成的位倒序排列。

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

無論在何處執(zhí)行縮放，都會(huì)記錄縮放值。

5. 使用 FastRSS 函數(shù)計(jì)算平方和的根。

6. 檢測(cè)最大值并作為輸出返回。

5：應(yīng)用

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

?

//---------------------------------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函數(shù)需要貼在代碼末尾。

3、使用功能：

?

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

?

該函數(shù)默認(rèn)返回最大振幅的頻率值。這與 EasyFFT 和 QuickFFT 函數(shù)完全相同。

首先是我們需要執(zhí)行 FFT 的數(shù)組，

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

第三個(gè)輸入是采樣率。

4.精度設(shè)置：

該值可以設(shè)置為 1 到 7。數(shù)字越高，精度越高。這里提高精度將提高我們近似正弦波的擬合度。默認(rèn)情況下，精度值設(shè)置為 5。在大多數(shù)情況下，此值效果很好。所有結(jié)果和速度聲明均基于此值?？梢酝ㄟ^更改此值來調(diào)整速度和準(zhǔn)確性。

?

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 的倍數(shù)。由于整數(shù)最多只能容納 +-32000 個(gè)值，因此輸出表示為倍數(shù)。

六，結(jié)論

1 / 2

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

速度比傳統(tǒng)FFT快3倍以上，

內(nèi)存消耗低（幾乎一半），

輸出與精確值相當(dāng)（低誤差），

希望這段代碼對(duì)項(xiàng)目有用。如有任何疑問或反饋，請(qǐng)通過評(píng)論或電子郵件告訴我。