Изложим способ реализации вычисления 2мДПФ дискретных сигналов с помощью построения тензоров 3-го ранга. На основании тензорного представления 2D-спектра сигнала найдена система ортогональных функций, принимающих в каждой точке значения {-1, 0, +1}, которые составляют базис в пространстве сигналов, размерности которых равны степени двойки.

Рассмотрим исходный двумерный сигнал xN1, N2[t1,t2] , размеры которого для простоты изложения будем считать равными, т.е. N1=N2=N , t1,t2=1÷N. (В статьях Григоряна все формулы приводятся с индексацией 1÷N, хотя несложно их преобразовать к виду с обычной индексацией 0÷N-1.) Тогда   2мДПФ   этого сигнала можно записать так

Для произвольных значений w1,w2,t=1÷N определим трёхмерное множество отсчётов двумерного сигнала — (тензор сигнала 3-го ранга)

Тогда   2мДПФ   исходного сигнала можно переписать, как сумму взвешенных элементов   тензора сумм 3-го ранга

Таким образом, введение   тензора сумм 3-го ранга   s3N, N, N [ w1,w2,t ]   позволяет представить   2мДПФ   SN, N [ w1,w2]   исходного сигнала через одномерные   N-точечные   векторы

Очевидно, что такое тензорное представление спектра взаимно однозначно и обладает следующим важным свойством. Обозначим через   a=a (mod N) , где a≠N и   N=N , тогда для любых   w1,w2,k   имеем

Действительно, в силу периодичности   2мДПФ   справедливо

Иными словами,   для разных отсчётов   2D-спектра   (w1,w2)   при помощи N-точечного   одномерного ДПФ вектора сумм

Например, пусть N=8, тогда для образующего отсчёта   (w1,w2)=(1,1)   по компонентам вектора   s38,8,8 [ w1,w2,t ] ,  t=1÷8 , получим значения 2D-спектра сигнала в точках (1,1), (2,2), ... , (8,8) , а   если выбрать образующий отсчёт (w1,w2)=(1,2) , то — в точках (1,2), (2,4), (3,6), (4,8), (5,2), (6,4), (7,6), (8,8).

Покажем, как без лишних вычислений получить 2D-спектр сигнала. Очевидно, что для этого необходимо оптимальным образом выбрать образующие точки 2D-спектра (w1,w2), чтобы образованные ими циклические группы отсчётов 2D-спектра    TN[w1,w2]    заполняли всю область определения 2D-спектра с минимальными пересечениями, т.е.

Для N — простого такое покрытие области определения 2D-спектра существует. Например, в качестве множества образующих отсчётов   2D-спектра JN, N   можно взять

Таким образом, при N простом 2D-спектр исходного двумерного сигнала можно вычислить с помощью   card( JN, N ) = (N+1)   процедур одномерного   N-точечного ДПФ.

При   N=2v   оптимального покрытия области определения 2D-спектра при выше рассмотренном тензоре сумм 3-го ранга не существует, хотя достаточно взять множество

В статье для   N=2v   показан даже несколько громоздкий способ, как исключить все лишние вичисления из одномерных ДПФ с идеей, похожей на алгоритм Split-Radix, однако через 2 года в статье А.М.Григорян приводит более элегантное решение для   N=2v .

И так, идём дальше.

Рассмотрим важный для практики случай, когда у входного сигнала все   N1=N2=N=2v. В силу симметрии комплексных экспонент   exp(2πj/N) , относительно точки   N/2 , а именно

Тогда   2мДПФ   исходного сигнала перепишется, как сумма взвешенных элементов   спаренного тензора разностей 3-го ранга

Аналогично выше рассмотренному тензору сумм 3-го ранга здесь также имеет место формула

Действительно, т.к. (опять же в силу симметрии)

Тогда, делая подстановку   k=2n−1 , запишем

Рассматривая полученную формулу для всех   n=1÷N/2 , находим, что в результате выполнения   N/2-точечного   ДП Фурье   вектора, образованного из взвешенных множителем   WN−t элементов спаренного тензора разностей 3-го ранга

Например, для образующего отсчёта (1,1) одномерное   N/2-точечное

Построим эффективный алгоритм вычисления 2D-спектра по ТА для случая, когда у входного сигнала все   N1=N2=N=2v . Очевидно, что, как и в случае с простым N , для этого необходимо оптимальным образом выбрать образующие точки 2D-спектра (w1,w2), чтобы соответствующие   N/2-точечные   спаренные циклические группы   TTN/2 [ w1,w2]   заполняли всю область определения 2D-спектра без пересечения, т.е.

Так как для всех   i=1÷N   очевидны равенства:

И более этого, всякое множество отсчётов 2D-спектра   JN, N , с помощью которого можно оптимально (т.е. без пересечения циклических групп) покрыть область определения 2D-спектра   ОО( SN, N [ w1,w2] )   с минимальной для этого мощностью, эквивалентно множеству

Действительно,

Далее очевидно, что если образующий отсчёт 2D-спектра   (w1,w2)   взят из множества   2i·JN/2i   для некоторого i ∈ {0,...,v=log2 N} , то мощность, образованной этим отсчётом, спаренной циклической группы   TTN/2 [ w1,w2]   равна   N/2i+1 . Поэтому в оптимальном покрытии области определения 2D-спектра   ОО( SN, N [ w1,w2] ) , объединяющем   3N−2   различных (т.е. не пересекающихся) спаренных циклических групп   TTN/2 [ w1,w2] ,   3N/2   из них содержат по   N/2   элементов каждая, следующие   3N/4   содержат по   N/4   таких элементов и т.д. Отсюда следует, что для определения полного 2D-спектра исходного двумерного сигнала размера   NхN   при   N=2v   достаточно выполнить   3N/2   одномерных   N/2-точечных   ДПФ,   3N/4   одномерных   N/4-точечных   ДПФ и т.д.

Иными словами, для   n=1÷N/2i+1   имеет место очевидное равенство

Рассматривая полученную формулу для всех   i ∈ {0,...,v=log2 N} , находим, что выполнение   N/2-точечного   ДП Фурье   вектора   W·ssN/2w1,w2 [t]   эквивалентно выполнению   N/2i+1-точечного   ДП Фурье   над сжатым вектором (т.е. вектором из меньшего числа точек), образованным из взвешенных множителем   (WN/2i)−t элементов спаренного тензора разностей 3-го ранга

Отметим здесь, что описанный ТА вычисления 2D-спектра существенно отличается от хорошо известного алгоритма редуцированного ДПФ Нуссбаумера , выполняемого с помощью сложных полиномиальных преобразований (ПП). Действительно, для   N=2v   в таком алгоритме вычисление   NхN-точечного 2мДПФ осуществляется с помощью ПП и посредством не только   3N/2   N-точечных   (а не N/2-точечных как в ТА)   редуцированных одномерных ДПФ, но ещё и   N/2хN/2-точечного   ДПФ, которое в свою очередь также аналогичным образом вычисляется посредством   3N/4   N/2-точечных   (а не N/4-точечных как в ТА)   редуцированных одномерных ДПФ и ещё   N/4хN/4-точечного   ДПФ и т.д. Поэтому предлагаемый ТА для 2мДПФ очевидно эффективнее указанного редуцированного ДПФ на основе ПП.

NB. Однако, потом Григорян А.М. согласился с тем, что вычислительная сложность его ТА для БПФ2 (по числу вещественных умножений) совпадает с той, которая у алгоритма, использующего ПП Нуссбаумера.

От себя замечу, что структурная сложность ПП Нуссбаумера слишком высока. Поэтому его наглядность (в смысле понятности для инженера) оставляет желать лучшего или требует от инженера длительного привыкания к ПП, чтобы применять их для операций ЦОС.

Подсчитаем объём нетривиальных операций умножения O( mult (FOURN, N) ) на поворачивающие экспоненты   WNt , необходимый для выполнения ТА вычисления   NхN-точечного   2мДПФ.

Тогда получим неулучшаемую оценку числа умножений, выраженную через оценки для одномерного ДПФ

Чтобы получить точную минимальную оценку числа умножений, т.е. O( mult (FOURN, N) ) , очевидно, в эту формулу нужно подставить точные оценки O( mult (FOURN/2i) )   для всех степеней двойки   2i=8,16, ... , N .

Не останавливаясь на одномерном случае, отметим, что все вышеприведенные рассуждения о спаренном тензорном представлении 2D-спектра легко переносятся и на случай одномерного сигнала, причём точные оценки указанных операций умножения   O( mult( FOURN/2i) )   равны для степеней двойки   2i ≥ 8  

Подставляя полученную оценку O( mult (FOURN/2i) )   для одномерных ДПФ, получим при больших   N   оценку для 2мДПФ

NB. Таким образом, с помощью введенного выше спаренного тензорного представления Фурье-спектра двумерного сигнала, получена точная оценка для операций комплексного умножения на нетривиальные поворачивающие множители, которых достаточно для вычисления 2мДПФ.

Далее, несмотря на то, что размеры двумерного сигнала предполагались совпадающими и равными степени двойки, спаренный тензорный способ вычисления спектра легко распространить и на более общий случай, когда размеры сигнала равны произвольным чётным числам.