Моделирование реализации модуля Быстрого Преобразования Фурье (БПФ/FFT) и сравнение с аналогичным ядром от Xilinx

Введение

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

Наличие модели позволяет решить сразу несколько задач:

  • во-первых, модель позволяет оценить качественные характеристики выбранного алгоритма ещё до начала написания RTL, и, при необходимости, легко внести изменения и достаточно быстро проверить их;

  • появляется возможность быстро сравнить разные реализации алгоритмов, в том числе, со сторонними реализациями;

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

 

В данной статье описываются результаты моделирования блока БПФ собственной разработки со следующими характеристиками:

  • размер векторов - 1024 точки;

  • входные и выходные данные представлены в формате комплексных чисел, где компоненты re/im представлены значениями с фиксированной запятой в формате целых чисел со знаком (16 бит);

  • БПФ выполняется алгоритмом с прореживанием по частоте RADIX-4;

  • реализация БПФ имеет конвейерную структуру;

  • масштабирование/нормализация результатов работы каждой стадии задаётся программно.

 

Для сравнения использовалось IP-ядро FFT от Xilinx с аналогичными характеристиками,
сгенерированное с помощью "Vivado v.2018.1 (win64) Build 2188600".

 

Среды моделирования

Для моделирования и исследования характеристик использовался пакет "GNU Octave, version 8.4.0".
Для симуляции ядра FFT от Xilinx использовался "ModelSim - Intel FPGA Starter Edition 2020.1".

 

Описание исследуемых характеристик

Термины:

  • SNR (Signal-to-Noise Ratio) - отношение сигнал/шум, вычисляется как отношение мощности полезного сигнала к мощности шума. Как правило, выражается в dB и вычисляется:
    SNR(dB) = 10 * log10(P_signal/P_noisy);

  • Шум (Noisy) - отклонение полученного сигнала от идеального;

  • Для вычисления мощности комплексного значения выполняется умножение этого значения на комплексно-сопряжённое.

 

Для оценки качественных характеристик исследуемых ядер использовались следующие значения SNR:

  • минимальный (самый плохой случай) SNR - для каждого входного тестового вектора вычислялось значение SNR. После тестирования на наборе тестовых векторов выбиралось минимальное значение;

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

 

Исследование выходного спектра

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

 

Обновлённая структура исследования

Основная идея обновлённой схемы заключалась в том, чтобы в качестве полезного (референсного) сигнала при расчёте SNR использовать  результат работы функции _fft()_ из пакета Octave над входным сигналом, а в качестве шума использовалось отклонение рассчитанного спектра от референсного. Для моделирования и получения характеристик исследуемых модулей использовались два теста: тест "бегущая единица" и тест "бегущий ноль".

 

Бегущая единица

Данный тест является некоторым аналогом одноименного теста для тестирования памяти. Суть теста:

  • На вход исследуемого модуля подаётся набор тестовых векторов;

  • Генерация каждого тестового вектора выполняется следующим образом:

    • в частотной области создаётся  вектор длиной, равной размеру БПФ, заполненный значением 0;

    • для заданной частотной компоненты устанавливается ненулевое (единичное) значение. Чтобы тестовые векторы не были чисто действительными, для каждого тестового вектора осуществляется поворот значения в комплексной плоскости по следующей формуле:
      dout(n) = exp(2 * pi * i * n / fft_size);

  • Каждый тестовый вектор предназначен для проверки только одной заданной частоты;

  • Тестовые векторы генерируются для проверки всех частот (по одной) для данного размера БПФ.

Структура теста представлена на Рисунке 1.

 

Где:

  • "Test generator" - формирует тестовый вектор в частотной области в формате плавающей точки;

  • "Octave ifft()" - функция из пакета Octave, выполняет обратное БПФ в формате плавающей точки для формирования тестового вектора во временной области. Поскольку мощность во входном векторе сосредоточена только в одной точке, а в выходном распределена по всему вектору, то амплитуда выходного сигнала не будет превышать 1.0/размер БПФ;

  • "Scaling up" - выполняет масштабирование тестового вектора до 1.0 (умножение на размер БПФ), чтобы получить максимальную амплитуду тестового вектора;

  • "FP2FIX" - выполняет конвертацию тестового вектора из формата плавающей точки в формат фиксированной точки. Для этого конвертация производится умножением входного вектора на 32767. После чего выполняется округление с насыщением для каждого значения вектора;

  • "Модель БПФ" - исследуемая модель, формирует спектр в частотной области;

  • "Octave fft()" - функция из пакета Octave, формирует референсный спектр в частотной области (полезный сигнал);

  • "Scaling down" - поскольку максимальное значение в референсном спектре превышает максимальное значение, определяемое разрядностью фиксированной точки, необходимо выполнять обратное масштабирование (деление на размер БПФ);

  • "SNR calculation" - вычисление SNR.

 

Для моделирования ядра FFT от Xilinx выполнялись следующие действия:

  • "Write input vector" - в пакете Octave выполняется запись входного тестового вектора в файл;

  • "Xilinx IP sim" - выполняется симуляция ядра FFT от Xilinx в среде ModelSim с использованием тестовых векторов с предыдущего шага;

  • "Write output vector" - результат симуляции записывается в файл;

  • "SNR calculation" - вычисление SNR.

 

Для исключения переполнения при моделировании теста "бегущая единица", для обеих моделей выход каждой стадии программируется на сдвиг = 2 (в документации на Xilinx FFT это называется "Scaling Schedule"). 

При вычислении SNR для случаев, когда шум равен 0, значение "бесконечность" заменяется на фиксированное значение 400 dB.

 

Результаты

График распределения SNR в зависимости от номера тестового вектора (тестируемой частоты) для разработанной модели БПФ представлен на Рисунке 2.

 

На графике можно заметить следующие особенности:

  • для тестовых векторов для частотных компонент с номерами 0, 256, 512 и 768 значение SNR = 400 dB, т.е. шум равен 0;

  • распределение SNR на интервале [0:255] повторяется 4 раза. Другими словами, достаточно анализировать распределение только для первых 256 тестовых векторов.

Поскольку симуляция ядра FFT от Xilinx занимает много времени, а при моделировании собственной модели было определено, что достаточно рассмотреть SNR только для первых 256 тестовых векторов, то при симуляции ядра FFT от Xilinx набор тестовых векторов был ограничен первыми 256 тестовыми векторами.

 

Результаты получились следующие:
Min SNR of FFT model = 90.7772 dB
Min SNR of Xilinx FFT = 89.6613 dB
Average SNR of FFT model = 94.606 dB
Average SNR of Xilinx FFT = 94.4597 dB

 

Бегущий ноль

Основное отличие этого теста от теста "бегущая единица", заключается в формировании тестового вектора:

  • в частотной области создаётся вектор заданного размера БПФ, заполненный ненулевыми значениями по следующей формуле:

    • angle = SIZE - (1:SIZE);

    • dout = exp(2 * pi  * i / SIZE * angle);

  • для заданной частоты устанавливается нулевое значение.

 

Структура теста представлена на Рисунке 3 и имеет незначительные отличия от теста "бегущая единица":

  • "Scaling down" - тестовый вектор во временной области после вычисления обратного БПФ масштабируется вниз (умножаем на latexmath:[(fft\_size - 4)/fft\_size]). Это связано с отсутствием логики "насыщения" в реализации от Xilinx. При арифметическом переполнении выходной спектр у ядра FFT от Xilinx "разваливается". Чтобы можно было выполнить сравнение выходного спектра исследуемой модели БПФ с результатами работы ядра FFT от Xilinx, пришлось снизить амплитуду входного тестового вектора. Коэффициент был подобран экспериментальным путем;

  • при формировании референсного спектра отсутствует обратное масштабирование, чтобы получить максимальную амплитуду;

  • для получения максимальной амплитуды выходных спектров, коэффициенты масштабирования ("Scaling Schedule") для обеих моделей (исследуемой модели и ядра FFT от Xilinx) были установлены в 0.

 

 Результаты

График распределения SNR в зависимости от номера тестового вектора (тестируемой частоты) для разработанной модели БПФ представлен на Рисунке 4.

 

Распределение SNR отличается от распределения в предыдущем тесте, но можно также заметить 4-кратное повторение первого сегмента. Симуляция ядра FFT от Xilinx также выполнялась только для первых 256 тестовых векторов.

 

Результаты получились следующие:
Min SNR of FFT model = 78.5121 dB
Min SNR of Xilinx FFT = 78.5687 dB
Average SNR of FFT model = 80.2368 dB
Average SNR of Xilinx FFT = 80.2085 dB

 

Выводы

  • При использовании SNR для оценки качественных характеристик разных реализаций важно использовать одинаковые методики измерения и одинаковые входные воздействия. Сами по себе значения SNR для разных реализация без учёта того, как они были получены, это "попугаи" и "удавы".

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

  • Если говорить непосредственно о модуле БПФ, то выходной спектр очень сильно зависит от характеристик входного сигнала. Поэтому для корректного конфигурирования модуля необходимо также проводить моделирование на примерах реальных сигналов, с которыми придётся работать.

  • При использовании ядра FFT от Xilinx необходимо учитывать отсутствие логики насыщения в арифметических операциях:
    (Product specification for FFT from Xilinx: 
    When an overflow occurs in the core, the data is wrapped rather than saturated, resulting in the transformed data becoming unusable for most applications).
    Другими словами, необходимо гарантировать отсутствие переполнения при работе модуля. Это возможно или за счёт жёсткого контроля амплитуды входного сигнала, или за счёт включения дополнительного сдвига на первой (входной) стадии модуля. В обоих случаях амплитуда выходного сигнала (спектра) будет ниже возможной. Третий вариант - это использовать модуль БПФ с плавающей арифметикой.