Схема бабочки

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

Полный текст статьи:

Схема бабочки — Википедия