Scientific journal
International Journal of Experimental Education
ISSN 2618–7159
ИФ РИНЦ = 0,425

APPLICATION OF FAST SVERTOCHNY ALGORITHMS

Timoshenko L.I. 1
1 Stavropol branch of the Ministry of Internal Affairs Krasnodar university of Russia
2573 KB
In modern and perspective algorithms of digital processing of signals the mathematical models using the device of linear algebra started finding broad application, the main computing procedures are operations like multiplication of vectors and matrixes, the address of matrixes, search of own vectors and own values of matrixes, the decision of systems of the linear algebraic equations.
digital processing of signals
realization of arithmetic operations
speed indicators
processing speed
algorithms of the accelerated calculation

Для достижения желаемого эффекта по обеспечению вычислений при стандартной разрядной сетке процессора цифровой обработки сигналов (ЦОС) были предложены алгоритмы коротких сверток, основанные на специальных способах умножения номиналов, которые можно использовать в соответствии с китайской теоремой об остатках (КТО) для вычисления больших сверток, заменяя их на последовательность коротких. Данные методы составляют основу второй группы методов цифровой обработки сигналов [1, с. 60-97., 2].

Если исходные две последовательности дискретных отчетов х(nT) и u(nT) представить в виде полиномиальной формы, то операцию циклического свертывания можно свести к процедуре умножения этих полиномов.

При этом вычисления циклической свертки двух последовательностей х(nT) и u(nT) равной длины N, эквивалентного нахождению коэффициентов полинома y(z) согласно выражения

tim1.wmf, (1)

где х(z) и u(z) – полиномиальная форма последовательностей х(nT) и u(nT) соответственно.

Если положить, что двучлен tim2.wmf может быть представлен в виде произведения S круговых неприводимых полиномов

tim3.wmf, (2)

где S – число делителей N, то это позволяет использовать для вычисления коротких сверток КТО. В этом случае вычисление свертки (1) выполняется согласно алгоритма:

Приведение полиномов х(z) и u(z) по модулю pi(z), i=1, 2,…,S, т.е.

tim4.wmf (3)

2. Определение произведения

tim5.wmf.

Восстановление значений y(z) с помощью КТО, т.е.

tim6.wmf. (4)

где Bi(z) – ортогональный базис i-го основания.

Если в качестве коэффициентов полиномов x(z) и u(z) выбрать элементы поля рациональных чисел Q, то рассматриваемый выше алгоритм будет иметь минимальную сложность. Это обусловлено тем, что в поле рациональных чисел круговые полиномы с индексами N<105 имеют простые коэффициенты {–1, 0, 1}

В этом случае обобщенная форма алгоритмов вычисления коротких сверток с помощью КТО имеет вид

tim7.wmf, (5)

где tim8.wmf – векторная форма выходной, входной и сворачивающей последовательностей соответственно; C, B, A, – матрицы; «·» – поточечное произведение векторов.

Значения элементов матриц C, B, A для коротких сверток длинной N <9, обеспечивающих минимальное количество операций умножения, приведены в работе [7, с. 76, 8, с. 38-39, 9, с. 77]. Альтернативным решением проблемы сокращения времени вычисления циклических сверток является гнездовой алгоритм.

Вычисление циклической свертки непосредственно по выражению (5) требует разработки специальных алгоритмов, минимизирующих число операций умножения для каждого значения N. Лучшие оценки по быстродействию вычислительных устройств получаются при использовании гнездового алгоритма [4, с. 60-97].

В основу данного алгоритма положена возможность сведения вычисления одномерной свертки к многомерной. Отправной точкой такого преобразования является изоморфизм, порождаемый китайской теоремой об остатках [5, с. 73-74, 14].

Если длина циклической свертки N может быть представлена в виде произведения двух чисел n1 и n2, т. е. N = n1 n2, причем НОД (n1, n2) = 1, то любое число из интервала 0, 1 … N–1 можно записать в виде (m1, m2), где m1 = N mod n1, m2= N mod n2. Тем самым устанавливается взаимнооднозначное соответствие между элементами кольца N и целыми числами отрезка tim9.wmf. При этом вычет m1 рассматривается как первая координата числа N, а вычет m2 – как вторая координата.

Рассмотрим матричную форму представления операции циклической свертки. В этом случае выражение (1) имеет вид

tim10.wmf. (6)

Тогда циклическая свертка определяется в виде произведения tim11.wmf циклической матрицы свертки на сворачиваемый вектор. Если строки матрицы упорядочить по первой координате m1, а столбцы – по второй, то получим разбиение по блокам, каждый из которых также образует циклическую матрицу для свертки меньшей размерности.

tim12.wmf

Перестановки строк и столбцов циклической матрицы осуществляются в следующем порядке: первыми ставятся те, у которых первая координата равна 0 , а вторая – в возрастающем порядке, затем те, у которых первая координата равна 1 и вторая в возрастающем порядке. В результате получается блочно-циклическая структура.

Обозначив через tim13.wmf

tim14.wmf, а также

tim15.wmf tim16.wmf

получаем преобразованную матрицу в более компактном виде

tim17.wmf. (7)

Для реализации гнездового алгоритма вычисления сверток представим выражение (7) в полиномиальной форме, воспользовавшись z-преобразованием. Тогда

tim18.wmf. (8)

используя круговые полиномы pi(z) представим двучлен tim19.wmf в виде

tim20.wmf. (9)

Тогда на основе КТО, получаем (1.28)

tim21.wmf, (10)

где

tim22.wmf. (11)

Известно [6, с. 98-100, 11, с. 59-60], что с помощью интерполяционной формулы Лагранжа может быть точно восстановлен полином степени N-1 по значениям N точках. В этом случае метод нахождения tim23.wmf заключается в определении констант <tim24.wmf а затем в вычислении интерполяционной формулы

tim25.wmf (12)

в которой интерполяционные полиномы имеют вид

tim26.wmf. (13)

В общем случае сложность гнездового алгоритма определяется следующим образом. Если tim27.wmf и tim29.wmf – количество умножений в алгоритмах вычисления tim30.wmf и tim31.wmf – точечной сверток соответственно, а tim32.wmf и tim33.wmf – количество сложений. Тогда, при НОД tim34.wmf, tim35.wmf – точечная свертка вычисляется за tim36.wmf операций умножений и tim37.wmf сложений.

Перестановка местами первой и второй координаты обработки приводит к изменению количества операций сложений, которые составят tim38.wmf. Таким образом, при выборе гнездового алгоритма предпочтение отдается тому способу при котором число сложений меньше.

Если tim39.wmf разлагается в произведение более чем двух взаимно простых сомножителей tim40.wmf то выражение для оценки временных затрат имеет вид

– число умножений

tim41.wmf (14)

– число сложений

tim42.wmf (15)

при условии, что tim43.wmf.

В формуле (15) в каждом последующем слагаемом количество символов tim44.wmf увеличивается на единицу по сравнению с предыдущим, вследствие чего число операций сложений A гораздо сильнее зависит от числа операций умножения tim45.wmf, чем от числа сложений. Поэтому для больших сверток наиболее выгодны алгоритмы, вычисляющие короткие свертки с наименьшим числом умножений, даже если это достигается за счет увеличения числа операций сложения.

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

В работах [17, с. 22-25, 12, с. 76-78] приведена нижняя оценка эффективности различных сверточных алгоритмов. Известно, что вычисление линейной свертки двух последовательностей х(n) и u(n) длины N эквивалентно определению коэффициентов полинома

tim46.wmf. (16)

При этом ord y(z) = ord x(z) + ord и (z) = 2N – 2. Применение данного алгоритма позволяет найти значение x(zi), и u(zi) в точках zi, i = 0,1,…,2N – 2, с последующим вычислением произведения

tim47.wmf. (17)

Искомый полином y(z) полностью определяется значениями yi(z) заданных в 2N-1 точках интерполяции zi. Таким образом, если для восстановления используется быстрый интерполяционный полином по китайской теореме об остатках, то вычислительная сложность алгоритма линейной свертки определяется 2N-1 умножениями вида (16).

В работах [13, с. 71-73, 18, с. 367-371, 19, с. 188-193 ] доказано, что минимальное число умножений, необходимых для вычисления циклической свертки длины N, равно tim48.wmf, где k – число делителей N , включая 1 и N. Известно, что полином tim49.wmf разлагается на произведение круговых полиномов, число которых равно k. Если положить, что tj – делитель N, то соответствующий этому делителю круговой полином tim50.wmf имеет степень tim51.wmf, а сумма степеней круговых полиномов равна N.

Применение КТО позволяет свести вычисление циклической свертки к выражению

tim52.wmf (18)

Известно, что для реализации равенства (1.36.18) требуется tim53.wmf умножений. Проведя суммирование по всем j, получаем

tim54.wmf. (19)

Таким образом, очевидно, что для сверток малой длины граница мультипликативной сложности достигнута, и, следовательно, улучшение алгоритмов цифровой обработки сигналов возможно только за счет сокращения числа операций сложения [15, с. 23-24, 16, с. 22-23].

Однако, несмотря на то, что все алгоритмы с минимальной мультипликативной сложностью имеют структуру вида (5), где поточечное умножение векторов tim55.wmf и tim56.wmf требует выполнения 2N-1 итераций над операндами, практическая реализация их довольно сложна. Кроме того, изменение величины N входного вектора x(n) влечет за собой изменение всей структуры вычислительного устройства.

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

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