| |
|
  |
 Реализация БПФ на ПЛИС, Тудности, встречаемые при реализации |
|
|
|
|
 Nov 29 2010, 10:50
|
Местный
Группа: Свой
Сообщений: 429
Регистрация: 11-08-05
Из: Санкт-Петербург
Пользователь №: 7 537
|
Цитата(Jhonny. @ Nov 28 2010, 11:44)  Необходимо реализовать преобразователь на 1152, 1024, 704 и 448 отсчетов, при этом длина должна выбираться динамически. Возможно ли сделать такой универсальный преобразователь или лучше сделать четыре отдельных с фиксированной длиной? Можно сделать универсальный. Наличие разнородных бабочек, безусловно, усложняет реализацию, но структура вычислений остается постоянной. Рекомендую посмотреть книжку Л. Рабинер и Б. Гоулд "Теория и применение цифровой обработки сигналов". На странице 418 есть пример 30-ти точечного БПФ, состоящего из 5-ти, 3-х и 2-х точечных бабочек. Сравнив структуру с 32-х точечны БПФ на стр. 420 или 64-х точечного БПФ на стр. 646 Вы увидите, насколько все одинаково по структуре. Поэтому я бы реализовывал универсальный преобразователь. Цитата(ZED @ Nov 11 2010, 16:00) В архиве единственная непустая папка 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.
|
|
|
|
|
|
|
|
Nov 29 2010, 13:42
|
Местный
Группа: Свой
Сообщений: 264
Регистрация: 17-04-07
Из: Москва
Пользователь №: 27 102
|
Цитата Наличие разнородных бабочек, безусловно, усложняет реализацию, но структура вычислений остается постоянной. Вычисление 30-ти точечного БПФ, состоящего из 5-ти, 3-х и 2-х точечных бабочек отличается от вычисления 32-х точечного БПФ. По всей видимости для каждого из БПФ (на 1152, 1024, 704 и 448 отсчетов) придется писать свою управляшку, и подключать ее в зависимости от размерности БПФ, а это не очень удобно мне кажется. Ну и подключение бабочек разной размерности.
|
|
|
|
|
|
|
|
Nov 29 2010, 20:58
|
Местный
Группа: Свой
Сообщений: 429
Регистрация: 11-08-05
Из: Санкт-Петербург
Пользователь №: 7 537
|
Цитата(ZED @ Nov 29 2010, 16:42) Вычисление 30-ти точечного БПФ, состоящего из 5-ти, 3-х и 2-х точечных бабочек отличается от вычисления 32-х точечного БПФ. Но структура и принцип "соединения" бабочек остается одинаковым. Цитата(ZED @ Nov 29 2010, 16:42) По всей видимости для каждого из БПФ (на 1152, 1024, 704 и 448 отсчетов) придется писать свою управляшку, и подключать ее в зависимости от размерности БПФ, а это не очень удобно мне кажется. Бабочки все равно придется делать всех типов - от этого не уйти. Но вот с универсальным управлением как раз особых проблем быть не должно - просто когда появляется 3-х точечная бабочка, то пропадает кратность степеням двойки и вычисления в блоке управления придется делать "честным" образом. Основная проблема с нечетными бабочками заключается в организации памяти, но эта проблема существует и при реализации нескольких вариантов БПФ под свое кол-во точек. Так что лучше уж решить эту проблему в общем виде и получить одно БПФ для разного кол-ва точек.
|
|
|
|
|
|
|
|
Nov 30 2010, 10:28
|
Участник
Группа: Участник
Сообщений: 15
Регистрация: 23-11-08
Пользователь №: 41 876
|
Спасибо за ответы  . То, что принцип соединения бабочек одинаков, интуитивно понятно. Вызывает затруднение количество разнородных бабочек. Для чисел 1152, 1024, 704, 448 я выделил 2-х, 3-х, 4-х, 7-ми и 11-ти точечные бабочки. Цитата(Sefo @ Nov 30 2010, 02:58) Но вот с универсальным управлением как раз особых проблем быть не должно - просто когда появляется 3-х точечная бабочка, то пропадает кратность степеням двойки и вычисления в блоке управления придется делать "честным" образом. Это значит, обходиться без хитрых сдвигов и маскирований? Цитата(Sefo @ Nov 30 2010, 02:58) Основная проблема с нечетными бабочками заключается в организации памяти, но эта проблема существует и при реализации нескольких вариантов БПФ под свое кол-во точек. Так что лучше уж решить эту проблему в общем виде и получить одно БПФ для разного кол-ва точек. Насколько общим должен быть вид? Ведь от конкретного числа точек зависят количество этапов и применяемые бабочки? И еще, все сказанное Вами относится к БПФ типа пинг-понг (разрабатываемого в этой теме)? У Рабинера, Гоулда написано про поточный метод, мне показалось, там проще организация памяти.
|
|
|
|
|
|
|
|
Nov 30 2010, 16:57
|
Местный
Группа: Свой
Сообщений: 429
Регистрация: 11-08-05
Из: Санкт-Петербург
Пользователь №: 7 537
|
Цитата(Jhonny. @ Nov 30 2010, 13:28) Спасибо за ответы . То, что принцип соединения бабочек одинаков, интуитивно понятно. Вызывает затруднение количество разнородных бабочек. Для чисел 1152, 1024, 704, 448 я выделил 2-х, 3-х, 4-х, 7-ми и 11-ти точечные бабочки. Я бы 2-х точечную бабочку из списка исключил бы - она неэффективная. Лучше 5-ти точечную добавить - при наличии 7-ми и 11-ти точечных она уже погоды не сделает. Цитата(Jhonny. @ Nov 30 2010, 13:28) И еще, все сказанное Вами относится к БПФ типа пинг-понг (разрабатываемого в этой теме)? У Рабинера, Гоулда написано про поточный метод, мне показалось, там проще организация памяти. Все сказанное относится к подавляющему большинству реализаций БПФ. Поточный метод у Рабинера и Гоулда не для современного железа - сильно устаревший и по ресурсам жутко неэффективный. К тому же легко реализуем только если на всех этапах одинаковые бабочки (ну или хотя бы с кратным числом точек). В общем, решите реализовать поточный метод - ищите современные примеры. Цитата(Jhonny. @ Nov 30 2010, 13:28) Это значит, обходиться без хитрых сдвигов и маскирований? Угу. Цитата(Jhonny. @ Nov 30 2010, 13:28) Насколько общим должен быть вид? Ведь от конкретного числа точек зависят количество этапов и применяемые бабочки? Что касается памяти, то все зависит от того как вы собираетесь реализовать БПФ. От самого по себе числа точек и количества этапов ничего не зависит. Вопрос лишь в том, какие бабочки на этом этапе и какие на следующем. Если они одинаковые или кратные (2 и 4, например), то все просто. Если бабочка будет получать точки на вход по очереди, то проблем нет никаких, но крайне медленно. Если подавать все точки сразу, что весьма эффективно, то надо память разбивать на банки и писать/читать туда/оттуда так, чтобы для каждой бабочки все точки находились в разных банках. А это уже не так просто в вашем случае. Нужно сначала определиться с ресурсами и быстродействием и исходя из этого думать какие методы реализации подойдут.
|
|
|
|
|
|
|
|
Jan 4 2011, 21:48
|
Местный
Группа: Свой
Сообщений: 429
Регистрация: 11-08-05
Из: Санкт-Петербург
Пользователь №: 7 537
|
Вот "причесанный" код нашего БПФ (\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 ( 29.72 килобайт )
Кол-во скачиваний: 207
|
|
|
|
|
|
|
|
Jan 11 2011, 04:14
|
Местный
Группа: Свой
Сообщений: 264
Регистрация: 17-04-07
Из: Москва
Пользователь №: 27 102
|
Вот коэффициенты ROM_x.mif плюс файл Matlab для их генерации. Надеюсь ничего не напутал.
|
|
|
|
|
|
|
|
Jan 20 2011, 20:29
|
Местный
Группа: Свой
Сообщений: 429
Регистрация: 11-08-05
Из: Санкт-Петербург
Пользователь №: 7 537
|
Цитата(ZED @ Jan 11 2011, 07:14) Вот коэффициенты 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. В умножителях на поворачивающие коэффициенты у нас нет деления - у нас сдвиг. Так что вспоминайте как мы собирались вычислять коэффициенты.
|
|
|
|
|
|
|
|
Jan 29 2011, 10:54
|
Участник
Группа: Участник
Сообщений: 15
Регистрация: 23-11-08
Пользователь №: 41 876
|
Попытался оптимизировать бабочку, убрав повторяющиеся операции. Вот что получилось: Код 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. Имеет ли право на жизнь такая реализация, или есть другие варианты оптимизации?
|
|
|
|
|
|
|
|
Aug 4 2011, 05:14
|
Местный
Группа: Свой
Сообщений: 264
Регистрация: 17-04-07
Из: Москва
Пользователь №: 27 102
|
Цитата Добрый день!
Я разбираюсь с БПФ и не могу понять, как на практике вычисляются поворачивающий множитель W ?, в книжках написано W= e^(-j*2*p*n*k/N), k- номер отсчета, N- длина последовательности, n- текущий номер, толи я не те книжки читаю( Все правильно. Вы читаете именно те книжки.
|
|
|
|
|
|
|
|
Sep 29 2011, 08:18
|
Частый гость
Группа: Свой
Сообщений: 199
Регистрация: 27-05-09
Из: Москва
Пользователь №: 49 648
|
Цитата(Костян @ Sep 28 2011, 17:26) Почему для W используется разрядность всего 12 бит , тогда как данные 17 ?
Из каких соображений разрядность W взята меньше, чем входных данных ? По всей видимости, чтобы за грубить результаты вычислений, при этом экономя память.
|
|
|
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
