二次電纜尋線儀及保護序列化測試儀FFT算法優(yōu)化研究

史春旻　沈心怡　張瑋　俞家融　王天序

摘 要：針對快速傅里葉變換（Fast Fourier Transform，F(xiàn)FT）算法在單片機中運行耗時較長的問題，開展了耗時原因分析。針對現(xiàn)有耗時較長的三角函數(shù)計算、2的N次方計算，優(yōu)化為查表法計算；平方和的根號計算，優(yōu)化為運行速度更快的簡化計算。該優(yōu)化方法簡單實用，可運用于其他需要計算優(yōu)化的場景。最后對該優(yōu)化方案進行了比較，研究結(jié)果表明，該優(yōu)化方法顯著提升了FFT的計算效率，具有很強的工程實用性。

關(guān)鍵詞：二次電纜尋線儀；保護序列化測試儀；FFT算法優(yōu)化

中圖分類號：TP33? ? 文獻標志碼：A? ? 文章編號：1671-0797（2023）13-0059-04

DOI：10.19514/j.cnki.cn32-1628/tm.2023.13.015

0? ? 引言

FFT（Fast Fourier Transform）算法是離散傅里葉變換的快速算法，由偉大的數(shù)學家高斯在計算小行星軌道時首次提出，高斯去世后，后人在其手稿中整理并發(fā)表在《高斯全集》第三卷，但當時并沒有FFT算法的使用場景，F(xiàn)FT算法就這樣被遺忘在歷史的長河中。20世紀60年代，由于檢測地下核試驗振動波等應用需求，美國投入了大量資源來研究傅里葉變換的計算方法。新的FFT算法由美國數(shù)學家和計算機科學家John W. Tukey于1965年提出[1]，它是一種用于計算復雜信號的離散傅里葉變換的快速方法，主要優(yōu)點是計算速度快，而且可以使用計算機高效地實現(xiàn)。FFT算法是一種數(shù)字信號處理（DSP）技術(shù)，用于將一個信號從時域轉(zhuǎn)換為頻域，它的主要作用是從信號中提取出頻率特性，從而用于信號的處理、檢測、分析和改善等。

在聲波二次電纜尋線儀及保護序列化測試儀設備研發(fā)過程中，需要在單片機中運行FFT算法程序，為了優(yōu)化和提升FFT算法程序在單片機中的計算速度，本文將研究國內(nèi)電力系統(tǒng)繼電保護和測控裝置中普遍使用的FFT算法，并提出改進方法，在計算精度和計算速度之間取得平衡，為今后涉及信號處理的相關(guān)產(chǎn)品研發(fā)和算法優(yōu)化提供一定的優(yōu)化思路。

1? ? 分裂基FFT算法介紹

本文采用了國內(nèi)繼電保護裝置廠家在中低壓保護裝置中普遍使用的分裂基FFT算法。

分裂基算法（Split-Radix FFT Algorithm，SRA）由Duhamel和Hollman于1984年提出，最初是針對規(guī)模為2的冪的DFT問題的計算優(yōu)化。Split-Radix FFT將N點DFT分解為一個N/2點DFT和兩個N/4點DFT。分裂基的基本思路是對偶序列輸出使用基2算法，對奇序列輸出使用基4算法，將基2和基4分解組合在一起。在FFT計算中用較大的基可以進一步減少復數(shù)乘法，N/4點基4算法比N/2點基2算法更有效。Split-Radix FFT是眾多FFT算法中乘法和加法次數(shù)最少的算法之一，其運算結(jié)構(gòu)好，運算程序短，在國內(nèi)繼電保護裝置中被廣泛采用，研究表明其乘法復雜度接近于理論最小值[1]。盡管該庫的計算速度很快，但該庫在RP2040 Arm-Cortex M0單片機中的執(zhí)行速度依然有一定的延時，為了能在二次電纜尋線儀及保護序列化測試儀項目的信號處理中有更好的表現(xiàn)，本文對分裂基FFT算法進行了一定程度的優(yōu)化。

2? ? FFT算法介紹

2.1? ? 傅里葉變換原理

傅里葉變換，將被測試信號分解為不同強度和頻率的正弦波，把所有的正弦波全部疊加起來則是原始信號。原始信號可能看起來完全不像正弦波，這就是傅里葉變換的神奇之處。

如果想知道原始信號中某個頻率的信號的強度，只需要將這個信號乘以這個正弦波，再計算曲線和坐標軸的面積之和。

比如某個信號f（t），包含以下分量：

f（t）=a1×sin t+a2×sin（2t）+a3×sin（3t）

如果要求sin t在f（t）的分量，需要在等式兩邊同時乘以sin x。

2.3? ? 快速傅里葉變換計算耗時的原因分析

檢查FFT運算的源碼，經(jīng)過統(tǒng)計可知，在計算8點FFT時，經(jīng)過了一次2的N次方運算、24次循環(huán)計算，每次循環(huán)包含4次sin和cos運算；最后求信號幅值和相位時，需要完成4次平方和再開根號運算、4次arctan函數(shù)運算。因為乘法、除法運算量幾乎不可壓縮，本文將重點關(guān)注FFT運算過程中數(shù)學函數(shù)調(diào)用計算量的優(yōu)化。

3? ? FFT算法優(yōu)化方案

3.1? ? 使用查表法實現(xiàn)sin和cos函數(shù)優(yōu)化

為了加快單片機三角函數(shù)的計算速度，需要避免使用math.h頭文件中的數(shù)學函數(shù)。本文選擇使用查表法計算sin和cos，在8位單片機中使用8位的sin和cos精度，在32位單片機中使用32位精度。

圖1以8位精度為例，構(gòu)造一個sin 0°到sin 90°的數(shù)組。為了降低單片機的內(nèi)存使用，這里統(tǒng)一使用8位內(nèi)存整型值數(shù)組保存sin值。實際項目中，根據(jù)單片機的內(nèi)存大小，在內(nèi)存充足的情況下，既可以使用16位整數(shù)數(shù)組，也可以使用32位浮點數(shù)組保存sin的值，使用浮點數(shù)組時，fast_sin函數(shù)不用再除以255，可減少一次除法運算。圖1中的每個值，除以255就可以得到對應的sin值。

根據(jù)圖1構(gòu)造的數(shù)組，編寫sin函數(shù)，所有超出0°～90°的值，根據(jù)sin函數(shù)的周期性和對稱性，做相應的平移和符號變換，再從數(shù)組中獲取對應的值。查表法sin函數(shù)實現(xiàn)方案如圖2所示。

同樣的方法可以構(gòu)造查表法cos函數(shù)，經(jīng)過測試，該方法相比傳統(tǒng)的數(shù)學函數(shù)庫，能將sin和cos的計算時間優(yōu)化到原有時間的3%，極大地提升了正弦函數(shù)和余弦函數(shù)的計算效率。

3.2? ? 使用查表法求解2的N次方

FFT求解過程中，需要求解2的N次方。根據(jù)需要求解信號的采樣長度，提前構(gòu)造2的N次方數(shù)組，能大幅度提升該計算的速度。圖3為最大12階2的N次方構(gòu)造數(shù)組示例（實際項目中需根據(jù)情況確定數(shù)組的長度）。

經(jīng)測試，使用查表法求解2的N次方，能有效節(jié)約FFT運算時間1～2 μs。

3.3? ? 使用近似法快速計算平方和根

在FFT運算中，需要求解復數(shù)的?！蘎e2+Im2，即平方和的平方根求解，此運算是比較耗時的運算，使用近似求解平方根的方法，能有效提升計算速度。圖4是快速平方和根號函數(shù)的C語言代碼實現(xiàn)，在fastRSS（Root of Squared Sum）中，當兩數(shù)的比例大于4倍的時候，直接返回最大數(shù)，兩數(shù)比例小于4倍的時候，使用近似求解。近似法快速計算平方和根函數(shù)實現(xiàn)方案如圖4所示。

該實現(xiàn)方案和精確解的誤差是多少呢？表1為Im固定為10，Re=1至Re=10時，fastRSS函數(shù)結(jié)果和精確解的誤差分析。

從表1的結(jié)果可以看出，使用fastRSS函數(shù)，最大誤差沒有超過2%，具有很高的精度，同時避免使用數(shù)學函數(shù)庫中的根號運算，有效提升了FFT算法計算速度。

4? ? FFT優(yōu)化后運算時間和精度分析

樹莓派RP2040單片機價格低廉，資源豐富。本文通過在RP2040單片機上運行優(yōu)化前后的FFT代碼，進行時間和精度分析。通過構(gòu)造兩個電壓和電流信號，并將采樣值在50 Hz周期中進行32點采樣，將采樣保存在測試數(shù)組中，再進行FFT運算，分析FFT運行的時間。表2是離散后的32點采樣值。

使用表2數(shù)據(jù)，分別代入優(yōu)化前后的程序，分析兩者數(shù)據(jù)的差異。表3為優(yōu)化前和優(yōu)化后RP2040單片機中FFT程序輸出結(jié)果。優(yōu)化前程序計算時間為3 639 μs，優(yōu)化后的執(zhí)行時間為2 124 μs，優(yōu)化效果顯著，節(jié)約單片機運算時間約42%。

從表3的結(jié)果可知，最大誤差為50 Hz電流分量結(jié)果，優(yōu)化前20.5 A，優(yōu)化后20.32 A，誤差為0.88%。優(yōu)化后的FFT算法具有非常高的精度。

5? ? 結(jié)論和建議

本文對FFT計算源碼過程中的函數(shù)調(diào)用進行了研究，針對部分數(shù)學函數(shù)提出了優(yōu)化方案，在一定程度上提升了單片機中FFT算法的運算效率，平均效率提升約42%。改進措施簡單實用，對單片機中其他計算量較大的運用場景也有一定的借鑒作用。

單片機中FFT算法還有其他的改進方法，比如在ARM-cortex M4處理器中調(diào)用SIMD指令加速乘法及三角函數(shù)運算[4]。本文僅提出單一的函數(shù)簡化計算方法，未來還能在現(xiàn)有的基礎之上，進一步進行算法優(yōu)化，提高單片機中FFT算法運行速率，降低硬件設計成本，提升芯片工作效率。

[參考文獻]

[1] 陳暾.基于ARM_V8平臺的FFT實現(xiàn)與優(yōu)化研究[D].長沙：湖南師范大學，2018.

[2] 王琳，胡耀，王世元.從采樣的角度談信號與系統(tǒng)中的傅里葉變換[J].安徽師范大學學報（自然科學版），2022，45（4）：332-337.

[3] 操廬寧.基于X86-64計算平臺的FFT實現(xiàn)與并行優(yōu)化[D].長春：吉林大學，2019.

[4] 姚建宇，張祎維，張廣婷，等.基于SIMD的三角函數(shù)高性能實現(xiàn)與優(yōu)化[J].計算機科學，2021，48（12）：29-35.

收稿日期：2023-03-14

作者簡介：史春旻（1981—），男，江蘇東臺人，高級工程師，研究方向：變電站二次系統(tǒng)運維。