Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Бабочки в алгоритмах БПФ
butterfly diagrams in FFT algorithms
В контексте алгоритмов быстрого преобразования Фурье (БПФ) бабочка – это часть вычисления, объединяющая результаты меньших дискретных преобразований Фурье (ДПФ) в большее ДПФ или, наоборот, разбивающая большее ДПФ на подпреобразования. Название «бабочка» происходит от формы диаграммы потока данных в случае радикса 2, как описано ниже. Считается, что первое упоминание этого термина в печати относится к техническому отчету MIT 1969 года. Та же структура также встречается в алгоритме Витерби, используемом для поиска наиболее вероятной последовательности скрытых состояний. Чаще всего термин «бабочка» используется в контексте алгоритма Кули–Тьюки БПФ, который рекурсивно разбивает ДПФ составного размера n = rm на r меньших преобразований размера m, где r – «радикс» преобразования. Эти меньшие ДПФ затем объединяются посредством бабочек размера r, которые сами являются ДПФ размера r (выполняемыми m раз над соответствующими выходами подпреобразований) и предварительно умножаются на корни из единицы (известные как факторы поворота). (Это случай «децимации по времени»; шаги также можно выполнять в обратном порядке, известном как «децимация по частоте», где бабочки выполняются первыми и затем умножаются на факторы поворота. Подробнее см. статью о БПФ Кули–Тьюки.)
In the context of fast Fourier transform algorithms, a butterfly is a portion of the computation that combines the results of smaller discrete Fourier transforms (DFTs) into a larger DFT, or vice versa (breaking a larger DFT up into subtransforms). The name "butterfly" comes from the shape of the data flow diagram in the radix 2 case, as described below. The earliest occurrence in print of the term is thought to be in a 1969 MIT technical report. The same structure can also be found in the Viterbi algorithm, used for finding the most likely sequence of hidden states. Most commonly, the term "butterfly" appears in the context of the Cooley–Tukey FFT algorithm, which recursively breaks down a DFT of composite size n = rm into r smaller transforms of size m where r is the "radix" of the transform. These smaller DFTs are then combined via size r butterflies, which themselves are DFTs of size r (performed m times on corresponding outputs of the sub transforms) pre multiplied by roots of unity (known as twiddle factors). (This is the "decimation in time" case; one can also perform the steps in reverse, known as "decimation in frequency", where the butterflies come first and are post multiplied by twiddle factors. See also the Cooley–Tukey FFT article.)
Другие применения
Бабочка также может быть использована для повышения случайности больших массивов частично случайных чисел, обеспечивая причинно-следственную связь каждого 32- или 64-битного слова со всеми остальными словами посредством выбранного алгоритма хеширования, так что изменение любого бита может повлечь изменение всех битов в массиве.
The butterfly can also be used to improve the randomness of large arrays of partially random numbers, by bringing every 32 or 64 bit word into causal contact with every other word through a desired hashing algorithm, so that a change in any one bit has the possibility of changing all the bits in the large array.