Рекомендации по применению быстрого преобразования Фурье на микроконтроллерах

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

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

Микроконтроллеры начального уровня на ядрах Cortex-M0/M0+, как правило, не имеют аппаратного модуля операций с плавающей точкой (FPU) и часто обладают скромным объёмом RAM (десятки килобайт). Реализация БПФ на таких ядрах возможна, но с серьёзными оговорками. Здесь приходится использовать арифметику фиксированной точки (форматы Q15, Q31), где дробные числа эмулируются целочисленными операциями. Это требует от разработчика тщательного контроля за переполнением и потерей точности. Оперативная память часто становится главным ограничивающим фактором, жёстко лимитирующим максимальный размер преобразования (например, БПФ на 256 или 512 точек может быть пределом).

Перелом наступает с появлением ядер Cortex-M4 и Cortex-M33. Ключевым их отличием является наличие FPU одинарной точности и набора DSP-инструкций (SIMD – Single Instruction, Multiple Data). SIMD позволяет за одну тактовую команду выполнить одну операцию (например, умножение) над несколькими парами данных одновременно. Поскольку ядро БПФ состоит из массовых операций умножения и сложения над комплексными числами, наличие этих инструкций даёт выигрыш в производительности в разы. Именно ядра M4/M7/M33 стали рабочими лошадками для задач цифровой обработки сигналов. Объём RAM в таких микроконтроллерах также серьёзно возрастает (сотни килобайт), позволяя работать с буферами для БПФ на 1024 или 2048 точек без особого напряжения.

Венцом развития для встраиваемых DSP-задач являются микроконтроллеры на ядрах Cortex-M7. Помимо мощного FPU и SIMD, они часто оснащаются кеш-памятью первого уровня (I/D Cache) и специализированной быстрой памятью – TCM (Tightly Coupled Memory). Доступ к TCM происходит практически без задержек, что критически важно для алгоритмов, интенсивно работающих с большими массивами данных. Разместив буферы входных данных и коэффициентов БПФ в TCM, разработчик может избежать «проседаний» производительности из-за ожидания тактовых циклов при работе с основной RAM. Это архитектурное решение выводит скорость выполнения БПФ на совершенно иной уровень, позволяя обрабатывать сложные сигналы с высокой частотой дискретизации.

Чтобы грамотно оптимизировать реализацию, необходимо понимать, что именно вычисляет микроконтроллер. БПФ – не отдельное преобразование, а семейство умных алгоритмов, радикально сокращающих количество операций для вычисления Дискретного Преобразования Фурье (ДПФ). Классический ДПФ требует порядка комплексных умножений и сложений, что для N=1024 точек означает более миллиона операций. Алгоритм БПФ, наиболее часто используемый Кули-Тьюки для степеней двойки, сокращает эту сложность до операций, что для того же N=1024 даёт чуть более 10 тысяч операций – выигрыш в два порядка.

Алгоритм работает по принципу «разделяй и властвуй». Исходная последовательность из N отсчётов рекурсивно разбивается на две более короткие последовательности – с чётными и нечётными номерами. Для этих половин также вычисляется БПФ, после чего результаты особым образом «собираются» в итоговый спектр. Этот процесс разбиения продолжается до тех пор, пока не останутся минимальные преобразования размером 2 (так называемые «бабочки» – butterfly operations). Каждая операция «бабочка» включает в себя комплексное умножение на заранее рассчитанный коэффициент (так называемый «поворачивающий множитель» или twiddle factor) и комплексное сложение/вычитание.

Именно здесь кроется ключ к оптимизации. Во-первых, коэффициенты (twiddle factors) являются константами, зависящими только от размера БПФ (N). Их категорически нельзя вычислять в реальном времени – это свело бы на нет всю выгоду алгоритма. Их необходимо предварительно рассчитать и хранить в памяти программы (Flash) в виде таблицы. Во-вторых, структура алгоритма приводит к нелинейному, «перестановочному» доступу к элементам массива входных данных. Для максимальной эффективности часто используется алгоритмическая хитрость – обработка данных на месте (in-place) в одном массиве, что экономит драгоценную RAM, но требует аккуратной перестановки отсчётов либо на входе, либо на выходе.

На практике конвейер обработки выглядит следующим образом. Первым и самым важным этапом является предварительная подготовка. Помимо расчёта таблицы коэффициентов, необходимо выбрать и предрасчитать окновную функцию (Ханна, Хэмминга). Применение окна к данным перед БПФ – обязательный шаг для борьбы с эффектом спектрального «размазывания», возникающим из-за обрыва непериодического сигнала на краях анализируемого окна. На этапе сбора данных от АЦП критически важно обеспечить частоту дискретизации (Fs) как минимум вдвое превышающую максимальную частоту в сигнале (теорема Котельникова) и использовать антиалиасный фильтр.

Сам вызов БПФ в современных проектах почти никогда не реализуется «с нуля». Для ядер ARM Cortex-M существует высокооптимизированная библиотека CMSIS-DSP, чьи функции написаны с использованием ассемблерных вставок и заточены под использование SIMD инструкций и FPU. Использование этой библиотеки – самый разумный и эффективный путь. После выполнения БПФ в выходном комплексном массиве содержится частотная информация. Для большинства задач анализа требуется амплитудный спектр, который получается расчётом модуля каждого комплексного отсчёта: . Для этой операции в CMSIS-DSP также есть оптимизированные функции. Важно помнить, что для вещественного входного сигнала спектр является симметричным, и полезная информация содержится только в первой половине массива (до частоты Fs/2).