автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Полиномиальные модели автоматных преобразований над полем GF(2")

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ПОЛИНОМИАЛЬНЫЕ МОДЕЛИ АВТОМАТНЫХ ПРЕОБРАЗОВАНИЙ НАД ПОЛЕМ СГ(2")

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

Работа выполнена в Казанском государственном университете.

Научный консультант доктор технических наук,

профессор Захаров Вячеслав Михайлович.

Официальные оппоненты доктор физико-математических наук,

профессор Алексеев Валерий Борисович,

доктор физико-математических наук, профессор Аблаев Фарид Мансурович,

доктор физико-математических наук, профессор Николаев Михаил Леонидович.

Ведущая организация: Ульяновский государственный

университет.

Защита состоится «22» декабря 2005 г. в 14 час. 30 мин. на заседании диссертационного Совета Д 212.081.21 в Казанском государственном университете по адресу: 420008, г. Казань, ул. Кремлёвская 18, корп. 2, ауд. 217.

С диссертацией можно ознакомится в библиотеке Казанского государственного университета.

Автореферат разослан «21» ноября 2005 г.

Ученый секретарь Диссертационного Совета, кандидат физ.-мат. наук, доцент

О.А.Задворнов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы диссертации. Аппарат теории конечных полей и полиномиальная алгебра широко используются в различных областях, связанных с преобразованием информации: в задачах синтеза вычислительных однородных структур, в теории кодирования, при построении генераторов псевдослучайных чисел, в криптографии, в системах передачи информации, в анализе динамических стохастических систем и др. Эффективность этого аппарата определяется адекватностью алгоритмам построения однородных сред преобразования информации, свойствами полиномов над конечным полем и рядом других особенностей. Особый теоретический и практический интерес представляют поля GF(2"). Алгоритмы вычисления в таких полях допускают параллельную реализацию и дают возможность выполнять потоковые преобразования над п-мерными векторами. При этом оцениваемая аппаратная сложность предлагаемых решений не является априорно высокой из-за свойств модулярной арифметики.

Приложение теории конечных полей для моделирования (получения) и преобразования случайных дискретных процессов исследовано в меньшей степени. Имеются решения частных задач: глубоко проработаны задачи синтеза генераторов случайных независимых последовательностей на основе полиномов. над полем GF(2) (Гавел Я., Кирьянов Б.Ф., Кузнецов В.М., Латыпов Р.Х., Мансуров P.M., Осмоловский С.А., Песошин В.А., Столов ЕЛ. и др.); предложено применение операций поля GF(2") для моделирования частных типов случайных линейных зависимых процессов (Бухараев Р.Г., Гладкий B.C., Карлайл Е.У., Кознов A.B., Taylor L. и др.); применение линейных автоматов над полем GF(2) для моделирования некоторых видов простых цепей MàpKOBa ( Столов Е.Л., Захаров В.М.).

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

Сложность задач этого направления исследований связана, в частности, с. вопросами описания случайных процессов из класса функций цепей Маркова полиномиальными функциями над конечным полем. Перспективным подходом решения отмеченной проблемы, является подход, основанный на моделировании вероятностных автоматов полиномами над полем GF(2"). Такие задачи рассматривались в работах Захарова В.М., Нурутдинова Ш.Р., Шалагина C.B., Соколова С.Ю. (1998-2004 г.). Марковские последовательности и их функции

(марковские функции (МФ)) широко используются для построения вероятностных моделей в таких областях как статистическое моделирование, распознавание образов, защита информации, техническая диагностика цифровых устройств. Применение моделей цепей Маркова (ЦМ) в качестве базовых при построении вероятностных моделей автоматного типа обуславливает интерес исследователей к теории моделирования марковских последовательностей, функций конечных ЦМ и построению автоматных моделей генераторов МФ, что отражено в многочисленных публикациях по данной тематике (автрры: Анишин A.C., Альпин Ю.А., Бухараев Р.Г., Гилл А., Гиоргадзе А.Х., Гладкий B.C., Гло-ва В.И., Захаров В.М., Кемени Дж., Кирьянов Б.Ф., Лоренц A.A., Нурмеев H.H., Paz А., Песошин В.А., Поспелов Д.А., Салимов Ф.И., Столов E.JL, Хамитов Г.П., Яковлев В.В. и др.).

Вероятностный автомат является обобщением конечного детерминированного автомата (КДА). В связи с этим возникает необходимость глубокого исследования вопросов представления КДА полиномами над полем GF(2"). По этому направлению важное практическое значение представляет задача отображения полиномиальных моделей КДА в однородные вычислительные среды.

В этой связи представляется актуальным выполнение настоящего исследования, основанного на новом подходе моделирования широкого класса дискретных случайных процессов с дискретным временем в поле GF(2"). Развиваемые методы включают предложенные понятия полиномиальных моделей в поле GF(2") дискретной случайной величины (ДСВ), простых и сложных цепей Маркова и марковских функций и доказательство соответствующих теорем, устанавливающих взаимосвязь стохастических матриц и полиномиальных функций над GF(2") и обосновывающих алгоритмы моделирования рассматриваемых процессов.

Цель исследований. .Целью диссертационной работы является создание теоретических основ, алгоритмов и методик представления детерминированных и вероятностных автоматных моделей полиномиальными функциями над полем G F (Г).

В соответствии с этой целью, исследования проводились в следующих направлениях.

1. Создание теоретических основ для разработки моделей эффективного умножителя в поле GF(2"), как расширение поля GF(2), эффективного умножителя в поле GF(22k), как расширение поля GF(2").

2. Разработка метода представления КДА полиномиальными моделями над полем GF(2"), повышающих эффективность их реализации в однородных вычислительных структурах.

3. Создание теоретических основ для моделирования и преобразования дискретных случайных процессов с дискретным временем из класса МФ, основанного на полиномиальной алгебре в поле GF(2"), моделирования в поле GF(2") случайных последовательностей с последействием, представления структурных моделей генераторов МФ и вероятностных автоматов в базисе полиномиальных функций. По первому направлению решались следующие задачи.

1. Разработка эффективного умножителя в поле GF(2"), как расширения поля GF(2).

2. Разработка способа построения поля вида GF({2k)2), изоморфного полю вида GF(2n).

■ 3. Разработка способа умножения в составных полях Галуа, позволяющего сократить вычислительную сложность. По второму направлению решались следующие задачи.

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

2. Исследование возможности и разработка алгоритма представления конечного автомата однородной сетью над GF(2") и оценка сложности такого представления.

3. Разработка метода проектирования однородных схем по описанию конечного автомата.

4. Разработка алгоритма минимизации количества элементов однородной вычислительной сети над GF(2"), реализующей конечный автомат с памятью.

По третьему направлению решались следующие задачи.

1. Исследование задач представления стохастических матриц и моделирования дискретных случайных величин, и марковских, функций средствами полиномиальных функций в поле -GF(2").

2. Разработка структурных моделей автономных вероятностных автоматов (ABA), генераторов ДСВ, МФ и методики их построения в базисе полиномиальных функций над полем GF(T).

3. Разработка автоматной модели из класса вероятностных автоматов с перестраиваемой структурой й метода моделирования на её основе случайных дискретных процессов с последействием в поле GF(2").

4. Разработка метода представления неоднородных ЦМ и их функций в поле GF(2").

Методы исследований. Для решения поставленных задач использованы методы теории вероятностей, теории вероятностных автоматов, теории графов, теории чисел, аппарат- конечных полей, линейной и полиномиальной алгебры и дискретной математики.

Исследования поддержаны грантом Российского фонда фундаментальных исследований № 99-01-00163 «Энтропийно-сложностные свойства дискретных вычислительных моделей»; грантом Российского фонда фундаментальных исследований № 03-01-00769 «Сложностные свойства классических и квантовых вычислений»; программой «Университеты России», проект № 015-04-01-52 «Синтез и сложность детерминированных и вероятностных дискретных вычислительных моделей».

Научная новизна работы

1. Доказана теорема и разработаны: метод построения составных полей GF((2k)2), изоморфных полю методика построения схем умножения в составном поле вида CF(2 ), позволяющие сократить вычислительную сложность и повысить скорость выполнения операции умножения - базовой операции, необходимой для реализации схем генераторов МФ. Разработана методика построения составных полей для предлагаемых схем умножения.

2. Доказана теорема, обосновывающая возможность представления произвольно-заданного детерминированного отображения в поле GF(2") в виде многочлена от s переменных, а также доказана теорема и разработан метод, с помощью которого можно вычислить коэффициенты такого многочлена. Доказана теорема и разработан алгоритм уменьшения количества ненулевых коэффициентов при высших степенях полиномиальной функции над полем GF(T). Разработан алгоритм представления КДА однородной вычислительной сетью.

3. Введено понятие полиномиальных моделей марковских функций над GF(2"). Предложены полиномиальные модели случайных процессов вида МФ над полем GF(2") из класса, порождаемого ABA с заданными ограничениями на функции перехода и выхода, в частности модели сложных ЦМ, марковского источника и конечноавтоматных случайных последовательностей. Модели МФ представлены в виде суперпозиций полиномиальных функций от одной и двух переменных над полем GF(2"). ■

4. Разработаны метод и алгоритм синтеза генераторов МФ в виде суперпозиции полиномиальных функций над полем Галуа. Доказаны теоремы,

_ обосновывающие метод.

5. Разработана полиномиальная модель над полем GF(2") генератора дискретной случайной величины (ДСВ).

6. Решена задача автоматного моделирования процессов с последействием, как расширение модели ABA. Предложен метод моделирования над полем GF(2") подкласса случайных последовательностей на основе ABA с динамически перестраиваемой структурой.

7. Разработан метод моделирования неоднородных цепей Маркова и вероятностных автоматов на основе полиномиальной алгебры в поле GF(2").

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

GF(2 ) позволяет сократить необходимую для реализации умножения вычислительную сложность. Спроектированные по предлагаемой методике схемы умножения могут быть использованы в качестве базовых блоков в широком классе устройств, применяющих алгебру полей Галуа. Построены структурные схемы типовых элементов синтезируемых параллельных и последовательных однородных цифровых схем. Разработан алгоритм, позволяющий по описанию конечного автомата синтезировать однородную (параллельную или последовательную) цифровую схему. Предложенные полиномиальные модели генераторов ЦМ и МФ позволяют использовать аппарат полей Галуа при моделировании рассматриваемых случайных процессов, что дает' возможность представить их в виде алгебраических выражений, допускающих параллельную реализацию. Предложенные структурные схемы генераторов ЦМ и МФ над полем GF(2") дают возможность их непосредственного использования при проектировании специализированных автоматных моделей. Предложены генераторы тестовых последовательностей, новизна которых защищена 6-ю. авторскими свидетельствами. Полученные оценки аппаратных затрат, представленные описания алгоритмов и программ дают разработчикам,возможность их непосредственного использования при проектировании специализированных устройств по современной технологии программируемых логических интегральных схем (ПЛИС). Разработанный метод моделирования. МФ полиномиальными функциями над полем GF(2") дает метод решения задачи управления вероятностными характеристиками. МФ. На базе полученных теоретических результатов разработаны Новые технические решения, защищенные авторскими свидетельствами.

Достоверность научных результатов! Основные полученные результаты сформулированы в виде теорем и утверждений, приведены их математические доказательства. Достоверность полученных методов и алгоритмов обуславливается формулировкой и доказательством, соответствующих теорем и утверждений. Работоспособность полученных методов и алгоритмов проверялась с помощью программного моделирования и средствами' САПР ПЛЙС/Xilitix. Данные о функционировании предложенных схем подтверждаются тестированием разработанных программных моделей и алгоритмами моделирования схем с помощью САПР «Xilinx Foundation З.Н».

Результаты использованы в НИР за 2001-2005гг. по гранту РФФИ № 99-0100163 «Энтропийно-сложностные свойства дискретных вычислительных моделей», по гранту РФФИ № 03-01-00769 «Сложностные свойства классических и квантовых вычислений», по проекту № 015-04-01-52 «Синтез и сложность детерминированных и вероятностных дискретных вычислительных моделей» программы «Университеты России», в ОАО «КНИАТ» (г. Казань), в Центре новых информационных технологий Республики Татарстан (г. Казань), в ГИБДД МВД Республики Татарстан (г. Казань) и в учебных процессах кафедры прикладной математики и кафедры теоретической кибернетики Казанского государственного университета и кафедры КСИБ Казанского технического университета (КАИ) им. А.Н.Туполева.

На защиту выносятся следующие результаты:

1. Метод вычисления коэффициентов многочлена, реализующего отображение поля СР(2") в себя.

2. Теорема, устанавливающая возможность реализации конечного автомата однородной сетью над ОР(2").

3. Алгоритм и методика реализации конечного автомата однородной сетью над ОР(2").

4. Теорема, устанавливающая возможность вычисления коэффициентов примитивного многочлена для построения поля вида ОР((2к)2), изоморфного полю вида СР(22к).

5. Методика -построения схем умножения в составных полях Галуа, позволяющая сократить вычислительную сложность и повысить скорость выполнения операции умножения.

6. Теорема, доказывающая существование алгоритма уменьшения количества ненулевых коэффициентов при высших степенях полинома над полем СР(2Р), используемого при полиномиальном моделировании отображения . вР(2т) *вР(2к) ОР(2к), р=т+к.

7. Полиномиальные модели и метод представления МФ над полем ОР(2"). Теоремы, устанавливающие взаимосвязь МФ и полиномиальных функций надполем СР(2").

8. Структурные модели генераторов ЦМ и МФ над полем ОР(2") и методика их построения в базисе полиномиальных функций над полем ОР(Т).

9. Полиномиальная модель представления генератора дискретной случайной величины полиномиальной функцией в поле ОР(2").

10.Автоматная модель из класса вероятностных автоматов с перестраиваемой структурой и её полиномиальное представление над полем ОР(2").

11.Комплекс прикладных программ, реализующих, предложенные методики и алгоритмы.

Апробация работы. Основные результаты работы докладывались и обсуждались на Итоговых научно-технических конференциях Казанского государственного университета (Казань, 1988-2005rT.);VIII Всесоюзной конференции по теоретической кибернетике (Горький, 1988г.), Всесоюзной научно-технической конференции "Повышение качества и надежности продукции, программного обеспечения ЭВМ и технических средств обучения" (Куйбышев, 1989г.), Международная конференция «Информатизация правоохранительных сис-тем»(Москва, 1997г.),Между народная конференция «Безопасность информа-ций»(Москва, 1997г.), Всеросс. научно-метод. Конференция "Интеграция образования, науки и производства — главный фактор повышения эффективности инженерного образования" (Казань, 2000г.), научно-практической конференции по актуальным вопросам информатики, вычислительной техники и информационной безопасности (Казань, 2001г.); Всероссийском семинаре «Сеточные методы для краевых задач и приложения» (Казань, 2000г., 2002г., 2004г., 2005г.); VII-M Международном семинаре «Дискретная математика и её приложения» (Москва, 2001г.), научно-практическая конференция по актуальным вопросам информатики, вычислительной техники и информационной безопасно-сти(Казань, 2001г.), Республ. Научн.-практ. конференция «Интеллектуальные системы и информационные технологии» (Казань, 2001г.), International confer-ёпсе OFEА'2001(S.-PETERBURG,2001), IX Всероссийская школа-семинар «Современные проблемы математического моделирования» (Ростов - на Дону, 2001г.), XIII Международной конференции «Проблемы теоретической, кибернетики» (Казань, 2002г.); V Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, 2002г.); Двенадцатой Международной конференции по вычислительной механике и современным прикладным программным системам (Владимир, 2003г.); Первая Всероссийская научная конференция «Методы и средства обработки информации»(Москва, 2003г.), городском семинаре «Методы моделирования» (Казань, 2002-2005гг.), ряде семинаров кафедры Теоретической кибернетики Казанского государственного университета (Казань, 2001-2005гг.), VIII Международном семинаре «Дискретная математика и ее приложения» (Москва, 2004г.), международная научная конференция «Актуальные проблемы математики и механики» (Казань, 2004г.), VI Международная конференция «Дискретные модели в теории управляющих систем»(Москва, 2004г.), XIV Международная конференция «Проблемы теоретической кибернетики» (Пенза, 23-28 мая 2005г.), Вторая Всероссийская научная конференция «Методы и средства обработки информации (МСО'2005)» (Москва, 5-7 октября 2005г.).

Публикации. По теме диссертации опубликовано 40 работ, включая 1 монографию. Основные результаты отражены в 40 публикациях.

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

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка используемой литературы, включающего 140 наименований, и приложения. Общий объем работы составляет 222 страницы, включая 36 рисунков и .18 таблиц. В конце каждой главы имеются выводы. .

Содержание работы

Во введении обосновывается актуальность темы диссертации, дается определение цели и задач исследования, приводится перечень основных результатов, выносимых на защиту. Представляется актуальным выполнение настоящего исследования, в котором разработаны теоретические основы, алгоритмы и методики представления детерминированных и вероятностных автоматных моделей полиномиальными функциями над полем ОГ(2"), а также разработан метод синтеза однородных вычислительных структур в поле СР(2"). Такой подход позволяет во многих случаях получать управляемые преобразователи и-мерных сигналов, для которых может быть легко использована технология ПЛИС. Дана структура диссертации..

В первой главе «Вычислительные модели преобразований над полем СР(2")» выполнены исследования, состоящие в разработке и исследовании эффективности создания вычислительных моделей в полях GF('2"/^. Вводятся известные понятия, определения и модели, необходимые для решения задач диссертационной работы. Содержатся необходимые сведения из аппарата полей Галуа. Сформулированы и доказаны теоремы, определяющие метод построения умножителя в поле ОР(2"), как расширение поля GFf2J. Разработаны структур^ ные модели таких умножителей.

Теорема 1.3. Пусть элементы поля СР(2") представлены в виде векторов, соответствующих многочленам по модулю примитивного многочлена т(х) над йР(2) степени и. Тогда для любых а,ре ОР(2п)

а.'Р=а01р+а,АрТ+ ... +ап.,А"-'рт, где а = (ао, а1, ..., а,,.,), ¡3 = (Ь0, Ь/, ..., Ь,,./) - элементы поля ОР(2"), А - сопровождающая матрица многочлена т(х).

Исследованы условия представления любого отображения в поле Галуа в виде многочлена от п переменных. Разработан метод вычисления коэффициентов многочленов, реализующих отображение поля ОР(2") в себя.

Теорема 1.5. Пусть С=ОР(2"), — произвольная функция, отобра-

к

жающая й ъ в, н существует многочлен /(х)~^а1х'>г~ 2"-1,*,а( яв.

••

ляющийся представлением отображения (7 в том смысле, что/(с)=<р(с) для всех с ей. Тогда коэффициенты многочлена / в <7 вычисляются при помощи выражения А-СГ' ,Р,где А=(а0, а,, ..., аг)т — вектор коэффициентов многочлена/(х), Г=(<р(0), <р(1), ..., <р(£~'))т (( — примитивный элемент поля С) - вектор значений отображения ср на элементах поля <7,

С =

1 0 0 0 о 4

0 1 ^-г-Ы то<1(г) с

0 1 с2 £ 2н тос!(г) с-2

0 г с с'- г-

1 1' 1 1 1 )

= 2" —1,1 < I < г — 1

(1)

Для моделирования произвольного отображения конечного поля в себя многочленом над 0^(2") и реализации его однородными вычислительными структурами получен способ вычисления коэффициентов этого многочлена.

Теорема 1.6. Пусть С=СР(2"), произвольная функция от 5 пере-

менных, отображающая рх<7х...х(? в (} и существует многочлен

(2)

являющийся представлением отображения (р в том • смысле, что /(с,с1,...,е)=<р(с,<1,...,е) для всех с, ¿1,..., ёеО. Пусть Ух- мерная матрица из 2" х2"...х 2" значений функции <р на элементах поля й: У0_ 0,.... о=<?(0, О,..., 0),

I •

Уи,)2, ...,11 =ф((.("), £ — примитивный элемент поля О, ¡¡, /2,..., Ь=0,г; г=2"-1. Тогда коэффициенты многочлена/(хьх2, ....х^ вычисляются при помощи системы выражений

с »^г. ь.....у, /2 к =0^;

^о,,*,.:., и^С'У*1' 0,, *.....У, /, = оГ7;/3 = <й;...; /, = <£г;

.....ь-ь *)=с'^-'>(и.....*). =0^;

- А=У®; . ' _

Матрица С' была определена в (1). Матрица А={а,ш.....■„}, ¡¡Ль..., ¡, =0,г,

г=2"-1 ■ содержит значения коэффициентов многочлена /(х1,х2,...,х^.

Знак * означает, что соответствующий индекс последовательно принимает значения от 0 до 2"-1.

Следствие Теоремы 1.6. При з=2 коэффициенты многочлена/(х1,х2,...,х^ вычисляются по формуле: Л~С'У(С')Т, где V 2-х мерная матрица, содержащая 2"х2" значений функции <р на элементах поля С.

Разработаны однородные вычислительные структуры, вычисляющие значения многочленов в поле СР(2").

Во второй главе «Модели схем умножения в расширениях-поля СР(2")» решается задача построения эффективных схем умножения в поле СР(2"). Решение основано на представлении поля СР(2") составным полем вида СР((2к )2), где п=2к. Дан обзор наиболее эффективных существующих методов построения схем умножения в составных полях Галуа, позволяющих сократить вычислительную "сложность операции умножения, которая является основной операцией при вычислении значений полиномов вида (2) в структурных схемах генераторов МФ. Разработан метод вычисления коэффициентов примитивного многочлена второй степени над полем вида ОР{{2к)2), изоморфного полю вида СР(21к). Метод основан на доказательстве Теоремы 2.1.

Теорема 2.1. Для синтеза поля С7Р(22к), как расширение поля СР(2к), всегда можно найти коэффициенты а,Ье ОР(2к) примитивного многочлена хи(х)=х2+ах+Ь, хеСР(22к), задающего структуру СР(22к).

Доказательство. Пусть С=СР(2к), Р— Ср(22к). Зададим элементы поля Р в базисе поля СР(2) при помощи примитивного многочлена р(х) =х2к+р2к-1Х2к~ '+... +р1х+р0, р,^.СР(2). Многочлену р(х) соответствует сопровождающая матрица

'0 0 0 . . 0

1 0 0. . . 0 л

А = 0 1 0 . . 0 Рг

.0 0 0 . . 1 Ргк-\,

При помощи матрицы А построим матрицу Т размера 2ку(22к-1), столбцами которой являются элементы поля Р в векторном представлении. Матрица Т • строится таким образом, что /-ый столбец матрицы Т равен первому столбцу

матрицы А', I = 1,22* -1. При этом А1"'1 = Е, где Е - единичная матрица.

Далее,' столбцам матрицы Т поставим во взаимно однозначное соответствие степени примитивного элемента £ для которого р(ф=0. Вектор, состоящий

из степеней £ обозначим Г = 1 2 3 ,...,4) •

Известно, что если поле Р=ОР((2к)2) есть расширение поля 0=0Р(2к), то

г1к

элементами поля О, будут неподвижные точки автоморфизма сj (ос) = а . , где вер, 0 < у < 1. В этом случае существует два автоморфизма: а0 (а) = а (тривиальный случай, для которого все элементы поля остаются неподвижными) и 2*

СГ[ (а) = а . Зададим элементы поля б в виде неподвижных точек автомор-

2к

физма ег,(а) = аг . Для этого выполним автоморфизм сГ|(а) и найдем неподвижные точки в 2. Для этого возведем все компоненты вектора 2 в степень 2*, учитывая что £ = ^, то есть, выполним возведение в степень, вычисляя показатель степени по тод(221,-1). Обозначим эту операцию как Г2 (тос1(22 Так как = неп6движными будуТ

компоненты вектора Е вида ' ¿;'(2 . Учитывая что ^(2 -1)(2 = , найдем 2к-1 неподвижных точек. Выпишем эти

элементы: Обозначим через С. То-

гда полученное множество можно переписать в виде: {^'.г^2,^3,...^2^1}, добавив к данному множеству нулевой элемент, получим поле С. По построению С является примитивным элементом поля в. Далее строим поле Р=СР(2и) как расширение полученного поля G=GFf2^. Чтобы это сделать, необходимо найти базис в О. Согласно теории, базис поля СР(2к) состоит из к элементов. Для определённости, пусть это будет множество: В={£(2, ...,Ск}-

Далее будем рассматривать поле СР^) как простое алгебраическое расширение степени 2 поля ОР(2к), получаемое присоединением корня С, примитивного многочлена второй степени над СР(2к). Найдем этот многочлен. Запишем его в виде: лр(х)=л2+ах+Ь, где а,6е СР(2к) — пока неизвестные коэффициенты, х<^(ЗР(22к), причём:

а = + а2^2<2*+1)... + (3)

Ъ = Ь^1 чА<?2(2,+1)-+^(2Ч,) , а„ъ,* ОЕ(2). (4)

Учитывая, что существует гомоморфизм между элементами поля СР(22к) в виде степеней примитивного элемента £ и элементами поля ОР(2к) в виде степеней того же £ запишем

или

<f2 + axiг" +2 + +1>+' +... + akt12'+ + + Ъ2?г(2Ч,) +...+ bkCi(2'+,) = 0.

Вместо степеней примитивного элемента f используем соответствующие им векторные представления из матрицы Т, что позволит записать систему линейных уравнений относительно а^а^.^.а^Ъ¡,Ь2,GF(2). Система уравнений имеет единственное решение, т.к. ранг системы уравнений равен 2к (как следствие примитивности модулярного многочлена р(х) степени 2к и свойств элементов поля GF(22k)). Подставляя найденные значения aia2,...,atbi,b2l...,bteGF(2) в выражения (3 - 4), найдем коэффициенты a, b, а значит построим примитивный многочлен w(x)=x2+ax+b, задающий структуру

поля GF(2lt), как простого алгебраического расширения степени 2 поля GF(2k). ■

Следствие Теоремы 2.1. Существует алгоритм синтеза составного поля вида GF((2k)2), изоморфного полю вида GF(22k) на основе примитивного многочлена \v(x)=x2+ax+b.

Доказательство следствия следует из доказательства теоремы 2.1

Предложена методика построения схем умножения в составном поле вида

71 '

GF(2 ). Методика проиллюстрирована на примере схем умножения в полях

GF(2 ) и GF(2 ). Для рассмотренных схем умножения вычислены, описывающие их логические выражения, разработаны соответствующие логические схемы, получены сложностные и временные оценки. Построены составные поля GF(2") заданной размерности.

Проведена сравнительная оценка вычислительной сложности и задержки предлагаемых схем умножения с традиционным подходом и модификацией алгоритма Карацубы-Офмана (АКО). Приведены сравнительные оценки для полей' GF{24) и GF{28), для этих полей построены схемы умножения, которые промоделированы и реализованы в САПР «Xilinx Foundation 3.1 i».

В третьей главе "Полиномиальные модели детерминированных автоматных--преобразований над полем GF(2")" рассматривается способ построения конечного автомата в виде однородной сети над полем GF(2"). Пусть Am=(X,Y,Q,8,X) и АМ)=(Х,, Y:,Qi,8i,Xi) - конечные автоматы Мура.

Определение 3.1. Автомат АМ1 моделирует автомат Ам, если существуют отображения <р: Х->Х,, у/: Y-^Yj, , такие что

х(8(х.д))=5,(ф), x(q))\ va(x,q))=x,(9(x),x(q)). (5)

Содержательный смысл этого определения заключается в следующем. _ Множества X, Y, Q можно отождествить с некоторыми подмножествами

Xl,Yl,<2i." A'j с Xi,Y1 <zY,,Q, cQj. При этом на указанных подмножествах автомат Ami ведет себя также как и Ам.

Под однородной сетью будем понимать сеть автоматов Аы=(X,, У), Q„ ¿¡,X), i = l,N, обмен информацией между которыми производится по однотипным и локальным связям. Положим Q QN. Часть входов и выходов

автоматов Ам, i = l,N, являются входами и выходами сети. Пусть X' - входной алфавит и У - выходной алфавит сети. Функционирование сети описывает автомат А'м =(ЛТ ,Y ,Q ,<5 ,Я). Покажем, как по произвольному автомату-Лм=(Х,У,0,д,Л) можно построить однородную сеть, причем автомат А'м, описывающий сеть, будет моделировать работу автомата Ам.

Теорема 3.1. Пусть M-(X,Y,Q,S(x,q),X(x,q)) конечный детерминированный автомат, тогда М моделируется автоматом Mi~(F,F,F,Sj(x,q),li(x,q)), где Х1: Yh QJCZF=GF(2"), где п наименьшее го натуральных чисел, для которых выполнены неравенства 2" > \Х\, 2" > |К|, 2" > |ig|, где - число элементов множествах = = г = 2" — I, е F.

/.О У=О /=0 J-о

Доказательство. Доложим п - наименьшее из натуральных чисел, для.которых выполнены неравенства 2" >\Х\,2" 2" ■ где число элементов множествах Обозначим F=GF(2"). Закодируем элементы множеств X, Y, Q элементами поля F, что эквивалентно построению отображений tp, yf, х в (5)-Чтобы не вводить новых обозначений, будем считать, что функции S, Л определены на некотором подмножестве F*F и принимают значения в F. Из интерполяционной формулы Лагранжа следует, что любую функцию <b:F-^F можно

г

представить в виде многочлена Ф(/) = г = 2" -1, /,а, е F. Рассмотрим

(=0

теперь отображение S(x,q), в котором х будем считать параметром. Тогда для

г

каждого х: S(x,q) = г = 2"-1. Коэффициенты а/х) сами являются

J.0

функциями на F со значениями в F, откуда следует, что

Г - г г

Oj{x) = ,г = 2" -1. Окончательно: = > г = 2"-1,

x,q,'ap е F, где все операции выполняются в поле F. Правая часть для S(x,q) определена на множестве F*F, обозначим её Sj(x,q). Аналогичные рассуждения применим к отображению X(x,q)._ Построенный автомат Mi=(F,F,F,Si(x,q),Xi(x,q)) моделирует исходный автоматМ. т

Рассмотрен автомат без памяти АЛ=(Х,У,Л), для которого X и У соответственно входной и выходной алфавиты, Я:X —» У. Пусть п наименьшее из натуральных чисел, для которых выполнены неравенства 2" > \Х\, 2" > |У|. Пусть б = ОГ(2") Закодируем элементы множеств X и У элементами поля О (это эквивалентно построению отображений <р и у/ в (5)). Будем считать, что отображение Я определено на множестве б со значениями в (7. Зададим отображение Л с помощью многочлена от одной переменной над полем

¿г(х)=£а,х',г=:2п-1,х,а,еО. (6)

/=о

Таким образом, построен автомат А'х моделирующий исходный автомат Ах Построена модель такого автомата при помощи многочлена от двух переменных. Пусть |_1о£2|АгУ= и, т * т < п - 2т. Разобьем входной алфавит X на непересекающиеся подмножества 1¥ и IV и <2 = X, «|2|. После этого отображение Л примет вид А: IV х -> У. Закодируем элементы множеств IV, <2, У элементами поля С — С/Г(2т). Отображение Л представим в виде многочлена от двух переменных над полем О: г г

- ¿С ч'■> г-2т - 1, а^ е С. Вычисление значений коэф-

1=оу=о • ' •

фициентов а,у в.^/Ну.д,) выполнено согласно следствию Теоремы (1.6). Автомат А V =(£?х(5,(?, моделирующий автомат Аг, можно реализовать парал-

лельной вычислительной схемой.

Рассмотрен случай автомата с памятью без выхода. Такой автомат описывается системой А0 = (X, . Выберем наименьшее значение п так, чтобы

выполнялись неравенства 2" > |Х[ 2" > ¡¿>|. Элементы множеств X и () закодируем элементами поля б = 0/г(2"). Получим, что отображение 3(х,д) определено яа подмножестве <7 х С/ со значениями в О. Представим его в виде многочлена

3(х,д)= ¿Х-лЛ/'. г = 2"-I, х,д,аиеО. (7)

Автомат (0,0,3(х,д)), моделирующий автомат А0 =(Х, <2,<5), реализуется однородной схемой, состоящей из блоков П,у, каждый из которых вычисляет произведение a¡jXJд'. Приведены методики синтеза последовательных и параллельных структур по описанию конечного автомата без выхода над полем

Исследован случай, при котором можно уменьшить количество элементов однородной сети, реализующей конечный автомат с памятью. Предложен способ выбора кодирования элементов входного и выходного множества исходного конечного автомата с памятью, при котором однородная схема, реализующая этот автомат содержит определённое количество блоков. Полиномиальная модель f(x,q), x,qeGF(2") может быть минимизирована в случае её представления в виде многочлена L(u) от одной переменной, ие GF(22"). Решение задачи уменьшения количества блоков Я,, f = 0, г, r = 21п -1, заключается в увеличении числа нулевых коэффициентов при высших степенях полинома L(u). Разработанный способ основан на методе минимизации функции перехода конечного детерминированного автомата (КДА) без выходов М = (X,Q,S) , определённого в поле Галуа, где X е GF(2"') = G - множество входных сигналов, Q е GF(2k) = F - множество состояний, отображение S:GxF~>F, или S(x,q) — q', где xeG, q,q'eF. Отображение S можно представить в виде многочлена вида (7) от двух переменных над полем GF{ 2"), где и.= тах(тД). Представим S в виде отображения 5': GF{2P) —> GF(2P), р = т + к. При этом 8\z) = z\ z,z' е GF(2P), z—\x,q)T, z' — {x',q')T. В результате 5' представляется в виде многочлена от одной переменной:

s=2?-i,z,al<=GF(2<'). (8)

'=0

Для реализации многочлена вида (8) требуется s-1 блоков, каждый из которых вычисляет произведение a,z',/= -.1.

Теорема 3.2. Пусть М = (X,Q,S) конечный детерминированный автомат без выходов, .'где X<=GF(2"') = G - множество входных .'элементов, Q е GF(2k) = F - множество состояний, отображение S:GxF~>F, или S{x,q) = q', где хе G, q,q' е F. Если построить полиномиальную модель для S(x,q) в виде многочлена от одной переменной L(u), u-(x,q)T над полем GF(2'"+k), то существует такое отображение S' :G*F -+GxF, для которого многочлен L(u) имеет минимальную степень.

Доказательство. Доказательство основано на возможности увеличения числа нулевых коэффициентов при высших степенях полинома L(u) пут?м использования компонент векторах' в отображении б'.

Отображению 5 поставим в соответствие отображение <^':GF(2,,)->■GF(2Í'), р = т + к. При этом 5'00 = г', еСР(2р),.

\7* Т

г = (х,<7) , г' = (х ,ц'у . В результате 8'представляется в виде многочлена вида (8). Отображение = т!, где г = {х,д)т, г' = (х',д')т проиллюстрировано на рис. I. Из рис. 1 видно, что вектор г'содержит компоненту х\ которая в дальнейших вычислениях не участвует и может принимать произвольные значения. Следовательно, отображению <5 можно поставить в. соответствие не одно отображение 5', а семейство отображений А- вида 6': А: (х,д)' —» (х',д'У , где хеХ, и Ух' е СР(2"'). Семейство Д содержит 2Ш отображений вида

«У', по одному для каждого л-'.

* т 6' х -

я

1

Рг

Рис. 1.

В множестве Д выделим такое отображение, для которого многочлен (8) имеет минимальную степень. Зададим элементы поля ОР(2р) в виде многочленов от £ где % - примитивный элемент поля ОР(2р), являющийся корнем примитивного многочлена т(х)= з? + (¿р-/хр~1+...+<1/х+ с10, <1-,еСР(2). Построим систему уравнений относительно коэффициентов многочлена (8) на основании Теоремы 1.5: Л = С_12',где 'А = (а0,а1,...,агУ, Я■= {2'0,г\,...,г'г)т, С'1 -матрица

(1) над О/7^, еС^), г = 2р-1, р = т+к. ■

Компоненты вектора А будут иметь вид а, =<эг,п + ,

/ = 0,г, г=2р-1, е СР(2). Компоненты вектора в свою очередь, будут иметь вйдг"

= //0' +... + 1Кт_1)С1 + <гю?"' +... + ^х*-,)^"1, е 0/г(2), (9)

где л '¡—(¡¡,о, 'и, - кт./), я\=(<Т1,о,аи. - ¡ц>аи 6 .

Вектору соответствует матрица, содержащая коэффициенты многочленов (9):

0,0 '0.1 ■■• Г0,»/-1 °0,0 •■• °0,*-1 ^1.0 '•• ""КО <Т!,*-1

Каждый столбец матрицы 2.' содержит коэффициенты при соответствующих степенях элемента £ Запишем совокупность многочленов (9) в векторном виде:

Г') = Ли» 'а».-. ит<?+ (к,, 'и.-. - •

+ 0о.п,-1, {1.т-1, ■■■. 'г.ст-/^ + (&0,0, <71,0,~; &г,о) £"'+

+(00./. о';./.--. + — + С^о.*-/, <Т1,к-1,—. аг.ы)Г<?~'-

(10)

Введём следующие обозначения:

THto.hti.h-, 'л/, ' = 0, от -1. а/,/,..., <тг^г, у = 0,Л-1, т+к=Р:

В результате (10) перепишем следующим образом:

2.\е, .....Г') = Тое+ Т,(!+ ... +Тт.,Г'+

+АхГ+о,Г+;+ ... +Ам<Г'- (11)

Аналогично запишем компоненты вектора А:

.....Г') =Аве+А,{'+ ... +АР_,Г', (12)

где А1=(ао1Ьаи,..., аг^Т;, /' = 0,р -1.

Представим элементы матрицы С' в виде многочленов от £ степени не выше р-1 с коэффициентами из СР(2). Эти коэффициенты зависят от вида примитивного многочлена т(х)= У + о^л/'"'+...+£//*+ с10, с?, еСР(2), корнем которого является элемент £ Таким образом, матрица С-1 будет иметь вид:

' С(<?, I'.....= С,?+[... (13)

Преобразуем выражение для Л, применяя формулы (11), (12) и (13). В результате получим: •

........ +С1>.,Г')у.

х(Т0!?+ ... ... +Ок.,Г')- (14)

Для того, чтобы в правой части (14) был многочлен степени, не превышающей р-1, необходимо все многочлены от />р-1 заменить на представления в виде многочленов от ]<р-1. В результате преобразования правой части (14) получим выражение вида:

. Аое+А,^+ ... +АР.,Г'= иГСв, С,, ... ,СР.1, Т0, Т,.....Т^РоРи

■ +и(С0, С,.....Ср.1, Т0, П ..., Тт.,р0р„ ...Ры){'+ :..

+ Ьр.,(Со, С,.....Ср.,, То, Т,, .."., Т„,.,Р„Р,.....(15)

где

[С0, С,,..., Cp_i, Та, 7],..., 7*m_,, D0 ,£),,..., Dt_, ] —

где Уу1,^* е GF(2) и их значения зависят от коэффициентов модулярного многочлена/я^.

Для того, чтобы построить многочлен (8) необходимо найти значения компонент векторов Т), у=0,т-1. Таким образом полностью доопределяется преобразование 6'. Построим неоднородную линейную систему относительно компонент векторов 7}, j = Q,m-\, приравнивая коэффициенты при одинаковых степенях £ в (15):

m-1 рЧ р-1

'C^D,, гдеЛ,определено в (12),

j=q 1=0 7=0 /=0

1И-1 р-1 /с-I iM

j=0 j—0 7=0 )=0

Обозначим = ^ /¡p^i ; тогда (17) запишется как: i=0

m-1 - _

^M'J')Tj = Al+N(,) . ,/ = 0~Fi-

(17)

(18)

Значение V1" в (18) может быть вычислено заранее. Далее,' обозначим

Т=(Т0,Т,.....М">=(Мо(", М,">, .... Мр_/'}), система (18) запишется:

А/5Г=Л/+///; ,/=0,р-1. (19)

где Л/''1 - матрица размерности 2р*рТ, Т — вектор размерности р2?, АиЪР - вектора размерности 2Р; причем компоненты обозначенных объектов из ОР(2),

1=0,р-1 Или . покомпонентно ={"$!}) Т=((и)рг' >

А, =(аг,)1Гхр1 = (я;,/)2%/); /=0,р-1. Распишем систему (19) подробно:

"»0.0 - mo.i

т\Я т1Л

0.(p-lX2'-])

„(П

1.(^1X2'-I)

f t

(0.0

m<0 min mm

^ 2'-i.o J'-I.I — "V-up-ixi'-i);

0,2*—1

Vi-ll'-l^

^»f-U+'V-Liy

(20)

/ = 0,p—l.

Далее строим системы уравнений относительно компонент Т, соответствующих коэффициентам а,, /=0, ...,2р-1 в А.

Цо'Vo -'„-u'-i = <wv

Чо • 'о,о + тц • 'од + • = «,., + ;

-¿Г" Л „ + Wr" ■. + -+•*.„.=«,„_,+ ц

(21)

0.0T"'í,l '0,1^— Vu'-I ~ '.í-' Л-"

i = 0,2' -1.

Таким образом, получили зависимости /у от возможных значений компонент коэффициентов ак многочлена (8). Т.е. задавая различные значения коэффициентам а* многочлена (8), «достраиваем» отображение 8'.

Выражения (21) позволяют вычислить конкретные значения вектора Т в зависимости от значений ..... <?~'), /-я компонента которого соответству-

ет коэффициенту a¡ в системе (12). Придавая коэффициентам при высших степенях L(u) a¡ нулевые значения до тех пор, пока объединённая система линейных уравнений из системы (21), соответствующим a¡, будет совместна, находим оптимальную (для рассматриваемой постановки задачи - минимальную) степень многочлена (8). щ

В четвертой главе «Полиномиальные модели вероятностных автоматов и функций конечных цепей Маркова над полем GF(T)t> рассматривается алгебраический подход к представлению автоматных моделей МФ на основе полиномов над полем GF(2"). Предлагаются полиномиальные модели и структурные схемы генераторов, позволяющие моделировать над полем GF(2") случайные процессы вида МФ из класса, порождаемого ABA с определенными ограничениями на функции перехода и выхода. ABA является частным случаем вероятностного автомата (В А) общего вида. Рассматривая ВА без входа (случай, когда X содержит только одну букву) будем иметь систему:

ABA = (Y,S,m(S',}'/S)), (22)

где X и Y - конечные входной и выходной алфавиты, S - конечное множество состояний, через /j.(s',y/s,x) обозначается условная вероятность того, что ABA, находясь в состоянии s eS и получив на вход букву х еX, перейдёт в новое состояние s' е. S тл выдаст букву у е Y. ВА (22) определяет семейство автономных вероятностных автоматов, различающихся ограничениями на Y, S. и способами задания ft{s',yls)-. Автомат (22) выполняет роль генератора дискретных случайных последовательностей (СП) с дискретным временем. Ограничения, накладываемые на (22) позволяют получить семейство классов СП (простые и сложные" цепи Маркова и различные немарковские СП) - марковские функции.

Обозначим символом U дискретную случайную величину (ДСВ) вида

и2, ..., ■ (23)

\Pi, Рг> •••> PiJ

_ _ . : / .

где u¡, i = (1, /), значения U и p¡ - их вероятности, О < p¡ < 1, ]Г = 1. Стохас-

/=1

тический вектор p¡, р2,..., p¡ обозначим символом р. Множество значений u¡, í" = 1, /, обозначим символом U.

Конечная простая однородная цепь Маркова может быть задана системой

вида

(5, Р,7Г0), • (24)

где 5' = {í|>j2,...,jot} - конечное множество ее состояний, Р - стохастическая матрица размера тхт, ж0 - /п-мерный стохастический вектор, задающий начальное распределение вероятностей состояний.

Представление ABA без выхода полиномиальной моделью над полем GF{2" ) обосновывает Теорема 4.1, доказательство которой дает методику синтеза автоматных марковских моделей в . базисе полиномов над полем GF(2"). Пусть дан полином (7), где п наименьшее натуральное число, удовлетворяющее условию 2" >1.

Теорема 4.1. Для заданной системы (24) можно указать случайную величину U (23) и полиномиальную функцию (7), со случайным начальным значением одной из переменных и коэффициентами a-tj е G такими, что случайная

величина U может быть преобразована функцией (7) в заданную ЦМ значений функции.

Доказано; что для системы (U,f(x,q), лг0) справедлива Теорема 4.2, обратная Теореме 4.1. ■

г

Теорема 4.2. Пусть заданы /(х q)— ^jctyx'ql, r — 2" -1, a,j,x,q eG

U1-й

с множеством {xf}, i = 1,1 значений переменной x и множеством {<?y }, j = l,m значений переменной q, случайная величина U с множеством значений {к,}, / = !,/, стохастический вектор р и вектор л0. Тогда последовательность вычисленных значений полинома f(x,q) является реализацией простой однородной ЦМ с множеством состояний {qj}, описываемой стохастической матрицей Р

размера |{<7у|» элементы которой однозначно определяются вектором р и по-' линомом f(x,q).

Далее представлены основные полиномиальные модели и структурные схемы исследуемых генераторов МФ. Разобьем множество 5 из системы (24) на непересекающиеся подмножества А1г Л2, ..., Ак :

к _

=5,/4; =0 при ¿^у,/,у = 1Д . (25)

1=1 '

Рассмотрим процесс {У,} с к состояниями, определяемый условием У, =/,

/ = 1Д, если в момент времени / ЦМ находится в каком-лцбо состоянии .г, подмножества Аг Состояния процесса {У,}, будем обозначать символами у{, уг,

Теорема 4.3. Последовательность состояний процесса {У,} представляется последовательностью значений функции = gл/ - суперпозиции двух полиномов g(q)'н /(х,д) над полем СР{2"), где п — наименьшее целое, удовлетворяющее условию 2" >1,1 < т2-т+1, т — количество элементов в множестве

Теорема 4.3 устанавливает, что МФ вида {}',} можно задать системой ПМУ =(С/,Ч/1 = g(q) • У(х,д),я0), где I/ - ДСВ, как в (23), Ч', - суперпозиция соответствующих полиномов, ж0 - начальное распределение состояний. Систему ПМ) будем называть полиномиальной моделью МФ вида {Г,}.'Генератор процесса {У,}, основанный па /7А/У, представим структурной схемой на рис. 2:

и ч

и Г х = и /0><7) = <7

Рис. 2. Структурная схема генератора процесса {У,} над полем ОР(2") Введем в рассмотрение вероятностную функцию ц(х!л), задаваемую стохастической матрицей размера т х г/, принимающую в состоянии значения .....с вероятностями Рц<Р,2'--'Рш■ Пусть стохастическая матрица, задающая //(г/.у), при имеющемся выражении (23), раскладывается на /[ < тс! -т +1 простых матриц.

Теорема 4.4. Последовательность состояний процесса {2,}, заданного системой (23) и функцией представляется последовательностью значе-

ний функции = /2 • /[ — суперпозиции двух полиномов вида (7) над полем 2"), где п — наименьшее целое, удовлетворяющее условию 2" > тах(/,/]).

Теорема 4.4 устанавливает, что МФ вида {2,} можно задать системой ,ПМ2 =(Ууи',у¥2 = /2(х',д)»/{{х,д),я0), где V - СДВ, принимающая множество значений и\,и'г,...,и)х. Генератор процесса {2,}, основанный наПМ2, представим структурной схемой на рис. 3:

Рис. 3. Структурная схема генератора процесса {2,} над полем GF(2")■

ПМ сложной (а-связной) ЦМ определим следующим образом. Пусть задан алфавит 2, | Z [= . Тогда а-связная (а > 1) ЦМ задается стохастической матрицей Ра с множеством состояний Z", | 2а |= с1а. Состояниями являются все. возможные упорядоченные последовательности — цепочки длины а, г = \,с1а , составленные в алфавите 2. Для каждого состояния определены р^ (г /е,), где

/ = 1 ,с!а, j = l,d, г¡^2. Если часть распределений p¡j(Zj/ej) для соответствующих е1 совпадают, то на множестве 2а в соответствии с различающимися распределениями зададим разбиение вида (25) на к попарно неэквивалентных подмножеств состояний; и вектор щ — начальное распределение букв алфавита У, \ ТГ\=к. '

Теорема 4.5. Последовательность значений а-связной ЦМ представляется последовательностью значений функции Чз = /г • £• /1 — суперпозиции

полиномов /! (х,д) и /2 (х ,д) вида (7) и %(д) вида (6) над полем 2"), где п —

наименьшее натуральное число, удовлетворяющее условию 2" > тзх{И,11,с1с'),

к^И<сР\ 11£Ыа-к +1.

Начальное состояние а-связной ЦМ определяется начальным значением переменной полинома g(q) по вектору я0. ПМ а-связной ЦМ над полем Галуа будем называть систему ПМ, =((/',% = /¡(х'.д')*g(q).• Мх,д),яа), У,?' еС^(2"). Генератор а-связной ЦМ* основанный на ПМ3, представим структурной схемой на рис. 4. Показано, что на ПМ3 можно моделировать более широкий, чем а-связные ЦМ, класс конечноавтоматных случайных последовательностей и, как

частный случай, класс случайных последовательностей типа «марковского ис-

Рис. 4. Структурная схема генератора а-связной ЦМ над полем СР(2")

Далее исследуются процессы с последействием, моделируемых вероятностным'автоматом, на основе эйлеровых стохастических матриц и решается задача моделирования зависимых процессов из класса процессов с последействием на основе неоднородных цепей Маркова. Предложена автоматная модель, из класса вероятностных автоматов с перестраиваемой структурой, для случая, соответствующего произвольно-эйлеровым из вершины V орграфам. Построенная автоматная модель расширяет функциональные возможности автономного вероятностного автомата. Даётся полиномиальное представление генератора рассматриваемого класса последовательностей над полем ОР(2") .

Введем в рассмотрение вероятностный автомат с перестраиваемой структурой, задаваемый системой АВА(<р) = (8,Рг,Р,вм), где £ = — конечное множество состояний, Ргр — стохастическая тхт матрица переходных

вероятностей; — начальное состояние автомата (в момент времени /0); Р — некоторое преобразование над стохастической матрицей Р^, заменяющее г-ю

строку ( / = 1 ,т) матрицы на новую строку, для которой по-прежнему выполняется условие стохастичности (нормировки). Ограничим задачу построения автоматной модели частным случаем, связанным с подклассом произвольно-эйлеровых из вершины у орграфов. Обозначим стохастическую матрицу Рр для этого случая — Ррг, а соответствующую матрице Ррг последовательность - <ррг.

Теорема 4.8. Пусть задана неразложимая стохастическая матрица Ррг = (Ру)ту.т - Тогда можно указать автомат АВА(<р), такой, что последовательность <ррг его состояний образует заданную стохастическую матрицу Ррг.

АВА{(р) позволяет получать разные реализации случайных' <ррг-последовательностей фиксированной длины, отличающиеся друг от друга по-

рядком следования элементов, так как эйлерова цепь формируется по вероятно-

а,, -

стному закону, но с одинаковыми частотами p'¡, = pjj = —, i,j = l,m. Каждый

a¡

цикл произвольно-эйлерового из вершины v орграфа содержит эту вершину. Следовательно <ррг -последовательность можно представить в виде последовательности циклов с концевыми вершинами v, каждый из которых реализуем на основе полинома g(q). Разработана структурная схема генератора <ррг-последовательностей, реализованная в виде композиции полиномов g(q).

В заключительной части четвёртой главы дано обобщение результатов решения задачи представления ABA над полем GF(2") на решение задачи полиномиального моделирования ВА общего вида над полем GF(2"). Вероятностный автомат общего вида представим системой :

(V,S,Z,m(s',z/s,v)),. (26)

где V = {v|,v2,...,vA} - конечный входной алфавит, S = {S|,í2,...,j„,} - конечное множество состояний, Z = {zl,z2,...,zd} - конечный выходной алфавит, р. -функция, определяющая вероятность перехода автомата в состояние s' и выдачи буквы z при условии, что на вход автомата подана буква v, когда он находиться в состоянии s. Функция ц задается двумя системами стохастических

матриц: системой стохастических матриц {P^i'J = 1 ,h) размера тхт, определяющей вероятностный закон переходов" автомата, и системой = \,h) размера mxd, определяющей вероятностный закон последовательности выходных букв. Последовательность состояний автомата (26) является простой неоднородной цепью Маркова, а выходная последовательность - ее функцией. Определим частный случай системы (26). Вероятностным автоматом без выхода (без функции выхода) будем называть систему:

' (27)

где p(s'/s,v) вероятностная функция переходов, задаваемая системой {P(Sj_¡,i = 1,й}, a F,5-элементы, определенные в системе (26). Разработан метод

построения полиномиальной модели В А (27) над полем GF( 2"), состоящий из следующих четырёх этапов.

Этап 1. По заданной системе стохастических матриц {/>(j)í,í = принадлежащих Р(лг), образуем стохастическую матрицу P(s¿) размером h-mxm-. Матрицу представим линейной стохастической комбинацией простых

матриц:

где - простая матрица, соответствующая символу «,,;' = . Коэффициенты /э,.,! = 1,/5 образуют стохастический вектор р = {р\.....Р/5)- Размерность

15 вектора удовлетворяет условию: шах Л,- </5 < "^к, - Ит + 1, где к,,1 = т,

1£1<Нт /=1

число ненулевых элементов в г строке матрицы .

Этап 2. По разложению (28) автомат (27) представим системой

(¿7,К,5,Д(у,/?)), (29)

- (Ри Р2> - /О где и = ■ - дискретная случайная величина с множест-

и2, ... ик)

вом значений С/ = {и1,и1,...,и1.}, V,5 - те же элементы, что и в (29), Д(и,/?)-функция переходов, ставящая паре (и, /?) новое состояние , /? = (V,5) - переменная пробегающая множество Ух Б и = Лот. По разложению (28) зададим функцию А(и,Р) автомата (29) в виде автоматной таблицы размера /3 х Ът, в которой строки помечены символами и е С/, столбцы — парами (у.-т).

Этап '3. Произведем кодирование символов и eU.fi еУх$ автомата (29) элементами поля 2"), где п наименьшее натуральное 'число, удовлетворяющее условию 2" >тах(/3,Ь), где Ь = 2''|о®2А^1о82'"\ определяемое при кодировании элементов множества V х 5.

Этап 4. Выполним представление функции А(и,/3) автомата (29) полиномом /(х,д) вида (7) над полем' СР(2"), порядок которого определен на этапе 3. ' . ■

Пусть в полиноме /(дг,17) переменная х соответствует символу ме[/, а переменная д - символу р е. V х 5, тогда автомат (29) можно представить полиномиальной моделью вида (С!,/(х,д)), для простых однородных цепей Маркова.

Для представления В А (26) над полем 0^(2") определим длину /6 стохастического вектора соответствующего системе = 1,й} по разложению вида (28). Тогда справедлива следующая теорема, устанавливающее существование полиномиальной модели над полем <^(2" ) для В А (26).

Теорема 4.9. Функция /j(s',z/s,v) вероятностного автомата (26), задан. ная системами {P^Sy,i = \,h} и {-P(z),í>' = представима полиномиальной

функцией — суперпозицией *F = f\* полиномов вида ■^.a¡,x'<JJ над полем

и=0

GF(2"), п - наименьшее целое, для которого определяется условие 2" > шах(/3,16, Ь), где Ъ = 2Г'0«2 ^log2 ml

В пятой главе «Реализация и тестирование полиномиальных моделей средствами программного комплекса и САПР ПЛИС/Xilinx» разработана структурная модель умножителя в поле Галуа GF(2") в виде комбинационной схемы, которая позволяет распараллелить процесс вычисления операции умножения. Предложены структурные модели умножителей в GF(2") с одним постоянным множителем - умножители на константу. Получены теоретические оценки сложности для предложенных моделей. Определены реальные затраты при реализации структурных моделей умножителей в базисе ПЛИС путем их компьютерного моделирования с использованием САПР фирмы Xilinx. На основе сравнения реальных затрат, полученных на САПР/Xilinx, с теоретическими оценками сложности получены оценки, показывающие адекватность структурных моделей умножителей однородной структуре ПЛИС. Описываются два разработанных пакета прикладных программ, позволяющих построить программные модели генераторов МФ. В первом пакете программ реализованы модели ABA, последовательности выходных букв которых являются рассмотренными случайными процессами вида МФ. Второй программный комплекс позволяет реализовать разработанные ПМ генераторов МФ и представляет собой набор модулей, реализующих функции над элементами полей GF(T).

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

В приложении приведены таблицы индексов построенных составных полей вида GF(22 ) s GF(28) для предложенных в четвертой главе схем умножения.

~ Основные выводы и результаты диссертации

I) Разработаны теоретические основы (Теоремы 1.3, 1.5-1.6 и следствие Теоремы 1.6) вычисления полиномиальных функций от двух переменных однородными вычислительными структурами. Разработана структурная модель умножения двух произвольных элементов поля GF(2"), позволяющая при схемной реализации использовать однотипные элементы и получать однородные вычислительные структуры. На основе доказанных результатов разработана цифровая схема из однотипных .элементов с однородными связями для ум-

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

2) Разработан метод построения схем умножения в составных полях вида СР(2г ). Сформулированы "и доказаны Теорема 2.1 и следствие Теоремы 2.1, что является основой метода построения составных полей вида йР((.2*)3), изоморфных полю вида и метода вычисления коэффициентов примитивного многочлена второй степени над СР(2к), являющегося модулярным для ОР((2к)2). Разработанный метод, .позволяет сократить вычислительную сложность и повысить скорость выполнения операции умножения по сравнению с АКО и его модификацией. При сравнении с традиционным подходом уменьшено число необходимых для реализации двухвходовых элементов, при этом время задержки не увеличено.

3) Доказана возможность реализации конечного автомата в виде однородной

сети, производящей однотипные операции в (Теорема 3.1). Разрабо-

тан алгоритм, позволяющий по описанию конечного автомата строить однородную цифровую схему, выполняющую потоковые вычисления над п-мерными двоичными векторами. Разработаны методики синтеза однородных схем по описанию конечного автомата. Сформулирована и доказана Теорема 3.2, устанавливающая способ уменьшения количества ненулевых коэффициентов при высших степенях многочлена над полем СР(2"), реализующего произвольное отображение поля йР(2") в себя. На основании этого результата построен формальный метод, при помощи которого решается задача уменьшения количества элементов однородной сети, реализующей конечный автомат с памятью.

4) Разработаны теоретические основы моделирования цепей Маркова и марковских функций полиномиальными моделями в поле ОР(2"), введено понятие полиномиальной модели Марковской функции над полем СР(2"). Предложены и разработаны полиномиальные модели случайных процессов из класса марковских функций на основе суперпозиции полиномов от одной и двух переменных над полем СР(2"). Адекватность предложенных ПМ, метода их построения и моделирования на их основе различных подклассов функций ЦМ обоснованы соответствующими теоремами (Теоремы 4.1 - 4.7). Разработан метод синтеза структурных моделей генераторов марковских функций в базисе полиномов над полем" ОР(2"), который позволяет эффек-

■ тивно осуществить распараллеливание выполняемых вычислений в однород-

ных вычислительных средах. Предложена и разработана полиномиальная модель над полем GF(2n) управляемого генератора ДСВ. Предлагаемые методы и методика построения полиномиальных моделей в виде суперпозиции полиномов обобщены до класса конечноавтоматных случайных последовательностей. Этот класс включает, как частные случаи, простые и сложные однородные ЦМ. Разработана полиномиальная модель для моделирования в поле GF(2") случайных дискретных процессов с последействием, обобщающая полиномиальную модель АВА (Теорема 4.8). Выполнено обобщение результатов решения задачи полиномиального представления простых однородных цепей Маркова на более широкий класс дискретных случайных процессов, порождаемых ВА — неоднородные цепи и их функции. Разработан метод представления вероятностных автоматов общего вида в базисе полиномиальных функций над полем GF(2") (Теорема 4.9).

5) Разработана структурная модель умножителя в поле Галуа GF(2") в виде комбинационной схемы, которая позволяет распараллелить процесс вычисления операции умножения. Предложены структурные модели умножителей в GF(2") с одним постоянным множителем - умножители на константу. Получены теоретические оценки сложности для предложенных моделей. Определены реальные затраты при реализации структурных моделей умножителей в базисе ПЛИС путем их компьютерного моделирования с использованием САПР фирмы Xilinx. На основе сравнения реальных затрат, полученных на САПР/Xilirix, с теоретическими оценками сложности получень! оценки, показывающие- адекватность структурных моделей умножителей однородной структуре ПЛИС. Разработан комплекс прикладных программ, позволяющий строить программные модели рассматриваемых генераторов МФ.

Список публикаций по теме диссертации Статьи в периодических изданиях, включенных в перечень ВАК

1. Нурутдинов Ш.Р. Применение теории линейных последователыюстных машин в системах диагностирования/ Латыпов Р.Х., Нурутдинов Ш.Р., Столов Е.Л., Фараджев Р.Г.//АиТ. 1988. №8. С.3-27.

2. Нурутдинов Ш.Р. Реализация автомата асинхронной сетью /Нурутдинов Ш.Р., Столов Е.Л. // Кибернетика, Киев, 1988, №6. С.108-109.

3. Нурутдинов Ш.Р. A.c. 1397920. Устройство для встроенного контроля . цифровых блоков./ Баранов А.И., Комаров Ю.С., Латыпов Р.Х., Нурутдинов Ш.Р., Столов Е.Л. //Б.И. №19. 1988,- 4с.

4. Нурутдинов Ш.Р. A.c. 1302285. Устройство для контроля цифровых блоков./Латыпов Р.Х., Мансуров P.M., Нурутдинов Ш.Р., Столов E.JI. ■ //Б.И. 1987. №13.-4с.

5. Нурутдинов Ш.Р. A.c. 1619276 СССР. Устройство, для оперативного контроля цифровых блоков/ Латыпов Р.Х., Нурутдинов Ш.Р., Столов Е.Л. // Б.И.№ 1, 1990. - Зс.

6. Нурутдинов Ш.Р. A.c. 1672438. Устройство для умножения двух элементов конечного поля GF(2")/ Нурутдинов Ш.Р., Столов Е.Л. // Б.И. №31, 1991,- 4с.

7. Нурутдинов Ш.Р. A.c. 1714604. Устройство для контроля двоичных последовательностей/ Латыпов Р.Х., Нурутдинов Ш.Р., Столов Е.Л. // Б.И. №7. 1991.-3 с.

8. Нурутдинов Ш.Р. A.c. 16953Ö4. Устройство для контроля логических блоков/ Латыпов Р.Х., Нурутдинов Ш.Р., Столов Е.Л. // Б.И. №44. 1991.-Зс. ___

9. Ш.Р.Нурутдинов Перестраиваемые схемы в системах встроенного тестирования /Ш.Р.Нурутдинов, Е.Л.Столов //АиТ. 1995, N11. С.179-183. ^

10.Нурутдинов Ш.Р. Аппаратная реализация умножения элементов поля

Галуа на программируемых микросхемах архитектуры FPGA /Захаров «

B.М., Нурутдинов Ш.Р., Шалагин C.B.//Вестник Казан, гос. техн. ун-та ' им. А.Н! Туполева.-2001.-№1.-С.36-47.

11 .Нурутдинов Ш.Р. Полиномиальное представление цепей Маркова над

полем Галуа /Захаров В.М., Нурутдинов Ш.Р., Шалагин C.B.// Вестник ' Казан, гос. техн. ун-та им. А.Н. Туполева.- 2001.- №3,- С.27-31.

12.Нурутдинов Ш.Р. Полиномиальное представление конечноавтоматных случайных последовательностей над полем Галуа /Захаров В.М., Нурут-динов Ш.Р., Соколов С.Ю., Шалагин C.B.// Вестник Казан, гос. техн. унта им. А.Н. Туполева,- 2003,- № 2.-С.24-28.

13.Нурутдинов Ш.Р. Моделирование цепей Маркова в полях Галуа //Дискретная математика.-М: АкадемИздатЦентр, Наука, РАН, том 16, "J -выпуск 2, 2004. С.136-147.

Монографии

14.Нурутдинов Ш.Р. "Основы теории полиномиальных моделей автоматных преобразований над полем Галуа".-Казань: Изд-во Казанский Государственный Университет им. В.И.Ульянова-Ленина, 2005 - 160 с.

Публикации в других научных изданиях

15. Нурутдинов Ш.Р. Сигнатурный анализатор с нелинейными обратными связями// Некоторые проблемы вычислительной математики, математической физики'и программного обеспечения.-М.: Изд-во МГУ, 1988:

C.82-83.

16. Нурутдинов Ш.Р. Реализация комбинационной схемы при помощи многочлена от нескольких переменных над конечным полем: VIII Всесоюзная конференция по теоретической кибернетике. 1988 г.: тез. докл.- Горький:.Изд-во ун-та. - Часть 2. - С.61-62.

17.Нурутдинов Ш.Р. Контролепригодный умножитель в поле GF(2") : "Повышение качества и надежности продукции, программного обеспечения ЭВМ и технических средств обучения": всесоюзная науч.-техн. конф., 1989 г.:-тез. докл. - Куйбышев: изд-во политех, ин-та. 1989. --С.181-182.

18. Нурутдинов Ш.Р. Обеспечение отказоустойчивости сетевой модели автомата /Нурутдинов Ш.Р.// Исследования по прикладной математике: сб. ст. — Казань, Вып.№16.: Изд-.во Казан, гос. ун-та, 1989. - С.138-144.

19.Нурутдинов Ш.Р. Контроль несанкционированной модификации больших файлов данных/ Минниханов Р.Н., Нурутдинов Ш.Р.,Столов ЕЛ Л Международная конференция «Информатизация правоохранительных систем» 1997 г.: тез. докл. - Москва: Изд-во Академия управления МВД Россия, 1997.-Часть 2.-С.68-69.

20.Нурутдинов Ш.Р. Контроль несанкционированной модификации больших файлов данных./ Минниханов Р.Н., Нурутдинов Ш.Р.,Столов ЕЛ.// Материалы международной конференции «Безопасность информации» - Москва: Изд-во Академия управления МВД Россия, 1997. - Часть 1. - С.230-231.

21.Нурутдинов Ш.Р. Вычисление произведения элементов поля Галуа/Нурутдинов Ш.Р., Шалагин C.B. // Труды Третьего всероссийского семинара "Теория сеточных методов для нелинейных краевых задач".- Казань: Изд-во Казан, мат. Общ.- 2000 Г.-С.94-96.

22.Нурутдинов Ш.Р. Синтез автономных вероятностных автоматов на основе полей Галуа/ Захаров В.М.,- Нурутдинов Ш.Р., Шалагин C.B. // В сб. "Исследования по информатике". Вып.2. Научно-практическое изда--ние Ин-т проблем информатики АН РТ - Казань: Отечество, 2000 г.-С.107-116.

23. Нурутдинов Ш.Р. Минимизация количества элементов однородной вычислительной структуры/ Нурутдинов Ш.Р., Шалагин C.B.//В сб. "Исследования по информатике". Вып.2. Научно-практическое издание Ин-т проблем информатики АН РТ - Казань: Отечество, 2000г.- С.117-124.

24.Нурутдинов Ш.Р..Построение модели умножителя в полях Галуа/ За-г харов В.М., Нурутдинов Ш.Р., Шалагин C.B. //Материалы VII Международного семинара "Дискретная математика и ее приложения." (29 янва-ря-2 февраля 2001г.) Ч.1.- М:Изд-во центра прикл. исслед. при Мех-Мат фак-те МГУ, 2001.- С.62-65.

25.Нурутдинов Ш.Р. Оценка адекватности вычислителей произведения элементов поля Галуа на программируемых микросхемах/Нурутдинов Ш.Р., Шалагин C.B.//Труды республ. научн.-практ. конф, "Интеллектуальные системы и информационные технологии".- Казань: "Отечество", 2001г.-С.82-84.

26.Nurutdinov Sh.R. Markov Chains in Galois Fields/ Nurutdinov Sh.R. // International conference OFEA'2001 OPTIMIZATION of FINITE ELEMENT APPROXIMATIONS \& SPLINES AND WAVELETS. S.-PETERBURG;-UNIVERSITY, pp.47-49.

27. Нурутдинов Ш.Р. Умножение в поле Галуа GF(16) в базисе поля GF(4)i Нурутдинов Ш.Р. // "Современные проблемы математического моделирования": IX Всероссийская школа-семинар, 17-21 сентября 2001 г.: сб. трудов. - Ростов-на Дону: Изд-во РГУ/2001 г. - С.272-275.

28. Нурутдинов Ш.Р. Реализация операции умножения в поле Галуа GF(16) в базисе поля GF(4)I Нурутдинов Ш.Р. // "Исследования по прикладной математике": сб. ст. - Казань: Изд-во Казан, мат. общ., Выпуск 23.2001 г.- С.111-117.

29.Нурутдинов Ш.Р. Модели марковских функций над полем Галуа/ Захаров В.М., Нурутдинов Ш.Р., Соколов С.Ю., Шалагин C.B. // Материалы Четвертого Всероссийского сёминара "Сеточные методы для краевых задач и приложения". - Казань: Изд-во Казанского математического общества, 2002.-G.61-64.

30. Нурутдинов Ш.Р. Синтез автоматных моделей цепей Маркова и их функций в конечных полях / Нурутдинов Ш.Р., Соколов С.Ю., Шалагин C.B. // Труды V Международной научно-технической конференции "Новые информационные технологии и системы". - Пенза: Изд-во ПГУ, 2002.-С.211-213.

31. Нурутдинов Ш.Р. Автоматные модели марковских функций над полем Галуа/ Нурутдинов Ш.Р., Соколов С.Ю. // Тез. докл. XII Международной конференции по вычислительной механике и современным прикладным программным системам.(ВМСППС'2003), 30 июня-5 июля 2003г., Владимир - М.: Изд-во МАИ, 2003.Т2.-С.504-505.

32.Нурутдинов Ш.Р. Полиномиальное представление изменения состояния квантового бита/Захаров В.М., Нурутдинов Ш.Р., Шалагин C.B.// Труды первой Всероссийской научной конференции "Методы и средства обработки информации"-М.: Изд-ский отдел ф-та ВМК МГУ. 1-3 октября, 2003г.

33.Нурутдинов Ш.Р. Полиномиальное представление автоматных моделей марковских функций над полем Галуа / Захаров В.М., Нурутдинов Ш.Р., Соколов С.Ю., Шалагин C.B. // Сб. ст. "Исследования по информатике".

Вып. 5. Научно-практическое издание. Институт проблем информатики АН РТ. - Казань: Отечество, 2003.-С.45-56.

34.Нурутдинов Ш.Р. Полиномиальные структурные модели генераторов цепей Маркова в базисе ПЛИС класса FPGA /Захаров В.М., Нурутдинов . Ш.Р., Шалагин C.B. // Сб. тр. "Исследования по информатике". Вып. 6. Науч.-практ. издание. Институт проблем информатики АН РТ. - Казань: Отечество, 2003.-С. 81 -95.

35.Нурутдинов Ш.Р. Модели конечноавтоматных случайных последовательностей над полем GF(2")I Захаров В.М., Нурутдинов Ш.Р., Соколов С.Ю., Шалагин C.B. // Материалы VIII Международного семинара "Дискретная математика и ее приложения" (2-6 февраля 2004г.)- М:Изд-во центра прикл. исслед. при Мех-Мат фак-те МГУ, 2004.- С.69-72.

36. Нурутдинов Ш.Р. Операция умножения в расширениях полей Галуа/ Нурутдинов Ш.Р. // Материалы VIII Международного семинара "Дискретная математика и ее приложения" (2-6 февраля 2004г.) Ч.1.- М:Изд-во центра прикл. исслед. при Мех-Мат фак-те МГУ, 2004.-С.145-148.

37. Нурутдинов Ш.Р. Моделирование конечных детерминированных автоматов в полях Галуа/ Нурутдинов Ш.Р. // Труды V Всероссийского семинара "Сеточные методы для краевых задач и приложения"( 17-21 сентября 2004г.) - Казань: Отечество, 2004 г.- С.61-64.

38.Нурутдинов Ш.Р. Полиномиальные модели вероятностных автоматов и функций цепей Маркова над полем GF(T)I Захаров В.М., Нурутдинов Ш.Р. //В кн. "Эволюционное моделирование". Труды Казанского городского семинара "Методы моделирования". Вып.2. - Казань: Изд-во ФЭН(Наука), 2004.С.51-73.

39.Нурутдинов Ш.Р. Полиномиальное моделирование конечных детермини-. рованных автоматов в полях Галуа/ Нурутдинов Ш.Р. // Материалы международной научной конференции "Актуальные проблемы математики и механики". Труды математического центра имени' Н.И.Лобачевского. Т.25 .-Казань: Изд-во Казанского математического общества. Казань, 26 сентября - 1 октября 2004г. - С.205-206.

40. Нурутдинов Ш.Р. Генерация псевдослучайных последовательностей с распределением, отличным от равномерного/ Нурутдинов Ш.Р. //Труды VI Международной конференции "Дискретные модели в теории управляющих систем ", Москва, (7-11 декабря 2004г.) - М:Издтельский отдел Факультета ВМиК МГУ им. М.В.Ломоносова, 2004,- С.252-254,-

Отпечатано с готового оригинал-макета в типографии Издательского центра Казанского государственного университета им. В.И.Ульянова-Ленина

Тираж 150 экз. Заказ 11/34

420008, г. Казань, ул. Университетская, 17 тел. 292-65-60. 231-53-59

ОСНОВНЫЕ УСЛОВНЫЕ ОБОЗНАЧЕНИЯ '

СОКРАЩЕНИЯ, ПРИНЯТЫЕ В ТЕКСТЕ.

ВВЕДЕНИЕ.

ГЛАВА 1. Вычислительные модели преобразований над полем GF(2n)

1.1. Определения теории полей Галуа

1.2 Связь между векторным и матричным представлением элементов поля GF(2n).

1.3 Структурная модель, реализующая операцию умножения элементов поля GF(2n).

1.4 Представление функций в GF(2n) многочленами от нескольких переменных.

1.4.1 Реализация многочленом от одной переменной.

1.4.2. Реализация функции от s переменных в GF(2n) многочленом от s переменных.

1.5. Структурные реализации полиномиальной функции и оценки их сложности.

1.5.1. Параллельная структура.

1.5.2. Систолическая векторная структура полинома /(х, q).

1.5.3. Систолическая структура полинома /(х, q).

1.5.4. Итеративная структура многочлена L{u).

ГЛАВА 2. Модели схем умножения в расширениях поля GF(2") •

2.1. Применение алгоритма Карацубы-Офмана для построения схемы умножения в составных полях вида GF((2k )4)

2.2. Модификация алгоритма Карацубы-Офмана для построения схемы умножения в составных полях вида GF((2k )4)

2.3. Алгоритм построения составного поля вида GF((2k)2), изоморфного полю вида GF(2 )

2.4. Построение схемы умножения в составном поле вида GF((22)2).

2.5. Построение схемы умножения в составном поле вида GF(((22)2)2).

ГЛАВА 3. Полиномиальные модели детерминированных автоматных преобразований над полем GF(2n)

3.1. Моделирование конечного автомата однородной сетью элементарных автоматов в поле GF(2n).

3.2. Моделирование в классе комбинационных схем.

3.2.1. Полиномиальная модель на основе многочлена от одной переменной над полем GF(2").

3.2.2. Полиномиальная модель на основе многочлена от двух переменных над полем GF(2n).

3.3. Полиномиальная модель автомата с памятью.

3.4. Синтез типовых элементов однородной вычислительной структуры.

3.4.1. Типовой элемент последовательной структуры.

3.4.2. Типовой элемент параллельной структуры.

3.4.3. Методика синтеза однородных автоматных схем.

3.5. Минимизация структуры полиномиальной модели

ГЛАВА 4. Полиномиальные модели вероятностных автоматов и функций конечных цепей Маркова над полем GF(2n)

4.1. Определения базовых вероятностных автоматных моделей.

4.2. Синтез автоматной марковской модели над полем GF(2").

4.3. Синтез генераторов марковских функций над полем GF(2").

4.3.1. Полиномиальная модель генератора процесса {Y,} над полем GF(2n).

4.3.2. Полиномиальная модель генератора процесса {ZJ над полем GF(2"). 119 4.4. Полиномиальная модель марковской функции вида а-связной цепи Маркова. 123 4.5 Синтез конечноавтоматных случайных последовательностей над полем GF{2n).

4.5.1. Определение вероятностной автоматной модели и постановка задачи

4.5.2. Полиномиальное представление конечноавтоматной модели надполем GF(2n).

4.6. Синтез генератора дискретной случайной величины. надполем GF(2n).

4.7 Автоматное моделирование случайных процессов с последействием на основе эйлеровых стохастических матриц.

4.7.1 Автоматная модель.

4.7.2 Структурная схема автоматной модели.

4.8 Реализация ^^-последовательности в полях GF(2").

4.9 Полиномиальные модели вероятностных автоматов общего вида над полем GF(2").

ГЛАВА 5. Реализация и тестирование полиномиальных моделей средствами программного комплекса и САПР ПЛИС/FPGA

5.1. Программируемые логические интегральные схемы

5.2. Представление и анализ структурных моделей операции умножения в поле GF(2")

5.2.1. Определение базовых математических моделей умножителя.

5.2.2. Структурные модели умножителей и их оценки сложности.

5.3. Оценки сложности структур умножителей над полем GF(2n) в базисе программируемых матрицах логических элементов.

5.3.1. Оценки сложности моделей в базисе ПЛИС.

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

5.4. Пакет программ, реализующий автоматные модели генераторов марковских функций.

5.5. Пакет программ, реализующий полиномиальные модели генераторов марковских функций над полем GF(2n).

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

Вероятностные автоматы имеют глубокую взаимосвязь с цепями Маркова (ЦМ) [3]. Частный случай В А - автономный вероятностный автомат (ABA) без выхода является автоматной моделью генератора однородной цепи Маркова. Процессы, порождаемые ABA с выходом рассматриваются как функции конечных однородных цепей Маркова (марковские функции (МФ))[1-3]. Последовательность состояний ВА общего вида является неоднородной цепью Маркова [1].В свою очередь, матричная теория цепей Маркова является аналитическим аппаратом решения задач синтеза и анализа вероятностных автоматов [1-3].

Марковские последовательности и их функции широко используются для построения вероятностных моделей в таких областях как статистическое моделирование [4-7], распознавание автоматов [11, 25-26], передача и защита информации [23], диагностика и анализ цифровых устройств [2728] и др. Применение моделей цепей Маркова (ЦМ) в качестве базовых при построении вероятностных моделей автоматного типа, обуславливает интерес ученых к теории моделирования марковских последовательностей, функций конечных ЦМ и построению автоматных моделей генераторов ЦМ.

Использование моделей ЦМ дает возможность получить простое и адекватное описание широкого класса систем. Важностью прикладного значения объясняется большое число публикаций по теории моделирования марковских последовательностей и их функций и построению моделей генераторов ЦМ [1-3, 27-29, 31-46]. Известен ряд работ по моделированию марковских последовательностей, основанных на автоматном представлении процессов этого класса [1-7, 27-29, 33-42]. При автоматном моделировании ЦМ конечная однородная цепь Маркова обычно представляется в виде конечного детерминированного автомата со случайным входом [38-39]. В работах [1-4, 7, 27, 32, 34, 36, 46] решены вопросы перехода от описания ЦМ в виде стохастической матрицы к описанию в виде стохастической линейной комбинации булевых стохастических матриц, определены условия автоматного преобразования случайных дискретных величин, предложены принципы построения управляемых генераторов случайных кодов, показано, что МФ можно рассматривать как процессы, порождаемые вероятностными автоматами [2-3,ОД}шм из перспективных подходов построения автоматных моделей ЦМ, предложенных в последние годы, представляется подход, использующий теорию конечных полей. Этот подход позволяет синтезировать структурные модели генераторов конечных ЦМ, состоящие из однородных блоков, с векторной обработкой данных. Для реализации полученных моделей могут быть использованы технологии производства интегральных схем, например программируемые логические интегральные- схемы (ПЛИС). Использование ПЛИС дает возможность синтезировать устройства с перестраиваемой структурой, что позволяет оперативно менять функциональные возможности вероятностных моделей и приводит к сокращению аппаратных затрат, а следовательно и стоимости разрабатываемого устройства.

В работах [4-7] показана перспективность нового подхода моделирования цепей Маркова и их функций, основанного на полиномиальной алгебре в конечном поле типа GF(2n). Достоинством вычислений в поле GF(2n) является то, что они обладают функциональной полнотой и допускают параллельную реализацию. Аппарат конечных полей позволяет строить автоматные схемы в виде однородной сети элементарных автоматов, выполняющих операции сложения и умножения в поле GF(2n) [8]. Эти и другие особенности конечного поля определили широкое использование аппарата теории конечных полей в области обработки процессов информации: в теории кодирования [8-24]; в цифровой обработке сигналов [25]; в анализе динамических стохастических систем [25-26], в задачах синтеза генераторов псевдослучайных последовательностей [28-29] и др.

Многие современные практические задачи предъявляют высокие требования к скорости генерирования формируемых последовательностей. Увеличение быстродействия может быть достигнуто с помощью распараллеливания проводимых вычислений [48-49].

Идея синтеза дискретных вероятностных моделей автоматного типа в однородных вычислительных средах получила развитие в работах [3, 32, 50-51], а использования арифметики конечных полей [9] для синтеза детерминированных цифровых устройств в однородных структурах в [44, 5260]. Известны также решения задачи построения генераторов равномерно распределенных случайных и псевдослучайных чисел в поле GF{2") [11, 28,31,61-65].

Большое число публикаций посвящено решению задачи разработки архитектуры схемы умножения элементов поля GF(2") для реализации в однородных вычислительных средах [67], а также решению задачи уменьшения вычислительной сложности схем умножения [55, 68-77], так как вычислительная сложность, при использовании технологии производства интегральных схем, может служить оценкой необходимой площади кристалла [77]. Использование идеи расширения модели играет важную роль в теории построения вычислительных структур. Применение расширений моделей и переход к более удобному базису возможно для умножения матриц [30, 66], что позволяет уменьшить вычислительную сложность операции умножения в полях Галуа (матричное представление элементов поля).

Известно решение задачи построения автоматных моделей генераторов ЦМ в базисе полиномиальных функций над полем Галуа [58-59]: предложены полиномиальная модель и структурная схема генератора простых однородных ЦМ над GF(2й); предложены альтернативные (по критериям сложности и быстродействия) структурные схемы - параллельного, систолического векторного, систолического и последовательностного типов -для реализации генераторов ЦМ в базисе полиномиальных функций; показана адекватность структуры модели генератора ЦМ над полем Галуа, состоящей из однородных блоков, структуре ПЛИС класса FPGA (Field Programmable Gate Array) [80-82]; показано, что аппарат полей GF{2") является эффективным инструментом для синтеза генераторов ЦМ в виде однородных структур.

Вероятностный автомат является обобщением конечного детерминированного автомата (КДА). В связи с этим возникает необходимость глубокого исследования вопросов представления КДА полиномами над полем GF(2n). По этому направлению важное практическое значение представляет задача отображения полиномиальных моделей КДА в однородные вычислительные среды.

В этой связи представляется актуальным выполнение настоящего исследования, основанного на новом подходе моделирования широкого класса дискретных случайных процессов с дискретным временем в поле GF(2n). Развиваемые методы включают предложенные понятия полиномиальных моделей в поле GF(2n) дискретной случайной величины (ДСВ), простых и сложных цепей Маркова и марковских функций и доказательство соответствующих теорем, устанавливающих взаимосвязь стохастических матриц и полиномиальных функций над GF(2n) и обосновывающих алгоритмы моделирования рассматриваемых процессов.

Целью диссертационной работы является создание теоретических основ, алгоритмов и методик представления детерминированных и вероятностных автоматных моделей полиномиальными функциями над полем GF(2n).

В соответствии с этой целью, исследования проводились в следующих направлениях.

1. Создание теоретических основ для разработки моделей эффективного умножителя в поле GF(2n), как расширение поля GF(2), эффективного умножителя в поле GF(22k), как расширение поля GF(2K).

2. Разработка метода представления КДА полиномиальными моделями над полем GF(2n), повышающих эффективность их реализации в однородных вычислительных структурах.

3. Создание теоретических основ для моделирования и преобразования дискретных случайных процессов с дискретным временем из класса МФ, основанного на полиномиальной алгебре в поле GF(2n), моделирования в поле GF(2n) случайных последовательностей с последействием, представления структурных моделей генераторов МФ и вероятностных автоматов в базисе полиномиальных функций.

По первому направлению решались следующие задачи.

1. Разработка эффективного умножителя в поле GF(2"), как расширения поля GF(2).

2. Разработка способа построения поля вида GF((2k)2), изоморфного полю вида GF(22k).

3. Разработка способа умножения в составных полях Галуа, позволяющего сократить вычислительную сложность.

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

2. Исследование возможности и разработка алгоритма представления конечного автомата однородной сетью над GF(2n) и оценка сложности такого представления.

3. Разработка метода проектирования однородных схем по описанию конечного автомата.

4. Разработка алгоритма минимизации количества элементов однородной вычислительной сети над GF(2n), реализующей конечный автомат с памятью.

По третьему направлению решались следующие задачи.

1. Исследование задач представления стохастических матриц и моделирования дискретных случайных величин, и марковских функций средствами полиномиальных функций в поле GF(2n).

2. Разработка структурных моделей автономных вероятностных автоматов (ABA), генераторов ДСВ, МФ и методики их построения в базисе полиномиальных функций над полем GF(2n).

3. Разработка автоматной модели из класса вероятностных автоматов с перестраиваемой структурой и метода моделирования на её основе случайных дискретных процессов с последействием в поле GF(2n).

4. Разработка метода представления неоднородных ИМ и их функций в поле GF(2").

Методы исследований. Для решения поставленных задач использованы методы теории вероятностей, теории вероятностных автоматов, теории графов, теории чисел, аппарат конечных полей, линейной и полиномиальной алгебры и дискретной математики.

Исследования поддержаны грантом Российского фонда фундаментальных исследований № 99-01-00163 «Энтропийно-сложностные свойства дискретных вычислительных моделей»; грантом Российского фонда фундаментальных исследований № 03-01-00769 «Сложностные свойства классических и квантовых вычислений»; программой «Университеты России», проект № 015-04-01-52 «Синтез и сложность детерминированных и вероятностных дискретных вычислительных моделей».

Научная новизна работы.

1. Доказана теорема и разработаны: метод построения составных полей GF((2k)2), изоморфных полю GF(22k), методика построения схем ум

2' ножения в составном поле вида GF(2 ), позволяющие сократить вычислительную сложность и повысить скорость выполнения операции умножения - базовой операции, необходимой для реализации схем генераторов МФ. Разработана методика построения составных полей для предлагаемых схем умножения.

2. Доказана теорема, обосновывающая возможность представления произвольно-заданного детерминированного отображения в поле GF(2n) в виде многочлена от s переменных, а также доказана теорема и разработан метод, с помощью которого можно вычислить коэффициенты такого многочлена. Доказана теорема и разработан алгоритм уменьшения количества ненулевых коэффициентов при высших степенях полиномиальной функции над полем GF(2n). Разработан алгоритм представления КДА однородной вычислительной сетью.

3. Введено понятие полиномиальных моделей марковских функций над GF(2n). Предложены полиномиальные модели случайных процессов вида МФ над полем GF(2") из класса, порождаемого ABA с заданными ограничениями на функции перехода и выхода, в частности модели сложных ЦМ, марковского источника и конечноавтоматных случайных последовательностей. Модели МФ представлены в виде суперпозиций полиномиальных функций от одной и двух переменных над полем GF(2n).

4. Разработаны метод и алгоритм синтеза генераторов МФ в виде суперпозиции полиномиальных функций над полем Галуа. Доказаны теоремы, обосновывающие метод.

5. Разработана полиномиальная модель над полем GF(2n) генератора дискретной случайной величины (ДСВ).

6. Решена задача автоматного Моделирования процессов с последействием, как расширение модели ABA. Предложен метод моделирования над полем GF(2n) подкласса случайных последовательностей на основе ABA с динамически перестраиваемой структурой.

7. Разработан метод моделирования неоднородных цепей Маркова и вероятностных автоматов на основе полиномиальной алгебры в поле GF(2n).

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

2' жения в составных полях вида GF(2 ) позволяет сократить необходимую для реализации умножения вычислительную сложность. Спроектированные по предлагаемой методике схемы умножения могут быть использованы в качестве базовых блоков в широком классе устройств, применяющих алгебру полей Галуа. Построены структурные схемы типовых элементов синтезируемых параллельных и последовательных однородных цифровых схем. Разработан алгоритм, позволяющий по описанию конечного автомата синтезировать однородную (параллельную или последовательную) цифровую схему. Предложенные полиномиальные модели генераторов ЦМ и МФ позволяют использовать аппарат полей Галуа при моделировании рассматриваемых случайных процессов, что дает возможность представить их в виде алгебраических выражений, допускающих параллельную реализацию. Предложенные структурные схемы генераторов ЦМ и МФ над полем GF(2n) дают возможность их непосредственного использования при проектировании специализированных автоматных моделей. Предложены генераторы тестовых последовательностей, новизна которых защищена 6-ю авторскими свидетельствами. Полученные оценки аппаратных затрат, представленные описания алгоритмов и программ дают разработчикам возможность их непосредственного использования при проектировании специализированных устройств по современной технологии программируемых логических интегральных схем (ПЛИС). Разработанный метод моделирования МФ полиномиальными функциями над полем GF(2n) дает метод решения задачи управления вероятностными характеристиками МФ. На базе полученных теоретических результатов разработаны новые технические решения, защищенные авторскими свидетельствами.

Результаты использованы в НИР за 2001-2005гг. по гранту РФФИ № 99-01-00163 «Энтропийно-сложностные свойства дискретных вычислительных моделей», по гранту РФФИ № 03-01-00769 «Сложностные свойства классических и квантовых вычислений», по проекту № 015-04-01-52 «Синтез и сложность детерминированных и вероятностных дискретных вычислительных моделей» программы «Университеты России», в ОАО «КНИАТ» (г. Казань), в Центре новых информационных технологий Республики Татарстан (г. Казань), в ГИБДД МВД Республики Татарстан (г. Казань) и в учебных процессах кафедры прикладной математики и кафедры теоретической кибернетики Казанского государственного университета и кафедры КСИБ Казанского технического университета (КАИ) им. А.Н.Туполева.

На базе полученных теоретических результатов разработаны новые технические устройства, защищенные авторскими свидетельствами.

Апробация работы. Основные результаты работы докладывались и обсуждались на Итоговых научно-технических конференциях Казанского государственного университета (Казань, 1988-2005rr.);VIII Всесоюзной конференции по теоретической кибернетике (Горький, 1988г.), Всесоюзной научно-технической конференции "Повышение качества и надежности продукции, программного обеспечения ЭВМ и технических средств обучения" (Куйбышев, 1989г.), Международная конференция «Информатизация правоохранительных систем»(Москва, 1997г.),Международная конференция «Безопасность информации»(Москва, 1997г.), Всеросс. научно-метод. Конференция "Интеграция образования, науки и производства -главный фактор повышения эффективности инженерного образования" (Казань, 2000г.), научно-практической конференции по актуальным вопросам информатики, вычислительной техники и информационной безопасности (Казань, 2001г.); Всероссийском семинаре «Сеточные методы для краевых задач и приложения» (Казань, 2000г., 2002г., 2004г., 2005г.); VII-m Международном семинаре «Дискретная математика и её приложения» (Москва, 2001г.), научно-практическая конференция по актуальным вопросам информатики, вычислительной техники и информационной безопасно-сти(Казань, 2001г.), Республ. Научн.-практ. конференция «Интеллектуальные системы и информационные технологии» (Казань, 2001г.), International conference OFEA'2001(S.-PETERBURG,2001), IX Всероссийская- школа-семинар «Современные проблемы математического моделирования» (Ростов - на Дону, 2001 г.), XIII Международной конференции «Проблемы теоретической кибернетики» (Казань, 2002г.); V Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, 2002г.); Двенадцатой Международной конференции по вычислительной механике и современным прикладным программным системам (Владимир, 2003г.); Первая Всероссийская научная конференция «Методы и средства обработки информации»(Москва, 2003г.), городском семинаре «Методы моделирования» (Казань, 2002-2005гг.), ряде семинаров кафедры Теоретической кибернетики Казанского государственного университета (Казань, 2001-2005гг.), VIII Международном семинаре «Дискретная математика и ее приложения» (Москва, 2004г.), международная научная конференция «Актуальные проблемы математики и механики» (Казань, 2004г.), VI Международная конференция «Дискретные модели в теории управляющих систем»(Москва, 2004г.), XIV Международная конференция «Проблемы теоретической кибернетики» (Пенза, 23-28 мая 2005г.), Вторая Всероссийская научная конференция «Методы и средства обработки информации (МСО'2005)» (Москва, 5-7 октября 2005г.).

На защиту выносятся следующие результаты, полученные лично: 1. Метод вычисления коэффициентов многочлена, реализующего отображение поля GF(2n) в себя.

2. Теорема, устанавливающая возможность реализации конечного автомата однородной сетью над GF(2").

3. Алгоритм и методика реализации конечного автомата однородной сетью над GF(2").

4. Теорема, устанавливающая возможность вычисления коэффициентов примитивного многочлена для построения поля вида GF((2k)2), изоморфного полю вида GF(22k).

5. Методика построения схем умножения в составных полях Галуа, позволяющая сократить вычислительную сложность и повысить скорость выполнения операции умножения.

6. Теорема, доказывающая существование алгоритма уменьшения количества ненулевых коэффициентов при высших степенях полинома над полем GF(2P), используемого при полиномиальном моделировании отображения. GF(2m) *GF(2k) -> GF(2k), р=т+к

7. Полиномиальные модели и метод представления МФ над полем GF(2n). Теоремы, устанавливающие взаимосвязь МФ и полиномиальных функций над полем GF(2").

8. Структурные модели генераторов ЦМ и МФ над полем GF(2n) и методика их построения в базисе полиномиальных функций над полем GF(2").

9. Полиномиальная модель представления генератора дискретной случайной величины полиномиальной функцией в поле GF(2").

10.Автоматная модель из класса вероятностных автоматов с перестраиваемой структурой и её полиномиальное представление над полем GF(2").

11.Комплекс прикладных программ, реализующих предложенные методики и алгоритмы.

Основное содержание диссертации опубликовано в 40 работах, включая одну монографию, статей [74-79] и тезисов докладов[80-89].

Структура и объем работы.

Диссертация состоит из введения, пяти глав, заключения, списка используемой литературы, включающего 140 наименований, и приложения. Общий объем работы составляет 222 страницы, включая 36 рисунков и 18 таблиц. В конце каждой главы имеются выводы.

Выводы по главе 5

1. Разработана структурная модель умножителя в поле GF{2") в виде комбинационной схемы, которая позволяет распараллелить процесс вычисления операции умножения. Предложены структурные модели умножителей в GF(2") с одним постоянным множителем. Получены теоретические оценки сложности для предложенных моделей.

2. Вычислены реальные затраты для реализации структурных моделей умножителей в базисе ПЛИС путем их компьютерного моделирования с использованием САПР фирмы Xilinx.

3. Выполнено сравнение реальных затрат, полученных на САПР/Xilinx, с теоретическими оценками сложности. Получены оценки, показывающие адекватность структурных моделей умножителей однородной структуре ПЛИС:

4. Разработан комплекс прикладных программ, позволяющий строить программные модели рассматриваемых генераторов МФ.

ЗАКЛЮЧЕНИЕ Основные выводы и результаты диссертационной работы

1) Разработаны теоретические основы (Теоремы 1.3, 1.5-1.6 и следствие Теоремы 1.6) вычисления полиномиальных функций от двух переменных однородными вычислительными структурами. Разработана структурная модель умножения двух произвольных элементов поля GF(2n), позволяющая при схемной реализации использовать однотипные элементы и получать однородные вычислительные структуры. На основе доказанных результатов разработана цифровая схема из однотипных элементов с однородными связями для умножения двух произвольных элементов поля GF(2n) (а.с. 167243 8). Разработан метод вычисления коэффициентов многочлена над GF(2n), моделирующего произвольное отображение поля GF(2") в себя, а также разработаны однородные вычислительные структуры, вычисляющие значения многочленов в поле GF(2n). Структуры отвечают различным ограничениям по сложности и быстродействию.

2) Разработан метод построения схем умножения в составных полях вида

2'

GF(2 ). Сформулированы и доказаны Теорема 2.1 и следствие Теоремы 2.1, что является основой метода построения составных полей вида к 2 'Т.к.

GF((2)), изоморфных полю вида GF( 2гк) и метода вычисления коэффициентов примитивного многочлена второй степени над GF(2k), являющегося модулярным для GF((2k)2). Разработанный метод, позволяет сократить вычислительную сложность и повысить скорость выполнения операции умножения по сравнению с АКО и его модификацией. При сравнении с традиционным подходом уменьшено число необходимых для реализации двухвходовых элементов, при 'этом время задержки не увеличено.

3) Доказана возможность реализации конечного автомата в виде однородной сети, производящей однотипные операции в GF(2") (Теорема 3.1). Разработан алгоритм, позволяющий по описанию конечного автомата строить однородную цифровую схему, выполняющую потоковые вычисления над л-мерными двоичными векторами. Разработаны методики синтеза однородных схем по описанию конечного автомата. Сформулирована и доказана Теорема 3.2, устанавливающая способ уменьшения количества ненулевых коэффициентов при высших степенях многочлена над полем GF(2n), реализующего произвольное отображение поля GF(2n) в себя. На основании этого результата построен формальный метод, при помощи которого решается задача уменьшения количества элементов однородной сети, реализующей конечный автомат с памятью.

4) Разработаны теоретические основы моделирования цепей Маркова и марковских функций полиномиальными моделями в поле GF(2n), введено понятие полиномиальной модели Марковской'функции над полем GF(2n). Предложены и разработаны полиномиальные модели случайных процессов из класса марковских функций на основе суперпозиции полиномов от одной и двух переменных над полем GF(2n). Адекватность предложенных ПМ, метода их построения и моделирования на их основе различных подклассов функций ЦМ обоснованы соответствующими теоремами (Теоремы 4.1 - 4.7). Разработан метод синтеза структурных моделей генераторов марковских функций в базисе полиномов над полем GF(2n), который позволяет эффективно осуществить распараллеливание выполняемых вычислений в однородных вычислительных средах. Предложена и разработана полиномиальная модель над полем GF(2n) управляемого генератора ДСВ. Предлагаемые методы и методика построения полиномиальных моделей в виде суперпозиции полиномов обобщены до класса конечноавтоматных случайных последовательностей. Этот класс включает, как частные случаи, простые и сложные однородные ЦМ. Разработана полиномиальная модель для моделирования в поле GF(2n) случайных дискретных процессов с последействием, обобщающая полиномиальную модель ABA (Теорема 4.8). Выполнено обобщение результатов решения задачи полиномиального представления простых однородных цепей Маркова на более широкий класс дискретных случайных процессов, порождаемых ВА - неоднородные цепи и их функции. Разработан метод представления вероятностных автоматов общего вида в базисе полиномиальных функций над полем GF(2n) (Теорема 4.9).

5) Разработана структурная модель умножителя в поле Галуа GF{2") в виде комбинационной схемы, которая позволяет распараллелить процесс вычисления операции умножения. Предложены структурные модели умножителей в GF(2") с одним постоянным множителем - умножители на константу. Получены теоретические оценки сложности для предложенных моделей. Определены реальные затраты при реализации структурных моделей умножителей в базисе ПЛИС путем их компьютерного моделирования с использованием САПР фирмы Xilinx. На основе сравнения реальных затрат, полученных на САПР/Xilinx, с теоретическими оценками сложности получены оценки, показывающие адекватность структурных моделей умножителей однородной структуре ПЛИС. Разработан комплекс прикладных программ, позволяющий строить программные модели рассматриваемых генераторов МФ.

1. Бухараев Р.Г., Захаров В.М. Управляемые генераторы случайных кодов. Казань: Изд-во Казан, ун-та, 1978. - 160 с.

2. Бухараев Р.Г. Автоматное преобразование вероятностных последовательностей // Вероятностные методы и кибернетика. Вып. 4. Казань: Изд-во Казан, ун-та, 1966. С. 24-33.

3. Бухараев Р.Г. Основы теории вероятностных автоматов. М.: Наука, 1985.-287 с.

4. Макаров С.В. О реализации стохастических матриц конечными автоматами // Вычислительные системы. Вып. 9. Новосибирск, 1963. С. 65-70.

5. Хамитов Г.П. Имитация случайных процессов. Иркутск: Изд-во Ир-кут. ун-та, 1983.- 184 с.

6. Четвериков В.Н., Баканович Э.А., Меньков А.В., Вычислительная техника для статистического моделирования. М.: Сов. радио, 1978. -312с.

7. Ченцов В.М. Об одном методе синтеза автономного стохастического автомата. // Кибернетика. 1968. - №3. - С. 32-35.

8. Гилл А. Линейные последовательностные машины. М.: Наука, 1974. -288 С.

9. Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т. Пер. с англ. М.: Мир, 1988.

10. Ю.Чеботарев Н.Г. Теория Галуа. Кн. 1 М.: ОНТИ НКТП СССР, 1936. -156 с.

11. Столов Е.Л. Методы компактного тестирования цифровых устройств. Казань: изд-во Казан, ун-та, 1993, - 116 с.

12. Вензин О.С., Иванов М.А. Стандарт криптографической защиты AES. Конечные поля. М.: КУДНЦ- ОБРАЗ, 2002.

13. Нечаев В.И. Элементы криптографии. Основы теории защиты информации. -М.: Высшая школа, 1999.

14. М.Крот A.M. Дискретные модели динамических систем на основе полиномиальной алгебры. Минск: Навука i тэхнжа. 1990.

15. Столов E.JI. Исчерпывающее тестирование и сигнатурный ана-лиз//АиТ .- 1992,- №6.- С. 167-172.

16. А.С. 1302285. Устройство для контроля цифровых блоков./Латы-пов Р.Х., Мансуров P.M., Нурутдинов Ш.Р., Столов Е.Л. //Б.И. 1987. №13.- 4с.

17. А.С. 1397920. Устройство для встроенного контроля цифровых блоков./Баранов А.И., Комаров Ю.С., ЛатыповР.Х., Нурутдинов Ш.Р., Столов Е.Л. //Б.И. №19. 1988.- 4с.

18. А.С. 1619276 СССР. Устройство для оперативного контроля цифровых блоков/ Латыпов Р.Х., Нурутдинов Ш.Р., Столов Е.Л. // Б.И.№ 1, 1990.-Зс.

19. А.С. 1714604. Устройство для контроля двоичных последовательностей/ Латыпов Р.Х., Нурутдинов Ш.Р., Столов Е.Л. // Б.И. №7. 1991.-Зс.

20. А.С. 1695304. Устройство для контроля логических блоков/ Латыпов Р.Х., Нурутдинов Ш.Р., Столов Е.Л. // Б.И. №44. 1991.- Зс.

21. Нурутдинов Ш.Р. Сигнатурный анализатор с нелинейными обратными связями// Некоторые проблемы вычислительной математики, математической физики и программного обеспечения.-М.: Изд-во МГУ, 1988. С.82-83.

22. Минниханов Р.Н., Нурутдинов Ш.Р., Столов E.J1. Контроль несанкционированной модификации больших файлов данных. //Тезисы докладов международной конференции «Информатизация правоохранительных систем», Москва., 1997, часть 2, С.68-69.

23. D.H. Green and I.S. Taylor. Irreducible polynomials over composite Galois fields and their applications in coding techniques. Proe. IEE, 121(9):93 5-939, September 1974.

24. A.C. 1481755 СССР, МКИ С 06 Г 7/58. Генератор случайного Марковского процесса / А.А.Гремальский, С.М.Андроник // Открытия, изобретения. 1989. - № 19. - С. 223.

25. Гремальский А.А., Андроник С.М. Генерация тестовых программ для микропроцессоров с помощью цепей Маркова // Исследование новых микропроцессорных приборов и устройств. Кишинев: Штинца, 1987.-С. 96-98.

26. Вероятностные автоматы и их приложения. Казань: Изд-во КГУ, 1986.-212 с.

27. Латыпов Р.Х., Нурутдинов Ш.Р., Столов Е.Л., Фараджев Р.Г. Применение теории линейных последовательных машин в системах диагностики. Обзор// Автоматика и телемеханика. 1988. - №8. - С. 3-27.

28. А.С. 664185 СССР. Генератор случайных чисел / Песошин В.А, Тарасов В.М., Мансуров P.M. // Открытия, изобретения. 1979. - № 19.

29. Алексеев В.Б. Сложность умножения матриц. Обзор// Кибернетический сб. М.:Мир, 1988. Вып. 25. С. 189 236.

30. Захаров В.М. Моделирование /-сложных цепей Маркова конечным детерминированным автоматом // Кн. Вероятностные автоматы и их приложения. Казань: Изд-во КГУ, 1986. - С. 155-161.

31. Гиоргадзе А.Х. Пространственно-временная декомпозиция и структурный анализ и синтез стохастических систем: Дисс. д-ра. техн. наук.-Тбилиси, 1981.-320 с.

32. Гладкий B.C. Вероятностные вычислительные модели. М.: Наука, 1973.-300 с.

33. Поспелов Д.А. Вероятностные автоматы. М.: Энергия, 1970. 88 с.

34. Лоренц А.А. Надёжность и быстродействие вероятностных автоматов. Рига: «Зинатне», 1976. - 112 с.

35. Бухараев Р. Г., Геза В.И. Специализированная ЭВМ для моделирования и обработки функций конечных однородных цепей Маркова. // Тезисы докл. Всес. симп. по вероятностным автоматам. Казань.: Изд-воКГУ, 1969.-С. 14-15.

36. Гилл А. Синтез вероятностных преобразователей. // Кибернетический сборник. М.: Мир, 1964. - №8.

37. Murray I.E. Consideration of Assumption. "IEEE Trans. Egng Manag." Vol., N 3, 1963, pp. 94-99.

38. Davis A.S. Markov chains as random input outomata. Amer. Math. Monthly, 1961, 68,3, pp. 264-267,

39. Wing O., Demetrions P. Analysis of probabilistic networks. IEEE trans, commun. techn., 1964, volume 12, N 3.

40. Booth J.L. Random input automata. Ln: JCMCL Conf., Tokyo, 1964.

41. Paz A. Introduction to probabilistic automata. N V, Academic Press., 1971.

42. James F. A review of pseudo-random number generators. // Comput. Phys. Commun., 1990, 60, N 3, pp. 329-344.

43. Столов Е.Л. Об одном классе генераторов псевдомарковских цепей // Исследования по прикладной математике. Казань: Изд-во Казан, унта, 1985. Вып. 8. С. 66-71.

44. А.С. 526909 СССР. Устройство для моделирования марковских процессов / Добрыдень В.А. // Открытия, изобретения. 1976. - № 32.

45. А.С. 1524046 СССР. Генератор случайных чисел. / Бухараев Р.Г., Захаров В.М., Баранов Г.Г., Комаров Ю.С., Кузнецов С.Е., Макаров И.И., Пермитин В.В. // Б.И. 1983. - № 43.

46. Альпин Ю.А., Захаров В.М. Моделирование случайных последовательностей автономными автоматными схемами // Вероятностные автоматы и их приложения. Казань: Изд-во Казан, ун-та, 1986. С. 22-29.

47. Гиоргадзе А.Х., Сафиуллина А.Г. О декомпозиции вероятностных автоматов // Кибернетика. 1975. - №2.

48. Гиоргадзе А.Х. Некоторые методы пространственно-временной декомпозиции вероятностных автоматов // Докл. АН СССР. 1977. - Т. 232. - №4.

49. А.С. 2802836 СССР. Устройство для умножения в конечных полях./ Харчистов Б.Ф., Финаев В.И. // БИ №15, 1981.

50. Сюрин В.Н., Иванов Н.Н., Альхимович В.В. Реализация вычислений в конечных полях. // Зарубежная радиоэлектроника. №5. - 1990.

51. Бояринов И.М. О систолических и полусистолических вычислениях в GF(2m). // Вопросы кибернетики. Разработка и использование СУПЕР-ЭВМ. М.: Наука, 1987. - С. 183-190. •

52. А.С. 1672438. Устройство для умножения двух элементов конечного поля GF(2n) / Нурутдинов Ш.Р., Столов Е.Л. // БИ, №31. 1991.

53. С. Paar. A new architecture for a parallel finite field multiplier with low complexity based on composite fields. IEEE Trans, on Computers, 45(7):856-861, July 1996.

54. H.F.Li, R.Jayakumar and C.Low. Restructuring for Fault-Tolerant Systolic Arrays // IEEE Trans, on computer, vol. 38. № 2, February 1989.

55. Jagma Sh., Aramaki T. Autonomously testable programmable logic arrays // Int. Simp, on FICS, Portland. June 1981. P. 41-43.

56. W.Daehn and J.Mucha. A hardware approach to self-testing of large programmable logic arrays // IEEE Trans. Comput., vol. C-80, N 11, pp. 829833, Nov. 1981.

57. Захаров B.M. Моделирование сложных цепей Маркова конечным детерминированным автоматом // Тезисы докладов III Всесоюзного симпозиума по вероятностным автоматам. Казань: Изд-во КГУ, 1983.-25 с.

58. А.С. 1108614 СССР. Генератор случайных последовательностей / Захаров В.М, Баранов Г.Г., Комаров Ю.С., Латыпов Р.Х., Столов Е.Л. // Б.И. 1984. - № 30.

59. А.с. 1224992 СССР. Генератор псевдослучайных чисел / Захаров В.М, Баранов Г.Г., Комаров Ю.С., Латыпов Р.Х., Столов Е.Л. // Б.И. 1986. -№14.

60. А.С. 1327099 СССР. Генератор случайных последовательностей / Захаров В.М, Баранов Г.Г. // Б.И. 1987. - № 28.

61. Кирьянов Б.Ф. Основы теории стохастических вычислительных машин и устройств. 1976. - Деп. ЦНИИГЭ приборостроения, № 524. -168с.

62. Алексеев В.Б. Некоторые вопросы сложности алгоритмов в дискретной математике и алгебре и их взаимосвязи// Сб. трудов XIII Между-нар. конф. «Проблемы теоретической кибернетики». Казань.: Изд-во КГУ, 2004. С.16 27.

63. Lows В.А., Rushforth С.К. A cellular-array multiplier for GF(2m). IEEE Trans. Comput., 1971, v.C-20, №12, pp 1573-1578.

64. T. Itoh and S. Tsujii. Structure of parallel multipliers for a class of fields GF(2k). Inform, and Сотр., 83:21-40, 1989.

65. E.D. Mastrovito. VLSI design for multiplication over finite fields GF(2m). In Lecture Notes in Computer Science 357, pages 297-309. Springer-Verlag, Berlin, March 1989.

66. M.A. Hasan, M. Wang, and V.K. Bhargava. Division and bit-serial multiplication over GF(qm). IEEE Trans, on Computers, 41(8):972-980, August 1992.

67. M.A. Hasan, M. Wang, and V.K. Bhargava. Modular construction of low complexity parallel multipliers for a class of finite fields GF(2m). IEEE Trans, on Computers, 41(8):962-971, August 1992.

68. S.T.J. Fenn, M. Benaissa, and D. Taylor. GF(2m) multiplication and division over the dual base. IEEE Trans, on Computers, 45(3):319-327, March 1996.

69. Захаров B.M., Нурутдинов Ш.Р. Шалагин С.В. Аппаратная реализация умножения элементов поля Галуа на программируемых микросхемах архитектуры FPGA // Вестник Казан, гос. техн. ун-та им. А.Н. Туполева. 2001. №1. С. 36-41.

70. Нурутдинов Ш.Р., Шалагин С.В. Вычисление произведения элементов поля Галуа // Теория сеточных методов для нелинейных краевыхзадач. Материалы третьего Всеросс. семинара. Казань: Изд-во Казанского мат. общества, 2000. - С. 144.

71. Рааг С., Fleishmann P., Roelse P. Efficient Multiplier Architectures for Galois Fields GF((24)") // IEEE Trans. Computers. 1998. № 2. Vol. 47. P. 162-170.

72. C. Paar and N. Lange. A comparative VLSI synthesis of finite field multipliers. In 3rd International Symposium on Communication Theory and its Applications, Lake District, UK, July 10-14 1995.

73. G. Orlando and C. Paar. A High-Performance Reconfigurable Elliptic Curve Processor for GF(2m). Workshop on Cryptographic Hardware and Embedded Systems (CHES) 2000, Springer-Verlag, Lecture Notes in Computer Science 1965, 2000.

74. С. Paar, P. Fleischmann, and P. Soria-Rodriguez. Fast arithmetic for public-key algorithms in Galois fields with composite exponents. IEEE Transactions on Computers, 48(10): 1025-1034, October 1999.

75. Алгебра, коды, диагностика. / Ю.Л. Сагалович.- М: Институт проблем передачи информации. РАН. 1993 г. 196 с.

76. Нурутдинов Ш.Р., Столов Е.Л. Перестраиваемые схемы в системах встроенного тестирования. // Автоматика и телемеханика. 1995. -№3 - С. 179-183.

77. Кун С. Матричные процессоры на СБИС. Пер. с англ. -М.: Мир, 1991.-672с.

78. Нурутдинов Ш.Р. Моделирование цепей Маркова в полях Галуа //Дискретная математика.-М: АкадемИздатЦентр, Наука, РАН, том 16, выпуск 2, 2004. С.136-147.

79. Никонов В.В., Кравцов С.Г., Самошин В.Н. Систолическая обработка информации: элементная база и алгоритмы // Зарубежная радиоэлектроника, 1987, №7. С.34-52.

80. G. Orlando and С. Paar. An Efficient Squaring Architecture for GF(2m) and its Applications in Cryptographic Systems. Electronic Letters, June 2000, vol. 36, no. 13, pp. 1116-1117.

81. C.C. Wang and D. Pei. A VLSI design for computing exponentiation in GF(2m) and its application to generate pseudorandom number sequences. IEEE Trans, on Computers, C-39(2):258-262, Febr. 1990.

82. Нурутдинов Ш.Р. Умножение в поле Галуа GF(16) в базисе поля GF(4). // Сборник трудов IX Всероссийской школы-семинарга «Современные проблемы математического моделирования». Ростов-на-Дону: Изд-во Ростовского гос. ун-та, 2001. С. 272-274.

83. Нурутдинов Ш.Р. Операция умножения в расширениях полей Галуа// Материалы VIII Международного семинара "Дискретная математика и ее приложения" (2-6 февраля 2004г.) 4.1.- М:Изд-во центра прикл. исслед. при Мех-Мат фак-те МГУ, 2004.- С. 145-148.

84. Нурутдинов Ш.Р. Реализация операции умножения в поле Галуа GF(16) в базисе поля GF(4)II В сб. "Исследования по прикладной математике". Выпуск 23.-Казань: Изд-во Казан, мат. общ., 2001.-С.1П-П7.

85. Xilinx. The Programmable Logic Data Book 1998, Copyright 1998 Xilinx, Inc., Printed in U.S.A.

86. Нурутдинов Ш.Р., Столов Е.Л. Реализация автомата асинхронной сетью. // Кибернетика. Киев, 1988. - №6. - С. 108-109.

87. Нурутдинов Ш.Р. Обеспечение отказоустойчивости сетевой модели автомата// Исследования по прикладной математике. Вып.№16.: Изд-во Казан, ун-та, 1989. С. 138-144.

88. Нурутдинов Ш.Р. Моделирование конечных детерминированных автоматов в полях Галуа// Труды V Всероссийского семинара "Сеточные методы для краевых задач и приложения"( 17-21 сентября 2004г.) Казань:2004,- С.61-64.

89. Нурутдинов Ш.Р., Шалагин С.В. Минимизация количества элементов однородной вычислительной структуры // Исследования по информатике. Вып. 2. Казань: Отечество, 2000. С. 117-124.

90. Левин Б.Р., Шварц В. Вероятностные модели и методы в системах связи и управления. М.: Радио и связь, 1985. - 312 с.

91. Захаров В.М. Аппаратно-программная организация специализированных процессоров на основе автономных вероятностных автоматов: Дис. д-ра. техн. наук. Казань. - 1992.

92. Захаров В.М., Нурутдинов Ш.Р., Шалагин С.В., Соколов С.Ю. Представление марковских функций над полем Галуа // Тез. докл. XIII Междунар. конф. «Проблемы теоретической кибернетики». М.: Изд-во МГУ, 2002. 4.1. С.71.

93. Глова В.И., Захаров В.М., Песошин В.А., Шалагин С.В. Моделирование. Дискретные вероятностные модели. Учебное пособие. Казань: Изд-во АБАК, 1998. - 50 с.

94. Захаров В.М., Баранов Г.Г. Синтез циклических многозначных последовательностей с заданной структурой // Тезисы научно-технической конференции «Вероятностные автоматы и их приложения». Тбилиси: «Мецниереба», 1986. - С. 24.

95. Nurutdinov Sh.R. Markov Chains in Galois Fields//International conference OFEA'2001 OPTIMIZATION of FINITE ELEMENT APPROXIMATIONS \& SPLINES AND WAVELETS. S.-PETERBURG-pp.47-49.

96. Кемени Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука, 1970. -272 с.

97. Захаров В.М., Нурутдинов Ш.Р., Соколов С.Ю., Шалагин С.В. Полиномиальное представление конечноавтоматных случайных-последовательностей над полем Галуа // Вестник Казан, гос. техн. ун-та им. А.Н. Туполева. 2003. - № 2. - С. 24-28.

98. Нурутдинов Ш.Р., Соколов С.Ю., Шалагин С.В. Синтез автоматных моделей цепей Маркова и их функций в конечных полях // Труды V Междунар. конф. «Новые информационные технологии и системы». Пенза: Изд-во Пензенск. ун-та, 2002. С. 211-213.

99. Галлагер Р. Теория информации и надежная связь. М.: Сов. радио, 1974.

100. Феллер В. Введение в теорию вероятностей и ее приложения. М.: Мир, 1984. Т. 1.

101. Нурутдинов Ш.Р. Обеспечение отказоустойчивой сетевой модели автомата. // Исследования по прикладной математике. Вып. 16. Казань: Изд-во Казанского ун-та. 1989. - С. 138-144.

102. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.

103. Романовский В.И. Дискретные цепи Маркова. M.-JL: Гостехиздат, 1949.-436 с.

104. Zacharov V.M., Kuznetsov S.E. Complexity of the problem of approximation of stochastic matrix by rational elements // International Conference FCT'87. Kazan, June 1987. Springer-Verlag Berlin, 1987. Vol. 278. P. 483-487.

105. Баранов Г.Г., Захаров B.M., Кузнецов C.E. Синтез циклических многозначных последовательностей с заданной структурой // Кибернетика. 1989. № 1.С. 15-18.

106. Захаров В.М., Столов E.JL, Баранов Г.Г., Комаров Ю.С. Генерирование псевдослучайных сигналов с марковскими свойствами // Тезисы докладов на конференции «Синтез и анализ цифровых алгоритмов обработки сигналов». Новгород, 1981.

107. Захаров В.М. Представление вероятностных автоматов некоторыми моделями орграфов // Тезисы докладов конф. «Математические методы в задачах исследования сложных систем». Пенза, 1984. -С.44-45,

108. Соколов С.Ю. Автоматное моделирование случайных процессов с последействием на основе эйлеровых стохастических матриц // Вестник Казан, гос. техн. ун-та им. А.Н. Туполева. 2003. - № 2. - С. 5862.

109. С.Е.Кузнецов, Н.Н.Нурмеев, Ф.И.Салимов. Задача о минимальном имплицирующем векторе.// Мат. Вопр. Киберн. Вып.З.: Сб. ст. /Под ред. С.В.Яблонского.- М.:Наука. Физматлит.С. 199-216.

110. Мальцев П.П. и др. Программируемые логические ИМС на КМОП-структурах и их применение. М.: Энергоатомиздат, 1998.

111. Березнев А.Г. и др. Применение программируемых логических интегральных схем архитектуры FPGA в проектировании средств вычислительной техники. // Информационные технологии. 1996. - №1. - С. 34-37.

112. Захаров В.М., Нурутдинов Ш.Р., Шалагин С.В. Аппаратная реализация умножения элементов поля Галуа на программируемых микросхемах архитектуры FPGA // В сб. "Вестник Казанского государственного технологического университета", №1, 2001.- С.36-47.

113. Иванов М.А., Чугунов И.В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей. М.: КУДНЦ -ОБРАЗ, 2003.

114. Кнышев Д.А., Кузелин М.О. ПЛИС фирмы «XILINX»: описание структуры основных семейств. М.: «Додэка - XXI», 2001.

115. Проектирование цифровых устройств на основе САПР/Xilinx. Учебное пособие / Бахарев А.Н., Захаров В.М., Кузнецов В.М., Песо-шин В.А., Шалагин С.В. Под редакцией Песошина В.А. Казань: Изд-во КГТУ им. А.Н.Туполева, 2002. - 121 с.