Добрый день! тоже хочется вклиниться, но из-за нехватки времени на реализацию... приходится брать готовое что-то.... вопщем как обычно вопрос такой : Вот на Альтере выложили БПФ на 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;

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

спасибо.

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

Да, там действительно нет коэффициента W1028? хотя кстати он тождественно равен W0. Там везде будут только 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 ( 514.34 килобайт ) Кол-во скачиваний: 182

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?

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



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

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

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

У нас 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#

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

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

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

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

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



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



Для размещения битов 'Х' в адресе воспользуемся маской 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')

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

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

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

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


Да.


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


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

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


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

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-ти разрядным чтобы его реализация была проще и, так сказать, алгоритмичнее.

Как у Вас дела с реализацией СРБТ?

Вот мои наработки, я там вывел некоторые сигналы для наглядности...

Давайте разберем Ваш код. На будущее попрошу Вас писать хоть какие-нибудь комментарии в случае, если написанный код не формирует ожидаемую временную диаграмму. А то, как вот в данном случае, непонятно – то ли Вы старались, но у Вас не получилось и Вы понимаете что не правильно на временной диаграмме, но знаете как добиться нужного результата, то ли Вы даже не попытались проанализировать результаты симуляции. В первом случае, хотелось бы понять, что именно вызвало трудности и написать дополнительные разъяснения, а во втором сказать, что не нужно так лениться
По вашей диаграмме видно, что все ADDR_ROTATE_xxx подозрительно быстро сходятся к 0 – уже в начале 3-го этапа (etap = 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_buf? Почему не написали просто ADDR_ROTATE(0) <= SHIFT_RIGHT(ADDR_ROTATE_(3), 2); ?



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