Реализация БПФ на ПЛИС, Тудности, встречаемые при реализации Опции

[ZED]

Доброго времени суток!

Нужно реализовать алгоритм БПФ с прореживанием по частоте на ПЛИС, но при реализации возникают трудности, вот некоторые из них:

1. Поворачивающие множители являются числами по модулю меньше либо равно единицы: |W|<=1. Я так понял, чтобы перейти к целым числам требуется умножать их на (2^N) и то, что после запятой отсекать (N - разрядность). Нужно ли то же самое делать с входными данными (x1 и x2) или не обязательно?
2. Нужно реализовать операции умножения и сложения со знаковыми числами, тут у меня такая задумка: преобразовать в integer соответствующего диапазона: от -(2^N)/2 до (2^N)/2 - 1, произвести нужные арифметические операции и преобразовать обратно std_logic_vector, код прилагается:

CODE

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_arith.all;

entity butterfly is
generic (b_size: natural := 14);
port (
x1, x2, w: in std_logic_vector(b_size - 1 downto 0);
y1, y2: out std_logic_vector(b_size - 1 downto 0)
);
end entity butterfly;

architecture behavioral of butterfly is
signal x1_int, x2_int, w_int: integer range -8192 to 8191;
signal y1_int: integer range -8192 to 8191;
signal y2_int: integer range -134217728 to 134217727; -- Т.к. производится умножение на поворачивающий множитель
begin
process (CLK) is
begin
-- Преобразовываю в тип integer:
x1_int <= conv_integer(x1);
x2_int <= conv_integer(x2);
w_int <= conv_integer(w);
y1_int <= conv_integer(y1);
y2_int <= conv_integer(y2);

-- Вычисляю бабочку и преобразовываю обратно в std_logic_vector (b_size - 1 downto 0):
y1 <= conv_std_logic_vector(x1_int + x2_int, b_size);
y2 <= conv_std_logic_vector((x1_int - x2_int) * w_int, b_size);
end process;
end architecture behavioral;

Вопрос будет ли так корректно сделать или все делается совершенно по-другому?
Буду рад любым вашим замечаниям, предложениям, советам и ссылкам. Заранее спасибо!

P.S. На форуме я искал и не нашел ответа на свои вопросы, тем более я уверен далее появятся новые, думаю лучше, чтоб это все было в одной теме...

[Sefo]

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

Чтобы не зарубится сразу в дебри сделаем БПФ на фиксированное число точек и, к тому же, являющееся степенью 4, 8 или 2. От того, какому числу будет кратно количество точек зависит какие бабочки нам потребуются и сколько будет этапов. Например, если взять 16 точек, то взяв 2-х точечную бабочку получим 3 этапа и, если принять, что бабочка и умножение на доворачивающие коэффициенты делается за один такт, то потратим 8*3=24 такта (т.е. на каждом этапе мы считаем по 8 бабочек). В случае с 4-х точечной бабочкой БПФ вычислится за 4*2=8 тактов (т.е. на каждом этапе мы считаем по 4 бабочки). Если взять 8-ми точечную бабочку (Т.Б.), то придется вычислять БПФ в 2 этапа и одной 8-ми Т.Б. будет недостаточно - либо на первом, либо на последнем этапе потребуется 2-х точечная бабочка. Тактов это займет 2+8=10 (т.е. на первом этапе вычисляем две 8-ми Т.Б., а на втором восемь 2-х Т.Б.). Если взять 32 точки, то портебуется либо 8-ми и 4-х Т.Б., либо 4-х и 2-х Т.Б., либо только 2-х Т.Б. Этапов потребуется соответственно 2, 3, 5. Тактов потребуется соответственно 4+8=12, 8+8+16=32, 5*16=80. В общем, чтобы понять, сколько этапов и какие бабочки нужны, надо разложить кол-во точек БПФ N на произведение a*b*c*...=N, где сами множители это степень бабочки, а их количество это количество необходимых этапов. Например при N = 16 подходят след. разложения 2*2*2=16, 4*4=16, 8*2=16. При N = 32 возьмем разложения, соответствующие описанным выше примерам: 8*4=32, 4*4*2=32, 2*2*2*2*2=32. Понятно, что в некоторых случаях количество этапов это просто показатель степени (2^5=32)

Далее нужно определится с необходимым быстродействием. Речь не идет пока о частоте клока - речь идет о простом количестве тактов (т.е. их интервал в нс, мс, мкс и т.д. не имеет значения). Одновременно нужно определится и с необходимым количеством ресурсов микросхемы. В БПФ связь этих двух параметров довольно четкая - мало тактов - много места, много тактов мало места. Например, выше, все расчеты тактов делались исходя из того, что бабочка и умножение на коэффициенты делаются за один такт. Это очень быстро, но для 4-х Т.Б. потребуется 8*4=24 сумматора (8 т.к. суммируем комплексные числа) и 3 комплексных(!) умножителя (т.е. 4*3=12 умножителей и 2 сумматора). Однако, если все это вычислять за 4 такта, то надо 8 сумматоров и 1 комплексный умножитель - существенно меньше по ресурсам, но в 4 раза медленнее. Кроме того 8-ми Т.Б. сама по себе больше 4-х, а 4-х больше 2-х.

Вот теперь про частоту клока. Потерю быстродействия можно компенсировать увеличением во столько же раз частоты клока, но тут нужно не забывать, что слишком большая частота клока может потребовать введения конвееризации некоторых операций. Это снизит выигрыш (степень компенсации) от увеличения частоты клока и неизбежно увеличит количество требуемых ресурсов. В конце концов, при слишком большой частоте появятся проблемы с "раскладкой" в ПЛИС.

Итак :

1) скольки точечное БПФ нужно?

2) Какой баланс выбираем между быстродействием, ресурсами и частотой клока?

Еще одно замечание. Для вычисления 4-х и 2-х Т.Б. нужны только сумматоры, а вот при вычислении 8-ми Т.Б. потребуется еще 2 умножителя. Правда умножать они будут всегда на константу - SQRT(2) (кажется).

Сообщение отредактировал Sefo - Feb 18 2009, 15:34