FFT (Fast Fourier Transform), Transformada Rápida de Fourier, es un algoritmo eficiente de la DFT (Transformada Discreta de Fourier). Tiene un papel insustituible en los métodos de procesamiento digital basados en el análisis de transformaciones tiempo-frecuencia.

Principio de FFT

Derivación de la fórmula

La fórmula de cálculo de la DFT es:

donde,

Al dividir la fórmula de la transformada discreta de Fourier en términos pares e impares, los primeros N/2 puntos se pueden expresar como:

De manera similar, los últimos N/2 puntos se pueden expresar como:

Por lo tanto, los valores de los últimos N/2 puntos pueden determinarse completamente a través de los valores intermedios calculados para los primeros N/2 puntos. Se continúa descomponiendo A[k] y B[k] en partes pares e impares hasta convertirlos en una DFT de 2 puntos, evitando así muchos cálculos repetidos y logrando el proceso de la Transformada Rápida de Fourier (FFT).

Estructura del algoritmo

El diagrama de estructura del cálculo de FFT de 8 puntos es el siguiente.

Como se ve en la figura, solo se necesitan unas pocas multiplicaciones y sumas simples para completar el proceso de DFT, en lugar de realizar tediosas multiplicaciones y acumulaciones para cada dato.

Características importantes

(1) Concepto de etapa

Cada división se denomina una etapa de operación.

Supongamos que el número de puntos de la operación FFT es N, y hay M etapas de operación, entonces cumplen:

Cada etapa de operación se identifica como m = 0, 1, 2, ..., M-1.

Para facilitar el cálculo por divisiones, el valor de N en FFT suele ser una potencia entera de 2.

(2) Unidad de mariposa

La estructura de cálculo FFT está compuesta por varias unidades de operación de mariposa. El diagrama de cada unidad de operación es el siguiente:

La entrada y salida de la unidad de mariposa satisfacen:

donde,

Cada unidad de mariposa realiza una multiplicación y dos sumas en su operación.

En cada etapa, hay N/2 unidades de mariposa.

Por lo tanto, el número de multiplicaciones y sumas necesarias para completar una FFT son respectivamente:

(3) Concepto de grupo

Las N/2 unidades de mariposa de cada etapa se pueden dividir en varios grupos, cada grupo tiene la misma estructura ydistribución de factores.

Por ejemplo, cuando m=0, se puede dividir en N/2=4 grupos.

Cuando m=1, se puede dividir en N/4=2 grupos.

Cuando m=M-1, solo se puede dividir en 1 grupo.

(4) Distribución de factoresEl factor existe en la etapa m, donde。

En la segunda etapa de la FFT de 8 puntos, es decir, m=1, los factores de operación de mariposa se pueden simplificar como:

(5) Inversión de bits

Para el cálculo de FFT de N=8 puntos, los códigos binarios correspondientes a las posiciones X(0) ~ X(7) son:

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

Invierta los códigos binarios de sus posiciones:

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

El decimal correspondiente a las posiciones en este momento es:

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

Corresponde exactamente al orden de los datos de entrada de la primera etapa de la FFT.

Esta característica es útil para la implementación de la FFT en programación.

Diseño de FFT

Descripción del diseño

Para explicar el proceso de transformación de la FFT mediante simulación de manera sencilla, se toma un valor pequeño de 8 puntos de datos.

Si los datos se ingresan en serie, primero se requiere almacenarlos en búfer, por lo que en el diseño el método de entrada de datos es paralelo.

La entrada de datos se divide en parte real e imaginaria, 2 partes en total, por lo que el resultado del cálculo también se divide en parte real e imaginaria.

El diseño adopta una estructura de pipeline y por el momento no se considera el consumo de recursos.

Para simplificar la estructura del diseño, aquí se hace una concesión: la multiplicación se realiza directamente con el signo de multiplicar. Si el diseño FFT se aplica en la práctica, es necesario reemplazar la estructura de multiplicación por un multiplicador con pipeline, o utilizar un IP de multiplicador de alta eficiencia proporcionado oficialmente.

Diseño de la unidad de mariposa

La unidad de mariposa es de operación de punto fijo, por lo que es necesario cuantificar en punto fijo el factor twiddle.

Con la ayuda de MATLAB, el factor twiddle se amplía 8192 veces (desplazamiento a la izquierda de 13 bits); consulte el apéndice.

Para evitar que la multiplicación y la suma en la operación de mariposa aumenten el ancho de bits etapa por etapa, después de completar cada etapa, los datos de salida deben truncarse a un ancho de bits fijo; esto también puede eliminar el efecto del aumento del factor twiddle. El código es el siguiente:

Ejemplo

`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) mutiply and Xm(p) delay
    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;
            //expanding 8192 times as 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) get Xm(q) mutiplied-results and Xm(p) delay again
    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;
            //Establezca el margen de ancho de bits con antelación para evitar el desbordamiento de datos
            xq_wnr_real    <= xq_wnr_real0 - xq_wnr_real1 ;
            xq_wnr_imag    <= xq_wnr_imag0 + xq_wnr_imag1 ;
      end
    end

   //======================================================//
   //(2.0) butter results
    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) discard the low 13bits because of 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

Instanciación de nivel superior

De acuerdo con el diagrama de estructura del algoritmo FFT, instancie las unidades de mariposa para completar la función FFT final.

Se pueden instanciar manualmente 12 veces en orden según la correspondencia de entrada y salida de las unidades de mariposa de cada etapa, o utilizar `generate` para la instanciación; en este caso, es necesario conocer muy bien las características de "grupo" y "etapa" en FFT:

  • (1) El diseño de FFT de 8 puntos requiere 3 etapas de operación, cada etapa tiene 4 unidades de mariposa, y el número de grupos en cada etapa es 4, 2, 1 respectivamente.

  • (2) En cada etapa, la distancia entre los dos puertos de entrada de una unidad de mariposa dentro de un grupo es siempre(m es el índice de la etapa, correspondiente al desplazamiento a la izquierda 1<<m), y la distancia entre los primeros puertos de entrada de dos unidades de mariposa dentro del grupo es 1.

  • (3) La distancia entre los primeros puertos de entrada de la primera unidad de mariposa de grupos adyacentes en cada etapa es(correspondiente al desplazamiento a la izquierda 2<<m).

El código de instanciación es el siguiente.

Entre ellos, las direcciones unidimensional y bidimensional de la señal de matriz xm_real (xm_imag) representan los identificadores de etapa y grupo.

Al determinar la relación de conexión entre los puertos de señal, se utiliza una lógica de decisión aparentemente compleja, e incluso incluye un signo de multiplicación; en realidad, el circuito finalmente generado es exactamente el mismo que el de instanciar manualmente 12 unidades de mariposa en el código. Esto se debe a que las variables en `generate` solo ayudan a generar el circuito real; el cálculo y la determinación de los valores relevantes ya se completan en tiempo de compilación. Estas variables no generan circuitos reales, solo proporcionan un método para una instanciación de módulos más rápida.

Ejemplo

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

    //operating data
    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;

    //factor, multiplied by 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

    //Inicialización de entrada, relacionada con la inversión 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;

    //butter instantiaiton
    //integer              index[11:0] ;
    genvar               m, k;
    generate
    //3 stage
    for(m=0; m<=2; m=m+1) begin: stage
        for (k=0; k<=3; k=k+1) begin: unit

            butterfly           u_butter(
               .clk        (clk                 ) ,
               .rstn       (rstn                ) ,
               .en         (en_connect[m*4 + k] ) ,
                       //¿Está dentro del grupo? Número de grupo + número dentro del grupo : número del siguiente grupo + nuevo número dentro del grupo
               .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) ]),                 //Aumentar la distancia entre los dos puertos de entrada de la unidad de mariposa
               .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) ]),

               //output data
               .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

El testbench se escribe de la siguiente manera; se utiliza principalmente para la entrada continua de 16 canales de datos reales y complejos. Debido a que cada FFT solo tiene 8 puntos de datos, los datos enviados son bastante arbitrarios, no son datos regulares como ondas sinusoidales.

Ejemplo

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

    //data input
    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

   //finish simulation
   initial #1000       $finish ;
endmodule

Resultados de la simulación

Se puede observar aproximadamente que los resultados de la FFT se pueden generar en pipeline.

Se utiliza la función FFT incorporada en MATLAB para operar sobre los mismos datos; los resultados FFT de los primeros 2 grupos de datos son los siguientes.

Se puede ver que cuando la primera señal de datos de entrada solo tiene válida la parte real, los resultados de la FFT son exactamente iguales.

Pero en la segunda entrada, la parte compleja de los datos también tiene señal; en este momento, los resultados entre ambos comienzan a tener errores, a veces bastante grandes.

Al simular en MATLAB el proceso FFT implementado en Verilog, se descubre que el resultado FFT de este proceso es básicamente consistente con el resultado de la FFT implementada en Verilog.

Se comparan los valores absolutos de los dos resultados FFT con errores, como se muestra en la figura.

Se puede ver que la tendencia de los resultados FFT es aproximadamente la misma, pero en algunos puntos hay errores visibles a simple vista.

Resumen del diseño:

Como se mencionó al diseñar la unidad de mariposa, al cuantificar el factor twiddle, la elección del ancho de bits introduce errores.

Además, el resultado de cada unidad de mariposa se trunca, lo que también introduce errores.

MATLAB no necesita considerar el problema de precisión al calcular la FFT; realiza el cálculo FFT de los datos con su máxima precisión.

Todo lo anterior conduce a diferencias en los resultados entre los dos métodos de cálculo FFT.

Los interesados pueden aumentar el factor twiddle y el ancho de bits de los datos de entrada, y también pueden aumentar el número de puntos FFT; luego, al comparar mediante simulación, el error relativo debería disminuir.

Apéndice: uso de MATLAB

Generación del factor twiddle

La FFT de 8 puntos solo necesita 4 factores twiddle. El factor twiddle se amplifica 8192 veces.

Ejemplo

clear all;close all;clc;
%=======================================================
% Wnr calcuting
%=======================================================
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 ; %Complemento a dos de números negativos
    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)   %Parte real
    Wnr(2*r+2,:)  =  dec2hex(Wnr_imag)   %Parte imaginaria
end

Comparación de resultados FFT

El proceso de simulación en MATLAB de la FFT implementada en Verilog es el siguiente; también incluye la comparación de los dos tipos de resultados FFT.

Ejemplo

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];
step    = [1+2j, 1+5j, 31+3j, 1+6j, 23+4j, 1+8j, 6+11j, 1+7j];
x2      = x + step;
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')

Descarga del código fuente

Download