Бабочка (БПФ)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/98/Butterfly-FFT.png/200px-Butterfly-FFT.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cb/DIT-FFT-butterfly.png/300px-DIT-FFT-butterfly.png)
Бабочка — элементарный шаг в алгоритме Кули-Тюки (англ. Cooley–Tukey FFT) вычисления быстрого преобразования Фурье.
Время работы шага Бабочка определяет длительность вычисления преобразования Фурье.[1]
В простейшем варианте (Radix-2 butterfly) является двухточечным преобразованием.
Формула для вычисления «Бабочки»:[1]
Обозначения: , – исходные точки; , – точки результата, – комплексный коэффициент.
Для БПФ данных размером , требуется произвести вычислений операции 2-Radix «Бабочка».[1][2][3]
Иногда используются операции бабочка более высокого порядка: Radix-4, Radix-8. Radix-4 является примерно на 20% более эффективным для преобразования Фурье большого количества данных. Операция большего порядка чем 8 практически не используется из-за незначительных приростов производительности и трудностей в реализации (ресурсоемкости).[4][5]
Сходная структура может применяться в реализациях алгоритма Витерби (операция ACS - Add-Compare-Select)[6].
Примечания
[править | править код]- ↑ 1 2 3 Реализация целочисленного БПФ на процессорах с архитектурой ARM // Схемотехника №3 март 2001
- ↑ Л. Рабинер и Б. Гоулд "Теория и применение цифровой обработки сигналов".
- ↑ Архивированная копия . Дата обращения: 29 декабря 2012. Архивировано из оригинала 14 августа 2003 года.
- ↑ http://www.ece.ucdavis.edu/~bbaas/281/slides/Handout.fft2.pdf Архивная копия от 6 декабря 2012 на Wayback Machine Higher Radices
- ↑ http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html Архивная копия от 30 апреля 2010 на Wayback Machine Radix-4 FFT Algorithm; Figure TC.3.9 Basic butterfly computation in a radix-4 FFT algorithm
- ↑ Implementing the Viterbi Algorithm in Today's Digital Communications Systems Архивная копия от 25 декабря 2012 на Wayback Machine // Design And Reuse (EETimes): "Viterbi ACS instructions are based on the Viterbi butterfly structure and symmetry. The structure is called “butterfly” due to its physical resemblance to the animal.", Figures 8-10
Ссылки
[править | править код]- Chapter 12: The Fast Fourier Transform (The Scientist and Engineer's Guide to Digital Signal Processing, By Steven W. Smith); перевод
Это заготовка статьи по математике. Помогите Википедии, дополнив её. |