Схема бабочки
- “Бабочка” – это часть вычислений в алгоритмах быстрого преобразования Фурье (БПФ), объединяющая результаты меньших ДПФ в больший ДПФ или наоборот.
- Название “бабочка” происходит от формы диаграммы потока данных в случае radix-2.
- Термин “бабочка” чаще всего используется в контексте алгоритма БПФ Кули-Тьюки, который рекурсивно разбивает БПФ на r преобразований меньшего размера m.
- Меньшие DFT объединяются с помощью бабочек размера r, которые сами по себе являются DFT размера r, умноженными на корни из единицы.
- В случае алгоритма Кули-Тьюки с системой счисления-2 “бабочка” – это просто DFT размера 2, принимающее два входных сигнала и выдающее два выходных сигнала.
- “Бабочка” также может быть использована для улучшения случайности больших массивов частично случайных чисел.
Полный текст статьи: