Jump to content

    
Sign in to follow this  
ZED

Реализация БПФ на ПЛИС

Recommended Posts

Добрый день! тоже хочется вклиниться, но из-за нехватки времени на реализацию... приходится брать готовое что-то.... вопщем как обычно :( вопрос такой : Вот на Альтере выложили БПФ на 32к точки. я правильно понимаю, что просто изменив параметры получаю свой fft - мне нужен на 512, или изменилось число входных данных и это уже совсем другой вычислитель получается и надо искать на 512 точек готовый?

 

parameter data_width = 16; //The number of bits in the input data for both real and imag parts

parameter twiddle_width = 16; //The number of bits in the twiddle factor for both real and imag parts

parameter transform_length = 32768;

parameter coshex_init_file = "fft_32K_coshex.hex";

parameter sinhex_init_file = "fft_32K_sinhex.hex";

parameter log2_transform_length = 15;

parameter mram_buf_add_width = 15;

 

а ну наверно надо другие син кос коеффициенты, да?

 

спасибо.

fft_32K.v

Share this post


Link to post
Share on other sites

Не знаю, я не сталкивался с Альтеровским БПФ, если там только 32 точечный, то прощек самому писать 512 (я так думаю), чем из 32-точечных слепить 512-точечный. Так что или свой или ищи готовый на 512.

Share this post


Link to post
Share on other sites

Да, там действительно нет коэффициента W1028? хотя кстати он тождественно равен W0. Там везде будут только W0. Вот я только немного с порядком не разобрался. При 4-х точечной бабочки у нас на выходе порядок отсчетов четвиричноинверсный, а при 2-х точечной - двоичноинверсный. Какой же порядок будет в нашем случае (даже если мы будем вычислять бабочки в разнобой)?

 

Честно говоря несовсем представляю другую реализацию gen_addr, но очень интересно.

Share this post


Link to post
Share on other sites
хотя кстати он тождественно равен W0.

Увы, тождественно не равен. Кстати сказать, нет такого коэффициента, который был бы тождественно равен какому либо другому коэффициенту. Бывают тривиальные коэффициенты.

 

 

При 4-х точечной бабочки у нас на выходе порядок отсчетов четвиричноинверсный, а при 2-х точечной - двоичноинверсный. Какой же порядок будет в нашем случае (даже если мы будем вычислять бабочки в разнобой)?

 

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

 

Честно говоря несовсем представляю другую реализацию gen_addr, но очень интересно.

 

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

 

Стал расписывать реализацию схемы управления и понял, что зря я 30 августа на 6 этапе решил за блок посчитать четыпе 2-х точечные бабочки – не стоит выбиваться из общего алгоритма, так что исправленная схема БПФ прилагается.

 

Очевидно, что нужен счетчик на 512 тактов, переполнение которого означает переход к следующему этапу БПФ и сам счетчик этапов. С этим все ясно.

 

Рассмотрим чтение и запись отдельно.

 

Начнем с чтения. По схеме хорошо видно, что количество бабочек в блоке и, соответственно количество тактов на блок с каждым этапом уменьшается в 4 раза. Исключение составляет последний 6-ой этап, где разница в 2 раза (на 4-ом этапе 8 тактов на блок, на 5-ом 2 такта, а на 6-ом 1 такт). При переходе от одного блока к другому мы вращаем банки памяти. Для реализации этого алгоритма нам необходим счетчик с переменным модулем счета COUNTER(8 downto 0). При этом модуль счета удобно формировать сдвиговым регистром, который при переходе к следующему этапу будет сдвигать свое значение вправо на 2 разряда. Тот факт, что на 6 этапе делить надо не на 4, а на 2 учиывается автоматически (в данном конкретном случае). Таким образом, начальное значение сдвигового регистра MODULE(8 downto 0) = (others => '1') (т.е. 511), далее при переходе к очередному этапу MODULE(8 downto 0) <= "00" & MODULE(8 downto 2). В результате сдвигов получаем следующий набор значений 511, 127, 31, 7, 1 и 0. При 0 мы будем вращать банки на каждом такте, что соответствует поведению на 6-ом этапе. Когда значение COUNTER будет становится равно модулю счета (если считаем вверх) происходит инкремент 2-х битного счетчика номера банка BANK_COUNTER(1 downto 0) . На всякий случай напомню, что наш "вращатель" банков на вход получает только одно 2-х разрядное число – номер начального банка. Само по себе значение номера блока нам, вобщем-то не нужно. Поcкольку количество блоков всегда кратно 4, то при переходе от этапа к этапу BANK_COUNTER(1 downto 0) всегда будет обнуляться и поэтому какой-либо сброс в начале следующего этапа не требуется. Т.е. В начале "заряжаем" COUNTER и BANK_COUNTER, а затем они крутятся себе особо не обращая внимания на смену этапов.

 

С адресами сложнее, но и интереснее. Но об этом в ближайшие дни.

 

FFT_2048__03_09_09_.rar

Share this post


Link to post
Share on other sites
Ваш gen_addr посмотрел, но мы сделаем другую реализацию – вычисление номеров банков и адресов настолько единообразно от этапа к этапу, что жалко заводить на каждый этап по "when …" с константами.

 

MODULE(8 downto 0) <= (others => '1')

MODULE(8 downto 0) <= "00" & MODULE(8 downto 2)

MODULE(8 downto 0) <= "0000" & MODULE(8 downto 4)

и т.д.

 

В Этом случае разве не понадобятся when?

Share this post


Link to post
Share on other sites
MODULE(8 downto 0) <= (others => '1')

MODULE(8 downto 0) <= "00" & MODULE(8 downto 2)

MODULE(8 downto 0) <= "0000" & MODULE(8 downto 4)

и т.д.

 

В Этом случае разве не понадобятся when?

 

Нет, т.к. я имел ввиду обычный сдвигорый регистр, что-то вроде этого:

 

process(CLK)
begin

  if rising_edge(CLK) then
    if INIT = '1' then
      MODULE(8 downto 0) <= (others => '1');
    elsif SHIFT_STROBE = '1' then
      MODULE(8 downto 0) <= "00" & MODULE(8 downto 2);
    end if;
  end if;

end process;

 

т.е. MODULE(8 downto 0) <= (others => '1') делается 1 раз перед началом вычисления очередного БПФ над очнредной порцией данных,

 

а MODULE(8 downto 0) <= "00" & MODULE(8 downto 2) - это описание операции сдвига, которая делается либо по стробу шириной в 1 такт, формируемому при переходе от одного этапа к другому, либо непосредственно по условию, которое является истиной только 1 такт при смене этапов.

Share this post


Link to post
Share on other sites

Продолжим разбираться с чтением. Посмотрим на адреса.

 

У нас 4 банка памяти и каждый получает свой собственный адрес. Адреса каждого банка (независимо от этапа) всегда принимает все значения от 0 до 511 причем на этапе каждое из этих значений адрес принимает только 1 раз. Разрядность адреса 9 бит. Разберем свойства адреса на примере 3-го этапа.

 

Свойство первое: во всех блоках бабочек все адреса блоков памяти в один и тот же момент времени (такт) имеют одинаковые значения в битах (4 downto 0). Например при вычислении 2-ой бабочки (посчитаем их от 0) адрес в банке 0 = 2 (000000010b), адрес в банке 1 = 34 (000100010b), адрес в банке 2 = 66 (001000010b) и адрес в банке 3 = 98 (001100010b)

 

Свойство второе: Старшая часть адреса (8 downto 7) в течении вычисления 4 блоков бабочки остается константой и только при переходе к следующей четверке блоков бабочек меняет свое значение, причем просто инкрементирует его на 1. При этом, эти биты одинаковы у всех адресов банков памяти.

 

Свойство третье: Из первого и второго свойства следует, что адреса банков памяти на протяжении всего этапа имеют одинаковые значения в битах (8 downto 7) и (4 downto 0) и единственное, что их отличает это биты (6 downto 5)

 

Свойство четвертое (очень полезное): Выше было сказано, что нам потребуется "счетчик на 512 тактов, переполнение которого означает переход к следующему этапу БПФ" – счетчик бабочек, попросту говоря. Если хорошо подумать, то Вы должны будете заметить, что если этот счетчик сделать считающим вверх, то биты (8 downto 7) и (4 downto 0) один в один совпадут с такими же битами этого счетчика.

 

Таким образом на третьем этапе нас волнует только одно - как формировать биты (6 downto 5). Но с этим вопросом разберемся чуть позже.

 

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

 

Этап 1: на с хеме хоть и не нарисовано, но думаю очевидно, что все адреса во всех банках это просто счетчик бабочек. Формат адресов банков получается NNNNNNNNN

Этап 2: биты (8 downto 7) у всех адресов свои, но биты (6 downto 0) совпадают со счетчиком бабочек. Формат адресов ##NNNNNNN.

Этап 3: Формат адресов NN##NNNNN.

Этап 4: Формат адресов NNNN##NNN.

Этап 5: Формат адресов NNNNNN##N.

Этап 6: Казалось бы этот этап своими адресами вообще ни на что не похож, но ... Как это ни странно, он очень даже вписывается в общий алгоритм. Формат адресов NNNNNNNN#.

 

Итак, чтобы нагляднее было выпишем еще раз форматы адресов на этапах БПФ

 

NNNNNNNNN

##NNNNNNN

NN##NNNNN

NNNN##NNN

NNNNNN##N

NNNNNNNN#

 

Как без особых трудозатрат сформировать адреса, а точнее сформировать биты # и "расставить" их по местам (напомню, что все остальные биты это просто наш счетчик бабочек) напишу в ближайшие дни.

 

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

Share this post


Link to post
Share on other sites

Хорошо, немного не понял пока тогда назначения счетчика BANK_COUNTER, где он нам пригодиться. А так вроде все понятно. Жду с нетерпением формирования адресов и "расстановки битов по местам".

Share this post


Link to post
Share on other sites

У нас выходы банков памяти подсоеденены к бабочке не на прямую, а через специальный мультиплексор, который "вращает" банки памяти относительно входов бабочки (т.е. данные на каждый вход бабочки подаются из нужного в данный момент банка памяти). BANK_COUNTER(1 downto 0) это сигнал управления этим "вращателем".

Share this post


Link to post
Share on other sites

Чтобы разобраться какими должны быть биты 'X' возьме опять 3-ий этап. Как видно, адреса должны вращаться относительно банков, на подобие как данные из банков памяти вращаются относительно входов бабочки. Конечно, можно сделать еще и отдельный блок "вращателя" для адресов, но лучше его прямо интегрировать в схему формирования адресов. Надеюсь, очевидно, что за "вращение" как раз и отвечают биты 'X'. Так же очевидно, что смена положения этих бит в адресе соответствует поведению обычного сдвигового регистра. Чтобы получить эффект "вращения" можно декрементировать значение битов 'X' по завершению каждого блока бабочек, но тот факт, что их положение и даже количество постоянно меняется усложнит реализацию. В данном случае, самое простое решение – лобовое. Видно, что биты сдвигаются – значит будем сдвигать, сказано, что должны вращаться – значит будем вращать. Я бы назвал эту конструкцию сдвиговым регистром барабанного типа (СРБТ) :) (см. рисуонк).

 

post-7537-1252706664_thumb.jpg

 

Рисунок отражает общий принцип действия, но нам нужно уточнить некоторые детали применительно к нашему БПФ. Разрядность. Она равна 11 (5 этапов по 2 бита + один этап 1 бит). При этом использоваться будут только младшие 9 бит. Дело в том, что на первом этапе биты X вообще не используются и, к тому же, у нас адрес всего 9-ти битный. Можно, конечно, сделать этот СРБТ и 9-ти разрядным, но тогда его инициализацию придется выполнять 2 раза – перед первым этапом и перед вторым, что выбивается из общего алгоритма, да и не сильно выигрывает по объему логики (а то и совсем выигрыша не будет). Так что сделаем его 11-ти разрядным. Т.к. количество вращений у нас кратно 4, то к каждому следующему этапу наш СРБТ будет сам возвращаться в нужное для след. этапа положение. Поэтому достаточно его инициализировать один раз перед вычислением БПФ, а дальше он будет работать по одной и той же схеме. Далее, нам надо учесть, что при переходе от одного этапа к другому нужно вращать и сдвигать одновременно. Подробная схема переходов приведена на рисунке. Чтобы не мучаться с рисованием перемещения битов по кругу, пунктиром обозначен адрес для банка №0. На рисунках представлены 2 схемы перемещения битов – как должен работать СРБТ в течение этапа и как при смене этапов и начальное значение, которое регистр должен получить при инициализации.

 

post-7537-1252706680_thumb.jpg

 

Для размещения битов 'Х' в адресе воспользуемся маской ADDR_ROTATE_MASK, которая будет реализована так же в виде 11-ти разрядного сдвигового регистра. Начальное значение = "00111111111". При смене этапов этот регистр должен всегда сдвигаться на 2 бита вправо с заменой 2-ух старших бит '1' (ADDR_ROTATE_MASK <= "11" & ADDR_ROTATE_MASK(10 downto 2)).

 

Таким образом финальный адрес формируется следующим образом

 

ADDR(i) <= (BUTTERFLY_COUNTER and ADDR_ROTATE_MASK) or ADDR_ROTATE(i)(8 downto 0);

 

где BUTTERFLY_COUNTER это упоминавшийся ранее счетчик бабочек (он "поставляет" биты 'n'), а ADDR_ROTATE это только что описанный СРБТ (он "поставляет" биты 'X')

 

Попробуйте сначала написать код только для СРБТ. Код должен быть очень простой – буквально несколько строчек.

Share this post


Link to post
Share on other sites

Я не очень понял, что за биты 'X', предполагаю, что это ранее обозначенные #. Вращения я так понял это переход от одного блока бабочек к другому, а сдвиг это от этапа к этапу. Далее не совсем понял первый рисунок. Ну и не понял почему вдруг

ADDR_ROTATE это только что описанный СРБТ

Почему он вдруг 8 разрядный получился, когда его мы хотели сделать 11 разрядным:

Разрядность. Она равна 11 (5 этапов по 2 бита + один этап 1 бит). При этом использоваться будут только младшие 9 бит. Дело в том, что на первом этапе биты X вообще не используются и, к тому же, у нас адрес всего 9-ти битный. Можно, конечно, сделать этот СРБТ и 9-ти разрядным, но тогда его инициализацию придется выполнять 2 раза – перед первым этапом и перед вторым, что выбивается из общего алгоритма, да и не сильно выигрывает по объему логики (а то и совсем выигрыша не будет). Так что сделаем его 11-ти разрядным.

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

Share this post


Link to post
Share on other sites
Я не очень понял, что за биты 'X', предполагаю, что это ранее обозначенные #.

Да, так и есть. Сорри. :blush:

 

Вращения я так понял это переход от одного блока бабочек к другому, а сдвиг это от этапа к этапу.

Да.

 

Далее не совсем понял первый рисунок.

Имелось ввиду, что 4 сдвиговых регистра передают свои значения друг другу циклически (ну и т.к. они сдвиговые, то еще и сдвигать вправо могут).

 

И не совсем ясна картинка №2

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

 

Попробуйте, представьте 2-ух мерный сдвиговый регистр (ввиде матрицы, например), который вправо (по оси X) выполняет обычный сдвиг, а вниз (по оси Y) выполняет циклический.

 

Ну и не понял почему вдруг он 8 разрядный получился, когда его мы хотели сделать 11 разрядным

Если Вы имеете ввиду

 

ADDR(i) <= (BUTTERFLY_COUNTER and ADDR_ROTATE_MASK) or ADDR_ROTATE(i)(8 downto 0);

 

то, во-первых (8 downto 0) это 9 разрядов, а во-вторых эта строка не означает, что сам по себе ADDR_ROTATE стал 9-ти разрядным. Просто для формирования адреса нам от него нужно всего 9 младших бит (ведь шина адреса у памяти 9-ти разрядная), но сам он является 11-ти разрядным чтобы его реализация была проще и, так сказать, алгоритмичнее.

 

При этом использоваться будут только младшие 9 бит. Дело в том, что на первом этапе биты X вообще не используются и, к тому же, у нас адрес всего 9-ти битный.

Share this post


Link to post
Share on other sites

Давайте разберем Ваш код. На будущее попрошу Вас писать хоть какие-нибудь комментарии в случае, если написанный код не формирует ожидаемую временную диаграмму. А то, как вот в данном случае, непонятно – то ли Вы старались, но у Вас не получилось и Вы понимаете что не правильно на временной диаграмме, но знаете как добиться нужного результата, то ли Вы даже не попытались проанализировать результаты симуляции. В первом случае, хотелось бы понять, что именно вызвало трудности и написать дополнительные разъяснения, а во втором сказать, что не нужно так лениться :)

По вашей диаграмме видно, что все ADDR_ROTATE_xxx подозрительно быстро сходятся к 0 – уже в начале 3-го этапа (etap = 2). Это происходит потому, что Вы правильно написали в сообщении

Вращения я так понял это переход от одного блока бабочек к другому, а сдвиг это от этапа к этапу.

но при реализации все сделали наоборот. Кроме этого при смене этапа у нас должен происходить одновременно и сдвиг и вращение. Так что ваш код

 

ADDR_ROTATE(1) <= ADDR_ROTATE(0);
ADDR_ROTATE(2) <= ADDR_ROTATE(1);
ADDR_ROTATE(3) <= ADDR_ROTATE(2);
ADDR_ROTATE(0) <= ADDR_ROTATE_buf;

 

Нужно дополнить еще и сдвигом

 

ADDR_ROTATE(1) <= SHIFT_RIGHT(ADDR_ROTATE(0), 2);
ADDR_ROTATE(2) <= SHIFT_RIGHT(ADDR_ROTATE(1), 2);
ADDR_ROTATE(3) <= SHIFT_RIGHT(ADDR_ROTATE(2), 2);
ADDR_ROTATE(0) <= SHIFT_RIGHT(ADDR_ROTATE_buf, 2);

 

Но и это не правильно т.к. SHIFT_RIGHT(ххх, 2) здесь не применим. A <= SHIFT_RIGHT(A, 2) эквивалентен коду A <= "00" & A(n downto 2); Но такой код не соответствует сдвигу нарисованному на диаграмме. Код, соответствующий диаграмме (без учета вращения) выглядит так A <= "00" & A(n downto 3) & A(1); Ну а если еще и учесть вращение, то код полностью соответствующий диаграмме будет таким

ADDR_ROTATE(1) <= "00" & ADDR_ROTATE(1)(10 downto 9) & ADDR_ROTATE(0)(8 downto 3) & ADDR_ROTATE(0)(1);
ADDR_ROTATE(2) <= "00" & ADDR_ROTATE(2)(10 downto 9) & ADDR_ROTATE(1)(8 downto 3) & ADDR_ROTATE(1)(1);
ADDR_ROTATE(3) <= "00" & ADDR_ROTATE(3)(10 downto 9) & ADDR_ROTATE(2)(8 downto 3) & ADDR_ROTATE(2)(1);
ADDR_ROTATE(0) <= "00" & ADDR_ROTATE(0)(10 downto 9) & ADDR_ROTATE(3)(8 downto 3) & ADDR_ROTATE(3)(1);

 

Зачем Вы ввели ADDR_ROTATE_buf? Почему не написали просто ADDR_ROTATE(0) <= SHIFT_RIGHT(ADDR_ROTATE_(3), 2); ?

 

 

...
if (count_but rem (TO_INTEGER(MODULE)+1) = MODULE) and (count_etap /= 0) then
...

Этим кодом, насколько я понимаю, Вы решили заменить счетчик блоков бабочек с переменным модулем счета. Сам по себе код правильный, но с точки зрения синтеза очень "дорогой" и медленный. Деление по модулю требует много логических элементов и работает достаточно медленно – простой счетчик по модулю во много раз лучше по обеим параметрам. Но если решить обойтись без счетчика, то правильнее воспользоваться свойствами MODULE – его можно использовать как маску. В нашем случае деление по модулю заменяется более простым маскированием.

 

...
signal COUNT_BLOCK: unsigned(8 downto 0); 
…
COUNT_BLOCK <= COUNT_BUT and MODULE;
…
if (COUNT_BLOCK = MODULE) and (COUNT_ETAP /= 0) then
…

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this