Fast orthogonal multivariate transforms

Abstract

Розглянуто модифікації швидкого алгоритму перетворення Фур’є Нусбаумера–Квандаля для довжин коду 2^n. Запропоновано можливість обчислення всіх коефіцієнтів у два кроки. На першому кроці обчислюються коефіцієнти з парним першим індексом за аналогією з алгоритмом Нусбаумера–Квандаля; на другому кроці обчислюються коефіцієнти з непарним першим індексом. Представлений порядок обчислень забезпечує паралельне оброблення та вдосконалення структури алгоритму без істотної зміни обчислювальної складності або з її зменшенням.

Modifications of Nussbaumer-Quandalle Fourier Transform fast algorithm for code lendths 2n 2n are considered. The possibility of calculating of all coefficients for two steps offered. At first step the even first index coefficients has calculated in analogy Nussbaumer-Quandalle algorithm; and at the second step the odd first index coefficients has calculated. The presented calculating order assured a parallel processing and structure algorithm improvement without essential or with conversed computional complexity changes.