Полиномиальные модели автоматных преобразований над полем GF(2")

• Автор: Нурутдинов, Шамиль Рамилович
• Шифр специальности: 05.13.18
• Научная степень: Докторская
• Год защиты: 2005
• Место защиты: Казань
• Количество страниц: 222 с. : ил.

ОГЛАВЛЕНИЕ.

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

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

ВВЕДЕНИЕ.

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

полем Р2п

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

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

элементов поля ОР2п.

1.3 Структурная модель, реализующая операцию умножения

элементов поля СР2п.

1.4 Представление функций в ОР2п многочленами
от нескольких переменных.
1.4.1 Реализация многочленом от одной переменной.
1.4.2. Реализация функции от 5 переменных в Р2п
многочленом от 5 переменных.
1.5. Структурные реализации полиномиальной функции
и оценки их сложности.
1.5.1. Параллельная структура.
1.5.2. Систолическая векторная структура полинома , .
1.5.3. Систолическая структура полинома ,.
1.5.4. Итеративная структура многочлена Ци.
Г ЛАВА 2. Модели схем умножения в расширениях поля ОР2п
2.1. Применение алгоритма КарацубыОфмана для построения схемы
умножения в составных полях вида вРЦ2к 4
2.2. Модификация алгоритма КарацубыОфмана для построения
схемы умножения в составных полях вида ОР2к 4
2.3. Алгоритм построения составного поля вида йР2к2,
изоморфного полю вида Р2
2.4. Построение схемы умножения в составном
поле вида 7Р 2.
2.5. Построение схемы умножения в составном
поле вида вР 2 2.
ГЛАВА 3. Полиномиальные модели детерминированных автоматных
преобразований над полем ОР2п
3.1. Моделирование конечного автомата однородной сетью
элементарных автоматов в поле ОР2п.
3.2. Моделирование в классе комбинационных схем.
3.2.1. Полиномиальная модель на основе многочлена
от одной переменной над полем Р2п.
3.2.2. Полиномиальная модель на основе многочлена
от двух переменных над полем Р2п.
3.3. Полиномиальная модель автомата с памятью.
3.4. Синтез типовых элементов однородной
вычислительной структуры.
3.4.1. Типовой элемент последовательной структуры.
3.4.2. Типовой элемент параллельной структуры.
3.4.3. Методика синтеза однородных автоматных схем.
3.5. Минимизация структуры полиномиальной модели ГЛАВА 4. Полиномиальные модели вероятностных автоматов
и функций конечных цепей Маркова над полем йР2п
4.1. Определения базовых вероятностных автоматных моделей.
4.2. Синтез автоматной марковской модели над полем вР2п.
4.3. Синтез генераторов марковских функций над полем Р2п.
4.3.1. Полиномиальная модель генератора процесса У
над полем СР2п.
4.3.2. Полиномиальная модель генератора процесса 2у
над полем Р2п.
4.4. Полиномиальная модель марковской функции вида асвязной
цепи Маркова.
4.5 Синтез конечноавтоматных случайных последовательностей
над полем вР2п.
4.5.1. Определение вероятностной автоматной модели
и постановка задачи
4.5.2. Полиномиальное представление конечноавтоматной модели
надполем Р2п.
4.6. Синтез генератора дискретной случайной величины.
над полем 2.
4.7 Автоматное моделирование случайных процессов с последействием
на основе эйлеровых стохастических матриц.
4.7.1 Автоматная модель.
4.7.2 Структурная схема автоматной модели.
4.8 Реализация последовательности в полях 2.
4.9 Полиномиальные модели вероятностных автоматов общего вида
над полем 2.
ГЛАВА 5. Реализация и тестирование полиномиальных моделей средствами программного комплекса и САПР ПЛИС
5.1. Программируемые логические интегральные схемы
5.2. Представление и анализ структурных моделей
операции умножения в поле 2
5.2.1. Определение базовых математических
моделей умножителя.
5.2.2. Структурные модели умножителей
и их оценки сложности.
5.3. Оценки сложности структур умножителей над полем 2 .
в базисе программируемых матрицах логических элементов.
5.3.1. Оценки сложности моделей в базисе ПЛИС.
5.3.2. Сравнение теоретических оценок с оценками реальных аппаратных затрат для схем умножения.
5.4. Пакет программ, реализующий автоматные модели генераторов
марковских функций.
5.5. Пакет программ, реализующий полиномиальные модели
генераторов марковских функций над полем 2.
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


XIII Международной конференции Проблемы теоретической кибернетики Казань, г. V Международной научнотехнической конференции Новые информационные технологии и системы Пенза, г. Двенадцатой Международной конференции по вычислительной механике и современным прикладным программным системам Владимир, г. Первая Всероссийская научная конференция Методы и средства обработки информацииМосква, г. Методы моделирования Казань, гг. Теоретической кибернетики Казанского государственного университета Казань, гг. VIII Международном семинаре Дискретная математика и ее приложения Москва, г. Актуальные проблемы математики и механики Казань, г. VI Международная конференция Дискретные модели в теории управляющих системМосква, г. XIV Международная конференция Проблемы теоретической кибернетики Пенза, мая г. Метод вычисления коэффициентов многочлена, реализующего отображение поля 2 в себя. Теорема, устанавливающая возможность реализации конечного автомата однородной сетью над ОР2п. Алгоритм и методика реализации конечного автомата однородной сетью над СР2п. Теорема, устанавливающая возможность вычисления коэффициентов примитивного многочлена для построения поля вида вР2 , изоморфного полю вида Рк. Методика построения схем умножения в составных полях Галуа, позволяющая сократить вычислительную сложность и повысить скорость выполнения операции умножения. Теорема, доказывающая существование алгоритма уменьшения количества ненулевых коэффициентов при высших степенях полинома над полем ОР2р, используемого при полиномиальном моделировании отображения. СР2т ОР2к СР2к, ртк. Полиномиальные модели и метод представления МФ над полем СР2п. Теоремы, устанавливающие взаимосвязь МФ и полиномиальных функций над полем СР2п. Структурные модели генераторов ЦМ и МФ над полем ОР2п и методика их построения в базисе полиномиальных функций над полем ОР2п. Полиномиальная модель представления генератора дискретной случайной величины полиномиальной функцией в поле СР2п. Автоматная модель из класса вероятностных автоматов с перестраиваемой структурой и е полиномиальное представление над полем СРТ. Комплекс прикладных программ, реализующих предложенные методики и алгоритмы. Основное содержание диссертации опубликовано в работах, включая одну монографию, статей и тезисов докладов. Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка используемой литературы, включающего 0 наименований, и приложения. Общий объем работы составляет 2 страницы, включая рисунков и таблиц. В конце каждой главы имеются выводы. Содержание работы. Во введении обосновывается актуальность темы диссертации, дается определение цели и задач исследования, приводится перечень основных результатов, выносимых на защиту. Представляется актуальным выполнение настоящего исследования, в котором разработаны теоретические основы, алгоритмы и методики представления детерминированных и вероятностных автоматных моделей полиномиальными функциями над полем йР2п, а также разработан метод синтеза однородных вычислительных структур в поле СР2п. Такой подход позволяет во многих случаях получать управляемые преобразователи мерных сигналов, для которых может быть легко использована технология ПЛИС. Дана структура диссертации. В первой главе Вычислительные модели преобразований над полем 2, исследуется эффективность создания вычислительных моделей в полях ОР2п. Вводятся известные понятия, определения и модели, необходимые для решения задач диссертационной работы. Содержатся необходимые сведения из аппарата полей Галуа. Разработана структурная модель операции умножения двух произвольных элементов поля ОР2п в базисе поля СР2. Исследованы условия представления любого отображения в поле Галуа в виде многочлена от переменных. Разработан метод вычисления коэффициентов многочленов, реализующих отображение поля СР2п в себя. Разработаны однородные вычислительные структуры, вычисляющие значения многочленов в поле СР2п. Во второй главе Модели схем умножения в расширениях поля ОР2п решается задача построения эффективных схем умножения в поле СР2п.