[發明專利]一種快速傅里葉分析算法

在審

• 申請號: 201910114045.4
• 申請日: 2019-02-14
• 公開（公告）號: CN109857980A
• 公開（公告）日: 2019-06-07
• 發明（設計）人: 汪洋;王浩然;吳碩
• 申請（專利權）人: 安徽慕京信息技術有限公司
• 主分類號: G06F17/14
• 分類號: G06F17/14
• 代理公司: 上海精晟知識產權代理有限公司 31253
• 代理人: 馮子玲

本發明公開了一種快速傅里葉分析算法，涉及技術領域。本發明包括獲取N個采樣點輸入數據的順序排序序列x(n)；通過y(n)＝x(G(m)+2^Lmax?1×l)計算輸入數據的倒序序列y(n)；從倒序序列y(n)中第一次可以取8點、或10點、或12點數據進行傅里葉變換；之后每次將分析點數擴大2倍進行傅里葉變換；直至進行N點相互獨立的傅里葉變換。本發明根據參與序列總點數和首次傅里葉變換點數的不同，通過y(n)＝x(G(m)+2^Lmax?1×l)計算輸入序列的倒序序列y(n)，然后利用一組公式快速完成首次8點、或10點、或12點的傅里葉變換；之后每次將分析點數擴大2倍進行傅里葉變換；直至進行N點相互獨立的傅里葉變換，降低計算時的時間復雜度，提高計算速率，便于電信號頻譜分析。

技術領域

本發明屬于電力信號分析和處理技術領域，特別是涉及一種快速傅里葉分析算法。

背景技術

傳統FFT是在計算過程中對輸入數據的序列x(n)進行奇偶分割；奇偶分割的目的就是達到高速計算，原來需要由0計算到N-1，現在分割之后就只需要由0計算到N/2-1，然后再合并即可。第一次分割得到偶數列和奇數列之后，還可以將偶數列中的偶數列和奇數列、奇數列中的偶數列和奇數列進行分割，就這樣可以一直分割到只有兩個點的時候進行傅里葉變換。

在對電力信號(電壓、電流)的分析中，首先確定進行何種功能分析(單周期分析、間諧波分析或者電壓波動與閃變分析)；然后進行動態頻率跟蹤，獲取信號的頻率，并根據功能分析要求調整數據點數；最后進行某種FFT分析并輸出結果。此時傳統FFT需要進行大量重復運算，導致計算速率慢，計算機進行計算時時間復雜度高，不利于電信號頻譜分析。

本發明中提出一種同時滿足基8(用于單周期分析)、基10(用于簡諧波分析)、基12(用于電壓波動與閃變分析)三種分析基的FFT算法。能夠降低計算時的乘法次數，提高計算速率，便于電信號頻譜分析。

發明內容

本發明的目的在于提供一種快速傅里葉分析算法，通過y(n)＝x(G(m)+2^Lmax-1×l)計算輸入序列的倒序序列y(n)，然后從倒序序列y(n)中中取出指定點數作為傅里葉變換的基；并利用公式完成首次傅里葉變換。之后每次以前一次分析點數的2倍進行傅里葉變換，直至進行N點相互獨立的傅里葉變換，解決了現有傅里葉變換計算速率較慢的問題。

為解決上述技術問題，本發明是通過以下技術方案實現的：

本發明為一種快速傅里葉分析算法，包括如下過程：

S00：獲取N個采樣點輸入數據的順序排序序列x(n)；

其中，n＝0,1,2,...,N-1；

S01：首先根據分析基數不同，計算基礎排序表G(m)，再通過y(n)＝x(G(m)+2^Lmax-1×l)計算輸入數據的倒序序列y(n)；

其中，L為FFT變換級數，最大變換級數Lmax＝log₂^N；

M為當L＝1時，即是第1次進行FFT變換的數據個數，稱這樣的FFT運算為基M運算；

G(m)為；

n＝0,1,2,...,N-1；

m＝0,1,2,...,2^L-1-1；

l＝0,1,2,...,M-1；

S02：構建旋轉因子表，對于點數和分析基數相同的序列點表，該表可以重復使用，以減少計算量；

A03：根據基數進行第一次傅里葉變換，

基8傅里葉變換，利用以下公式進行首次變換：