6.5.3. МНОГОМЕРНОЕ БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ

Двумерное дискретное преобразование Фурье было определено в гл. 3 следующим образом:

Замечаем, что выражение (6.35) очень похоже на (6.26). Действительно, можно дать полезную интерпретацию алгоритма БПФ в терминах многомерного дискретного преобразования Фурье (см. [7]). Что касается расчетов по формуле (6.35), то можно

заметить, что эти расчеты включают вычисление М ДПФ вида

а затем ДПФ вида

Ясно, что можно рассчитать (6.36) и (6.37) с помощью одного из вышеописанных алгоритмов. Если являются степенями 2, то число требуемых комплексных умножений будет равно в противоположность комплексным умножениям при прямом вычислении по (6.35).

Основной трудностью при вычислении двумерных ДПФ является большое число запоминающих ячеек, необходимых для осуществления вычислений с замещением. Для комплексных данных требуется действительных запоминающих регистров для хранения входных выборок или результирующего преобразования. Например, при требуется регистра. Если требуемого объема памяти с произвольным доступом нет, то можно использовать один из видов массовой памяти с последовательным доступом, таких, как магнитный диск или магнитная лента, где строки или столбцы записываются друг за другом. Это увеличивает сложность реализации вычислений по (6.36) и (6.37). Например, если данные записываются в память по строкам, то легко осуществить строчные преобразования (6.36), но если результаты строчных преобразований записываются последовательно по строкам, то трудно обратиться к данным, требуемым для столбцовых преобразований. Один из способов преодоления этой трудности состоит в выполнении сразу нескольких строчных преобразований, сохранении результатов и затем записи результирующих значений в транспонированном порядке. После формирования всего транспонированного массива требуемые столбцовые преобразования вычисляются как строчные преобразования транспонированного массива. Результирующее двумерное преобразование записывается в транспонированном порядке [12].