clear all; close all; clc;
pkg load signal; % Для запуска в Matlab эту строку надо удалить!
% ------------------------------------------------------------------------------
% Исходные данные - a и b случайные комплексные векторы размера [3 x 1]
% ------------------------------------------------------------------------------
a = randn(2, 1) + 1i* randn(2, 1);
b = randn(2, 1) + 1i* randn(2, 1);
% ------------------------------------------------------------------------------
% Алгоритм Винограда расчета циклической свертки N = 4
% ------------------------------------------------------------------------------
s1 = b(2) + b(1); s2 = b(2) - b(1);
m1 = (a(2) + a(1)) * s1 / 2;
m2 = (a(2) - a(1)) * s2 / 2;
c1 = m1 - m2;
c0 = m1 + m2;
% ------------------------------------------------------------------------------
% ПРОВЕРКА РЕЗУЛЬТАТА
% ------------------------------------------------------------------------------
% Встроенная функция циклической свертки
z0 = cconv(a, b, 2)
% Циклическая свертка через FFT
z1 = ifft(fft(a).*fft(b))
% Циклическая свертка через матричное умножение
ind = [1 2;
2 1;];
z2 = b(ind)*a
% Циклическая свертка через алгоритм Винограда
z3 = [c0; c1]
Алгоритм Винограда для расчета циклической свертки
![]() DSPL-2.0 — свободная библиотека алгоритмов цифровой обработки сигналов Распространяется под лицензией LGPL v3
Страница проекта на SourceForge
|
В предыдущем разделе мы рассмотрели линейную и циклическую свертку и показали, что расчет линейной свертки можно проводить на основе циклической.

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




Ранее мы уже говорили, что линейная свертка двух последовательностей может быть представлена в виде произведения двух полиномов с коэффициентами, соответствующими исходным последовательностям. В результате получаем полином чья степень равна сумме степеней исходных полиномов.
Результат циклической свертки также может быть представлен через полиномиальное произведение вида [1]:






Таким образом, произведение полиномов и
берется по модулю
, т.е.
ничто иное как остаток от деления
на
.
В результате в выражении (3) представляет собой полином степени
, чьи коэффициенты равны циклической свертке коэффициентов
и
.
Само по себе выражение (3), на первый взгляд, не упрощает расчет циклической свертки, однако исследование модулярной алгебры, которое было проведено в 70-х годах XX века привело к разработке алгоритмов расчета циклической свертки с минимально возможным числом операций умножения.
В 1976 году Шмуэль Виноград доказал следующую теорему [2].
Теорема (Винограда)
Количество операций умножения необходимое для расчета -точечной циклической свертки согласно (3) равно
, где
— число неприводимых многочленов
.
Вычисление циклической свертки при требует две операции умножения, так как
а многочлен
представляется произведением двух неприводимых многочленов.
Напомним, что неприводимым многочленом называют такой многочлен, который делится без остатка только на себя. Легко видеть, что многочлены и
являются неприводимыми.
Полиномы при
не являются неприводимыми и могут быть разложены в произведение
неприводимых многочленов
:

















Для того чтобы получить алгоритм Винограда для циклической свертки необходимо научиться рассчитывать остаток от деления полиномов. Проще всего это сделать путем деления полиномов уголком, как это показано на рисунке 1.

Пример демонстрирует процесс деления полинома на
. В результате частное равно
, а остаток от деления равен
. Тогда, можно записать, что






Таким образом












Применение вышеизложенных формул рассмотрим на простейшем примере для .
Тогда



![[a_0, \,\,\,a_1]](img/eqlin-042.png)
![[b_0, \,\,\, b_1]](img/eqlin-043.png)
















Расчет полиномов и
потребовал две операции умножения.
Шаг 3. Рассчитываем полиномы используя (12):











![[c_0, \,\,\, c_1]](img/eqlin-053.png)
![[a_0, \,\,\,a_1]](img/eqlin-042.png)
![[b_0, \,\,\, b_1]](img/eqlin-043.png)
Заметим, что коэффициенты можно учесть при вычислении двух произведений
и
на шаге 2.
Тогда окончательно двухточечную циклическую свертку



Скрипт GNU Octave cconv2.m
, реализующий расчет двухточечной циклической свертки приведен в следующем листинге:
Алгоритм для двухточечной циклической свертки можно получить напрямую из выражения (33) без использования долгих полиномиальных преобразований, раскрыв матричное произведение и вынеся общие множители за скобки. Однако для более длинных сверток простым вынесением за скобки уже не обойтись, и необходимо использовать полиномиальные преобразования алгоритма Винограда.

Рассмотрим теперь алгоритм Винограда для .
Тогда




![[a_0, \,\,\,a_1, \,\,\, a_2]](img/eqlin-058.png)
![[b_0, \,\,\, b_1, \,\,\, b_2]](img/eqlin-059.png)



















Шаг 3. Рассчитываем полиномы используя (12):
















Окончательно .
Шаг 5. Формируем полиномы согласно (12) на основе рассчитанных
и
:


Шаг 6. Восстанавливаем полином согласно 8:







![[c_0, \,\,\, c_1, \,\,\, c_2]](img/eqlin-069.png)
![[a_0, \,\,\,a_1, \,\,\,a_2]](img/eqlin-070.png)
![[b_0, \,\,\, b_1, \,\,\, b_2]](img/eqlin-059.png)
Заметим, что коэффициент также можно учесть при вычислении умножений
.
Тогда окончательно трехточечную циклическую свертку


Скрипт GNU Octave cconv3.m
, реализующий расчет трехточечной циклической свертки приведен в следующем листинге:
clear all; close all; clc;
pkg load signal; % Для запуска в Matlab эту строку надо удалить!
% ------------------------------------------------------------------------------
% Исходные данные - a и b случайные комплексные векторы размера [3 x 1]
% ------------------------------------------------------------------------------
a = randn(3, 1) + 1i* randn(3, 1);
b = randn(3, 1) + 1i* randn(3, 1);
% ------------------------------------------------------------------------------
% Алгоритм Винограда расчета циклической свертки N = 4
% ------------------------------------------------------------------------------
s1 = a(1) + a(2); s2 = b(1) + b(2);
m1 = ( s1 + a(3)) * ( s2 + b(3)) / 3;
m2 = (a(2) - a(3)) * (b(2) - b(3)) / 3;
m3 = (a(1) - a(2)) * (b(2) - b(1)) / 3;
m4 = (a(1) - a(3)) * (b(1) - b(3)) / 3;
q0 = m4 - m2; q1 = m4 + m3;
s3 = m1 - q0; s4 = m1 + q0;
s5 = m1 + q1; s6 = q1 - q0;
c2 = s3 - q1;
c1 = s5 + s6;
c0 = s4 - s6;
% ------------------------------------------------------------------------------
% ПРОВЕРКА РЕЗУЛЬТАТА
% ------------------------------------------------------------------------------
% Встроенная функция циклической свертки
z0 = cconv(a, b, 3)
% Циклическая свертка через FFT
z1 = ifft(fft(a).*fft(b))
% Циклическая свертка через матричное умножение
ind = [1 3 2;
2 1 3;
3 2 1];
z2 = b(ind)*a
% Циклическая свертка через алгоритм Винограда
z3 = [c0; c1; c2]
Заметим, что для многих практических приложений вектор считается постоянным, поэтому операции сложения, использующие только
, где
могут быть предварительно просчитаны и могут не учитываться в оценке вычислительной сложности алгоритма. Таким образом алгоритм может быть переписан в следующем виде:


Количество сложений при этом можно оптимизировать, если использовать следующий эквивалентный алгоритм [4, стр. 66]:



\label{subsection:winograd_cconv4}
Ну и наконец рассмотрим еще один пример алгоритма Винограда для расчета циклической свертки размера .
Циклическую свертку последовательностей и
можно представить в матричной форме как
можно записать как:







Получим алгоритм Винограда для 4-точечной циклической свертки.
Шаг 1. Рассчитываем полиномы и
, использую теорему Безу (18), процедуру деления полиномов уголком и выражение (10):







Аналогично используя (11):







Шаг 2. Формируем полиномы согласно (9):
Первые два полинома вырождаются в умножения и
:







Применим алгоритм Винограда для расчета двухточечной циклической свертки.
Введем обозначения :






Шаг 3. Рассчитываем полиномы используя (12):









Шаг 5. Формируем полиномы согласно (12) на основе рассчитанных
и
:



Шаг 6. Восстанавливаем полином согласно 8:











Тогда окончательно алгоритм Винограда циклической свертки размера имеет вид:

Если вектор считать постоянным, то коэффициенты
могут быть предварительно рассчитанными и тогда алгоритм требует 5 умножений и 17 сложений.
Оптимизация алгоритма для минимизации сложений при постоянных значениях позволяет рассчитывать 4-точечную свертку при использовании 15 умножений как [4, стр. 67]:


При построении малоточечных ДПФ Винограда целесообразнее использовать оптимизированные алгоритмы циклических сверток с минимальным числом умножителей и сумматоров. В этом случае коэффициенты будут постоянными поворотными коэффициентами, которые будут входить в выражение как предварительно просчитанные константы.
Скрипт GNU Octave cconv4.m
, реализующий расчет четырехточечной циклической свертки приведен в следующем листинге:
clear all; close all; clc;
pkg load signal; % Для запуска в Matlab эту строку надо удалить!
% ------------------------------------------------------------------------------
% Исходные данные - a и b случайные комплексные векторы размера [4 x 1]
% ------------------------------------------------------------------------------
a = randn(4, 1) + 1i* randn(4, 1);
b = randn(4, 1) + 1i* randn(4, 1);
% ------------------------------------------------------------------------------
% Алгоритм Винограда расчета циклической свертки N = 4
% ------------------------------------------------------------------------------
% Расчет коэффициентов С1(z) = m1 и C2(z) = m2
s1 = a(1) + a(3); s2 = a(2) + a(4); q1 = b(1) + b(3); q2 = b(2) + b(4);
s3 = a(1) - a(3); s4 = a(2) - a(4); q3 = b(1) - b(3); q4 = b(2) - b(4);
s5 = s1 + s2; s6 = s1 - s2; q5 = q1 + q2; q6 = q1 - q2;
m1 = s5 * q5 / 4; m2 = s6 * q6 / 4;
% Расчет коэффициентов С3(z) = p1 * z + p0 через двухточ. циклическую свертку
s7 = s4 + s3; s8 = s4 - s3; q7 = q4 + q3; q8 = q4 - q3;
m3 = s7 * q7 / 4; m4 = s8 * q8 / 4; m5 = s4*q4;
q9 = m3 + m4; p0 = q9 - m5; p1 = m3 - m4;
% восстановление C(z) = (C1(z)*S1(z) + C2(z)*S2(z) + C3(z)*S3(z)) mod (z^4-1).
% C(z) = c0 + c1*z + c2*z^2 + c3*z^4.
% Коэффициенты 1/4 учтены в m1 и m2, а 1/2 в m3, m4 и m5.
s9 = m1 - m2; s10 = m1 + m2;
c0 = s10 + p0; c1 = s9 + p1; c2 = s10 - p0; c3 = s9 - p1;
% ------------------------------------------------------------------------------
% ПРОВЕРКА РЕЗУЛЬТАТА
% ------------------------------------------------------------------------------
% Встроенная функция циклической свертки
z0 = cconv(a, b, 4)
% Циклическая свертка через FFT
z1 = ifft(fft(a).*fft(b))
% Циклическая свертка через матричное умножение
ind = [1 4 3 2;
2 1 4 3;
3 2 1 4;
4 3 2 1];
z2 = b(ind)*a
% Циклическая свертка через алгоритм Винограда
z3 = [c0; c1; c2; c3]
В данном разделе мы рассмотрели алгоритм Винограда расчета коротких циклических сверток с минимально возможным числом операций умножения.
Мы рассмотрели методику разработки алгоритмов для произвольной длины свертки, а также рассмотрели примеры вывода алгоритмов Винограда для сверток длины ,
и
.
Алгоритмы Винограда циклических сверток имеют ключевое значение при выводе малоточечных алгоритмов Винограда быстрого преобразования Фурье, которые, в свою очередь, позволяют простроить высокоэффективные алгоритмы БПФ практически для любого размера ДПФ.