в каком бпф используется бит реверсная перестановка выходных отсчетов
Реализация узла БПФ с плавающей точкой на ПЛИС
Всем привет! В этой статье речь пойдет о реализации быстрого преобразования Фурье в формате с плавающей точкой на ПЛИС. Будут показаны основные особенности разработки ядра от самой первой стадии до готового конфигурируемого IP-ядра. В частности, будет проведено сравнение с готовыми ядрами фирмы Xilinx, показаны преимущества и недостатки тех или иных вариантов реализации. В статье будет рассказано о главной особенности ядра БПФ и ОБПФ — об отсутствии необходимости переводить данные в натуральный порядок после БПФ и ОБПФ для их совместной связки. В этой статье я постараюсь отразить всё тонкости реализации проекта под названием FP23FFTK, приведу реальные примеры использования готового ядра. Проект написан на языке VHDL и заточен под FPGA фирмы Xilinx последних семейств.
Введение
В цифровой обработке сигналов, без всякого сомнения, основным инструментом анализа является быстрое преобразование Фурье (БПФ). Алгоритм находит применение практически во всех областях науки и техники. Простейшим физическим примером преобразования Фурье может служить восприятие звука человеком. Всякий раз, когда мы слышим звук, ушная раковина автоматически выполняет сложное вычисление, проделать которое человек способен лишь после нескольких лет обучения математике. Суть явления заключается в том, что слуховой орган представляет звук в виде спектра последовательных значений громкости для тонов различной высоты, а мозг превращает получаемую информацию в воспринимаемый звук.
В вопросах радиотехники алгоритмы БПФ находят применение в свёртке и при проектировании цифровых корреляторов, используется при обработке изображений, а также в аудио- и видеотехнике (эквалайзеры, спектроанализаторы, вокодеры). Кроме того методы БПФ лежат в основе всевозможных алгоритмов шифрования и сжатия данных (jpeg, mpeg4, mp3), а также при работе с длинными числами. БПФ используется в гидроакустических системах для обнаружения надводных кораблей и подводных лодок, в радиолокационных системах для получения информации о скорости, направлении полета и расстоянии до целей.
Различные модули БПФ имеются в наличии практически в любом пакете прикладных программ, предназначенных для научных исследований, например в Maple, MATLAB, GNU Octave, MathCAD, Mathematica. Специалист должен понимать процесс преобразования Фурье и уметь грамотно его применять для решения поставленных задач, где это необходимо.
Первая программная реализация алгоритма БПФ была осуществлена в начале 60-х годов XX века в вычислительном центре IBM Джоном Кули под руководством Джона Тьюки. В 1965 году ими же была опубликована статья, посвященная алгоритму быстрого преобразования Фурье. Данный метод лег в основу многих алгоритмов БПФ и получил название по фамилиям разработчиков – Cooley-Tukey. С тех пор было выпущено достаточно много различных публикаций и монографий, в которых разрабатываются и описываются различные методы и алгоритмы БПФ, снижающие количество выполняемых операций, уменьшающие энергетические затраты и ресурсы и т.д. На сегодняшний день БПФ – это название не одного, а большого ряда различных алгоритмов, предназначенных для быстрого вычисления преобразования Фурье.
Теория
Я не буду подробно рассказывать теорию из курса радиотехнического факультета типа «Цифровая обработка сигналов». Вместо этого я приведу подборку самых полезных источников, где можно познакомиться как с теоретическими изысканиями, так и с практическими выкладками и особенностями реализации тех или иных алгоритмов БПФ.
Алгоритм
Узел БПФ выполнен по алгоритму Кьюли-Туки с основанием 2. Все вычисления для такой реализации сводятся к многократному выполнению базовой операции «бабочка». Метод преобразования – по конвейерной схеме с частотным прореживанием (для БПФ) и временным прореживанием (для ОБПФ). В алгоритме применяется схема двукратного параллелизма. Такой подход позволяет производить обработку непрерывного потока комплексных отсчетов с АЦП, частота дискретизации которого в 2 раза выше тактовой частоты обработки. То есть «бабочка» БПФ за один такт производит вычисление сразу для двух комплексных отсчетов. Если использовать 4- или 8-кратный параллелизм, то возможна обработка потока данных от АЦП или любого другого источника на частоте в 4 и 8 раз выше, чем частота обработки. Такие схемы часто применяются в задачах полифазного преобразования Фурье (Polyphase FFT) и представляют особый интерес.
Для экономии RAMB памяти в кристалле ПЛИС, начиная с определенной стадии БПФ (при NFFT > 4096 точек) применяется линейная интерполяция поворачивающих коэффициентов – разложение в ряд Тейлора до первой производной. Это позволяет вместо хранения всего набора коэффициентов использовать лишь часть из них, а остальные получать путем приближенного вычисления из исходного набора. Жертвуя ресурсами примитивов DSP48, производится экономия ресурсов блочной памяти RAMB, что для узлов БПФ является критичным местом в любой аппаратной реализации на ПЛИС. Об этом подробнее будет рассказано далее.
Структурная схема
В структуре реализованного узла БПФ можно выделить 3 функциональных узла: преобразование данных из целочисленного типа в специальный формат с плавающей точкой, входной буфер для записи отсчетов сигнала и ядро БПФ, которое содержит различные законченные узлы специального назначения.
Схематический вид синтезированного проекта: Input buffer + FP converters + FFT Core
Для увеличения эффективности все вычисления проводятся в специальном 23-битном формате с плавающей запятой FP23. Это прогрессивная реализация алгоритмов FP18 и FP27, на базе которых построена вся логика. Для формата FP23 характерны следующие особенности: разрядность слова – 23 бит, мантиссы – 16, экспоненты – 6 и знака – 1. Формат FP23 специально адаптирован к архитектуре ПЛИС и учитывает внутренние особенности работы блоков кристалла, таких как универсальный блок цифровой обработки DSP48 и блоки памяти RAMB18. Применение формата с плавающей запятой обеспечивает высокую точность обработки сигналов с АЦП вне зависимости от их амплитуды и позволяет избежать вычислительной ошибки при масштабировании данных, свойственной системам с целочисленным аппаратным вычислением с ограничением по разрядности вычислений. Почитать о нём можно в моей предыдущей статье.
На следующем рисунке изображена конвейерная схема вычисления БПФ для последовательности длины N=2^n. Она содержит:
Конвейер ядра БПФ построен так, что данные на его вход должны поступать в естественном порядке, а на выходе БПФ формируется поток данных в разрядо-инверсном порядке. Для ОБПФ все наоборот – данные на входе в двоично-инверсном порядке, а на выходе в естественном или натуральном порядке. В этом состоит главное преимущество этой связки БПФ и ОБПФ по сравнению с готовыми ядрами от Xilinx, для которых данные на входе должны быть строго в натуральном порядке, а данные на выходе зависят от включенной опции.
Что такое двоично-инверсный порядок и как он получается из натурального порядка наглядно демонстрирует следующая картинка (для последовательности N = 8 отсчетов):
Входной буфер
Исходный код на VHDL для реализации памяти буфера или линий задержки достаточно прост и по сути осуществляет работу двухпортовой памяти:
Генераторы поворачивающих коэффициентов
Для каждой стадии вычисления бабочки нужно разное количество коэффициентов. Например, для первой стадии нужен всего 1 коэффициент, для второй стадии 2, для третьей 4 и т.д. пропорционально степени двойки. В связи с этим поворачивающие коэффициенты реализуются на базе распределенной (SLICEM) и внутренней (RAMB) памяти FPGA в виде ROM-памяти, которая хранит отсчеты синуса и косинуса. Для экономного хранения используется приём, позволяющий сократить ресурсы памяти. Он заключается в том, что с помощью четверти периода синуса и косинуса можно построить весь период гармонического сигнала, используя лишь операции со знаком и направлением счета адреса памяти. При необходимости можно хранить лишь восьмую часть коэффициентов, а остальные участки получать путём переключения источника данных гармонических сигналов между собой и изменением направления счетчика. В текущей реализации это не приносит выигрыша производительности и незначительно экономит ресурс блочной памяти, причем существенно увеличивает объем занимаемых логических ресурсов кристалла.
Пример фомирования косинуса:
Коэффициенты хранятся в целочисленном формате разрядностью 16 бит и уже после извлечения из памяти они переводятся в формат FP23. Мной была проведена оценка производительности для схем с целочисленным форматом и с форматом в плавающей точке. Практика показала, что первый вариант в 1.5 раза экономит память кристалла, при этом никак не ухудшается производительность всего ядра, а добавленная задержка на преобразование форматов на некоторых стадиях даже вносит некоторые преимущества (выравнивание задержек по данным и коэффициентам для бабочки с децимацией по частоте).
Хранение поворачивающих коэффициентов для малых длин БПФ осуществляется в распределенной памяти ПЛИС в ячейках SLICEM до стадии, когда необходимо хранить 512 комплексных отсчетов с суммарной разрядностью 32 бит. При больших длинах БПФ используется блочная память кристалла RAMB18, причем для хранения 1024 пар отсчетов необходимо использовать всего 2 блока RAMB18, что эквивалентно 36*1K = 16*2*1K = 18K * 2. Отметим, что 1024 коэффициента преобразуются в 2048 с помощью описанного ранее метода частичного хранения данных, а с учётом двукратного параллелизма Radix-2, это позволяет обслуживать БПФ длиной NFFT = 4096 отсчетов.
Для длин БПФ NFFT > 4096 отсчетов применяется разложение коэффициентов в ряд Тейлора до первой производной, что позволяет с достаточно высокой точностью рассчитывать поворачивающие коэффициенты и дополнительно экономить память ПЛИС. Опустим некоторые теоретические выкладки и перейдем непосредственно к практическим особенностям вычисления.
Для больших значений NFFT поворачивающие коэффициенты хранятся не напрямую в блочной памяти ПЛИС, а получаются путём расчета по методу Тейлора. Расчётные формулы для действительной и мнимой части поворачивающих коэффициентов в упрощенном виде приведены ниже:
На рисунке приведена упрощенная схема реализации вычислений коэффициентов по схеме Тейлора (счетчик адреса используется для извлечения коэффициентов из памяти и математических операций с данными)
Так как вычисления поворачивающих коэффициентов производятся с помощью математических действий и извлечения данных из блочной памяти, то каждая стадия хранения коэффициентов занимает ресурсы DSP48 и RAMB18. Для представленных расчетных формул был написан алгоритм, использующий 2 операции умножения гармонических функций и 1 операцию умножения на значение счетчика, что эквивалентно 3 блокам DSP48.
Если бы в ядре не использовалась схема Тейлора, то для каждой следующей стадии ресурсы блочной памяти росли бы пропорционально степени 2. Для 4096 отсчетов затрачивается 4 примитива RAMB, для 8192 отсчетов — 8 примитивов и т.д. При использовании алгоритма Тейлора, количество примитивов блочной памяти всегда остается фиксированным и равным 2.
Код для создания коэффициентов синуса и косинуса строится на базе VHDL-функции (необходимо использовать пакет MATH). Функция синтезируема и успешно преобразует данные в 32-битный вектор данных в целочисленном формате.
Таблица ресурсов для реализации поворачивающих коэффициентов:
Бабочка
Каждая бабочка для БПФ и ОБПФ использует 4 умножителя и 6 сумматоров-вычитателей, реализуя функцию комплексного умножения и сложения / вычитания. Из представленных функциональных блоков только умножители используют ячейки DSP48, по 1 штуке каждый. Отсюда следует, что на одну бабочку БПФ приходится всего 4 примитива DSP48. Формулы для вычисления бабочки с прореживанием по частоте и по времени приведены в источниках выше. Реализуются бабочки достаточно просто. Ресурсов блочной памяти бабочка не занимает. Подводный камень здесь простой и легко обходится: следует учитывать задержки на вычисления в процессе расчета данных и выгрузки поворачивающих коэффиицентов Wn. Для БПФ и ОБПФ эти задержки — разные!
Линии задержки
Кросс-коммутаторы и линии задержки реализуют перестановку данных в требуемый порядок для каждой стадии БПФ. Самое подробное описание алоритма перестановки приведено в книге Рабинера и Голда! Используют распределенную или блочную память ПЛИС. Никаких трюков для экономии памяти здесь, к сожалению, провести нельзя. Это самый неоптимизируемый блок и реализуется как есть.
Таблица ресурсов для реализации линий задержки в общем виде:
Позволю себе вытащить картинку из книги, в которой показан процесс двоичной перестановки в линиях задержки на разных стадиях для NFFT = 16.
На C++ этот алгоритм реализуется так:
На бабочку поступают отсчеты A и B с номерами jN и jN+iN, а коэффициенты WW поступают с номерами ii*CNT_jj. Для полного понимания процесса достаточно взглянуть на схему двоичной перестановки и пример из книги.
Общий объем ресурсов
Дальнейшие действия достаточно просты — все узлы необходимо правильно соединить между собой, учесть задержки на выполнение различных операций (математика в бабочках, выгрузка коэффициентов для разных стадий). Если все сделать правильно, в конечном результате у вас получится готовое рабочее ядро.
В следующей таблице представлен расчет ресурсов для ядра БПФ FP23FFTK и для ядра БПФ от Xilinx (опции Floating point, Radix-2, Pipelined Streaming I/O). В таблице для ядра Xilinx приведены две колонки ресурсов для блочной памяти: (1) — без преобразования порядка из двоично-инверсного в натуральный (bitreverse output data) и (2) — с преобразованием (natural output data).
Как видно из таблицы, ядро FP23FFTK занимает в 2.5 раза меньше примитивов DSP48 при NFFT = 64K, что обусловлено в первую очередь форматом данных с урезанной мантиссой и экспонентой (FP23 vs FP32). Кроме того, ядро занимает в 2.5 раза меньше компонентов блочной памяти для опции bitreverse и в 4 раза меньше для опции natural в ядре Xilinx. Обосновать это можно усеченным форматом данных, но он дает выигрыш лишь в 1.5 раза. Остальные улучшения связаны с особенностями хранения поворачивающих коэффициентов и использованием алгоритма Тейлора.
Пример: ядро БПФ от Xilinx обязано принимать данные на входе в натуральном порядке (особенность ядра!), поэтому для связки БПФ + ОБПФ ядер Xilinx при NFFT = 64K потребуется
1600 ячеек блочной памяти, а для той же связки в формате FP23FFTK всего лишь
400 ячеек RAMB, поскольку для ОБПФ не требуется переводить данные в естественноую форму, а на его выходе данные уже в натуральном порядке. Эта особенность позволяет строить компактные фильтры сжатия (связка БПФ+ОБПФ) на быстрых свертках в небольших кристаллах ПЛИС без потери производительности!
Ниже приведен лог синтеза ядра БПФ для NFFT = 65536 точек:
Производительность ядра
В силу того, что я ограничен в железе, ядро БПФ тестировалось только на двух кристаллах: Virtex-6 (XC6VSX315T) и Kintex-7 (XC7K325T).
Для связки БПФ+ОБПФ при NFFT = 64K отсчетов на Xilinx FPGA Virtex-6 SX315T удалось добиться стабильной работы фильтра на частоте Fdsp = 333 MHz. Ядро БПФ от Xilinx также работало на этой частоте, но объем занимаемых ресурсов был существенно выше.
Для ПЛИС Kintex-7 реализована стабильная многоканальная схема с независимыми фильтрами при NFFT = 8K, частота обработки также равна Fdsp = 333 MHz.
К сожалению, на частотах выше 333МГц и на ПЛИС других семейств проверка работы узлов не проводилась.
В таблице ниже приведены значения задержек в тактах от входа до выхода ядра (полное вычисление пачки длиной NFFT отсчетов) для разных длин БПФ. Как видно из таблицы, для Xilinx и здесь результаты неутешительные. С помощью ядра FP23FFTK удалось в
2.5 раза сократить время полного вычисления БПФ! А если ещё включить перевод в натуральный порядок в IP Xilinx, то значения будут ещё больше.
Примеры реализации на ПЛИС
1400 DSP48). 4x FP23FFTK, NFFT = 16K
1400 DSP48). 16x FP23FFTK, NFFT = 16K
3. БПФ + ОБПФ 64К (большой фильтр сжатия). ПЛИС: XC7VX1140TFLG-2 (
4. Рисунок случайной разводки БПФ (напоминает бабочку):
Проверка ядра
Для моделирования и отладки ядра БПФ в формате с плавающей точкой на ПЛИС применялись разные средства разработки.
А) Тестирование RTL-модели ядра БПФ проводилось с помощью САПР Xilinx Vivado и Aldec Active-HDL. Несмотря на высокую производительность Vivado, она имеет несколько недостатков, один из которых – плохие средства редактирования кода. Вроде бы продукт постоянно развивается, но некоторые полезные примочки до сих пор отсутствуют в программе, поэтому исходный код написан в Notepad++, настроенный под работу с VHDL/Verilog файлами. В отличие от Vivado, Active-HDL моделирует намного быстрее, а также позволяет сохранять временные диаграммы после выхода из приложения. Modelsim в работе не применялся за неимением лицензии 🙂
Б) Тестирование программной модели ядра БПФ было проведено в Microsoft Visual Studio, для чего на языке C++ было написано приложение, повторяющее RTL-модель, но без задержек и тактовых частот, что позволило достаточно быстро и эффективно отлаживаться на разных стадиях проектирования (генераторы поворачивающих коэффициентов, перестановочные коммутационные узлы, математические операции, реализация алгоритма Тейлора и полное законченное ядро БПФ).
В) Полное тестирование проводилось в Matlab / GNU Octave. Для отладки были созданы скрипты с различными тестовыми сигналами, но идеальным для визуального моделирования оказался простейший ЛЧМ-сигнал с различными настройками девиации, амплитуды, смещения и других параметров. Он позволяет проверить работу БПФ на всем участке спектра, в отличие от гармонических сигналов. При тестировании синусоидальными сигналами, я несколько раз попадал в ловушку, которую устраняет применение ЛЧМ-сигнала. Если подать синусоидальный сигнал определенной частоты на вход БПФ, то на выходе я получал хорошую гармонику на нужной частоте, но стоило мне изменить период входной синусоиды – возникали ошибки. Природу этих ошибок в процессе отладки RTL-кода отследить было непросто, но затем я нашёл ответ: неправильные задержки в узлах бабочек и поворачивающих коэффициентов на некоторых стадиях вычислений. Использование ЛЧМ-сигнала устранило эту проблему и позволило подобрать правильные задержки на каждой стадии вычисления БПФ. Также с помощью m-скриптов проводилось сравнение работы C++ и RTL-моделей, а также проверялась разница в вычислениях в формате с плавающей точкой FP23 и в формате float/double.
Алгоритм тестирования
Этот процесс может показаться несколько рутинным, но именно в такой последовательности мне удалось добиться правильности работы всех узлов БПФ. Возможно, он поможет и вам, если вы будете пользоваться ядром в своих проектах.
1. Запустить скрипт Matlab / Octave для создания эталонного сигнала. Вы можете управлять следующими переменными:
После проведения этих магических действий на экране отразятся графики входного сигнала, и графики прохождения сигнала через узлы БПФ и ОБПФ. Для тестирования только одного узла БПФ необходимо взять другой m-скрипт из каталога math и сделать некоторые изменения в исходных файлах.
Визуальная проверка C++ и RTL-модели (связка БПФ + ОБПФ):
Тестовый ЛЧМ-сигнал с белым шумом (модель в Vivado)
БПФ входного сигнала:
Еще один пример тестирования (входной сигнал и результат БПФ):
Тестирование в железе (отладка в ChipScope) на ПЛИС Kintex-7:
Работа фильтра — сжатый ЛЧМ-импульс (в исходных кодах реализации фильтра сжатия нет):
Особенности ядра БПФ FP23FFTK
Исходный код
Все исходники ядра БПФ FP23FFTK на VHDL (включая базовые операции в формате FP23), модель для проверки на С++ и m-скрипты для Matlab / Octave доступны в моем профиле на гитхабе.
Дальнейшие планы
Разумеется, развитие проекта на этом не заканчивается. В моих планах на базе уже созданных моделей сделать много интересного и нового, например:
Заключение
В процессе реализации удалось получить высокопроизводительное ядро, занимающее значительно меньше ресурсов и обеспечивающее высокую производительность. В сравнении с ядром от Xilinx решение FP23FFTK выигрывает по ресурсам, общему времени задержки и, вероятно, максимальной частоте обработки данных. Кроме того, связка ядер БПФ и ОБПФ для проекта FP23FFTK не требует перевода в натуральный порядок, а максимальная длина преобразования ограничена лишь ресурсами ПЛИС!
На получение стабильного результата в железе и полную реализацию этого проекта я потратил несколько лет (чистое время не считал, увы). Проект создавался урывками, вечерами, выходными, периодически забрасывался и частично или полностью менялся подход к различным узлам. Часто некоторые идеи отбрасывали назад или сильно забрасывали вперед, причем иногда чисто случайно. Один из главных вывод, который я сделал в процессе этой работы — необходимость тщательной проверки каждой стадии проектирования независимыми средствами. Например, без модели на С++ мне иногда вообще не удавалось продвинуться в реализации, поэтому пришлось написать множество небольших тестов и отлаживать каждый кусок отдельно перед общим тестированием узла.
Надеюсь, это ядро кому-то поможет в задачах ЦОС и найдет применение в ваших проектах. Некоторые моменты я деликатно опустил и не стал делать на них акцент (расчет интегральной ошибки преобразования, шумы квантования в формате FP23 и т.д.). Выражаю благодарность dsmv2014, который всегда приветствовал мои идеи и положительно воспринимал мои авантюрные начинания по реализации тех или иных задач цифровой обработки сигналов на ПЛИС.
Реализация целочисленного БПФ на ПЛИС
Однажды меня спросили заказчики, нет ли у меня в проектах целочисленного БПФ, на что я всегда отвечал, что это уже сделано другими в виде готовых, хоть и кривых, но бесплатных IP-ядер (Altera / Xilinx) – берите и пользуйтесь. Однако, эти ядра не оптимальны, обладают набором «особенностей» и требуют дальнейшей доработки. В связи с чем, уйдя в очередной плановый отпуск, который не хотелось провести бездарно, я занялся реализацией конфигурируемого ядра целочисленного БПФ.
КДПВ (процесс отдладки ошибки переполнения данных)
В статье я хочу рассказать, какими способами и средствами реализуются математические операции при вычислении быстрого преобразования Фурье в целочисленном формате на современных кристаллах ПЛИС. Основу любого БПФ представляет узел, который носит название «бабочка». В бабочке реализуются математические действия – сложение, умножение и вычитание. Именно о реализации «бабочки» и её законченных узлов будет идти рассказ в первую очередь. За основу взяты современные семейства ПЛИС фирмы Xilinx – это серия Ultrascale и Ultrascale+, а также затрагиваются старшие серии 6- (Virtex) и 7- (Artix, Kintex, Virtex). Более старшие серии в современных проектах – не представляют интереса в 2018 году. Цель статьи – раскрыть особенности реализации кастомных ядер цифровой обработки сигналов на примере БПФ.
Введение
Ни для кого не секрет, что алгоритмы взятия БПФ прочно вошли в жизнь инженеров цифровой обработки сигналов, а следовательно, этот интрумент нужен постоянно. У ведущих производителей FPGA, таких как Altera / Xilinx уже есть гибкие конфигурируемые ядра FFT / IFFT, однако они имеют ряд ограничений и особенностей, в связи с чем мне уже не раз приходилось пользоваться собственными наработками. Вот и в этот раз мне пришлось реализовать БПФ в целочисленном формате по схеме Radix-2 на ПЛИС. В своей прошлой статье я уже делал БПФ в формате с плавающей точкой, и оттуда вы знаете, что в для реализации БПФ применяется алгоритм с двухкратным параллелизмом, то есть ядро может обрабатывать два комплексных отсчета на одной частоте. Это ключевая особенность БПФ, которая отсуствует в готовых ядрах FFT Xilinx.
Пример: требуется разработать узел БПФ, осуществляющий непрерывную работу входного потока комплексных чисел на частоте 800 МГц. Ядро от Xilinx такое не потянет (реально достижимые тактовые частоты обработки в современных ПЛИС порядка 300-400 МГц), либо потребует каким-то образом децимировать входной поток. Кастомное ядро позволяет без предварительного вмешательства тактировать два входных отсчета на частоте 400 МГц вместо одного отсчета на 800 МГц. Другой минус ядра FFT Xilinx связан с невозможностью принимать входной поток в бит-реверсном порядке. В связи с чем тратится огромный ресурс памяти кристалла ПЛИС для перестановки данных в нормальный порядок. Для задач быстрой свертки сигналов, когда два узла БПФ стоят друг за другом, — это может стать критичным моментом, то есть задача просто не ляжет в выбранный кристалл ПЛИС. Кастомное ядро БПФ позволяет принимать на входе данные в нормальном порядке, а выдавать – в бит-реверсном, а ядро обратного БПФ – наоборот, получает данные в бит-реверсном порядке, а выдает в нормальном. Экономится сразу два буфера на перестановку данных.
Поскольку большая часть материала этой статьи могла пересекаться с предыдущей, я решил сосредоточиться на раскрытии темы математических операции в целочисленном формате на FPGA для реализации БПФ.
Параметры ядра БПФ
Как и любые другие звенья в цепи, БПФ имеет входные порты управления – тактовый сигнал и сброс, а также входные и выходные порты данных. Кроме того, в ядре используется сигнал USE_FLY, который позволяет динамически выключать бабочки БПФ для процессов отладки или возжности посмотреть исходный входной поток.
В таблице ниже приведен объем занимаемых ресурсов FPGA в зависимости от длины БПФ NFFT для DATA_WIDTH = 16 и двух разрядностей TWDL_WIDTH = 16 и 24 бит.
Ядро при NFFT = 64K стабильно работает на частоте обработки FREQ = 375 MHz на кристалле Kintex-7 (410T).
Структура проекта
Схематичный граф узла БПФ показан на следующем рисунке:
Все, кто хотя бы раз сталкивался с алгоритмом быстрого преобразования Фурье, знают, что в основе этого алгоритма лежит элементарная операция – «бабочка». Она преобразует входной поток, умножая входные данные на поворачивающие коэффициенты (twiddle factor). Для БПФ есть две классические схемы преобразования – децимация по частоте (DIF, decimation-in-frequency) и децимация по времени (DIT, decimation-in-time). Для DIT алгоритма характерно разбиение входной последовательности на две последовательности половинной длительности, а для DIF алгоритма – на две последовательности четных и нечетных отсчетов длительностью NFFT. Кроме того, эти алгоритмы отличаются математическими действиями для операции «бабочка».
A, B – входные пары комплексных отсчетов,
X, Y – выходные пары комплексных отсчетов,
W – комплексные поворачивающие множители.
Поскольку входные данные – комплексные величины, то бабочка требует один комплексный умножитель (4 операции умножения и 2 операции сложения) и два комплексных сумматора (4 операции сложения). Это и есть весь математический базис, который необходимо реализовать на ПЛИС.
Умножитель
Следует отметить, что все математические операции на FPGA зачастую выполняются в дополнительном коде (2’s complement). Умножитель на ПЛИС можно реализовать двумя способами — на логике, используя триггеры и таблицы LUT, или на специальных блоках вычисления DSP48, которые давно и прочно вошли в состав всех современных ПЛИС. На логических блоках умножение реализуется с помощью алгоритма Бута или его модификаций, занимает приличный объем логических ресурсов и далеко не всегда удовлетворяет временным ограничениям на высоких частотах обработки данных. В связи с этим, умножители на ПЛИС в современных проектах практически всегда проектируются на базе DSP48 узлов и лишь изредка – на логике. Узел DSP48 – это сложная законченная ячейка, которая реализует математические и логические функции. Основные операции: умножение, сложение, вычитание, накопление, счетчик, логические операции (XOR, NAND, AND, OR, NOR), возведение в квадрат, сравнение чисел, сдвиг и т.д. На следующем рисунке представлена ячейка DSP48Е2 для семейства ПЛИС Xilinx Ultrascale+.
Путем нехитрой конфигурации входных портов, операций вычисления в узлах и выставления задержек внутри узла – можно сделать скоростную математическую молотилку данных.
Отметим, у всех топовых вендоров FPGA в среде проектирования есть стандартные и бесплатные IP-ядра для вычисления математических функций на базе узла DSP48. Они позволяют вычислять примитивные математичекие функции и выставлять различные задержки на входе и выходе узла. У Xilinx это IP-Core «multiplier» (ver. 12.0, 2018), которое позволяет конфигурировать умножитель на любую разрядность входных данных от 2 до 64 бит. Кроме того, можно задать способ реализации умножителя – на логических ресурсах или встроенных примитивах DSP48.
Оцените, сколько логики «кушает» умножитель с разрядностью входных данных на портах A и B = 64 бит. Если использовать узлы DSP48, то их потребуется всего 16.
Основное ограничение, накладываемое на ячейки DSP48 — разрядность входных данных. В узле DSP48E1, который является базовой ячейкой ПЛИС Xilinx 6 и 7 серии разрядность портов входа для умножения: «A» — 25 бит, «B» — 18 – бит, Следовательно, результат умножения представляет 43-битное число. Для семейства ПЛИС Xilinx Ultrascale и Ultrascale+ узел претерпел несколько изменений, в частности разрядность первого порта выросла на два бита: «A» — 27 бит, «B» — 18 — бит. Кроме того, сам узел называется DSP48E2.
Дабы не иметь привязку к конкретному семейству и кристаллу FPGA, обеспечить «чистоту исходного кода», и учесть все возможные разрядности входных данных, решено спроектировать собственный набор умножителей. Это позволит максимально эффективно реализовать комплексные умножители для «бабочек» БПФ, а именно — умножители и сумматор-вычитатель на базе DSP48 блоков. Первый вход умножителя — это входные данные, второй вход умножителя — поворачивающие множители (гармонический сигнал из памяти). Набор умножителей реализуется с помощью встроенной библиотеки UNISIM, из которой необходимо подключить примитивы DSP48E1 и DSP48E2 для дальнейшего их использования в проекте. Набор умножителей представлен в таблице. Следует отметить, что:
Дальнейшее увеличение разрядности не представляет интереса в рамках поставленной задачи по причинам, описанным ниже:
Разрядность поворачивающих множителей
Сумматор
Аналогично умножителю, сумматор может строиться на логических ресурсах, используя цепочку переноса, или на DSP48 блоках. Для достижения максимальной пропускной способности второй метод предпочтительнее. Один примитив DSP48 позволяет реализовать операцию сложения до 48 бит, два узла – до 96 бит. Для реализуемой задачи таких разрядностей вполне достаточно. Кроме того, примитив DSP48 обладает специальным режимом «SIMD MODE», который распараллеливает встроенный 48-битный АЛУ на несколько операций с разными данными небольшой разрядности. То есть, в режиме «ONE» используется полная разрядная сетка в 48 бит и два операнда, а в режиме «TWO» разрядная сетка разбивается на несколько параллельных потоков по 24 бита каждый (4 операнда). Этот режим, используя всего один сумматор, помогает сократить количество занимаемых ресурсов кристалла ПЛИС на небольших разрядностях входных отсчетов (на первых стадиях вычисления).
Рост разрядности данных
Операция умножения двух чисел с разрядностями N и M в двоичном дополнительном коде приводит к росту выходной разрядности до Р = N + M.
Операция сложения двух чисел с разрядностями N и M в двоичном дополнительном коде приводит к росту выходной разрядности на один бит.
Учет особенностей алгоритма
0.003% и полностью приемлимо для реализации задачи.
Усечение разрядности снизу:
Сложение/вычитание данных в операциях «бабочки» никак не подвергается минимизации и только эта операция вносит вклад в рост разрядности выходных данных на один бит на каждой стадии вычисления.
Комплексный умножитель строится аналогично – на базе умножителей и сумматора-вычитателя, однако для некоторых вариантов разрядности входных данных дополнительные ресурсы не потребуются, о чем будет рассказано ниже.
Входной буфер и линии задержки и кросс-коммутаторы аналогичны тем, что описаны в предыдущей статье. Поворачивающие множители стали целочисленными с конфигурируемой разрядностью. В остальном — глобальных изменений в проектировании ядра БПФ — нет.
Особенности ядра БПФ INT_FFTK
Исходный код
Исходный код ядра БПФ INTFFTK на VHDL (включая базовые операции и набор умножителей) и m-скрипты для Matlab / Octave доступны в моем профиле на гитхабе.
Заключение
В ходе разработки спроектировано новое ядро БПФ, обеспечивающее большую производительность по сравнению с аналогами. Связка ядер БПФ и ОБПФ не требует перевода в натуральный порядок, а максимальная длина преобразования ограничена лишь ресурсами ПЛИС. Двукратный параллелизм позволяет обрабатывать входные потоки удвоенной частоты, чего не может делать IP-CORE Xilinx. Разрядность на выходе целочисленого БПФ линейно растет в зависимости от количества стадий преобразовани.
В прошлой статье я писал о дальнейших планах: ядра БПФ Radix-4, Radix-8, Ultra-Long FFT на много миллионов точек, FFT-FP32 (в формате IEEE-754). Если коротко, то они практически все разрешены, но по тем или иным причинам в настоящий момент не могут быть вынесены на публику. Исключение составляет алгоритм FFT Radix-8, к которому я даже не присупал (сложно и лень).
В очередной раз выражаю благодарность dsmv2014, который всегда приветствовал мои авантюрные идеи. Спасибо за внимание!
UPDATE 2018/08/22
В исходные коды добавил вариант SCALED FFT / IFFT. На каждой бабочке производится усечение разрядности на 1 бит (truncate LSB). Выходная разрядность данных = входной разрядности.
В дополнение приведу два графика прохождения реального сигнала через ПЛИС, чтобы показать свойство интегральности преобразования, то есть: как влияет усечение на результат накапливания ошибки на выходе БПФ. Из теории известно, что в результате преобразования Фурье ухудшается отношение сигнал-шум при усечении входного сигнала относительно варианта без усечения.
Пример: Размах входной амплитуды — 6 бит. Сигнал — синусоида на 128 отсчете ПФ. NFFT = 1024 отсчетов, DATA_WIDTH = 16, TWDL_WIDTH = 16.
Рис. 1 Отношение сигнал-шум слабое: