可以用基2FFT演算法

Ⅰ 基-2fft演算法的軟體實現 matlab代碼

% 基於Matlab的時間抽取基2FFT演算法
function y=myditfft(x)
%本程序對輸入序列實現DIT-FFT基2演算法，點數取大於等於長度的2的冪次
%------------------------------------
% Leo's fft program(改編網上的一個程序)
%------------------------------------
m=log2(2^nextpow2(length(x))); %求的x長度對應的2的最低冪次m
N=2^m;
if length(x)<N
x=[x,zeros(1,N-length(x))]; %若長度不是2的冪，補0到2的整數冪
end
x;
%--------------------------------------------------------------------------
%對輸入序列進行倒序
%如果輸入序列的自然順序號I用二進制數（例如n2n1n0）表示
%則其倒位序J對應的二進制數就是（n0n1n2），這樣，在原來自然順序時應該放x(I)的
%單元，現在倒位序後應放x(J)。
%--------------------------------------------------------------------------
%以下程序相當於以下程序:
%nxd=bin2dec(fliplr(dec2bin([1:N]-1,m)))+1; %求1：2^m數列的倒序
%y=x(nxd); %將倒序排列作為初始值
%--------------------------------------------------------------------------
NV2=N/2;
NM1=N-1;
I=0;
J=0;
while I<NM1
if I<J
T=x(J+1);
x(J+1)=x(I+1);
x(I+1)=T;
end
K=NV2;

while K<=J
J=J-K;
K=K/2;
end
J=J+K;
I=I+1;
end
x;
%--------------------------------------------------------------------------
%以下程序解釋:
%第一級從x(0)開始,跨接一階蝶形,再取每條對稱
%第二級從x(0)開始,跨接兩階蝶形,再取每條對稱
%第m級從x(0)開始,跨接2^(m-1)階蝶形,再取每條對稱....
%--------------------------------------------------------------------------
for mm=1:m %將DFT做m次基2分解，從左到右，對每次分解作DFT運算
Nmr=2^mm;
u=1; %旋轉因子u初始化
WN=exp(-j*2*pi/Nmr); %本次分解的基本DFT因子WN＝exp(-i*2*pi/Nmr)
for n=1:Nmr/2 %本次跨越間隔內的各次碟形運算
for k=n:Nmr:N %本次碟形運算的跨越間隔為Nmr=2^mm
kp=k+Nmr/2; %確定碟形運算的對應單元下標(對稱性)
t=x(kp)*u; %碟形運算的乘積項
x(kp)=x(k)-t; %碟形運算的加法項
x(k)=x(k)+t;
end
u=u*WN; %修改旋轉因子，多乘一個基本DFT因子WN
end
end
y=x; %輸出

Ⅱ 以2為基的FFT演算法的基本運算單元是什麼

T/FFT的發展歷史
離散傅里葉變換（Discrete Fourier Transform，DFT）是數字信號處理最重要的基石之一，也是對信號進行分析和處理時最常用的工具之一。在200多年前法國數學家、物理學家傅里葉提出後來以他名字命名的傅里葉級數之後，用DFT這個工具來分析信號就已經為人們所知。歷史上最偉大的數學家之一。
歐拉是第一個使用「函數」一詞來描述包含各種參數的表達式的人，例如：y = f(x)。他是把微積分應用於物理學的先驅者之一。 給出了一個用實變數函數表示傅立葉級數系數的方程； 用三角級數來描述離散聲音在彈性媒介中傳播，發現某些函數可以通過餘弦函數之和來表達。 但在很長時間內，這種分析方法並沒有引起更多的重視，最主要的原因在於這種方法運算量比較大。直到1965年，Cooley和Tukey在《計算機科學 》發表著名的《機器計算傅立葉級數的一種演算法》論文，FFT才開始大規模應用。
那個年代，有個肯尼迪總統科學咨詢委員會。其中有項研究主題是，對蘇聯核測試進行檢測，Tukey就是其中一員。美國/蘇聯核測試提案的批准，主要取決於不實地訪問核測試設施而做出檢測的方法的發展。其中一個想法是，分析離海岸的地震計情況，這種計算需要快速演算法來計算DFT。其它應用是國家安全，如用聲學探測遠距離的核潛艇。所以在軍事上，迫切需要一種快速的傅立葉變換演算法，這也促進了FFT的正式提出。
FFT的這種方法充分利用了DFT運算中的對稱性和周期性，從而將DFT運算量從N2減少到N*log2N。當N比較小時，FFT優勢並不明顯。但當N大於32開始，點數越大，FFT對運算量的改善越明顯。比如當N為1024時，FFT的運算效率比DFT提高了100倍。在庫利和圖基提出的FFT演算法中，其基本原理是先將一個N點時域序列的DFT分解為N個1點序列的DFT，然後將這樣計算出來的N個1點序列DFT的結果進行組合，得到最初的N點時域序列的DFT值。實際上，這種基本的思想很早就由德國偉大的數學家高斯提出過，在某種情況下，天文學計算（也是現在FFT應用的領域之一）與等距觀察的有限集中的行星軌道的內插值有關。由於當時計算都是靠手工，所以產生一種快速演算法的迫切需要。 而且，更少的計算量同時也代表著錯誤的機會更少，正確性更高。高斯發現，一個富氏級數有寬度N=N1*N2，可以分成幾個部分。計算N2子樣本DFT的N1長度和N1子樣本DFT的N2長度。只是由於當時尚欠東風——計算機還沒發明。在20世紀60年代，伴隨著計算機的發展和成熟，庫利和圖基的成果掀起了數字信號處理的革命，因而FFT發明者的桂冠才落在他們頭上。
之後，桑德（G.Sand）-圖基等快速演算法相繼出現，幾經改進，很快形成了一套高效運算方法，這就是現在的快速傅立葉變換（FFT）。這種演算法使DFT的運算效率提高1到2個數量級，為數字信號處理技術應用於各種信號的實時處理創造了良好的條件，大大推進了數學信號處理技術。1984年，法國的杜哈梅（P.Dohamel）和霍爾曼（H.Hollamann）提出的分裂基塊快速演算法，使運算效率進一步提高。
庫利和圖基的FFT演算法的最基本運算為蝶形運算，每個蝶形運算包括兩個輸入點，因而也稱為基-2演算法。在這之後，又有一些新的演算法，進一步提高了FFT的運算效率，比如基-4演算法，分裂基演算法等。這些新演算法對FFT運算效率的提高一般在50%以內，遠遠不如FFT對DFT運算的提高幅度。從這個意義上說，FFT演算法是里程碑式的。可以說，正是計算機技術的發展和FFT的出現，才使得數字信號處理迎來了一個嶄新的時代。除了......

Ⅲ 求教在基2-FFT演算法中補零後輸出幅值減小的問題

1.補零可以使FFT後的結果更平滑，可以反映出原信號的頻譜。因為FFT前後的點數一樣， 實際上補零的作用是增加了頻域的顯示解析度。如果有MATLAB可以看到 補零前的數據和補零後的數據 圖形是基本一致的，但是多了補的0的個數個采樣點來平滑。\r\n\r\n2.補零不會增加你數據中攜帶的信息。所以不能提高信號的頻率解析度，就是說如果你的采樣率不夠表現信號特性，你補零後，貌似采樣率夠了，但是實際上並不能顯示出信號的正確信息。\r\n\r\n3.利用插值(就是根據信號波形補充可能的圖形位置)也可以補償數據到2的整數次方，插值會攜帶數據信息，根據你的插值方法可以增加采樣率。

Ⅳ 基數為2的FFT演算法

從上節所述，FFT演算法快速的關鍵在於將原來傅氏矩陣分解為每一行僅含有兩個非零項l與Wⁱ的矩陣的乘積。下面用基數為2，即N=2ⁿ的情形討論矩陣的分解過程.並主要按時間分解的情況討論。

按時間分解的FFT演算法

設N=2ⁿ，n為正整數。考慮輸入序列x₀(l)的DFT

物探數字信號分析與處理技術

將l與m用二進製表示

物探數字信號分析與處理技術

將(7-2-2)代入(7-2-1)中，得到

物探數字信號分析與處理技術

為了說明問題，我們取N=8，於是從(7-2-2)得到

物探數字信號分析與處理技術

從(7-2-4)和(7-2-3)得到

物探數字信號分析與處理技術

將(7-2-5)中的W的指數按時間l進行分解，有

物探數字信號分析與處理技術

因為

物探數字信號分析與處理技術

故從(7-2-6)得到

物探數字信號分析與處理技術

將上式代入(7-2-5)中得到

物探數字信號分析與處理技術

物探數字信號分析與處理技術

我們在公式(7-2-7)中由里往外求和，並置

物探數字信號分析與處理技術

於是得到

物探數字信號分析與處理技術

首先寫出(7-2-8)的所有式子

物探數字信號分析與處理技術

將方程組(7-2-12)寫成矩陣形式，得到

物探數字信號分析與處理技術

我們看到(7-2-13)中的方陣，正好是(7-1-13)中的方陣，也就是(7-1-12)中被分解出來的第3個矩陣，只不過這里的x₁(l)與x₀(l)中的l是用二進制數表示而已。

再寫出(7-2-9)的所有式子，得到

物探數字信號分析與處理技術

將方程組寫成矩陣形式，則有

物探數字信號分析與處理技術

顯然(7-2-15)中的矩陣，正好是(7-1-14)中的方陣，也就是(7-1-12)中被分解出來的第二個矩陣，只不過這里的x₂(l)與x₁(l)是用二進制數表示而已，最後將(7-2-10)中的全部式子寫出，得到

物探數字信號分析與處理技術

將方程組(7-2-16)寫成矩陣形式，則有

物探數字信號分析與處理技術

顯然，(7-2-17)中的方陣正是(7-1-15)中的方陣，也就是(7-1-12)中被分解出來的第1個矩陣，只不過這里的x₃(l)與x₂(l)中的l是用二進制數表示。

由此可見，(7-2-7)中由里往外的三個求和式(7-2-8)、(7-2-9)及(7-2-10)，完全確定了(7-1-12)中三個被分解的矩陣因子。求和得到的最終結果x₃(m₀，m₁，m₂)，與我們所要求的X(m₂，m₁，m₀)正好是逆序的。

到此為止，我們就看到(7-1-11)中的方陣是怎樣被分解成三個方陣因子的。對於N=8，方程(7-2-8)～(7-2-11)就是計算DFT的FFT演算法。為了對FFT演算法有一個直觀的了解並便於編製程序，我們以N=8為例，畫出其流程圖(圖7-2-1)。

根據(7-2-13)，將其中的W⁴用-W⁰代替，畫出從x₀(r)到x₁(r)的流程圖。這一迭代過程用符號#1表示;再根據(7-2-15)，將其中的與W⁴、W⁶分別換成-W⁰與-W²，畫出從x₁(r)到x₂(r)的流程圖，這一迭代過程記為#2;最後，根據(7-2-17)，將其中的W⁴、W⁶、W⁵、W⁷分別換成-W⁰、-W²、-W¹、-W³，畫出流程圖7-2-3合並圖7-2-1～7-2-3，就得到從x₀(r)到x₃(r)的完整流程圖7-2-4。

圖7-2-1 第一次遞推

圖7-2-2 第二次遞推

在圖7-2-5中，畫出N=16=2⁴的FFT演算法流程圖:

根據從x₀到譜X的FFT演算法流程圖7-2-4與圖7-2-5，我們總結出如下幾點:

(1)從x₀到終值x_r的最大迭代次數r，由r=log₂N確定。

例如，N=8，最大迭代次數r=3;N=16，最大迭代次數r=4。

(2)在第r次迭代中，要乘的W因子為

圖7-2-3 第三次遞推

例如，N=8，在第一次迭代中，要乘因子W⁰;在第二次迭代中要乘因子W⁰，W¹，W²，W³。

(3)在第r次迭代中，包含2^r-1個組，每個組

包含 。例如N=8，第一次迭代r=1，有

一個組，每組包含8個x(s);在第二次迭代中包含2個組，每組包含4個x(s);第三次迭代中包含4個組，每組2個x(s)。

圖7-2-4 x₀(r)到x₃(r)的完整流程圖

(4)在第r次迭代中，各組包含的W因子各不相同，且每一組僅包含一種類型的因子 ，此因子在組中一半數為正，另一半數為負。例如N=8，第二次迭代中，第一組包含因子W⁰，且在該組中一半數為正，另一半數為負;第二組包含因子W²，在該組中也是一半數為正，另一半數為負。

(5)在第r次迭代中，各組包含的W因子除正負號外類型均相同。所以只須確定每組中第一個因子，之後按半數反號，即得到所求W因子。具體做法是，在每組第一個因子W^SN2r對應的x_r(k)中，將k表示成n位的二進制數，n=log₂N，並把這個二進制數右移n-r位，左邊空出的地方添零補足n位，之後再將此n位二進制數逆位，即得到所求W因子的指數。例如，N=8，迭代#2包含兩組，每組包含4個x₂(k)，第二組第一個因子W對應於x₂(4)。將4表示成3位的二進制數為100，把它右移1位成10，右邊添零補成3位為010，逆位仍為010，故所求因子為W²，第2組全部W因子為W²，W²，-W²，-W²。又如，N=16，迭代#3中包含4個組，每組包含4個x₃(k)，第4組第1個因子W對應於x₃(12)。將12表示成4位的二進制數為1100。右移1位變成110，將左邊空處添零補成4位為0110，逆位仍為0110，故所求因子為W⁶，從而第4組全部W因子為W⁶，W⁶，-W⁶與-W⁶。

圖7-2-5 N=16=2⁴的FFT演算法流程圖

(6)如果已知N=2的FFT演算法，容易從它求得n=2的FFT演算法。具體作法是，在n=2^n-1的FFT演算法中，將所有x_r(l)的個數加倍，所有W的個數及其乘冪加倍，就得N=2ⁿ中前n-1次迭代的全部結果。之後，將新得到的第n-1次迭代中乘冪相同的W個數減半，就是第n次迭代中前2ⁿ/2個W，將這些W的乘冪依次加1，就得到後2ⁿ/2個W。例如N=16的前3次迭代，都是N=8的三次迭代中所有x_r(l)的個數加倍，W的個數及其乘冪加倍的結果。再將N=16的第三次迭代中乘冪相同的W個數減半，就是第4次迭代中前8個W。

(7)在第r-1次迭代中的x_r-1(i)與x_r-1(j)僅用於計算r次迭代中的x_r(i)與x_r(j)，而不會用於計算任何其它的x_r(k)與x_r(l)。例如N=16的第二次迭代中的x₂(0)與x₂(2)，只用於計算第三次迭代中的x₃(0)與x₃(2);第三次迭代中的x₃(8)與x₃(9)也只用於計算第四次迭代中的x₄(8)與x₄(9)。因此，我們可以把第r次迭代中的x_r(i)與x_r(j)，存放到r-1次迭代x_r-1(i)與x_r-1(j)所佔用的原存儲單元中去，這樣，所需要的計算機存儲容量就只限於原數據序列占據的單元數。如果是復序列的話，存儲單元要加倍。

(8)上述FFT演算法也可用於計算逆離散傅氏變換(IDFT)(圖7-2-6)，只不過在計算時要將上述FFT演算法中的W因子用其共軛W^*代替，並將最後迭代計算的結果統統乘以1/N.

圖7-2-6 N=8的逆離散富氏變換流程圖

Ⅳ 採用基2的FFT演算法共需要多少 復數乘法運算

二分之（N）*log2（N）

Ⅵ 如何實現128點的基2-FFT演算法,並與MATLAB的fft演算法作對比分析.

我只能給你一個fft演算法，流程圖說起來有點復雜，可以matlab裡面的函數tic（開啟時鍾）t=toc（關閉時鍾）t就是運算過程的時間
當然tic放程序開始，toc放結尾，來分析之即可
function d=lxfft(x)
n=length(x);
if n>2
for i=0:n/2-1
x1(i+1)=x(2*i+1);
x2(i+1)=x(2*i+2);
end
X1=lxfft(x1);
X2=lxfft(x2);
for i=0:n/2-1
X2(i+1)= X2(i+1)*exp(-j*2*pi/n*i);//旋轉因子
d(i+1)=X1(i+1)+X2(i+1);
d(i+n/2+1)=X1(i+1)-X2(i+1);
end
else
d(1)=x(1)+x(2);
d(2)=x(1)-x(2);
end
end

Ⅶ 基2—fft演算法的軟體實現(MATLAB代碼)

參考網路： clc; clear all; close all; x=ones(1,128); %輸入的信號，自己可以改變 %整體運用原位計算 m=nextpow2(x);N=2^m; % 求x的長度對應的2的最低冪次m if length(x)<N x=[x,zeros(1,N-length(x))]; % 若x的長度不是2的冪，補零到2的整數冪 end nxd=bin2dec(fliplr(dec2bin([1:N]-1,m)))+1; % 求1:2^m數列序號的倒序 y=x(nxd); % 將x倒序排列作為y的初始值 for mm=1:m % 將DFT作m次基2分解,從左到右，對每次分解作DFT運算,共做m級蝶形運算，每一級都有2^(mm-1)個蝶形結 Nz=2^mm;u=1; % 旋轉因子u初始化為WN^0=1 WN=exp(-i*2*pi/Nz); % 本次分解的基本DFT因子WN=exp(-i*2*pi/Nz) for j=1:Nz/2 % 本次跨越間隔內的各次蝶形運算,在進行第mm級運算時需要2^(mm-1)個 蝶形 for k=j:Nz:N % 本次蝶形運算的跨越間隔為Nz=2^mm kp=k+Nz/2; % 蝶形運算的兩個因子對應單元下標的關系 t=y(kp)*u; % 蝶形運算的乘積項 y(kp)=y(k)-t; % 蝶形運算 y(k)=y(k)+t; % 蝶形運算 end u=u*WN; % 修改旋轉因子,多乘一個基本DFT因子WN end end y y1=fft(x) %自己編的FFT跟直接調用的函數運算以後的結果進行對比

Ⅷ 試畫出信號按時間抽取的基-2FFT演算法信號流圖，並寫出對應過程奇偶分流的公式。

基2演算法，序列的長度是為2的冪，序列的DFT為。序列可以由奇序列和偶序列組成，DFT分別為和。 從最後一級往前分解對應的蝶形結構，這些蝶形結構最左邊的輸入都是序列的DFT值，而分解直到最左邊的蝶形結構是兩點序列的DFT，此時最左邊的值是序列x[k]。

f1=50; %10Hz

f2=100; %100Hz

%抽樣頻率

Fs=1000; %100Hz

%抽樣點數N

L=10;

N=2^L;

%抽樣脈沖序列

n = 0:N-1;

t = n./Fs;

% f2 一個周期的采樣數

M = floor(Fs/f2);

%被采樣信號

x = cos(2*pi*f1.*t)+sin(2*pi*f2.*t);

%采樣序列

subplot(311);

stem(t(1:2*M),x(1:2*M));

hold off;

%傅里葉變換

%根據有限長序列的離散傅里葉變換公式計算DFT

n = 0:N-1;

k = 0:N-1;

F = x * exp(-j*2*pi/N).^(n'*k);

subplot(312);

plot(n,abs(F));

subplot(313);

plot(k,angle(F));

(8)可以用基2FFT演算法擴展閱讀：

庫利－圖基快速傅里葉變換演算法是將序列長為N的DFT分區為兩個長為N/2的子序列的DFT，因此這一應用只適用於序列長度為2的冪的DFT計算，即基2-FFT。實際上，如同高斯和庫利與圖基都指出的那樣，庫利－圖基演算法也可以用於序列長度N為任意因數分解形式的DFT，即混合基FFT，而且還可以應用於其他諸如分裂基FFT等變種。

盡管庫利－圖基演算法的基本思路是採用遞歸的方法進行計算，大多數傳統的演算法實現都將顯示的遞歸演算法改寫為非遞歸的形式。另外，因為庫利－圖基演算法是將DFT分解為較小長度的多個DFT，因此它可以同任一種其他的DFT演算法聯合使用。