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

[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. На форуме я искал и не нашел ответа на свои вопросы, тем более я уверен далее появятся новые, думаю лучше, чтоб это все было в одной теме...

[soldat_shveyk]

1. Чтобы поворачивающий множитель W, меньший единицы, преобразовать в целое число, имеющее разрядность N бит, надо выполнить следующее преобразование:
round(W*(N-1)) - если число положительное,
(2^N) - round(abs(W)*(N-1)) - если число отрицательное.

Правила приведены для дополнительного кода.

2. Для умножения знаковых чисел надо пользоваться специальной мегафункцией, указав ей параметр "SIGNED"

3. Если вы делаете БПФ на ПЛИС, то надо смотреть на алгоритмы по основанию 4, а не по основанию 2.
Получается намного удобнее и эффективнее. Классическая бабочка - наследие от процессоров DSP, где она сделана аппаратно. Ядром алгоритма БПФ по основанию 4 является более сложный 4-х точечный БПФ, где все поворачивающие множители равны либо 1, либо -1. На ПЛИС удобно реализуется на сумматорах, можно сделать комбинаторную сехему, выполняющею этот самый 4-х точечный БПФ за один такт. Я такое делал, железно работало на частотах выше 100 МГц.

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

[Builder]

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

Сам не знаю как лучше, но все-же, а если посмотреть как делает та-же Альтера или Ксалинкс?
Возможность посмотреть исходники вроде есть.

[ZED]

Сам не знаю как лучше, но все-же, а если посмотреть как делает та-же Альтера или Ксалинкс?
Возможность посмотреть исходники вроде есть.

Пишу в квартусе, стало быть ПЛИС Альтера, если можно дайте ссылочку на исходник. У Калинкса нашел там для фиксированной запятой, пытался разобраться, не получилось...

Для умножения знаковых чисел надо пользоваться специальной мегафункцией, указав ей параметр "SIGNED"

Так и думал, что сначала нужно перевести к типу SIGNED.
Нужно ли то же самое делать с входными данными (x1 и x2) или не обязательно?

Если вы делаете БПФ на ПЛИС, то надо смотреть на алгоритмы по основанию 4, а не по основанию 2.

Тоже к этому склоняюсь. буду думать...

round(W*(N-1)) - если число положительное,

вот это не совсем понял

Сообщение отредактировал ZED - Jan 18 2009, 21:45

[soldat_shveyk]

Я малость ошибся правильно будет так:

round(W*(2^(N-1)-1))

Пример:
допустим, поворачивающий множитель равен W=0.077391
и нужно преобразовать в 16-разрядную целочисленную форму, представленную в дополнительном коде (1 знаковый бит + 15 бит мантисса).

(2^15) - 1 = 32767.

0.077391 * 32767 = 2535.8709 - дробную часть нельзя просто отбросить, нужно выполнять честное округление,
чтобы ошибка была центрированая, поэтому
round(2535.8709) = 2536.

[ZED]

Я малость ошибся правильно будет так:
round(W*(2^(N-1)-1))

Теперь понятно, спасибо!

Вот такой еще вопрос возник, нужно реализовать ПЗУ (ROM) для поворачивающих множителей, планирую подавать адрес и читать из файла, но Квартус синтезирует RAM память, а не ROM со всякими там WE, data_in и т.д., которые соответственно подключены либо к генератору нуля или единицы. А из файла не читает, не пойму может я где ошибся или нужно что-то указывать при синтезе, вот мой код:

Код

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_unsigned.all;
use std.textio.all;

entity fft_rom is

generic(addr_size : natural := 5;
data_size : natural := 14);

port(
clk: in std_logic;
addr: in std_logic_vector (addr_size - 1 downto 0);
data: out std_logic_vector (data_size - 1 downto 0)
);
end entity fft_rom;

architecture behavioral of fft_rom is

type RomType is array (0 to 2**5) of bit_vector(data_size - 1 downto 0);
-- Функция чтения из файла:
function FillRom (RomFileName: in string)
return
    RomType is
    file RomFile: text is in RomFileName;
    variable RomFileLine : line;
    variable ROM: RomType;
begin
    for i in RomType'range loop
        readline(RomFile, RomFileLine);
        read (RomFileLine, ROM(i));
    end loop;
    return ROM;
end function;
-- конец функции

signal ROM: RomType := FillRom("C:\ROM.dat");

begin
    process(clk)
        begin
            if (clk'event and clk = '1') then
                data <= to_stdlogicvector(ROM(conv_integer(addr)));
            end if;
    end process;
end architecture behavioral;

С Квартусом никогда не работал, может кто чего посоветует?

P.S. Также остается открытым вопрос, корректно таким способом организовать бабочку или же это делается другими методами?

Код

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;

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


architecture behavioral of butterfly is

signal x1_int : integer range -8192 to 8191;
signal x2_int : integer range -8192 to 8191;
signal w_int : integer range -8192 to 8191;
signal y1_int : integer range -8192 to 8192;
signal y2_int : integer range -13427728 to 13427727;

begin
x1_int <= to_integer(signed (x1));
x2_int <= to_integer(signed (x2));
w_int <= to_integer(signed (w));

process (CLK)
begin
if (rising_edge(CLK)) then
    y1_int <= x1_int + x2_int;
    y2_int <= (x1_int - x2_int)*w_int;
end if;
end process;
y1 <= std_logic_vector(to_signed(y1_int, b_size));
y2 <= std_logic_vector(to_signed(y2_int, b_size));
end behavioral;

[soldat_shveyk]

Не силен в Verilog. Помочь не могу.
А не пробовали использовать мегафункцию FFT?

[ZED]

Не силен в Verilog. Помочь не могу.
А не пробовали использовать мегафункцию FFT?

Это VHDL, мегафункцию не пробовал, кстати посоветуете какую и где скачать? Но просто хочется самому реализовать, "ручками" так сказать. Я вот тоже к сожалению не силен в vhdl, но очень хочу его освоить, вот и задаю вопросы. В книжках она как правило не освещены, либо я читаю не те книжки. Кстати слышал вышла книжка: Перельройзен Е.З. Проектируем на VHDL. - М.: Изд-во "СОЛОН-Пресс", 2004. Читал кто? Как она? К сожалению уже все раскупили, где достать не знаю...

[soldat_shveyk]

ALTERA FFT Compiler - все основное там есть. Для моделирования достаточно оригинальной версии,
посмотрите, поиграете параметрами - выберете что Вам подойдет.
Там еще хелп достаточно полезный приложен.
Если не подойдут Вам оригинальные варианты, то берем Рабинера-Голда, и впред, создавать свою реализацию.

[ZED]

Если не подойдут Вам оригинальные варианты, то берем Рабинера-Голда, и впред, создавать свою реализацию.

Рабинер Голд имеется, но вот с языком проблемы, вот я и спрашиваю как то или иное реализовать на vhdl, почему так или иначе синтезирует квартус и т.д.

ALTERA FFT Compiler - все основное там есть. Для моделирования достаточно оригинальной версии,
посмотрите, поиграете параметрами - выберете что Вам подойдет.

Спасибо, документацию нашел, а вот сам файл не смог скачать...

[soldat_shveyk]

Для ознакомительной работы в режиме OpenCore можно скачать без проблем. Пробуйте.

Еще погуглите кракнутый FFT Compiler, в сети полно этого добра. Для начала подойдет любая, не обязательно самая свежая версия.
Там можно будет и исходники посмотреть, они как раз на VHDL.

[ZED]

Вопрос по vhdl остается открытым, но похоже кроме soldat_shveyk и меня эта тема (БПФ) никого не интересует...

[soldat_shveyk]

Откопал у себя исходники всех альтеровских БПФ-ов, если надо, пришлю.
Исходники рабочие, пользовался, проверял.

[ZED]

Буду очень признателен: zed1986@yandex.ru

Спасибо!

[ZED]

Возникла еще одна проблема, реализую БПФ по схеме "пинг-понг", т.е бабочка, две ОЗУ и одно ПЗУ для хранения поворачивающих множителей. Бабочку нужно подключать то к одной памяти на чтение, а к другой на запись, то на оборот:

ОЗУ - 1 | Чтение | Запись | Чтение | Запись |
-------------------------------------------------------------
ОЗУ - 2 | Запись | Чтение | Запись | Чтение |

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

[BuTeK]

поделитесь рабочей коркой БПФ на почту cvik@tut.by

[ZED]

поделитесь рабочей коркой БПФ на почту cvik@tut.by

Рабочей пока нету, тем более она у меня не дома, так что до понедельника...

[анатолий]

Проще всего сначала представить данные в формате Integer с диапазоном.
Тогда и отлаживать, и видеть вычисления проще, и сравнить с Матлабом можно,
и синтезируется нормально.
Напр. Бабочка программируется так:
YR<=AR+BR*WR/32768-BI*WI/32768;
и т.д.,
где все числа - в диапазоне -32768... 32767.
Напр. коэффициент WR= 0,999=32767.
Вот только двоичную инверсию лучше делать с переводом адреса с целого в вектор и обратно.
А в конце все это можно перевести в векторные данные и соптимизировать по точности и т.п.

[ZED]

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

[ZED]

В общем нужно масштабировать данные после операций бабочки, вопрос как это сделать? Тут похоже ключевая фраза: "блочная плавающая точка". Может есть у кого какая-нибудь информация по этому поводу? Также вопросы какие разряды брать после умножителя (знаю на форуме было две темы по этому поводу, но там все так путанно, столько мнений, в общем теряюсь где правда, где нет). То же дело обстоит с сумматорами. Подскажите пожалуйста или дайте ссылки на инфу...

[Sefo]

Как ваши дела с БПФ? Если вопрос еще актуальный и хочется разобраться самому во всех тонкостях и написать свой собственный БПФ, а не хоть как-нибудь "пристроить" чужой, то могу Вас "провести" по процессу создания БПФ своими руками от начала и до конца. Только начать придется с начала, но зато будет нужный Вам результат.

[BuTeK]

Конечно актуально! Поделитесь информацией... Очень итересно!

[ZED]

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

[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

[ZED]

Не совсем понял про разделение бабочки и поворачивающих множителей. Ведь сама бабочка включает в себя домножение на поворачивающий множитель. Вот к примеру бабочка с прореживанием по частоте:

W - поворачивающий множитель, который меняется от бабочки к бабочке и от этапа к этапу.
Теперь с количеством точек: нужно 2048.
Выбор баланса - быстродействие.
Также предлагаю реализовать алгоритм с постоянной структурой по схеме "пинг-понг":


Прореживание по частоте.
Суть метода: В ОЗУ-1 находятся отсчеты сигнала, над которыми будет производиться БПФ, на нечетных этапах данные берутся из ОЗУ-1, а поворачивающие множители из ПЗУ, вычисляется бабочка и результат записывается в ОЗУ-2 (бабочка одна). Те же действия повторяются над всеми парами точек. Для четных этапов все наоборот: данные берутся из ОЗУ-2, поворачивающие множители по-прежнему из ПЗУ, вычисляется бабочка и результат записывается в ОЗУ-1.

[Sefo]

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

[ZED]

Хорошо, жду с нетерпением, завтра я буду вечером и с удовольствием прочту. Спасибо!

[Sefo]

На рисунке показана базовая операция для БПФ с прореж. по частоте, если бы было прореживание по времени, то умножение на W было бы нарисовано не на выходе, а на входе. Кроме того, значение W зависит от положения бабочки в схеме алгоритма. В некоторых случаях, умножение на W является тривиальным: когда W = -+1 + j0 умножение как таковое вообще отсутствует, когда W = 0 +- j1 реальная и мнимая части просто меняются местами и изменяется знак. Алгоритмов вычисления БПФ можно придумать много, а способов реализации каждого - еще больше. К примеру, если при реализации алгоритма используется несколько экземпляров бабочек, чтобы распараллелить вычисления, то, может оказаться, что какие-то экземпляры бабочек всегда будут получать тривиальные коэффициенты и им комплексные умножители вообще не понадобятся. В конце концов, суть БПФ в том, что ДПФ большего порядка вычисляются через ДПФ меньшего. Ведь n-точечная бабочка это не что иное, как n-точечное ДПФ. Вы сами можете легко получить формулы для вычисления n-точечных бабочек просто расписав n-точечное ДПФ и упростив выражения. Поэтому, если рассуждать строго, считать умножение на W частью бабочки, как на вашей картинке, неправильно. В любом случае, с инженерной точки зрения, умножение на W следует вынести за пределы бабочки. Это дает возможность лучше понять где и на чем можно сэкономить при реализации алгоритма БПФ и это так же дает некоторые удобства самой реализации. Так что далее, упоминая бабочку, я буду иметь ввиду "чистую" бабочку.

Теперь про некоторые особенности бабочек.

Если Вы распишите 2-х и 4-х точечное ДПФ, то увидите, что все коэффициенты тривиальные: либо вещественная, либо мнимая 1! При реализации, умножение на такие коэффициенты не требует использования умножителей. Поэтому, 2-х и 4-х точечные бабочки "дешевые" для реализации. Все что нужно, это сложить, вычесть и поменять местами Re и Im.

С 8-ми и более Т.Б. дела обстоят хуже – если Вы их распишите, то увидите, что появляются нетривиальные коэффициенты – SQRT(2)/2. Тут без умножителей не обойтись. Правда, умножители эти всегда умножают на константу, что несколько экономит место (если нет DSP блоков или речь идет об ASIC, а не о ПЛИС). Из-за этого нюанса, внесение в бабочку еще и умножения на W может запутать новичка.

Итак важная особенность бабочки ("чистой") в том, что она всегда вычисляется одинаково, в каком бы алгоритме она не применялась.

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

Теперь про реализацию.

Хотите Пин-понг – реализуем пин-понг. Но Вы уверены, что 2-х Т.Б. Вас устроит по быстродействию? Ведь 2-х точечная бабочка для 2048 точек это 11*1024 = 11264 такта (4-х + 2-х точечная сделают все за 512*5 + 1024 = 3584).

[ZED]

Честно говоря, конечно лучше бы 4-х Т.Б. Но как с ней сделать алгоритм на 2048 точек, нам ведь все равно потребуется 2-х Т.Б. ? Если это можно сделать с 4-х Т.Б. я вполне согласен!

[Sefo]

Итак, делаем более быстрый вариант с 4-х и 2-х Т.Б.

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

Не знаю, насколько у Вас много времени, но лучше, если Вы нарисуете схему и блок-схему в чем-нибудь вроде Visio, чтобы было проще ее редактировать, исправляя ошибки или оптимизируя (и Вам и мне).

Поскольку мы уже подходим к реализации, то мне необходимо знать какой Вы спроектировали интерфейс между БПФ и самой системой - т.е. кто является источником данных и какой протокол передачи их в БПФ, кто является приемником данных и по какому протоколу он их будет принимать. Также мне надо знать какая(какие) ПЛИС будут использованы и какая частота клока.

Если я правильно нпонял, то средой разработки будет Квартус и Вы с ним не очень знакомы. Можно полюбопытствовать какой у Вас опыт разработки и какими программами Вы пользовались?

[ZED]

Пока никакого интерфейса я не проектировал, считал, что данные уже лежат в одном из ОЗУ (Точнее в двух - для реальной и мнимой части). Опыт разработки у меня очень маленький, был отдаленно знаком с Ise WebPack, но уже все забыл. С квартусом да не очень знаком, ибо иногда не подозреваю что он выкинет в RTL на тот или иной участок кода. Схема получается довольно-таки громоздкая из-за мультиплексирования, переключения шин, да и задержек с адресами. Так что не уверен, что она будет понятна. У меня в принципе основной вопрос как масштабировать результаты после бабочки и домножения на поворачивающие множители, т. е. все упирается в реализацию бабочки и домножения и масштабирования.

[Sefo]

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

P.S. Поймите, если Вы реализуете БПФ кое-как, потратив немеряно времени на отладку и накладывая одну заплату на другую - Вы ничему не научитесь. Я сталкивался с глюками Квартуса, видел как он делает некоторые вещи нерационально, но... я не могу сказать про него, что я "иногда не подозреваю что он выкинет в RTL на тот или иной участок кода". На правильно написанный код действия Квартуса всегда предсказуемы.

Сообщение отредактировал Sefo - Feb 20 2009, 19:24

[ZED]

Вот пожалуйста, мои инсинуации: http://ifolder.ru/10661141
___________
|D Q |
|___CLK____|

Это задержка на несколько тактов (на 3, если бабочка выполняется за один такт, т.к. из памяти данные поступают через 2 такта после подачи адреса)

Mux - соответственно мультиплексоры

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

[Sefo]

Первые комментарии такие. Это не блок схема, а схема электрическая принципиальная. Но поскольку она не полностью дорисована, то она с практической точки зрения безполезна - из нее с трудом видна структура устройства и она недостаточно детальна, чтобы по ней кодировать (к тому же если ее один в один перенести в VHDL, то получится не самое лечшее использование возможностей языка).

Непонятно назначение блока на входе памяти данных с одним входом D, двумя выходами Q и сигналом Sel (Sel_demux). Какую функцию они выполняют? Ведь если D, по вашей задумке должно подаваться только на один из Q, то что тогда что будет на другом???

Еще непонятно назначение мультиплексоров на выходе из памяти. Получается, что данные, которые всегда являются вещественной частью (согласно схеме), могут (и будут) попадать на вход бабочки, куда должна подаваться мнимая часть и наоборот. Похоже баг.

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

[ZED]

Непонятно назначение блока на входе памяти данных с одним входом D, двумя выходами Q и сигналом Sel (Sel_demux). Какую функцию они выполняют? Ведь если D, по вашей задумке должно подаваться только на один из Q, то что тогда что будет на другом??? smile.gif

Это переключатель шины, он выдает сигнал со входа D на выход Q_1 или Q_2, в зависимости от сигнала sel_demux

У нас базовая операция (БО) бабочка должна сначала брать данные из памяти 1, а потом из памяти 2, поэтому нужны мультиплексоры в том числе и на выходе из памяти.

Получается, что данные, которые всегда являются вещественной частью (согласно схеме), могут (и будут) попадать на вход бабочки, куда должна подаваться мнимая часть и наоборот. Похоже баг.

Да тут я просто перепутал, там в бабочке по-другому расположены сигналы? должно быть так:
http://ifolder.ru/10668100

Это не блок схема, а схема электрическая принципиальная. Но поскольку она не полностью дорисована, то она с практической точки зрения безполезна - из нее с трудом видна структура устройства и она недостаточно детальна, чтобы по ней кодировать (к тому же если ее один в один перенести в VHDL, то получится не самое лечшее использование возможностей языка).

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

[Sefo]

Но что подается на Q2 когда D подается на Q1?

[ZED]

На Q2 подается Z, когда D подается на Q1

[Sefo]

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

Кроме блок схемы я просил Вас еще нарисовать схему алгоритма БПФ, причем, раз уж мы решили делать с помощью 4-х и 2-х Т.Б., то имеется ввиду именно эта схема (конечно-же не надо расписывать "честно" все 2048 точек ). Вы ее уже нарисовали?

Блок-схема должна отражать основные блоки и потоки данных и управления. На блок схеме нет смысла расписывать, что, например, память состоит из двух блоков - как ее реализовать мы решим позже. Сначала нужно понять какими свойствами должно обладать память, что ей нужно на вход, какое управление и что у нее быдет на выходе. Между прочим, нет особой необходимости вещественную и мнимую части хранить строго в разных блоках памяти. Можно и в одном блоке - решить, что n старших разрядов это Re, а n младших разрядов Im.

Когда мы нарисуем хорошую блок-схему мы поймем какие блоки нам нужны и как они будут взаимодействовать. После этого можно будет прорабатывать внутренности каждого блока по-отдельности.

[ZED]

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

Согласен, можно шину подключить к 1-ой и 2-ой ОЗУ, нам ведь все равно, сигнал WE в принципе все разреши (когда можно записывать, а когда нет)

Кроме блок схемы я просил Вас еще нарисовать схему алгоритма БПФ, причем, раз уж мы решили делать с помощью 4-х и 2-х Т.Б., то имеется ввиду именно эта схема (конечно-же не надо расписывать "честно" все 2048 точек smile.gif). Вы ее уже нарисовали?

Не не нарисовал, т.к. не особо понимаю как делать с помощью 2-х бабочек (2-х ТБ и 4-х ТБ) какие там нужны поворачивающие множители. Может вы что подскажите?

Блок-схема должна отражать основные блоки и потоки данных и управления. На блок схеме нет смысла расписывать, что, например, память состоит из двух блоков - как ее реализовать мы решим позже. Сначала нужно понять какими свойствами должно обладать память, что ей нужно на вход, какое управление и что у нее быдет на выходе. Между прочим, нет особой необходимости вещественную и мнимую части хранить строго в разных блоках памяти. Можно и в одном блоке - решить, что n старших разрядов это Re, а n младших разрядов Im.

Память должна быть двухпортовая, должна иметь сигнал разрешения записи WE, соответственно она должна тактироваться (CLK).

Сообщение отредактировал ZED - Feb 21 2009, 16:12

[Sefo]

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

Схему алгоритма я нарисую, но, видимо, к вечеру понедельника или во вторник.

Вы же, попробуйте, всетаки, нарисовать блок-схему и продумайте интерфейс БПФ с внешним миром. Как-то же надо данные туда загрузить, а результаты выгрузить . Или для Вас БПФ это совсем учебный пример, который и в ПЛИС никода в реальности прошиваться не будет?

[ZED]

Не, это не учебный, ну я думаю там отсчеты будут поступать через АЦП в буферную внешнюю ОЗУ, а оттуда загружаться внутрь ПЛИС в ОЗУ-1, но я не селен в ПЛИСах, поэтому не могу продумать сей интерфейс, может подскажите где прочитать?

[Sefo]

Все внешние интерфейсы всегда определяются тем, к чему вы подсоединяете свое. В данном случае, есть 2 варианта.

1) Отсчеты АЦП нужны только для БПФ

2) Только некоторая часть отсчетов АЦП "идет" в БПФ.

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

Во 2-м случае, нужно либо "честно" в нужные моменты времени перекачивать данные из буферного внешнего ОЗУ в память БПФ, либо попытаться свести все к варианту 1), т.е подсоединить выход АЦП и к ПЛИС и к внешнему ОЗУ параллельно и по каки-нибудь сигналам внешней синхронизации "выхватывать" нужные порции данных АЦП из потока.

Раз задача реальная, то расскажите мне по-подробнее, какую роль в ней играет ПЛИС и БПФ и тогда я смогу подсказать как лучше организовать интерфейсы.

[ZED]

Не, у меня первый вариант, я так понимаю, что блок должен генерить сигнал ClockEnable для ОЗУ-1...

[Sefo]

Только не ClockEnable, а Write_Enable. Он так же должен следить за состоянием БПФ и когда тот освободится стартовать очередную закачку данных в БПФ.

Вот обещанная схема алгоритма БПФ http://ifolder.ru/10719475. Каждый этап я нарисовал на отдельном листе (за исключением 5-го и 6-го - они на одном листе). На схеме номера точек, это адрес памяти, при этом на 1-ом этапе, слева, адрес памяти соответствует также порядковому номеру входного отсчета. Я пока не нарисовал как переставлены выходные гармоники - в ближайшее время дорисую.

В качестве упражнения для Вас на 4, 5 и 6 этапах я оставил незаполненными поворачивающие коэффициенты. Вам нужно, посмотрев как W образуются на 1, 2 и 3 этапах, распространить эту же логику на оставшиеся. На 6-м этапе будьте внимательны - там есть небольшой подвох (т.е. все очень логично, но можно по "инерции" ошибиться).

Итак: с Вас блок схема БПФ и недостающие коэффициенты на схеме алгоритма БПФ

[Sefo]

Куда же Вы пропали?

[ZED]

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

[ZED]

Вот исправленный БПФ-алгоритм и недоделанная схема, может завтра довершу ее, если получится, а сейчас уже поздно...

Прикрепленные файлы

 FFT.rar ( 438.26 килобайт ) Кол-во скачиваний: 251

 

[Sefo]

Стоп, стоп! С блок-схемой притормозите - к сожалению, Вы опять рисуете схему электрическую принципиальную, к тому же опять намудрили с мультиплексорами. Я вечером нарисую блок-схему, а Вы ее доработаете - так, думаю, лучше будет, иначе зря потратите кучу времени.

С коэффициентами на 6-м этапе, увы, ошиблись. Какие бы Вы там коэффициенты написали бы, если бы я Вас не предостерег от возможной ошибки?

[Sefo]

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

Что с коэффициентами на 6-м этапе? Есть хоть какие-нибудь соображения?

Теперь немного про вашу схему.

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

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

Если уж Вы стали рисовать 2-х тактовую 4-х ТБ, то демультиплексор из 2 в 3 ненужен, даже несмотря на то, что данные подаются еще и на 2-х ТБ . Нужен обычный мультиплексор 2 в один (поскольку данные нужно брать то из одной памяти, то из другой). Мы ведь этот ляп уже обсуждали. Почему Вы его снова допустили?

Прикрепленные файлы

 FFT_Diagram.rar ( 27.17 килобайт ) Кол-во скачиваний: 306

 

[ZED]

А вот, что подразумевалось под блок-схемой=)) Спасибо, понял... Алгоритм переделал, по крайней мере я думаю, что так должно быть. А как дать бабочке сразу 4 отсчета, я просто не представляю это возможным, кроме как через задержку на один так два из них.

Мы ведь этот ляп уже обсуждали. Почему Вы его снова допустили?

Мы обсуждали ляп про переключение шины.

Нужен обычный мультиплексор 2 в один (поскольку данные нужно брать то из одной памяти, то из другой)

Вы предлагаете подключать данные еще и к 2-х Т.Б. всегда?

Вот блок-схема БПФ. Вам нужно дорисовать к ней интерфейс с внешним миром.

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

Прикрепленные файлы

 FFT.rar ( 298.89 килобайт ) Кол-во скачиваний: 151

 

[Sefo]

...строго не судите, просто очень сложно все это не в живую обсуждать...

Я Вас понимаю.

Алгоритм переделал, по крайней мере я думаю, что так должно быть.

Увы, не так Если Вы внимательно посмотрите на предыдущие этапы, то заметите следующее. На первом этапе 1 группа из 512-ти бабочек, на втором этапе – 4 одинаковых группы по 128 бабочек и т.д. В каждой группе нулевая бабочка (будем считать с 0) имеет все коэффициенты W0. Так вот на 6-ом этапе у нас получается 1024 группы по 1 бабочке в каждой – она 0-ая и единственная. Так что все коэффициенты у нее W0. При классическом (как наш) прореживании по частоте на последнем этапе нет умножений (в смысле, что умножаем все на W0 = 1). При прореживании по времени, умножение отсутствует на первом этапе.

Исправляйте...

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

Принципиально, это ничем не отличается от того, чтобы подавать 2 отсчета одновременно, или 3, или 5. Что именно Вас смущает в том, чтобы подавать одновременно больше 2-х отсчетов?

Мы обсуждали ляп про переключение шины.

Здесь все тоже самое.

Вы предлагаете подключать данные еще и к 2-х Т.Б. всегда?

У Вас все равно не получится ничего не подать на вход 2-х точечной бабочки. Внутри ПЛИС нет логических ячеек с Z-состоянием на выходе (Quartus на этом прекратит синтез с ошибкой). Но даже в обычной схеме, если вы выход микросхемы А переведете в Z-состояние, то на входе микросхемы Б, на который приходит провод с выхода микросхемы А, не будет "ничего" – микр. Б все равно будет как-то "интерпретировать" то, что будет наводится на входную ножку Поэтому все равно, что Вы подадите на 2-х точечную бабочку когда она не нужна – специальную константу, случайные сигнал или то же, что и на 4-х Т.Б. Вам все равно придется поставить мультиплексор, который будет выбирать откуда брать результат – с 2-х или 4-х Т.Б.

Про блок-схему напишу днем или вечером.

[ZED]

Исправил.

Вас смущает в том, чтобы подавать одновременно больше 2-х отсчетов?

Да, меня это смущает, как из памяти сразу считать 4 отсчета, где мы возьмем такую память? Если только сами напишем...

Прикрепленные файлы

 FFT_2048.rar ( 272.28 килобайт ) Кол-во скачиваний: 155

 

[Sefo]

Теперь про блок-схему.

Если бы там нужно было только лишь нарисовать АЦП и три зеленые линии, то я не стал бы Вас просить это делать - это нарисовать можно меньше чем за минуту.

Я хотел, чтобы Вы немножко подумали как подключить АЦП к БПФ.

Блок-схема она не просто так рисуется – это первое приближение реализации. Она определяет макроблоки (модули) проекта и их взаимодействие. От того, насколько мы удачно разделим устройство на макроблоки зависит простота и удобство дальнейшего проектирования, реализации и отладки. Блок-схема не должна углубляться в детали реализации, но и не может от них абстрагироваться совсем – она должна учитывать реализацию, но в первом приближении. Блок-схема не расписывает детально все сигналы, соединяющие блоки, но она определяет структуру интерфейсов между ними. Макроблок, в свою очередь, не должен быть "перегружен начинкой". Грубо говоря, блок-схему БПФ можно свести и к 2-м квадратам "Память" и "Бабочка", двунаправленной стрелки между ними, стрелки на вход от АЦП и стрелки на выход. Но от такой блок-схемы не будет никакой помощи в реализации. Наоборот возникнет множество вопросов вроде "как это реализовать?", "куда это поместить?" (в "Бабочку" или в "Память"), "как это состыковать?" и т.д. и т.п.

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

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

2) Я бы не нарисовал блок управления, но нарисовал бы управляющие сигналы от блока к блоку. Этот вариант гораздо лучше 1-го. В некоторых системах такое распределенное управление бывает даже весьма выгодным и удобным, но в нашем случае оно хуже, чем централизованное. В нашем случае операции в блоках настолько детерминированы, набор их настолько ограничен, а взаимодействия между блоками настолько стационарны, что удобнее управлять всем этим из одного места. При попытке сделать в БПФ распределенное управление, мы столкнемся с трудностью его распределения по блокам.

Идем дальше.

На моей блок-схеме потоки данных, обозначенные синими линиями, одинаковые. Из памяти в бабочку мы передаем 4 точки всегда (2-х Т.Б. может рассматриваться либо как частный случай, когда из 4 точек используются только 2, а можно сделать и две 2-х ТБ – они ведь очень маленькие и сверх простые и схема БПФ нам это позволяет, но об этом позже), из бабочки в умножители тоже 4 точки всегда (неважно, что один из 4-х умножит. физически будет там отсутствовать за перманентной равностью коэффициента 1), из умножителей в память тоже возвращается 4 точки всегда. Мало того, точки-то комплексные!

И тут Вы... , извините,... "втыкаете" АЦП прямо в память! Неужели он у Вас выдает комплексный сигнал и по 4 точки за раз?!

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

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


Предлагаю параллельно с подключением АЦП заняться уже и самой бабочкой.

Сколько разрядов на данные и сколько на коэффициенты Вы предполагаете?

Напишите, пожалуйста VHDL код 4-х точечной бабочки (не забудьте, умножение на доворачивающие множители в нее не входит). Если что-то не ясно, не стесняйтесь, спрашивайте сразу.

Сообщение отредактировал Sefo - Mar 6 2009, 15:46

[sazh]

Теперь про блок-схему.

Я хотел, чтобы Вы немножко подумали как подключить АЦП к БПФ.

А кто с утра еще не пЪян,
тот, извините , не улан.

[Sefo]

[ZED]

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

Добавил блок квадратурной дискретизации.

Сколько разрядов на данные и сколько на коэффициенты Вы предполагаете?

На данные 16 разрядов, на коэффициенты - 12.

Напишите, пожалуйста VHDL код 4-х точечной бабочки (не забудьте, умножение на доворачивающие множители в нее не входит).

Попробовал, прилагаю, не забыл

Если что-то не ясно, не стесняйтесь, спрашивайте сразу.

Спасибо!

Прикрепленные файлы

 FFT_2048.RAR ( 66.72 килобайт ) Кол-во скачиваний: 188

 

[ZED]

Там нужно еще библиотеку добавить:

Код

use IEEE.std_logic_unsigned.all;

[Sefo]

После просмотра и синтеза вашего кода в Квартусе у меня появились следующие вопросы:

1) Зачем Вы поставили регистры на входе?

2) Зачем Вы используете тип integer? Тем более, что разрядность входных данных у Вас задана через параметр, а диапазон значений integer жестко фиксирован.

3)Просинтезируйте (просто отдельным проектом только butterfly_complex.vhd) и посмотрите в RTL Viewer во что превращается ваш код. Проанализируйте, во что Квартус его превратил.

[ZED]

Зачем Вы поставили регистры на входе?

Да, действительно, все CONV_INTEGER нужно вынести за процесс...

Зачем Вы используете тип integer? Тем более, что разрядность входных данных у Вас задана через параметр, а диапазон значений integer жестко фиксирован.

Квартус сам разберется складывать целые числа, а потом просто переведет их в std_logic_vector нужной нам размерности, лишнее уберет...

Просинтезируйте (просто отдельным проектом только butterfly_complex.vhd) и посмотрите в RTL Viewer во что превращается ваш код. Проанализируйте, во что Квартус его превратил.

Если вынести за процесс конвертацию в integer? то синтезирует следующее:

[Sefo]

В том то и дело, что Квартус плохо разобрался как сложить числа. Посмотрите внимательно, чтобы сложить 4 числа нужно всего 3 сумматора, а Квартус вставил еще и четвертый. Спрашивается зачем? Можно предположить, что для округления, но попробуйте при симуляции задать на вход 1,1,1,0 или -2,-2,-2,-1. На одном из выходов (где чистое сложение) в первом случае будет 3/4 = 0.75, что при округлении должно дать 1, а у Вас будет 0, во втором случае -7/4 = -1.75, что при округлении должно давать -2, а у Вас будет -1. Спрашивается зачем нужны четвертые сумматоры, если дробная часть не округляется, а отбрасывается? "Честный" код без integer и без округлений после синтеза занимает в 1.6 раз меньше места.

Сообщение отредактировал Sefo - Mar 7 2009, 14:38

[Sefo]

Попробовали написать код без integer?

[ZED]

Попробовал, но не могу проверить (Quartus сломался) и не знаю, вообще так это делается или нет. Вот код:

Код

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;

entity butterfly_complex is
    generic (b_size: natural := 16);
    
    port(CLK: in std_logic;
         x1_re: in std_logic_vector(b_size - 1 downto 0);
         x1_im: in std_logic_vector(b_size - 1 downto 0);
         x2_re: in std_logic_vector(b_size - 1 downto 0);
         x2_im: in std_logic_vector(b_size - 1 downto 0);
         x3_re: in std_logic_vector(b_size - 1 downto 0);
         x3_im: in std_logic_vector(b_size - 1 downto 0);
         x4_re: in std_logic_vector(b_size - 1 downto 0);
         x4_im: in std_logic_vector(b_size - 1 downto 0);        
        
         y1_re: out std_logic_vector(b_size - 1 downto 0);
         y1_im: out std_logic_vector(b_size - 1 downto 0);
         y2_re: out std_logic_vector(b_size - 1 downto 0);
         y2_im: out std_logic_vector(b_size - 1 downto 0);
         y3_re: out std_logic_vector(b_size - 1 downto 0);
         y3_im: out std_logic_vector(b_size - 1 downto 0);
         y4_re: out std_logic_vector(b_size - 1 downto 0);
         y4_im: out std_logic_vector(b_size - 1 downto 0)        
        );
end entity butterfly_complex;


architecture beh_butter of butterfly_complex is
-- Сигналы для конвертации типов std_logic -> signed:
signal x1_re_sig : signed(b_size + 2 downto 0);
signal x1_im_sig : signed(b_size + 2 downto 0);
signal x2_re_sig : signed(b_size + 2 downto 0);
signal x2_im_sig : signed(b_size + 2 downto 0);
signal x3_re_sig : signed(b_size + 2 downto 0);
signal x3_im_sig : signed(b_size + 2 downto 0);
signal x4_re_sig : signed(b_size + 2 downto 0);
signal x4_im_sig : signed(b_size + 2 downto 0);

signal y1_re_sum : signed(b_size + 2 downto 0);
signal y1_im_sum : signed(b_size + 2 downto 0);
signal y2_re_sum : signed(b_size + 2 downto 0);
signal y2_im_sum : signed(b_size + 2 downto 0);
signal y3_re_sum : signed(b_size + 2 downto 0);
signal y3_im_sum : signed(b_size + 2 downto 0);
signal y4_re_sum : signed(b_size + 2 downto 0);
signal y4_im_sum : signed(b_size + 2 downto 0);

signal y1_re_sig : signed(b_size - 1 downto 0);
signal y1_im_sig : signed(b_size - 1 downto 0);
signal y2_re_sig : signed(b_size - 1 downto 0);
signal y2_im_sig : signed(b_size - 1 downto 0);
signal y3_re_sig : signed(b_size - 1 downto 0);
signal y3_im_sig : signed(b_size - 1 downto 0);
signal y4_re_sig : signed(b_size - 1 downto 0);
signal y4_im_sig : signed(b_size - 1 downto 0);

begin
        x1_re_sig <= resize(SIGNED(x1_re), b_size + 3);
        x1_im_sig <= resize(SIGNED(x1_im), b_size + 3);
        x2_re_sig <= resize(SIGNED(x2_re), b_size + 3);
        x2_im_sig <= resize(SIGNED(x2_im), b_size + 3);
        x3_re_sig <= resize(SIGNED(x3_re), b_size + 3);
        x3_im_sig <= resize(SIGNED(x3_im), b_size + 3);
        x4_re_sig <= resize(SIGNED(x4_re), b_size + 3);
        x4_im_sig <= resize(SIGNED(x4_im), b_size + 3);
        
        -- Вычисление y1_re:
        y1_re_sum <= x1_re_sig + x2_re_sig + x3_re_sig + x4_re_sig + "0000000000000000100";
        
        -- Вычисление y1_im:
        y1_im_sum <= x1_im_sig + x2_im_sig + x3_im_sig + x4_im_sig + "0000000000000000100";

        -- Вычисление y2_re:
        y2_re_sum <= x1_re_sig + x2_im_sig - x3_re_sig - x4_im_sig + "0000000000000000100";

        -- Вычисление y2_im:
        y2_im_sum <= x1_im_sig - x2_re_sig - x3_im_sig + x4_re_sig + "0000000000000000100";

        -- Вычисление y3_re:
        y3_re_sum <= x1_re_sig - x2_re_sig + x3_re_sig - x4_re_sig + "0000000000000000100";

        -- Вычисление y3_im:
        y3_im_sum <= x1_im_sig - x2_im_sig + x3_im_sig - x4_im_sig + "0000000000000000100";

        -- Вычисление y4_re:
        y4_re_sum <= x1_re_sig - x2_im_sig - x3_re_sig + x4_im_sig + "0000000000000000100";

        -- Вычисление y4_im:
        y4_im_sum <= x1_im_sig + x2_re_sig - x3_im_sig - x4_re_sig + "0000000000000000100";
        
        y1_re_sig(b_size - 1 downto 0) <= y1_re_sum(b_size + 2 downto 3);
        y1_im_sig(b_size - 1 downto 0) <= y1_im_sum(b_size + 2 downto 3);
        y2_re_sig(b_size - 1 downto 0) <= y2_re_sum(b_size + 2 downto 3);
        y2_im_sig(b_size - 1 downto 0) <= y2_im_sum(b_size + 2 downto 3);
        y3_re_sig(b_size - 1 downto 0) <= y3_re_sum(b_size + 2 downto 3);
        y3_im_sig(b_size - 1 downto 0) <= y3_im_sum(b_size + 2 downto 3);
        y4_re_sig(b_size - 1 downto 0) <= y4_re_sum(b_size + 2 downto 3);
        y4_im_sig(b_size - 1 downto 0) <= y4_im_sum(b_size + 2 downto 3);
        

process (CLK)
begin
    if (rising_edge(CLK)) then

        -- Вычисление y1_re:
        
        y1_re_sum <= CONV_STD_LOGIC_VECTOR(y1_re_sig, b_size);

        -- Вычисление y1_im:
        y1_im_sum <= CONV_STD_LOGIC_VECTOR(y1_im_sig, b_size);

        -- Вычисление y2_re:
        y2_re_sum <= CONV_STD_LOGIC_VECTOR(y2_re_sig, b_size);

        -- Вычисление y2_im:
        y2_im_sum <= CONV_STD_LOGIC_VECTOR(y2_im_sig, b_size);

        -- Вычисление y3_re:
        y3_re_sum <= CONV_STD_LOGIC_VECTOR(y3_re_sig, b_size);

        -- Вычисление y3_im:
        y3_im_sum <= CONV_STD_LOGIC_VECTOR(y3_im_sig, b_size);

        -- Вычисление y4_re:
        y4_re_sum <= CONV_STD_LOGIC_VECTOR(y4_re_sig, b_size);

        -- Вычисление y4_im:
        y4_im_sum <= CONV_STD_LOGIC_VECTOR(y4_im_sig, b_size);

    end if;
end process;

end beh_butter;

Сообщение отредактировал ZED - Mar 8 2009, 10:49

[Sefo]

Кроме того, что код оказался не компилируем, различных преобразований, все же, многовато . С разрядностью тоже переборщили, хотя и всего на 1 разряд. По этой же причине (неправильная разрядность), видимо, Вы для округления прибавляете 4, вместо 2 - это приведет к неправильным вычислениям.

Разберемся с разрядностью. При сложении 4 чисел самое большое | маленькое, что мы можем получить это max(x)*4 | min(x)*4. Поскольку умножение на 4 есть не что иное как сдвиг влево на 2 разряда, то

1) переполнение при любых числах на входе БПФ не может превысить 2 разряда.
2) в обоих крайних случаях мы получим "00" в двух младших разрядах.

Из 1) и 2) следует, что разрядность сумы должна быть только лишь на 2 разряда больше, чем данные и для округления перед делением на 4 мы можем прибавить "000000000000000010" (т.е. 2) не опасаясь переполнения.

Для бабочки достаточно использования только std_logic_vector. Кстати, лучше нумеровать точки с 0. Вот код.

CODE

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

entity butterfly_complex is
generic (b_size: natural := 16);

port(CLK: in std_logic;
x0_re: in std_logic_vector(b_size-1 downto 0);
x0_im: in std_logic_vector(b_size-1 downto 0);
x1_re: in std_logic_vector(b_size-1 downto 0);
x1_im: in std_logic_vector(b_size-1 downto 0);
x2_re: in std_logic_vector(b_size-1 downto 0);
x2_im: in std_logic_vector(b_size-1 downto 0);
x3_re: in std_logic_vector(b_size-1 downto 0);
x3_im: in std_logic_vector(b_size-1 downto 0);

y0_re: out std_logic_vector(b_size-1 downto 0);
y0_im: out std_logic_vector(b_size-1 downto 0);
y1_re: out std_logic_vector(b_size-1 downto 0);
y1_im: out std_logic_vector(b_size-1 downto 0);
y2_re: out std_logic_vector(b_size-1 downto 0);
y2_im: out std_logic_vector(b_size-1 downto 0);
y3_re: out std_logic_vector(b_size-1 downto 0);
y3_im: out std_logic_vector(b_size-1 downto 0)
);
end entity butterfly_complex;

architecture beh_butter of butterfly_complex is

signal x0_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x0_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x1_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x1_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x2_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x2_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x3_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x3_im_sig : std_logic_vector(b_size-1 + 2 downto 0);

signal y0_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y0_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y1_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y1_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y2_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y2_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y3_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y3_im_sig : std_logic_vector(b_size-1 + 2 downto 0);

Begin --=======================================================

x0_re_sig <= (1 downto 0 => x0_re(b_size-1)) & x0_re;
x0_im_sig <= (1 downto 0 => x0_im(b_size-1)) & x0_im;
x1_re_sig <= (1 downto 0 => x1_re(b_size-1)) & x1_re;
x1_im_sig <= (1 downto 0 => x1_im(b_size-1)) & x1_im;
x2_re_sig <= (1 downto 0 => x2_re(b_size-1)) & x2_re;
x2_im_sig <= (1 downto 0 => x2_im(b_size-1)) & x2_im;
x3_re_sig <= (1 downto 0 => x3_re(b_size-1)) & x3_re;
x3_im_sig <= (1 downto 0 => x3_im(b_size-1)) & x3_im;

--------------------------------------

-- Вычисление y0
y0_re_sig <= x0_re_sig + x1_re_sig + x2_re_sig + x3_re_sig + 2;
y0_im_sig <= x0_im_sig + x1_im_sig + x2_im_sig + x3_im_sig + 2;

-- Вычисление y1
y1_re_sig <= x0_re_sig + x1_im_sig - x2_re_sig - x3_im_sig + 2;
y1_im_sig <= x0_im_sig - x1_re_sig - x2_im_sig + x3_re_sig + 2;

-- Вычисление y2
y2_re_sig <= x0_re_sig - x1_re_sig + x2_re_sig - x3_re_sig + 2;
y2_im_sig <= x0_im_sig - x1_im_sig + x2_im_sig - x3_im_sig + 2;

-- Вычисление y3
y3_re_sig <= x0_re_sig - x1_im_sig - x2_re_sig + x3_im_sig + 2;
y3_im_sig <= x0_im_sig + x1_re_sig - x2_im_sig - x3_re_sig + 2;

--------------------------------------

process (CLK)
begin
if (rising_edge(CLK)) then

y0_re <= y0_re_sig(b_size-1 + 2 downto 2);
y0_im <= y0_im_sig(b_size-1 + 2 downto 2);
y1_re <= y1_re_sig(b_size-1 + 2 downto 2);
y1_im <= y1_im_sig(b_size-1 + 2 downto 2);
y2_re <= y2_re_sig(b_size-1 + 2 downto 2);
y2_im <= y2_im_sig(b_size-1 + 2 downto 2);
y3_re <= y3_re_sig(b_size-1 + 2 downto 2);
y3_im <= y3_im_sig(b_size-1 + 2 downto 2);

end if;
end process;


end beh_butter;

Теперь идем дальше. 2-х точечная бабочка это всего лишь A+B и A-B. Как несложно видеть и то и другое со всеми входными данными и в разных комбинациях у нас есть в формулах 4-х Т.Б. (недаром же ее можновычислить через 2-х Т.Б. ). Учитывая, что у нас из памяти за такт вычитывается по 4 точки, то нам неплохо бы "выжать" из формул 4-х Т.Б. две 2-х Т.Б. В качестве входа для первой 2-х Т.Б. возьмем Х0 и Х1, а в для второй Х2 и Х3. Разумеется, на вход бабочки нужно добавить сигнал управления типом бабочки, а выходные регистры должны должны защелкивать соответствующий результат.

Дерзайте.

[ZED]

Пока на ум пришло только это:

Код

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

entity butterfly_complex is
generic (b_size: natural := 16);

port(CLK: in std_logic;
x0_re: in std_logic_vector(b_size-1 downto 0);
x0_im: in std_logic_vector(b_size-1 downto 0);
x1_re: in std_logic_vector(b_size-1 downto 0);
x1_im: in std_logic_vector(b_size-1 downto 0);
x2_re: in std_logic_vector(b_size-1 downto 0);
x2_im: in std_logic_vector(b_size-1 downto 0);
x3_re: in std_logic_vector(b_size-1 downto 0);
x3_im: in std_logic_vector(b_size-1 downto 0);

switch: in std_logic_vector;

y0_re: out std_logic_vector(b_size-1 downto 0);
y0_im: out std_logic_vector(b_size-1 downto 0);
y1_re: out std_logic_vector(b_size-1 downto 0);
y1_im: out std_logic_vector(b_size-1 downto 0);
y2_re: out std_logic_vector(b_size-1 downto 0);
y2_im: out std_logic_vector(b_size-1 downto 0);
y3_re: out std_logic_vector(b_size-1 downto 0);
y3_im: out std_logic_vector(b_size-1 downto 0)
);
end entity butterfly_complex;

architecture beh_butter of butterfly_complex is

signal x0_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x0_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x1_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x1_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x2_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x2_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x3_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x3_im_sig : std_logic_vector(b_size-1 + 2 downto 0);

signal y0_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y0_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y1_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y1_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y2_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y2_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y3_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y3_im_sig : std_logic_vector(b_size-1 + 2 downto 0);

Begin --=======================================================

x0_re_sig <= (1 downto 0 => x0_re(b_size-1)) & x0_re;
x0_im_sig <= (1 downto 0 => x0_im(b_size-1)) & x0_im;
x1_re_sig <= (1 downto 0 => x1_re(b_size-1)) & x1_re;
x1_im_sig <= (1 downto 0 => x1_im(b_size-1)) & x1_im;
x2_re_sig <= (1 downto 0 => x2_re(b_size-1)) & x2_re;
x2_im_sig <= (1 downto 0 => x2_im(b_size-1)) & x2_im;
x3_re_sig <= (1 downto 0 => x3_re(b_size-1)) & x3_re;
x3_im_sig <= (1 downto 0 => x3_im(b_size-1)) & x3_im;

--------------------------------------
if (switch = '0') then

-- Вычисление y0
y0_re_sig <= x0_re_sig + x1_re_sig + x2_re_sig + x3_re_sig + 2;
y0_im_sig <= x0_im_sig + x1_im_sig + x2_im_sig + x3_im_sig + 2;

-- Вычисление y1
y1_re_sig <= x0_re_sig + x1_im_sig - x2_re_sig - x3_im_sig + 2;
y1_im_sig <= x0_im_sig - x1_re_sig - x2_im_sig + x3_re_sig + 2;

-- Вычисление y2
y2_re_sig <= x0_re_sig - x1_re_sig + x2_re_sig - x3_re_sig + 2;
y2_im_sig <= x0_im_sig - x1_im_sig + x2_im_sig - x3_im_sig + 2;

-- Вычисление y3
y3_re_sig <= x0_re_sig - x1_im_sig - x2_re_sig + x3_im_sig + 2;
y3_im_sig <= x0_im_sig + x1_re_sig - x2_im_sig - x3_re_sig + 2;

--------------------------------------
else

-- Вычисление y0
y0_re_sig <= x0_re_sig + x1_re_sig + 1;
y0_im_sig <= x0_im_sig + x1_im_sig + 1;

-- Вычисление y1
y1_re_sig <= x0_re_sig - x1_im_sig + 1;
y1_im_sig <= x0_im_sig - x1_re_sig + 1;

-- Вычисление y2
y2_re_sig <= x2_re_sig + x3_re_sig + 1;
y2_im_sig <= x2_im_sig + x3_im_sig + 1;

-- Вычисление y3
y3_re_sig <= x2_re_sig - x3_im_sig + 1;
y3_im_sig <= x2_im_sig - x3_re_sig + 1;


process (CLK)
begin
if (rising_edge(CLK)) then
if (switch = '0') then
y0_re <= y0_re_sig(b_size-1 + 2 downto 2);
y0_im <= y0_im_sig(b_size-1 + 2 downto 2);
y1_re <= y1_re_sig(b_size-1 + 2 downto 2);
y1_im <= y1_im_sig(b_size-1 + 2 downto 2);
y2_re <= y2_re_sig(b_size-1 + 2 downto 2);
y2_im <= y2_im_sig(b_size-1 + 2 downto 2);
y3_re <= y3_re_sig(b_size-1 + 2 downto 2);
y3_im <= y3_im_sig(b_size-1 + 2 downto 2);
else
y0_re <= y0_re_sig(b_size-1 + 1 downto 1);
y0_im <= y0_im_sig(b_size-1 + 1 downto 1);
y1_re <= y1_re_sig(b_size-1 + 1 downto 1);
y1_im <= y1_im_sig(b_size-1 + 1 downto 1);
y2_re <= y2_re_sig(b_size-1 + 1 downto 1);
y2_im <= y2_im_sig(b_size-1 + 1 downto 1);
y3_re <= y3_re_sig(b_size-1 + 1 downto 1);
y3_im <= y3_im_sig(b_size-1 + 1 downto 2);
end if;
end process;


end beh_butter;

Сообщение отредактировал ZED - Mar 8 2009, 20:22

[Sefo]

"if" не может быть использован вне процесса. Этот код не компилируем.

Вне процесса можно A <= B when x = y else C;

Исправляйте. Либо поместите в процесс, либо примените конструкцию с when.

Еще однобитовый switch не может быть std_logic_vector Максимум std_logic.

Сообщение отредактировал Sefo - Mar 8 2009, 20:55

[ZED]

"if" не может быть использован вне процесса. Этот код не компилируем.

Да точно, забыл...

Вне процесса можно A <= B when x = y else C;

Да, но нескольким значениям значений не присвоишь, а жаль...

Исправляйте. Либо поместите в процесс, либо примените конструкцию с when.

Выход только поместить в процесс...

Еще однобитовый switch не может быть std_logic_vector smile.gif Максимум std_logic.

CTL+C CTL+V =)) Исправил, просинтезировать нет возможности...

Код

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

entity butterfly_complex is
generic (b_size: natural := 16);

port(CLK: in std_logic;
x0_re: in std_logic_vector(b_size-1 downto 0);
x0_im: in std_logic_vector(b_size-1 downto 0);
x1_re: in std_logic_vector(b_size-1 downto 0);
x1_im: in std_logic_vector(b_size-1 downto 0);
x2_re: in std_logic_vector(b_size-1 downto 0);
x2_im: in std_logic_vector(b_size-1 downto 0);
x3_re: in std_logic_vector(b_size-1 downto 0);
x3_im: in std_logic_vector(b_size-1 downto 0);

switch: in std_logic;

y0_re: out std_logic_vector(b_size-1 downto 0);
y0_im: out std_logic_vector(b_size-1 downto 0);
y1_re: out std_logic_vector(b_size-1 downto 0);
y1_im: out std_logic_vector(b_size-1 downto 0);
y2_re: out std_logic_vector(b_size-1 downto 0);
y2_im: out std_logic_vector(b_size-1 downto 0);
y3_re: out std_logic_vector(b_size-1 downto 0);
y3_im: out std_logic_vector(b_size-1 downto 0)
);
end entity butterfly_complex;

architecture beh_butter of butterfly_complex is

signal x0_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x0_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x1_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x1_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x2_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x2_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x3_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal x3_im_sig : std_logic_vector(b_size-1 + 2 downto 0);

signal y0_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y0_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y1_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y1_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y2_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y2_im_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y3_re_sig : std_logic_vector(b_size-1 + 2 downto 0);
signal y3_im_sig : std_logic_vector(b_size-1 + 2 downto 0);

Begin --=======================================================

x0_re_sig <= (1 downto 0 => x0_re(b_size-1)) & x0_re;
x0_im_sig <= (1 downto 0 => x0_im(b_size-1)) & x0_im;
x1_re_sig <= (1 downto 0 => x1_re(b_size-1)) & x1_re;
x1_im_sig <= (1 downto 0 => x1_im(b_size-1)) & x1_im;
x2_re_sig <= (1 downto 0 => x2_re(b_size-1)) & x2_re;
x2_im_sig <= (1 downto 0 => x2_im(b_size-1)) & x2_im;
x3_re_sig <= (1 downto 0 => x3_re(b_size-1)) & x3_re;
x3_im_sig <= (1 downto 0 => x3_im(b_size-1)) & x3_im;

--------------------------------------

process (CLK)
begin
if (rising_edge(CLK)) then
if (switch = '0') then

-- Вычисление y0
y0_re_sig <= x0_re_sig + x1_re_sig + x2_re_sig + x3_re_sig + 2;
y0_im_sig <= x0_im_sig + x1_im_sig + x2_im_sig + x3_im_sig + 2;

-- Вычисление y1
y1_re_sig <= x0_re_sig + x1_im_sig - x2_re_sig - x3_im_sig + 2;
y1_im_sig <= x0_im_sig - x1_re_sig - x2_im_sig + x3_re_sig + 2;

-- Вычисление y2
y2_re_sig <= x0_re_sig - x1_re_sig + x2_re_sig - x3_re_sig + 2;
y2_im_sig <= x0_im_sig - x1_im_sig + x2_im_sig - x3_im_sig + 2;

-- Вычисление y3
y3_re_sig <= x0_re_sig - x1_im_sig - x2_re_sig + x3_im_sig + 2;
y3_im_sig <= x0_im_sig + x1_re_sig - x2_im_sig - x3_re_sig + 2;

y0_re <= y0_re_sig(b_size-1 + 2 downto 2);
y0_im <= y0_im_sig(b_size-1 + 2 downto 2);
y1_re <= y1_re_sig(b_size-1 + 2 downto 2);
y1_im <= y1_im_sig(b_size-1 + 2 downto 2);
y2_re <= y2_re_sig(b_size-1 + 2 downto 2);
y2_im <= y2_im_sig(b_size-1 + 2 downto 2);
y3_re <= y3_re_sig(b_size-1 + 2 downto 2);
y3_im <= y3_im_sig(b_size-1 + 2 downto 2);

else

-- Вычисление y0
y0_re_sig <= x0_re_sig + x1_re_sig + 1;
y0_im_sig <= x0_im_sig + x1_im_sig + 1;

-- Вычисление y1
y1_re_sig <= x0_re_sig - x1_im_sig + 1;
y1_im_sig <= x0_im_sig - x1_re_sig + 1;

-- Вычисление y2
y2_re_sig <= x2_re_sig + x3_re_sig + 1;
y2_im_sig <= x2_im_sig + x3_im_sig + 1;

-- Вычисление y3
y3_re_sig <= x2_re_sig - x3_im_sig + 1;
y3_im_sig <= x2_im_sig - x3_re_sig + 1;

y0_re <= y0_re_sig(b_size-1 + 1 downto 1);
y0_im <= y0_im_sig(b_size-1 + 1 downto 1);
y1_re <= y1_re_sig(b_size-1 + 1 downto 1);
y1_im <= y1_im_sig(b_size-1 + 1 downto 1);
y2_re <= y2_re_sig(b_size-1 + 1 downto 1);
y2_im <= y2_im_sig(b_size-1 + 1 downto 1);
y3_re <= y3_re_sig(b_size-1 + 1 downto 1);
y3_im <= y3_im_sig(b_size-1 + 1 downto 2);
end if;
end if;
end process;


end beh_butter;

[Sefo]

Когда у Вас будет возможность просинтезировать код? Потому что мы подошли к самому интересному - во что Квартус превращает наш код и как его заставить сделать то, что нам нужно.

Попробуйте просинтезировать Квартусом простое выражение (в отдельном проекте) R = A+B+1 (или R = A+B+'1'), где R,A и B есть std_logic_vector(15 downto 0) и посмотрите в RTL Viewer что получилось.

Как Вы думаете, что должно было получиться, если бы Квартус был бы "умнее"? Какую стандартную операцию представляет из себя выражение A+B+1?

[ZED]

Квартус синтезирует 2 сумматора, на вход одного из которых подана единица. Операция должна быть округлением...

[Sefo]

Вот это-то и плохо. У нас обычное суммирование с переносом. A+B+carry - это полный сумматор. Это мы его используем для округления, а еще такой сумматор используется для вычисления суммы чисел на нескольких полных сумматорах, когда разрядность самих чисел больше разрядности сумматора. Самое обидное, что ячейки ПЛИС все это позволяют. Если запустить Квартусовский Мегавизард, то Вы найдете там сумматор со входом переноса, который при синтезе будет занимать ровно столько ячеек, сколько разрядов и ни одной больше. А на наш код он ставит аж 2 сумматора!

К сожалению, Квартус не отличается хорошей оптимизацией математических выражеий. Если он видит два '+' он ставит 2 сумматора.

Есть идеи, как его заставить реализовать A+B+1 на одном сумматоре в VHDL, не прибегая к использованию его мегафункций?

Сообщение отредактировал Sefo - Mar 9 2009, 12:27

[ZED]

Если только самому как-то описывать полный сумматор, а так идей нету.

[Sefo]

Извиняюсь за длительную паузу. Прием очень простой. Если обоим операндам приписать по одному разряду справа равному '1', то при сложении неизбежно образуется перенос, который сложится со младшим разрядом (точнее, бывшим младшим разрядом) суммы, а т.к. результат самого сложения двух констант, равных '1' никогда использоваться не будет, то Квартус в процессе оптимизации эту ячейку удалит. Да даже если и не удалит, то такой "довесок" в n раз меньше, чем второй сумматор на n разрядов.

signal A : std_logic_vector(n-1 downto 0);
signal B : std_logic_vector(n-1 downto 0);

signal SUM : std_logic_vector(n-1 downto 0); -- SUM = (A + B + 1);

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

signal S std_logic_vector(n downto 0);

Тогда

S <= (A & '1') + (B & '1');

SUM <= S(n downto 1);

Кстати, к A+B+m, где m > 1 описанный прием уже не применить.

Предлагаю Вам с этим немного поэкспериментировать на досуге.

Идем дальше. К сожалению, все вышесказанное (не только конкретно в этом сообщении) про сложение не работает для вычитания. Для A-B+1 придется ставить 2 сумматора.
Кроме того, в отличие от A+B, A-B уже не гарантирует '0' в младшем разряде в крайних случаях. Для сложения крайние случаи это когда оба слагаемых либо максимальны, либо минимальны, а для вычитания – когда одна переменная имеет максимальное значение, а другая минимальное. А поскольку '0' не гарантирован, то при отбрасывании младшего разряда при сдвиге вправо ничего страшного не произойдет, а вот при округлении (т.е. прибавлении 1 перед сдвигом) результат может переполнится больше чем на 1 разряд по сравнению с разрядностью исходных переменных.
Пример:
( (-32768) – (32767) + 1 ) >> 1 = (-65535 + 1) >> 1 = -65534 >> 1 = -32767 все в порядке - разность переполнилась на один "законный" разряд, после сложения переполнения не произошло и после деления на 2 все вернулось обратно к 16-ти разрядам.
Теперь другой пример:
( (32767) – (-32768) + 1 ) >> 1 = (65535 + 1) >> 1 = -65536 >> 1 = -32768 фигня получилась - разность переполнилась на один "законный" разряд, а после добавления 1 переполнилась еще раз, превратившись в отрицательное число.
Такое поведение вычитания обусловлено как раз несимметричностью дополнительного кода – модуль максимального числа на 1 меньше модуля минимального. При вычитании, так скажем, самого отрицательного числа оно меняет знак, станивится положительным и... для его представления нужно уже на 1 разряд больше т.к. оно становится всего на единицу больше максимального положительного числа.

Какие отсюда следуют выводы?

1) избавиться от лишних сумматоров нам удасться лишь для y0_re и y0_im (для случая 2-х Т.Б. еще и y2), где у нас сплошное суммирование. С этим должно быть все понятно.

2) при вычислении y1,2,3 у нас может возникнуть переполнение. Тут нужно учесть, что локально увеличить разрядность мы не можем т.к. это переполнение не устраняется делением на 4 или 2.

Есть 2 варианта:

Первый, увеличить разрядность данных повсеместно на 1 и расширить диапазон значений только на нехватающую 1 т.е. 16-ти разрядные данные сделать 17-ти разрядными, а диапазон сделать от -32768 до +32768. Этот способ очень прост т.к. достаточно 16-ти разрядные данные АЦП расширить знаком до 17-ти разрядных и все.

Второй, это на выходе из АЦП заменять -32768 на 32767. Не очень "честно", но если сохранять разрядность, то "честно" все равно не получится, а резать в бабочке гораздо более затратно по ресурсам ПЛИС.

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

Что касается переполнения, то выбирайте, увеличим разрядность или срежем на выходе АЦП?

Вопросы есть?

[ZED]

Прошу прощения, что долго не отвечал, просто по учебе загрузили, надеюсь все к среде разрулить и вплотную заняться делом!

[Sefo]

Ну как, разрулили?

[ZED]

Да, спасибо, разрулил более менее, надеюсь еще какое-то время меня трогать не будут=))

Да, вопросы есть:

1. Не совсем понятно , что значит "локально увеличить разрядность". Это имеется ввиду в ПЛИС resize?

2. Почему бы в ПЛИС не сделать так:

Код

signal A : std_logic_vector(n-1 downto 0);
signal B : std_logic_vector(n-1 downto 0);
signal SUM_buf : std_logic_vector(n downto 0);
signal SUM : std_logic_vector(n downto 0);

SUM_buf <= resize(A, n+1) -  resize(B, n+1)
SUM <= SUM_buf(n downto 1);

Сообщение отредактировал ZED - Mar 18 2009, 17:19

[Sefo]

1) Локально, это имеется ввиду внутри бабочки. В случае (A+B+C+D)/4 с округлением (т.е. (A+B+C+D+2) >> 2) мы можем (и делаем) объявить внутри бабочки сигналы A_ B_ C_ D_ с разрядностью на 2 больше, чем A,B,C,D. Складываем их, прибавляем 2 (для округления) и отбросываем 2 младших разряда (т.е. /4). В этом случае, выполнив все необходимые операции, мы снова возвращаемся к разрядности такой же как и у A,B,C,D. У нас на входе разрядность n, внутри бабочки разрядность n+2, а на выходе опять n. И при этом мы нигде ничего не реряем. При наличие вычитания, если мы не будем округлять, а просто отбрасывать 2 младших разряда, то мы тоже ничего не потеряем и разрядность результата будет такая же как и разрядность входных данных. Но при наличие вычитания и желания проделать операции с округлением результата мы в некоторых случаях сможем получить результат (именно конечный результат), для представления которого нам не хватит разрядности такой же как и у входных данных - нам потребуется на один разряд больше. (см пример в пред. сообщении) Т.е. выход будет на один разряд больше ==> выход умножителей придется сделать на 1 разряд больше ==> разрядность памяти придется увеличить на 1 разряд ==> вход бабочки тоже увеличится на 1 разряд - круг замкнулся т.к. наши данные во время вычисления БПФ "гуляют" по кругу.

2)Так как Вы написали - это (A-/2 без округления (т.е. (A->>1), а Вы в бабочке округляете (т.е. (A-B+1)>>1). Я же ведь даже конкретный пример привел - просимулируйте.


Теперь понятно?

На всякий случай повторю - не делай мы в бабочке округления при делении на 4 никаких проблем бы не было.

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

[Azatot]

Господа,так ведь же есть уже готовые БПФ ядра и у Xilinx, и у Altera. Лично пользуюсь Xilinx ядром, вроде, не плохо получается. В своем проекте мы вешаем на вход АЦП и потоком гоняем 1024 точки.

[Sefo]

В данном случае преследуются учебные цели. Понятно, что для работы, если есть готовое IP и, к тому же, бесплатно, то глупо им не воспользоваться. Но для ПЛИС довольно много полезных и бесплатных IP, вроде БПФ, включено в состав средств разработки, а если ASIC надо делать? Увы, для ASIC IP задорма никто не дает. Я вот, однажды делал БПФ для ASIC. Там нужна была небольшая постобработка результатов их анализ и формирование выборок из спектра по заданным критериям - большую чать этого довеска удалось встроить прямо в последнюю стадию БПФ и задействовав вычислительные ресурсы самого БПФ. Получился существенный выигрыш и по быстродействию и площадь здорово сэкономили. С покупным IP так удачно не получилось бы.

В общем, надо пользоваться готовым IP там, где это можно, но хороший инженер должен уметь реализовать это IP и сам.

Так что я очень поддерживаю желание ZEDa собрать свой собственный "велосипед" свомим руками.

[ZED]

Ну я так и имел ввиду:

Код

signal A : std_logic_vector(n-1 downto 0);
signal B : std_logic_vector(n-1 downto 0);
signal SUM_buf : std_logic_vector(n downto 0);
signal SUM : std_logic_vector(n downto 0);

SUM_buf <= resize(A, n+1) -  resize(B, n+1) + '1'
SUM <= SUM_buf(n downto 1);

resize расширяет число знаковым разрядом, соответственно при сложении/вычитании 4 отсчетов resize(OTSCHOT, n+2), а потом отбрасываем.

Понятно, спасибо, в том числе и за поддержку.

[Sefo]

Теперь мне не очень понятно, поняли ли Вы меня правильно.

Код

CODE

signal A : std_logic_vector(n-1 downto 0);
signal B : std_logic_vector(n-1 downto 0);
signal SUM_buf : std_logic_vector(n downto 0);
signal SUM : std_logic_vector(n-1 downto 0);

SUM_buf <= resize(A, n+1) - resize(B, n+1) + '1'
SUM <= SUM_buf(n downto 1);

в случае A = (2^n)-1 и B = -(2^n) даст неверный результат.

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

Сообщение отредактировал Sefo - Mar 19 2009, 20:00

[ZED]

Чего-то не симулируется, квартус лагает, вот проект:

Код

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

entity summator is
    generic (b_size: natural := 16
             );
    
    port(A: in std_logic_vector(b_size - 1 downto 0);
         B: in std_logic_vector(b_size - 1 downto 0);
         SUM: out std_logic_vector(b_size - 1 downto 0)
        );
end entity summator;


architecture beh_summator of summator is

signal A_sig : std_logic_vector(b_size downto 0);
signal B_sig : std_logic_vector(b_size downto 0);
signal SUM_buf : std_logic_vector(b_size downto 0);

begin
A_sig <= (0 => A(b_size-1)) & A;
B_sig <= (0 => B(b_size-1)) & B;
SUM_buf <= A_sig - B_sig + '1';
SUM <= SUM_buf(b_size downto 1);

end beh_summator;

[Sefo]

Что значит не симулируется? Под проектом я понимаю все квартусовские файлы.

[ZED]

Что значит не симулируется?

Временная диаграмма не работает - выдает одни иксы: XXXXXXX и т.д. Что-то с Квартусом или компом, я его стабильно раз в неделю переставляю. А может и я что-то не так делаю...
Проект прикрепляю.

Прикрепленные файлы

 summator.rar ( 440.25 килобайт ) Кол-во скачиваний: 84

 

[Sefo]

Вы просто не тот файл смотрите. Результаты симуляции лежат в каталоге db\ и называется файл summator.sim.vwf. Вообще-то этот файл Квартус Вам должен был сам показать по окончании симуляции в одном из окон репорта. Если Вы в этом файле измените формат отображения для SUM с Binary на Signed Decimal, то Вы увидите, что результат = -32768, что неверно.

[sazh]

Временная диаграмма не работает - выдает одни иксы: XXXXXXX и т.д. Что-то с Квартусом или компом, я его стабильно раз в неделю переставляю. А может и я что-то не так делаю...
Проект прикрепляю.

Если я что то и переставляю, так это новую версию Квартуса. Чего и вам желаю.
А выдавать неопределенности (при функционале) он может, если только галочка не стоит на опции Overwrite.....
Иначе cмотрите в опции report.
Что касается Вашего сумматора, ничего сказать не могу. Потому что текст не понимаю (понятно только, что он не правильно работает. А в своих библиотеках сами копайтесь.

Вы просто не тот файл смотрите. Результаты симуляции лежат в каталоге db\ и называется файл summator.sim.vwf. Вообще-то этот файл Квартус Вам должен был сам показать по окончании симуляции в одном из окон репорта. Если Вы в этом файле измените формат отображения для SUM с Binary на Signed Decimal, то Вы увидите, что результат = -32768, что неверно.

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

[ZED]

Вот, что у меня получилось:

Прикрепленные файлы

 summator.rar ( 421.59 килобайт ) Кол-во скачиваний: 79

 

[Sefo]

Если я что то и переставляю, так это новую версию Квартуса. Чего и вам желаю.
А выдавать неопределенности (при функционале) он может, если только галочка не стоит на опции Overwrite.....
Иначе cмотрите в опции report.
Что касается Вашего сумматора, ничего сказать не могу. Потому что текст не понимаю (понятно только, что он не правильно работает. А в своих библиотеках сами копайтесь.

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

А можно поинтересоваться, с чего вдруг вы тут это "ляпнули"? Как-то очень не впопад

Что касается Вашего сумматора, ничего сказать не могу. Потому что текст не понимаю (понятно только, что он не правильно работает. А в своих библиотеках сами копайтесь.

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

Интересно, в каком семестре мы подойдем к изучению умножителей.

Мне интересно, а Вам-то какая разница? Да, с бабочкой (точнее с ее вычитателями) несколько затянулось, но ведь задача стоит разобраться, а не как можно скорее получить код БПФ.

Иль дайте есть, иль ешьте сами.

Что Вы имеете ввиду?

--------- Для всех кто читает эту тему ----------

Еще раз повторяю, эта тема преследует исключительно учебные цели.

Я буду искренне благодарен тем, кто может дополнить написанное чем-то полезным, но...

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

Вот, что у меня получилось:

Теперь Вам понятно, почему при (A+B +1) >> 1 результат всегда занимает столько же разрядов, сколько операнды, а при (A-B+1) >> 1 результат может потребовать для хранения на один разряд больше, чем сами операнды?

На всякий случай привожу правильный код вычитателя.

CODE

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

entity subtractor is
generic (b_size: natural := 16
);

port(A: in std_logic_vector(b_size - 1 downto 0);
B: in std_logic_vector(b_size - 1 downto 0);
SUM: out std_logic_vector(b_size downto 0)
);
end entity subtractor;


architecture beh_subtractor of subtractor is

signal A_sig : std_logic_vector(b_size + 1 downto 0);
signal B_sig : std_logic_vector(b_size + 1 downto 0);
signal SUM_buf : std_logic_vector(b_size + 1 downto 0);

begin
A_sig <= (1 downto 0 => A(b_size-1)) & A;
B_sig <= (1 downto 0 => B(b_size-1)) & B;
SUM_buf <= A_sig - B_sig + '1';
SUM <= SUM_buf(b_size + 1 downto 1);

end beh_subtractor;

Сообщение отредактировал Sefo - Mar 22 2009, 11:48

[ZED]

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

[Sefo]

Все-таки, Вы не поняли.

Округление мы уже произвели. Собственно, из-за него и приходится увеличить разрадность сигнала для хранения результата на 1.

Вы в каком городе живете?

[ZED]

В Москве.
Просто вы писали:

В случае (A+B+C+D)/4 с округлением (т.е. (A+B+C+D+2) >> 2) мы можем (и делаем) объявить внутри бабочки сигналы A_ B_ C_ D_ с разрядностью на 2 больше, чем A,B,C,D. Складываем их, прибавляем 2 (для округления) и отбросываем 2 младших разряда (т.е. /4). В этом случае, выполнив все необходимые операции, мы снова возвращаемся к разрядности такой же как и у A,B,C,D. У нас на входе разрядность n, внутри бабочки разрядность n+2, а на выходе опять n. И при этом мы нигде ничего не реряем.

Т.е. на выходе бабочки должна быть разрядность такая как и на входе.

Но тут же вы писали:

Но при наличие вычитания и желания проделать операции с округлением результата мы в некоторых случаях сможем получить результат (именно конечный результат), для представления которого нам не хватит разрядности такой же как и у входных данных - нам потребуется на один разряд больше. (см пример в пред. сообщении) Т.е. выход будет на один разряд больше ==> выход умножителей придется сделать на 1 разряд больше ==> разрядность памяти придется увеличить на 1 разряд ==> вход бабочки тоже увеличится на 1 разряд - круг замкнулся т.к. наши данные во время вычисления БПФ "гуляют" по кругу.

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

И возникает вопрос стоит ли округление таких затрат?

[Sefo]

Видимо, словами "круг замкнулся" я Вас запутал.

Разрядность бабочки у нас не будет увеличиваться на каждом этапе.

Я пытался объяснить, что при наличие вычитания в операциях бабочки с округлением потребует от нас повсеместного (т.е. в каждом блоке, но не на каждом этапе ! ) увеличения разрядности на 1 поскольку диапазон значений данных с АЦП от -32768 до +32767, а при вычислениях БПФ диапазон результатов будет от -32768 до +32768 ( независимо от этапа). Такой диапазон чисел для представления требует не 16, а 17 разрядов.

Забегая вперед, кроме бабочки, в умножителе, когда -32768 Вы умножите на -1.0, то получите +32768 - это число для представления требует опять таки 17 разрядов (как видите, даже если убрать округление в бабочке, то нам все равно не избежать этой проблемы в умножителях).

Из-за этого нам нужно либо исключить число -32768 из входного потока данных с АЦП (тогда при любых вычислениях БПФ мы никогда не получим +32768 - т.е. будем всегда иметь диапазон от -32767 до +32767) либо сделать 17-ти разрядные шины данных, чтобы по ним можно было бы "гонять" +32768.

Надеюсь, теперь все встало на свои места.

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

Сообщение отредактировал Sefo - Mar 22 2009, 15:52

[ZED]

Все вроде понял, т.е. мы сразу после АЦП добавляем знаковыми разрядами до 17 разрядов и гоним в паямть с 17 разрядными словами и уже работаем с 17 разрядными данными.

[Sefo]

Да.

Ура! Ттеперь можно перейти к умножителям.

Вы хотели на коэффициенты заложить 12 разрядов. У коэффициентов БПФ диапазон Re и Im частей от -1.0 до +1.0. Как Вы думаете, какое 12-ти разрядное число лучше поставить в соответствовие -1.0 и какое в соответствие +1.0? И почему?

Опыт бабочки должен Вам помочь.

[ZED]

1.0 это 2047

-1.0 это -2047

Чтобы не увеличивать разрядность:

Забегая вперед, кроме бабочки, в умножителе, когда -32768 Вы умножите на -1.0, то получите +32768 - это число для представления требует опять таки 17 разрядов (как видите, даже если убрать округление в бабочке, то нам все равно не избежать этой проблемы в умножителях).

[Sefo]

Давайте пока так начнем. Впроцессе реализации сами догадаетесь, почему это не самый лучший вариант. Хотя так тоже можно. Кстати, надеюсь, что написав

Чтобы не увеличивать разрядность

Вы имели ввиду разрядность коэффициентов.

Все данные с бабочки мы направим на блок комплексных умножителей. В этом блоке будет 4 умножителя, один из которых всегда умножает на (1.0 + j0). Такой подход удобен т.к. все данные (все 4 точки) идут единым путем и каждый блок нашего БПФ сам заботится о том, чтобы одни данные не "отстали"/"опередили" другие.

Итак:

1) жду от Вас код блока комплексных умножителей

2) код самого комплексного умножителя.

[ZED]

Вот комплексный перемножитель, не знаю правильно ли я все сделал, но вроде умножает=))

Прикрепленные файлы

 complex_multiplier.rar ( 418.56 килобайт ) Кол-во скачиваний: 102

 

[Sefo]

Хорошо. Код внимательно посмотрю завтра - навскидку, вместо

CODE

entity complex_multiplier is
generic (b_size: natural := 17;
w_size: natural := 12
);
port (
y_re: in std_logic_vector(b_size downto 0);
y_im: in std_logic_vector(b_size downto 0);
...

наверное должно было быть

CODE

entity complex_multiplier is
generic (b_size: natural := 17;
w_size: natural := 12
);
port (
y_re: in std_logic_vector(b_size-1 downto 0);
y_im: in std_logic_vector(b_size-1 downto 0);
...

Присланное закрывает пункт 2, а что с пунктом 1 ? Где блок умножителей согласно блоксхеме?

[Sefo]

вроде умножает=))

Я Вас попрошу серьезнее относиться к результатам симуляции. Ни черта он у Вас не умножает.

Результат должен был быть 58593 + j 0, а у Вас в 2 раза меньше.

Вопрос на засыпку - Вы уже на нем засыпались , но теперь, надеюсь, ответите правильно:

Чему равна разрядность произведения двух знаковых чисел, если разрядость одного числа n, а другого k?

[ZED]

Чему равна разрядность произведения двух знаковых чисел, если разрядость одного числа n, а другого k?

n+k

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

А вот вроде как блок, не знаю то или не то, голова уже не работает, вроде по RTL 4 комплексных перемножителя в одном блоке...

Прикрепленные файлы

 complex_multiplier.rar ( 433.8 килобайт ) Кол-во скачиваний: 93
 block_multipliers.rar ( 239.91 килобайт ) Кол-во скачиваний: 95

 

[Sefo]

n+k

Не угадали. n+k это для беззнаковых операндов. А для знаковых чуть-чуть иначе. Ну, подумайте же как следует!

[ZED]

По-моему что для знаковых, что для беззнаковых произведение будет размерности n+k, только для знаковых старшие два разряда знаковые. Если вы это имеете ввиду, то можно сказать, что для знаковых размерность будет n + k -1.