Содержание к диссертации
Введение
Глава 1. Связь цепей Маркова, вероятностных автоматов и полиномиальных функций в конечном поле 16
1.1. Связь цепей Маркова, вероятностных автоматов и полиномиальных функций 16
1.2. Базовые понятия и теоремы 22
1.2.1. Определения теории цепей Маркова 22
1.2.2. Определения теории конечных полей 24
1.2.3. Базовые полиномиальные модели для моделирования цепей Маркова и их функций в поле GF(2") 25
1.3. О задаче анализа цепей Маркова по критерию линейной сложности 27
1.4. О задаче разработки комплекса методик и программ 30
1.5. Выводы по главе 31
Глава 2. Методы представления случайных последовательностей полиномиальными функциями над конечным полем 32
2.1. Представление стохастических матриц полиномиальными функциями над полем GF(2") с учетом точности представления элементов матриц 32
2.1.1. Введение 32
2.1.2. Подход разложения матриц, основанный на методе минимакса 34
- Алгоритм минимакса 34
2.1.3. Двоично-рациональный подход разложения матриц 36
- Алгоритм 2 36 -Алгоритм 2м 38
- Алгоритм 3 45
- Алгоритм Зм 47
- Алгоритм 4 49
- Алгоритм 4м 54
2.1.4. Метод построения функций цепей Маркова над полем GF(2") и оценки порядка поля 59
2.1.5. Выводы по разделу 60
2.2. Представление расширенных цепей Маркова над полем GF(2") 63
2.2.1. Введение 63
2.2.2. Получение стохастической матрицы расширенной цепи Маркова 63
- Постановка задачи 63
- Определение "промежуточной" матрицы переходов 64
- Определение матрицы О расширенной цепи Маркова 70
- Алгоритм вычисления матрицы О расширенной цепи Маркова по 72
матрице Р исходной цепи Маркова
2.2.3. Полиномиальные модели расширенных цепей Маркова над полем GF(2") 72
- Модель генератора расширенной цепи Маркова на регистре сдвига 72
- Полиномиальная модель расширенной цепи Маркова на основе имплицирующего вектора 73
- Полиномиальная модель расширенной цепи Маркова на основе приведенного автомата 78
2.3. Моделирование случайных последовательностей минимальными полиномами над конечным полем по заданной стохастической матрице 82
2.3.1. Введение 82
2.3.2. Теоретический анализ. Постановка задачи 83
2.3.3. Схема построения минимального многочлена над полем GF(gc) 84
2.3.4. Метод моделирования случайной последовательности на основе минимального полинома 86
2.3.5. Характеризация класса случайных последовательностей 90
2.4. Выводы по главе 92
Глава 3. Методы анализа полиномиальных функций, моделирующих случайные последовательности в конечном поле 93
3.1. Анализ нелинейных моделей преобразователей случайных последовательностей над полем GF(2") на основе стохастических матриц 93
3.1.1. Введение 93
3.1.2. Определение базовых полиномиальных функций над полем GF(2") 94
3.1.3. Полиномиальные нелинейные динамические модели, порождающие функции цепей Маркова. Вероятностные характеристики моделей 95
- Полиномиальная модель цепи Маркова 95
- Полиномиальная модель марковской функции Bt 96
- Полиномиальная модель марковской функции Zt 100
- Полиномиальная модель марковской функции Z't 102
3.2. Статистический анализ линейной сложности регулярных цепей Маркова 104
3.2.1. Введение 104
3.2.2. Постановка задачи 106
3.2.3. Реализация и тестирование алгоритма Берлекэмпа-Мэсси 108
3.2.4. Обсуждение полученных результатов 113
3.3. Выводы по главе 117
Глава 4. Комплекс методик и программ для решения задач построения и анализа полиномиальных функций и моделирования случайных последовательностей 118
4.1. Методика программной реализации представления простых и расширенных цепей Маркова над полем GF(2") 118
4.2. Методика программной реализации моделирования случайных последовательностей на основе минимальных полиномов 121
4.3. Программная реализация алгоритма Берлекэмпа-Месси 122
4.4. Методика программной реализации статистического анализа линейной сложности регулярных цепей Маркова 126
4.5. Программный комплекс "Лабораторный практикум вычислений в конечных полях" 128
4.6. Программный комплекс "Генераторы псевдослучайных чисел" 131
4.7. Подсистема временного прогнозирования для автоматизированного рабочего места менеджера предприятия 133
4.8. Выводы по главе 137
Заключение 138
Список литературы
- Базовые полиномиальные модели для моделирования цепей Маркова и их функций в поле GF(2")
- Подход разложения матриц, основанный на методе минимакса
- Получение стохастической матрицы расширенной цепи Маркова
- Полиномиальные нелинейные динамические модели, порождающие функции цепей Маркова. Вероятностные характеристики моделей
Введение к работе
Во введении обосновывается актуальность темы диссертации, дается определение цели и задач исследования, приводится перечень основных результатов, выносимых на защиту. Дана структура диссертации.
Актуальность работы. Одним из подходов моделирования цепей Маркова (ЦМ) и марковских функций является подход, использующий теорию конечных полей [1]. Перспективность этого подхода определяется приложением функций конечных ЦМ [2-4], возрастающей сложностью вероятностных дискретных моделей [2, 3] и эффективностью арифметики конечных полей в задачах цифровой обработки информации [5-10]. Аппарат конечных полей используется для решения задач синтеза вероятностных автоматов и генераторов случайных двоичных последовательностей, для моделирования случайных линейных зависимых процессов в конечном поле и некоторых типов цепей Маркова и вероятностных автоматов (ВА) (Аблаев Ф.М. [11, 12], Бухараев Р.Г. [2, 3, 13-15], Кирьянов Б.Ф. [16], Крашенинников В.Р. [17, 18], Кузнецов В.М. [19], Латыпов Р.Х. [20-24], Мансуров P.M. [25], Осмоловский С.А. [26], Песошин В.А. [19, 25], Столов Е.Л. [20-23, 27-30], Taylor L. [31]).
В работах Захарова В.М., Нурутдинова Ш.Р., Соколова С.Ю., Шалагина СВ. (2000-2006 г.г.) [32-34] предложен подход моделирования дискретных случайных процессов на полиномиальных моделях, описываемых полиномиальными функциями (ПФ) над полем GF(2"). Полиномиальные функции рассматриваются как модели дискретных преобразователей цепей Маркова [10, 32-37]. Разработаны методы представления полиномиальными функциями над полем GF(2") простых и сложных ЦМ и определенных функций однородных и неоднородных ЦМ (ФЦМ). Задача представления решается как задача вычисления коэффициентов полиномов над полем GF(2") на основе заданных стохастических матриц. Решена валеная прикладная задача отображения полиномиальных моделей в однородные вычислительные среды, позволяющие реализовать параллельные алгоритмы вычисления и проводить потоковые преобразования над «-мерными векторами при моделировании дискретных случайных процессов [10, 32-39]. Однако, в этом направлении существуют недостаточно исследованные вопросы и нерешенные задачи, имеющие теоретическое и практическое значение.
Для дальнейшего развития и повышения эффективности методов моделирования дискретных случайных процессов в конечном поле актуальным является исследование вопросов, связанных с повышением точности полиномиальных моделей, определением их свойств и вероятностных характеристик, расширением класса случайных последовательностей (СП), представляемых полиномиальными функциями над полем GF(2") и конечным полем GF(qc) характеристики qc>2, с получением оценок порядка поля в зависимости от точности задания закона цепи Маркова и структуры стохастических матриц (СМ), а также ряд других вопросов, связанных с построением (вычислением коэффициентов) и анализом полиномиальных функций над конечным полем.
Объект исследования. Модели и аналитические методы моделирования случайных последовательностей над конечным полем.
Предмет исследования. Полиномиальные модели, порождающие функции цепей Маркова в конечном поле, свойства и характеристики этого класса моделей.
Целью диссертационной работы является развитие полиномиальных моделей, аналитических методов и построение эффективных методик для моделирования цепей Маркова и их функций в конечном поле.
Научная задача. Разработка новых аналитических методов построения полиномиальных функций и анализа свойств полиномиальных функций, порождающих случайные последовательности в конечном поле на основе стохастических матриц, с учетом структурных свойств СМ и точности задания переходных вероятностей.
Решение общей научной задачи и достижение поставленной цели связано с решением следующих задач.
Разработка метода и алгоритмов представления стохастических матриц полиномиальными функциями над полем GF(2"). Определение оценок порядка поля GF(2") с учетом точности задания элементов стохастических матриц (переход от объекта ЦМ к ВА и к ПФ, от ВА и ПФ к ФЦМ (рис.В1,а) по схеме, представленной на рис.В1,б)).
Разработка метода и алгоритмов моделирования расширенных цепей Маркова (РЦМ) полиномиальными функциями над полем GF(2"). Определение порядка поля GF(2") с учетом структуры стохастической матрицы расширенной цепи Маркова (переход от простой ЦМ к расширенной ЦМ, и от расширенной ЦМ к В А и к ПФ (рис.В1,а) по схеме, представленной на рис .В 1,6)).
Разработка метода представления неразложимых стохастических матриц с заданной точностью полиномами минимальной степени над конечным полем GF(gc) характеристики qc > 2 (представление объекта ЦМ в виде полинома над конечным полем (рис.В1,а) с использованием объекта СМР (рис.В1,б)).
Разработка метода вычисления характеристик полиномиальных моделей, предназначенных для получения случайных последовательностей из класса функций цепей Маркова (переход от объекта ПФ к ЦМ и ФЦМ (рис.В1,а)).
Статистический анализ цепей Маркова по критерию линейной сложности (ЛС) последовательностей. Исследование взаимосвязи энтропии неразложимых стохастических матриц с линейной сложностью реализаций цепей Маркова (исследование объекта ЦМ (рис.В1,а) по объекту СМ Р (рис.В1,б)).
Разработка комплекса методик и программ, реализующих предлагаемые методы и алгоритмы.
Рис. В1,а иллюстрирует известную [2, 3, 32, 33] существующую взаимосвязь между математическими объектами - ЦМ, В А, ПФ, ФЦМ. Рис. В 1,6 иллюстрирует схему общего подхода [32-34], в рамках которого решаются перечисленные задачи 1-6. Подход основан на разложении стохастических матриц Р на пару - дискретную случайную величину (ДСВ) и конечный
детерминированный автомат (КДА), получаемые из разложения P = ^iqiB
1-Х
[40], где q = (q,) - имплицирующий вектор длины /, J.gt, = 1
Данная схема представляет предмет исследования, сформулированный выше.
а) б) \^_у
Puc.el. Взаимосвязи и схема общего подхода решаемых задач Методы исследований. Для решения поставленных задач использованы методы теории чисел, теории вероятностей, математической статистики, теории детерминированных и вероятностных автоматов, теории графов, аппарат конечных полей, линейной и полиномиальной алгебры, дискретной математики.
Научная новизна работы и значимость результатов.
- Новые метод и алгоритмы представления стохастических матриц с
двоично-рациональными элементами полиномиальными функциями над полем
GF(2"), с учетом точности задания переходных вероятностей. Сформулированы
и доказаны теоремы, обосновывающие метод.
Новые метод и алгоритмы получения и отображения закона расширенных цепей Маркова в полиномиальную функцию над полем GF(2W). Сформулированы и доказаны теоремы, обосновывающие метод.
Новый метод представления стохастических матриц с заданной точностью и моделирования случайных последовательностей из класса неоднородных цепей Маркова полиномами минимальной степени над полем GF(<7C) характеристики qc>2. Доказана теорема, устанавливающая линейную связь между точностью задания стохастической матрицы и величиной минимальной степени полинома.
Новый метод определения вероятностных характеристик случайных последовательностей из класса функций однородных цепей Маркова, порождаемых полиномиальными нелинейными динамическими моделями над полем GF(2"). Доказаны теоремы, устанавливающие формулы для вычисления асимптотических вероятностных характеристик случайных
последовательностей.
- Методика исследования однородных простых и сложных цепей Маркова
на основе критерия линейной сложности. Сформулирован критерий
нахождения длин реализаций марковских последовательностей при заданной
точности представления матриц цепей Маркова. Определены стохастические
зависимости линейной сложности реализаций цепей Маркова от энтропии
стохастических матриц.
Достоверность результатов работы. Основные полученные результаты сформулированы в виде теорем и утверждений, приведены их доказательства. Предложенные аналитические методы и алгоритмы обоснованы доказательством теорем. Адекватность предложенных моделей подтверждается компьютерным моделированием и сравнением с известными результатами.
Практическая значимость работы.
- Решение задачи представления РЦМ полиномиальными функциями над
полем GF(2") расширяет класс дискретных случайных процессов, получаемых
на полиномиальных моделях, и позволяет определить свойства данных
процессов и стохастических матриц РЦМ.
-Предложенные алгоритмы разложения СМ ЦМ на имплицирующий вектор (ИВ) и множество стохастических булевых матриц (СБМ) позволяют определить вычислительную и комбинационную сложности вероятностных автоматов, синтезируемых в некотором логическом базисе.
Полученные формулы определения предельного распределения вероятностей символов СП, порождаемых полиномиальными нелинейными динамическими моделями дискретных преобразователей информации, и фундаментальная матрица для СМ позволяют на их основе получить ряд других характеристик СП, например, матрицу средних времен достижения, векторы предельных дисперсии и корреляции.
Метод моделирования СП на основе минимального полинома позволяет: воспроизводить на линейных регистрах сдвига реализации ЦМ; расширить функциональное использование линейных регистров сдвига.
Методика исследования ЛС марковских последовательностей расширяет класс задач применения ЛС, дает возможность моделировать ЦМ на основе линейных и нелинейных полиномов минимальных степеней, позволяет выявлять свойства ЛС марковских функций.
Комплекс программ, алгоритмов и методик является инструментальным средством для моделирования СП и исследования свойств полиномиальных функций над конечным полем.
Результаты работы используются:
в подсистеме временного прогнозирования производственно-экономических показателей состояния предприятия (на базе разработанной в диссертации программной реализации математического аппарата числовых стохастических матриц), включенной в состав автоматизированного рабочего места менеджера предприятия, введенного в опытную эксплуатацию в ОАО "ICL-КПО ВС", г. Казань (справка об использовании результатов);
в учебном процессе кафедры Компьютерных систем (предыдущее
название (до 2006 года) - Компьютерные системы и информационная безопасность) и кафедры Систем информационной безопасности КГТУ им. А.Н. Туполева в форме учебного электронного пособия "Лабораторный практикум по вычислениям в конечных полях" (акт внедрения).
На защиту выносятся следующие результаты, полученные лично:
метод и алгоритмы определения закона и свойств РЦМ по СМ исходной простой ЦМ, теоремы, обосновывающие метод и алгоритмы;
метод представления заданного закона РЦМ минимизированной автоматной моделью и полиномиальной функцией над полем GF(2"), теоремы, обосновывающие метод и свойства стохастических матриц РЦМ;
- метод и алгоритмы разложения СМ ЦМ с двоично-рациональными
элементами на ИВ и множество СБМ, теоремы, обосновывающие метод и
алгоритмы;
аналитический метод определения характеристик СП из класса функций однородных ЦМ, порождаемых полиномиальными нелинейными динамическими моделями над полем GF(2"), теоремы, обосновывающие метод;
статистический метод исследования однородных простых и сложных ЦМ на основе критерия ЛС;
- аналитический метод представления СМ с заданной точностью и
моделирования СП из класса неоднородных ЦМ полиномами минимальной
степени над полем GF(qc), теорема, обосновывающая метод;
- комплекс методик и программ, реализующий предложенные методы и
алгоритмы.
Апробация результатов работы. Основные результаты докладывались и
обсуждались на следующих конференциях и семинарах: X-XV Всероссийские
молодежные научные конференции "Туполевские чтения" (Казань, 2002-2007);
Всероссийская научная конференция студентов и аспирантов (Таганрог, 2004);
XIV Международная конференция "Проблемы теоретической кибернетики"
(Пенза, 2005); Региональная научно-методическая конференция
"Профессиональные компетенции в структуре модели современного инженера" (Нижнекамск, 2005); 6-ая Международная конференция молодых ученых и студентов (Самара, 2005); Международная научно-практическая конференция "Инфокоммуникационные технологии глобального информационного общества" (Казань,2005); Региональная научно-методическая конференция "Информационная культура в системе подготовки будущего инженера" (Нижнекамск, 2006); Всероссийский семинар "Ситуационные исследования" (Казань, 2006); Региональная научно-техническая конференция по вопросам информатики, вычислительной техники и информационной безопасности (Казань, 2006); Региональная научно-практическая конференция "Наука и профессиональное образование" (Нижнекамск, 2007); 9-ый Международный семинар "Дискретная математика и ее приложения" (Москва, 2007); Всероссийская научная конференция студентов, аспирантов и молодых ученых "Наука, технологии, инновации" (Новосибирск, 2007); Республиканский научный семинар "Методы моделирования" при КГТУ им. А.Н. Туполева (Казань, 2004-2008).
Содержание работы опубликовано в 29 работах, включая^3 статьи [41-43], опубликованные в изданиях, входящих в перечень ВАК, 16 статей [44-59] в других изданиях, 9 тезисов [60-68] докладов и одну работу [69], зарегистрированную в отраслевом, фонде алгоритмов и программ.
Структура и объем диссертации.
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения.
В первой главе "Связь цепей Маркова, вероятностных автоматов и полиномиальных функций в конечном поле" дан обзор результатов, определяющих связь ЦМ, вероятностных автоматов и полиномиальных моделей над полем GF(2"). Вводятся известные понятия, теоремы и модели, необходимые для изложения решаемых задач. Уточняется постановка задач.
Во второй главе "Методы представления случайных последовательностей полиномиальными функциями над конечным полем" решаются задачи Г-3 диссертационной работы.
В разделе 2.1 "Представление стохастических матриц полиномиальными функциями над полем GF(2") с учетом точности представления элементов матриц" предложен метод представления- СМ с двоично-рациональными элементами полиномиальными функциями над полем GF(2"). Метод основан на предложенных трех алгоритмах двоично-рационального разложения СМ на комбинацию СБМ и ИВ. Получены оценки порядка поля GF(2") в зависимости от точности представления элементов СМ. Доказаны теоремы, определяющие оценки вычислительной сложности (ВС) и размера / ИВ для предложенных алгоритмов.
В разделе 2.2 "Представление расширенных цепей Маркова, над полем GF(2")" решены задачи синтеза и анализа модели расширенных цепей Маркова над полем GF(2"). Доказана теорема, обосновывающая алгоритм вычисления закона РЦМ по заданной СМ исходной простой ЦМ; определены свойства структуры матрицы, РЦМ. Предложен метод представления заданного стохастического закона РЦМ в определенную полиномиальную функцию над полем GF(2"). Предложены полиномиальные модели РЦМ. Определены оценки размера ИВ, получаемого при разложении матрицы РЦМ на множество СБМ и ИВ, исходя из результатов раздела 2.1. Получены оценки порядка поля GF(2").
В разделе 2.3 "Моделирование случайных последовательностей минимальными полиномами над конечным полем по заданной стохастической матрице" предложен обоснованный доказанной теоремой метод моделирования случайных последовательностей из класса неоднородных ЦМ над полем GF(gc), где qc>2- простое число. Предлагаемый метод позволяет по заданной матрице Р и фиксированной длине СП получать семейство реализаций СП на основе минимальных полиномовДх) над полем GF(qc).
Третья глава "Методы анализа полиномиальных функций, моделирующих случайные последовательности в конечном поле", состоит из двух разделов, в которых исследуются: свойства полиномиальных нелинейных динамических моделей преобразователей ЦМ и функций ЦМ и свойства линейной сложности марковских последовательностей (решаются задачи 4, 5 диссертационной
работы).
В разделе 3.1 "Анализ нелинейных моделей преобразователей случайных последовательностей над полем GF(2") на основе стохастических матриц" решена задача анализа полиномиальных нелинейных динамических моделей (ПНДМ) над полем GF(2"), порождающих случайные последовательности (СП) из класса функций конечных однородных ЦМ. Доказаны теоремы, обосновывающие аналитическое определение характеристик СП стохастических векторов, характеризующих асимптотику распределений вероятностей символов СП. Для четырех последовательно усложняемых ПНДМ, описывающих классы СП, определены их полиномиальные функции над полем GF(2") и структурные схемы.
В разделе 3.2 "Статистический анализ линейной сложности регулярных цепей Маркова" предложен метод статистического анализа однородных простых и сложных ЦМ по критерию ЛС (с использованием результатов раздела 2.3). Определены статистические критерии нахождения необходимых для исследования ЛС длин реализаций МП при заданной точности представления СМ, рассмотрены их отличия и особенности. Показана взаимосвязь ЛС и энтропии МП: определены оценки математического ожидания и дисперсии линейной сложности МП, моделируемых по заданным матрице Р и энтропии Н(Р); определены оценки математического ожидания и дисперсии линейной сложности, характеризующие подклассы МП с определенной величиной Н(Р); определен профиль ЛС МП.
В четвертой главе "Комплекс методик и программ для решения задач представления и анализа полиномиальных функций" описывается разработанный комплекс методик и программ, реализующий методы и алгоритмы, предложенные в диссертации. Методики задают последовательность шагов построения полиномиальных моделей и моделирования на их основе СП с заданными свойствами; позволяют повысить эффективность полиномиальных моделей за счет уменьшение ВС алгоритмов, повышения точности полиномиальных моделей и уменьшения порядка конечного поля с учетом структуры и точности задания элементов СМ. Комплекс позволяет решать следующие задачи: преобразование закона цепи Маркова в полиномиальную модель с использованием двоично-рационального разложения СМ и представление марковских функций полиномиальными моделями; тестирование предложенных полиномиальных моделей; получение закона расширенной цепи Маркова; исследование характеристик марковских и псевдомарковских циклических последовательностей с помощью алгоритма Берлекэмпа-Месси.
В заключении сформулированы основные результаты диссертационной работы.
Диссертация выполнена на кафедре компьютерных систем Казанского государственного технического университета им. А.Н. Туполева.
Базовые полиномиальные модели для моделирования цепей Маркова и их функций в поле GF(2")
В диссертационной работе, одной из решаемых задач является задача анализа полиномиальной нелинейной модели преобразователя случайных последовательностей, состоящая в определении требуемых характеристик СП при заданном полиномиальном описании этой модели. Задача является обратной к задаче, решаемой в [33]. Основными определяемыми вероятностными характеристиками являются стохастические векторы, описывающие асимптотику распределений вероятностей значений СП.
Связь цепей Маркова, вероятностных автоматов и полиномиальных функций над полем GF(2") определяется на_ основе представления СМ Р размера тхт линейной стохастической комбинацией множества СБМ и ИВ вида [40] Р-Т ЯаВ, (1-2) где / т2 - т + 1 (для минимаксного алгоритма); qa - элементы ИВ q, а = 0,1-1; B = (b1}), i,j = 0,т-\ - стохастическая булева матрица (СБМ) квадратная матрица размера тхт, у которой элементы Ьч є {0; 1} и на каждой /-ой строке существует только один элемент Ьц = 1. Размер ИВ зависит от алгоритма разложения и определяет комбинационную сложность соответствующего автомата, представленного в некотором логическом базисе (сложность автоматных моделей марковских функций и случайных конечноавтоматных последовательностей, представленных над GF(2")).
В известных полиномиальных моделях, основанных на использовании полиномиальных функций [32, 33] гг - от одной переменной g{y) = J aj- y, гj- = 2" -1, аУ , у є GF(2" ) (1.3) »=0 - от двух переменных /(x,9) = XlX/)xV / =2" -l, 2") (1-4) /=0у=0 минимальный порядок поля GF(2") определяется из условия / 2".
Пусть величина U - дискретная случайная величина (ДСВ), принимающая конечное число значений х0з ..., M с вероятностями из ИВ q = {q,} размера /,
Теорема 1.3 [32, 33]. Существуют такие ДСВ U и функция Дх, q) (1.4) со случайным начальным значением и коэффициентами а\р є G, что U может быть преобразована функцией Дх, q) в заданную ЦМ вида (1.1). Минимальный порядок поля GF(2") выбирается из условия 2" I. и X1 —т- Ах, ч) 2 ч. Рис. 1.3. Структурная схема модели (1.5) Теорема 1.3 обосновывает полиномиальную модель [32] (U;A ,q)), (1.5) где U - ДСВ со множеством значений {х,} с вероятностями из ИВ q ; Дх, q) функция (1.4) со множеством {х,} значений переменной х и множеством (} значений переменной q для моделирования ЦМ в поле GF(2"), 1 = 0,1-1, j = 0,т-1. На рис. 1.3 представлена структурная схема полиномиальной модели (1.5). Теорема определяет связь порядка поля с размерами матрицы Р. Связь порядка поля GF(2") со структурой и точностью представления матриц Р для (1.5) является малоисследованной задачей (например, исследуемые в главе
2 разреженные матрицы РЦМ). Теорема 1.4 (анализа) [32,33]. Для системы (1.5) и вектора щ последовательность вычисленных значений полинома fix, q) является реализацией простой однородной ЦМ с множеством состояний {qj}, описываемой матрицей Р, элементы которой однозначно определяются ИВ q и функцией J{x, q).
Разобьем множество состояний S на непересекающиеся подмножества Со, ..., Ch_x; \JCj=S; СаПС, = 0, аф], a,j = 0,hs-l. Рассмотрим процесс Yt = { yj }, і - 0, т -1, с hs состояниями, определяемый условием yf =J, если в момент времени t ЦМ находится в каком-либо состоянии st подмножества Q. Процесс Yt называется функцией конечной простой ЦМ [13]. Теорема 1.5 [33]. Последовательность состояний процесса {Yt} представляется последовательностью значений суперпозиции двух полиномов g(y) и Дх, q) вида у/ = gxf над полем GF(2"), где п - наименьшее целое, удовлетворяющее условию 2" I, I т2 - т + 1. Теорема 1.5 устанавливает, что функцию ЦМ вида {Yt} можно задать системой (U,yr = gxf,lT0). (1.6) Система (1.6) является полиномиальной моделью функции ЦМ вида {7,} [33]. На рис. 1.4 представлена структурная схема модели (1.6) [33]. Рис. 1.4. Структурная схема модели (1.6) 1.3. О задаче анализа цепей Маркова по критерию линейной сложности В данной работе предлагается применять критерий линейной сложности для решения следующих задач, связанных с моделированием цепей Маркова в конечном поле: - статистический анализ случайных последовательностей, являющихся реализациями ЦМ, по критерию линейной сложности; - представление закона ЦМ минимальным полиномом над конечным полем: і) - анализ влияния энтропии матриц на. линейную сложность реализаций ЦМ. " Понятие "линейная сложность" (ЛС) [6, 188] связано с понятием линейных рекуррентных последовательностей над конечным полем. Одной из проблемных задач исследования ЛС является разработка методов повышения ЛС периодических последовательностей. Аппарат исследования псевдослучайных и случайных последовательностей, основанный на критерии ЛС, используется в следующих областях: - в моделировании для исследования качества случайных чисел [133]; - применение алгоритма Берлекэмпа "решения ключевого уравнения над произвольным полем" для кодирования информации [189]; - тестирование работоспособности цифровых схем [24]; - тестирования качества поточных шифров и исследование аналитической сложности последовательностей псевдослучайных чисел в криптологии [6].
Линейная сложность (линейный размах) последовательности является одной из аналитических мер качества последовательностей (характеризует сложность ее аналитического строения) ч [6], которая определяет длину минимальной рекурренты (минимальную степень характеристического полинома [6]), задающей регистр сдвига с линейной обратной связью (ЛРС), способный сгенерировать данную последовательность. Любая последовательность, которую можно сгенерировать конечным автоматом над конечным полем, является линейной рекурентной последовательностью [6] и имеет конечную ЛС [188]. Алгоритмом вычисления ЛС для заданной последовательности в конечном поле и определения вида характеристического полинома последовательности является алгоритм Берлекэмпа-Месси (АБМ) [190,191]. Расширение данного алгоритма для алгебраической системы "кольцо" выполнено в работе [192].
Если элементы, образующие период последовательности, выбираются случайно, то степень минимального многочлена такой последовательности близка к величине ее периода [6]. Большое значение ЛС последовательности означает, что требуется более длинная подпоследовательность для выявления периода всей последовательности. Большое значение ЛС является необходимым, но не достаточным условием качества последовательности [193, 194]. В работе [195] демонстрируется, что последовательности, имеющие большое значение ЛС при представлении элементов в поле GF(2), могут иметь малое значение ЛС в поле GF(gc), где qc - простое число. Известен подход повышения ЛС последовательностей, основанный на применении функций усложнения [6, 196]. В [196] приводятся результаты по применению алгоритмов нахождения ЛС для анализа генераторов псевдослучайных чисел, имеющих сложную аналитическую структуру.
Подход разложения матриц, основанный на методе минимакса
Алгоритм минимакса Приведем описание алгоритма 1 [4]. На каждом цикле алгоритма 1, до тех пор, пока матрица Р не станет нулевой, осуществляется выбор по строкам максимальных элементов /?/,- матрицы Р, i,j = 0,т-\, задающих координаты текущей СБМ. Минимальное значение из выбранных элементов /?/,-, вычитаемое из BCQxpij, задает элемент ИВ.
Пусть d - накопленная к текущему шагу сумма минимаксных элементов. Матрица Р будет полностью разложена в (2.1), если переменная d станет равной единице. СБМ В = {Ьі}, і = 0,т -1, представлена вторым способом. Исходные данные: матрица Р. Результаты вычислений: число /; ИВ q размера /; множество {Р }, с = 0,/-1. Для алгоритма 1 известны следующие оценки размера / ИВ: 1) 1 / т2 - т + 1 [4, 128]; (2.2) т-\ 2) max о-,- 1 Тст{-т + \ [154,155], (2.3) 0 / /и-1 .„ если 3p,j = 0, /,у = 0,/?/-1, где сг,- - число ненулевых элементов /-ой строки матрицы Р. Такое же количество СБМ будет во множестве {Р(с)} после выполнения алгоритма 1.
Вначале ИВ q и множество {Р } являются пустыми. 1. Вычислить d = 0 и / = 0. 2. Для каждой /-ой строки, / = 0,тп -1, вычислить bt = max ри. 0 / ш-1 J 3. Вычислить минимаксный элемент MinMax= min pih . Поиск 0 , ш-1 минимаксного элемента позволяет получить ИВ, элементы которого упорядочены в порядке невозрастания значений. 4. Вычислить d=d +MinMax и добавить в ИВ q новый элемент qi = MinMax. 5. Для V/ = 0,7W-1 вычислить pib = pib -MinMax. 6. Добавить СБМ В во множество {Р }. 7. Изменить 1:1 = 1+1. 8. Если d 1, то переход к шагу 2; иначе выход из алгоритма 1. Предложение 2.1. Вычислительная сложность алгоритма 1 равна 0(рг4). Доказательство. Рассмотрим ВС алгоритма 1 по шагам. 1. Инициализация переменных d = О и / = 0 (две операции). 2. Нахождение максимальных элементов по т строкам - т2 сравнений и т присвоений. 3. Нахождение MinMax (минимума из максимальных элементов) - т операций сравнения и одна операция присвоения. 4. d = d + MinMax и qi= MinMax - две операции присвоения. 5. Вычитание MinMax из максимальных по строкам элементов - т вычитаний. 6. Добавление матрицы В во множество {Р } - т присвоений. 7./ = /+1- одно присвоение. 8. Проверка условия выхода из алгоритма 1 - одно сравнение. В худшем случае потребуется т -т + \ [4, 128] повторений шагов 2-8.
Таким образом, получаем, что 2 + {т +т + т + 1+т+1+т+ 4)(т --т + 1) = 2 + (т2 + 4т + 6){т2-т + \) = т4 + Ътъ + Ът2-2m + S. То есть ВС алгоритма 1 равна 0(т ). Что и требовалось доказать. СБМ В будем называть уникальной, если на текущем шаге некоторого алгоритма, выполняющего разложение (2.1), матрица В {Р }. Покажем, что СБМ, получаемые в алгоритме 1, не требуется сравнивать на уникальность с ранее найденными СБМ.
Замечание 2.2. В разложении (2.1) матрицы Р по алгоритму 1 каждая из СБМ уникальна. Доказательство. Координаты элементов pl b , i = 0,m-l, матрицы Р задают позиции единичных элементов в СБМ В . При выполнении операции pih = pib —MinMax для V/ = 0,т -1 хотя бы один из элементов pib
станет равным нулю. Элементы матрицы Р, ставшие равные нулю на предыдущих циклах алгоритма 1 (шаги 1-8 из предложения 2.1), не будут участвовать в последующих циклах формирования множества {Р с)}. То есть каждая из найденных СБМ уникальна. Что и требовалось доказать.
Из данного замечания следует, что для алгоритма 1 размер / ИВ не сокращается при объединении одинаковых СБМ. Пример 2.1. По алгоритму 1 выполним разложение (2.1) матрицы . Результаты вычислений представим в таблице 2.1. Пусть p = 2/8 1/8 5/8 4/8 2/8 2/8 5/8 1/8 2/8 максимальные по строкам элементы матрицы Р подчеркиваются одной линией, а минимальный элемент из максимальных по строкам - двойной.
Для выполнения алгоритмов второго подхода элементы матрицы Р необходимо привести к одному знаменателю. Для этого:
1) вначале элементы ру 0 (i,j = 0,т -1) матрицы Р с заданной точностью є = 112ь приводятся к обыкновенной дроби;
2) затем находится общий знаменатель элементов как наименьшее общее кратное от всех элементов/?/, 0 матрицы Р. Элементы pij 0 матрицы Р = (р,у), Ре Р (т, b), i,j = 0,т -1, приведенные к виду ру = ау/2 , а =0,2Ь, можно хранить не в виде вещественных чисел диапазона от 0 до 1, а в виде целых положительных чисел ау диапазона от 0 до 2 - числителей элементов исходной матрицы Р. Оперирование целыми числами ау позволяет исключить округления, аналогичные возникающим в алгоритме 1 при вычитании из элементов ру минимаксных элементов (шаг 5 алгоритма 1). Алгоритм 2 Формализуем метод, описанный в [3], в виде алгоритма 2.
Получение стохастической матрицы расширенной цепи Маркова
Пусть задана последовательность состояний Sj\,sj2,... простой однородной ЦМ с конечным множеством состояний S = {Sj} и стохастической матрицейР = (pij)размератхт, i,j = 0,m-l.
Образуем из этой исходной цепи новую, расширенную [93] цепь Маркова следующим образом [93]. Составим всевозможные цепочки символов 5/ є S длины г = v + к, г 2, v 1, к О, j = 0,т -1, имеющие вид (sy h sj2, ..., sJV, 5/ , ..., Sjv+к). Смежные цепочки содержат к = г- v общих символов и v ("величина сдвига") отличающихся символов. Предположим, что исходная цепь за 2v + к -1 шагов последовательно ПереХОДИТ ИЗ НеКОТОрОГО СОСТОЯНИЯ Sji В 5/2, Затем ИЗ 5/2 В 5/з, ..., ИЗ 5/(2vfK-l) в Sj(2v+Ky Смежные цепочки длины г будем рассматривать как один шаг перехода нового процесса ИЗ СОСТОЯНИЯ ($) ь ..., Sj у, Sj v+i, ..., Sj vt-к)
В СОСТОЯНИе (Sj vt-Ъ —tSj 2vt Sj2v+b Sj2V K) Этот новый расширенный процесс (расширенная цепь Маркова) является ЦМ [93] с пҐк состояниями (цепочки символов 5/ длины г, j = 0,т-\у, обозначим их символами А{, і = 0,mv+K -1. Состояния РИМ далее будем считать упорядоченными лексикографически: (50) ...,5os So), (S0, ..., So, Si), ..., (So, ..., 50, Sm.\), (So, ..., SU So), (So, ..., Si, SX), ..., (S0, ...,5b5m.i), \Sm-\ , Sm-\, SQ), 5 -1, ..., 5 -1, S\j, ..., (5OT_i, ..., Sm,\, Sm.\). Образование состояний А,- РЦМ из цепочек символов s,- є S, і = 0, т -1, иллюстрируют рис.2.2 (СОСТОЯНИЯ А\ = (5Ь 52, 53), А2 = (53, 54, 55), А3 = (s5, 5б, 57), ...) и рис.2.3 (СОСТОЯНИЯ Ai=(su 52, 53), А2 = (52, 53, 54), А3 = (s3, 54, 55), Аг Рис.2.2. Цепочки РЦМ при v = 2, к = 1 Рис. 2.3. Цепочки РЦМ при v = 1, к = 2 Обозначим через О стохастическую матрицу размера ггҐкх-пҐк этой РЦМ.
Для решения рассматриваемой задачи анализа определим матрицу О РЦМ через матрицу Р исходной ЦМ при v 2, к 2. Для частного случая v = к = 1 эта задача решена в [93].
Определение "промежуточной"матрицы переходов Р у
Получение матрицы О РЦМ осуществим на основе понятия "промежуточной" стохастической матрицы. Пусть Рщ есть Р по определению. Определим матрицу Р через матрицу Р по следующей схеме, У 1.
1. Зададим квадратную матрицу PQ) размера mJxmJ. 2. Заполняем матрицу PQ) следующим образом (рис. 2.4). т} -т $ Строка№0: р0оpQX ... pQ(m.i) т Строка №1 /гГ 0: 0 РюРп -..РКт-1)0 P(m-i)0 Р(т-1)ї PCw-lXw-DP т} - 2т 0, Строка №»i-l: 0 mJ -т т -т Рис. 2.4. Механизм получения первых т строк матрицы Р 3. Продолжаем эту процедуру, двигаясь вправо вниз, используя в циклическом порядке строки матрицы Р: строка №0, строка №1, ..., строка №?и-1, строка №0, строка №1, ... до тех пор, пока элементы Р(т-\уо,Р(т-\)\, , Р(т i)(m-i) не займут места в столбцах с номерами »i7-m, mJ — т + I, ..., mJ \ соответственно. Таким образом, строятся первые т J строк матрицы Р .
4. Последующие строки являются »1-1 кратным повторением построенных первых т J l строк матрицы Р , гдеу = v + к. пҐк ггҐ\ Р(у+к)= Р(г) будем использовать для построения матрицы О РЦМ в качестве стохастической "промежуточной" матрицы размера т т \ элементы которой были определены вышеописанным способом. В дальнейшем промежуточную матрицу Р(Г) будем обозначать как W= (Wjj), i,j = 0,тґ -1.
Замечание 2.3. Матрицу W можно построить и с помощью алгебры матриц. Пусть дана матрица Р = (pij), i,j = 0,т -1. Тогда определим матрицу W как где - Е и т - единичные матрица и вектор-столбец размеров тг 2 хтг 2 и т соответственно; - - символ операции кронекерово (тензорного) произведения [186] матриц; -С = \ВоВ\ ... Вт.\\ - матрица размера т т2, являющаяся последовательной если а = / конкатенацией матриц Bt = (b ), i,j,a = Q,m -1, где b$ =-1 аг J 0, еслиа і Пример 2.10. Пусть Р = Р = Для г = 2 (v = к = 1) получим матрицу PQ), представленную на рис.2.6.
Отметим следующие особенности структуры матрицы W: а) ее размеры равны тгхтг; б) элементы каждой /-ой строки матрицы Р, i = 0,m-l, последовательно занимают т столбцов матрицы W, а все элементы Р располагаются в т2 столбцах матрицы W; в) число отличных блоков строк (матрица Е 8 С), последовательно, сверху вниз образующих матрицу W, равно т, а каждый из блоков строк состоит из mr 1 строк; .г-\ г) в каждом блоке из т строк матрицы W располагается mrlm = т г-2 М. повторений матрицы С, а общее число матриц С в матрице Травно пі д) содержимое каждой /-ой строки матрицы W, i = 0,mr — 1, повторяется через тгЛ строк в строках под номерами / + d-mrA, d = \,т -1; е) в каждой / -ой строке матрицы W, i = 0,mr -І, по координатам (/;//// modmr + d), d = 0,т-1, последовательно располагаются т ненулевых элементов, где mod - операция получения целочисленного остатка от деления одного числа на другое;
Полиномиальные нелинейные динамические модели, порождающие функции цепей Маркова. Вероятностные характеристики моделей
Вычислим матрицу W. Элементы wfj матрицы W2 равны w = Xwfewac k,c = 0,mr -1. Если переменная с равна у + d-m2, d = 0,тг -1,то для каждого элемента w$ каждое слагаемое суммы будет равно нулю из-за равенства нулю ЭЛеМеНТОВ Wac, = 0,777 -1. То ЄСТЬ ЗЛЄМЄНТЬІ МЭТрИЦЫ W" В СТОЛбЦЭХ С номерамиу + d-m2 также остаются раными нулю.
Тогда, при возведении матрицы W в степень а 2, в матрице Wa будут нулевые столбцы. Следовательно, нельзя попасть из некоторого начального состояния РЦМ в любое другое состояние за конечное число шагов. То есть матрица Q= Wv не является регулярной, а соответствующая ей РЦМ не является эргодической. Утверждение доказано.
Утверждение 2.4. Если РЦМ, заданная матрицей О размера тг хтг:) с длиной цепочек г = v + тс, образована матрицей Р с одинаковыми строками, то данная цепь является цепью Маркова-Брунса [96].
Доказательство. Это утверждение следует из способа построения цепи Маркова-Брунса [96]. Пусть задан процесс выпадения событий из множества S, \S\ = т, появление которых не зависит от предыстории. Вероятность появления следующих друг за другом двух событий А и В этого процесса равна Р{АВ) = Р(А)Р(В), А є S,B є S. Зададим вероятности появления событий в виде вектора {pi), / = 0,777-1. Образуем из описанного процесса цепь Маркова с 7?7 состояниями. Матрица Р переходов состояний данной цепи состоит из строк, каждая из которых равна {/?,}, так как появление текущего события не зависит от предыдущего состояния.
Объединим цепочки из / состояний рассматриваемого процесса в новые СОСТОЯНИЯ, ГДЄ r = V + К. ЭТОТ НОВЫЙ ПрОЦеСС ЯВЛЯеТСЯ РЦМ С 777Г состояниями и матрицей переходов Q=WV размера тгх?пг. В то же время, построенный укрупненный процесс является цепью Маркова-Брунса [96]. Утверждение доказано.
Утверждение 2.5. Если у РЦМ, заданной матрицей Q размера тг тг, число общих символов в цепочках к = 1, а длина цепочек равна г = к + v, то данная цепь является г-сложной цепью Маркова [96]. Таким образом, из утверждений 2.4 и 2.5 видно, что: - РЦМ, цепи Маркова-Брунса и / -связные сложные цепи обладают общими характеристиками; - цепи Маркова-Брунса являются частным случаем РЦМ, если стохастическая матрица Q РЦМ образована из матрицы простой ЦМ, содержащей одинаковые строки. Алгоритм вычисления матрицы О РЦМ по матрице Р исходной ЦМ. На основе приведенных выше свойств структур матриц W, О и теоремы 2.11 сформулируем алгоритм получения матрицы О. Исходные данные: матрица Р размера т ХАИ; переменные к, v, r = K+v 2. Результат вычислений: матрица О размера тг тг. Шаг 1. Вычисляются ненулевые элементы матрицы W по формуле (2.7), вытекающей из свойств а) - и) структуры матрицы W (формула (2.7) - третий способ получения матрицы W): WUl.mmodm +d)=Po »).d i = nf -1 = 0 Ю-1 С2-7) где і - текущий номер строки матрицы W, d - текущий номер столбца матрицы Р. Шаг 2. Вычисляется соотношение (2.6). Модель генератора расширенной цепи Маркова на регистре сдвига Исходя из определения РЦМ последовательность состояний РЦМ можно получить по схеме (рис.2.9), где - блок 1 - генератор состояний [3] простой цепи Маркова (генератор цепи Маркова - ГЦМ) по заданным стохастической матрице Р размера т т и МНОЖеСТВу СОСТОЯНИЙ Sj Є S, j = 0,772 -1; - блок 2 является регистром сдвига (PC), формирующим цепочки из символов Sj є S длины г, и выдающим их в виде одного состояния А{ РЦМ, j = 0,/и -1, / = 0,тг -1; - сигнал "управление величиной сдвига v" задает количество v отличающихся символов Sj между двумя соседними состояниями РЦМ; между моментами считывания состояний РЦМ происходит v тактов сдвига СОДерЖИМОГО PC С ОДНОВремеННЫМ Добавлением В PC V НОВЫХ СОСТОЯНИЙ Sj ГЦМ,у = 0,яі-1; - сигнал "синхронизация считывания состояний А", і = 0,т -1, подается при накоплении в PC цепочки из поступивших от ГЦМ г символов Sj, j = Q,m -1, отличающейся от предыдущего состояния РЦМ на v символов.
Синхронизация считывания состояний/!,
Рассматриваемой задачей синтеза является построение полиномиальной модели над полем GF(2"), эквивалентной (по равенству законов получаемых РЦМ) изображенной на рис.2.9 схеме генератора РЦМ. Сопоставим схеме, представленной на рис.2.9, два других подхода представления РЦМ по заданной матрице О над полем GF(2"): с помощью построения имплицирующего вектора (ИВ) для ЦМ [3] и на основе получения определенного приведенного вероятностного автомата [227]. На основе этих двух подходов в работах [32, 33] были предложены полиномиальные модели над полем GF(2") для моделирования простых и сложных цепей Маркова. Покажем, каким образом на основе данных подходов можно представить РЦМ по заданной матрице О полиномиальными функциями над полем GF(2").
Решение этой задачи позволяет осуществлять: - расширение класса дискретных случайных процессов, получаемых на полиномиальных моделях; - определение свойств полиномиальной модели над GF(2H), порождающей заданный случайный процесс; подобная задача анализа полиномиальных моделей, порождающих функции ЦМ, решена в [41].
Похожие диссертации на Методы и алгоритмы построения и анализа полиномиальных функций над конечным полем на основе стохастических матриц
