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

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Штучний інтелект
Дата:	2011
Автори:	Терещенко, А.Н., Задирака, В.К., Кудин, А.М.
Формат:	Стаття
Мова:	Російська
Опубліковано:	Інститут проблем штучного інтелекту МОН України та НАН України 2011
Теми:	Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/60239
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Использование циклических сдвигов для ускоренного вычисления циклических сверток длины равной произведению взаимно простых чисел / А.Н. Терещенко, В.К. Задирака, А.М. Кудин // Штучний інтелект. — 2011. — № 3. — С. 521-536. — Бібліогр.: 10 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859603979693981696
author	Терещенко, А.Н. Задирака, В.К. Кудин, А.М.
author_facet	Терещенко, А.Н. Задирака, В.К. Кудин, А.М.
citation_txt	Использование циклических сдвигов для ускоренного вычисления циклических сверток длины равной произведению взаимно простых чисел / А.Н. Терещенко, В.К. Задирака, А.М. Кудин // Штучний інтелект. — 2011. — № 3. — С. 521-536. — Бібліогр.: 10 назв. — рос.
collection	DSpace DC
container_title	Штучний інтелект
first_indexed	2025-11-28T01:51:23Z
format	Article
fulltext	«Штучний інтелект» 3’2011 521 8Т УДК 510.52 А.Н. Терещенко, В.К. Задирака, А.М. Кудин Институт кибернетики имени В.М. Глушкова НАН Украины, г. Киев, Украина teramidi@ukr.net, zvk140@ukr.net Использование циклических сдвигов для ускоренного вычисления циклических сверток длины равной произведению взаимно простых чисел В работе рассматривается метод вычисления циклических сверток длины     1 0 n i imN , где 1),( ji mm , ji  . Рассматривается новое блочно-циклическое представление свертки за счет использования циклических сдвигов в каждом блоке. При таком подходе китайская теорема об остатках (КТО) не используется. Метод является эффективным за счет использования несложных пред- и поствычислений с применением циклических сдвигов. Он позволяет распараллелить вычисления. Получены априорные оценки сложности по количеству операций умножения. Приведены примеры вычислений сверток. Введение Циклические свертки широко используются при построении цифровых фильтров, в задачах ассиметричной криптографии и т.д. Как известно, выбор метода зависит от области его эффективного использования. Циклическая свертка используется при реализации быстрой операции умножения с использованием быстрых преобразований Фурье, Уолша, Хаара [1]. Операция умножения занимает большую часть вычислитель- ного времени при реализации операций ассиметричной криптографии, в частности в задачах распространения секретного ключа, шифрования информации, выработки и верификации электронно-цифровой подписи и т.д. В работе [2] Д. Питасси предложил метод вычисления циклической свертки длины nN 2 , усовершенствованный впоследствии Девисом [3]. Данный метод приводит операцию вычисления циклической свертки длины n2 к вычислению трех циклических сверток половинной длины 12 n . На каждой итерации количество сверток половинной длины увеличивается в три раза. Итерации продолжаются до получения сверток длины 2. В работе [4], следуя Питасси, показано, что вычисление циклической свертки длины kN  2 , k – нечетное, сводится к вычислению двух свер- ток длины k , что позволяет реализовать операцию умножения двух k -разрядных чисел, k – нечетное. Метод, рассматриваемый в данной работе, является продолже- нием работы [4]. В работе [5] приведен метод умножения больших чисел, основанный на циклической свертке длиной, равной степени двойки с использованием прео- бразования Уолша. В работе [6] приведены оптимальные алгоритмы по количеству операций умножения, сложения и вычитания для вычисления сверток длины 2, 3, 4, 5, 7, 8, 9. Р.К. Агарвал и Ч.С. Баррас предложили отображать одномерный массив в многомерный, используя удвоение числа точек [7]. В работе Винограда [8] для Терещенко А.Н., Задирака В.К., Кудин А.М. «Искусственный интеллект» 3’2011 522 8Т вычисления длинных сверток применяются билинейные формы. В работе [9] Р.К. Агар- вал и Дж.У. Кули применяют китайскую теорему об остатках (КТО) для преобра- зования одномерной циклической свертки в многомерную, которая циклична по всем направлениям. Упомянутые выше работы направлены на уменьшение числа однословных умножений. Сегодня архитектура современного процессора такова, что операции одно- словного умножения и сложения выполняются за одинаковое число тактов. Поэтому дальнейшие работы должны учитывать этот факт и также быть направлены на оптимизацию количества таких однословных операций, как сложение, вычитание, сдвиги. Одним из оригинальных подходов для решения таких задач можно назвать комби- нацию программного и аппаратного подхода, при котором перед началом каждого вычисления в зависимости от длины входных данных прошиваются эффективные для данных длин подпрограммы [10]. Для вычисления свертки длины N стандартным методом необходимо выполнить 2N операций умножения, что соответствует умножению квадратной матрицы на вектор длины N . Продолжая идею Питасси [2], [3], операцию вычисления циклической свертки длины 15N (     1 0 N m jmmj N yxr , 1,0  Nj ) можно свести к вычислению трёх сверток длины 5N (рис. 1). 21411857411310129630 036912 120369 912036 691203 369120 1013147 7101314 4710131 1471013 1314710 5811142 2581114 1425811 1114258 8111425 2 14 11 8 5 5811142 2581114 1425811 1114258 8111425 036912 120369 912036 691203 369120 1013147 7101314 4710131 1471013 1314710 7 4 1 13 10 1013147 7101314 4710131 1471013 1314710 5811142 2581114 1425811 1114258 8111425 036912 120369 912036 691203 369120 12 9 6 3 0 rrrrrrrrrrrrrrr xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx y y y y y xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx y y y y y xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx y y y y y Рисунок 1 – Вычисления свертки длины 53 rkN , где rk, – нечетные Свертки 012 30 xx xx    , 52 85 xx xx    , 107 1310 xx xx    повторяются по три раза. Данный подход позволяет значительно уменьшить число операций умножения, сложения, вычитания и т.д. Использование циклических сдвигов для ускоренного вычисления... «Штучний інтелект» 3’2011 523 8Т Далее будет показано, что вычисление любой циклической свертки длины rkN  , 1),( rk , rk  , можно представить в виде k блоков, повторяющихся k раз. Такой метод позволяет свести задачу вычисления свертки длины rkN  к задаче вычисления свертки длины k . Далее будем использовать выражение «секция» вместо «блок», что созвучно с методом парисекции, рассмотренным Девисом [3]. Новизной предложенного метода является использование циклических сдвигов в каждом блоке для представления свертки в блочно-циклическом виде без ис- пользования китайской теоремы об остатках. Преимуществом данного метода является то, что не используются предвычисления, на каждой итерации достаточно знать p ( rkN  , rk  , krd  , 1 r dp ), не используются дискретные преобразо- вания, метод разбиения подобный для любых длин сверток. Операторы и обозначения Перед тем как рассмотреть предложенный метод, введем следующие операторы и обозначения. Последовательности NX и NY длины N представляются векторами- столбцами:            1 0 N N x x X  ,            1 0 N N y y Y  . Циклическую свертку двух сигналов NX и NY обозначим оператором  : NNN YXR  ,            1 0 N N r r R  ,     1 0 N m jmmk N yxr , 1,0  Nj , что соответствует записи: 3210 21033 10322 03211 32100 rrrr yyyyx yyyyx yyyyx yyyyx или 3210 01233 30122 23011 12300 rrrr xxxxy xxxxy xxxxy xxxxy . Введем следующие операторы: S , P , U , D (S-“Select” (выбрать), P-“Part” (часть), U-“Up” (вверх), D-“Down” (вниз)), и обозначим их следующим образом: kjiN r ji xXS , , 1,0  rj , 1,0  ki , где rNk  ; циклический сдвиг элементов вверх – NN UXV  , N kk xv 1 , 1,0  Nk ; циклический сдвиг элементов вниз – NN DXV  , N Nkk xv 1 , 1,0  Nk ; циклический сдвиг элементов вверх p раз –  N p N XUV  , N pkk xv  , 1,0  Nk ; циклический сдвиг элементов вниз p раз –  N p N XDV  , N pNkk xv  , 1,0  Nk . Терещенко А.Н., Задирака В.К., Кудин А.М. «Искусственный интеллект» 3’2011 524 8Т Проиллюстрируем операторы для длин 15,12,5N :                  3 2 1 0 4 5 x x x x x DX ,                  0 4 3 2 1 5 x x x x x UX ,                  2 1 0 4 3 5 2 )( x x x x x XD ,                  1 0 4 3 2 5 2 )( x x x x x XU , )()( 12 0 4 1 6 3 0 9 12 0 4 3 XSD x x x x XSU               ,                  12 9 6 3 0 15 0 5 x x x x x XS ,                  13 10 7 4 1 15 1 5 x x x x x XS ,                  14 11 8 5 2 15 2 5 x x x x x XS ,                  4 3 2 1 0 15 0 5 x x x x x XP ,                  9 8 7 6 5 15 1 5 x x x x x XP ,                  14 13 12 11 10 15 2 5 x x x x x XP . Постановка задачи. Если целые положительные векторы NX , NY , NR вида     1 0 2 N i i iN xX  ,     1 0 2 N i i iN yY  ,     1 0 2 N i i iN rR  , где 2,,0  iii ryx , 2N , тогда выражение NR вида                     1 0 1 0 1 0 222 NN i i i N i i iNNN ryxYXR     , где    )(mod N yxr   , представляет собой циклическую свертку NX и NY . Необходимо найти эффективный алгоритм вычисления циклической свертки. Свойства последовательностей Лемма 1. Пусть последовательность NJ составляют элементы 1,0  Nj , где rkN  , rk  , 1),( rk . Если NJ разбить на k секций длины r с использованием опе- ратора S , то каждая секция N i r JS , 1,0  ki , содержит индекс, которой делится на r . Доказательство. Так как каждая секция является результатом применения оператора S , то соседние элементы внутри каждой секции отличаются на k . Нулевая секция 0i будет состоять из следующих элементов: krkk  )1(,...,2,,0 . Использование циклических сдвигов для ускоренного вычисления... «Штучний інтелект» 3’2011 525 8Т Элементы секции 1i будут следующими: krkk  )1(1,...,21,1,1 . Их можно выразить следующим образом: kpz 1 , 1,0  rp , (1) где r – длина секции. Найдем значение p , при котором z делится на r без остатка. Сделаем замену drk  в формуле: NkNNN dprpdprpdrpkpz  11)(11 , 1,0  Np . Отсюда видно, что z будет делиться на r только в том случае, когда rkN dp  1 делится на r : 01  r dp , rr dddp  11 , т.е. когда 1 dp . Число p можно найти, используя расширенный алгоритм Эвклида: 11   rrddrrpd , dr  . Для случая 1i соотношения (1) можно записать в следующем виде: NNNi zikpikpiiz  )1()( . (2) С учетом того, что число секций (длины r ) равно k и порядковый номер в секции не может превышать длины секции rpi  )( , соотношение (2) примет следующий вид: kpz 1 ; NNii zikpiz  , ri pip  , 1,0  ki , (3) где k – количество секций длины r , p – порядковый номер элемента в секции i со значением iz , которое делится на r без остатка. Окончательно получаем: r krdp 11 )(   ; ri pip  , 1,0  ki . (4) kpz 1 ; Ni ziz  , 1,0  ki . (5) Лемма доказана. Соотношение (5) можно представить в виде ki rzirz  , 1,0  ki , упрощающем вычисление iz . Лемма 1 устанавливает зависимость между числом циклических сдвигов p секции, номером секции i , числом секций k и длиной секции r . Для примера рассмотрим последовательность )14...,,1,0(15 J , 15N , 3k , 5r . Вычислим 32)( 5 111   r krdp , 10331 z . Найдем ip , iz , 2,01,0  ki , используя соотношение (3). Таблица 1 – Вычисление N i r JS , ri pip  , Ni ziz  , 1,0  ki , для 1553  rkN , где rk, – нечетные i N i r JS ri pip  Ni ziz  0i )12,9,6,3,0(15 0 5 JS 030 50 p 0100 150 z 1i )13,10,7,4,1(15 1 5 JS 331 51 p 101011 z 2i )14,11,8,5,2(15 2 5 JS 132 52 p 5102 152 z Терещенко А.Н., Задирака В.К., Кудин А.М. «Искусственный интеллект» 3’2011 526 8Т Рассмотрим )34...,,1,0(35 J , 35N , 5k , 7r . Обратный элемент p будет равен 42)( 7 111   r krdp , 21541 z . Найдем ip , iz , 4,01,0  ki , используя соотношение (3). Таблица 2 – Вычисление N i r JS , ri pip  , Ni ziz  , 1,0  ki , для 3575  rkN , где rk, – нечетные i N i r JS ri pip  Ni ziz  0i )30,25,20,15,10,5,0(35 0 7 JS 040 70 p 0210 350 z 1i )31,26,21,16,11,6,1(35 1 7 JS 441 71 p 21211 35 z 2i )32,27,22,17,12,7,2(35 2 7 JS 142 72 p 7212 352 z 3i )33,28,23,18,13,8,3(35 3 7 JS 543 73 p 28213 353 z 4i )34,29,24,19,14,9,4(35 4 7 JS 244 74 p 14214 354 z Анализируя табл.1, 2 и лемму 1, приходим к следующему утверждению. Лемма 2. Пусть последовательность NJ составляют элементы 1,0  Nj , где rkN  , rk  , 1),( rk . Если NJ разбить на k секций длиной r с использованием оператора S , то первый элемент секций N i r p JSU i , 1,0  ki , содержит индекс iz , которое делится на r без остатка, где ip и iz определяются следующими выражениями: r krdp 11 )(   ; 00 p ; pp 1 ; rii ppp  1 , 1,2  ki . kpz 1 ; 00 z ; zz 1 ; Nii zzz  1 , 1,2  ki . (6) Доказательство. Применяя рекуррентные соотношения к соотношениям (4) и (5), приходим к искомым формулам. С учетом леммы 2 табл. 1 может быть представлена в следующем виде. Таблица 3 – Вычисление N i r JS , N i r p JSU i , 000  zp , rii ppp  1 , Nii zzz  1 , 1,1  ki для 1553  rkN , где rk, – нечетные i N i r JS ri pip  N i r p JSU i Ni ziz  0 )12,9,6,3,0(15 0 5 JS 030 50 p )12,9,6,3,0(15 0 5 0 JSU 0100 150 z 1 )13,10,7,4,1(15 1 5 JS 331 51 p )7,4,1,13,10(15 1 5 3 JSU 101011 z 2 )14,11,8,5,2(15 2 5 JS 132 52 p )2,14,11,8,5(15 2 5 1 JSU 5102 152 z Из табл. 3 видно, что секции можно строить сразу, опуская циклические сдвиги вверх. Для этого достаточно знать индекс первого элемента каждой секции. Индексы остальных элементов в каждой секции отличаются на шаг k , равный количеству секций при разбиении. Использование циклических сдвигов для ускоренного вычисления... «Штучний інтелект» 3’2011 527 8Т Рассмотрим построение секций, начиная с первых элементов секций, на примере последовательности )27...,,1,0(28 J . 28N , 4k , 7r . Вычислим 53)( 7 111   r krdp , 12753  rrpd , 214511  kpz . Найдем iz , 3,01,0  ki , используя формулу (6). Таблица 4 – Вычисление N i r JS , ri pip  , Ni ziz  , 1,0  ki , для 2874  rkN , где k – четное, r – нечетное i Ni ziz  N i r p JSU i ri pip  0i 00 z )24,20,16,12,8,4,0(28 0 7 0 JSU 050 70 p 1i 21 zzi )17,13,9,5,1,25,21(28 1 7 5 JSU 551 71 p 2i 14212 282 z )10,6,2,26,22,18,14(28 2 7 3 JSU 352 72 p 3i 7213 283 z )3,27,22,19,15,11,7(28 3 7 1 JSU 153 73 p Таблица 5 – Вычисление секций для 99119  rkN , где k , r – нечетные, 6p , 55z i 99 zizi  i 99 zizi  i 99 zizi  0 00 z 3 663 z 6 336 z 1 551 z 4 224 z 7 887 z 2 112 z 5 775 z 8 448 z Лемма 3. Пусть последовательность )1...,,1,0(  NJN , rkN  , 1),( rk , rk  упорядочена: ))(()( N i r p N i r JSUTP i , ri pip  , 1,0  ki , где r krp 1)(  . Тогда к первоначальному порядку полученную последовательность NT переводят следующие соотношения: r krp 1)(  ; ))(()( N i r p N i r TPDTP i , ri pip  , 1,0  ki . )()( N i kN i k TSJP  , 1,0  ri , (7) Доказательство. Оператор ipU (up-вверх) в выражении N i r p JSU i циклически сдвигает вверх каждую секцию i на ip раз. Соответственно, чтобы получить зна- чения секции в первоначальном (исходном) состоянии, нужно применить обратный оператор D (down-вниз) для каждой секции ip раз, т.е. циклически сдвинуть вниз каждую секцию i на такое же ip раз: )( N i r p N i r TPDTP i , 1,0  ki . После этого перво- начальными элементами каждой секции i будут элементы со значениями i , которые отстоят друг от друга на r элементов (длина каждой секции равна r ). Получили следу- ющую последовательность, состоящую из секций, выделенных вертикальными линиями: 1...,,12,1...)1(1...,,1,1)1(...,,,0  Nkkkrkkrk . Терещенко А.Н., Задирака В.К., Кудин А.М. «Искусственный интеллект» 3’2011 528 8Т Выборка первых элементов, отстоящих друг от друга на r шагов, из k секций определяется выражением NkTS 0 , что соответствует последовательности )1...,,1,0( k . Выборка элементов )12...,,1,(  kkk , следующими за первыми в каждой секции, определяется выражением NkTS1 . Продолжая выборку по формуле (7), получим первоначальную последовательность. Лемма доказана. Более детально рассмотрим последовательность 15J длиной 15 элементов 3k , 5r . Согласно табл. 3 упорядочивание 155155 JSUJP ipi i , ri ip 3 , 2,0i , дает следующую последовательность, разбитую на 3 секции: )2,14,11,8,57,4,1,13,1012,9,6,3,0(15 T . Выражения )( 155155 JPDTP ipi i , 5 3 ipi , 2,0i , приводят предыдущую последовательность к следующему виду: )14,11,8,5,213,10,7,4,112,9,6,3,0(15 T . Соотношения 153153 TSJP ii  , 4,0i , приводят к первоначальной последова- тельности: )14,13,1211,10,98,7,65,4,32,1,0(15 J . Лемма 4. Циклическую свертку NR длины rkN  , 1 rk , 1),( rk сигна- лов NX и NY выражения N i r i Ni XSUXP  , N i r i Ni YSUYP  , N i r i Ni RSURP  , 1,0  ki переводят в блочно-циклический вид. Доказательство. Циклическая свертка сигналов NX и NY определяется выражением      1 0 N m mjmj yxr N , 1,0  Nj . Воспользуемся оператором S и найдем секции длиной r для сигнала NX (преобразования для сигнала NY не приводятся, т.к. они аналогичны):                    kN kN k Nr x x x x XS 2 0 0 ... ,                     1 12 1 1 1 ... kN kN k Nr x x x x XS , …,                       1 1 12 1 1 ... N kN k k N k r x x x x XS . (8) Элементы каждой секции i , полученные с использованием оператора S , сдвинем циклически вверх на i раз 1,0  ki :                    kN kN k Nr x x x x XSU 2 0 00 ... ,                                                           1 1 1 21 1 1 1 21 1 1 111 ......... x x x x x x x x U x x x x UXSU kN kr r kN kN r kN kN k Nr , Использование циклических сдвигов для ускоренного вычисления... «Штучний інтелект» 3’2011 529 8Т                                                            k kr kr r kN r k kN k k Nr x x x x x x x x U x x x x UXSU 2 22 2 2 2 2 2 2 2 2 22 2 2 222 ......... , …, (9)                      kri kri kri ri N i r i x x x x XSU 2 ... , …,                                            krN krN krN rN krk krk krk rk N k r k x x x x x x x x XSU 2 )1( 2)1( )1( )1( 11 ...... . Из (9) видно, что индексы при x первых (самых верхних) элементах каждой секции делятся на r : riN i r i xXSU 0][ , 1,0  ki . Так как каждая секция построена таким образом, что индекс при x следу- ющего элемента в секции отличается от предыдущего на k , то все элементы секций можно записать следующим образом: Ni kjzjN i r i xXSU ][ , 1,0  rj , rizi  , 1,0  ki . (10) Вычисление свертки с учетом (10) можно представить в следующем виде        1 0 1 0 )()( k i r j kjrikmkjrqrikmrq NNN yxr , 1,0  rm , 1,0  kq . (11) Из данного соотношения видно, что в каждой колонке N kmrq  матрицы (рис. 2) индексы при x и y каждой строчки N kjri  отличаются на одно и то же число N kmrq  , что говорит о свойстве цикличности данного представления. Рассмотрим вычисление свертки.      krNkrNrNkrrkNk kNkN kk kkN rNkrNkrN krNrNkrN krNkrNrN rNkrNkrN krrNkrN krNkrNrN krN krN rN rkrkr krrkr krkrr kNkN kk kkN rkN krrkr krr kr r rkN krrkr krr rNkrNkrN krNkrN NkrNrN kNkN kk kkN kN k rrrrrrrrr xxx xxx xxx xxx xxx xxx xxx xxx xxx y y y xxx xxx xxx xxx xxx xxx xxx xxx xxx y y y xxx xxx xxx xxx xxx xxx xxx xxx xxx y y y                                                                                                                                                                               ............ ... ............ ... ... ... ... ............ ... ... ... ............ ... ... ............... ... ............ ... ... ... ... ............ ... ... ... ............ ... ... ... ............ ... ... ... ... ............ ... ... ... ............ ... ... 10 02 20 0 2222 2222 222 2 2 2222 2222 222 02 20 0 11 2 1 1 11 2 1 2 1 1 02 20 00 Рисунок 2 – Вычисление свертки длины rkN  , 1 kr Терещенко А.Н., Задирака В.К., Кудин А.М. «Искусственный интеллект» 3’2011 530 8Т Для доказательства блочности представления достаточно исследовать верхние левые элементы секций (блоков). С учетом соотношения (11) (при 0m , 0j ) получаем следующие выражения: rirqri yx N   , 1,0  ki , 1,0  kq , (12) где rirqri yx N   элемент строчки N ri  и столбцы N rq  матрицы. Откуда видно, что угловые элементы N rqix  )( , 1,0  ki , 1,0  kq , отстоят друг от друга на r строчек и столбцов. Выражение kN qirrqi  )( , 1,0  ki , 1,0  kq показывает, что элемент x с одним и тем же индексом k qir  в верхних левых углах блоков повторяется k раз. Для демонстрации шага индекса между секциями, шага индекса внутри секции и корректности построения свертки достаточно использовать более компактное представление:     ......... ............ ... ......... ... ... ......... ... ... ... ... ......... ... ... ......... ... ... ... 0 0 01 0 00 krrk k kN rkr r kr r rNkrN krNrN k kN k rrrr xx xx xx xx y y xx xx xx xx y y                                                                  Рисунок 3 – Индексы в секции и между секциями Из рис. 3 несложно определить количество элементов в каждой секции и число секций, необходимых для построения свертки. Из рис. 3 также видно, что с учетом того, что шаг индекса внутри каждой секции равен k и шаг индекса между секциями делится на r , где 1 kr , свертка построена корректно. С учетом (12) и операторов U и S вычисление свертки rkN  , 1 kr , можно представить следующим образом: N k r k NrNr NrN k r k N k r k N k r k NrNrNrNr NrN k r k NrNr RSURSURSU XSUXSUXSUYSU XSUXSUXSUYSU XSUXSUXSUYSU 111100 00221111 22001111 11110000 ... ... ............... ... ...    Рисунок 4 – Вычисление свертки длины rkN  , 1 kr в операторном виде С учетом обозначений N i r ii N XSUX  , N i r ii N YSUY  , N i r ii N RSUR  рис. 4 можно представить в блочном виде, в котором вычисление свертки длины rkN  , 1),( rk , 1 kr , сводится к вычислению k сверток длины r . Лемма доказана. Использование циклических сдвигов для ускоренного вычисления... «Штучний інтелект» 3’2011 531 8Т 110 0211 0011 1100 ... ... ............... ... ...    k NNN N k N k N k N NNNN N k NNN RRR XXXY XXXY XXXY Рисунок 5 – Свертка длины rkN  , 1 kr в блочном виде Продемонстрируем вычисление свертки при k – нечетном, 1 kr и покажем на примере вычисления свертки длины 4312 N . Вычисление можно представить в виде: 12 2 4 2 12 1 4 1 12 0 4 0 52118110749630 0369 9036 6903 3690 46101 14710 10147 71014 81125 58112 25811 11258 5 2 11 8 12 2 4 2 81125 58112 25811 11258 0369 9036 6903 3690 46101 14710 10147 71014 1 10 7 4 12 1 4 1 46101 14710 10147 71014 81125 58112 25811 11258 0369 9036 6903 3690 9 6 3 0 12 0 4 0 RSURSURSU rrrrrrrrrrrr xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx y y y y YSU xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx y y y y YSU xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx y y y y YSU Рисунок 6 – Вычисления свертки длины 43N 12 2 4 2 12 1 4 1 12 0 4 0 12 0 4 0 12 1 4 1 12 2 4 2 12 2 4 2 12 2 4 2 12 0 4 0 12 1 4 1 12 1 4 1 12 1 4 1 12 2 4 2 12 0 4 0 12 0 4 0 RSURSURSU XSUXSUXSUYSU XSUXSUXSUYSU XSUXSUXSUYSU Рисунок 7 – Вычисление свертки длины 43N в операторном виде Индексы в операторах S , U для входных и выходного сигналов совпадают в соответствующих секциях. С учетом того, что для вычисления свертки длины 3N и 4N необходимо 4 и 5 операций умножения соответственно [6], для вычисления свертки длины 4312 N необходимо 20 операций умножения, что соответствует оценке Винограда [8]. Это на 4 операции меньше, чем разбиение )32(26212 N на две секции по 6 элементов, которые разбиваются далее на 2 секции по 3 элемента (для вычисления свертки таким способ необходимо 24 операции однословного умножения [4]). Терещенко А.Н., Задирака В.К., Кудин А.М. «Искусственный интеллект» 3’2011 532 8Т Лемма 5. Циклическую свертку NR длины rkN  , 1 dkr , 1),( rk сигналов NX и NY соотношения 1 r dp ; N i r p Ni XSUXP i , N i r p Ni YSUYP i , N i r p Ni RSURP i , ri ipp  , 1,0  ki переводят к блочно-циклическому виду. Доказательство. Воспользуемся оператором S (8) и найдем секции длиной r входных NX , NY и выходного NR сигналов. С учетом леммы 2 элементы каждой секции сдвинем циклически вверх ip раз, 1,0  ki . kpz 1 , r krdp 11 )(   ; ri pip  , Ni izz  , 1,0  ki ;                    kN kN k Nr x x x x XSU 2 0 00 ... , …,                     kz kz kz z N i r p i i i i i x x x x XSU 2 ... ,…,                           kz kz kz z N k r p k k k k k x x x x XSU 1 1 1 1 1 2 1 ... . (13) С учетом (13) вычисление свертки можно представить в виде: N k r p Nr p Nr NrN k r p N k r p N k r p Nr p NrNr p Nr p Nr p N k r p NrNr RSURSURSU XSUXSUXSUYSU XSUXSUXSUYSU XSUXSUXSUYSU k kkk k 1100 00211 20011 110000 11 211 211 11 ... ... ............... ... ...       Рисунок 8 – Вычисление свертки с использованием операторов U и S Вычисление свертки можно представить в виде следующих выражений: r krp 1)(  , kpz 1 ;      1 0 k i ikmrq tr N ,      1 0 )()( r j kjzkmkjrqzi NiNi yxt , Ni izz  , 1,0  ki , 1,0  rm , 1,0  kq . (14) Из (14) видно, что в каждой колонке N kmrq  свертки индексы при x и y в каждой строчке Ni kjz  отличаются на одно и то же число N kmrq  , что говорит о свойстве цикличности данного представления. С учетом обозначений N i r pi N XSUX i , N i r pi N YSUY i , N i r pi N RSUR i рис. 8 можно представить в блочном виде, аналогичном рис. 5. Лемма доказана. Лемма 4 является частным случаем леммы 5 и (14) равнозначна (12) при 1 dkr ( 1)( 11   rr krdp , rz  ). Использование циклических сдвигов для ускоренного вычисления... «Штучний інтелект» 3’2011 533 8Т Априорные оценки сложности Теорема 1. Априорная оценка сложности вычисления циклической свертки длины rkN  , 1),( rk , 1 dkr , где k и r – взаимно простые числа, имеет вид: )()()( *** rQkQNQ  , )()()()( * rQkQrkQNQ   , (15) где )(* kQ , )(* rQ , )(kQ , )(rQ – количество операций умножения, сложения и вычитания для вычисления циклических сверток длины k и r . Доказательство. Циклическая свертка сигналов NX и NY , где rkN  , 1),( rk , 1 dkr , может быть представлена в блочно-циклическом виде (рис. 5, 8). Если )(* kQ , )(* rQ , )(kQ , )(rQ – количество операций умножения, сложения и вычитания, необходимых для вычисления циклических сверток длины k и r , то общую сложность вычисления свертки длины rkN  можно представить априорными оценками (15). Теорема доказана. Теорема 1 применима в следующих случаях: 1. k – нечетное, r – четное, rk  . 2. k – нечетное, r – нечетное, rk  , k и r – взаимно простые. 3. k – четное, r – нечетное, rk  . Случай, когда rk, – четные, не рассматривается, так как по условию числа k и r взаимно простые. Вычисление свертки вида kN  2 , k – нечетное [4], является частным случаем теоремы 1. Теорема 2. Априорная оценка сложности вычисления циклической свертки длины     1 0 n i imN , 1),( ji mm , ji  , 1210 ...   nn mmmm , имеет вид:     1 0 ** )()( n i imQNQ ,                              1 0 1 1 1 0 * )()()( n i n ik ki i k i mmQmQNQ , где )(* imQ , )( imQ – количество операций умножения, сложения и вычитания, необходимых для вычисления циклической свертки длины im . Доказательство. Рассмотрим свертку длины 00 NmN  , где 1),( 00 Nm взаимно простые, тогда согласно теореме 1 априорные оценки сложности можно выразить следующими выражениями: )()()( 0 * 0 ** NQmQNQ  , )()()()( 00 * 00 NQmQNmQNQ   , (16) где )( 0 * mQ , )( 0mQ , )( 0 * NQ , )( 0NQ – количество операций умножения, сложения и вычитания, необходимых для вычисления циклических сверток длины 0m и 0N . Пусть 110 NmN  также является произведением взаимно простых чисел 1),( 11 Nm , тогда согласно теореме 1 и формуле (16) априорные оценки сложности для свертки длины 11000 NmmNmN  можно выразить следующими выражениями: Терещенко А.Н., Задирака В.К., Кудин А.М. «Искусственный интеллект» 3’2011 534 8Т  )()()()()()( 1 * 1 * 0 * 0 * 0 ** NQmQmQNQmQNQ  , )()()()( 00 * 00 NQmQNmQNQ    )()()()()()( 11 * 110 * 110 NQmQNmQmQNmmQNQ   )()()()()()()( 11 * 0 * 110 * 110 NQmQmQNmQmQNmmQNQ   , где )( 0 * mQ , )( 0mQ , )( 1 * mQ , )( 1mQ , )( 1 * NQ , )( 1NQ – количество операций умножения, сложения и вычитания, необходимых для вычисления циклических сверток длины 0m , 1m и 1N . Продолжая разбиение 1N на меньшие длины, приходим к соотношениям (16). Теорема доказана. Оценки в теоремах 1 и 2 аналогичны оценкам, полученным Р.К. Агарвалом и Дж.У. Кули при реализации метода с использованием китайской теоремы об остатках [9, с. 104-105]. Следствие 1. Если сомножители являются степенью числа:     1 0 k i n i imN , то деление на меньшие свертки должно производиться в порядке возрастания величины сомножителей 1210 1210 ...    kk n k n k nn mmmm , а не в порядке возрастания основания числа 1210 ...   kk mmmm . Так разбиение свертки длины 2245 7532  про- изводится следующим образом: 4252 3725  ( 81493225  ). Сначала каждый сигнал разбивается на 25 секций, каждая из которых разбивается на 32 секции и т.д. Следствие 2. При группировке сомножителей порядок разбиения меняется. Имеется в виду, что число сомножителей может быть уменьшено за счет группировки сомножителей. Так, в предыдущем примере при группировке сомножителей 25 и 49 меняется порядок разбиения 49258132  . Это свойство является очень важным, так как для одной и той же длины свертки возможны различные разбиения с различной оценкой сложности, среди которых можно выделить лучшую оценку. Важным является то, что возможно комбинирование методов. Так, например, в предыдущем примере 49258132  первый сомножитель является степенью двойки, что позволяет использовать методы, основанные на представлении большей свертки за счет нескольких сверток половинной длины. Для остальных шагов 492581...  будут использоваться другие методы. Если в начале последовательности ...7532  стоят маленькие числа, то актуальным встает вопрос оптимизации вычислений не только длинных, но и коротких сверток. Таблица 6 – Количество операций умножения для вычисления коротких сверток [6, с. 67-70] N 2 3 4 5 7 8 9 )(* NQ 2 4 5 10 16 14 19 Далее в таблицах приведены априорные оценки сложности по количеству операций однословного умножения для вычисления циклической свертки различной длины разными методами. Использование циклических сдвигов для ускоренного вычисления... «Штучний інтелект» 3’2011 535 8Т Таблица 7 – Количество операций умножения для вычисления сверток длиной, равной произведению взаимно простых чисел предложенным методом     1 0 n i imN 6=2 3 10=2 5 18=2 9 24=3 8 35=5 7 63=7 9     1 0 ** )()( n i ii mQNQ 8=2 4 20=2 10 38=2 19 42=3 14 160=10 16 304=16 19 Таблица 8 – Количество операций умножения для вычисления сверток с использованием преобразования Уолша [3] n 3 4 5 6 nN 2 8 16 32 64 2* 35)(  nNQ 15 45 135 405 С учетом того, что при умножении двух N разрядных чисел получается N2 разрядное число, можно использовать свертку длины 63 для умножения чисел длиной 32 слова. Согласно табл. 7 необходимо 304 целочисленных операций однословного умножения для реализации операции 32 разрядного умножения. Для сравнения: для вычисления дискретного преобразования Фурье длины 64 для одного числа необходимо 19264log)264( 2  операции, где присутствуют операции с плавающей запятой, а для реализации операции умножения, основанной на пре- образовании Фурье необходимо выполнять прямое и обратное преобразования. Метод удобен также тем, что пред- и поствычисления в виде циклических сдвигов для обоих входных сигналов одинаковые, что является отличием от методов Агарвала – Кули и Агарвала – Барраса. Выводы В данной работе предложен метод вычисления сверток длины, равной произве- дению взаимно простых чисел с использованием циклических сдвигов и без использова- ния китайской теоремы об остатках. Предложенный метод позволяет параллельно вычислять свертки меньшей размерности. Приведены априорные оценки сложности вычисления сверток длиной, равной произведению двух и более взаимно простых сомножителей. Приведены зависимости между элементами секций, числом секций, длиной секций, на которые разбиваются свертки. Приведены примеры разбиения цикли- ческих сверток разных длин. Предложенный метод может быть использован для вычи- сления циклической свертки целочисленных, вещественных или комплексных сигналов. Литература 1. Залманзон Л.А. Преобразование Фурье, Уолша, Хаара и их применение в управлении, связи и других областях / Залманзон Л.А. – М. : Наука, 1989. – 496 с. 2. Pitassi D.A. Fast convolution using the Walsh transform / D.A. Pitassi // Applicat. Walsh Functions. – 1971. – April. – P. 130-133. 3. Davis W.F. A class of efficient convolution algorithms / W.F. Davis // Applicat. Walsh Functions. – 1972. – March. – P. 318-329. Терещенко А.Н., Задирака В.К., Кудин А.М. «Искусственный интеллект» 3’2011 536 8Т 4. Терещенко А.Н. Оптимизация метода Питасси вычисления свертки / А.Н. Терещенко // Искусственный интеллект. – 2009. – № 1 – С. 204-212. 5. Реализация операции умножения с использованием преобразования Уолша / А.Н. Терещенко, С.С. Мель- никова, Л.А. Гнатив [и др.] // Проблемы управления и информатики. – 2010. – № 2. – С. 102-126. 6. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток / Нуссбаумер Г. ; пер. с англ. – М. : Радио и связь, 1985. 7. Agarwal R.C. Fast one-dimensional digital convolution by multidimensional technique / R.C. Agarwal ad C.S. Burrus // IEEE Trans, Acoust., Speech, Signal Processing. – 1974. – Feb. – Vol. ASSP-22. – P. 1-10. 8. Winograd S. Some bilinear forms whose multiplicative complexity depends on the field of constants / S. Wi- nograd // Mathematical Systems Theory. – Vol. 10. 9. Макклеллан Дж.Г. Применение теории чисел в цифровой обработке сигналов / Дж.Г. Макклеллан, Ч.М. Райдер ; пер. с англ. / под ред. Ю.И. Манина. – М. : Радио и связь, 1983. – 264 с., ил. 10. Задирака В.К. Построение программно-аппаратных комплексов арифметики сверхбольших чисел / В.К. Задирака, А.М. Кудин // Комп’ютерна математика. Оптимізація обчислень : збірник наукових праць НАНУ, Ін-т кібернетики ім. В.М. Глушкова. – Київ, 2001. – Т. 1. – С. 158-163. Literatura 1. Zalmanzon L.A. Preobrazovanie Fur'e, Uolsha, Haara i ih primenenie v upravlenii, svjazi i drugih oblastjah. M.: Nauka. 1989. 496 s. 2. Pitassi D.A. Applicat. Walsh Functions. April 1971. P. 130-133. 3. Davis W.F Applicat. Walsh Functions. March 1972. P. 318-329. 4. Tereshhenko A.N. Iskusstvennyj intellekt. № 1. 2009. S. 204-212. 5. Tereshhenko A.N. Mezhdunarodnyj nauchno-tehnicheskij zhurnal Problemy upravlenija i informatiki. № 2. 2010. S. 102-126. 6. Nussbaumer G. Bystroe preobrazovanie Fur'e i algoritmy vychislenija svertok. M. : Radio i svjaz'. 1985. 66 s. 7. R.C. Agarwal. IEEE Trans, Acoust., Speech, Signal Processing. Feb. 1974. Vol. ASSP-22. P. 1-10. 8. Winograd S. Mathematical Systems Theory. Vol 10. 9. Makklellan Dzh.G. Primenenie teorii chisel v cifrovoj obrabotke signalov. M.: Radio i svjaz'. 1983. 264 s. 10. Zadiraka V.K. Komp'juternaja matematika. Optimіzacіja obchislen': Zbіrnik naukovih prac' NANU, Іnt-t kіbernetiki іm. V.M. Glushkova. Kyiv. T. 1. 2001. S. 158-163. А.М. Терещенко, В.К. Задірака, А.М. Кудін Використання циклічних зсувів для прискореного обчислення циклічних згорток довжини, яка дорівнює множенню взаємно простих чисел В роботі розглядається метод обчислення циклічних згорток довжиною     1 0 n i imN , де 1),( ji mm , ji  . Розглядається нове блоково-циклічне представлення згортки за рахунок використання циклічних зсувів у кожному блоці. При такому підході китайська теорема про залишки (КТЗ) не використовується. Метод є ефективним за рахунок використання нескладних перед- та післяобчислень із застосуванням циклічних зсувів. Він дозволяє розпаралелювати обчислення. Отримані апріорні оцінки складності за кількістю операцій множення. Наведені приклади обчислення згорток. A.N. Tereshchenko, V.K. Zadiraka, A.M. Kudin Using of Cyclic Shifts for Fast Computation of Cyclic Convolution of Length Equal to Multiplication of Relatively Primes The computation method of cyclic convolution of two series each of length of     1 0 n i imN , where 1),( ji mm , ji  is considered. The new block-cyclic convolution presentation with using of cyclic shifts in each block is proposed. The Chinese Remainder Theorem is not used in this method. The method is effective due to using simple pre- and postcomputations like cyclic shifts. It allows computations in parallel. The number of multiplications in proposed method is given. The examples of convolution computations are presented. Статья поступила в редакцию 22.06.2011.
id	nasplib_isofts_kiev_ua-123456789-60239
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1561-5359
language	Russian
last_indexed	2025-11-28T01:51:23Z
publishDate	2011
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
record_format	dspace
spelling	Терещенко, А.Н. Задирака, В.К. Кудин, А.М. 2014-04-12T15:12:05Z 2014-04-12T15:12:05Z 2011 Использование циклических сдвигов для ускоренного вычисления циклических сверток длины равной произведению взаимно простых чисел / А.Н. Терещенко, В.К. Задирака, А.М. Кудин // Штучний інтелект. — 2011. — № 3. — С. 521-536. — Бібліогр.: 10 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/60239 510.52 ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Нейронные сети и нейросетевые технологии. Информационная безопасность ИС Использование циклических сдвигов для ускоренного вычисления циклических сверток длины равной произведению взаимно простых чисел Використання циклічних зсувів для прискореного обчислення циклічних згорток довжини, яка дорівнює множенню взаємно простих чисел Using of Cyclic Shifts for Fast Computation of Cyclic Convolution of Length Equal to Multiplication of Relatively Primes Article published earlier
spellingShingle	Использование циклических сдвигов для ускоренного вычисления циклических сверток длины равной произведению взаимно простых чисел Терещенко, А.Н. Задирака, В.К. Кудин, А.М. Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
title	Использование циклических сдвигов для ускоренного вычисления циклических сверток длины равной произведению взаимно простых чисел
title_alt	Використання циклічних зсувів для прискореного обчислення циклічних згорток довжини, яка дорівнює множенню взаємно простих чисел Using of Cyclic Shifts for Fast Computation of Cyclic Convolution of Length Equal to Multiplication of Relatively Primes
title_full	Использование циклических сдвигов для ускоренного вычисления циклических сверток длины равной произведению взаимно простых чисел
title_fullStr	Использование циклических сдвигов для ускоренного вычисления циклических сверток длины равной произведению взаимно простых чисел
title_full_unstemmed	Использование циклических сдвигов для ускоренного вычисления циклических сверток длины равной произведению взаимно простых чисел
title_short	Использование циклических сдвигов для ускоренного вычисления циклических сверток длины равной произведению взаимно простых чисел
title_sort	использование циклических сдвигов для ускоренного вычисления циклических сверток длины равной произведению взаимно простых чисел
topic	Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
topic_facet	Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
url	https://nasplib.isofts.kiev.ua/handle/123456789/60239
work_keys_str_mv	AT tereŝenkoan ispolʹzovaniecikličeskihsdvigovdlâuskorennogovyčisleniâcikličeskihsvertokdlinyravnoiproizvedeniûvzaimnoprostyhčisel AT zadirakavk ispolʹzovaniecikličeskihsdvigovdlâuskorennogovyčisleniâcikličeskihsvertokdlinyravnoiproizvedeniûvzaimnoprostyhčisel AT kudinam ispolʹzovaniecikličeskihsdvigovdlâuskorennogovyčisleniâcikličeskihsvertokdlinyravnoiproizvedeniûvzaimnoprostyhčisel AT tereŝenkoan vikoristannâciklíčnihzsuvívdlâpriskorenogoobčislennâciklíčnihzgortokdovžiniâkadorívnûêmnožennûvzaêmnoprostihčisel AT zadirakavk vikoristannâciklíčnihzsuvívdlâpriskorenogoobčislennâciklíčnihzgortokdovžiniâkadorívnûêmnožennûvzaêmnoprostihčisel AT kudinam vikoristannâciklíčnihzsuvívdlâpriskorenogoobčislennâciklíčnihzgortokdovžiniâkadorívnûêmnožennûvzaêmnoprostihčisel AT tereŝenkoan usingofcyclicshiftsforfastcomputationofcyclicconvolutionoflengthequaltomultiplicationofrelativelyprimes AT zadirakavk usingofcyclicshiftsforfastcomputationofcyclicconvolutionoflengthequaltomultiplicationofrelativelyprimes AT kudinam usingofcyclicshiftsforfastcomputationofcyclicconvolutionoflengthequaltomultiplicationofrelativelyprimes

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

Репозитарії

Схожі ресурси