DSP FFT Вычислительная точность
arXiv eess.SP

MPARA: приближение поворотов FFT сдвигами и сложениями без умножителей

ArXiv:2611.24829

Комплексные повороты в FFT можно вычислять без обычных умножителей, но число микроповоротов приходится распределять между коэффициентами. MPARA делает это жадно по остаточной фазовой ошибке всего вектора, вместо одинаковой точности каждого вращения. Неожиданный результат: больше операций иногда ухудшает ортогональность из-за накопления ошибки усиления.

Метод. Единичные комплексные коэффициенты сначала приводятся к фазам меньше π/4 перестановками действительной и мнимой частей и сменой знаков. На итерации выбираются L элементов с наибольшим модулем тангенса остаточной фазы; их знаки образуют разреженное кодовое слово. Общий шаг выбирается как степень двойки, а фаза обновляется на arctan(2−k). Каждый ненулевой микроповорот требует двух сдвигов и двух сложений. Lmax ограничивает общий бюджет, kmax глубину сдвига. В опыте используется L=7, kmax=6 и 256-точечный radix-16 FFT с 16-точечными radix-4 частями. Коэффициенты готовятся заранее: это не адаптивное частотно-временное разложение входной речи.

Жадное распределение микроповоротов по остаточной фазовой ошибке. Единичные коэффициенты FFT: Точные комплексные повороты заданного FFT. Приведение фазы к |θ| < π/4: Перестановка частей и смена знаков. Выбрать L больших остатков: Новое: общий жадный выбор по всему вектору. Микроповорот arctan(2⁻ᵏ): Новое: бюджет; два сдвига + два сложения. Поправка усиления: Для глубин 0, 1, 2; глубже без коррекции. Приближённый FFT-256: Проверка F̂ᴴF̂/256 против единичной матрицы.
Схема по материалам статьи, алгоритм 2, разделы 3–4 и таблица 1. Показана подготовка коэффициентов, а не адаптация к текущей речи. На итерации выбирают L=7 элементов; общий бюджет Lmax и kmax=6 ограничивают приближение. Микроповорот имеет шаг arctan(2⁻ᵏ), не линейный фазовый сдвиг 2⁻ᵏ. Коррекция масштаба обязательна для точности, но эвристична; детали radix-разложения сокращены. Новое — распределение бюджета, отмечено словом.

Результаты. Качество проверяется по матрице J=F̂ᴴF̂/256, которая для ортогонального преобразования должна совпадать с единичной. Раздельно измеряются ошибки диагонали и внедиагональных элементов при примерно 4000–9000 сложений. MPARA даёт меньшую ошибку в рассмотренном диапазоне, чем сравниваемые CSD и MPGBP. Но результаты относятся к аппроксимации преобразования, а не к PESQ, распознаванию речи или качеству кодека. Приведённый после коррекции диапазон усиления одного составного поворота — 0,9887–1,0078, то есть модуль всё ещё не строго единичный.

Ограничения. В статье нет измерений FPGA/ASIC, энергии, памяти и времени обработки речевого потока. Выигрыш по числу сложений не переводится автоматически в ускорение на процессоре с быстрым умножением. Параметр L выбран поиском для конкретного FFT; перенос на другие размеры и требования к динамическому диапазону требует повторной настройки. Эвристическая коррекция амплитуды — существенная часть метода, а не необязательное косметическое улучшение.

Фишка из статьи. Таблица 1 показывает, почему нельзя оптимизировать только фазу. Микроповорот CORDIC одновременно изменяет амплитуду. Для первых трёх глубин авторы тратят дополнительные сдвиги и сложения на коррекцию, а более глубокие оставляют без неё. Числа ниже — усиление после указанной коррекции на данной глубине.

Глубина kКоррекцияУсиление
01 − 2⁻² − 2⁻⁴ + 2⁻⁶0,9944
11 − 2⁻³ + 2⁻⁶0,9957
21 − 2⁻⁵0,9986
≥3Без поправкиМежду 1 и 1,0078

Как это читать: добавленные глубокие микроповороты уменьшают фазовый остаток, но накапливают нескорректированный масштаб. Именно поэтому диагональная ошибка на рисунке 2 не обязана монотонно падать с бюджетом операций. Для банка фильтров или спектрального признакового тракта пришлось бы отдельно проверить чувствительность к этому изменению нормы.

Источник. Оригинальное название: Greedy Vector Approximation Based on Rotation for Multiplierless Complex Products. arXiv:2611.24829; полный текст PDF.

Оригинальная статья на arXiv