FFT (Fast Fourier Transform), также известное как быстрое преобразование Фурье, — это эффективный алгоритм для DFT (Discrete Fourier Transform). Этот алгоритм играет незаменимую роль в методах цифровой обработки, основанных на анализе с помощью частотно-временного преобразования.

Принцип FFT

Вывод формулы

Формула вычисления DFT:

где,

Разделив формулу дискретного преобразования Фурье на нечётные и чётные члены, первые N/2 точек можно выразить как:

Аналогично, последние N/2 точек можно выразить как:

Видно, что значения последних N/2 точек могут быть полностью определены промежуточными значениями, полученными при вычислении первых N/2 точек. Продолжайте выполнять чётно-нечётное разложение A[k] и B[k], пока оно не станет 2-точечным DFT, что позволяет избежать множества повторных вычислений и реализует процесс быстрого дискретного преобразования Фурье (FFT).

Структура алгоритма

Структурная схема вычисления 8-точечного FFT выглядит следующим образом.

Из рисунка видно, что процесс DFT можно выполнить всего лишь с помощью нескольких простых умножений и сложений, а не утомительного умножения и накопления для каждого элемента данных.

Важные характеристики

(1) Понятие этапа

Каждое разбиение называется одним этапом вычислений.

Пусть число точек вычисления FFT равно N, а общее число этапов равно M; они удовлетворяют:

Каждый этап обозначается m = 0, 1, 2, ..., M-1.

Для удобства разбиения вычислений число точек БПФ N часто выбирают равным целой степени 2.

(2) Блок «бабочка»

Структура вычисления БПФ состоит из нескольких блоков операции «бабочка». Принципиальная схема каждого блока операции выглядит следующим образом:

Вход и выход блока «бабочка» удовлетворяют:

где,

Каждый блок «бабочка» при работе выполняет одно умножение и два сложения.

На каждой ступени имеется N/2 блоков «бабочка».

Следовательно, число умножений и сложений, необходимых для выполнения одного БПФ, соответственно равно:

(3) Понятие группы

N/2 блоков «бабочка» на каждой ступени можно разделить на несколько групп, причём каждая группа имеет одинаковую структуру ираспределение поворотных коэффициентов.

Например, при m=0 их можно разделить на N/2=4 группы.

При m=1 их можно разделить на N/4=2 группы.

Когда m=M-1, его можно разделить только на 1 группу.

(4) Распределение поворотных коэффициентовПоворотный коэффициент присутствует на этапе m, где。

На второй ступени 8-точечного БПФ, т. е. при m=1, поворотный коэффициент операции «бабочка» можно упростить до:

(5) Реверсирование битов

Для вычисления N=8-точечного БПФ двоичные коды, соответствующие позициям X(0) ~ X(7), имеют вид:

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

Реверсируйте двоичные коды их позиций:

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

Десятичные значения, соответствующие позициям в этот момент, следующие:

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

Это в точности соответствует порядку входных данных для первой ступени БПФ.

Эта особенность полезна для программной реализации БПФ.

Проектирование БПФ

Описание проекта

Чтобы просто проиллюстрировать процесс преобразования БПФ с помощью моделирования, количество точек данных установлено равным небольшому значению 8.

Если данные вводятся последовательно, их сначала нужно буферизовать, поэтому в данном проекте используется параллельный способ ввода данных.

Входные данные разделены на две части: действительную и мнимую, поэтому результаты вычислений также разделены на действительную и мнимую части.

В проекте используется конвейерная структура, и потребление ресурсов пока не учитывается.

Чтобы упростить структуру проекта, здесь сделан компромисс: в операции умножения напрямую используется оператор умножения. Если проект БПФ применяется на практике, структуру умножения необходимо заменить на конвейерный умножитель или использовать официальный высокоэффективный IP-умножитель.

Проектирование блока бабочки

Блок бабочки использует операции с фиксированной запятой, поэтому поворотный коэффициент необходимо квантовать в формат с фиксированной запятой.

Умножьте поворотный коэффициент на 8192 в MATLAB (сдвиг влево на 13 бит); см. приложение.

Чтобы умножение и сложение в операциях бабочки не увеличивали разрядность от каскада к каскаду, после каждого каскада вычислений выходные данные необходимо усечь до фиксированной разрядности. Это также устраняет влияние масштабирования поворотного коэффициента. Код выглядит следующим образом:

Пример

`timescale 1ns/100ps
/**************** блок бабочки *************************
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) умножение и Xm(p) задержка
    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 раза как 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) получить результаты умножения Xm(q) и снова задержать 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;
            // Заранее задайте запас по разрядности, чтобы предотвратить переполнение данных
            xq_wnr_real    <= xq_wnr_real0 - xq_wnr_real1 ;
            xq_wnr_imag    <= xq_wnr_imag0 + xq_wnr_imag1 ;
      end
    end

   //======================================================//
   //(2.0) результаты 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) отбросить младшие 13 бит из-за 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

Инстанцирование верхнего уровня

В соответствии со структурной схемой алгоритма БПФ создайте экземпляры блоков-бабочек, чтобы реализовать окончательную функцию БПФ.

Вы можете вручную создать 12 экземпляров последовательно в соответствии с соответствием входов и выходов блоков-бабочек на каждом этапе либо использовать generate для создания экземпляров. В этом случае вам нужно хорошо разбираться в особенностях «групп» и «этапов» в БПФ:

  • (1) Проект 8-точечного БПФ требует 3 этапов вычислений. На каждом этапе имеется 4 блока-бабочки, а количество групп на каждом этапе составляет соответственно 4, 2 и 1.

  • (2) На каждой ступени расстояние между двумя входными портами блока бабочки внутри группы всегда(m — индекс ступени, соответствующий операции сдвига влево 1<<m); расстояние между первыми входными портами двух блоков бабочки в группе равно 1.

  • (3) Расстояние между первыми входными портами первых блоков бабочки соседних групп на каждой ступени равно(соответствует операции сдвига влево 2<<m).

Код инстанцирования выглядит следующим образом.

Здесь одномерные и двумерные адреса матричных сигналов xm_real (xm_imag) — это идентификаторы, представляющие ступень и группу.

При определении связей между сигнальными портами используется кажущаяся сложной логика проверки, и она также содержит операторы умножения. Фактически итоговая сгенерированная схема в точности совпадает с написанным вручную кодом для инстанцирования 12 блоков бабочки. Это объясняется тем, что переменные в блоке generate лишь помогают генерировать реальную схему, а вычисление и проверка соответствующих значений выполняются во время компиляции. Эти переменные, конечно, не создают реальных схем; они лишь предоставляют способ более быстрого инстанцирования модулей.

Пример

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,
    вход знаковый [23:0]      x7_imag,

    output                   valid,
    выход знаковый [23:0]     y0_real,
    выход знаковый [23:0]     y0_imag,
    выход знаковый [23:0]     y1_real,
    выход знаковый [23:0]     y1_imag,
    выход знаковый [23:0]     y2_real,
    выход знаковый [23:0]     y2_imag,
    выход знаковый [23:0]     y3_real,
    выход знаковый [23:0]     y3_imag,
    выход знаковый [23:0]     y4_real,
    выход знаковый [23:0]     y4_imag,
    выход знаковый [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
    );

    //рабочие данные
    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;

    //коэффициент, умноженный на 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

    // Инициализация входных данных; связана с обратным порядком битов
    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
    //integer              index[11:0] ;
    genvar               m, k;
    generate
    //3 ступени
    for(m=0; m<=2; m=m+1) begin: stage
        for (k=0; k<=3; k=k+1) begin: единица

            butterfly u_butter(
               .clk        (clk                 ) ,
               .rstn       (rstn                ) ,
               .en         (en_connect[m*4 + k] ) ,
                       // Находится ли внутри группы? индекс группы + внутригрупповой индекс : индекс следующей группы + новый внутригрупповой индекс
               .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) ]),                 // Увеличить расстояние между двумя входными портами блока butterfly
               .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) ]),

               //выходные данные
               .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] ;
    присвоить     y1_real = xm_real[3][1] ;
    присвоить     y1_imag = xm_imag[3][1] ;
    присвоить     y2_real = xm_real[3][2] ;
    присвоить     y2_imag = xm_imag[3][2] ;
    присвоить     y3_real = xm_real[3][3] ;
    присвоить     y3_imag = xm_imag[3][3] ;
    присвоить     y4_real = xm_real[3][4] ;
    присвоить     y4_imag = xm_imag[3][4] ;
    присвоить     y5_real = xm_real[3][5] ;
    присвоить     y5_imag = xm_imag[3][5] ;
    присвоить     y6_real = xm_real[3][6] ;
    присвоить     y6_imag = xm_imag[3][6] ;
    assign     y7_real = xm_real[3][7] ;
    assign     y7_imag = xm_imag[3][7] ;

endmodule

testbench

Тестовый стенд написан следующим образом, в основном для непрерывного ввода 16 каналов вещественных и комплексных данных. Поскольку каждое БПФ имеет только 8 точек данных, входные данные произвольны, а не регулярны, как, например, синусоидальные волны.

Пример

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

    //ввод данных
    initial      begin
        en = 0 ;
        x0_real = 24'd10;
        ⟦⟧x1_real = 24'd20;
        x_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

   //завершить моделирование
   initial #1000       $finish ;
endmodule

Результаты моделирования

Можно приблизительно увидеть, что результаты БПФ могут выводиться конвейерным способом.

Используя встроенную функцию БПФ MATLAB для обработки тех же данных, результаты БПФ первых 2 групп данных выглядят следующим образом.

Видно, что когда у первого входного сигнала данных действительна только вещественная часть, результаты БПФ полностью совпадают.

Однако, когда вторые входные данные также содержат сигнал в мнимой части, в результатах этих двух начинают появляться ошибки, и иногда ошибки довольно велики.

При моделировании в MATLAB процесса БПФ, реализованного на Verilog, обнаружено, что результаты БПФ этого процесса в основном совпадают с результатами БПФ, реализованного на Verilog.

Возьмите абсолютные значения двух ошибочных результатов БПФ для сравнения, как показано на рисунке ниже.

Видно, что тенденции результатов БПФ примерно одинаковы, но в отдельных точках видны ошибки.

Итоги проектирования:

Как упоминалось при проектировании блока «бабочка», при квантовании поворотного множителя выбор разрядности вносит ошибки.

Кроме того, результат операции каждого блока «бабочка» усекается, что также вносит ошибки.

MATLAB не нужно учитывать вопросы точности при вычислении БПФ; он выполняет вычисления БПФ над данными с максимальной точностью.

Всё вышеперечисленное приведёт к различиям между результатами двух методов вычисления БПФ.

Заинтересованные читатели могут дополнительно увеличить разрядность поворотного множителя и входных данных, а также увеличить число точек БПФ, затем выполнить сравнительное моделирование; относительная ошибка должна уменьшиться.

Приложение: использование MATLAB

Генерация поворотных множителей

8-точечное БПФ требует всего 4 поворотных множителя. Поворотные множители масштабируются с коэффициентом 8192.

Пример

clear all;close all;clc;
%=======================================================
% Вычисление Wnr
%=======================================================
for r = 0:3
    Wnr_factor  = cos(pi/4*r) - j*sin(пи/4*r) ;
    Wnr_integer = floor(Wnr_factor * 2^13) ;
   
    if (real(Wnr_integer)<0)
        Wnr_real    = real(Wnr_integer) + 2^16 ; %Дополнительный код отрицательных чисел
    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)   %Действительная часть
    Wnr(2*r+2,:)  =  dec2hex(Wnr_imag)   %Мнимая часть
end

Сравнение результатов БПФ

Моделирование в MATLAB процесса БПФ, реализованного на Verilog, выглядит следующим образом, и оно также включает сравнение двух результатов БПФ.

Пример

clear all;close all;clc;
%=======================================================
% 8-точечное БПФ
%=======================================================
for r=0:3
    Wnr(r+1)  = cos(pi/4*r) - j*sin(пи/4*r) ;
end
x       = [10, 20, 30, 40, 10, 20 ,30 ,40];
шаг    = [1+2j, 1+5j, 31+3j, 1+6j, 23+4j, 1+8j, 6+11j, 1+7j];
x2      = x + шаг;
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')

Скачать исходный код

Скачать