Методы и алгоритмы построения и анализа полиномиальных функций над конечным полем на основе стохастических матриц

Размещено на http://www.allbest.ru/

22

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

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

МЕТОДЫ И АЛГОРИТМЫ ПОСТРОЕНИЯ И АНАЛИЗА ПОЛИНОМИАЛЬНЫХ ФУНКЦИЙ НАД КОНЕЧНЫМ ПОЛЕМ НА ОСНОВЕ СТОХАСТИЧЕСКИХ МАТРИЦ

Эминов Булат Фаридович

05.13.18 - Математическое моделирование,

численные методы и комплексы программ

Казань - 2008

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

им. А.Н. Туполева

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

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

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

профессор Аблаев Фарид Мансурович

доктор технических наук,

профессор Крашенинников Виктор Ростиславович

Ведущая организация: Новгородский государственный университет им. Ярослава Мудрого (г. Великий Новгород)

Защита состоится " 6" июня 2008 г. в 14 часов на заседании диссертационного совета Д 212.079.01 в Казанском государственном техническом университете им. А.Н. Туполева по адресу: 420111, г. Казань, ул. К.Маркса, 10.

С диссертацией можно ознакомиться в библиотеке Казанского государственного технического университета им. А.Н. Туполева.

Автореферет разослан "___" __________ 2008 г.

Ученый секретарь

диссертационного совета, П.Г. Данилаев

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

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

Актуальность работы. Одним из подходов моделирования цепей Маркова (ЦМ) и марковских функций является подход, использующий теорию конечных полей. Перспективность этого подхода определяется приложением функций конечных ЦМ, возрастающей сложностью вероятностных дискретных моделей и эффективностью арифметики конечных полей в задачах цифровой обработки информации. Аппарат конечных полей используется для решения задач синтеза вероятностных автоматов и генераторов случайных двоичных последовательностей, для моделирования случайных линейных зависимых процессов в конечном поле и некоторых типов ЦМ (Аблаев Ф.М., Бухараев Р.Г., Гавел Я., Кирьянов Б.Ф., Кознов Ф.В., Крашенинников В.Р., Кузнецов В.М., Латыпов Р.Х., Мансуров Р.М., Осмоловский С.А., Песошин В.А., Столов Е.Л., Taylor L.).

В работах Захарова В.М., Нурутдинова Ш.Р., Соколова С.Ю., Шалагина С.В. (2000-2006 г.г.) предложен подход моделирования дискретных случайных процессов на полиномиальных моделях, описываемых полиномиальными функциями над полем GF(2n). Полиномиальные функции рассматриваются как модели дискретных преобразователей цепей Маркова. Разработаны методы представления полиномиальными функциями над полем GF(2n) простых и сложных ЦМ и определенных функций однородных и неоднородных ЦМ. Задача представления решается как задача вычисления коэффициентов полиномов над полем GF(2n) на основе заданных стохастических матриц. Решена важная прикладная задача отображения полиномиальных моделей в однородные вычислительные среды, позволяющие реализовать параллельные алгоритмы вычисления и проводить потоковые преобразования над n-мерными векторами при моделировании дискретных случайных процессов. Однако, в этом направлении существуют недостаточно исследованные вопросы и нерешенные задачи, имеющие теоретическое и практическое значение.

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

Объект исследования. Модели и аналитические методы моделирования случайных последовательностей над конечным полем.

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

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

Цель работы: развитие полиномиальных моделей, аналитических методов и построение эффективных методик для моделирования цепей Маркова и их функций в конечном поле.

Решение общей научной задачи и достижение поставленной цели связано с решением следующих задач.

1. Разработка метода и алгоритмов представления стохастических матриц полиномиальными функциями над полем GF(2n). Определение оценок порядка поля GF(2n) с учетом точности задания элементов стохастических матриц.

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

3. Разработка метода представления неразложимых стохастических матриц с заданной точностью полиномами минимальной степени над конечным полем GF(qc) характеристики qc ? 2.

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

5. Статистический анализ цепей Маркова по критерию линейной сложности последовательностей. Исследование взаимосвязи энтропии неразложимых стохастических матриц с линейной сложностью реализаций цепей Маркова.

6. Разработка комплекса методик и программ, реализующих предлагаемые методы и алгоритмы.

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

Научная новизна работы и значимость результатов.

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

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

- Новый метод представления стохастических матриц с заданной точностью и моделирования случайных последовательностей из класса неоднородных цепей Маркова полиномами минимальной степени над полем GF(qc) характеристики qc ? 2. Доказана теорема, устанавливающая линейную связь между точностью задания стохастической матрицы и величиной минимальной степени полинома.

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

- Методика исследования однородных простых и сложных цепей Маркова на основе критерия линейной сложности. Сформулирован критерий нахождения длин реализаций марковских последовательностей при заданной точности представления матриц цепей Маркова. Определены стохастические зависимости линейной сложности реализаций цепей Маркова от энтропии стохастических матриц.

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

Практическая значимость.

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

- Предложенные алгоритмы разложения СМ ЦМ на имплицирующий вектор (ИВ) и множество стохастических булевых матриц (СБМ) позволяют определить вычислительную и комбинационную сложности вероятностных автоматов, синтезируемых в некотором логическом базисе.

- Полученные формулы определения предельного распределения вероятностей символов случайных последовательностей (СП), порождаемых полиномиальными нелинейными динамическими моделями дискретных преобразователей информации, и фундаментальная матрица для СМ позволяют на их основе получить ряд других характеристик СП, например, матрицу средних времен достижения, векторы предельных дисперсии и корреляции.

- Метод моделирования СП на основе минимального полинома позволяет: воспроизводить на линейных регистрах сдвига реализации ЦМ; расширить функциональное использование линейных регистров сдвига.

- Методика исследования линейной сложности (ЛС) марковских последовательностей расширяет класс задач применения ЛС, дает возможность моделировать ЦМ на основе линейных и нелинейных полиномов минимальных степеней, позволяет выявлять свойства ЛС марковских функций.

- Комплекс программ, алгоритмов и методик является инструментальным средством для моделирования СП и исследования свойств полиномиальных функций над конечным полем.

Результаты работы используются:

- в подсистеме временного прогнозирования производственно-экономических показателей состояния предприятия (на базе разработанной в диссертации программной реализации математического аппарата числовых стохастических матриц), включенной в состав автоматизированного рабочего места менеджера предприятия, введенного в опытную эксплуатацию в ОАО "ICL-КПО ВС", г. Казань (справка об использовании результатов);

- в учебном процессе кафедры Компьютерных систем (предыдущее название (до 2006 года) - Компьютерные системы и информационная безопасность) и кафедры Систем информационной безопасности КГТУ им. А.Н. Туполева в форме учебного электронного пособия "Лабораторный практикум по вычислениям в конечных полях" (акт внедрения).

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

- метод и алгоритмы определения закона и свойств РЦМ по СМ исходной простой ЦМ, теоремы, обосновывающие метод и алгоритмы;

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

- метод и алгоритмы разложения СМ ЦМ с двоично-рациональными элементами на ИВ и множество СБМ, теоремы, обосновывающие метод и алгоритмы;

- аналитический метод определения характеристик СП из класса функций однородных ЦМ, порождаемых полиномиальными нелинейными динамическими моделями над полем GF(2n), теоремы, обосновывающие метод;

- статистический метод исследования однородных простых и сложных ЦМ на основе критерия ЛС;

- аналитический метод представления СМ с заданной точностью и моделирования СП из класса неоднородных ЦМ полиномами минимальной степени над полем GF(qc), теорема, обосновывающая метод;

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

Апробация работы. Основные результаты докладывались и обсуждались на следующих конференциях и семинарах: Х-XV Всероссийские молодежные научные конференции "Туполевские чтения" (Казань, 2002-2007); Всероссийская научная конференция студентов и аспирантов (Таганрог, 2004); XIV Международная конференция "Проблемы теоретической кибернетики" (Пенза, 2005); Региональная научно-методическая конференция "Профессиональные компетенции в структуре модели современного инженера" (Нижнекамск, 2005); 6-ая Международная конференция молодых ученых и студентов (Самара, 2005); Международная научно-практическая конференция "Инфокоммуникационные технологии глобального информационного общества" (Казань,2005); Региональная научно-методическая конференция "Информационная культура в системе подготовки будущего инженера" (Нижнекамск, 2006); Всероссийский семинар "Ситуационные исследования" (Казань, 2006); Региональная научно-техническая конференция по вопросам информатики, вычислительной техники и информационной безопасности (Казань, 2006); Региональная научно-практическая конференция "Наука и профессиональное образование" (Нижнекамск, 2007); 9-ый Международный семинар "Дискретная математика и ее приложения" (Москва, 2007); Всероссийская научная конференция студентов, аспирантов и молодых ученых "Наука, технологии, инновации" (Новосибирск, 2007); Республиканский научный семинар "Методы моделирования" при КГТУ им. А.Н. Туполева (Казань, 2004-2008).

Публикации. Содержание работы опубликовано в 29 работах, включая 3 статьи, опубликованные в изданиях, входящих в перечень ВАК, 16 статей в других изданиях, 9 тезисов докладов и одну работу, зарегистрированную в отраслевом фонде алгоритмов и программ.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения и списка использованной литературы, включающего 250 наименований, изложена на 153 страницах машинописного текста, содержит 44 рисунка и 12 таблиц, приложение на 10 страницах.

СОДЕРЖАНИЕ РАБОТЫ

полиномиальный стохастический матрица

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

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

Связь цепей Маркова, вероятностных автоматов и полиномиальных функций над полем GF(2n) определяется на основе представления СМ P размера mЧm линейной стохастической комбинацией ИВ и множества СБМ вида

, (1.1)

где l ? m2 - m + 1 (для минимаксного алгоритма); qa - элементы ИВ , ; B(a) - СБМ (авторы: Бухараев Р.Г., Габбасов Н.З., Gelenbe S.E., Гиоргадзе А.X., Davis A.C., Захаров В.М., Костромин Г.Я., Кузнецов С.Е., Метра И.А., Паршенков Н.Я., Поспелов Д.А., Нурмеев Н.Н., Салимов Ф.И., Сачков В.Н., Ченцов В.М., Чирков М.К., Шилкевич Т.П. и др.). Размер ИВ зависит от алгоритма разложения и определяет сложность автоматных моделей марковских функций и рассматриваемых полиномиальных моделей над GF(2n).

В известных полиномиальных моделях, основанных на использовании полиномиальных функций

- от одной переменной

 (1.2)

- от двух переменных

(1.3)

минимальный порядок поля GF(2n) определяется из условия 2n ? l.

Пусть задана конечная простая ЦМ системой

(S, P, ), (1.4)

где S = {si} - конечное множество состояний ЦМ; P = (pij), - СМ; - вектор размера m начального распределения вероятностей состояний. Величина U - дискретная случайная величина (ДСВ), принимающая конечное число значений x0, …, xl-1 с вероятностями из ИВ  = {qi} размера l, .

Теорема 1.1 ¹⁾ Захаров В.М., Нурутдинов Ш.Р., Шалагин С.В. Полиномиальное представление цепей Маркова над полем Галуа // Вестник КГТУ им. А.Н. Туполева, 2001, №3. - С. 27-31.). Существуют такие ДСВ U и функция f(x, q) (1.3) со случайным начальным значением и коэффициентами GF(2n), что U может быть преобразована f(x, q) в заданную ЦМ вида (1.4). Минимальный порядок поля GF(2n) выбирается из условия 2n ? l.

Теорема 1.1 обосновывает полиномиальную модель (U; f(x, q)), (1.5)

где U - ДСВ со множеством значений {xi} с вероятностями из ИВ ; f(x, q) - функция (1.3) со множеством {xi} значений переменной x и множеством {qj} значений переменной q для моделирования ЦМ в поле GF(2n), , . Теорема определяет связь порядка поля с размерами матрицы P. Связь порядка поля GF(2n) со структурой и точностью представления матриц P является малоисследованной задачей (например, исследуемые в главе 2 разреженные матрицы РЦМ).

Дана постановка задачи представления ЦМ над конечным полем GF(qc), основанная на понятии "линейная сложность". Данное понятие связано с понятием линейных рекуррентных последовательностей над конечным полем. Исследования псевдослучайных и случайных последовательностей с помощью ЛС имеют следующие направления: разработка методов улучшения ЛС периодических последовательностей, исследование качества случайных чисел в моделировании; применение алгоритма Берлекэмпа “решения ключевого уравнения над произвольным полем” для кодирования информации; тестирование работоспособности цифровых схем; тестирование качества поточных шифров и исследование аналитической сложности генераторов чисел в криптологии (авторы: Алферов А.П., Берлекэмп Э., Иванов М.А., Куракин В.Л., Jansen C. J., Klapper A., Massey J. L., Reeds J.A., Rueppel R. A., Schaub T., Sloane N.J.A., Smeets B., Zong-duo Dai). В меньшей степени ЛС исследована в теории моделирования марковских последовательностей (МП) над конечным полем.

Во второй главе "Методы представления случайных последовательностей полиномиальными функциями над конечным полем" решаются задачи 1-3.

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

Рассмотрены следующие алгоритмы минимаксного и двоично-рационального подходов разложения (1.1) матрицы P: алгоритм 1, использующий метод минимакса; предлагаемые алгоритмы 2-4, базирующиеся на двоично-рациональном представлении элементов матрицы P; алгоритм 2 основан на методе двоично-рационального разложения матриц (Бухараев Р.Г., Захаров В.М., 1978). Доказаны конечность предложенных алгоритмов и факт различия всех формируемых ими СБМ. Данные алгоритмы позволяют снизить ВС разложения (1.1) и получить точную оценку размера ИВ для заданных матриц и точности представления матриц. В алгоритмах 3 и 4 отсутствуют ограничения на класс двоично-рациональных СМ, выявленных в алгоритме 2.

Все элементы матриц P рассматриваются в виде двоично-рациональной дроби с b разрядами. Используются следующие формы представления СБМ: в виде квадратных бинарных матриц (способ 1) размера mЧm и в виде векторов B = {bi} (способ 2) размера m, , где позиции элементов в матрицах P задают позиции равных единице элементов СБМ.

Предложена модификация алгоритма 2 (алгоритм 2м), позволяющая снизить ВС со значения O(m4b3) до O(m3b2) при хранении СБМ способом 2 и исключении операции сравнения получаемых СБМ с ранее найденными.

Пусть (m, b) - класс СМ с двоично-рациональными элементами, представленными с точностью е = 2-b.

Теорема 2.1. Алгоритм 2 для класса матриц (m, b) не результативен (не создается искомый ИВ), если матрица P  (m, b), P = (pij), , обладает одним из следующих свойств:

1) , для которого не выполняется равенство: , где cijk - значение k-го разряда pij, ,

2)  pij = 1, где .

Показано, что задача вычисления размера l ИВ для алгоритма 2 сводится к задаче нахождения экстремума числа двоичных единиц в разрядах элементов по строкам матрицы P.

Теорема 2.2. Размер l ИВ, получаемого при разложении (1.1) матрицы P по алгоритму 2, определяется условиями

l?,=const,, и

.

В алгоритме 3 координаты единичных элементов СБМ задаются координатами выбранных последовательно по одному из каждой строки, при минимальном j, элементов pij > 0 матрицы P, , а каждый элемент ИВ равен 2-b.

Предложен алгоритм 4, обладающий следующими особенностями:

- устраняются ограничения (теорема 2.1) на класс матриц алгоритма 2;

- его ВС минимальна для обоих подходов и зависит от m и b;

- дает точную оценку параметра l для конкретной матрицы P.

Алгоритм 4 состоит из следующих пунктов.

1. Из исходной матрицы P формируются матрицы W(k) = (), , , , по правилу: при pij = 1, то ; иначе  = cijk. Необходимый объем памяти для матриц W(k) равен m2b(b + 1)/2 бит.

2. При не соблюдении условия d = 0, , , значения d любых элементов  > 0 с удвоением переносятся в соответствующие элементы матрицы W(k+1), так как справедливо равенство 1/2a = 2k/2a+k, где a - натуральное число.

3. Текущая СБМ B(l) для формируется из элементов  > 0 матрицы W(k) при минимальном j. Осуществляется проверка повторения матрицы B(l) в матрицах W(j), . При получении B(l) в W(j) к ql добавляется , иначе в ИВ добавляется элемент .

Теорема 2.3. Размер l ИВ, получаемого при разложении (1.1) матрицы P по алгоритму 4, определяется условиями

l?, =const, и , (2.1)

где , - элементы матриц W(k), полученные к пункту 3 алгоритма.

Параметры ВС и l (таблица) алгоритмов двоично-рационального подхода зависят не только от размера m и энтропии H(P) матриц P, как в минимаксном подходе, но и от числа разрядов b представления элементов. Размер l ИВ для алгоритма 4 при b-const с ростом размера m матриц увеличивается, а при достижении соотношения m2 ? m + 1 > 2b становится константой. Уменьшение ВС в рассматриваемых алгоритмах осуществляется за счет: последовательного выбора элементов из строк; представления СБМ в виде вектора чисел и исключения сравнения полученных СБМ с ранее найденными; снижения точности представления элементов матрицы P. Например, вычислительная сложность снижается от 6561 (алгоритм 1) операций к 5652 (алгоритм 4) для СМ размера 99 и при числе двоичных разрядов b = 4 представления элементов.

Таблица

Алгоритм	Оценка ВС	Оценка l
алгоритм 1	O(m4)	известные оценки 1  l  m2 - m + 1 и (2.2) , (2.3) уi - число ненулевых элементов в строке i
алгоритм 2	O(m4b3)	l ? ,  = const, , и
алгоритм 2м	O(m3b2)
алгоритм 3	O(m3)	1  l  m2 - m + 1
алгоритм 4 (соавторство с Нурмеевым Н.Н.)	O(mb(17m+b))	l ? ,  = const, , и

Теорема 2.4. Порядок n поля GF(2n) в системе (1.5) для класса СМ (m, b), представленных в виде (1.1) по алгоритму 4, определяется из условия 2n ? max(l, m), где l - размер ИВ, удовлетворяющего условию (2.1).

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

1. Выполняется разложение (1.1) матрицы P с помощью алгоритма 4 на ИВ и множество СБМ. Размер ИВ удовлетворяет условию теоремы 2.3.

2. ИВ и множество СБМ преобразуются в автоматную таблицу конечного детерминированного автомата (КДА).

3. По автоматной таблице вычисляется функция f(x, q) вида (1.3) над полем GF(2n), порядок которого определяется теоремой 2.4.

Шаги метода детально описаны в диссертации, в главе 4.

В разделе 2.2 "Представление расширенных цепей Маркова над полем GF(2n)" решены задачи синтеза и анализа модели расширенных цепей Маркова над полем GF(2n). Доказана теорема (2.5), обосновывающая алгоритм вычисления закона РЦМ по заданной СМ исходной простой ЦМ. Предложен метод (теоремы 2.5, 2.7, 2.8) представления заданного стохастического закона РЦМ в определенную полиномиальную функцию над полем GF(2n). Предложены полиномиальные модели РЦМ, определены свойства структуры матрицы РЦМ (в частности, теорема 2.6 и следствие 2.1). Определены оценки размера ИВ, получаемого при разложении (1.1) матрицы РЦМ, исходя из результатов раздела 2.1. Получены оценки порядка поля GF(2n).

Пусть задана последовательность состояний sj 1, sj 2,… простой однородной ЦМ с конечным множеством состояний S = {s j} и матрицей P = (pij) размера mЧm, . Составим цепочки символов s j длины r = v + к ? 2, v ? 1, к ? 0, имеющие вид (sj 1, …, sj v, sj v+1, …, sj v+к). Смежные цепочки, содержащие к = r - v общих символов и v отличающихся символов, будем рассматривать как один шаг перехода расширенной ЦМ с mv+к состояниями Ai, , определяемой матрицей Q размера mv+кЧmv+к. Определим матрицу Q РЦМ (задача анализа) через матрицу P исходной ЦМ при v ? 2, к ? 2. Пусть E и оm - единичные матрица и вектор-столбец размеров mr-2Чmr-2 и m соответственно; - символ операции кронекерово произведения матриц; C = |B0 B1 … Bm-1| - матрица размера mЧm2, являющаяся последовательной конкатенацией матриц Bi = (), , где .

Замечание 2.1. Пусть дана матрица P = (pij), . Тогда по формуле W = оm  E  C определяется "промежуточная" стохастическая матрица W = (wcd), , размера mv+кЧmv+к, на основе которой вычисляется матрица Q.

Утверждение 2.1. Пусть дана матрица P = (pij), pij > 0, , и на ее основе получена матрица W = (wad), , с цепочками длины r = v + к, v > 1, к > 1. Тогда для W r = : .

Теорема 2.5. Пусть W v - v-я степень матрицы W, v ? 1, к ? 0. Тогда переходная матрица Q РЦМ вида

(sj 1, …, sj v, sj v+1, …, sj v+к) > (sj v+1, …, sj v+к, …, sj 2v+к) > …

равна Q = W v. (2.4)

Теорема 2.6. Пусть дана матрица P = (pij), pij > 0, , и на ее основе получена матрица Q РЦМ размера mrЧmr, r = v + к ? 2, v ? 1, к ? 0. Тогда РЦМ - эргодическая.

Следствие 2.1. Пусть дана матрица P = (pij) ЦМ, и pij = 0, ; на основе P получена матрица Q РЦМ размера mrЧmr, r ? 2, v ? 1, к ? 0. Тогда РЦМ не является эргодической.

Утверждение 2.2. Если РЦМ, заданная матрицей Q размера mrЧmr, с длиной цепочек r = v + к, образована матрицей P с одинаковыми строками, то данная цепь является цепью Маркова-Брунса.

Предложен алгоритм вычисления матрицы Q РЦМ по матрице P. Исходные данные: матрица P размера mЧm; переменные к, v, r ? 2. Результат вычислений: матрица Q размера mrЧmr.

1. Вычисляются ненулевые элементы матрицы W по формуле

 = p(i mod m), d, , , (2.5)

где i - текущий номер строки матрицы W, d - текущий номер столбца P.

2. Вычисляется соотношение (2.4).

Поставим в соответствие матрице Q размера mrЧmr полиномиальную модель (1.5) - (U, f(x, q)), где f(x, q) - функция (1.3), принимающая mr значений; переменные x и q принимают соответственно l и mr значений.

Структурная схема построенной автоматной модели (1.5) для РЦМ представлена на рис.2.1 (рис.2.2 - схема полиномиальной модели (1.5)), где Г - генератор ДСВ U; М - КДА, со множеством состояний A j, , входным алфавитом {x0, …, xl-1} и функцией переходов, полученной по Q.

Утверждение 2.3. Пусть задана матрица Q РЦМ размера mrЧmr, r ? 2. Тогда для ИВ матрицы Q, получаемого по минимаксному алгоритму, с учетом числа ненулевых элементов, размер l лежит в диапазоне

mv ? l ? mr - mк + 1. (2.6)

С учетом структуры СМ РЦМ, порядок поля, необходимого для построения полиномиальной модели РЦМ, был снижен с (mr)2 к mr.

Теорема 2.7. Пусть задана матрица Q РЦМ размера mrЧmr, r ? 2. Тогда порядок поля GF(2n) для модели (1.5) определяется из условия 2n ? mr, где n - наименьшее целое.

Учитывая разреженность матриц РЦМ осуществим синтез автоматной модели РЦМ на основе принципа приведения множества состояний A j.

Теорема 2.8. Алгоритм i-эквивалентных разбиений сводит число h состояний автоматной модели РЦМ, заданной матрицей Q, к значению m.

Схема построенной автоматной модели РЦМ изображена на рис.2.3 (рис.2.4 - полиномиальная модель). Блок 1 - КДА с множеством состояний приведенного автомата, yc - состояние КДА. Блок 2 - Г для моделирования системы из m случайных величин. Блок 3 - регистр сдвига (РС), образующий цепочки zc символов si  S длины v, . Цепочки из si образуют текущее состояние A j РЦМ, .

Теорема 2.9. Пусть задана РЦМ матрицей Q размера mrЧmr и параметрами v, к. Тогда последовательность состояний РЦМ представляется последовательностью значений функции ш = f2Чf1 - суперпозиции полиномов вида (1.3) над полем GF(2n), где n - наименьшее целое, удовлетворяющее условию 2n ? l, а l удовлетворяет неравенству (2.6).

Теорема 2.9 дает следующий метод построения полиномиальной модели над полем GF(2n) для моделирования РЦМ.

1. Вычисляется матрица Q РЦМ по алгоритму (раздел 2.2).

2. По матрице Q задается автоматная модель, представленная на рис.2.3.

3. По автоматной модели определяется функция ш = f2Чf1 и строится полиномиальная модель, представленная на рис.2.4, где блоки 1 и 3 соответствуют блокам 1 и 3 автоматной модели, а блок 2 моделирует ДСВ с числом значений l из (2.6).

В разделе 2.3 "Моделирование случайных последовательностей минимальными полиномами над конечным полем по заданной стохастической матрице" предложен метод моделирования случайных последовательностей из класса неоднородных ЦМ над полем GF(qc), где qc ? 2 - простое число. Предлагаемый метод позволяет по заданной матрице P получать семейство реализаций СП фиксированной длины на основе минимальных полиномов f(x) (полиномов минимальной степени) над полем GF(qc); доказана теорема, обосновывающая метод.

Пусть заданы P = (pij), , и  = (р0, …, рm-1) - предельный вектор для P; ц = (si 1, …, si N) - последовательность длины N в алфавите S, обладающую следующими свойствами: для любого i буква si входит ai ? 1 раз в ц; буква sj следует aij ? 0 раз за si (и за si N следует si 1); выполняются

и . (2.7)

С ц свяжем неразложимую матрицу , , удовлетворяющую (2.7), и предельный вектор =(), .

Положим: 1) точность приближения матрицы P = (pij) матрицей Pц = (), , удовлетворяет условию , 0 < е < 1; 2) длина N последовательности ц определяется из условия N  N*, N* - максимальное из и . Требуется построить минимальный полином f(x) над GF(qc), вырабатывающий последовательность uN длины N ? N *. Матрица Pц , соответствующая uN , должна с заданной величиной е > 0 аппроксимировать исходную матрицу P.

Теорема 2.10. Пусть заданы неразложимая СМ P = (pij) размера mm и числа 0 < е < 1, N ? N*. Тогда существует минимальный полином f(x) над полем GF(qc), вырабатывающий последовательность uN'+1 длины N' + 1 с законом Pц = (), который удовлетворяет условиям

, (2.8)

и , , (2.9)

, (2.10)

и степень L полинома f(x) удовлетворяет условию 2L ? N ' + 1.

Следствие 2.2 (из теоремы 2.10). Число последовательностей uN ' + 1, полученных по матрице Pц размера mЧm и удовлетворяющих условиям (2.8)-(2.10) теоремы 2.10, ограничено сверху величиной m L, где

.

Представим на рис. 2.5 метод моделирования СП на основе полинома f(x): входные параметры, необходимые для преобразований, надписаны в верхней части; величины, над которыми выполняются преобразования - посередине; известные алгоритмы, выполняющие преобразования - внизу.

Благодаря алгоритму получения матрицы Pц, для аппроксимации исходной матрицы P с заданной точностью необходима реализация ЦМ длиной не в N 2 символов, а в N.

Третья глава "Методы анализа полиномиальных функций, моделирующих случайные последовательности в конечном поле", состоит из двух разделов, в которых исследуются свойства полиномиальных нелинейных динамических моделей преобразователей функций ЦМ и линейной сложности МП (решаются задачи 4, 5).

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

Определение базовых полиномиальных функций над полем GF(2n). Введем в рассмотрение ЦМ, заданную системой (1.4), и полиномиальные функции g(y) (1.2) и f(x, q) (1.3) над полем GF(2n); значения этих функций обозначим соответственно и б, б,   GF(2n). Поставим в соответствие матрице P полиномиальную модель (1.5) - (U, f(x, q)), где f(x, q) - функция (1.3), принимающая m значений, а переменные x и q - соответственно l и m значений.

Утверждение 3.1. Порядок поля GF(2n) в (1.5) определяется из условия 2n ? l1, где n - наименьшее целое, а l1 - размер ИВ для матриц P, у которых pij = 0, определяемый условием (2.3).

Полиномиальные нелинейные динамические модели, порождающие функции цепей Маркова

1. Зададим следующие ограничения на систему (1.5).

1) Пусть значение (t+1) функции f(x, q), полученное в момент времени t+1, есть состояние ЦМ, определяемое переменными x(t) и q(t) = (t) во время t.

2) Значение q в момент t = 0 определяется вектором .

При этих ограничениях системе (1.5) соответствует ПНДМ над полем GF(2n) вида

(U, (t+1) = f(x(t), q(t)), ). (3.1)

Последовательность значений f(x(t), q(t)) в системе (3.1) в моменты t = 1, 2, … является простой однородной ЦМ, определяемой P и . На структурной схеме модели (3.1) (рис.3.1) функциональное назначение блоков 1, 2 соответствует системе (3.1); блок 1 - генератор ДСВ U; блок D - элемент задержки на единицу времени t = 1. Пусть  = (pб i(t)) - вектор распределения вероятностей значений f(x(t), q(t)) для времени t; - предельный вектор эргодической ЦМ.

Теорема 3.1. Для СП, порождаемой моделью (3.1):

 и P=. (3.2)

2. Разобьем множество S системы (1.4) на непересекающиеся подмножества

C0, …, ;  = S; Ca ? Cj = 0, a ? j, , (3.3)

и выполним отображение

(s): S > Bt = {, …, }, (3.4)

где Bt = {} - функция конечной ЦМ с hs значениями, определяемая условием  = j, если в момент времени t ЦМ находится в каком-либо состоянии si подмножества Cj, .

По аналогии с (3.1) функцию Bt будем моделировать над полем GF(2n) ПНДМ вида:

(U, ш1(t+1) = g(y(t+1))·f(x(t), q(t)), ), (3.5)

где 2n ? l1; q(t) = б(t); функция g(y(t+1)) реализует отображение (s); ш1 - суперпозиция функций f(x, q) и g(y); последовательность значений функции ш1 в моменты t представляет функцию Bt.

Пусть  = (pв j(t)) и - вектор и предельный вектор распределения вероятностей значений функции ш1(t). Зададим бинарную матрицу Л = (лij), где лij = 1, если si  Cj, , .

Теорема 3.2. Для ПНДМ (3.5), заданной системой ((1.4), (3.4)) = (S, P, Bt , (s), ), векторы и вычисляются по формулам

и . (3.6)

На систему (3.5) наложим следующие ограничения.

а1) l ? rf определяет порядок поля, а функции f(x, q) соответствует матрица коэффициентов Af = (),   GF(2n), .

а2) Заданы ДСВ U с ИВ размера l, l ? rf , и вектор размера m.

а3) Переменная x и функция f(x, q) принимают соответственно l и m значений, а множества значений q(t), б и y(t+1) совпадают.

а4) Функция g(y) реализует отображение м(s).

Следствие 3.1. Пусть задана система (3.5) с ограничениями а1) - а4). Тогда для нее однозначно определяются матрица P, векторы

, и . (3.7)

3. Зададим функцию ЦМ системой

((1.4), Z, (z/s)), (3.8)

где функция (z/s) задается матрицей P(z/s) = (), , , а элемент определяет вероятность появления буквы zjZ при состоянии si.

Системе (3.8), по теореме 3.2, поставим в соответствие ПНДМ

(U, U , ш2(t+1) = f2[x(t+1), q(t+1)]·f1[x(t), q(t)], ), (3.9)

где 2n ? max(l1, l2); l2 - размер ИВ, полученного при разложении матрицы P(z/s); U и U  - ДСВ, определяемые по разложению (1.1) матриц P и P(z/s); ш2(t+1) - задает процесс Zt и является суперпозицией функций f2 и f1 вида (1.3). и - вектор и предельный вектор распределения вероятностей значений ш2(t).

Следствие 3.2. Если в системе (3.8) ЦМ - эргодическая, то для модели (3.9), заданной по системе (3.8), векторы и вычисляются по формулам

и . (3.10)

Рассмотрим систему (3.9) при следующих ограничениях.

с1) Пусть заданы вектор ; ДСВ U и U ', состоящие соответственно из l1 и l2 значений.

c2) Заданы порядок n поля GF(2n) из условия 2n ? max(l1, l2) и матрицы коэффициентов для f1(x, q) и f2(x, q).

c3) Задано ограничение a3) на функцию f1(x, q).

c4) Переменная x в f2(x, q) и функция f2(x, q) принимают соответственно l2 и |Z| значений, а множества значений q(t) и f1(x, q) совпадают.

Следствие 3.3. Пусть задана система (3.9) с ограничениями c1) - c4). Тогда для процесса Zt однозначно определяются матрицы P и P(z/s), вектор (3.10) и, если полученная ЦМ является эргодической, то и вектор (3.10).

4. Введем систему вида

 = ((1.4), (3.4), Z, (z/b(t))), (3.11)

где (z/b(t)) задается матрицей  = (), , , а определяет вероятность появления буквы zj  Z от буквы .

Заданную системой (3.11) функцию ЦМ можно моделировать ПНДМ вида

(U, U , ш3(t+1) = f2[x(t+1); q(t+1)]·ш1(t+1), ), (3.12)

где ш3(t) - суперпозиция функций f2 и ш1, а последовательность значений функции ш3(t) задает процесс Z't (рис.3.2 - структурная схема модели (3.12)).

Пусть и - вектор и предельный вектор распределения вероятностей значений ш3(t).

Следствие 3.4. Для модели (3.12), заданной по системе (3.11), векторы и равны и . (3.13)

Совокупность формул (3.2), (3.6), (3.7), (3.10), (3.13), определяемых теоремами (3.1, 3.2) и следствиями (3.1-3.4), образует метод вычисления характеристик ПНДМ вида (3.1), (3.5), (3.9) и (3.12) над полем GF(2n), порождающих СП из класса функций ЦМ.

В разделе 3.2 "Статистический анализ линейной сложности регулярных цепей Маркова" предложен метод статистического анализа однородных простых и сложных ЦМ по критерию ЛС (с использованием результатов раздела 2.3). Определены статистические критерии нахождения необходимых для исследования ЛС длин реализаций МП при заданной точности представления СМ, рассмотрены их отличия и особенности. Показана взаимосвязь ЛС и энтропии СМ: определены оценки математического ожидания M(L(lc)) и дисперсии D(L(lc)) МП, моделируемых по заданным матрице P и энтропии H(P), где L(lc) - значение ЛС МП длины lс; определены оценки M(L(lc)) и D(L(lc)), характеризующие подклассы МП с определенной величиной H(P); определен профиль ЛС МП.

ЛС линейной рекуррентной последовательности (ЛРП) определяет минимальную длину ЛРС, реализующего данную последовательность. Алгоритмом вычисления ЛС заданной ЛРП и нахождения полинома f(x) является АБМ. Функция L(i) называется профилем ЛС последовательности u, где L(i) задает ЛС последовательности u = (s0, s1, …, si-1) для .

Пусть у ЦМ с алфавитом состояний S стохастическая матрица P = (pij) размера mЧm (m rЧm r - для r-сложных ЦМ) принадлежит классу регулярных матриц MR; предельный вектор , матрица частот P', вектор ' = (ai / lc) соответствуют обозначениям , Pц и раздела 2.3. Опишем метод статистического анализа однородных простых и сложных ЦМ по критерию ЛС.

1. Строятся матрицы P  MR методом статистического моделирования при условиях: стохастичности по строкам, регулярности СМ и соответствия P одной из трех, равных по величине, групп энтропии Hi(P), .

2. Вычисляется точность е отображения свойств исходной ЦМ реализацией ЦМ из условия 2(1 - л)d ? е. (3.14)

Выражение (3.14) вытекает из неравенства Берштейна: , где , - вероятность перехода ЦМ в состояние si  S за d шагов, d = 1, 2, …

3. Параллельно со статистическим моделированием реализаций ЦМ определяется lс, с остановкой при выполнении |рi - ai / lc| ? е,, (3.15)

- критерия, задающего длины последовательностей, достаточных для отображения с точностью свойств ЦМ, и отражающего закономерности и предельные свойства P. Для реализации ЦМ вычисляется ее ЛС (с помощью АБМ) и строится профиль ЛС.

4. В пункте 3 генерируются реализации ЦМ, число которых соответствует заданному уровню точности, и по ним вычисляются оценки M(L(lс)) и D(L(lс)), строятся плотность и функция распределения величины L(lс).

ВС АБМ для двоичной последовательности длины lс составляет оценку O(). Правильность работы программной реализации метода анализа проверялась на основе анализа следующих последовательностей: псевдослучайных двоичных, полученных на ЛРС; случайных чисел; реализаций ЦМ при Hmax(P); полученных аффинными преобразованиями.

Для простых и сложных ЦМ получены следующие оценки (по критерию (3.15)), близкие к случайным последовательностям с равномерным распределением: M(L(lс))  lс /2 + щ, щ < 1 - коэффициент,

D(L(lс))  86/81 при H(P)  [0,5·Hmax(P); 0,9·Hmax(P)] и Hmax(P) = log 2 m, распределение случайной величины ЛС с ростом объема выборки стремится к нормальному закону.

Показано, что среди сложных и простых ЦМ, матрицы которых равны, ЛС больше у сложных ЦМ из-за избыточности двоичного кодирования состояний. ЛС зависит от H(P) и не зависит от m. Если на данном этапе построения профиля ЛС наблюдается горизонтальный тренд, то изменяется f(x) без увеличения L или для АБМ являются предсказуемыми символы последовательности. Значение ЛС растет при повторе символов последовательности, не начинающихся с начала последовательности. Полученные оценки ЛС ЦМ могут служить оценками необходимой величины минимальной степени полинома при моделировании ЦМ над полем GF(qc) (раздел 2.3).

В четвертой главе "Комплекс методик и программ для решения задач построения и анализа полиномиальных функций и моделирования случайных последовательностей" описывается разработанный комплекс методик и программ, реализующий методы и алгоритмы, предложенные в диссертации. Комплекс позволяет решать следующие задачи: преобразование закона цепи Маркова в полиномиальную модель с использованием двоично-рационального разложения СМ и представление марковских функций полиномиальными моделями; тестирование предложенных полиномиальных моделей; получение закона расширенной цепи Маркова; исследование характеристик марковских и псевдомарковских циклических последовательностей с помощью АБМ.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Предложен новый метод моделирования случайных последовательностей фиксированной длины N из класса неоднородных цепей Маркова, заданных стохастическими матрицами, на основе полиномов минимальной степени над конечным полем GF(qc), qc ? 2, позволяющий повысить точность представления стохастических матриц полиномами пропорционально величине 1/N. Доказана теорема, устанавливающая существование минимальных полиномов для представления стохастических матриц с заданной точностью.

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

5. Предложена новая методика статистического анализа однородных простых и сложных цепей Маркова по критерию линейной сложности. Статистическим моделированием получены оценки линейной сложности реализаций цепей Маркова.

6. Разработан комплекс методик и программ, реализующий предложенные методы и алгоритмы.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

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

1. Захаров В.М., Эминов Б.Ф. Анализ нелинейных моделей преобразователей случайных последовательностей над полем GF(2n) на основе стохастических матриц // Вестник Казанского государственного технического университета им. А.Н. Туполева. - Казань: КГТУ им. А.Н. Туполева, 2006, №3. - С. 41-46.

2. Эминов Б.Ф. Метод моделирования случайных последовательностей класса неоднородных цепей Маркова полиномами минимальной степени над полем GF(q) // Системы управления и информационные технологии. Вып. 4.1(30). - Воронеж: Изд-во "Научная книга", 2007. - С. 203-207.

3. Захаров В.М., Эминов Б.Ф. Анализ алгоритмов разложения двоично-рациональных стохастических матриц на комбинацию булевых матриц // Информационные технологии, №3. - М.: Изд-во Новые технологии, 2008. - С. 54-59.

II. Статьи в сборниках и материалах научно-технических конференций.

4. Эминов Б.Ф. К задаче анализа полиномиальных моделей автономных вероятностных автоматов // ХII Туполевские чтения: Международная молодежная научная конференция. Том 3. - Казань: КГТУ им. А.Н. Туполева, 2004. - С. 60-62.

5. Захаров В.М., Эминов Б.Ф. Автоматное моделирование расширенных цепей Маркова // Актуальные проблемы современной науки: Труды 1-го Международного форума молодых ученых и студентов. Ч.18.-Самара: Изд-во Самар.гос.техн.ун-та, 2005.- С.146-148.

6. Эминов Б.Ф. Программный комплекс обучающих средств "Основы криптографической защиты информации" // Прикладная информатика - 2004: Доклады факультетской научно-технической конференции. - Казань: КГТУ им. А.Н. Туполева, 2005. - С. 84-88.

7. Эминов Б.Ф. Анализ полиномиальных моделей автономных вероятностных автоматов // Прикладная информатика - 2004: Доклады факультетской научно-технической конференции. - Казань: КГТУ им. А.Н. Туполева, 2005. - С. 36-40.

8. Дьячков В.В., Эминов Б.Ф. Временное прогнозирование функционирования предприятия на нейронных сетях // Информационная культура в системе подготовки будущего инженера: Материалы региональной научно-методической конференции, Нижнекамск. - Казань: КГТУ им. А.Н. Туполева, 2006. - С. 64-66.

9. Эминов Б.Ф. Построение имплицирующего вектора на основе двоично-рационального представления элементов стохастических матриц // Информационная культура в системе подготовки будущего инженера: Материалы региональной научно-методической конференции, Нижнекамск. - Казань: КГТУ им. А.Н. Туполева, 2006. - С. 222-224.

10. Эминов Б.Ф. Модели ситуационного управления как инструмент познания // Всероссийский семинар Ситуационные исследования: вып. 2. Типология ситуаций // Под ред. Н.М.Солодухо. - Казань: КГТУ им.А.Н.Туполева, 2006. - С. 84-94.

11. Эминов Б.Ф. Минимизация автоматной модели расширенной цепи Маркова методом l-эквивалентных преобразований//ХIV Туполевские чтения:Международная молодежная науч. конференция, том 4. - Казань: КГТУ им.А.Н.Туполева, 2006. - С.74-76.

12. Захаров В.М., Эминов Б.Ф. Статистический анализ линейной сложности регулярных цепей Маркова // Исследования по информатике. Выпуск 10. ИПИ АН РТ. - Казань: Отечество, 2006. - С. 37-50.

13. Эминов Б.Ф. Влияние точности представления двоично-рациональных элементов стохастических матриц на размер имплицирующего вектора // Научно-техническая конференция по вопросам информатики, вычислительной техники и информационной безопасности. - Казань: КГТУ им. А.Н. Туполева, 2006. - С. 122-125.

14. Эминов Б.Ф. Получение стохастической матрицы расширенной цепи Маркова//Наука и профессиональное образование: Материалы региональной научно-практической конференции, Нижнекамск. - Казань: КГТУ им. А.Н.Туполева, 2007. - С.225-230.

15. Захаров В.М., Эминов Б.Ф. Представление расширенных цепей Маркова над полем GF(2n) // Моделирование процессов. Труды Казанского научного семинара "Методы моделирования". Вып.3. - Казань: КГТУ им.А.Н.Туполева, 2007. - С. 270-286.

16. Эминов Б.Ф. Моделирование случайных последовательностей минимальными полиномами над конечным полем по заданной стохастической матрице // Информационнные технологии моделирования и управления. Научно-технический журнал. Вып. 7 (41). - Воронеж: Изд-во Научная книга, 2007. - С. 811-818.

17. Эминов Б.Ф. Применение алгоритма Берлекемпа-Месси к синтезу и анализу рекуррентных двоичных последовательностей // ХV Туполевские чтения: Международная молодежная науч.конф. Том 3. - Казань: КГТУ им.А.Н.Туполева, 2007. - С.90-92.

...