1.5. НЕКОТОРЫЕ ПЕРСПЕКТИВНЫЕ АЛГОРИТМЫ ВЫЧИСЛЕНИЯ ДПФ

1.5.1. Алгоритм Винограда

Алгоритм Винограда [1.12] основан на представлении матрицы -точечного ДПФ, где все — взаимно-простые числа, в виде прямого произведения матриц -точечных ДПФ

и сведении вычисления -точечных ДПФ к вычислению круговых сверток с использованием модульной арифметики в кольце полиномов (см. 1.4.7).

Алгоритм Винограда, имеющий «гнездовую» структуру, существенно эффективнее классических алгоритмов при приблизительно равном числе операций сложения он требует на 80% меньше операций умножения.

Вычисление ДПФ коротких последовательностей.

При где — простое, нечетное число, можно свести к вычислению круговых сверток:

1. Пусть . Тогда матрица путем соответствующей перестановки строк и столбцов может быть преобразована в циклическую матрицу размера Взаимно-однозначное соответствие между показателями степени элементов матрицы и индексами элементов циклической матрицы (1-43) задается так:

где а — первообразный корень числа

Пример 1.20. Пусть . Первообразным корнем числа 7 является Тогда соответствие (1.71) запишется так:

а матрица преобразуется к виду

Тогда искомое ДПФ примет вид:

Выражение (1.72) представляет собой -точечную круговую свертку последовательностей для вычисления которой с помощью полиномиальных преобразований требуется восемь операций умножения и 34 — сложения (см. табл. 1.5). Для вычисления всего ДПФ к этому числу операций добавляются одна операция умножения на и две операции сложения (см. табл. 1.6).

2. Пусть - целое. В этом случае вычисление ДПФ сводится к вычислению двух -точечных ДПФ и одной -точечной круговой свертки. Это эквивалентно одной двум четырем сверткам. Взаимно-однозначное соответствие между показателями степени элементов циклических матриц и индексами элементов матрицы (1.43) задается равенством

где — первообразный корень числа ра+-.

Пример 1.21. Пусть . В этом случае первообразные корнч Соответствие (1.73) для запишется так:

Тогда круговая свертка будет иметь вид

Последовательности вычисляются с помощью

Последовательности такие, что

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

3. Пусть - целое. В этом случае вычисление ДПФ сводится к вычислению двух -точечных ДПФ и двумерной -точечной круговой свертки, матрица которой имеет вид

где представляют собой циклические матрицы размера Взаимно-однозначное соответствие между показателями степени элементов матриц и индексами элементов матрицы (1.43) имеет вид

Пример 1.22. Пусть Соответствия (1.74) запишутся так:

Тогда:

Последовательности вычисляются с помощью 4-точечного ДПФ:

(см. скан)

Последователькости такие, что

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

В [1.12] приведены алгоритмы вычисления ДПФ коротких последовательностей для N = 2, 3, 4, 5, 7, 8, 9, 16. В табл. 1.6 приводится число требуемых при этом арифметических операций.

Вычисление ДПФ длинных последовательностей.

Пусть — взаимно-простые числа. Если сделать перестановку входной и выходной последовательностей, как и в алгоритме взаимно-простых делителей (см. 1.3.5), то

Таблица 1.6 (см. скан)

матрицу исходного ДПФ можно представить в виде прямого произведения матриц и -точечных ДПФ:

Пример 1.23. Пусть Из уравнений (1.37) и Переставим элементы согласно (1.35):

Введем векторы:

Тогда искомое ДПФ преобразуется к виду

где — матрица -точечного ДПФ.

Матрица выражения (1.75) и есть прямое произведение

Для вычисления векторов воспользуемся алгоритмом вычисления

Для вычисления векторов необходимо использовать алгоритм -точечного ДПФ. Элементы полученного массива следует переставить согласно (1.36) для получения искомого массива:

Таким образом, -точечное ДПФ требует а, операций сложения и операций умножения, включая умножений на -точечное ДПФ требует операций сложения и операций умножения, включая умножений на Тогда число требуемых операций сложения А и умножения М для -точечного ДПФ составит:

Пример 1.24. Пусть Согласно табл. Пользуясь формулами (1.76) и (1.77), находим:

Теперь пусть Тогда число операций умножения не изменится, а число операций сложения станет равным