Бабочка (БПФ)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Диаграмма потока данных соединяет входы x (слева) с выходами y (справа) для «бабочки» алгоритма БПФ. Диаграмма напоминает бабочку (на рисунке приводится бабочка Морфо)
БПФ по основанию 2 с прореживанием по времени разбивает ДПФ размерности N на два ДПФ размерности N/2 c последующим объединяющим шагом, состоящим из множественных операций "бабочка".

Бабочка — элементарный шаг в алгоритме быстрого преобразования Фурье Кули-Тюки (Cooley–Tukey FFT (англ.)русск.).

Время работы шага Бабочка определяет длительность вычисления преобразования Фурье.[1]

В простейшем варианте (Radix-2 butterfly) является двухточечным преобразованием.

Формула для вычисления "Бабочки":[1]

Y_1 = X_1 + X_2 \cdot W

Y_2 = X_1 - X_2 \cdot W

Обозначения: X_1, X_2 – исходные точки; Y_1, Y_2 – точки результата, W – комплексный коэффициент.

Для БПФ данных размером 2^k = N, требуется произвести N \cdot log_2 N вычислений операции 2-Radix "Бабочка".[1][2][3]

Иногда используются операции бабочка более высокого порядка: Radix-4, Radix-8. Radix-4 является примерно на 20% более эффективным для преобразования Фурье большого количества данных. Операция большего порядка чем 8 практически не используется из-за незначительных приростов производительности и трудностей в реализации (ресурсоемкости).[4][5]

Сходная структура может применяться в реализациях алгоритма Витерби (операция ACS - Add-Compare-Select)[6].

Примечания[править | править вики-текст]

  1. 1 2 3 Реализация целочисленного БПФ на процессорах с архитектурой ARM // Схемотехника №3 март 2001
  2. Л. Рабинер и Б. Гоулд "Теория и применение цифровой обработки сигналов".
  3. http://www.ee.ucla.edu/~ingrid/Courses/ee201aS03/lectures/ee201a_lec16Viterbi.pdf
  4. http://www.ece.ucdavis.edu/~bbaas/281/slides/Handout.fft2.pdf Higher Radices
  5. http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html Radix-4 FFT Algorithm; Figure TC.3.9 Basic butterfly computation in a radix-4 FFT algorithm
  6. Implementing the Viterbi Algorithm in Today's Digital Communications Systems // 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

Ссылки[править | править вики-текст]