FFT (Fast Fourier Transform), également appelée transformée de Fourier rapide, est un algorithme efficace pour la DFT (Discrete Fourier Transform). Elle joue un rôle irremplaçable dans les méthodes de traitement numérique basées sur l'analyse par transformée temps-fréquence.

Principe de la FFT

Dérivation de la formule

La formule de calcul de la DFT est :

où,

En scindant la formule de la transformée de Fourier discrète en termes impairs et pairs, les N/2 premiers points peuvent être exprimés comme :

De même, les N/2 derniers points peuvent être exprimés comme :

On peut voir que les valeurs des N/2 derniers points peuvent être complètement déterminées par les valeurs intermédiaires obtenues lors du calcul des N/2 premiers points. Continuez à effectuer une décomposition pair-impair sur A[k] et B[k] jusqu'à obtenir une DFT à 2 points, ce qui évite de nombreux calculs répétés et permet de réaliser le processus de transformée de Fourier discrète rapide (FFT).

Structure de l'algorithme

Le schéma structurel du calcul de la FFT à 8 points est le suivant.

On peut voir sur la figure que le processus DFT peut être réalisé avec seulement quelques multiplications et additions simples, plutôt qu'avec une multiplication et une accumulation fastidieuses pour chaque élément de données.

Caractéristiques importantes

(1) Notion d'étage

Chaque division est appelée un étage de calcul.

Soient N le nombre de points de calcul de la FFT et M le nombre total d'étages ; ils vérifient :

Chaque étage est identifié par m = 0, 1, 2, ..., M-1.

Pour faciliter le calcul par découpage, le nombre de points FFT N est souvent une puissance entière de 2.

(2) Unité papillon

La structure de calcul FFT se compose de plusieurs unités d'opération papillon. Le schéma de chaque unité d'opération est le suivant :

L'entrée et la sortie de l'unité papillon vérifient :

où,

Chaque unité papillon effectue une multiplication et deux additions pendant son fonctionnement.

Chaque étage comporte N/2 unités papillon.

Par conséquent, les nombres de multiplications et d'additions nécessaires pour effectuer une FFT sont respectivement :

(3) Concept de groupe

Les N/2 unités papillon de chaque étage peuvent être divisées en plusieurs groupes, et chaque groupe a la même structure etla même distribution des facteurs de rotation.

Par exemple, lorsque m=0, il peut être divisé en N/2=4 groupes.

Lorsque m=1, il peut être divisé en N/4=2 groupes.

Lorsque m=M-1, il ne peut être divisé qu'en 1 groupe.

(4) Répartition des facteurs de rotationLe facteur de rotation existe à l'étape m, où。

Dans la deuxième étape de la FFT à 8 points, c'est-à-dire m=1, le facteur de rotation de l'opération papillon peut être simplifié en :

(5) Inversion des bits

Pour un calcul de FFT à N=8 points, les codes binaires correspondant aux positions X(0) ~ X(7) sont :

X(000), X(001), X(010), X(011), X(100), X(101), X(110), X(111)

Inversez les codes binaires de leurs positions :

X(000), X(100), X(010), X(110), X(001), X(101), X(011), X(111)

Les valeurs décimales correspondant aux positions à ce moment-là sont :

X(0), X(4), X(2), X(6), X(1), X(5), X(3), X(7)

Cela correspond exactement à l'ordre des données d'entrée pour la première étape de la FFT.

Cette caractéristique est bénéfique pour l'implémentation de programmation de la FFT.

Conception de la FFT

Description de la conception

Afin d'illustrer simplement le processus de transformation FFT par simulation, le nombre de points de données est fixé à une petite valeur de 8.

Si les données sont entrées en série, elles doivent d'abord être mises en mémoire tampon, c'est pourquoi la méthode d'entrée des données dans cette conception est parallèle.

L'entrée des données est divisée en deux parties : partie réelle et partie imaginaire, donc les résultats de calcul sont également divisés en partie réelle et partie imaginaire.

La conception adopte une structure pipeline et ne prend pas en compte la consommation de ressources pour l'instant.

Pour rendre la structure de conception plus simple, un compromis est fait ici : le calcul de multiplication utilise directement l'opérateur de multiplication. Si la conception FFT est appliquée en pratique, la structure de multiplication doit être remplacée par un multiplieur pipeline, ou utiliser l'IP officielle de multiplieur haute efficacité.

Conception de l'unité papillon

L'unité papillon utilise des opérations en virgule fixe, donc le facteur twiddle doit être quantifié en virgule fixe.

Utilisez MATLAB pour multiplier le facteur twiddle par 8192 (décalage à gauche de 13 bits) ; voir l'annexe.

Pour éviter que la multiplication et l'addition dans les opérations papillon n'augmentent la largeur de bits étage par étage, après chaque étage d'opération, les données de sortie doivent être tronquées à une largeur de bits fixe. Cela supprime également l'effet de la mise à l'échelle du facteur twiddle. Le code est le suivant :

Exemple

`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) multiplier et Xm(p) retarder
    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;
            //développement 8192 fois en tant que Wnr
            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) obtenir les résultats multipliés de Xm(q) et retarder à nouveau Xm(p)
    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;
            // Définir la marge de largeur de bits à l'avance pour éviter un débordement de données
            xq_wnr_real    <= xq_wnr_real0 - xq_wnr_real1 ;
            xq_wnr_imag    <= xq_wnr_imag0 + xq_wnr_imag1 ;
      end
    end

   //======================================================//
   //(2.0) résultats butter
    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) supprimer les 13bits de poids faible en raison de Wnr
    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

Instanciation de niveau supérieur

D'après le schéma de structure de l'algorithme FFT, instanciez les unités papillon pour compléter la fonction FFT finale.

Vous pouvez instancier manuellement 12 fois en séquence selon la correspondance entrée-sortie des unités papillon dans chaque étage, ou utiliser generate pour l'instanciation. Dans ce cas, vous devez très bien connaître les caractéristiques des "groupes" et des "étages" dans la FFT :

  • (1) Une conception FFT à 8 points nécessite 3 étages de fonctionnement. Chaque étage comporte 4 unités papillon, et le nombre de groupes dans chaque étage est respectivement 4, 2, 1.

  • (2) Dans chaque étage, la distance entre les deux ports d'entrée d'une unité papillon au sein d'un groupe est toujours(m est l'indice d'étage, correspondant à l'opération de décalage à gauche 1<<m) ; la distance entre les premiers ports d'entrée des deux unités papillon d'un groupe est 1.

  • (3) La distance entre les premiers ports d'entrée des premières unités papillon de groupes adjacents dans chaque étage est(correspondant à l'opération de décalage à gauche 2<<m).

Le code d'instanciation est le suivant.

Ici, les adresses unidimensionnelles et bidimensionnelles des signaux matriciels xm_real (xm_imag) sont des identifiants représentant l'étage et le groupe.

Lors de la détermination des relations de connexion entre les ports de signal, une logique de jugement apparemment complexe est utilisée, et elle contient également des opérateurs de multiplication. En fait, le circuit final généré est exactement le même que celui obtenu en écrivant manuellement du code pour instancier 12 unités papillon. Cela vient du fait que les variables du bloc generate ne font qu'aider à générer le circuit réel, et le calcul et le jugement des valeurs associées sont effectués au moment de la compilation. Ces variables ne génèrent certainement pas de circuits réels ; elles fournissent seulement une méthode pour une instanciation plus rapide des modules.

Exemple

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,
    entrée signé [23:0]      x7_imag,

    output                   valid,
    sortie signé [23:0]     y0_real,
    sortie signé [23:0]     y0_imag,
    sortie signé [23:0]     y1_real,
    sortie signé [23:0]     y1_imag,
    sortie signé [23:0]     y2_real,
    sortie signé [23:0]     y2_imag,
    sortie signé [23:0]     y3_real,
    sortie signé [23:0]     y3_imag,
    sortie signé [23:0]     y4_real,
    sortie signé [23:0]     y4_imag,
    sortie signé [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
    );

    //données de fonctionnement
    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;

    //facteur, multiplié par 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

    // Initialisation de l'entrée ; liée à l'inversion de bits
    assign xm_real[0][0] = x0_real;
    assign xm_real[0][1] = x4_real;
    assign xm_real[0][2] = x2_real;
    assign xm_real[0][3] = x6_real;
    assign xm_real[0][4] = x1_real;
    assign xm_real[0][5] = x5_real;
    assign xm_real[0][6] = x3_real;
    assign xm_real[0][7] = x7_real;
    assign xm_imag[0][0] = x0_imag;
    assign xm_imag[0][1] = x4_imag;
    assign xm_imag[0][2] = x2_imag;
    assign xm_imag[0][3] = x6_imag;
    assign xm_imag[0][4] = x1_imag;
    assign xm_imag[0][5] = x5_imag;
    assign xm_imag[0][6] = x3_imag;
    assign xm_imag[0][7] = x7_imag;

    //instanciation de butter
    //integer index[11:0] ;
    genvar               m, k;
    generate
    //3 étages
    for(m=0; m<=2; m=m+1) begin: étage
        for (k=0; k<=3; k=k+1) begin: unité

            butterfly u_butter(
               .clk        (clk                 ) ,
               .rstn       (rstn                ) ,
               .en         (en_connect[m*4 + k] ) ,
                       // Est-ce dans le groupe ? index de groupe + index intra-groupe : index du groupe suivant + nouvel index intra-groupe
               .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) ]),                 // Augmenter la distance entre les deux ports d'entrée de l'unité papillon
               .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) ]),

               //données de sortie
               .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

Le banc de test est écrit comme suit, principalement pour l'entrée continue de 16 canaux de données réelles et complexes. Comme chaque FFT ne comporte que 8 points de données, les données d'entrée sont arbitraires, et non des données régulières telles que des ondes sinusoïdales.

Exemple

`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));

    //entrée de données
    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

   //fin de simulation
   initial #1000       $finish ;
endmodule

Résultats de simulation

On peut approximativement voir que les résultats de la FFT peuvent être produits de manière pipeline.

En utilisant la fonction FFT intégrée de MATLAB pour traiter les mêmes données, les résultats de la FFT des 2 premiers groupes de données sont les suivants.

On peut voir que, lorsque le premier signal de données d'entrée ne comporte que la partie réelle valide, les résultats de la FFT sont exactement les mêmes.

Cependant, lorsque la deuxième donnée d'entrée comporte également un signal dans la partie imaginaire, les résultats entre les deux commencent à présenter des erreurs, et parfois les erreurs sont assez importantes.

En utilisant MATLAB pour simuler le processus FFT implémenté en Verilog, on constate que les résultats FFT de ce processus sont globalement cohérents avec les résultats FFT implémentés en Verilog.

Prenez les valeurs absolues des deux résultats FFT erronés pour les comparer, comme le montre la figure ci-dessous.

On peut voir que les tendances des résultats FFT sont à peu près les mêmes, mais qu'il y a des erreurs visibles sur certains points.

Résumé de la conception :

Comme mentionné dans la conception de l'unité papillon, lors de la quantification du facteur de rotation, le choix de la largeur de bits introduit des erreurs.

De plus, le résultat d'opération de chaque unité papillon est tronqué, ce qui introduit également des erreurs.

MATLAB n'a pas besoin de tenir compte des problèmes de précision lors du calcul de la FFT ; il effectue les calculs de FFT sur les données avec sa plus haute précision.

Tout ce qui précède conduira à des différences entre les résultats des deux méthodes de calcul de FFT.

Les lecteurs intéressés peuvent augmenter davantage les largeurs de bits du facteur de rotation et des données d'entrée, et peuvent également augmenter le nombre de points de FFT, puis effectuer une comparaison par simulation ; l'erreur relative devrait diminuer.

Annexe : Utilisation de MATLAB

Générer les facteurs de rotation

Une FFT à 8 points ne nécessite que 4 facteurs de rotation. Les facteurs de rotation sont mis à l'échelle par 8192.

Exemple

clear all;close all;clc;
%=======================================================
% Calcul de Wnr
%=======================================================
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 ; %Complément à deux des nombres négatifs
    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)   %Partie réelle
    Wnr(2*r+2,:)  =  dec2hex(Wnr_imag)   %Partie imaginaire
end

Comparaison des résultats FFT

La simulation MATLAB du processus FFT implémenté en Verilog est la suivante, et elle inclut également une comparaison des deux résultats FFT.

Exemple

clear all;close all;clc;
%=======================================================
% FFT à 8 points
%=======================================================
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];
Pas    = [1+2j, 1+5j, 31+3j, 1+6j, 23+4j, 1+8j, 6+11j, 1+7j];
x2      = x + Pas;
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')

Téléchargement du code source

Téléchargement