Заданы последовательности (начало координат в нижнем левом углу): s(n,m) = 
, h(n,m) = 
.
Вычислить свертку z(n,m) = s(n,m) ** h(n,m).
ДПФ размера 2 х 2 для s(n,m). S(0,0) = s(0,0) + s(1,0) + s(0,1) + s(1,1) = 2+1+1+0 = 4
S(1,0) = s(0,0) - s(1,0) + s(0,1) - s(1,1) = 2 -1+1 -0 = 2
S(0,1) = s(0,0) + s(1,0) - s(0,1) - s(1,1) = 2+1 -1 -0 = 2
S(1,1) = s(0,0) - s(1,0) - s(0,1) + s(1,1) = 2 -1 -1+0 = 0
После аналогичного вычисления H(k,l) и перемножения S(k,l)= S(k,l) H(k,l):
S(k,l) = 
, H(k,l)= 
, Z(k,l)= 
.
После обратного ДПФ размера 2 х 2 получим результат циклической свертки: z(n,m) = 
.
Дополним опорные области s(.) и h(.) до размера 4 х 4 (для исключения искажения спектра, в принципе,
достаточен размер 3 х 3), и повторим вычисления:
s(n,m)= 
, h(n,m)= 
.
S(k,l)= 
, H(k,l)= 
.
S(k,l)= 
. s(n,m)= 
.
Сравнение данного результата с ДПФ размером 2 х 2 позволяет наглядно видеть эффект
цикличности свертки.
В настоящее время имеются разнообразные и весьма эффективные алгоритмы ДПФ. Для прямого вычисления P-мерного ДПФ требуется (N1 
N2 ... NP)2 операций умножения и сложения. Для многомерного ДПФ, как и для одномерного, существуют алгоритмы быстрых преобразований Фурье. Простейший из них в двумерном ДПФ - разбиение на строки и столбцы, который мы уже рассматривали. Аналогично, Р-мерное ДПФ может заменяться Р-операциями одномерных ДПФ, при этом общее количество операций умножения и сложения сокращается.
литература
9. Даджион Д., Мерсеро Р. Цифровая обработка многомерных сигналов. – М.: Мир, 1988. – 488 с.
