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 undTwiddle-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-VerteilungDer 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

`timescale 1ns/100ps
/**************** 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

timescale 1ns/100ps
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

`timescale 1ns/100ps
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

clear all;close all;clc;
%=======================================================
% 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

clear all;close all;clc;
%=======================================================
% 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