Difference between revisions of "Cooley–Tukey Fast Fourier Transform, radix-2 case"

From Algowiki
Jump to navigation Jump to search
[unchecked revision][unchecked revision]
(Created page with "Основные авторы описания: А.В.Фролов, Вад.В.Воеводин (#Описание л...")
 
Line 1: Line 1:
−
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]])
+
Primary authors of this description: [[:ru:Участник:Frolov|A.V.Frolov]], [[:ru:Участник:VadimVV|Vad.V.Voevodin]] ([[#Locality of data and computations|Section 2.2]]), [[:ru:Участник:Teplov|A.M.Teplov]] (раздел [[#Scalability of the algorithm and its implementation|Section 2.4]])
  
−
== Описание свойств и структуры алгоритма ==
+
== Description of the properties and structure of the algorithm ==
  
−
=== Общее описание алгоритма ===
+
=== General description ===
  
−
'''Простой алгоритм Кули-Тьюки''' - один из вариантов '''быстрого преобразования Фурье''' для ''комплексных'' векторов с размерностью, равной степени двойки, без использования специфичных приёмов, использующихся для степеней четвёрки, восьмёрки и др. Заключается в последовательном применении метода быстрого преобразования Фурье и сведении преобразования к последовательности преобразований Фурье размерности 2 и выполнения умножений на т.н. поворотные множители. Несмотря на то, что проигрывает алгоритмам Кули-Тьюки, разлагающим степени двойки на степени 4, 8 и др. и использующим их специфику, весьма распространён, что связано с самой простой из алгоритмов БПФ записью программной реализации.
+
'''Simple Cooley-Tukey algorithm''' is a variant of '''Fast Fourier Transform''' intended for ''complex'' vectors of power-of-two size and avoiding special techniques used for sizes equal to power of 4, power of 8, etc. The algorithm repeatedly applies the Fast Fourier Transform and reduces the entire process to a sequence of Fourier transforms of size 2 and multiplications by the so-called twiddle factors. It is slower than Cooley-Tukey algorithms that express a power-of-two size as a power of 4, power of 8, etc. and then use special features of these cases. Nevertheless, this algorithm is widespread for the reason that its program implementation is the simplest of all FFT implementations.  
  
−
=== Математическое описание ===
+
=== Mathematical description ===
  
−
Исходные данные: преобразуемый комплексный вектор <math>a</math> (элементы <math>a_{i}</math>).
+
Input data: complex vector to be transformed <math>a</math> (with components <math>a_{i}</math>).
  
−
Вычисляемые данные: комплексный вектор - результат преобразования <math>b</math> (элементы <math>b_{i}</math>).
+
Output data: complex vector <math>b</math> (with components <math>b_{i}</math>), the result of the transform 
  
−
При этом размерность векторов - <math>n</math>, причём <math>n = 2^l</math>
+
The size (dimension) of the vectors is <math>n</math>; moreover, <math>n = 2^l</math>
  
−
==== Рекурсивное описание ====
+
==== Recursive description ====
  
−
Вектор записывается по строкам по 2 элемента в каждой. После этого над каждой строкой выполняется преобразование Фурье порядка 2,
+
The input vector is first written as a sequence of rows, each row containing only two components. Then each row undergoes the Fourier transform of size two. The resulting elements are multiplied by the twiddle factors <math>exp (2 \pi i(m-1)(j-1)/n)</math> (<math>m</math> is the row index, and <math>j</math> is the column index). Finally, each column is processed by the FFT of size <math>n/2</math>. For the first column, the twiddle factors are equal to 1; hence, no actual multiplication is performed. For the second column, the multiplication by the twiddle factors is combined with the Fourier transform of size two. This combination, called a
−
получившиеся элементы умножаются на поворотные множители <math>exp (2 \pi i(m-1)(j-1)/n)</math> (<math>m</math> - номер строки, <math>j</math> - номер столбца), после чего выполняется БПФ порядка <math>n/2</math> над каждым из столбцов.
+
butterfly by the FFT experts, is the basic operation of the simple Cooley-Tukey algorithm. The butterfly consists in adding two complex numbers and calculating their difference with the subsequent multiplication by another complex number. On the whole, there are <math>n/2</math> butterflies at each step, while the number of steps is <math>l-1</math>. Only sums and differences are calculated at the last step <math>l</math>.
−
Поскольку для 1-го столбца поворотные множители равны 1, то реально умножение на них не выполняется, а умножения на поворотные множители элементов второго столбца соединяются с преобразованием Фурье порядка 2. Эта комбинация, называемая "бабочкой" в среде специалистов по БПФ, и является основной операцией в простом алгоритме Кули-Тьюки. "Бабочка" состоит из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего на каждом шаге выполняется <math>n/2</math> "бабочек", а шагов - <math>l-1</math>. Последний,
 
−
<math>l</math>-й шаг вычисляет только суммы и разности.
 
  
−
==== Тригонометрические функции ====
+
==== Trigonometric functions ====
  
−
Несмотря на то, что в вычислениях используются поворотные множители <math>exp (2 \pi i(m-1)(j-1)/n)</math>, нецелесообразно вычислять их в процессе выполнения алгоритма Кули-Тьюки, поскольку вычисления косинусов и синусов (в мнимой экспоненте) тогда составили бы львиную долю вычислений алгоритма. Поэтому обычно (как и в других версиях БПФ) поворотные множители вычисляются заранее и хранятся в специальном массиве. Здесь мы будем предполагать, что алгоритм выполняется именно так.
+
Although the calculations described above use the twiddle factors <math>exp (2 \pi i(m-1)(j-1)/n)</math>, it is unreasonable to calculate them while executing the Cooley-Tukey algorithm. Otherwise, the calculations of sines and cosines would constitute the lion's share of all calculations in the algorithm. Usually (and similarly to the other versions of FFT), the twiddle factors are pre-calculated and stored in a separate array. We assume here that the algorithm is executed in exactly this form.  
  
−
=== Вычислительное ядро алгоритма ===
+
=== Computational kernel of the algorithm ===
  
−
Вычислительное ядро алгоритма составляют "бабочки", состоящие из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего их <math>(1/2) n log_{2} n </math> штук, при этом в <math>n/2</math> из них умножение не выполняется.
+
The computational kernel of the algorithm is compiled of butterflies. Each butterfly consists in adding two complex numbers and calculating their difference with the subsequent multiplication by another complex number. There are on the whole <math>(1/2) n log_{2} n </math> butterflies. No multiplications are performed in <math>n/2</math> butterflies.  
  
−
=== Макроструктура алгоритма ===
+
=== Macrostructure of the algorithm ===
  
−
Макроструктура алгоритма лучше всего описывается рекурсивно, как <math>n/2</math> преобразований Фурье порядка 2, умножение <math>n/2</math> пар комплексных чисел и затем 2 БПФ порядка <math>n/2</math>.  
+
The macrostructure of the algorithm can best of all be described in a recursive manner, namely, as <math>n/2</math> Fourier transforms of size two, the multiplication of <math>n/2</math> pairs of complex numbers, and two FFTs of size <math>n/2</math>.  
  
−
=== Описание схемы реализации последовательного алгоритма ===
+
=== Implementation scheme of the serial algorithm ===
  
−
Нерекурсивная схема организации состоит в том, что на каждом шаге (а всего их <math>log_{2} n </math>) для выполнения "бабочки" все элементы разбиваются на <math>n/2</math> пар. В зависимости от номера шага, разница координат для каждой пары элементов удваивается. На первом шагу она равна 1, на последнем - <math>n/2</math>.  
+
Under the nonrecursive organization scheme, the execution of a butterfly is preceded by partitioning the components into <math>n/2</math> pairs (there are on the whole <math>log_{2} n </math> butterflies). At each step, the difference of indices of the elements in a pair is doubled. This difference is 1 at the first step and <math>n/2</math> at the last step. The result of addition is written into the component with a lesser index, while the result of subtraction and subsequent multiplication is written into the component with a larger index.  
−
При этом результат суммы записывается в элемент с меньшим номером, а результат вычитания с последующим умножением - в элемент с большим.  
 
  
−
=== Последовательная сложность алгоритма ===
+
=== Serial complexity of the algorithm ===
  
−
Если считать только главные члены выражений для последовательной сложности алгоритма, то простой алгоритм Кули-Тьюки может быть выполнен за <math>n log_{2} n</math> операций комплексного сложения и <math>(1/2) n log_{2} n </math>операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к ''линейно-логарифмическому'' классу по последовательной сложности.
+
If the serial complexity is determined by considering only the principal terms of the number of operations, then the simple Cooley-Tukey algorithm requires <math>n log_{2} n</math> complex additions and <math>(1/2) n log_{2} n </math> complex multiplications. Thus, the simple Cooley-Tukey algorithm can be qualified as a linear logarithmic complexity algorithm.  
  
−
=== Информационный граф ===
+
=== Information graph ===
−
[[file:Cooley-Tukey Fourier Transform algorithm.png|center|thumb|600px|Простой алгоритм Кули-Тьюки для n=8. Op+ - операция сложения двух комплексных чисел. Op- - операция вычитания двух комплексных чисел и умножения результата вычитания на комплексное число (поворотный множитель). В последнем столбце операций умножение не производится. Привязка вершин выполнена по оси абсцисс - к параметру внешнего цикла, по оси ординат - к обрабатываемым элементам массива]]
+
[[file:Cooley-Tukey Fourier Transform algorithm.png|center|thumb|600px|The simple Cooley-Tukey algorithm for n=8. Op+ denotes the addition of two complex numbers, while Op- denotes the subtraction of two complex numbers followed by multiplying the result by another complex number (a twiddle factor). No multiplications occur in the last column. The vertices of the graph correspond to the parameter of the outer loop along the horizontal axis and the components of the array along the vertical axis.]]
  
−
Как видно из рисунка, этот граф не является линейным ни по размерам, ни по формулам для дуг графа. По размерам он линейно-логарифмический, а формулы дуг имеют экспоненциальные компоненты.В элементарной "бабочке" на i-м шаге каждый раз участвует пара элементов массива, у которых запись их номеров, уменьшенных на единицу, в двоичной системе различается только в i-1-м бите.
+
It is evident from the figure that this graph is not linear either in the size or in formulas for its edges. The size of the graph is linear logarithmic, while the edge formulas contain exponentials. At the i-th step, each butterfly involves two components whose indices in their binary representation differ only in the (i-1)-th bit.
  
−
=== Описание ресурса параллелизма алгоритма ===
+
=== Parallelism resource of the algorithm ===
  
−
Если считать только главные члены выражений, то простой алгоритм Кули-Тьюки имеет критический путь, состоящий из <math>log_{2} n </math> операций комплексного сложения/вычитания и <math>log_{2} n </math> операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к ''логарифмическому'' классу по параллельной сложности. По ширине ЯПФ сложность алгоритма ''линейна''.
+
If only the principal terms of the number of operations are considered, then the simple Cooley-Tukey algorithm has a critical path formed of <math>log_{2} n </math> complex additions/subtractions and <math>log_{2} n </math> complex multiplications. Thus, in terms of parallel complexity, the simple Cooley-Tukey algorithm can be placed into the ''logarithmic'' class. In terms of the parallel form width, the complexity of the algorithm is "linear''.
  
−
=== Описание входных и выходных данных ===
+
=== Description of the input and output data ===
  
−
'''Входные данные''': вектор <math>a</math> (элементы <math>a_{i}</math>).
+
'''Input data''': vector <math>a</math> (with components <math>a_{i}</math>).
  
−
'''Объём входных данных''': <math>n</math> .  
+
'''Size of the input data''': <math>n</math> .  
  
−
'''Выходные данные''': вектор <math>b</math> (элементы <math>b_{i}</math>).
+
'''Output data ''': vector <math>b</math> (with components <math>b_{i}</math>).
  
−
'''Объём выходных данных''': <math>n</math>.
+
'''Size of the output data''': <math>n</math>.  
  
−
=== Свойства алгоритма ===
+
=== Properties of the algorithm ===
  
−
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным''.  
+
It is clear that, in the case of unlimited resources, the ratio of the serial to parallel complexity is ''linear''.
  
−
При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – ''логарифмическая''.
+
The computational power of the algorithm, understood as the ratio of the number of operations to the total size of the input and output data, is ''logarithmic''.  
  
−
При этом алгоритм полностью детерминирован.  
+
The algorithm is completely determined.
  
−
Заметим, что простой алгоритм Кули-Тьюки не является оптимальным даже для векторов размером степень двойки. Однако здесь мы не рассматриваем другие алгоритмы БПФ.
+
Note that the simple Cooley-Tukey algorithm is not optimal even for vectors of power-of-two size. However, we do not consider any other FFT algorithms here.
  
 
[[Ru:Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки]]
 
[[Ru:Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки]]
  
 
[[Category:Started articles]]
 
[[Category:Started articles]]

Revision as of 13:08, 16 July 2015

Primary authors of this description: A.V.Frolov, Vad.V.Voevodin (Section 2.2), A.M.Teplov (раздел Section 2.4)

1 Description of the properties and structure of the algorithm

1.1 General description

Simple Cooley-Tukey algorithm is a variant of Fast Fourier Transform intended for complex vectors of power-of-two size and avoiding special techniques used for sizes equal to power of 4, power of 8, etc. The algorithm repeatedly applies the Fast Fourier Transform and reduces the entire process to a sequence of Fourier transforms of size 2 and multiplications by the so-called twiddle factors. It is slower than Cooley-Tukey algorithms that express a power-of-two size as a power of 4, power of 8, etc. and then use special features of these cases. Nevertheless, this algorithm is widespread for the reason that its program implementation is the simplest of all FFT implementations.

1.2 Mathematical description

Input data: complex vector to be transformed [math]a[/math] (with components [math]a_{i}[/math]).

Output data: complex vector [math]b[/math] (with components [math]b_{i}[/math]), the result of the transform

The size (dimension) of the vectors is [math]n[/math]; moreover, [math]n = 2^l[/math]

1.2.1 Recursive description

The input vector is first written as a sequence of rows, each row containing only two components. Then each row undergoes the Fourier transform of size two. The resulting elements are multiplied by the twiddle factors [math]exp (2 \pi i(m-1)(j-1)/n)[/math] ([math]m[/math] is the row index, and [math]j[/math] is the column index). Finally, each column is processed by the FFT of size [math]n/2[/math]. For the first column, the twiddle factors are equal to 1; hence, no actual multiplication is performed. For the second column, the multiplication by the twiddle factors is combined with the Fourier transform of size two. This combination, called a butterfly by the FFT experts, is the basic operation of the simple Cooley-Tukey algorithm. The butterfly consists in adding two complex numbers and calculating their difference with the subsequent multiplication by another complex number. On the whole, there are [math]n/2[/math] butterflies at each step, while the number of steps is [math]l-1[/math]. Only sums and differences are calculated at the last step [math]l[/math].

1.2.2 Trigonometric functions

Although the calculations described above use the twiddle factors [math]exp (2 \pi i(m-1)(j-1)/n)[/math], it is unreasonable to calculate them while executing the Cooley-Tukey algorithm. Otherwise, the calculations of sines and cosines would constitute the lion's share of all calculations in the algorithm. Usually (and similarly to the other versions of FFT), the twiddle factors are pre-calculated and stored in a separate array. We assume here that the algorithm is executed in exactly this form.

1.3 Computational kernel of the algorithm

The computational kernel of the algorithm is compiled of butterflies. Each butterfly consists in adding two complex numbers and calculating their difference with the subsequent multiplication by another complex number. There are on the whole [math](1/2) n log_{2} n [/math] butterflies. No multiplications are performed in [math]n/2[/math] butterflies.

1.4 Macrostructure of the algorithm

The macrostructure of the algorithm can best of all be described in a recursive manner, namely, as [math]n/2[/math] Fourier transforms of size two, the multiplication of [math]n/2[/math] pairs of complex numbers, and two FFTs of size [math]n/2[/math].

1.5 Implementation scheme of the serial algorithm

Under the nonrecursive organization scheme, the execution of a butterfly is preceded by partitioning the components into [math]n/2[/math] pairs (there are on the whole [math]log_{2} n [/math] butterflies). At each step, the difference of indices of the elements in a pair is doubled. This difference is 1 at the first step and [math]n/2[/math] at the last step. The result of addition is written into the component with a lesser index, while the result of subtraction and subsequent multiplication is written into the component with a larger index.

1.6 Serial complexity of the algorithm

If the serial complexity is determined by considering only the principal terms of the number of operations, then the simple Cooley-Tukey algorithm requires [math]n log_{2} n[/math] complex additions and [math](1/2) n log_{2} n [/math] complex multiplications. Thus, the simple Cooley-Tukey algorithm can be qualified as a linear logarithmic complexity algorithm.

1.7 Information graph

The simple Cooley-Tukey algorithm for n=8. Op+ denotes the addition of two complex numbers, while Op- denotes the subtraction of two complex numbers followed by multiplying the result by another complex number (a twiddle factor). No multiplications occur in the last column. The vertices of the graph correspond to the parameter of the outer loop along the horizontal axis and the components of the array along the vertical axis.

It is evident from the figure that this graph is not linear either in the size or in formulas for its edges. The size of the graph is linear logarithmic, while the edge formulas contain exponentials. At the i-th step, each butterfly involves two components whose indices in their binary representation differ only in the (i-1)-th bit.

1.8 Parallelism resource of the algorithm

If only the principal terms of the number of operations are considered, then the simple Cooley-Tukey algorithm has a critical path formed of [math]log_{2} n [/math] complex additions/subtractions and [math]log_{2} n [/math] complex multiplications. Thus, in terms of parallel complexity, the simple Cooley-Tukey algorithm can be placed into the logarithmic class. In terms of the parallel form width, the complexity of the algorithm is "linear.

1.9 Description of the input and output data

Input data: vector [math]a[/math] (with components [math]a_{i}[/math]).

Size of the input data: [math]n[/math] .

Output data : vector [math]b[/math] (with components [math]b_{i}[/math]).

Size of the output data: [math]n[/math].

1.10 Properties of the algorithm

It is clear that, in the case of unlimited resources, the ratio of the serial to parallel complexity is linear.

The computational power of the algorithm, understood as the ratio of the number of operations to the total size of the input and output data, is logarithmic.

The algorithm is completely determined.

Note that the simple Cooley-Tukey algorithm is not optimal even for vectors of power-of-two size. However, we do not consider any other FFT algorithms here.

Retrieved from "https://algowiki-project.org/algowiki/en/index.php?title=Cooley–Tukey_Fast_Fourier_Transform,_radix-2_case&oldid=291"