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 et
la 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 rotation
Le 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
/**************** 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
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
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
%=======================================================
% 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
%=======================================================
% 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