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].