2.3.2. Разбиение на строки и столбцы

Сумму ДПФ в (2.71) можно переписать в виде

.                    (2.72)

Величина в квадратных скобках - это двумерная последовательность, которую мы обозначим . Тогда выражение (2.72) можно записать в виде пары соотношений

,                             (2.73а)

.                             (2.73б)

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

-мерное ДПФ можно выполнить тем же путем. Сначала вычисляется одномерное ДПФ по одной из переменных (например, ) для каждого значения остальных переменных. Это требует в общей сложности  одномерных ДПФ. Затем одномерные ДПФ вычисляются по переменной  для всех значений остальных  переменных . Эта процедура повторяется до тех пор, пока не будут найдены одномерные ДПФ по всем пространственным переменным.

Какая экономия в объеме вычислений достигается благодаря этой процедуре? Мы уже видели, что при прямом вычислении требуется

                                                         (2.74)

комплексных умножений и сложений. Если в методе разложения на столбцы и строки для вычисления одномерного ДПФ применяется прямое вычисление, то вычисление многомерного ДПФ требует

      (2.75)

комплексных умножений и сложений. Если каждое из чисел записывается в виде степени двух, чтобы использовать одномерное БПФ, то количество комплексных умножений можно еще уменьшить до

.                (2.76)

Количество комплексных сложений вдвое больше этого числа. Можно также использовать и другие быстрые алгоритмы вычисления одномерного ДПФ, если для выполнения многомерного ДПФ применен метод разбиения на столбцы и строки.

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

Для этого примера разбиение на столбцы и строки уменьшает количество арифметических операций почти в 500 раз. Использование одномерного БПФ уменьшает объем вычислений примерно в  раз. (Заметим, что в одних сутках около  с.)