FFT (Fast Fourier Transform), auch bekannt als schnelle Fourier-Transformation, ist ein effizienter Algorithmus für DFT (Diskrete Fourier-Transformation). Er spielt eine unersetzliche Rolle in digitalen Verarbeitungsmethoden, die auf Zeit-Frequenz-Transformationsanalyse basieren.
FFT-Prinzip
Formelherleitung
Die DFT-Berechnungsformel lautet:

wobei,

Durch Aufteilen der Formel der diskreten Fourier-Transformation in ungerade und gerade Terme können die ersten N/2 Punkte ausgedrückt werden als:

Analog dazu können die letzten N/2 Punkte ausgedrückt werden als:

Man erkennt, dass die Werte der letzten N/2 Punkte vollständig durch die Zwischenwerte bestimmt werden können, die bei der Berechnung der ersten N/2 Punkte erhalten werden. Führen Sie die Gerade-Ungerade-Zerlegung für A[k] und B[k] weiter durch, bis daraus eine 2-Punkt-DFT wird, wodurch viele wiederholte Berechnungen vermieden und der Prozess der schnellen diskreten Fourier-Transformation (FFT) realisiert wird.
Algorithmusstruktur
Das Strukturdiagramm der 8-Punkt-FFT-Berechnung ist wie folgt.
Aus der Abbildung ist ersichtlich, dass der DFT-Prozess mit nur wenigen einfachen Multiplikationen und Additionen abgeschlossen werden kann, anstatt für jedes Datenelement eine mühsame Multiplikation und Akkumulation durchzuführen.

Wichtige Eigenschaften
(1) Begriff der Stufe
Jede Aufteilung wird als eine Stufe der Operation bezeichnet.
Sei N die Anzahl der FFT-Operationspunkte und M die Gesamtzahl der Stufen; sie erfüllen:

Jede Stufe wird durch m = 0, 1, 2, ..., M-1 gekennzeichnet.
Um die Split-Berechnung zu erleichtern, ist die Anzahl der FFT-Punkte N oft eine ganzzahlige Zweierpotenz.
(2) Butterfly-Einheit
Die FFT-Berechnungsstruktur besteht aus mehreren Butterfly-Operationseinheiten. Das schematische Diagramm jeder Operationseinheit ist wie folgt:

Der Eingang und der Ausgang der Butterfly-Einheit genügen:

wobei,
Jede Butterfly-Einheit führt während ihres Betriebs eine Multiplikation und zwei Additionen durch.
Jede Stufe hat N/2 Butterfly-Einheiten.
Daher beträgt die Anzahl der Multiplikationen und Additionen, die zur Durchführung einer FFT erforderlich sind, jeweils:

(3) Konzept der Gruppe
Die N/2 Butterfly-Einheiten in jeder Stufe können in mehrere Gruppen unterteilt werden, und jede Gruppe hat die gleiche Struktur und
Twiddle-Faktor-Verteilung.
Zum Beispiel kann es bei m=0 in N/2=4 Gruppen unterteilt werden.
Wenn m=1, kann es in N/4=2 Gruppen unterteilt werden.
Wenn m=M-1, kann es nur in 1 Gruppe unterteilt werden.
(4)
Twiddle-Faktor-Verteilung
Der Twiddle-Faktor existiert in Stufe m, wobei
。
In der zweiten Stufe der 8-Punkt-FFT, d. h. m=1, kann der Twiddle-Faktor der Butterfly-Operation vereinfacht werden zu:

(5) Bit-Umkehr
Für eine FFT-Berechnung mit N=8 Punkten sind die Binärcodes, die den Positionen X(0) ~ X(7) entsprechen:
X(000), X(001), X(010), X(011), X(100), X(101), X(110), X(111)
Kehren Sie die Binärcodes ihrer Positionen um:
X(000), X(100), X(010), X(110), X(001), X(101), X(011), X(111)
Die Dezimalwerte, die den Positionen zu diesem Zeitpunkt entsprechen, sind:
X(0), X(4), X(2), X(6), X(1), X(5), X(3), X(7)
Dies entspricht genau der Reihenfolge der Eingabedaten für die erste Stufe der FFT.
Diese Eigenschaft ist vorteilhaft für die programmtechnische Implementierung der FFT.
FFT-Design
Entwurfsbeschreibung
Um den FFT-Transformationsprozess anhand einer Simulation einfach zu veranschaulichen, wird die Anzahl der Datenpunkte auf einen kleinen Wert von 8 gesetzt.
Wenn die Daten seriell eingegeben werden, müssen sie zuerst gepuffert werden, daher ist die Dateneingabemethode in diesem Entwurf parallel.
Die Dateneingabe ist in zwei Teile unterteilt: Realteil und Imaginärteil, daher sind auch die Berechnungsergebnisse in Realteil und Imaginärteil unterteilt.
Der Entwurf verwendet eine Pipeline-Struktur und berücksichtigt vorerst den Ressourcenverbrauch nicht.
Um die Entwurfsstruktur einfacher zu machen, wird hier ein Kompromiss eingegangen: Die Multiplikationsberechnung verwendet direkt den Multiplikationsoperator. Wenn der FFT-Entwurf in der Praxis angewendet wird, muss die Multiplikationsstruktur durch einen Pipeline-Multiplizierer ersetzt werden, oder es ist der offizielle hocheffiziente Multiplizierer-IP zu verwenden.
Entwurf der Butterfly-Einheit
Die Butterfly-Einheit verwendet Festkommaoperationen, daher muss der Twiddle-Faktor auf Festkomma quantisiert werden.
Verwenden Sie MATLAB, um den Twiddle-Faktor mit 8192 zu multiplizieren (Linksverschiebung um 13 Bits); siehe Anhang.
Um zu verhindern, dass die Multiplikation und Addition in Butterfly-Operationen die Bitbreite Stufe für Stufe erhöhen, müssen die Ausgabedaten nach jeder Operationsstufe auf eine feste Bitbreite abgeschnitten werden. Dadurch wird auch der Effekt der Twiddle-Faktor-Skalierung entfernt. Der Code lautet wie folgt:
Beispiel
/**************** butter unit *************************
Xm(p) ------------------------> Xm+1(p)
- ->
- -
-
- -
- ->
Xm(q) ------------------------> Xm+1(q)
Wn -1
*//////////////////////////////////////////////////////
module butterfly
(
input clk,
input rstn,
input en,
input signed [23:0] xp_real, // Xm(p)
input signed [23:0] xp_imag,
input signed [23:0] xq_real, // Xm(q)
input signed [23:0] xq_imag,
input signed [15:0] factor_real, // Wnr
input signed [15:0] factor_imag,
output valid,
output signed [23:0] yp_real, //Xm+1(p)
output signed [23:0] yp_imag,
output signed [23:0] yq_real, //Xm+1(q)
output signed [23:0] yq_imag);
reg [4:0] en_r ;
always @(posedge clk or negedge rstn) begin
if (!rstn) begin
en_r <= 'b0 ;
end
else begin
en_r <= {en_r[3:0], en} ;
end
end
//=====================================================//
//(1.0) Xm(q) multiplizieren und Xm(p) verzögern
reg signed [39:0] xq_wnr_real0;
reg signed [39:0] xq_wnr_real1;
reg signed [39:0] xq_wnr_imag0;
reg signed [39:0] xq_wnr_imag1;
reg signed [39:0] xp_real_d;
reg signed [39:0] xp_imag_d;
always @(posedge clk or negedge rstn) begin
if (!rstn) begin
xp_real_d <= 'b0;
xp_imag_d <= 'b0;
xq_wnr_real0 <= 'b0;
xq_wnr_real1 <= 'b0;
xq_wnr_imag0 <= 'b0;
xq_wnr_imag1 <= 'b0;
end
else if (en) begin
xq_wnr_real0 <= xq_real * factor_real;
xq_wnr_real1 <= xq_imag * factor_imag;
xq_wnr_imag0 <= xq_real * factor_imag;
xq_wnr_imag1 <= xq_imag * factor_real;
//8192-mal als Wnr erweitern
xp_real_d <= {{4{xp_real[23]}}, xp_real[22:0], 13'b0};
xp_imag_d <= {{4{xp_imag[23]}}, xp_imag[22:0], 13'b0};
end
end
//(1.1) multiplizierte Ergebnisse von Xm(q) holen und Xm(p) erneut verzögern
reg signed [39:0] xp_real_d1;
reg signed [39:0] xp_imag_d1;
reg signed [39:0] xq_wnr_real;
reg signed [39:0] xq_wnr_imag;
always @(posedge clk or negedge rstn) begin
if (!rstn) begin
xp_real_d1 <= 'b0;
xp_imag_d1 <= 'b0;
xq_wnr_real <= 'b0 ;
xq_wnr_imag <= 'b0 ;
end
else if (en_r[0]) begin
xp_real_d1 <= xp_real_d;
xp_imag_d1 <= xp_imag_d;
// Bitbreitenmarge im Voraus festlegen, um Datenüberlauf zu verhindern
xq_wnr_real <= xq_wnr_real0 - xq_wnr_real1 ;
xq_wnr_imag <= xq_wnr_imag0 + xq_wnr_imag1 ;
end
end
//======================================================//
//(2.0) butter Ergebnisse
reg signed [39:0] yp_real_r;
reg signed [39:0] yp_imag_r;
reg signed [39:0] yq_real_r;
reg signed [39:0] yq_imag_r;
always @(posedge clk or negedge rstn) begin
if (!rstn) begin
yp_real_r <= 'b0;
yp_imag_r <= 'b0;
yq_real_r <= 'b0;
yq_imag_r <= 'b0;
end
else if (en_r[1]) begin
yp_real_r <= xp_real_d1 + xq_wnr_real;
yp_imag_r <= xp_imag_d1 + xq_wnr_imag;
yq_real_r <= xp_real_d1 - xq_wnr_real;
yq_imag_r <= xp_imag_d1 - xq_wnr_imag;
end
end
//(3) die niedrigen 13bits wegen Wnr verwerfen
assign yp_real = {yp_real_r[39], yp_real_r[13+23:13]};
assign yp_imag = {yp_imag_r[39], yp_imag_r[13+23:13]};
assign yq_real = {yq_real_r[39], yq_real_r[13+23:13]};
assign yq_imag = {yq_imag_r[39], yq_imag_r[13+23:13]};
assign valid = en_r[2];
endmodule
Instanziierung auf oberster Ebene
Instanziieren Sie gemäß dem Strukturdiagramm des FFT-Algorithmus die Butterfly-Einheiten, um die endgültige FFT-Funktion zu vervollständigen.
Sie können 12 Mal manuell nacheinander gemäß der Eingabe-Ausgabe-Zuordnung der Butterfly-Einheiten in jeder Stufe instanziieren oder generate zur Instanziierung verwenden. In diesem Fall müssen Sie mit den Eigenschaften von "Gruppen" und "Stufen" in der FFT sehr vertraut sein:
-
(1) Ein 8-Punkt-FFT-Entwurf erfordert 3 Operationsstufen. Jede Stufe hat 4 Butterfly-Einheiten, und die Anzahl der Gruppen in jeder Stufe ist jeweils 4, 2, 1.
-
(2) In jeder Stufe ist der Abstand zwischen den beiden Eingangsports einer Butterfly-Einheit innerhalb einer Gruppe immer
(m ist der Stufenindex, entsprechend der Linksverschiebungsoperation 1<<m); der Abstand zwischen den ersten Eingangsports der beiden Butterfly-Einheiten in einer Gruppe beträgt 1. -
(3) Der Abstand zwischen den ersten Eingangsports der ersten Butterfly-Einheiten benachbarter Gruppen in jeder Stufe ist
(entsprechend der Linksverschiebungsoperation 2<<m).
Der Instanziierungscode lautet wie folgt.
Hierbei sind die eindimensionalen und zweidimensionalen Adressen der Matrixsignale xm_real (xm_imag) Bezeichner, die die Stufe und Gruppe repräsentieren.
Wenn die Verbindungsbeziehungen zwischen Signalports bestimmt werden, wird scheinbar komplexe Beurteilungslogik verwendet, und sie enthält außerdem Multiplikationsoperatoren. Tatsächlich ist die letztendlich generierte Schaltung genau dieselbe wie beim manuellen Schreiben von Code zur Instanziierung von 12 Butterfly-Einheiten. Das liegt daran, dass die Variablen im Generate-Block nur beim Generieren der tatsächlichen Schaltung unterstützen und die Berechnung und Beurteilung der zugehörigen Werte zur Kompilierzeit abgeschlossen werden. Diese Variablen erzeugen sicherlich keine tatsächlichen Schaltungen; sie bieten lediglich eine Methode zur schnelleren Modulinstanziierung.
Beispiel
module fft8 (
input clk,
input rstn,
input en,
input signed [23:0] x0_real,
input signed [23:0] x0_imag,
input signed [23:0] x1_real,
input signed [23:0] x1_imag,
input signed [23:0] x2_real,
input signed [23:0] x2_imag,
input signed [23:0] x3_real,
input signed [23:0] x3_imag,
input signed [23:0] x4_real,
input signed [23:0] x4_imag,
input signed [23:0] x5_real,
input signed [23:0] x5_imag,
input signed [23:0] x6_real,
input signed [23:0] x6_imag,
input signed [23:0] x7_real,
input signed [23:0] x7_imag,
output valid,
output signed [23:0] y0_real,
output signed [23:0] y0_imag,
output signed [23:0] y1_real,
output signed [23:0] y1_imag,
output signed [23:0] y2_real,
output signed [23:0] y2_imag,
output signed [23:0] y3_real,
output signed [23:0] y3_imag,
output signed [23:0] y4_real,
output signed [23:0] y4_imag,
output signed [23:0] y5_real,
output signed [23:0] y5_imag,
output signed [23:0] y6_real,
output signed [23:0] y6_imag,
output signed [23:0] y7_real,
output signed [23:0] y7_imag
);
//Betriebsdaten
wire signed [23:0] xm_real [3:0] [7:0];
wire signed [23:0] xm_imag [3:0] [7:0];
wire en_connect [15:0] ;
assign en_connect[0] = en;
assign en_connect[1] = en;
assign en_connect[2] = en;
assign en_connect[3] = en;
//Faktor, multipliziert mit 0x2000
wire signed [15:0] factor_real [3:0] ;
wire signed [15:0] factor_imag [3:0];
assign factor_real[0] = 16'h2000; //1
assign factor_imag[0] = 16'h0000; //0
assign factor_real[1] = 16'h16a0; //sqrt(2)/2
assign factor_imag[1] = 16'he95f; //-sqrt(2)/2
assign factor_real[2] = 16'h0000; //0
assign factor_imag[2] = 16'he000; //-1
assign factor_real[3] = 16'he95f; //-sqrt(2)/2
assign factor_imag[3] = 16'he95f; //-sqrt(2)/2
// Eingabeinitialisierung; bezogen auf Bit-Umkehr
assign xm_real[0][0] = x0_real;
assign xm_real[0][1] = x4_real;
assign xm_real[0][2] = x2_real;
zuweisen xm_real[0][3] = x6_real;
zuweisen xm_real[0][4] = x1_real;
zuweisen xm_real[0][5] = x5_real;
zuweisen xm_real[0][6] = x3_real;
zuweisen xm_real[0][7] = x7_real;
zuweisen xm_imag[0][0] = x0_imag;
zuweisen xm_imag[0][1] = x4_imag;
zuweisen xm_imag[0][2] = x2_imag;
zuweisen xm_imag[0][3] = x6_imag;
zuweisen xm_imag[0][4] = x1_imag;
zuweisen xm_imag[0][5] = x5_imag;
zuweisen xm_imag[0][6] = x3_imag;
assign xm_imag[0][7] = x7_imag;
//butter Instanziierung
//integer index[11:0] ;
genvar m, k;
generate
//3 Stufen
for(m=0; m<=2; m=m+1) begin: stage
for (k=0; k<=3; k=k+1) begin: Einheit
butterfly u_butter(
.clk (clk ) ,
.rstn (rstn ) ,
.en (en_connect[m*4 + k] ) ,
// Ob innerhalb der Gruppe? Gruppenindex + Intra-Gruppen-Index : nächster Gruppenindex + neuer Intra-Gruppen-Index
.xp_real (xm_real[ m ] [k[m:0] < (1<<m) ?
(k[3:m] << (m+1)) + k[m:0] :
(k[3:m] << (m+1)) + (k[m:0]-(1<<m))] ),
.xp_imag (xm_imag[ m ] [k[m:0] < (1<<m) ?
(k[3:m] << (m+1)) + k[m:0] :
(k[3:m] << (m+1)) + (k[m:0]-(1<<m))] ),
.xq_real (xm_real[ m ] [(k[m:0] < (1<<m) ?
(k[3:m] << (m+1)) + k[m:0] :
(k[3:m] << (m+1)) + (k[m:0]-(1<<m))) + (1<<m) ]), // Erhöhe den Abstand zwischen den beiden Eingangsports der Butterfly-Einheit
.xq_imag (xm_imag[ m ] [(k[m:0] < (1<<m) ?
(k[3:m] << (m+1)) + k[m:0] :
(k[3:m] << (m+1)) + (k[m:0]-(1<<m))) + (1<<m) ]),
.factor_real(factor_real[k[m:0]<(1<<m)?
k[m:0] : k[m:0]-(1<<m) ]),
.factor_imag(factor_imag[k[m:0]<(1<<m)?
k[m:0] : k[m:0]-(1<<m) ]),
//Ausgabedaten
.valid (en_connect[ (m+1)*4 + k ] ),
.yp_real (xm_real[ m+1 ][k[m:0] < (1<<m) ?
(k[3:m] << (m+1)) + k[m:0] :
(k[3:m] << (m+1)) + (k[m:0]-(1<<m))] ),
.yp_imag (xm_imag[ m+1 ][(k[m:0]) < (1<<m) ?
(k[3:m] << (m+1)) + k[m:0] :
(k[3:m] << (m+1)) + (k[m:0]-(1<<m))] ),
.yq_real (xm_real[ m+1 ][(k[m:0] < (1<<m) ?
(k[3:m] << (m+1)) + k[m:0] :
(k[3:m] << (m+1)) + (k[m:0]-(1<<m))) + (1<<m) ]),
.yq_imag (xm_imag[ m+1 ][((k[m:0]) < (1<<m) ?
(k[3:m] << (m+1)) + k[m:0] :
(k[3:m] << (m+1)) + (k[m:0]-(1<<m))) + (1<<m) ])
);
end
end
endgenerate
assign valid = en_connect[12];
assign y0_real = xm_real[3][0] ;
assign y0_imag = xm_imag[3][0] ;
assign y1_real = xm_real[3][1] ;
assign y1_imag = xm_imag[3][1] ;
assign y2_real = xm_real[3][2] ;
assign y2_imag = xm_imag[3][2] ;
assign y3_real = xm_real[3][3] ;
assign y3_imag = xm_imag[3][3] ;
assign y4_real = xm_real[3][4] ;
assign y4_imag = xm_imag[3][4] ;
assign y5_real = xm_real[3][5] ;
assign y5_imag = xm_imag[3][5] ;
assign y6_real = xm_real[3][6] ;
assign y6_imag = xm_imag[3][6] ;
assign y7_real = xm_real[3][7] ;
assign y7_imag = xm_imag[3][7] ;
endmodule
testbench
Die Testbench ist wie folgt geschrieben, hauptsächlich für die kontinuierliche Eingabe von 16 Kanälen mit reellen und komplexen Daten. Da jede FFT nur 8 Datenpunkte hat, sind die Eingangsdaten beliebig, keine regelmäßigen Daten wie Sinuswellen.
Beispiel
module test ;
reg clk;
reg rstn;
reg en ;
reg signed [23:0] x0_real;
reg signed [23:0] x0_imag;
reg signed [23:0] x1_real;
reg signed [23:0] x1_imag;
reg signed [23:0] x2_real;
reg signed [23:0] x2_imag;
reg signed [23:0] x3_real;
reg signed [23:0] x3_imag;
reg signed [23:0] x4_real;
reg signed [23:0] x4_imag;
reg signed [23:0] x5_real;
reg signed [23:0] x5_imag;
reg signed [23:0] x6_real;
reg signed [23:0] x6_imag;
reg signed [23:0] x7_real;
reg signed [23:0] x7_imag;
wire valid;
wire signed [23:0] y0_real;
wire signed [23:0] y0_imag;
wire signed [23:0] y1_real;
wire signed [23:0] y1_imag;
wire signed [23:0] y2_real;
wire signed [23:0] y2_imag;
wire signed [23:0] y3_real;
wire signed [23:0] y3_imag;
wire signed [23:0] y4_real;
wire signed [23:0] y4_imag;
wire signed [23:0] y5_real;
wire signed [23:0] y5_imag;
wire signed [23:0] y6_real;
wire signed [23:0] y6_imag;
wire signed [23:0] y7_real;
wire signed [23:0] y7_imag;
initial begin
clk = 0; //50MHz
rstn = 0 ;
#10 rstn = 1;
forever begin
#10 clk = ~clk; //50MHz
end
end
fft8 u_fft (
.clk (clk ),
.rstn (rstn ),
.en (en ),
.x0_real (x0_real),
.x0_imag (x0_imag),
.x1_real (x1_real),
.x1_imag (x1_imag),
.x2_real (x2_real),
.x2_imag (x2_imag),
.x3_real (x3_real),
.x3_imag (x3_imag),
.x4_real (x4_real),
.x4_imag (x4_imag),
.x5_real (x5_real),
.x5_imag (x5_imag),
.x6_real (x6_real),
.x6_imag (x6_imag),
.x7_real (x7_real),
.x7_imag (x7_imag),
.valid (valid),
.y0_real (y0_real),
.y0_imag (y0_imag),
.y1_real (y1_real),
.y1_imag (y1_imag),
.y2_real (y2_real),
.y2_imag (y2_imag),
.y3_real (y3_real),
.y3_imag (y3_imag),
.y4_real (y4_real),
.y4_imag (y4_imag),
.y5_real (y5_real),
.y5_imag (y5_imag),
.y6_real (y6_real),
.y6_imag (y6_imag),
.y7_real (y7_real),
.y7_imag (y7_imag));
//Dateneingabe
initial begin
en = 0 ;
x0_real = 24'd10;
x1_real = 24'd20;
x2_real = 24'd30;
x3_real = 24'd40;
x4_real = 24'd10;
x5_real = 24'd20;
x6_real = 24'd30;
x7_real = 24'd40;
x0_imag = 24'd0;
x1_imag = 24'd0;
x2_imag = 24'd0;
x3_imag = 24'd0;
x4_imag = 24'd0;
x5_imag = 24'd0;
x6_imag = 24'd0;
x7_imag = 24'd0;
@(negedge clk) ;
en = 1 ;
forever begin
@(negedge clk) ;
x0_real = (x0_real > 22'h3F_ffff) ? 'b0 : x0_real + 1 ;
x1_real = (x1_real > 22'h3F_ffff) ? 'b0 : x1_real + 1 ;
x2_real = (x2_real > 22'h3F_ffff) ? 'b0 : x2_real + 31 ;
x3_real = (x3_real > 22'h3F_ffff) ? 'b0 : x3_real + 1 ;
x4_real = (x4_real > 22'h3F_ffff) ? 'b0 : x4_real + 23 ;
x5_real = (x5_real > 22'h3F_ffff) ? 'b0 : x5_real + 1 ;
x6_real = (x6_real > 22'h3F_ffff) ? 'b0 : x6_real + 6 ;
x7_real = (x7_real > 22'h3F_ffff) ? 'b0 : x7_real + 1 ;
x0_imag = (x0_imag > 22'h3F_ffff) ? 'b0 : x0_imag + 2 ;
x1_imag = (x1_imag > 22'h3F_ffff) ? 'b0 : x1_imag + 5 ;
x2_imag = (x2_imag > 22'h3F_ffff) ? 'b0 : x2_imag + 3 ;
x3_imag = (x3_imag > 22'h3F_ffff) ? 'b0 : x3_imag + 6 ;
x4_imag = (x4_imag > 22'h3F_ffff) ? 'b0 : x4_imag + 4 ;
x5_imag = (x5_imag > 22'h3F_ffff) ? 'b0 : x5_imag + 8 ;
x6_imag = (x6_imag > 22'h3F_ffff) ? 'b0 : x6_imag + 11 ;
x7_imag = (x7_imag > 22'h3F_ffff) ? 'b0 : x7_imag + 7 ;
end
end
//Simulation beenden
initial #1000 $finish ;
endmodule
Simulationsergebnisse
Grob ist erkennbar, dass die FFT-Ergebnisse pipelineartig ausgegeben werden können.

Mit der in MATLAB integrierten FFT-Funktion, angewendet auf dieselben Daten, sind die FFT-Ergebnisse der ersten 2 Datengruppen wie folgt.
Es ist zu erkennen, dass die FFT-Ergebnisse genau gleich sind, wenn beim ersten Eingangsdatensignal nur der Realteil gültig ist.
Wenn jedoch auch die zweiten Eingangsdaten ein Signal im Imaginärteil enthalten, beginnen die Ergebnisse zwischen den beiden Fehler aufzuweisen, und manchmal sind die Fehler ziemlich groß.

Durch Simulation des in Verilog implementierten FFT-Prozesses mit MATLAB zeigt sich, dass die FFT-Ergebnisse dieses Prozesses im Wesentlichen mit den in Verilog implementierten FFT-Ergebnissen übereinstimmen.
Bilden Sie die Beträge der beiden fehlerhaften FFT-Ergebnisse zum Vergleich, wie in der untenstehenden Abbildung gezeigt.
Es ist zu erkennen, dass die Verläufe der FFT-Ergebnisse ungefähr gleich sind, jedoch an einzelnen Punkten sichtbare Fehler auftreten.

Zusammenfassung des Designs:
Wie im Design der Butterfly-Einheit erwähnt, führt bei der Quantisierung des Twiddle-Faktors die Wahl der Bitbreite zu Fehlern.
Darüber hinaus wird das Operationsergebnis jeder Butterfly-Einheit abgeschnitten, was ebenfalls Fehler verursacht.
MATLAB muss bei der Berechnung der FFT keine Genauigkeitsprobleme berücksichtigen; es führt die FFT-Berechnungen mit seiner höchsten Genauigkeit für die Daten durch.
All dies führt zu Unterschieden zwischen den Ergebnissen der beiden FFT-Berechnungsmethoden.
Interessierte Leser können die Bitbreiten des Twiddle-Faktors und der Eingangsdaten weiter erhöhen und auch die Anzahl der FFT-Punkte erhöhen und dann einen Simulationsvergleich durchführen; der relative Fehler sollte abnehmen.
Anhang: MATLAB-Verwendung
Twiddle-Faktoren generieren
Eine 8-Punkt-FFT benötigt nur 4 Twiddle-Faktoren. Die Twiddle-Faktoren werden mit 8192 skaliert.
Beispiel
%=======================================================
% Wnr-Berechnung
%=======================================================
for r = 0:3
Wnr_factor = cos(pi/4*r) - j*sin(Pi/4*r) ;
Wnr_integer = floor(Wnr_factor * 2^13) ;
if (real(Wnr_integer)<0)
Wnr_real = real(Wnr_integer) + 2^16 ; %Zweierkomplement negativer Zahlen
else
Wnr_real = real(Wnr_integer) ;
end
if (imag(Wnr_integer)<0)
Wnr_imag = imag(Wnr_integer) + 2^16 ;
else
Wnr_imag = imag(Wnr_integer);
end
Wnr(2*r+1,:) = dec2hex(Wnr_real) %Realteil
Wnr(2*r+2,:) = dec2hex(Wnr_imag) %Imaginärteil
end
FFT-Ergebnisvergleich
Die MATLAB-Simulation des in Verilog implementierten FFT-Prozesses ist wie folgt und enthält außerdem einen Vergleich der beiden FFT-Ergebnisse.
Beispiel
%=======================================================
% 8dots fft
%=======================================================
for r=0:3
Wnr(r+1) = cos(pi/4*r) - j*sin(Pi/4*r) ;
end
x = [10, 20, 30, 40, 10, 20 ,30 ,40];
Schrittweite = [1+2j, 1+5j, 31+3j, 1+6j, 23+4j, 1+8j, 6+11j, 1+7j];
x2 = x + Schrittweite;
xm0 = [x2(0+1), x2(4+1), x2(2+1), x2(6+1), x2(1+1), x2(5+1), x2(3+1), x2(7+1)] ;
%% stage1
xm1(1) = xm0(1) + xm0(2)*Wnr(1) ;
xm1(2) = xm0(1) - xm0(2)*Wnr(1) ;
xm1(3) = xm0(3) + xm0(4)*Wnr(1) ;
xm1(4) = xm0(3) - xm0(4)*Wnr(1) ;
xm1(5) = xm0(5) + xm0(6)*Wnr(1) ;
xm1(6) = xm0(5) - xm0(6)*Wnr(1) ;
xm1(7) = xm0(7) + xm0(8)*Wnr(1) ;
xm1(8) = xm0(7) - xm0(8)*Wnr(1) ;
floor(xm1(:))
%% stage2
xm2(1) = xm1(1) + xm1(3)*Wnr(1) ;
xm2(3) = xm1(1) - xm1(3)*Wnr(1) ;
xm2(2) = xm1(2) + xm1(4)*Wnr(2) ;
xm2(4) = xm1(2) - xm1(4)*Wnr(2) ;
xm2(5) = xm1(5) + xm1(7)*Wnr(1) ;
xm2(7) = xm1(5) - xm1(7)*Wnr(1) ;
xm2(6) = xm1(6) + xm1(8)*Wnr(2) ;
xm2(8) = xm1(6) - xm1(8)*Wnr(2) ;
floor(xm2(:))
%% stage3
xm3(1) = xm2(1) + xm2(5)*Wnr(1) ;
xm3(5) = xm2(1) - xm2(5)*Wnr(1) ;
xm3(2) = xm2(2) + xm2(6)*Wnr(2) ;
xm3(6) = xm2(2) - xm2(6)*Wnr(2) ;
xm3(3) = xm2(3) + xm2(7)*Wnr(3) ;
xm3(7) = xm2(3) - xm2(7)*Wnr(3) ;
xm3(4) = xm2(4) + xm2(8)*Wnr(4) ;
xm3(8) = xm2(4) - xm2(8)*Wnr(4) ;
floor(xm3(:))
%% fft
fft1 = fft(x)
fft2 = fft(x2)
plot(1:8, abs(fft2))
hold on
plot(1:8, abs(xm3), 'r')
Quellcode-Download
Herunterladen