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

• Автор: Соколов, Сергей Юрьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Казань
• Количество страниц: 157 с.

ОГЛАВЛЕНИЕ

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

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

ВВЕДЕНИЕ

ГЛАВА 1. Базовые понятия и определения

1. Автоматные модели простой однородной цепи Маркова

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

3. Полиномиальная модель простой однородной цени

Маркова

4. Определения теории графов

5. Методы многомерного статистического анализа

ГЛАВА 2. Полиномиальное представление автоматных
моделей марковских функций над полем Галуа
1. Определения вероятностных автоматных моделей
случайных процессов из класса марковских функций
2. Полиномиальные модели и структурные схемы генерато ров марковских функций над полем Галуа
3. Полиномиальное представление конечноавтоматных
случайных последовательностей над полем Галуа
4. Заключение
ГЛАВА 3. Автоматное моделирование случайных процессов с последействием на основе эйлеровых
стохастических матриц
1. Постановка задачи
2. Автоматная модель
3. Структурная схема автоматной модели
4. Реализация последовательности в конечных полях
5. Заключение
ГЛАВА 4. Построение схем умножения в составном поле вида
сг2
1. Применение алгоритма КарацубыОфмана для построения
схемы умножения в составных полях вида СГ2 4
2. Модификация алгоритма КарацубыОфмана для
построения схемы умножения в составных полях вида
I
3. Алгоритм построения составного поля вида Г2 , изоморфного полю вида С7А
4. Построение схемы умножения в составном поле вида
СГ 2
5. Построение схемы умножения в составном поле вида
вГ22 Ю
6. Заключение
ГЛАВА 5. Комплекс прикладного программного обеспечения для реализации синтеза и анализа полиномиальных моделей генераторов марковских функций
1. Пакет программ, реализующий автоматные модели
генераторов марковских функций
2. Пакет программ, реализующий полиномиальные модели
генераторов марковских функций над полем Г2
3. Методика статистического анализа генераторов
марковских функций
4. Заключение
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


В связи с отмеченным выше актуальной является задача развития предложенного в работах [-] подхода моделирования конечных ЦМ над полем GF(2"): построение полиномиальных моделей для более широкого класса случайных дискретных процессов и представление структурных схем генераторов МФ над полем GF(2n). В прикладном отношении актуальной является задача повышения эффективности предложенного подхода, с цслыо сокращения используемой площади кристалла и увеличения быстродействия синтезируемых устройств. Целью диссертационной работы является: разработка эффективных моделей генераторов и методов моделирования случайных дискретных процессов из класса марковских функций с использованием операций в полях Галуа GF(2"). МФ и их статистического анализа. Научная новизна работы. Предложены полиномиальные модели случайных процессов вида МФ над полем Галуа из класса, порождаемого автономными вероятностными автоматами с заданными ограничениями на функции перехода и выхода, в частности модели сложных ЦМ, марковского источника и конечноавтоматных случайных последовательностей. Модели МФ представлены в виде суперпозиций полиномиальных функций от одной и двух переменных над полем б/г(2#*). Предложены структурные схемы генераторов МФ на основе полученных полиномиальных моделей над полем 2"). Решена задача автоматного моделирования процессов с последействием на основе разработанной многоурновой модели без возвращения. Предложен метод моделирования над полем Галуа подкласса случайных последовательностей, соответствующего известному подмножеству эйлеровых орграфов - классу произвольно-эйлеровых (произвольно-вычерчиваемых) орграфов. Предложены структурные схемы генераторов этого типа последовательностей. Р(2 ), позволяющие сократить вычислительную сложность и повысить скорость выполнения операции умножения - базовой операции, необходимой для реализации схем генераторов МФ. Разработана методика построения составных полей для предлагаемых схем умножения. Предложена методика статистического распознавания генераторов МФ на основе методов многомерной математической статистики, включающая модель признаков и позволяющая выполнять идентификацию и проводить тестирование рассматриваемых генераторов. Практическая значимость работы. Предложенные полиномиальные модели генераторов МФ позволяют использовать аппарат полей Галуа при моделировании рассматриваемых случайных процессов, что дает возможность представить их в виде алгебраических выражений, допускающих параллельную реализацию. Предложенные структурные схемы генераторов МФ над полем <7/’/(2/*) дают возможность их непосредственного использования при проектировании специализированных автоматных моделей. Галуа. Разработанная методика многопараметрической классификации и идентификации стохастических матриц и случайных последовательностей позволяет определить степень сходства заданных статистических характеристик различных классов рассматриваемых случайных процессов, оценить их качество (в статистическом смысле). Предложенная методика может быть применена для задач идентификации более широкого класса (идентификация вида генератора псевдослучайной последовательности, шифра и т. Результаты работы использованы в НИР за -гг. Российского фонда фундаментальных исследований (РФФИ) № 3 «Энтропийно-сложностные свойства дискретных вычислительных моделей», по гранту РФФИ № 9 «Сложностныс свойства классических и квантовых вычислений», по проекту № 5- «Синтез и сложность детерминированных и вероятностных дискретных вычислительных моделей» программы «Университеты России», в ОАО «КНИАТ» (г. Казань), в Центре новых информационных технологий Республики Татарстан (г. Казань), в ГИБДД МВД Республики Татарстан (г. Казань) и в учебном процессе кафедры Компьютерных систем и информационной безопасности КГТУ им. А.Н. Туполева (КАИ). Апробация результатов работы. Основные результаты работы докладывались и обсуждались на итоговой университетской научно-технической конференции студентов КГГУ им. А. Н. Туполева (Казань, г. IX Всероссийские Туполевские чтения студентов» (Казань, г. Казань, г. Четвертом Всероссийском семинаре «Сеточные методы для краевых задач и приложения» (Казань, г. Юбилейные X Всероссийские (с международным участием) Туполевские чтения студентов» (Казань, г.