Fft bin что это
О классификации методов преобразования Фурье на примерах их программной реализации средствами Python
Введение
Публикации по методу Фурье условно можно разделить на две группы. Первая группа так называемых познавательных публикаций, например, [1,2].
Вторая группа публикаций касается применения преобразований Фурье в технике, например, при спектральном анализе [3,4].
Ни в коем случае не умоляя достоинства этих групп публикации стоит признать, что без классификации, или хотя бы попытки осуществить такую классификацию, получить системное представление о методе Фурье, по моему мнению, затруднительно.
Задачи публикации
Провести классификацию методов преобразования Фурье на примерах их программной реализации средствами Python. При этом для облегчения чтения использовать формулы только в программном коде с соответствующими пояснениями.
Гармонический анализ и синтез
Гармоническим анализом называют разложение функции f(t), заданной на отрезке [0, Т] в ряд Фурье или в вычислении коэффициентов Фурье по формулам.
Гармоническим синтезом называют получение колебаний сложной формы путем суммирования их гармонических составляющих (гармоник).
Результат
Спектральный анализ периодических функций заключается в нахождении амплитуды Аk и фазы j k гармоник (косинусоид) ряда Фурье. Задача, обратная спектральному анализу, называется спектральным синтезом.
Результат
Фильтрация аналоговых сигналов
Под фильтрацией подразумевается выделение полезного сигнала из его смеси с мешающим сигналом — шумом. Наиболее распространенный тип фильтрации — частотная фильтрация. Если известна область частот, занимаемых полезным сигналом, достаточно выделить эту область и подавить те области, которые заняты шумом.
Программная реализация иллюстрирует технику фильтрации с применением БПФ. Сначала синтезируется исходный сигнал, представленный 128 отсчетами вектора v. Затем к этому сигналу присоединяется шум с помощью генератора случайных чисел (функция np. random.uniform(0,0.5)) и формируется вектор из 128 отсчетов зашумленного сигнала.
Результат
Решение дифференциальных уравнений в частных производных
Алгоритм решения дифференциальных уравнений математической физики с использованием прямого и обратного БПФ приведен в [5]. Воспользуемся приведенными данными для программной реализации на Python решения дифференциального уравнения распространения тепла в стержне с применением преобразования Фурье.
Результат
Вывод
В статье приведена попытка классификации по областям применения методов преобразования Фурье.
Понимание алгоритма БПФ
Здравствуйте, друзья. Уже завтра стартует курс «Алгоритмы для разработчиков», а у нас остался один неопубликованный перевод. Собственно исправляемся и делимся с вами материалом. Поехали.
Быстрое преобразование Фурье (БПФ — англ. FFT) является одним из важнейших алгоритмов обработки сигналов и анализа данных. Я пользовался им годами, не имея формальных знаний в области компьютерных наук. Но на этой неделе мне пришло в голову, что я никогда не задавался вопросом, как БПФ так быстро вычисляет дискретное преобразование Фурье. Я стряхнул пыль со старой книги по алгоритмам, открыл ее, и с удовольствием прочитал об обманчиво простой вычислительной уловке, которую Дж. В. Кули и Джон Тьюки описали в своей классической работе 1965 года, посвященной этой теме.
Цель этого поста — окунуться в алгоритм БПФ Кули-Тьюки, объясняя симметрии, которые к нему приводят, и показать несколько простых реализаций на Python, применяющих теорию на практике. Я надеюсь, что это исследование даст специалистам по анализу данных, таким как я, более полную картину того, что происходит под капотом используемых нами алгоритмов.
Дискретное преобразование Фурье
БПФ — это быстрый алгоритм для вычисления дискретного преобразования Фурье (ДПФ), которое напрямую вычисляется за . ДПФ, как и более знакомая непрерывная версия преобразования Фурье, имеет прямую и обратную форму, которые определяются следующим образом:
Прямое дискретное преобразование Фурье (ДПФ):
Обратное дискретное преобразование Фурье (ОДПФ):
Преобразование из xn → Xk является переводом из конфигурационного пространства в пространство частотное и может быть очень полезным как для исследования спектра мощности сигнала, так и для преобразования определенных задач для более эффективного вычисления. Некоторые примеры этого в действии вы можете найти в главе 10 нашей будущей книги по астрономии и статистике, где также можно найти изображения и исходный код на Python. Пример использования БПФ для упрощения интегрирования сложных в противном случае дифференциальных уравнений смотрите в моем посте «Решение уравнения Шредингера в Python».
Из-за важности БПФ (далее может быть использовано равносильное FFT — Fast Fourier Transform) во многих областях Python содержит множество стандартных инструментов и оболочек для его вычисления. И NumPy, и SciPy имеют оболочки из чрезвычайно хорошо протестированной библиотеки FFTPACK, которые находятся в подмодулях numpy.fft и scipy.fftpack соответственно. Самый быстрый БПФ, о котором я знаю, находится в пакете FFTW, который также доступен в Python через пакет PyFFTW.
На данный момент, однако, давайте оставим эти реализации в стороне и зададимся вопросом, как мы можем вычислить БПФ в Python с нуля.
Вычисление дискретного преобразования Фурье
Для простоты мы будем касаться только прямого преобразования, поскольку обратное преобразование может быть реализовано очень похожим образом. Взглянув на приведенное выше выражение ДПФ (DFT), мы видим, что это не более чем прямолинейная линейная операция: умножение матрицы на вектор
с матрицей М, заданной
Имея это в виду, мы можем вычислить ДПФ с использованием простого умножения матрицы следующим образом:
Мы можем перепроверить результат, сравнив его со встроенной в numpy БПФ-функцией:
Просто чтобы подтвердить медлительность нашего алгоритма, мы можем сравнить время выполнения этих двух подходов:
Мы более чем в 1000 раз медленнее, что и следовало ожидать для такой упрощенной реализации. Но это не самое худшее. Для входного вектора длины N алгоритм БПФ масштабируется как , в то время как наш медленный алгоритм масштабируется как . Это означает, что для элементов мы ожидаем, что БПФ завершится за где-то около 50 мс, в то время как наш медленный алгоритм займет около 20 часов!
Так как же БПФ добивается такого ускорения? Ответ заключается в использовании симметрии.
Симметрии в дискретном преобразовании Фурье
Одним из наиболее важных инструментов в построении алгоритмов является использование симметрий задачи. Если вы можете аналитически показать, что одна часть проблемы просто связана с другой, вы можете вычислить подрезультат только один раз и сэкономить эти вычислительные затраты. Кули и Тьюки использовали именно этот подход при получении БПФ.
Мы начнем с вопроса о значении . Из нашего выражения выше:
где мы использовали тождество exp [2π i n] = 1, которое выполняется для любого целого числа n.
Последняя строка хорошо показывает свойство симметрии ДПФ:
для любого целого числа i. Как мы увидим ниже, эту симметрию можно использовать для гораздо более быстрого вычисления ДПФ.
ДПФ в БПФ: использование симметрии
Кули и Тьюки показали, что можно разделить вычисления БПФ на две меньшие части. Из определения ДПФ имеем:
Мы разделили одно дискретное преобразование Фурье на два слагаемых, которые сами по себе очень похожи на меньшие дискретные преобразования Фурье, одно на значения с нечетным номером и одно на значения с четным номером. Однако до сих пор мы не сохранили никаких вычислительных циклов. Каждый член состоит из (N / 2) ∗ N вычислений, всего .
Хитрость заключается в использовании симметрии в каждом из этих условий. Поскольку диапазон k равен 0≤k True
Сопоставим этот алгоритм с нашей медленной версией:
-In [6]:
Наш расчет быстрее чем прямая версия на порядок! Более того, наш рекурсивный алгоритм асимптотически : мы реализовали быстрое преобразование Фурье.
Обратите внимание, что мы все еще не приблизились к скорости встроенного алгоритма FFT в numpy, и этого следовало ожидать. Алгоритм FFTPACK, стоящий за fft numpy, — это реализация на Фортране, которая получила годы доработок и оптимизаций. Кроме того, наше решение NumPy включает в себя как рекурсию стека Python, так и выделение множества временных массивов, что увеличивает время вычислений.
Хорошая стратегия для ускорения кода при работе с Python / NumPy — по возможности векторизовать повторяющиеся вычисления. Это мы можем сделать — в процессе удалять наши рекурсивные вызовы функций, что сделает наш Python FFT еще более эффективным.
Обратите внимание, что в вышеупомянутой рекурсивной реализации FFT на самом низком уровне рекурсии мы выполняем N / 32 идентичных матрично-векторных произведений. Эффективность нашего алгоритма выиграет, если одновременно вычислить эти матрично-векторные произведения как единое матрично-матричное произведение. На каждом последующем уровне рекурсии мы также выполняем повторяющиеся операции, которые можно векторизовать. NumPy отлично справляется с такой операцией, и мы можем использовать этот факт для создания этой векторизованной версии быстрого преобразования Фурье:
Хотя алгоритм немного более непрозрачен, это просто перестановка операций, используемых в рекурсивной версии, с одним исключением: мы используем симметрию в вычислении коэффициентов и строим только половину массива. Опять же, мы подтверждаем, что наша функция дает правильный результат:
Поскольку наши алгоритмы становятся намного более эффективными, мы можем использовать больший массив для сравнения времени, оставляя DFT_slow :
In [9]:
Мы улучшили нашу реализацию еще на порядок! Сейчас мы находимся на расстоянии примерно в 10 раз от эталона FFTPACK, используя всего пару десятков строк чистого Python + NumPy. Хотя это все еще не соответствует в вычислительном отношении, с точки зрения читаемости версия Python намного превосходит исходный код FFTPACK, который вы можете просмотреть здесь.
Итак, как FFTPACK достигает этого последнего ускорения? Ну, в основном, это просто вопрос детальной бухгалтерии. FFTPACK тратит много времени на повторное использование любых промежуточных вычислений, которые можно использовать повторно. Наша клочковатая версия все еще включает в себя избыток выделения памяти и копирования; на низкоуровневом языке, таком как Fortran, легче контролировать и минимизировать использование памяти. Кроме того, алгоритм Кули-Тьюки можно расширить, чтобы использовать разбиения размером, отличным от 2 (то, что мы здесь реализовали, известно как БПФ Кули-Тьюки радикса по основе 2). Также могут быть использованы другие более сложные алгоритмы БПФ, в том числе принципиально отличные подходы, основанные на сверточных данных (см., Например, алгоритм Блюштейна и алгоритм Рейдера). Комбинация вышеупомянутых расширений и методов может привести к очень быстрым БПФ даже на массивах, размер которых не является степенью двойки.
Хотя функции на чистом Python, вероятно, бесполезны на практике, я надеюсь, что они преподнесли некоторую интуицию в том, что происходит на фоне анализа данных на основе FFT. Как специалисты по данным, мы можем справиться с реализацией «черного ящика» фундаментальных инструментов, созданных нашими более алгоритмически настроенными коллегами, но я твердо убежден, что чем больше у нас понимания о алгоритмах низкого уровня, которые мы применяем к нашим данным, тем лучшими практиками мы будем.
Этот пост был полностью написан в блокноте IPython. Полный блокнот можно скачать здесь или посмотреть статически здесь.
Многие могут заметить, что материал далеко не новый, но, как нам кажется, вполне актуальный. В общем пишите была ли статья полезной. Ждём ваши комментарии.
Сверхдлинное преобразование Фурье на FPGA
В этой статье я хочу рассказать про реализацию алгоритма сверхдлинного быстрого преобразования Фурье на ПЛИС. Написать эту статью меня побудило желание поделиться личным практическим опытом, который не хотелось бы потерять, оставив информацию только у себя в голове. А поскольку я больше не занимаюсь задачами цифровой обработки сигналов на ПЛИС, то я просто обязан передать доступные мне знания.
В этой статье показана невозможность реализации «классической» схемы очень длинного БПФ даже на самых современных кристаллах ПЛИС и предложен алгоритм, позволяющий это сделать. Также пошагово рассмотрена основная идея алгоритма: от математической составляющей до создания законченного решения на базе ПЛИС с использованием внешней DDR-памяти. Статья затронет тонкости проектирования многоканальных систем обработки для подобного класса задач и, в частности, опишет мой практический опыт.
Постановка задачи
Представьте, что вам необходимо разработать широкополосный спектроанализатор с высокой разрешающей способностью по частоте. Известно, что чем больше длина БПФ, тем выше разрешающая способность. То есть вам необходимо спроектировать систему, которая принимает сигналы от АЦП, делает некую обработку внутри FPGA и выдает данные по высокоскоростному интерфейсу (например, PCIe, USB etc.) на следующие стадии обработки данных.
Формализуем требования задания:
Классический подход не работает!
Прежде чем переходить к описанию алгоритма сверхдлинного преобразования Фурье, следует сказать о принципиальной невозможности реализации на ПЛИС классических схем БПФ при определенных длинах. Именно из-за этого возникает решение, которое будет описано в этой статье.
Представим, что перед вами стоит задача разработать узел БПФ длиной от 256К до 64М отсчетов. В свободном доступе от лидирующих вендоров Xilinx & (ex. Altera) Intel нет доступных ядер с длиной БПФ, превышающей 64К точек. Причиной служит огромный расход блочной памяти (BRAM) кристалла ПЛИС при увеличении длины БПФ. Не спасает и появление URAM блоков в микросхемах от Xilinx. Даже если вы напишете свое супер-оптимальное решение по классической схеме алгоритма БПФ через конвейерное соединение узлов бабочек и кросс-коммутационных узлов, вы не сможете реализовать его на ПЛИС. Почему?
При увеличении длины БПФ в N раз, как минимум во столько же раз пропорционально изменяется объем занимаемых ресурсов BRAM. Для БПФ в формате с плавающей точкой число узлов BRAM увеличивается пропорционально, но для БПФ в формате с фиксированной точкой оценка потребляемых ресурсов еще пессимистичнее. Это вызвано тем, что на каждой стадии вычисления БПФ (после каждой бабочки) разрядность промежуточных данных растет на 1 бит.
Конечная разрядность на выходе узла БПФ вычисляется по формуле
Для примера, БПФ длиной 1М отсчетов прибавляет ко входному сигналу 20 бит. Если входной сигнал имеет разрядность 16 бит, то выходной сигнал будет 36 бит соответственно.
Посмотрим на таблицу занимаемых ресурсов для БПФ 64К отсчетов на примере Xilinx. По грубой оценке, если вам нужно сделать блок Floating-Point FFT на 1М точек, то вам потребуется 400 * 16 = 6400 элементов блочной памяти типа RAMB36K или
220 Мбит! Такими ресурсами обладает только топовый Virtex UltraScale+ (VU29P) и то за счет URAM ячеек.
На следующих таблицах показано, сколько внутренней памяти есть у современных FPGA от Xilinx на примере серии Kintex.
Kintex Ultrascale
Kintex Ultrascale+
Как видно, ресурсы ПЛИС по блочной памяти сильно ограничены, поэтому реализовать БПФ даже для длины 1М точек в классическом виде практически невозможно.
Сверхдлинное БПФ
К счастью, можно использовать небольшой математический трюк и сделать одномерное БПФ на базе двумерного.
Общая идея алгоритма в том, что вектор сигнала длины N разбивается на N1 и N2 отсчетов (где N1 и N2 кратны степени двойки). Этот вектор преобразуется в матрицу размерности N1 x N2, над которой производятся все вычисления. Короткие БПФ длиной N1 и N2 применяются к строкам и столбцам.
Формула для вычисления БПФ:
Разобъем последовательность N на произведение N1 и N2, тогда:
Тогда формула принимает вид:
После преобразования поворачивающих множителей:
Можно заметить, что одномерное БПФ длины N превращается в два БПФ с длинами N1 и N2, и домножение результата первого БПФ на поворачивающие множители.
Структурная схема алгоритма сверхдлинного БПФ:
Пример: ядро БПФ длиной 1М отсчетов. Можно разбить вычисление на два БПФ по 1К отсчетов: 1024 х 1024 = 1048576. На следующем рисунке показано, что узлу БПФ на 1024 точек требуется всего 7 ячеек RAMB36K.
Видно, что небольшие ядра БПФ практически не занимают ресурсы ПЛИС, в частности почти не используют блочную память. Пройдемся по всем элементам алгоритма и посмотрим на основные особенности каждого.
Пошаговая реализация
Блоки БПФ
Узлы БПФ реализуются по классической конвейерной схеме — последовательное соединение log2(N) бабочек Radix-2 / Radix-4 и узлов кросс-коммутации. Можно использовать готовые бесплатные ядра от вендоров FPGA, либо написать свое оптимизированное ядро. Узлы FFT могут производить вычисления в формате fixed-point, floating-point или в каком-то своем кастомном формате, в зависимости от задачи.
Ядро БПФ может быть реализовано с выдачей результата в бит-реверсном порядке, либо в натуральном (нормальном) порядке. В первом случае вы еще больше экономите ресурсы блочной памяти, но немного усложняете алгоритмы перестановок данных при транспонировании матриц. Если вы только начали реализовывать сверхдлинные БПФ, то начните со второго варианта, т.к. он проще в отладке.
Если вы реализуете многоканальную систему, а ядро БПФ написали сами, не используя готовое решение от производителей вашей ПЛИС, то можете дополнительно сэкономить память BRAM на хранении поворачивающих коэффициентов для бабочек БПФ. Для N независимых параллельных каналов можно использовать всего 1 модуль хранения поворачивающих множителей. То есть, чем больше канальность системы — тем больше экономия ресурсов.
Поворачивающие множители
Согласно схеме алгоритма, перед подачей матрицы на второе звено БПФ, данные необходимо домножить на поворачивающие множители. Сделать это можно двумя способами — использовать DDS или взять алгоритм CORDIC. Первый способ предполагает хранение большого массива данных, что требует значительного объема блочной памяти ПЛИС, за которую мы боремся с самого начала этой статьи. Теоретически, можно использовать аппроксимацию по Тейлору и сократить хранимый массив в BRAM. Но на моей практике такое решение искажает результирующий спектр из-за ступенчатой формы сигнала поворачивающих множителей.
Второй способ на базе CORDIC вообще не требует блочной памяти BRAM, так как использует итеративную схему применения операции сдвига и сложения/вычитания. К недостаткам алгоритма CORDIC можно отнести длительное время вычисления следующего значения (требуется порядка 20-30 тактов, число зависит от разрядности). Этот недостаток приводит к организации дополнительной линии задержки поступающих данных, что отнимает определенный логический ресурс ПЛИС. Например, для многоканальной схемы с разрядностью 512 (2 комплексных отсчета по 32 бит, 8 каналов) дополнительно потребуется 512 * 30 = 15 тысяч триггеров. В FPGA Xilinx для этого есть ячейки SLICEM, организующие линию задержки на сдвиговых регистрах. Либо на линию задержки можно потратить несколько блоков BRAM.
К ядру CORDIC выдвигаются следующие требования:
Для многоканальной схемы также можно использовать один узел поворачивающих множителей на весь поток данных и сэкономить ресурсы ПЛИС.
Узлы транспонирования
Контроллеры памяти используются для хранения векторов промежуточных данных, а также для транспонирования матрицы на всех стадиях алгоритма. Это может быть любая доступная вам память: QDR SRAM, DDR3 или DDR4 SDRAM. В своих проектах я использовал последние две. Но общие принципы работы одинаковы: контроллер памяти транспонирует выборку — получает пачку данных «по строкам«, а выдает пачку данных в формате «по столбцам«.
Как видно из схемы алгоритма, для этой задачи требуется три внешних узла памяти, к которым выделяются два главных требования.
Первое:
Память должна хранить минимальную выборку из 2 длин БПФ. Это необходимо для того, чтобы в процессе записи одной пачки данных в прямой форме (по строкам матрицы) иметь возможность успевать дочитать вторую пачку в инверсной форме (по столбцам матрицы). Но самое лучшее решение хранения данных не через мультиплексор, а когда внешняя память реализована по схеме FIFO. В таком случае внешняя память может хранить много пачек данных длиной N и эффективно использовать свой ресурс.
Также на практике такая схема позволяет бороться с небольшими замираниями интерфейса на выходе узла БПФ. В частности, при кратковременном замирании передачи по шине PCIe, вероятность переполнения памяти в режиме FIFO существенно ниже, чем у схемы с переключением между одной пачкой и другой. В реализованных мной проектах, DDR-память при замираниях на шине PCIe в режиме мультиплексора переполнялась почти всегда, а в режиме FIFO — никогда.
Рассчитаем объем для хранения данных во внешней памяти. Пусть разрядность входных данных 32 бита (single floating-point), сигнал — комплексный (I / Q), длина БПФ равна 1М отсчетов, схема реализации — «пинг-понг» как минимально необходимое требование. Тогда для хранения потребуется 2 * 32 / 8 = 8 МБ памяти. Для хранения данных в режиме FIFO глубиной 32 потребуется уже 256 МБ памяти.
Второе:
Память должна успевать записывать и читать данные в режиме реального времени. Согласно алгоритму, схема передачи данных на входе и выходе контроллера отличается. Поэтому нужно правильно организовать процесс передачи данных на максимальной скорости, чтобы не происходило разрывов и искажения данных. Для этого еще на этапе проектирования или покупки готовой платы, на которой будет работать сверхдлинное БПФ, нужно рассчитать максимальную пропускную способность всей системы. То есть найти максимальный поток ввода-вывода во внешнюю память согласно даташиту и определить скорость подачи данных от многоканального АЦП.
От длины БПФ пропускная способность не зависит.
Кроме того, к кристаллу ПЛИС предъявляется требование взаимодействия с тремя контроллерами памяти. Например, на каждый контроллер памяти SO-DIMM DDR4 SDRAM x64 необходимо три банка ПЛИС (эквивалентно
150 физическим ножкам ввода-вывода кристалла). Суммарно потребуется не менее 450 I/O портов или 9 HP (High-Performance) банков ПЛИС, не считая банков мультигигабитных трансиверов и конфигурационного банка Bank0.
Пример настроек IP-ядра DDR4 SDRAM:
Следует отметить, что для достижения максимальной производительности, при чтении требуется производит обход по всем FSM группам контроллера памяти в ПЛИС (см. даташит на Xilinx DDR MIG), то есть нужно проходить по всем банкам и группам банков физической памяти. Это накладывает дополнительные ограничения и приводит к необходимости иметь буфер данных после контроллера памяти в ПЛИС. Его назначение — организация и упаковка обработанных транзакций с каждого банка памяти для дальнейшей передачи на следующие узлы схемы. Для реализации буфера данных идеально подходят модули URAM (блоки глубиной 4K и разрядностью 72 бит), которые появились в современных FPGA от Xilinx.
Также отмечу, что последний узел транспонирования можно использовать как аккумулятор, реализуя схему накопления спектральных компонент для усреднения результирующего спектра.
Оконная функция
Наложение окна на входной сигнал — необязательная операция, но если вам необходимо добавить оконную функцию к длинному БПФ, то вы можете столкнуться с трудностями.
Поскольку мы используем сверхдлинные БПФ, то нам совсем негде хранить массив для оконных функций. Для БПФ длины N потребуется немало ресурсов блочной памяти. Например, оконная функция в виде 32-битного сигнала длиной 16М отсчетов потребует с учетом её симметричности: 32 * 4 / 2 = 256 Мбит. Даже для топовых кристаллов FPGA это много. А если нужно иметь возможность непрерывно переключать функции (как минимум потребуется два независимых буфера данных)?
Решить эту проблему можно очень просто, используя окна Блэкмана-Харриса нужного порядка и стандартную формулу вычисления коэффициентов окна. Применяя известный CORDIC для генерации гармонических сигналов нужной частоты, можно реализовать оконную функцию Блэкмана-Харриса любого порядка без использования блочной памяти FPGA!
Чем выше порядок оконной функции — тем ниже уровень боковых лепестков спектра. На практике мне приходилось использовать окна до 5 порядка. Останавливаться на этом не будем, более подробно об оконной фильтрации на ПЛИС я уже рассказывал в своей предыдущей статье.
Контрольные точки
Ниже показано прохождение сигнала через узлы алгоритма сверхдлинного БПФ. В качестве входного воздействия выбран сигнал в виде пика на одном значении и ЛЧМ сигнал.
Скрипт, который формирует данные на каждой стадии Ultra-Long FFT. Написан на Python, для его работы требуются библиотеки numpy, scipy и matplotlib.
Диаграммы в Vivado
Транспонированный ЛЧМ сигнал до и после одной из стадий БПФ:
Прохождение ЛЧМ сигнала через узел БПФ:
Практический пример
Пусть перед вами стоит задача с такими вводными:
Входной поток информации: (2 * 16) * 400e6 / 2^30 =
1.5 ГБ/c.
Промежуточный поток информации:
Объем памяти для хранения одной пачки БПФ: (2 * 32 / 8) * 16M = 128 МБ.
Пропускная способности памяти на чтение и запись — не менее
6 ГБ/c.
Этому требованию удовлетворяет DDR4-2400 SDRAM x32 по формуле: Freq * Double Rate * (Width / Byte) = 1.2e9 * 2 * (32 / 8) / 2^30 = 8.94 ГБ/c.
С помощью IP Catalog создадим ядра DDR, FFT, CORDIC. Полное БПФ 16М точек раскладывается на матрицу БПФ как 4К х 4К. Пусть на перепаковку данных до и после контроллера DDR требуется FIFO, которые занимают 4 ячейки блочной памяти RAMB36K.
Грубая оценка потребления ресурсов ПЛИС на реализацию алгоритма. Нам необходимо 3 контроллера памяти, 2 узла БПФ 4К, один CORDIC, 6 блоков FIFO (до и после контроллеров памяти), 3 буфера банков памяти. Для простоты не будем учитывать линии задержки для согласования потока, комплексные умножители и остальную логику.
Как видно, проект занимает не очень много ресурсов и помещается в относительно дешевые ПЛИС. Однако, не стоит забывать, что 3 контроллера памяти требуют определенное количество I/O портов ПЛИС, поэтому подойдут не все микросхемы.
Заключение
В данной статье показан способ реализации узлов сверхдлинных БПФ на ПЛИС в задачах высокоточного анализа спектра сигнала в режиме реального времени. Проектирование такого алгоритма требует определенной конфигурации «хардварной» части — к ПЛИС должны подключаться три независимых контроллера памяти. Однако, это позволяет создавать схемы очень длинных БПФ с количеством точек от 256К до 256М. Поскольку алгоритм имеет много нюансов в аппаратной реализации, необходимо заранее просчитать параметры всех узлов схемы и убедиться в реализуемости ядра на выбранной вами конфигурации.
Для реализации алгоритма сверхдлинного БПФ идеально подходят платы Alveo U200 / U250 от Xilinx (4 контроллера DDR4 на борту) или Alveo U280 (два DIMM DDR4 и HBM2).