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