Алгоритм Винограда для расчета циклической свертки

Содержание

Введение

Представление циклической свертки через модулярные полиномиальные преобразования

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

Правила деления полиномов

Циклическая свертка N=2

Циклическая свертка N=3

Циклическая свертка N=4

Выводы

Список литературы

DSPL-2.0 — свободная библиотека алгоритмов цифровой обработки сигналов

Распространяется под лицензией LGPL v3

Страница проекта на SourceForge

Введение

В предыдущем разделе мы рассмотрели линейную и циклическую свертку и показали, что расчет линейной свертки можно проводить на основе циклической.

Шмуэль Виноград
1936 – 2019

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

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

Вывод алгоритмов Винограда довольно громоздкий, но мы рассмотрим примеры данных алгоритмов для циклических сверток длины N = 2 , N = 3 и N = 4 , которые покажут методику и приемы проектирования алгоритмов Винограда циклических сверток произвольной длины.

Представление циклической свертки через модулярные полиномиальные преобразования

В предыдущем разделе мы определили циклическую свертку двух последовательностей a(n) и b(n) равной длительности отсчетов, $n = 0\ldots N-1$ как:

(1)

которую можно представить в матричной форме:

(2)

Квадратная матрица $\mathbf{B}$ содержит только

различных элементов, причем каждая строка (столбец) матрицы получается путем циклического сдвига предыдущей строки (столбца) матрицы на один отсчет. Матрица такой структуры называется циркулянтом или циркуляционной матрицей.

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

Результат циклической свертки также может быть представлен через полиномиальное произведение вида [1]:

(3)

где

(4)

(5)

(6)

полиномы степени N-1

, содержащие по

коэффициентов.

Таким образом, произведение полиномов A(z) и B(z) берется по модулю z^N-1 , т.е. C(z) ничто иное как остаток от деления A(z)B(z) на z^N-1 .

В результате C(z) в выражении (3) представляет собой полином степени N-1 , чьи коэффициенты равны циклической свертке коэффициентов A(z) и B(z) .

Само по себе выражение (3), на первый взгляд, не упрощает расчет циклической свертки, однако исследование модулярной алгебры, которое было проведено в 70-х годах XX века привело к разработке алгоритмов расчета циклической свертки с минимально возможным числом операций умножения.

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

В 1976 году Шмуэль Виноград доказал следующую теорему [2].

Теорема (Винограда) Количество операций умножения необходимое для расчета -точечной циклической свертки согласно (3) равно 2N - k , где — число неприводимых многочленов z^N-1 .

Вычисление циклической свертки при N = 2 требует две операции умножения, так как 2N = 4 а многочлен z^2 - 1 = (z-1)(z+1) представляется произведением двух неприводимых многочленов.

Напомним, что неприводимым многочленом называют такой многочлен, который делится без остатка только на себя. Легко видеть, что многочлены z - 1 и z+1 являются неприводимыми.

Полиномы z^N-1 при N>1 не являются неприводимыми и могут быть разложены в произведение неприводимых многочленов Q_i(z) :

(7)

Тогда, в соответствии с китайской теоремой об остатках, полином C(z)

может быть представлен

(8)

где

(9)

(10)

(11)

а полиномы S_i(z)

находятся из алгоритма Евклида как:

(12)

а полином

удовлетворяет условию:

(13)

Заметим, что полиномы Q_i(z)

не зависят от входных полиномов A(z)

, а только от величины

Правила деления полиномов

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

Рисунок 1. Пример деления полиномов

Пример демонстрирует процесс деления полинома 4z^3 + 3z^2 - z + 2 на z^2 - z + 1 . В результате частное равно 4z + 7 , а остаток от деления равен 2z -5 . Тогда, можно записать, что

(14)

а сам полином можно представить в виде:

(15)

Рассмотрим еще один пример. Пусть требуется рассчитать $Y(z) = (8z^3 + 2z -1) \Mod (z^2 - 2z)$ . Это также можно посчитать через деление уголком, как это показно на рисунке 2 (отсутствующий квадратичный член

добавлен как 0 z^2

Рисунок 2. Пример деления полиномов

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

(16)

Заметим, что если порядок полинома X(z)

меньше порядка полинома Y(z)

, то

(17)

Для расчета полиномов A_i(z)

и других полезно вспомнить теорему Безу [3, стр. 45], которая говорит о том, что

(18)

т.е. остаток от деления полинома X(z)

на

, равен значению полинома X(z)

при

Циклическая свертка N=2

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

(19)

представляется произведением двух неприводимых многочленов Q_1(z) = z-1

. Входными данными для расчета циклической свертки являются последовательности $[a_0, \,\,\,a_1]$ и $[b_0, \,\,\, b_1]$ . Тогда полином A(z) = a_0 + a_1 z

, соответственно B(z) = b_0 + b_1 z

и в соответствии с (3) и (8) можно записать:

(20)

Шаг 1. Рассчитываем полиномы A_i(z)

, использую теорему Безу (18) и выражение (10):

(21)

(22)

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

(23)

(24)

Шаг 2. Формируем полиномы C_i(z)

согласно (9):

(25)

(26)

Здесь

— промежуточные суммы, а m_1

— промежуточные умножения.

Расчет полиномов C_1(z) и C_2(z) потребовал две операции умножения.

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

(27)

(28)

Шаг 4. Расчет полиномов R_i(z)

из уравнения (13).

(29)

(30)

Шаг 5. Формируем полиномы S_i(z)

согласно (12) на основе рассчитанных R_i(z)

(31)

Шаг 6. Восстанавливаем полином C(z)

согласно 8:

(32)

где $[c_0, \,\,\, c_1]$ — результат двухточечной циклической свертки последовательностей $[a_0, \,\,\,a_1]$ и $[b_0, \,\,\, b_1]$ .

Заметим, что коэффициенты $\frac{1}{2}$ можно учесть при вычислении двух произведений m_1 и m_2 на шаге 2.

Тогда окончательно двухточечную циклическую свертку

(33)

можно получить через алгоритм Винограда вида:

(34)

Таким образом, получили два умножения, 6 сложений и масштабирование с коэффициентом $\frac{1}{2}$ .

Скрипт GNU Octave cconv2.m , реализующий расчет двухточечной циклической свертки приведен в следующем листинге:

cconv2.m


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]

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

Циклическая свертка N=3

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

(35)

представляется произведением k=2

неприводимых многочленов Q_1(z) = z-1

. Входными данными для расчета циклической свертки являются последовательности $[a_0, \,\,\,a_1, \,\,\, a_2]$ и $[b_0, \,\,\, b_1, \,\,\, b_2]$ . Тогда полиномы A(z)

равны

(36)

В соответствии с (3) и (8) можно записать:

(37)

Шаг 1. Рассчитываем полиномы A_i(z)

, использую теорему Безу (18), процедуру деления полиномов уголком и выражение (10):

(38)

(39)

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

(40)

(41)

Шаг 2. Формируем полиномы C_i(z)

согласно (9):

(42)

(43)

Рассмотрим произведение:

(44)

Нетрудно показать, что

(45)

где

(46)

Тогда после деления уголком получим

(47)

Расчет полиномов C_1(z)

потребовал четыре операции умножения.

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

(48)

(49)

Шаг 4. Расчет полиномов R_i(z)

из уравнения (13).

(50)

Полином

найдем из уравнения

(51)

(52)

Чтобы выполнить это условие, полином R_2(z)

должен иметь степень не ниже первой, т.е. можно записать $R_2(z) = \alpha z + \beta$ , где $\alpha$ и $\beta$ можно найти из уравнения (52). Учтем, что

(53)

тогда

(54)

Тогда можно составить систему уравнений:

(55)

решением которой будет $\alpha = -\frac{1}{3}$ и $\beta = -\frac{2}{3}$ .

Окончательно $R_2(z) = -\frac{1}{3}(z + 2)$ .

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

(56)

(57)

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

(58)

Рассчитываем

(59)

(60)

Тогда

(61)

Коэффициент $\frac{1}{3}$ учтем в умножениях $m_1 \ldots m_4$ , выполняемых на шаге 2. Тогда после деления уголком получим окончательно:

(62)

где $[c_0, \,\,\, c_1, \,\,\, c_2]$ — результат трехточечной циклической свертки последовательностей $[a_0, \,\,\,a_1, \,\,\,a_2]$ и $[b_0, \,\,\, b_1, \,\,\, b_2]$ .

Заметим, что коэффициент $\frac{1}{3}$ также можно учесть при вычислении умножений $m_1\ldots m_4$ . Тогда окончательно трехточечную циклическую свертку

(63)

можно получить через алгоритм Винограда вида:

(64)

Полученный алгоритм требует 19 сложений и 4 умножения для расчета трехточечной циклической свертки.

Скрипт GNU Octave cconv3.m , реализующий расчет трехточечной циклической свертки приведен в следующем листинге:

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]

Заметим, что для многих практических приложений вектор $\mathbf{b}$ считается постоянным, поэтому операции сложения, использующие только b_k , где $k = 0, \,\,1, \,\, 2$ могут быть предварительно просчитаны и могут не учитываться в оценке вычислительной сложности алгоритма. Таким образом алгоритм может быть переписан в следующем виде:

(65)

Операции на пересчет коэффициентов $r_1 \ldots r_4$ можно не учитывать. Тогда полученный алгоритм требует 4 умножения и 14 сложений.

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

(66)

который также требует 4 умножения, но всего 11 сложений (операции на расчет $r_1 \ldots r_4$ не учитываются).

Циклическая свертка N=4

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

Циклическую свертку последовательностей $[a_0, \,\, a_1, \,\, a_2,\,\,a_3]$ и $[b_0, \,\, b_1, \,\, b_2,\,\,b_3]$ можно представить в матричной форме как можно записать как:

(67)

Тогда в модулярной арифметике можно представить:

(68)

(69)

Полином

можно разложить на произведение трех полиномов:

(70)

Тогда

согласно теореме Винограда, 4-точечная циклическая свертка может быть реализована с использованием 2N - k = 5

умножителей.

Получим алгоритм Винограда для 4-точечной циклической свертки.

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

(71)

где

. Тогда

(72)

Третий полином можно получить в результате деления уголком:

(73)

где

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

(74)

где

. Тогда

(75)

Третий полином можно получить в результате деления уголком:

(76)

где

Шаг 2. Формируем полиномы C_i(z) согласно (9):

Первые два полинома вырождаются в умножения m_1 и m_2 :

(77)

(78)

Третий полином C_3(z)

равен

(79)

В результате деления уголком получим остаток:

(80)

Заметим, что коэффициенты C_3(z)

можно получить из матричного уравнения:

(81)

в котором произведение матрицы на вектор описывает двухточечную циклическую свертку.

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

Введем обозначения :

(82)

(83)

Согласно алгоритму Винограда для двухточечной свертки и выражению (81)

(84)

Таким образом, расчет полиномов C_1(z)

требует 5 операций умножения.

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

(85)

(86)

(87)

Шаг 4. Расчет полиномов R_i(z)

из уравнения (13).

(88)

откуда $R_1(z) = \frac{1}{4}$ . Аналогично

(89)

откуда $R_2(z) = -\frac{1}{4}$ , а также

(90)

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

(91)

(92)

(93)

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

(94)

Введем обозначения

(95)

а также учтем масштабирующие коэффициенты $\frac{1}{4}$ при расчете множителей m_1

, а коэффициенты $\frac{1}{2}$ при p_1

учтем в множителях m_3

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

(96)

Алгоритм требует 25 операций сложения и 5 умножений.

Если вектор $\mathbf{b}$ считать постоянным, то коэффициенты $q_1 \ldots q_8$ могут быть предварительно рассчитанными и тогда алгоритм требует 5 умножений и 17 сложений.

Оптимизация алгоритма для минимизации сложений при постоянных значениях $b_0 \ldots b_3$ позволяет рассчитывать 4-точечную свертку при использовании 15 умножений как [4, стр. 67]:

(97)

Здесь коэффициенты $r_1 \ldots r_7$ рассчитываются однократно, и операции для расчета данных коэффициентов можно не учитывать.

При построении малоточечных ДПФ Винограда целесообразнее использовать оптимизированные алгоритмы циклических сверток с минимальным числом умножителей и сумматоров. В этом случае коэффициенты $r_1 \ldots r_7$ будут постоянными поворотными коэффициентами, которые будут входить в выражение как предварительно просчитанные константы.

Скрипт GNU Octave cconv4.m , реализующий расчет четырехточечной циклической свертки приведен в следующем листинге:

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]

Выводы

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

Мы рассмотрели методику разработки алгоритмов для произвольной длины свертки, а также рассмотрели примеры вывода алгоритмов Винограда для сверток длины N = 2 , N = 3 и N = 4 .

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

Список литературы

[1] Winograd S. On Computing the Discrete Fourier Transform. MATHEMATICS OF COMPUTATION, 1978, Vol. 32, Num. 141, pp. 175–189

[2] Winograd S. Some bilinear forms whose multiplicative complexity depends on the field of constants. Mathematical systems theory, 1976, Vol. 10, pp. 169–180. doi 10.1007/BF01683270

[3] Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. Москва, Наука, 1970, 720 с.

[4] Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. Москва, Радио и связь, 1985.

[5] Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. Москва, Мир, 1989, 448 c.

Последнее изменение страницы: 12.05.2022 (19:41:21)

Страница создана Latex to HTML translator ver. 5.20.11.14