[Sefo 0]

Необходимо реализовать преобразователь на 1152, 1024, 704 и 448 отсчетов, при этом длина должна выбираться динамически. Возможно ли сделать такой универсальный преобразователь или лучше сделать четыре отдельных с фиксированной длиной?

 

Можно сделать универсальный. Наличие разнородных бабочек, безусловно, усложняет реализацию, но структура вычислений остается постоянной. Рекомендую посмотреть книжку Л. Рабинер и Б. Гоулд "Теория и применение цифровой обработки сигналов". На странице 418 есть пример 30-ти точечного БПФ, состоящего из 5-ти, 3-х и 2-х точечных бабочек. Сравнив структуру с 32-х точечны БПФ на стр. 420 или 64-х точечного БПФ на стр. 646 Вы увидите, насколько все одинаково по структуре. Поэтому я бы реализовывал универсальный преобразователь.

 

В архиве единственная непустая папка RTL, где хранятся vhdl-файлы описания компонентов бабочки, памяти и файл констант FFT_Package.

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

 

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

x_sig(0).re <= (1 downto 0 => x(0).re(b_size-1)) & x(0).re;
x_sig(0).im <= (1 downto 0 => x(0).im(b_size-1)) & x(0).im;
x_sig(1).re <= (1 downto 0 => x(1).re(b_size-1)) & x(1).re;
x_sig(1).im <= (1 downto 0 => x(1).im(b_size-1)) & x(1).im;
x_sig(2).re <= (1 downto 0 => x(2).re(b_size-1)) & x(2).re;
x_sig(2).im <= (1 downto 0 => x(2).im(b_size-1)) & x(2).im;
x_sig(3).re <= (1 downto 0 => x(3).re(b_size-1)) & x(3).re;
x_sig(3).im <= (1 downto 0 => x(3).im(b_size-1)) & x(3).im;

 

я предпочитаю не полениться и написать пару функций чтобы не засорять код:

 

D := expand_sign(D_i);

 

Функции не сложные, но зато универсальные - не зависят от разрядности и размерности complex_data_bus. Захотите, например, 8-ми точечную бабочку и придется еще 8 строк добавлять чтобы знаком расширить, а с функциями вспомогательные выражения (да и сами функции) редактировать не придется - только основной код нужно будет поменять.

 

Получается более читаемый код, особенно для тех кто его не писал. Читающий первый раз имеет возможность не вдаваться во второстепенные подробности. Выражение D := expand_sign(D_i) понятно и без комментариев. Если назначение функции не совсем ясно, то можно ограничится чтением комментариев к ней не вдаваясь в подробности реализации.

 

Что касается пустоты папок, так я только начал их наполнять. За столь медленный темп извиняюсь, но быстрее, пока никак не получается. Сначала я доработаю код, затем начнем наполнять папку Modelsim.

[ZED 0]

Наличие разнородных бабочек, безусловно, усложняет реализацию, но структура вычислений остается постоянной.

Вычисление 30-ти точечного БПФ, состоящего из 5-ти, 3-х и 2-х точечных бабочек отличается от вычисления 32-х точечного БПФ. По всей видимости для каждого из БПФ (на 1152, 1024, 704 и 448 отсчетов) придется писать свою управляшку, и подключать ее в зависимости от размерности БПФ, а это не очень удобно мне кажется. Ну и подключение бабочек разной размерности.

[Sefo 0]

Вычисление 30-ти точечного БПФ, состоящего из 5-ти, 3-х и 2-х точечных бабочек отличается от вычисления 32-х точечного БПФ.

 

Но структура и принцип "соединения" бабочек остается одинаковым.

 

По всей видимости для каждого из БПФ (на 1152, 1024, 704 и 448 отсчетов) придется писать свою управляшку, и подключать ее в зависимости от размерности БПФ, а это не очень удобно мне кажется.

 

Бабочки все равно придется делать всех типов - от этого не уйти.

 

Но вот с универсальным управлением как раз особых проблем быть не должно - просто когда появляется 3-х точечная бабочка, то пропадает кратность степеням двойки и вычисления в блоке управления придется делать "честным" образом.

 

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

 

 

[Jhonny 0]

Спасибо за ответы:).

То, что принцип соединения бабочек одинаков, интуитивно понятно. Вызывает затруднение количество разнородных бабочек. Для чисел 1152, 1024, 704, 448 я выделил 2-х, 3-х, 4-х, 7-ми и 11-ти точечные бабочки.

 

Но вот с универсальным управлением как раз особых проблем быть не должно - просто когда появляется 3-х точечная бабочка, то пропадает кратность степеням двойки и вычисления в блоке управления придется делать "честным" образом.

Это значит, обходиться без хитрых сдвигов и маскирований?

 

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

 

Насколько общим должен быть вид? Ведь от конкретного числа точек зависят количество этапов и применяемые бабочки?

 

И еще, все сказанное Вами относится к БПФ типа пинг-понг (разрабатываемого в этой теме)? У Рабинера, Гоулда написано про поточный метод, мне показалось, там проще организация памяти.

 

[Sefo 0]

Спасибо за ответы:).

То, что принцип соединения бабочек одинаков, интуитивно понятно. Вызывает затруднение количество разнородных бабочек. Для чисел 1152, 1024, 704, 448 я выделил 2-х, 3-х, 4-х, 7-ми и 11-ти точечные бабочки.

 

Я бы 2-х точечную бабочку из списка исключил бы - она неэффективная. Лучше 5-ти точечную добавить - при наличии 7-ми и 11-ти точечных она уже погоды не сделает.

 

И еще, все сказанное Вами относится к БПФ типа пинг-понг (разрабатываемого в этой теме)? У Рабинера, Гоулда написано про поточный метод, мне показалось, там проще организация памяти.

 

Все сказанное относится к подавляющему большинству реализаций БПФ.

 

Поточный метод у Рабинера и Гоулда не для современного железа - сильно устаревший и по ресурсам жутко неэффективный. К тому же легко реализуем только если на всех этапах одинаковые бабочки (ну или хотя бы с кратным числом точек). В общем, решите реализовать поточный метод - ищите современные примеры.

 

Это значит, обходиться без хитрых сдвигов и маскирований?

 

Угу.

 

Насколько общим должен быть вид? Ведь от конкретного числа точек зависят количество этапов и применяемые бабочки?

Что касается памяти, то все зависит от того как вы собираетесь реализовать БПФ. От самого по себе числа точек и количества этапов ничего не зависит. Вопрос лишь в том, какие бабочки на этом этапе и какие на следующем. Если они одинаковые или кратные (2 и 4, например), то все просто. Если бабочка будет получать точки на вход по очереди, то проблем нет никаких, но крайне медленно. Если подавать все точки сразу, что весьма эффективно, то надо память разбивать на банки и писать/читать туда/оттуда так, чтобы для каждой бабочки все точки находились в разных банках. А это уже не так просто в вашем случае.

 

 

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

[Sefo 0]

Вот "причесанный" код нашего БПФ (\RTL). Так же прилагается Квартусовский проект. Проект пока формальный – т.е. он компилируется, но это еще ничего не значит, кроме отсутствия синтаксических ошибок. В качестве микросхемы стоит Cyclone III, что не принципиально. Для компиляции один файл (\Quartus\FPGA_RTL\Coef_Memory_Bank.vhd) требует поддержки VHDL-2008 т.к использует unconstrained array of string. При отсутствии соответствующей версии Квартуса можно воспользоваться несколько кривоватым приемом подходящим для более ранних стандартов VHDL, описанным в комментариях (код так же приведен). Файлы \Quartus\FPGA_RTL\ROM_*.mif для инициализации ROM коэффициентов взяты из проекта ZED и содержат просто sin и cos, что неправильно.

 

Следующим этапом – моделирование и исправление багов. Пока я готовлю соответствующие файлы просьба ZEDу сгенерировать mif-файлы с правильным набором коэффициентов.

 

FFT_Project.rar

[ZED 0]

Вот коэффициенты ROM_x.mif плюс файл Matlab для их генерации. Надеюсь ничего не напутал.

FFT_Coefficients.rar

[Sefo 0]

Вот коэффициенты ROM_x.mif плюс файл Matlab для их генерации. Надеюсь ничего не напутал.

 

Увы :) напутали. Придется Вам пролистать эту тему и найти то место, где обсуждалось как правильно рассчитать коэффициенты. Вкратце проблема следующая:

 

В арифметике с фиксированной точкой Вы берете за 1 некое число Х. Если нужно посчитать чему равно 0.3 от некоего числа D, то делаем так

1) предвычисляем целочисленный коэффициент Y = round(0.3 * X), соответствующий 0.3.

2) R = Y * D

3) Q = R / X

 

Если X выбран так, что не является степенью 2, то на шаге 3 нужно выполнять честное деление, а если X = 2^n, то Q = R >> n.

 

В умножителях на поворачивающие коэффициенты у нас нет деления - у нас сдвиг.

 

Так что вспоминайте как мы собирались вычислять коэффициенты.

[ZED 0]

А ну да, коэффициенты у нас лежат в диапазоне от -1024 до 1024.

FFT_Coefficients.rar

[Jhonny 0]

Попытался оптимизировать бабочку, убрав повторяющиеся операции. Вот что получилось:

 

architecture RTL of Butterfly is
    
    signal D : complex_data_p2_bus;

    signal add01_re : std_logic_vector(fft_data'high + 2 downto 0);
    signal add01_im : std_logic_vector(fft_data'high + 2 downto 0);
    signal add23_re : std_logic_vector(fft_data'high + 2 downto 0);
    signal add23_im : std_logic_vector(fft_data'high + 2 downto 0);

    signal sub01_re : std_logic_vector(fft_data'high + 2 downto 0);
    signal sub01_im : std_logic_vector(fft_data'high + 2 downto 0);
    signal sub23_re : std_logic_vector(fft_data'high + 2 downto 0);
    signal sub23_im : std_logic_vector(fft_data'high + 2 downto 0);

    signal sub01    : std_logic_vector(fft_data'high + 2 downto 0);
    signal sub02    : std_logic_vector(fft_data'high + 2 downto 0);
    signal sub13    : std_logic_vector(fft_data'high + 2 downto 0);

begin

    D <= expand_sign(D_i);

    add01_re <= D(0).re + D(1).re + 1;
    add01_im <= D(0).im + D(1).im + 1;

    sub01_re <= D(0).re - D(1).re + 1;
    sub01_im <= D(0).im - D(1).im + 1;

    add23_re <= D(2).re + D(3).re + 1;
    add23_im <= D(2).im + D(3).im + 1;

    sub23_re <= D(2).re - D(3).re + 1;
    sub23_im <= D(2).im - D(3).im + 1;

    sub01    <= D(0).re - D(1).im;
    sub02    <= D(0).im - D(2).im;
    sub13    <= D(1).re - D(3).re;
                
    process (CLK)    
    variable Y: complex_data_p2_bus;
    begin 
             
        if rising_edge(CLK) then
            if RESETsn = '0' then                
                Y_ro <= (others => (re => (others => '0'), im => (others => '0')));
            else    
                if (MODE_i = Butterfly_4_Point) then
                    Y(0).re := add01_re + add23_re;
                    Y(0).im := add01_im + add23_im;

                    Y(1).re := sub01 - D(2).re - D(3).im + 2;
                    Y(1).im := sub02 - sub13 + 2;                                    
              
                    Y(2).re := sub01_re + sub23_re;
                    Y(2).im := sub01_im + sub23_im;

                    Y(3).re := sub01 - D(2).re + D(3).im + 2;
                    Y(3).im := sub02 + sub13 + 2;                                  
                              
                    Y_ro <= get_msb(Y, 0);
                else
                    Y(0).re := add01_re;
                    Y(0).im := add01_im;
              
                    Y(1).re := sub01_re;
                    Y(1).im := sub01_im;
                    
                    Y(2).re := add23_re;
                    Y(2).im := add23_im;
              
                    Y(3).re := sub23_re;
                    Y(3).im := sub23_im;
              
                    Y_ro <= get_msb(Y, 1);
                end if;                            
            end if;
        end if;
    
    end process;
end RTL;

 

Синтезировал в Xilinx ISE 12.3, до этого было

18-bit adder : 6

18-bit subtractor : 2

19-bit adder : 19

19-bit subtractor :11

После стало так 19-bit adder : 18, 19-bit subtractor :10.

 

Имеет ли право на жизнь такая реализация, или есть другие варианты оптимизации?

 

[chirik8807 0]

Добрый день!

Я разбираюсь с БПФ и не могу понять, как на практике вычисляются поворачивающий множитель W ?, в книжках написано W= e^(-j*2*p*n*k/N), k- номер отсчета, N- длина последовательности, n- текущий номер, толи я не те книжки читаю(

[ZED 0]

Добрый день!

Я разбираюсь с БПФ и не могу понять, как на практике вычисляются поворачивающий множитель W ?, в книжках написано W= e^(-j*2*p*n*k/N), k- номер отсчета, N- длина последовательности, n- текущий номер, толи я не те книжки читаю(

 

Все правильно. Вы читаете именно те книжки.

[chirik8807 0]

Почитав еще литературы стало яснее, что как правило, коэффициенты вычисляются заранее и хранятся в ОЗУ, или их можно через синусы посчитать W= cos(2*p*k/N) - j*sin(2*p*k/N).

[Костян 0]

Почему для W используется разрядность всего 12 бит , тогда как данные 17 ?

Из каких соображений разрядность W взята меньше, чем входных данных ?

[almost 0]

Почему для W используется разрядность всего 12 бит , тогда как данные 17 ?

Из каких соображений разрядность W взята меньше, чем входных данных ?

 

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