Содержание к диссертации
Введение
Глава 1. Основные понятия и определения
1.1. Этапы и структурная схема общего метода синтеза
1.2. Применение полиномиальных преобразований для синтеза устройств вычислительной техники
1.3. Определения теории полей Галуа и полиномиальной алгебры
1.4. Программируемые логические интегральные схемы класса FPGA.
1.5. Элементы теории цепей Маркова.
1.6. Методы многопараметрического анализа
Глава 2. Методы синтеза генераторов дискретных стохастических процессов класса марковских и их функций над полем GF(2N )
2.1. Методы синтеза и анализа генераторов простых и сложных однородных цепей Маркова на основе полиномиальных марковских моделей
2.2. Метод синтеза генераторов детерминированных и стохастических функций однородных и неоднородных цепей Маркова
2.3. Метод синтеза генератора дискретных случайных величин с заданным законом распределения
Глава 3. Устройства для вычисления значений дискретных детерминированных нелинейных функций на основе нелинейных полиномиальных преобразований над полем Галуа
3.1. Схемы устройств для вычисления значений ДДНФ, определенные при использовании операций над элементами поля Га-луа
3.2. Метод синтеза устройств для вычисления ДДНФ от M переменных на основе системы из L нелинейных полиномиальных функций от M L переменных
3.3. Метод синтеза генераторов неоднородных цепей Маркова и их функций на основе цифровых устройств для вычисления ДДНФ
3 Глава 4. Схемы функциональных модулей операций в конечных полях 115
4.1. Функциональные модули операции умножения элементов поля GF(2N ) как IP-ядра. 118
4.2. Функциональные модули операции умножения элементов расширений поля GF ((2K ) F ) на основе IP-ядер 126
4.3. Схемы функциональных модулей операции вычисления остатка от деления по заданному простому модулю для потока чисел 136
Глава 5. Методология реализации устройств на основе однотипных IP-ядер, представленных на ПЛИС/FPGA 146
5.1. Методика оценки степени соответствия функционального модуля архитектуре ПЛИС/FPGA 149
5.2. Методика синтеза устройств ВТ на основе IP-ядер на распределенных вычислительных системах с программируемой архитектурой 153
5.3. Методики синтеза и идентификации семейства генераторов, описываемых полиномиальными марковскими моделями 161
Глава 6. Техническая реализация и применение устройств ВТ на основе нелинейных полиномиальных преобразований над конечным полем 182
6.1. Генераторы ДСП класса марковских и их функций на РВС ПА «Медведь» 185
6.2. Устройства ВТ определенных подклассов теоретико-полиномиальных преобразований на РВС ПА «Медведь» 187
6.3. Анализ степени соответствия архитектуре ПЛИС/FPGA функциональных модулей операции умножения элементов полей вида GF(2 ) и GF ( 2K ) 196
6.4. Синтез функциональных модулей операции вычисления остатка от деления по заданному модулю для потока чисел на ПЛИС/FPGA 214
6.5. Схема устройства ВТ для отображения и варьирования состояния дискретной модели КМС(N) и ее частных случаев 221
Заключение. 236
Список сокращений и условных обозначений. 242
Список литературы. 244
- Применение полиномиальных преобразований для синтеза устройств вычислительной техники
- Метод синтеза генераторов детерминированных и стохастических функций однородных и неоднородных цепей Маркова
- Метод синтеза устройств для вычисления ДДНФ от M переменных на основе системы из L нелинейных полиномиальных функций от M L переменных
- Функциональные модули операции умножения элементов расширений поля GF ((2K ) F ) на основе IP-ядер
Применение полиномиальных преобразований для синтеза устройств вычислительной техники
Полиномиальные преобразования (ПП) находят свое применение при решении задач синтеза широкого класса устройств вычислительной техники, предназначенных для генерирования числовых последовательностей с заданными свойствами [1, 3, 9, 13, 30 32, 55, 58, 64, 67, 72 – 73, 83, 105 - 106, 118, 120, 131, 143, 194 - 195, 212, 268, 284, 319, 321, 329 - 330] и цифровой обработки сигналов [23 - 24, 33, 48, 63, 70, 81, 124, 137, 155, 163, 204, 221, 255, 320].
Синтез генераторов равномерно распределенных псевдослучайных чисел (ПСЧ) производится при использовании линейных функций, задаваемых на основе частных случаев полиномов Жегалкина И.И. над полем GF(2) [304].
Ci GF(2), i = 0, n -1, заданы на основе образующего многочлена поля Галуа степени n [174]. Решение задачи синтеза указанного генератора предполагает использование регистра сдвига и сумматоров по модулю два [131, 161, 212]. В литературе данные ГПСЧ носят название «регистр сдвига с линейной обратной связью». Путем варьирования коэффициентов Ci GF(2), i = 0, n -1, в (1.2.3) организуется наиболее предпочтительный режим работы указанного генератора, с целью генерирования так называемой последовательности максимальной длины или М-последовательности [5, 11, 29, 74, 83, 130 - 131, 212, 219, 226, 329 - 330]. Указанные ГПСЧ находят применение для реализации недетерминированных методов тестирования и диагностики, использующие в качестве входного воздействия на контролируемое устройство вычислительной техники последовательность чисел, генерируемых с равной частотой, достаточно большой длины [51, 305]. Известны также методы самотестирования и сигнатурного анализа цифровых устройств с использованием генераторов М-последовательностей [166 - 169, 193, 197, 242 - 243], в том числе генераторов линейных марковских функций [357], а также линейных последовательностных машин [73, 169] и детерминированных автоматов на основе линейных преобразований [186, 239]. Достоинство указанных подходов – относительная простота синтеза устройств, производящих линейные преобразования. Вместе с тем, для указанных подходов ограничен класс процессов и явлений, адекватно отображаемых при их применении.
Теоретический и практический интерес представляют вопросы синтеза генераторов дискретных стохастических процессов (ДСП) класса марковских и их функций на основе автоматных преобразований (см. п. 1.4) [1, 3, 7 -10, 13, 15, 55, 58 - 60, 64, 148, 154, 169, 194, 197, 241 - 243]. Указанный класс стохастических преобразований в общем случае является нелинейным [86], что расширяет его возможности для адекватного отображения более широкого класса процессов и явлений, по сравнению с линейными преобразованиями, в таких областях, как исследование стохастических процессов различной природы [22, 31, 34 – 35], статическое моделирование [180, 253, 263 - 264], распознавание образов [40, 250], передача и защита информации в сетях ЭВМ [74, 88, 226, 248, 260, 300], в автоматизированных системах обработки информации, тестирования и диагностики цифровых устройств [13, 82, 84, 219, 223] и др. Одним из подходов к синтезу генераторов ДСП класса марковских и их функций является подход, использующий теорию конечных полей [174, 261]. Перспективность этого подхода определяется приложением функций конечных ЦМ [58 – 59, 217], возрастающей сложностью вероятностных дискретных моделей [58 – 59] и эффективностью арифметики конечных полей в задачах цифровой обработки информации [29, 127, 194, 338, 340 - 341]. Аппарат конечных полей используется для решения задач синтеза генераторов ДСП указанных классов на основе вероятностных автоматов [7, 18 - 19, 55, 58 - 60], применяемых для моделирования широкого класса случайных нелинейных процессов и явлений [7, 18 - 19, 55, 58 - 60, 64, 154, 205]. Каждая из стохастических функций, описывающих указанные генераторы, представима на основе композиции [162, 217], включающей генератор дискретной случайной величины (ДСВ) с заданным законом распределения [333, 364] и конечный детерминированный автомат (КДА). Функция перехода КДА, в свою очередь, представима и на сдвиговых регистрах [85], и как система булевых функций (БФ) на основе ПП в полях Га-луа [174]. Второй вариант более предпочтителен, т.к., в отличии от первого варианта, позволяет закодировать элементы множества входов и множества стояний КДА произвольным образом. В [262] теоретически обоснован рекурсивный алгоритм синтеза произвольной БФ на основе полиномов вида (1.2.2), а также получены оценки сложности указанных БФ. В качестве меры сложности выступают элементарные схемы (ЭС) – двухвходовые элементы, реализующие произвольную БФ от двух переменных [37]. Предложенные результаты хорошо согласуются с фундаментальными работами из области дискретной математики и ее приложений [95, 176, 179, 218, 225, 301, 303]. Данные обстоятельства открывают возможность для синтеза генераторов ДСП класса марковских и их функций на основе ПП, допускающих распараллеливание, а также оперативное изменение свойств указанных генераторов путем варьирования коэффициентов нелинейных полиномиальных функций (НПФ), определенных над конечным полем вида GF(2n ) [174]. К недостатку данного подхода относится экспоненциальное увеличение количества коэффициентов НПФ при линейном росте разрядности генерируемых двоичных чисел последовательности [105 – 106, 118, 194 - 195]. Вместе с тем, возможность организации распараллеливания процесса вычисления НПФ при использовании свойств полиномиальной алгебры (на теоретическом уровне), а также большого количества однотипных специализированных процессоров (на уровне физической реализации), актуализирует исследования по созданию теоретических основ и методов синтеза специализированных устройств ВТ на основе ПП в конечных полях.
Для решения задачи синтеза специализированных устройств вычислительной техники, используемых для выполнения как автоматных преобразований так и цифровой обработки сигналов, широкое применение находят теоретико-числовые и полиномиальные преобразования в полях Галуа [63]. Анализ известных подходов, используемых при разработке высокопроизводительных устройств ВТ, показывает, что характерным для них является широкое применение различных форм параллельной обработки информации, а исследования отечественных и зарубежных учёных указывают на целесообразность применения теории чисел для целей её кодирования [23 - 24, 33, 48, 63, 70, 73, 81, 124, 137 - 138, 155, 163, 174, 204, 221, 255, 320]. Если значение сигнала, подаваемого на вход данного устройства, рассматривать как подмножество алгебраических систем, обладающих структурой кольца или конечного поля [174, 261], то реализацию ортогональных преобразований для данного сигнала можно свести к теоретико-числовым преобразованиям (ТЧП), определяемым в пространстве кольца вычетов целых чисел по модулю целого числа М [138]. ТЧП представляют собой преобразования, выполняемые над полиномами в целочисленных отсчетах, определяемые в пространстве кольца вычетов по модулю образующего полинома с заданными свойствами – над полиномиальными вычетами. Данные преобразования носят название теоретико-полиномиальных преобразований. В работах [155 - 157] ТПП определены как дискретные преобразования в различных базисах посредством применения полиномиальной алгебры. К ним, в частности, относятся базисные функции дискретных ортогональных (унитарных) преобразований (Фурье, Уолша, Виленкина-Крестенсона, Хартли, Меллина, слэнт, косинусного и др.) [36, 53, 81, 84, 221, 327]. Достоинство ТЧП и ТПП заключается в том, что сложные операции умножения чисел, принадлежащих кольцу, можно заменить более простыми операциями, такими как сложение и сдвиг полиномиальных массивов в кольце, а также оптимально «спроектировать» структуру преобразования на основе ТПП [155]. Одним из направлений развития параллельных вычислительных технологий является система счисления в остаточных классах (СОК), обладающая высоким уровнем естественного параллелизма при выполнении арифметических операций. Суть СОК состоит в представлении целого числа в виде упорядоченного набора неотрицательных вычетов по группе взаимно простых оснований (модулей), причем арифметические операции сложения, вычитания и умножения выполняются над вычетами меньшей разрядности независимо друг от друга и без межразрядных переносов [24, 70]. Вместе с тем, недостатком ТЧП и СОК является то, что разрядность групп чисел, представляющих собой неотрицательный(ные) вычет(ы), ограничена снизу величиной основания (модуля), который является простым числом, не кратным степени два. Данное обстоятельство накладывает ограничение на эффективность выполнения операций над числами, представляемыми в ТЧП и СОК на уровне двоичных разрядов, и степень распараллеливания операций, производимых над указанными числами.
Метод синтеза генераторов детерминированных и стохастических функций однородных и неоднородных цепей Маркова
Определим схемы, описывающие генераторы детерминированной функции ЦМ [106]. Пусть конечная простая ОЦМ задана системой вида (1.5.2). Разобьем множество состояний данной ОЦМ - S, на непересекающиеся подмножества Д,
Рассмотрим процесс {Yt} с к состояниями, определяемый условием Yt=i, i = \,k, если в момент времени ґЦМ находится в каком-либо состоянии st подмножества Д. Процесс {ГД называют марковской функцией [248] (функцией цепи Маркова [55, 58, 143] или укрупненным процессом, если ЦМ допускает укрупнение [145]). Далее состояния процесса {Yt }, будем обозначать символами
Схема генератора функции ЦМ, заданная АВА A(3) согласно (1.5.7), изображена на рис. 2.2.1, где блок 2 является КДА типа Мура, функции перехода и выхода которого задаются соответственно функциями (x, s) = s и (s) = y . x = и Схема генератора функции ЦМ, описываемого АВА типа Л(3) При определенных ограничениях (см., например, [145]) на разбиение (2.2.1), процесс {Yt} является новой ЦМ с к состояниями и матрицей переходных вероятностей размера Ах А, определяемой по заданной F [145]. В общем случае укрупненный процесс нельзя представить в виде простой конечной цепи Маркова. В этом случае вероятностные характеристики процесса {Yt} определены в соответствии с [227]. Введем в рассмотрение следующие автоматные модели из класса автономных вероятностных автоматов [30, 55, 58, 217]. Определение 2.2.1 [106]. Автономным вероятностным автоматом АВА{\) будем называть систему где 5 = {52}, і = \,тп, - множество состояний АВА{\), U - дискретная случайная величина, принимающая конечное множество значений U = {ul,u2,...,u1} на і входе АВА{\) с вероятностями pi,р2,...,pj, Л-=1, 0 Л 1 A(u,s) - функ 2—1 ция переходов, ставящая паре (u,s) в соответствие новое состояние se S согласно (1.5.6), 7TQ - вектор начального распределения состояний. Последовательность состояний автомата (2.2.2) является простой ЦМ [55, 58, 145]. Если распределение (р1,р2,...,р1) входных букв автомата (2.2.2) отве 76 матрица размера я?хя?, соответствующая символу ut, 1 т -лз + 1, то закон функционирования ЦМ определяется ЭСМ F системы (1.5.2) размерности тхт [58, 217]. Замечание 2.2.1. Для стохастической матрицы размера mxd, тФ d, булевы стохастические матрицы M(ut) имеют размер mxd и их число в разложении (1.5.5) определяется величиной /1 md- я? +1 [58]. Определение 2.2.2 [106]. Автономным вероятностным автоматом АВА(2) будем называть систему где U, 5, A(u,s), л0, те же математические объекты, что и в (2.2.2), у={У1,У2,...,Ук} - конечный выходной алфавит, S(s): S Y - функция, отображающая S на Y Таким образом, АВА(2) задается как конечный детерминированный автомат Мура со случайным входом. Последовательность его состояний является цепью Маркова, а последовательность букв в алфавите Y - марковской функцией {Yt} [55]. Определение 2.2.3 [106]. Автономным вероятностным автоматом АВА(3) будем называть систему АВА(3) = (/, S,Z,A(u,s),ju(z/ S),7T0) , (2.2.4) Лемма 2.1.2 [174] выполняется и для частного случая - произвольной функции от одной переменной, отображающей G в G Обозначим символом у/ отображение (функцию), представляющее собой суперпозицию отображений (ph i = 1, 2, 3. В данном разделе определены теоретические основы синтеза генераторов ДСП из класса функций ЦМ, заданных на основе автоматных моделей (2.2.2) -(2.2.5) при использовании НПФ от одной и от двух переменных вида (1.3.4) и (1.3.5), соответственно, над полем Галуа. Для НПФ вида (1.3.5) над полем G, когда выполняется условие q = 0, имеет место частный случай - НПФ от одной переменной вида (1.3.4): / = 2" — 1, h = а0 bt, хє G. i=0 Синтез генераторов ДСП, описываемых АВА(1) - АВА(5), сводится к синтезу элементов данных АВА, таких как: управляемый генератор случайных кодов (УГСК) [58, 108, 268] и ЦВУ, описываемое КДА [72, 80, 217]. При этом элементы данных АВА определены на основе НПП. Замечание 2.2.5. Реализация УГСК на базе генераторов ДСВ представлена в п. 2.3. Методы анализа и синтеза генератора конечной простой ОЦМ вида (2.1.2), описываемого АВА(1), определены в п. 2.1. Рассмотрим методы синтеза генератора функций ЦМ [105 - 106, 114 - 115, 118]. Схема генератора марковской функции вида {Yt} определена на основе следующей теоремы. Теорема 2.2.1 [105 - 106]. Для цепи Маркова, заданной системой (1.5.2), где начальное значение переменной q полиномиальной функции f(x,q) определяется распределением ж0, последовательность состояний процесса {Yt}, заданного разбиением (2.2.1) на множестве S, представима последовательностью значений функции 4,1=g(q)» f(x,q) - суперпозицией двух НПФ вида (1.3.4) и (1.3.5) над GF(2"), минимальная степень которых удовлетворяет условию 2п 1, где1 т —т + 1. Если задать начальное значение переменной q НПФ /(л, q) по стохастическому вектору л0, то при использовании функции у/1 можно получить последовательность состояний процесса {Yt}. Таким образом, теорема 2.2.1 устанавливает, что генератор ДСП из класса детерминированных марковских функций вида {Yt}, задаваемый системой вида (2.2.3), представим распределенной полиномиальной моделью вида [105 -106] ПМ1 =(U,y/i = g(q) f(x,q),7io) (2.2.6) Генераторы ДСП класса марковских и их функций реализуемы на основе структурной схемы, представленной на рис. 2.2.1. Получение значений, снимаемых с выходов блоков «Генератор ЦМ», «g {z)y , «g"(z)», «fx{x,q)y , « ґЛх", у)» и «g(q)», производится параллельно, а элементы указанных ДСП формируются конвейерно, с сохранением промежуточных результатов в блоках «Генератор ЦМ , « f,(x , о)», « fAx \ у)» и «g(q) . Модуль «D» есть набор D триггеров, составляющих регистр с общим синхровходом. В результате, указанная схема позволяет реализовать вычисление элементов ДСП данных классов при использовании распределенных вычислений. При этом в соответствующих блоках реализовано вычисление значений НПФ над полем Галуа от одной переменной вида (1.3.4) и от двух переменных вида (1.3.5). В данной связи, схема, приведенная на рис. 2.2.1, получила название распределенной полиномиальной схемы (РПС).
Метод синтеза устройств для вычисления ДДНФ от M переменных на основе системы из L нелинейных полиномиальных функций от M L переменных
На основе теоремы 3.2.2 определим, что система НПФ вида (3.2.5), вычисляющая значение многочлена вида (1.2.2) из классов А(к), к = \,п, и Bid- d- ... ; d ), d є [і, п], / = 1, я?, также принадлежит к указанным клас сам полиномов. Согласно выражениям (3.2.1) и (3.2.3), порядки оценок временной сложности для ЦВУ НПФ вида (3.1.2), реализованной на базе параллельной и систолической схем [1181, выраженных в ЭС, равны От (я?-я) и От (я?-2л) соответст венно. Тогда как согласно теореме 3.2.2, на основе (3.2.8), порядок оценки временной сложности для ЦВУ, определенного системой НПФ вида (3.2.5) равен От (logJm-n)) и не зависит от количества полиномов в системе - к. Для па SPF раллельной схемы ЦВУ различие в порядке оценок по сравнению с предложенной схемой будет линейно возрастать как с ростом степени поля GF(2"), так и количества переменных я?. Для последовательной схемы различие порядков оценки при увеличении п возрастает экспоненциально, и возрастает линейно при увеличении я?. Порядки оценок аппаратной сложности для схем указанных ЦВУ, согласно (3.2.2) и (3.2.4), составляют Оп (п2 -2) и Оп (п2.2(л+1)(ш_1)) а порядок оценки аппаратной сложности для ЦВУ системы из к НПФ вида (3.2.5), определенной на базе теоремы 3.2.2 согласно (3.2.9), равен Оп (к-ш-п). Различие порядков оценок аппаратной сложности для данных схем возрастает экспоненциально при увеличении степени поля GF(2n). Причем для систолической схемы различие возрастает в два раза быстрее, чем для параллельной. В случае увеличения количества переменных (я?) рост различия порядка оценок будет экспоненциальный, причем скорость роста данного различия для параллельной схемы будет в два раза выше, чем для последовательностной [289].
107 Таким образом, получено преимущество при вычислении НПФ от т переменных вида (1.2.2), отображающей заданную ДДНФ вида у/(х,..., я ), на базе
ЦВУ системы НПФ вида (3.2.5) согласно теореме 3.2.1 по порядкам оценок как временной так и аппаратной сложности. Преимущество по оценкам временной сложности получено за счет организации распараллеливания вычисления разрядов значения заданной ДДНФ. Данное преимущество достигается за счет отнесения ДДНФ к заданным классам - А(к), k = 1,n, и Bid d ... ; d ),
Представив величины у и я,... я , определенные как л-разрядные векторы, на основе множества / -разрядных векторов, таких что п = к-1 - [у(1) ,..., у(т)}, \х(1) , ..., х( Л, t = 1,m, выражение (3.2.10) определяется как система НПФ, определенных над полем GF(2k) [286]: возможность представления НПФ вида (1.2.2) от т переменных над GF(2n) на основе системы из /НПФ вида (1.2.2) над GF(2k) от т-1 переменных каждая, 1 = п/к. Имеет место Утверждение 3.2.1 [289]. Полиномиальная функция вида (3.2.10) от т переменных над элементами поля GF(2n) реализуема как система из /полиномов вида (3.2.11) от / т переменных над элементами GF(2к), п-к-1.
Справедлива Теорема 3.2.3 [289]. Оценки временной и аппаратной сложности вычисления полиномиальной функции вида (3.2.10) от т переменных над GF(2n), на основе системы из / полиномиальных функций вида (3.2.11) над GF(2k) от т-1 переменных, принадлежащих к классам А(р) и В ш:г ... t/(z,)), z = l,l, равны Т\ = maxJlog2 cf;.z) [ и Qs = 7-Xz-ilXT-i 4 соответственно.
На основе утверждения 3.2.1 предложен и теоретически обоснован метод синтеза ЦВУ ДДНФ, принадлежащей классам А(п) и Bid; ... ; d ), d.-n, j = \,m, на основе системы из 1НПФ, включающий три этапа [289]. 1) представление множества значений и т множеств значений переменных указанной ДДНФ / -разрядными векторами, п = к 1 [286]. 2) определение / ДДНФ, принадлежащих классам А(к) и Bid ... ; d ,), d.-k, / = 1, #?/, на основе отображений вида (1.3.1) для т-1 множеств эле ментов GF(2k) в одно множество элементов GF(2k). 3) вычисление коэффициентов для /НПФ от т-1 переменных каждая, определенных над GF(2k), которые соответствуют отображениям вида (1.3.1), полученным на этапе 2). Порядки оценок временной и аппаратной сложности ЦВУ НПФ вида (3.2.10), представленной системой многочленов вида (3.2.11) над GF(2k), вычислены на основе операций над GF{2) и составляют 0(log(#? п)) и 0(l2 -т-п), 1=п/к, соответственно. Это определяет преимущество данных ЦВУ по порядкам оценок временной сложности в сравнении с ЦВУ, определенными на основе схем, предложенных в п. 3.1: примерно в n-(m+\og2n)l\og2(m-n) раз для параллельной и примерно в (т-2п -log2m)/log2(m-n) раз - для систолической, соответственно [286]. Разработан программный продукт, позволяющий решать задачу синтеза ЦВУ ДДНФ от я? переменных, синтезируемых на основе системы из / многочленов от 1-т переменных над полем GF(2k), п-k-l. При этом количество всевозможных значений ДДНФ, а также каждой из я? ее переменных, не превышает 2к [233].
Функциональные модули операции умножения элементов расширений поля GF ((2K ) F ) на основе IP-ядер
Функциональные модули операции умножения элементов расширений поля GF ((2k )f ) на основе IP-ядер Элементы G(n) описываются многочленами степени не выше (n - 1) в фор ме a(x) = an-1xn-1 + ... + a1x + a0 , ai GF(2), i = 0,n -1 [174]. Каждый элемент a(x) есть вычет по модулю P(x), где P(x) = xn + dn-1xn-1 + ...+ d1x + d0 - неприводи мый многочлен степени n, образующий для G(n) [174]. a(x) степени не выше (n - 1) может быть представлен как вектор из n двоичных переменных (). G представимо в виде G, где . G изоморфно an-1, ...,a1,a0 (n) ((kf)) k f = n((kf)) GF(2k )/ R(x), где R(x) = x f + g f-1x f-1 +...+ g1x + g0 - неприводимый полином сте пени f над GF(2 ), , [174]. Элемент G представим k x, gi GF(2k ) i = 0, f -1 ((kf)) 127 многочленом степени f -1 - A(x) = af-1x f-1 +K+ a1x + a0 , где x, ai GF(2k ) , i = 0, f -1, A(x) GF((2k )f ) , ai , i = 0, f -1 есть k-разрядные двоичные векторы [174]. A(x) n=k f - , f Тогда элемент определяем разрядным вектором то есть векторами размерностью k. Многочлен R(x) является образующим для G((kf) ) . ФМ ОУ/G((kf) ) представляют интерес, в частности, с практической точки зрения [317, 337, 339]. Синтез ФМ ОУ/G((kf) ) , сводится к выполнению операций над G(k) = GF(2k ) : умножения (в том числе - на константу) и сложения. ФМ ОУ/G((kf)) привлекательны тем, что операция умножения над G(n) , изоморфным G((kf)) , n=k f , сводится к набору операций над G(k ) , которое имеет в 2n-k раз меньшую размерность и представимо k-разрядными векторами, имеющими в f раз меньшую размерность.
Предложен метод синтеза ФМ для вычисления произведения элементов поля G((kf) ) , включающая два этапа [282 - 283].
Этап 1 – синтез ФМ для операции умножения в G(k) .
Этап 2 – синтез ФМ для умножения на константу и сложения по модулю два элементов G(k) .
В результате, ФМ, выполняющий ОУ/G((kf) ) , включает в себя модули первого типа (М1), выполняющие ОУ/G(k ) , и модули второго типа (М2), выполняющие операции умножения на константу и сложения по модулю два для элементов G(k) . Результаты, снимаемые с выходов М1, сохраняются по синхросигналу в регистрах. Затем сохраненные результаты поступают на М2, с выходов которых снимаются f групп из k разрядов, составляющих произведения элементов поля G((kf) ) . Таким образом, результаты, полученные при использовании М1 в предыдущий период времени между приходом синхросигналов, сохраняются в регистрах с целью использования в текущий период времени для выполнения операций внутри М2. В этот же период времени задействованы М1 для обработки вновь поступивших данных. В результате организована конвейерная обработка данных.
Операция вычисления остатка от деления по заданному модулю, отличному от степени числа два, в конечном поле (далее - Операция) используется для синтеза ФМ, применяемых для решения широкого круга задач. К данным задачам, в частности, относятся: реализация рекуррентных преобразований над потоками чисел [187], тестирование и диагностика преобразователей информации [169], реализация кодовых последовательностей и конгруэнтных генераторов псевдослучайных чисел (ГПСЧ) [16 - 17, 206, 299]. ГПСЧ применимы, в том числе, для построения (синтеза) генераторов ДСП класса марковских и их функций, представленных в пп. 2.1 - 2.3 и в п. 3.3. Операция является наиболее трудоемкой по критерию временной сложности, что критично для случаев, когда существует потребность в обработке за заданный период времени больших объемов информации с использованием модульной операции. Вопросам снижения оценок времени задержки функционирования для ФМ, реализующих Операцию, в литературе уделяется большое внимание. Примеры различных способов реализации на основе ФМ Операции представлены в [16 - 17, 206, 299]. При реализации встроенных систем или прототипов различных устройств, использующих Операцию, актуальна задача представления их структурных схем в базисе ПЛИС класса FPGA [308, 355 - 356, 361 - 363].
Предложены две схемы ФМ Операции на основе последовательного (поэтапного, конвейерного) выполнения заданного набора операций, с сохранением результатов, полученных на каждом этапе [126, 298 - 299]. При этом различные этапы вычисления остатков для чисел в потоке реализуются параллельно. Данное обстоятельство позволяет обеспечить конвейерную обработку последовательностей чисел заданной разрядности и снизить оценки временной сложности получения остатков по модулю, отличного от степени числа два, для обрабатываемого потока чисел.
Применение Операции для синтеза ФМ рассмотрим на примере конгруэнтного ГПСЧ по простому модулю, где используется Операция. При формировании последовательностей псевдослучайных чисел актуальна задача синтеза конгруэнтного мультипликативного ГПСЧ над конечным полем вида [229]: где р = 2 р +1 - jf-разрядное число Смита, р - простое число, а - примитивный элемент. Период последовательности чисел, полученной на основе (4.3.1), равен величине р -1 [229]. ГПСЧ, реализуемый согласно (4.3.1), характеризуется относительно высокой оценкой временной сложности выполнения Операции, которую обозначим как mod р [1871. S J
Исправить данный недостаток призваны предлагаемые ФМ вычисления Операции, позволяющие организовать конвейерный метод вычисления, который включает w этапов. Для первой схемы - w= f-k + l этап, где /и к- разрядности (х q) и хм (х) соответственно [298 - 299]. Для второго ФМ значение w определяется эмпирическим путем на основе заданных значений /и к, а также р [116 - 117, 208]. Для предложенных ФМ Операций различные этапы вычисления остатков, включающие различные операции, производятся одновременно для системы из w формул вида (4.3.1) [298 - 299]: = 1, f -k +1, имеет номер f -1, а младший – 0. Тогда на этапе y, y = 1, f -k +1, выполняются две операции сравнения: первой величины, представленной либо n старшими разрядами произведения (на первом этапе) либо (на последующих этапах) n +1 разрядами частичного остатка под номерами f - y +1, f - y, …, f - y-k +1, с величинами ps и 2ps . На выход поступает наименьшая положительная разность первой величины и одного из вычитаемых - ps либо 2ps . Если первая величина меньше ps , то на выход поступают разряды частичного остатка f - y, f - y -1, …, f - y-k +1, а также разряд произведения под номером f - y -k , выступающий как младший разряд полученного результата. Следствие распараллеливания процесса выполнения операции mod ps согласно (4.3.2) - снижение времени генерирования числа xi+1. Но при этом требуется сохранять промежуточные результаты, полученные на каждом из этапов вычисления остатка от деления по модулю ps . С выхода ГПСЧ (4.3.2) снимаются псевдослучайные числа (ПСЧ), представляющие собой чередование i-х элементов подпоследовательностей {xi( j)}, j = 1, f -k +1. Для обеспечения воспроизведения псевдослучайных последовательностей (ПСП) данного типа, следует задать f - k +1 начальных состояний [298 - 299].
Обозначим T(q) , T (q) и Q (q) , Q (q) - оценки временной и аппаратной сложности операций умножения на константу q и сложения c q соответственно. Кроме того, Tcm (c), Tsb (c) и Tmx есть оценки временной сложности для операций сравнения и вычитания с константой c, а также для операции мультиплексирования k-разрядных чисел. Оценки аппаратной сложности для указанных операций обозначим Qcm (c), Qsb (c) и Qmx .
