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]
Алгоритм Винограда для расчета циклической свертки
В предыдущем разделе мы рассмотрели линейную и циклическую свертку и показали, что расчет линейной свертки можно проводить на основе циклической.

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




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






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

















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

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






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












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



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
















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











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



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

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




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



















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
















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


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







![[c_0, \,\,\, c_1, \,\,\, c_2]](img/eqlin-69.png)
![[a_0, \,\,\,a_1, \,\,\,a_2]](img/eqlin-70.png)
![[b_0, \,\,\, b_1, \,\,\, b_2]](img/eqlin-59.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-точечной циклической свертки.
Шаг 1. Рассчитываем полиномы и
, использую теорему Безу (18), процедуру деления полиномов уголком и выражение (10):







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







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







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






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









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



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











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

Скрипт 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]
В данном разделе мы рассмотрели алгоритм Винограда расчета коротких циклических сверток с минимально возможным числом операций умножения.
Мы рассмотрели методику разработки алгоритмов для произвольной длины свертки, а также рассмотрели примеры вывода алгоритмов Винограда для сверток длины ,
и
.
Алгоритмы Винограда циклических сверток имеют ключевое значение при выводе малоточечных алгоритмов Винограда быстрого преобразования Фурье, которые, в свою очередь, позволяют простроить высокоэффективные алгоритмы БПФ практически для любого размера ДПФ.