Диссертация (1150736), страница 32
Текст из файла (страница 32)
В данном разделе собраны наиболее быстрые алгоритмы вещественного БПФ и двойной интерполяции.Введём обозначения. БПФ размера определяется матрицей ℱ =−( )−1,=0 , где = 2. Матрица ℱ = ℱ симметрична. Обратная к нейматрица обладает свойствами = ℱ−1 = −1 ℱ̄ = −1 (¯ ).Пусть 0 , . . ., −1 — стандартные орты в R .
Введём матрицу отражения = (0 , −1 , . . . , 1 ), матрицу инверсии = (−1 , . . . , 0 ) и диагональнуюматрицу = diag{( )−1=0 }. Тогда, очевидно, ℱ = ℱ̄ = ,¯ . ℱ = ℱ̄ Если вектор вещественный, то вектор = ℱ обладает свойствомсопряжённо-чётной симметрии = ¯, которое будем обозначать CE(conjugate-even symmetry). Для чётного оно состоит в том, что компоненты 0 и /2 вещественные и − = ¯ при 1 ≤ < /2.Далее C , C обозначает сложность операций комплексного сложения икомплексного умножения, соответственно, а R , R — сложность аналогичных вещественных операций.
Если сложность вещественного умножения исложения одинаковы, то эта сложность обозначается R .203Будем предполагать, что комплексное сложение и умножение выполняетсяобычным способом, и поэтомуC = 2R ,C = 2 R +4 R = 6R .В некоторых случаях архитектура вычислительного устройства позволяет учитывать, что умножение на 1 и на не имеет сложности, а умножение на /4имеет сложность 2 R +2 R = 4R .Сложность комплексного и вещественного БПФ порядка обозначим, соответственно, () и (). Очевидно, что сложность циклической свёртки равна 3()+ C в комплексном случае и 3 ()+(/2−1) C +2 R в вещественном случае. Далее будем считать, что есть степень 2, и поэтому умножениеи деление на сводится к сдвигу и не имеет сложности.D.1Комплексный алгоритм Radix-2Здесь и далее в этом разделе будут использоваться следующие обозначения.
Если — вектор длины = 2, то 0 и 1 обозначают вырезки, соответственно, из первых компонент и последних компонент вектора . Вектордлины из чётных компонент вектора обозначается ′0 , а из нечётных компонент — ′1 .Введём матрицу перестановки размера , для которой =col(′0 , ′1 ). Докажем, что тогда при = 2:(︃)︃ℱℱ, ℱ =′′−ℱ ℱ ′где = diag{( )−1=0 }. Действительно, пусть — номер строки, а — номерстолбца. Тогда2 = ,0 ≤ < , (2+1) = ,0 ≤ < ,(2+1)(+) = −(2+1) ,0 ≤ < ,0 ≤ < ,0 ≤ < ,Поскольку ℱ = ( ℱ) , то(︃)︃ (︃ )︃ (︃ )︃ (︃)︃′ℱ ℱ′000 + 1ℱ ===,′ℱ −ℱ′110 − 12040 ≤ < .(︃ )︃01(︃=ℱ ′0′ℱ ′1)︃.На этом равенстве основан стандартный алгоритм БПФ radix-2 во временнойобласти.
Обычно алгоритм начинается с перестановки битовой инверсииΠ = diag{/2 , /2 } · · · diag{4 , . . . , 4 }.Стандартный алгоритм radix-2 в частотной области основан на формуле(︃ )︃(︃)︃(︃ )︃ (︃)︃′0ℱ 000 + 1=ℱ=,=.′1′ℱ 110 − 1В нём сначала выполняются бабочки, а потом перестановка битовой инверсии.Лемма 36 Сложность стандартного алгоритма radix-2 в частотной области или во временной области в реализации, не учитывающей особенностейумножения на 1, и (1 ± )/2, равна = 2 ≥ 4.() = C + ( − 1) C = (3 − ) R +(2 − 2) R ,2При учёте особенностей умножений на 1, и (1 ± )/2 сложность стандартного алгоритма radix-2 равна() = (3 − 3 + 4) R +(2 − 7 + 12) R , = 2 ≥ 4.Начальные данные: (1) = 0, (2) = 2 C .Доказательство.
Особенности умножения на 1, и (1 ± )/2 учитывают′. Без учёта особенностей сложность удовлетворяется при умножении на рекуррентному уравнению() = 2(/2) + C +/2 C ,(2) = 2 C .Решение этого уравнения при = 2 ≥ 2 есть() = C + ( − 1) C = (3 − ) R +(2 − 2) R ,2что совпадает с заключением леммы.При учёте особенностей умножений на 1, и (1 ± )/2 рекуррентная формула имеет вид() = 2(/2) + (3 − 4) R +(2 − 12) R ,(4) = 16 R ,а решение при = 2 ≥ 4 есть() = (3 − 3 + 4) R +(2 − 7 + 12) R .205D.2Комплексный алгоритм Split-Radix в частотной области′Пусть = 2 = 4ℓ. Кроме диагональных матриц размера и раз′′ 4′ 2мера введём матрицу ℓ′′ = diag{( )ℓ−1=0 }. Очевидно, что (ℓ ) = (ℓ ) =′ℓ и что = diag{ℓ′′ , ℓ′′ }.В алгоритме radix-2 в частотной области разложим бабочку, применённуюдля вычисления 1′ , повторно.
Введём обозначения = 1′ и = 1 . Тогда(︃ )︃(︃)︃ (︃)︃ (︃)︃′′′′0′ℱℱℱℓℓℓ ℓ 0ℓ 0′= 1′ = ℱ 1 ==,′′′′′1ℓ 1ℱℓ ℓ −ℱℓ ℓℱℓ ℓ′ ℓ′′ ¯1¯ ′′ и ℓ ℱ̄ℓ = ℱℓ ℓ . Поэтомугде 0 = 0 + 1 , 1 = ¯0 + ¯1 . При этом ℓ′ ℓ′′ = ℓ ℓ1′ = ℓ ℱℓ ℓ′′ 1 .Полученная формула определяет рекуррентное правило расчёта компоненты 1′ в алгоритме БПФ в частотной области. Компонента 0′ вычисляется попрежнему, как ℱ 0 .Лемма 37 Сложность комплексного алгоритма split-radix в частотной области равна)︂(︂)︂(︂16243828 − − (−1) + 2 R + − + (−1) + 6 R ,() =399399где = 2 ≥ 4, всего 4 − 6 + 8 вещественных операций. Начальные значения: (1) = 0, (2) = 4 R , (4) = 16 R .Доказательство. Из полученной рекуррентной формулы следует, что сложность алгоритма удовлетворяет уравнению() = (/2) + 2(/4) + C +2ℓ C +2(ℓ − 2) C +2(2 R +2 R )= (/2) + 2(/4) + (4 − 4) R +(2 − 12) R .Обозначим = (2 ).
Тогда последовательность удовлетворяет линейному разностному уравнению = −1 + 2−2 + 2 C +2−1 C +2(2−2 − 2) C +2(2 R +2 R ).Решением является функция из заключения леммы.206D.3Вещественный алгоритм Radix-2 во временной областиОн также называется алгоритмом Эдсона-Бергланда.Пусть вектор вещественный и применяется radix-2 во временной области. Результат каждой стадии есть CE вектор. Одна векторная бабочка содержит два вещественных сложения для нулевой и средней частот, а в оставшихся /2 − 2 бабочках обрабатывается только половина из них. Каждая бабочкавключает два комплексных сложения и одно комплексное умножения. Поэтому выполнено рекуррентное уравнение () = 2 (/2)+2 R +(/4−1)(2 C + C ) = 2 (/2)+(3/2−4) R +(−6) R .при ≥ 4. Начальные данные: (1) = 0, (2) = 2 R , (4) = 6 R . Решениеуравнения при = 2 ≥ 4:)︂(︂)︂(︂573 − + 4 R + − + 6 R .
() =222Алгоритм неудобен для реализации свёртки, так как требует проведениябитовой перестановки входного вещественного массива до начала работы.D.4Вещественный алгоритм Split-Radix в частотной областиРассмотрим split-radix алгоритм в частотной области, на вход которого подаётся вещественный массив. Тогда в обозначениях комплексной версии алгоритма вектор вещественный. Поэтому 0 = 1 и, следовательно, 1′ = ¯0′ .Этот вектор можно отдельно не вычислять.Таким образом, расчёт вещественного БПФ col(0′ , 1′ ) длины 2 сводитсяк расчёту вещественного БПФ 0′ длины и к расчёту комплексного БПФ0′ = ℱℓ ℓ′′ 0 длины ℓ = /2.Лемма 38 Сложность вещественного алгоритма split-radix в частотной области равна)︂(︂)︂(︂17121914 − − (−1) + 3 R + − + (−1) + 3 R , () =399399207где = 2 ≥ 2, всего 2−4+6 вещественных операций, если для реализациикомплексного БПФ также применяется алгоритм split-radix.Доказательство.
Рекуррентное уравнение для сложности определяетсярасщеплением и умножением на ℓ′′ : () = (/2) + (/4) + R +(ℓ − 2) C +(2 R +2 R )= (/2) + (/4) + (3/2 − 2) R +( − 6) R .Подстановка значения () из леммы 37 и решение получающегося линейногоуравнения первого порядка приводит к утверждению леммы.Обратное преобразование от CE вектора к вещественному вектору требуеттакого же количества операций, как в лемме 37.Свёртка вещественных массивов длины = 2 может быть рассчитанапри помощи данного split-radix алгоритма в частотной области, умножения идвойственного split-radix алгоритма во временной области. Алгоритмы БПФосуществляются на месте и требуют ровно ячеек вещественной памяти.D.5Двойная вещественная интерполяция−1, где вектор вещеЗадан комплексный ∈ R . Известно, что = ℱственный.
Требуется рассчитать вектор = ℱ col(, 0), где = 2.Расщепим целевой вектор на чётные и нечётные компоненты: =′ — вектор,col(′0 , ′1 ). Очевидно, что ′0 = — исходный вектор и ′1 = ℱ подлежащий расчёту.−1Вещественный вектор = ℱ рассчитывается алгоритмом в частотнойобласти со сложностью ().′Для нахождения ′1 = ℱ применим алгоритм split-radix в частотнойобласти. Вектор вещественный, выделим первые 0 , 1 — векторы первыхи последних ℓ = /2 компонент и сформируем вектор 0 = 0 + 1 . В соответствии с алгоримом split-radix вектор ′1 полностью определяется векторомℱℓ ℓ′′ 0 .208Лемма 39 Алгоритм двойной вещественной интерполяции с входным вектором длины имеет сложность() = () + (/2) + (/2 − 2) C +(2 R +2 R ).Если вещественные и комплексные БПФ реализуются алгоритмами splitradix, то сложность двойной вещественной интерполяции равна(︂)︂(︂)︂28126184() = − + (−1) + 3 R + − − (−1) + 3 R .399399Здесь = 2 ≥ 2, всего 4 − 6 + 6 вещественных операций.
Начальныезначения: (2) = 0, (4) = 2 R .√Доказательство. Умножение на ′′ ℓ с учётом особенностей 1 и (1 + )/ 2требует ℓ − 2 комплексных умножения, 2 вещественных сложения и умножения. для расчёта вектора 1 требуется также одно вещественное БПФ−1 и одно комплексное БПФ ℱℓ ℓ′′ 0 . Отсюда получаем первое утвеж = ℱдение леммы.Второе утверждение получается прямой прдстановкой заключения лемм37 и 37:Таким образом, вместо расчёта ℱ выполняется ℱ , и эти операцииимеют одинаковую сложность.По сравнению с вещественным DIO split-radix алгоритмом отсутствует вычисление векторов 0 +1 и 0 −1 , так как 1 = 0.
Поэтому сложность всейоперации двойной интерполяции при = 2 имеет вид() = () + (ℓ) + (ℓ − 2) C +(2 R +2 R )= () + (/2) + ( − 2) R +(2 − 6) R(︂)︂(︂)︂41712191= − − (−1) + 3 R + − + (−1) + 3 R399399)︂(︂)︂(︂8221924+(−1)− + (−1) +2 R +(−1)− − (−1) +6 R399399+( − 2) R +(2 − 6) R(︂)︂(︂)︂82814261= − + (−1) + 3 R + − − (−1) + 3 R .399399всего 4 − 6 + 6 вещественных операций. Начальные значения: (2) = 0,(4) = 2 R .209.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
