Содержание к диссертации
Введение
ГЛАВА I. Базовые понятия и определения 17
1. Автоматные модели простой однородной цепи Маркова 17
2. Определения теории полей Галуа 20
3. Полиномиальная модель простой однородной цепи Маркова 25
4. Определения теории графов 29
5. Методы многомерного статистического анализа 30
ГЛАВА 2. Полиномиальное представление автоматных моделей марковских функций над полем Галуа 38
1. Определения вероятностных автоматных моделей случайных процессов из класса марковских функций 39
2. Полиномиальные модели и структурные схемы генераторов марковских функций над полем Галуа 43
3. Полиномиальное представление конечноавтоматных случайных последовательностей над полем Галуа 52
4. Заключение 59
ГЛАВА 3. Автоматное моделирование случайных процессов с последействием на основе эйлеровых стохастических матриц 60
1. Постановка задачи 61
2. Автоматная модель 64
3. Структурная схема автоматной модели 70
4. Реализация ррг -последовательности в конечных полях 71
5. Заключение 81
ГЛАВА 4. Построение схем умножения в составном поле вида GF(22) 83
1. Применение алгоритма Карацубы-Офмана для построения схемы умножения в составных полях вида GF((2k )4 )
2. Модификация алгоритма Карацубы-Офмана для построения схемы умножения в составных полях вида GF((2k)4) 89
3. Алгоритм построения составного поля вида GF((2 ) ), изоморфного полю вида
4. Построение схемы умножения в составном поле вида GF((22)2) 99
5. Построение схемы умножения в составном поле вида GF(((22)2)2) 104
6. Заключение 110
ГЛАВА 5. Комплекс прикладного профаммного обеспечения для реализации синтеза и анализа полиномиальных моделей генераторов марковских функций 114
1. Пакет программ, реализующий автоматные модели генераторов марковских функций 115
2. Пакет программ, реализующий полиномиальные модели генераторов марковских функций над полем GF(2n) 120
3. Методика статистического анализа генераторов марковских функций 123
4. Заключение 127
Заключение 128
Литература 130
Приложение I 144
Приложение II 153
- Полиномиальная модель простой однородной цепи Маркова
- Полиномиальные модели и структурные схемы генераторов марковских функций над полем Галуа
- Реализация ррг -последовательности в конечных полях
- Алгоритм построения составного поля вида GF((2 ) ), изоморфного полю вида
Полиномиальная модель простой однородной цепи Маркова
Цель ДА заключается в том, чтобы на основе измерения различных характеристик (признаков, параметров) объекта классифицировать его, то есть отнести к одной из нескольких групп (классов) некоторым оптимальным способом. Под оптимальным способом понимают обычно или минимум математического ожидания потерь, или минимум вероятности ложной классификации.
ДА используется в том случае, когда исследователь обладает так называемыми обучающими выборками (ОВ). На основе ОВ строится решающее правило (РП), позволяющее по результатам измерений параметров объекта указать группу, к которой он принадлежит. Число групп заранее известно, также известно, что объект заведомо принадлежит к определенной группе.
Для формализации проблемы классификации удобно интерпретировать многомерное наблюдение (/-мерный объект) как точку в /-мерном пространстве признаков. Совокупность объектов, относящихся к одному классу Dh образует «облако» в этом же пространстве. Для успешной классификации необходимо, чтобы: 1) «облако» из D/ в основном было сконцентрировано в некоторой области R/ пространства признаков; 2) в область Rj попала незначительная часть «облаков» объектов, соответствующих остальным классам. Построение РП можно рассматривать как задачу поиска к непересекающихся областей R; (/ = 1Д), удовлетворяющих приведенным выше условиям. Обычно переходят от вектора признаков, характеризующий объект, к линейной функции от них, дискриминантной функции (ДФ) - гиперплоскости, наилучшим образом разделяющей совокупность выборочных точек. ДА основывается на следующих предположениях: 1) измеряемые характеристики объекта имеют нормальное распределение; 2) дисперсии и ковариации наблюдаемых переменных в разных классах являются однородными (отличие между классами имеется только в средних значениях). В STATISTIC А 5.0 реализованы три метода дискриминантного анализа: стандартный, пошаговый включения и пошаговый исключения. РП строится на основе линейных ДФ, которые имеют вид: Таким образом, построение РП сводится к нахождению коэффициентов Ujfjy J = 1,/, /7 = ІД. Классифицируемый объект, которому соответствует вектор Xj, / = 1, N, относится к той группе, для которой значение fjfj, h = ],k, вычисляемое по значениям x h, максимально. В пошаговом методе модель строится последовательно. Для метода включения на каждом шаге оценивается вклад в ДФ не включенных в модель переменных. Переменная, дающая наибольший вклад, включается в модель, далее система переходит к следующему шагу. При пошаговом методе исключения в модель включаются все переменные, затем производится их последовательное исключение. После того как оценка РП по ОВ получена, встает вопрос о том, насколько хорошо она справляется с поставленной задачей классификации. При этом наиболее важной является оценка качества классификации объектов, которые не использовались в обучении. Для получения этой оценки имеющиеся исходные матрицы данных для каждого из классов разбиваются на две части - собственно ОВ и контрольную выборку (KB). После оценивания РП по ОВ с его помощью проводится классификация объектов из КВ. Получающиеся частоты ошибочных классификаций и являются соответствующими оценками (при делении их на объемы KB). Рекомендуется обычно деление исходных данных на ОВ и KB примерно на равные части. Точность оценок параметров РП можно в какой-то степени повысить, проведя после экзамена переоценку параметров РП уже на основе всех имеющихся данных. Иногда используется также оценка, основанная на подсчете частот ошибочных классификаций при применении РП на ОВ. Данная оценка будет смещенной и, как правило, заниженной. Тем не менее она может быть полезна, поскольку может служить мерой применимости РП данного типа в данной задаче классификации. Так как если иа материале обучения РП дает большие частоты ошибок, то классы либо вообще плохо разделимы при используемом наборе признаков, либо для решения данной задачи необходим другой вид РП, например, нужно ввести нелинейные преобразования признаков или обратиться к непараметрическому методу, кусочно-линейному правилу классификации и т.д. Объединяет различные процедуры, используемые для проведения классификации. В результате применения этих процедур исходная совокупность объектов разделяется на кластеры или группы (классы) схожих между собой объектов. Под кластером обычно понимают группу объектов, обладающую свойством плотности (плотность объектов внутри кластера выше, чем вне его), дисперсией, отделимостью от других кластеров, формой, размером. КА основывается на двух положениях: 1) в один кластер объединяются объекты, сходные между собой по определённым критериям (свойствам, признакам); 2) степень сходства у объектов, принадлежащих одному классу, должна быть больше, чем у объектов, относящихся к разным классам. В STATISTICA 5.0 реализованы следующие методы кластеризации: joining (tree clustering), &-means clustering, two-way joining.
Полиномиальные модели и структурные схемы генераторов марковских функций над полем Галуа
После получения информация о том, сколько дисперсии выделил каждый фактор, может быть решен вопрос о том, сколько факторов следует оставить. Это решение является произвольным. При решении данной задачи распространение получили два критерия; критерий Кайзера (Kaiser, 1960) и критерий каменистой осыпи (Cattell, 1966).
По критерию Кайзера отбираются только факторы, с собственными значениями, большими I. Это означает, что если фактор не выделяет дисперсию, эквивалентную, по крайней мере, дисперсии одной переменной, то он опускается.
Критерий каменистой осыпи является графическим методом. Собственные значения представляются в виде графика. Далее на графике находится такое место, где убывание собственных значений слева направо максимально замедляется. Предполагается, что справа от этой точки находится только «факториальная осыпь» - «осыпь» является геологическим термином, обозначающим обломки горных пород, скапливающиеся в нижней части скалистого склона.
Критерий Кайзера иногда сохраняет слишком много факторов, в то время как критерий каменистой осыпи иногда сохраняет слишком мало факторов. Поэтому обычно исследуется несколько решений с большим или меньшим числом факторов, и затем выбирается одно наиболее «осмысленное». В STATISTICA 5.0 реализованы метод главных компонент и методы, объединенные в группу, названную анализ главных факторов.
Анализ главных компонент - это метод преобразования данной последовательности наблюдаемых переменных в другую последовательность переменных. Процедура выделения главных компонент подобна вращению, максимизирующему дисперсию исходного пространства переменных. Цель вращения заключается в максимизации дисперсии (изменчивости) «новой» переменной (фактора) и минимизации разброса вокруг нее.
При вращении факторной структуры факторные нагрузки могут быть изображены в виде диаграммы рассеяния, на которой каждая переменная представлена точкой. Оси могут быть повернуты в любом направлении без изменения относительного положения точек. При этом действительные координаты точек, то есть факторные нагрузки, изменяются. Существуют различные методы вращения с целью получение факторов, с высокими нагрузками для одних переменных и низкими - для других. В STATISTICA 5.0 реализованы следующие методы вращения: варимакс, биквартимакс, кварти макс и эквимакс.
Метод главных факторов является наиболее ранним методом факторного анализа, в котором методика анализа главных компонент используется применительно к редуцированной корреляционной матрице, на главной диагонали которой располагают оценки общностей. В качестве оценки общности обычно используют квадрат множественного коэффициента корреляции между соответствующей переменной и совокупностью остальных переменных.
Основное различие метода главных факторов от метода главных компонент состоит в том, что в анализе главных компонент предполагается, что должна быть использована вся изменчивость переменных, тогда как в анализе главных факторов используется только изменчивость переменной, общая и для других переменных. В большинстве случаев эти два метода приводят к весьма близким результатам. Однако анализ главных компонент часто более предпочтителен как метод сокращения данных, в то время как анализ главных факторов лучше применять с целью определения структуры данных.
В данной главе рассматривается алгебраический подход к представлению автоматных моделей МФ на основе полиномов над полем Галуа. Предлагаются полиномиальные модели и структурные схемы генераторов, позволяющие моделировать над полем GF(2n) случайные процессы вида МФ из класса, порождаемого ABA с определенными ограничениями на функции перехода и выхода.
Представление вероятностных автоматных моделей на основе операций в полях Галуа привлекательно тем, что открывается возможность представлять преобразование случайных процессов алгебраическими выражениями (полиномами), что позволяет распараллеливать выполняемые вычисления и оперативно менять свойства моделируемых случайных процессов путем изменения коэффициентов полиномов над конечным полем.
Далее в этой работе функции ЦМ будем рассматривать как случайные процессы, получаемые на выходе вероятностных моделей автоматного типа [1-2, 23, 109-110]. Под случайным процессом будем понимать конечно-значный случайный процесс с дискретным неотрицательным временем, в результате протекания которого формируется конечнозначная случайная последовательность.
Подход к построению моделей основан на ПМ (1.8) конечной простой однородной ЦМ [72-73, 84, III]. Основные результаты, приведенные в данной главе, опубликованы в [77-78].
Реализация ррг -последовательности в конечных полях
В главах 2 и 3 были предложены ПМ генераторов случайных процессов из класса МФ, основанные на суперпозиции ПФ вида (1.6) и (1.7). Реализация ПФ (1.6) и (1.7) в виде систолических структур представлена на рис. 1.5 и 1.4. В рассмотренных структурах базовым является блок, выполняющий выражение вида af3+y. Таким образом, для реализации предложенных ПМ необходимы схемы, выполняющие операции сложения и умножения. Основную сложность при реализации вычислений в полях Галуа представляет операция умножения. Это связано с тем, что для реализации большинства схем умножения в поле GF{2") с параллельной архитекту-рой разрядов требуется операций умножения и и — 1 операций сложения в поле GF(2) [70], а для реализации схемы сложения в поле GF(2") всего лишь п операций сложения в поле GF(2).
Архитектура схемы умножения важна также потому, что такие функции как инверсия и возведение в степень, основаны на операции умножения. Кроме того, поля Галуа широко используются в таких приложениях, как криптография [123, 130, 131], генерирование псевдослучайных чисел [124], системы связи [125] и т.д. Это объясняет интерес к исследованиям по разработке архитектур схем умножения, особенно тех, которые могут быть эффективно реализованы в однородных структурах, что отражено в многочисленных публикациях [45-49, 62-71].
Схемы умножения обычно классифицируют по архитектуре разрядов: с последовательной или параллельной архитектурой. Схемы умножения с параллельной архитектурой разрядов выполняют умножение с меньшей задержкой, что делает такую архитектуру предпочтительной для многих приложений. Однако, использование схем умножения с параллельной архитектурой разрядов ведет к более высоким затратам аппаратных средств.
Вычислительная сложность, выраженная в количестве двухвходовых элементов, может служить оценкой [71] площади кристалла необходимой при реализации в виде интегральных схем. Поэтому привлекательной является идея использования параллельной архитектуры разрядов схемы умножения с минимальным числом реализующих ее двухвходовых элементов. В ряде работ были предложены архитектуры схем умножения со сложностью менее чем и2. Наиболее перспективными из известных алгоритмов являются алгоритм Карацубы-Офмана (АКО) [126] и его модификация [70].
В данной главе решается задача разработки новой параллельной архитектуры схем умножения, имеющей, по сравнению с известными подходами, меньшую вычислительную сложность [88, 115]. В 1-2 рассмотрена основная идея АКО и его модификации. Приведены оценки вычислительной сложности и задержки получаемых с помощью данных подходов схем умножения. В 3 предложен алгоритм по строения составного поля вида GF((2 ) ), изоморфного полю вида GF(22k). Предложенный алгоритм используется при построении схем умножения в 4-5. В 4 предложена методика построения схемы умноже ния в поле вида GF(2 ), сформулировано утверждение о существовании такой схемы умножения, даны оценки ее вычислительной сложности и задержки, построена логическая схема. В 5 предложена методика построе 2з ния схемы умножения в поле вида GF(2 ), на основании схемы умножения, описанной в 4. Сформулировано утверждение о существовании, даны оценки вычислительной сложности и задержки, построена логическая схема. В 6 проводится сравнение предлагаемой методики построения схем умножения с существующими подходами, формулируются основные результаты, полученные в главе 4. В операцию (4.1) включены два шага: 1. Обыкновенное полиномиальное умножение (х), 2. Сокращение по модулю р{х) (mod). Для совершения этих шагов требуется выполнение действий с коэффициентами, которые являются элементами подполя GF(2 ). Для умно жения коэффициентов at х6(. требуется, по крайней мере [70], к двухвхо довых элементов AND и к1-\ двухвходовых сумматоров по модулю 2 (XOR), а суммирование коэффициентов а,+6;- может быть реализовано всего лишь с помощью /г двухвходовых элементов XOR. Так как умножение коэффициентов обладает большей вычислительной сложностью, чем сложение, в [49] АКО применен к первому шагу уравнения (4.1). Этот алгоритм выполняет полиномиальное умножение с сокращением числа умножений за счет повышения числа сложений. Сложность алгоритма описывается леммами 4.1 и 4.2. Лемма 4.1 [70]. Два произвольных многочлена от одной переменной со степенью меньшей или равной трем и с коэффициентами, принадлежащими полю GF{2 ), могут быть перемножены посредством алгоритма Карацубы-Офмана со сложностью:
Алгоритм построения составного поля вида GF((2 ) ), изоморфного полю вида
При проектировании цифровых устройств ошибка, допущенная на начальных этапах проектирования и выявленная лишь при вводе устройства в эксплуатацию, может вызвать недопустимое увеличение необходимых для разработки экономических и временных затрат. Одним из способов не допустить подобной ситуации является построение программной модели, позволяющей оценить характеристики проектируемого устройства и провести его тестирование.
В данной главе описываются два разработанных пакета прикладных программ, позволяющих построить программные модели генераторов МФ. Также описана методика анализа задающих работу генераторов стохастических матриц и частотных характеристик формируемых последовательностей на основе методов многомерной математической статистики и программа, автоматизирующая формирование таблицы «Объект-признак», содержащей данные для многомерного статистического анализа.
В 1 описан пакет программ, реализующий модели ABA, последовательности выходных букв которых являются рассмотренными во второй главе случайными процессами из класса МФ. В 2 описан пакет программ, реализующий предложенные во второй главе ГТМ генераторов МФ над полем GF{2"). В 3 предложена методика анализа, позволяющая оценить характеристики формируемых случайных последовательностей и провести тестирование моделируемых генераторов, и описана программа, формирующая таблицу «Объект-признак». В 4 формулируются основные результаты, полученные в главе 5.
Во время построения предлагаемых во второй главе ПМ генераторов МФ ошибки могут быть допущены как при осуществлении перехода от автоматных моделей генераторов МФ к предлагаемым ПМ, так и при задании начальных параметров автоматных моделей генераторов МФ. Ошибки первого типа могут быть выявлены с помощью идентификации и сравнительного анализа характеристик последовательностей, получаемых с помощью ПМ и соответствующих им автоматных моделей генераторов МФ. Ошибки второго типа, при существовании последовательностей с желаемыми характеристиками и выбираемыми в качестве эталона, также могут быть выявлены с помощью сравнительного анализа и идентификации.
Описываемый в данном параграфе разработанный пакет программ реализует автоматные модели генераторов случайных процессов из класса МФ. С его помощью формируются последовательности, играющие роль «эталонов» при анализе характеристик последовательностей, формируемых ПМ генераторов МФ над полем GF{2n).
Сравнение и анализ характеристик последовательностей, формируемых автоматными и ПМ, позволяет при проектировании ПМ генераторов МФ над полем GF(2n) обнаружить ошибки, допущенные при переходе от автоматных к ПМ, которые привели к изменению частотных характеристик формируемых последовательностей. Данный пакет программ удобен при разработке тем, что дает возможность коррекции характеристик формируемых случайных последовательностей в зависимости от нужд разработчика. Входные параметры, задающие работу автоматных моделей, представляются в виде стохастических векторов, матриц переходов и разбиения исходного множества на непересекающиеся подмножества, что дает разработчику возможность проследить зависимость характеристик формируемых последовательностей от набора входных параметров автоматной модели. Входные параметры ПМ представляют собой вектора и матрицы коэффициентов ПФ, являющиеся элементами конечных полей. Их интерпретация и анализ взаимосвязи с характеристиками формируемых последовательностей представляются более трудными. Описываемый комплекс программ реализован на языке Object Pascal. Первый пакет программ представляет собой набор модулей реализующих ABA А(4)-А(7) (2.2), (2.3), (2.5), (2.7) и модуль, позволяющий выполнить разложение вида (1.5) стохастической матрицы Р на множество простых матриц и стохастический вектор. Экранная форма данного модуля представлена на рис. 5.1. Взаимосвязь в программном комплексе между разработанными модулями осуществляется с помощью формируемых файлов. Вспомогательные модули выполняют предварительные вычисления и сохраняют их результат в указанные пользователем файлы. Полученные файлы используются при дальнейшей работе в модулях моделирующих работу генераторов МФ. Модуль, экранная форма которого представлена на рис. 5.1, может выполнить разложение, как стохастической матрицы, задающей вероятности переходов, так и стохастических матриц (2.4), (2.6), задающих вероятностные функции ju(zl s), ju(zlу). Модуль реализует метод разложения на простые матрицы, описанный в [23]. Размеры исходной матрицы задаются параметрами т и d. Значения элементов матрицы Р могут быть загружены из текстового файла с помощью кнопки рыть і, вызывающей диалог открытия файла, или введены пользователем в самом модуле. Введенные или измененные значения элементов матрицы Р могут быть сохранены в сохранения файла. Диалоги сохранения файлов вызываются также при нажатии на кнопки J2J , позволяющие задать имена и месторасположения файлов, в которые будут записаны результаты разложения стохастической матрицы Р. Пользователю предоставляется возможность выбора формата результата разложения: в виде стохастического вектора и набора простых матриц, или в виде стохастического вектора и матрицы переходов. Матрица переходов имеет размерность /их/, при этом значения 7-го столбца определяются на основеу -й простой матрицы.
Похожие диссертации на Полиномиальные модели генераторов марковских функций над полем GF(2+)
