Марковские автоматы над полем Галуа и их моделирование в базисе программируемых матриц логических элементов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Шалагин, Сергей Викторович

• Шалагин, Сергей Викторович
• кандидат технических наук
• 2001

Оглавление диссертации кандидат технических наук Шалагин, Сергей Викторович

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

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

ВВЕДЕНИЕ.

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

§ 1. Определения марковских моделей.

§ 2. Поля Галуа.

§ 3. Программируемые матрицы логических элементов.

§ 4. Методы многомерной классификации.

ГЛАВА 2. Синтез структур марковских моделей над полем Галуа.

§ 1. Полиномиальное представление марковской модели над полем Галуа.

§ 2. Структурная модель генератора цепей Маркова над полем

Галуа.

§ 3. Структурные реализации полиномиальной функции и оценки их сложности.

§ 4. Минимизация структуры полиномиальной модели.

§ 5. Синтез генератора дискретных случайных величин над полем Галуа.

§ 6. Распространение результатов на задачи синтеза автономных вероятностных автоматов.

ГЛАВА 3. Компьютерное моделирование полиномиальных моделей в структуре ПМЛЭ.

§ 1. Определение базовых математических моделей умножителя.

§ 2. Структурные модели умножителей и их оценки сложности.

§ 3. Оценки сложности синтеза умножителей над полем Галуа в базисе программируемых матриц логических элементов.

§ 4. Временные оценки сложности и результаты моделирования. 100 ГЛАВ А 4. Кластерный анализ марковских моделей.

§ 1. Общая постановка задачи кластерного анализа стохастических матриц.

§2. Модель данных. ПО

§3. Схема кластерного анализа.

§4. Получение результатов кластерного анализа.

§5 Оценка обоснованности (достоверности) результатов.

§6 Оценка зависимости (корреляции) внутри множества классификационных признаков.

ГЛАВА 5. Комплекс прикладных программ для реализации алгоритмов синтеза и анализа полиномиальных моделей.

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

§ 2. Программа разложения стохастической матрицы на взвещенную сумму простых матриц.

Введение диссертации (часть автореферата) на тему «Марковские автоматы над полем Галуа и их моделирование в базисе программируемых матриц логических элементов»

В теории и практике моделирования динамических, сложных систем в качестве их моделей широко используются цепи Маркова.

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

Примерами эффективного применения цепей Маркова (ЦМ) являются статистическое моделирование [1-5], распознавание образов [6-7], передача и защита информации в сетях ЭВМ [8-9], в автоматизированных системах обработки информации, тестирования и диагностики цифровых устройств [10-12] и др.

Известно большое число работ по теории моделирования марковских последовательностей и построению генераторов ЦМ [13-37, 62-64]. На основные принципиальные вопросы, связанные с моделированием марковских последовательностей ответы получены на базе теоретико-автоматных представлений [1-2, 4, 13-18, 21-33]. В частности, уже в первых работах по автоматному моделированию ЦМ [29-30] отображен взгляд на конечную однородную цепь Маркова как на конечный детерминированный автомат (КДА) со случайным входом, показан переход от описания ЦМ в виде стохастической матрицы к описанию в виде стохастической линейной комбинации булевых стохастических матриц, определены условия автоматной преобразуемости случайной дискретной величины в другую [1, 4, 13-15, 21], показана возможность моделирования ЦМ на основе булевых функций 1, 16], получены результаты по решению задачи построения имплицирующего стохастического вектора для заданной стохастической матрицы [4, 17, 21, 114], предложены принципы построения управляемых генераторов случайных кодов [13].

Появление микроэлектронной технологии интегральных схем стимулировало исследования в 70-х годах по синтезу дискретных вероятностных моделей автоматного типа [15, 18, 20, 27, 38-40] в однородных вычислительных средах. В работах Гиоргадзе А.Х. [18] был развит метод пространственно-временной декомпозиции вероятностных автоматов [39-40], основанный на специальном и направленном расщеплении и склеивании состояний конечной простой однородной ЦМ. Но такой подход построения однородных структур вероятностных моделей не достаточно адекватно отвечает требованиям параллельной и потоковой обработки информации. Кроме того, он требует реализации распределенных в клеточном пространстве источников «случайности», что усложняет построение моделей.

В 80-90 гг. появились работы, показывающие эффективность аппарата полей Галуа - GF(2) [41] - для синтеза детерминированных цифровых устройств [37, 44-50, 65-67] в однородных структурах [68-69 .

В литературе также нашли широкое отражение задачи построения генераторов равномерно распределенных случайных и псевдослучайных чисел в поле GF(2) [10, 42-43, 51-61, ПО, 112]. Однако задача построения автоматных моделей генераторов цепей Маркова (марковских автоматов [70, стр. 19]) над полем Галуа в литературе не получила освещения.

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

Актуальность этой задачи определяется широким применением ММ.

Появление современных компьютерных технологий позволяет ставить и решать новые задачи по синтезу и анализу ММ. При разработке цифровых устройств в настоящее время привлекателен подход к синтезу на основе программируемых логических интегральных схем (ПЛИС, зарубежное обозначение которых - LCA или FPGA [71-72]). ПЛИС типа FPGA по своей архитектуре представляют собой программируемые матрицы логических элементов (ПМЛЭ), что позволяет реализовать на них параллельную обработку данных. ПМЛЭ представляют собой однородные вычислительные структуры [68-69] и широко используются в качестве различных логических блоков, микропрограммных устройств управления и др. На базе ПМЛЭ строятся высокоэффективные аппаратные макромодули, выполненные как фрагменты системных функций, такие как модули цифровых фильтров, модули быстрого преобразования Фурье, модули обработки высокоскоростных потоков цифровых данных в реальном масштабе времени [71-83].

Построение устройств на ПМЛЭ предполагает выполнение предварительной структурной и функциональной проработки проектируемого устройства (проекта), которая включает в качестве важнейшей задачу оценки логических ресурсов ПМЛЭ, требуемых для реализации проекта. Подобная задача, в частности, решается в [73], где дана определённая методика её решения и приведены оценки логических ресурсов ПМЛЭ серии ХСЗххх 72], требуемых для построения некоторых стандартных компонентов технических схем: счётчиков, мультиплексоров, дешифраторов и др.

Задача синтеза на базе ПМЛЭ решается с помощью современной комплексной компьютерной технологии автоматизированного проектирования [71-72].

В связи с отмеченным подходом представляется актуальной задача разработки методов анализа, с помощью компьютерного моделирования, степени адекватности структурных моделей генераторов цепей Маркова, построенных над полем Галуа, структуре ПМЛЭ.

При реализации семейств генераторов ЦМ на базе ПМЛЭ возникает вопрос хранения больших массивов исходных данных, связанных с представлением стохастических матриц (СМ). В настоящей работе предлагается подход [85-88] к решению задачи уменьшения объема данных, основанный на классификации (группировании) стохастических матриц, задающих генераторы ЦМ, методами многомерной математической статистики [8991] с использованием «Интегрированной системы STATISTIC А 5.0» [92], с последующим выделением представителей получаемых групп.

Диссертационная работа посвящена задаче исследования возможности и эффективности построения марковских автоматов (МА) в полях Галуа и разработка методов анализа степени соответствия получаемых структур структуре программируемых однородных вычислительных сред.

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

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

• разработка математической модели представления марковских автоматов над полем Галуа GF{2");

• разработка структурных моделей генераторов ЦМ над полем GF(2") и получение оценок их сложности;

• исследование адекватности структурных реализаций многочленов над полем GF{2"), задающих генераторы ЦМ, структуре ПМЛЭ, на основе компьютерного моделирования;

• разработка модели многопараметрического анализа множеств стохастических матриц методами кластер анализа с целью уменьшения объема исходных данных для моделирования ЦМ с заданными свойствами;

• разработка комплекса прикладных программ для анализа и синтеза марковских автоматов.

Научная новизна работы.

• Дана постановка задачи построения марковских автоматов над полем Галуа. Введено понятие «полиномиальная модель однородной конечной простой цепи Маркова» над полем ОР{2"). Установлена взаимосвязь ЦМ и полиномов над полем Галуа. Предложен метод и разработаны алгоритмы и методика синтеза марковских автоматов в виде суперпозиции полиномиальных функций над полем Галуа. Предложены и разработаны альтернативные структурные реализации генераторов ЦМ на основе полиномиальных функций над полем 0Р{2"), получены их сложностные и временные оценки.

• Разработаны алгоритм минимизации количества ненулевых коэффициентов полиномиальной функции над полем 0Р{2'") и метод представления генератора дискретной случайной величины (ДСВ) полиномиальными функциями над полем Галуа.

• Получены оценки сложности полиномиальных моделей ЦМ в базисе программируемых матриц логических элементов.

• Дана постановка задачи классификации стохастических эргодических матриц методами многомерной математической статистики и предложена методика классификации.

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

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

Предложенная полиномиальная модель марковского автомата над полем Галуа расширяет область применения модулярной и полиномиальной арифметик на задачи моделирования случайных процессов. ПолзЛенные оценки аппаратных затрат, представленные описания алгоритмов и программ дают разработчикам возможность их непосредственного использования при моделировании и проектировании специализированных автоматных моделей по современной технологии ПМЛЭ. Предложенный метод представления марковских моделей полиномиальными функциями над полем Галуа может быть применён для решения задач синтеза более широкого класса вероятностных автоматных моделей. Разработанная методика многопараметрической классификации стохастических матриц позволяет получать новые их характеристики, которые могут быть использованы для представления класса марковских моделей одной полиномиальной функцией над полем Галуа и соответственно - для уменьшения объема исходных данных при моделировании цепей Маркова.

Результаты работы использованы в НИР за 2000г. по гранту РФФИ № 99-01-00163 «Энтропийно-сложностные свойства дискретных вычислительных моделей» и по проекту Х2 015-04-01-52 «Синтез и сложность детерминированных и вероятностных дискретных вычислительных моделей» программы «Университеты России», в ФНПЦ «Радиоэлектроника» (г. Казань), в центре новых информационных технологий (ЦНИТ) РТ (г. Казань), в ГИБДД МВД Республики Татарстан (г. Казань) и в учебном процессе кафедры ЭВМ Казанского государственного технического университета.

Апробация результатов работы. Основные положения и результаты докладывались и обсуждались на Ш-й Республиканской научно-технической конференции молодых учёных и специалистов (Казань, 1997г.); Всероссийских студенческих Туполевских чтениях «Актуальные проблемы авиастроения» (Казань, 1998г.); 1-й Всероссийской научно-технической конференции «Компьютерные технологии в науке, проектировании и производстве» (Нижний Новгород, 1999г.); Ш-ем Всероссийском семинаре «Теория сеточных методов для нелинейных краевых задач» (Казань, 2000г.); Всероссийской научно-технической конференции «Тупо-левские чтения студентов» (Казань, 2000г.); Всероссийской научнометодической конференции «Интеграция образования, науки и производства - главный фактор повышения эффективности инженерного образования» (Казань, 2000г.); Итоговой научной конференции Казанского государственного университета (Казань, 2001г.); VII-m Международном семинаре «Дискретная математика и её приложения» (Москва, 2001г.), городском семинаре «Методы моделирования» (Казань, 2001г.), ряде семинаров кафедры Теоретической кибернетики Казанского государственного университета (Казань, 2001г.).

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

• полиномиальная модель марковского автомата над полем Галуа GF(2"), метод построения структурных моделей марковских автоматов в виде суперпозиции полиномиальных функций в полях Галуа, однородные схемы генераторов ЦМ;

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

• оценки сложности структурных моделей умножителей над полем Галуа и методика анализа их адекватности логической структуре ПМЛЭ;

• модель и методика многопараметрического анализа марковских моделей методами кластерного анализа;

• комплекс прикладных программ для реализации алгоритмов синтеза и анализа марковских автоматов.

Основное содержание диссертации опубликовано в 23 работах, включая 7 статей [84-86, 93-95, 126], 15 тезисов [87-88, 96-108] и 1 учебное пособие [109].

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения и двух приложений.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Шалагин, Сергей Викторович

Выводы по главе 5

1. Разработан комплекс программных средств, включающий три прикладных программы, служащих для исследования эффективности алгоритма минимизации количества ненулевых коэффициентов полиномиальной функции. Первая программа осутцествляет генерацию неповторяющихся автоматных функций переходов, заданных таблично (автоматные таблицы), фиксированной размерности. Вторая - ставит в соответствие указанным автоматным таблицам полиномиальные функции. Третья - определяет заданные характеристики ПФ с целью набора статистики.

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

3. Разработана методика вычисления таблицы «Объект признак» на базе редактора электронных таблиц Microsoft Excel 97 и программная реализация связанной с ней задачей построения стохастических матриц (имеющих заданную структуру) методом рандомизации.

4. Разработанные программы использованы: а) при решении задач настоящей диссертационной работы; б) в организациях при выполнении плановых НИР: см. Приложение 2. в) в учебном процессе кафедры ЭВМ Казанского государственного технического университета по курсам «Моделирование», «САПР», «Синтез и анализ криптографических алгоритмов».

ЗАКЛЮЧЕНИЕ.

В работе получены следующие основные результаты.

1. Поставлена и решена задача синтеза МА в базисе полиномиальных функций над полем Галуа. Результатами решения являются: предложена разработанная полиномиальная модель над полем GF{2") конечной простой однородной цепи Маркова, теорема синтеза, задающая метод преобразования МА в полиномиальную модель и теорема анализа, обосновывающая обратное преобразование полиномиальной модели в МА; установлена взаимосвязь стохастических матриц с полиномиальными функциями, что позволяет реализовать распараллеливание процесса обработки информации и реализовывать более адекватные структуры генераторов цепей Маркова в программируемых однородных вычислительных средах; предложены альтернативные (по критериям сложности и быстродействия) структурные схемы - параллельного, систолического векторного, систолического и последовательностного типов - для реализации генераторов ЦМ в базисе полиномиальных функций. (Грант РФФИ № 99-01-00163).

2. Разработан алгоритм минимизации заданных полиномиальных функций на основе известного метода, а также предложен метод полиномиального представления генератора ДСВ с заданным законом распределения над полем Галуа. Предложена структурная модель генератора ЦМ, основанная на преобразовании вида суперпозиция полиномиальных функций над полем Галуа. Показана возможность применения понятия «суперпозиция полиномиальных функций над полем Галуа» для построения ABA с выходом, что позволяет расширить класс цепей Маркова, генерируемых посредством полиномиальных функций. (Грант РФФИ№ 99-01-00163).

3. Предложены структурные модели схем умножения в поле Галуа (умножителей). Доказаны утверждения, определяющие теоретические оценки сложности и оценки реальных затрат при реализации умножителей в базисе ПМЛЭ, а также теоретические оценки времени выполнения операции умножения элементов поля Галуа. Предложена методика исследования адекватности структурных реализаций умножителей, задающих генераторы ЦМ, матричной архитектуре ПМЛЭ (Грант РФФИ № 99-01-00163).

4. Разработана модель и соответствующая методика многопараметрического анализа множеств стохастических матриц, задающих полиномиальные модели генераторов ЦМ, что позволяет решать задачу уменьшения объема исходных данных при моделировании семейств ЦМ (проект № 01504-01-52 программы «Университеты России»).

5. Разработан комплекс прикладных программ для реализации алгоритмов синтеза и анализа полиномиальных моделей, задающих МА, с целью решения следующих задач: разложения стохастических матриц, задающих ПМ, на взвешенную сумму простых матриц, генерации ЦМ на основе заданной стохастической матрицы, вычисления укрупненной цепи Маркова, определения структуры полиномиальной модели на основе задающей ее СМ.

Результаты диссертации использованы в ПЦР за 2000г. по гранту РФФИ № 99-01-00163 «Энтропийно-сложностные свойства дискретных вычислительных моделей» и по проекту № 015-04-01-52 «Синтез и сложность детерминированных и вероятностных дискретных вычислительных моделей» программы «Университеты России», в Казанском ФНПЦ «Радиоэлектроника», в центре новых информационных технологий (ЦНИТ) РТ, в Госинпром КНИАТ, в институте проблем информатики (ИПИ) АН РТ и в учебном процессе кафедры ЭВМ Казанского государственного технического университета.

Список литературы диссертационного исследования кандидат технических наук Шалагин, Сергей Викторович, 2001 год

1. Макаров СВ. О реализации стохастических матриц конечными автоматами. // Вычислительные системы. - Новосибирск, 1963. - Вып. 9. - С. 65-70.

2. Хамитов Г.П. Имитация случайных процессов. Иркутск: Изд-во ИГУ, 1983.

3. Четвериков В.Н., Баканович Э.А., Меньков A.B., Вычислительная техника для статистического моделирования. М.: Сов. радио, 1978. -312 с.

4. Чепцов В.М. Об одном методе синтеза автономного стохастического автомата. //Кибернетика. 1968. - №3. - С. 32-35.

5. Походзей Б.Б. Преобразование случайных битов в случайные величины с конечными дискретными распределениями. // Вести. Ле-нингр. ун-та. Сер. матем., механ., астр., 1983. №13. - Вып. 3. - С. 31-36.

6. Барашко A.C., Павлив A.C. Обобщённый подход к статистическому распознаванию автоматов. // Кибернетика и системный анализ, 1988. -№1.-С. 46-56.

7. Баращко A.C. Об одном статистическом методе распознавания автоматов. Тезисы докладов XII Междунар. конф. «Проблемы теоретической кибернетики» Н.Новгород, 1999. М.: Изд-во МГУ, 1999. -4.1.-С. 19.

8. Герасименко В.А. Защита информации в автоматизированных системах обработки данных. Книга 1. М. Энергоатомиздат, 1994. -400с.

9. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. / Под ред. В.Ф. Шаньгина. М.: Радио и связь, 1999. - 328 С.

10. Столов Е.Л. Методы компактного тестирования цифровых устройств. Казань: изд-во Казанского ун-та, 1993.- 116с.

11. A.c. 1481755 СССР, МКИ С 06 Г 7/58. Генератор случайного Марковского процесса / А.А.Гремальский, С.М.Андроник // Открытия, изобретения. 1989. - № 19. - С. 223.

12. Гремальский A.A., Андроник СМ. Генерация тестовых программ для микропроцессоров с помощью цепей Маркова // Исследование новых микропроцессорных приборов и устройств. Кищинев: Штинца, 1987.-С 96-98.

13. Бухараев Р. Г., Захаров В. М. Управляемые генераторы случайных кодов. Казань: КГУ, 1978. - 160 с.

14. Бухараев Р.Г. Автоматное преобразование вероятностных последовательностей. // Вероятностные методы и кибернетика. Казань.: Изд-во КГУ, 1966. - Вып. 4. - - С. 24-33.

15. Бухараев Р.Г. Основы теории вероятностных автоматов. М.: Наука,1985. -287 с.

16. Бухараев Р.Г. Теория конструирования мащин для статистического моделирования (Вероятностные автоматы): Дисс. д-ра. техн. наук. -Казань, 1968.

17. Вероятностные автоматы и их приложения. Казань: Изд-во КГУ,1986. -212 с.

18. Гиоргадзе А.Х. Пространственно-временная декомпозиция и структурный анализ и синтез стохастических систем: Дисс. д-ра. техн. наук. -Тбилиси, 1981. -320 с.

19. Гладкий B.C. Вероятностные вычислительные модели. М.: Наука, 1973.-300 с.

20. Кузин Г.С. Летунов Ю.П. Плахотшин A.M. Принципы построения вероятностных моделей сетевых систем. // Некоторые вопросы кибернетики. М.: Изд-во МИФИ, 1970. - Вып. 1.

21. Поспелов Д.А. Вероятностные автоматы. М.: Энергия, 1970. - 88 с.

22. Лоренц А.А. Надёжность и быстродействие вероятностных автоматов. Рига: "Зинатне", 1976. - 112 с.

23. Левин Б.Р., Шварц В. Вероятностные модели и методы в системах связи и управления. М.: Радио и связь, 1985. - 312 с.

24. Бзгхараев Р.Г. Проблемы синтеза вероятностных преобразователей. -Рига: Зинатне, 1971. С.

25. Бухараев Р. Г., Геза В.И. Специализированная ЭВМ для моделирования и обработки функций конечных однородных цепей Маркова. // Тезисы докл. Всес. симп. по вероятностным автоматам. Казань.: Изд-воКГУ, 1969.-С. 14-15.

26. Гилл А. Синтез вероятностных преобразователей. // Кибернетический сборник. М.: Мир, 1964. - №8.

27. Церцвадзе Г.Н. Некоторые свойства и методы синтеза стохастических автоматов. // Автоматика и телемеханика. 1963. - Т. 24. - № 3.

28. Мубаракзянов Р.Г. Автоматное преобразование случайных последовательностей с конечным множеством состояний. // Тезисы научно-технической конференции «Вероятностные автоматы и их приложения». Тбилиси: Мецнеереба, 1986. - С. 12.

29. Murray I.E. Consideration of Assumption. "IEEE Trans. Egng Manag." Vol.,N3,1963, pp. 94-99.

30. Davis A.S. Markov chains as random input outomata. Amer. Math. Monthly, 1961, 68, 3, pp. 264-267.

31. Wing O., Demetrions P. Analysis of probabilistic networks. IEEE trans, commun. techn., 1964, volume 12, N 3.

32. Booth J.L. Random input automata. Ln: JCMCL Conf, Tokyo, 1964.

33. Paz A. Introduction to probabilistic automata. N V, Academic Press., 1971.

34. Marsaglia G.Generating discrete random variables in a computer. // Communs ACM, 1963, v. 6, N 1, pp. 37-38.

35. James F. A review of pseudo-random number generators. // Comput. Phys. Commun., 1990, 60, N 3, pp. 329-344.

36. Kramosil J. Algorithmic complexity and pseudo-random sequences. // Trans. 10* Prague Conf on Inf Theory, Statist. Decis. Funct., Random Process. Prague, July 7-11, 1986. Vol. A. Prague, 1988, pp. 55-72.

37. Айзенберг H.H., Семион И.В., Циткин А.И. Полиномиальные представления логических функций. // Автоматика и вычислительная техника. -1971. №2. - С. 6 - 13.

38. Paz А. Whirl decomposition or stochastic automata. Technical Kept., 1970, №8.

39. Гиоргадзе A.X., Сафиуллина А.Г. О декомпозиции вероятностных автоматов // Кибернетика. 1975. - №2.

40. Гиоргадзе А.Х. Некоторые методы пространственно-временной декомпозиции вероятностных автоматов // Докл. АН СССР. 1977. - Т. 232. - №4.

41. Лидл Р., Нидеррайтер Г. Конечные поля. В 2 т. М.: Мир, 1988.

42. Латыпов Р.Х., Нурутдинов Ш.Р., Столов Е.Л., Фараджев Р.Г. Применение теории линейных последовательных машин в системах диагностики // Автоматика и телемеханика. 1988. - №8. - С. 3-27.

43. Латыпов Р.Х. Периодические последовательности, порождаемые регистрами сдвига с нелинейной обратной связью // Изв. вузов. Математика. №5.- 1989.-С. 5-13.

44. Харчистов Б.Ф., Финаев В.И. Устройство для умножения в конечных полях.//А.с. 2802836/18-24. -БИ №15, 1981.

45. Сюрин В.П., Иванов Н.Н., Альхимович В.В. Реализация вычислений в конечных полях. // Зарубежная радиоэлектроника. №5. - 1990.

46. Бояринов И.М. О систолических и полусистолических вычислениях в GF(2'"). // Вопросы кибернетики. Разработка и использование СУПЕР-ЭВМ. М.: Наука, 1987. - С. 183-190.

47. A.c. 1672438. Устройство для умножения двух элементов конечного поля GF(2") / Нурутдинов Ш.Р., Столов Е.Л. Опубл. в БИ, 1991. -№31.

48. Нурутдинов Ш.Р., Столов Е.Л. Перестраиваемые схемы в системах встроенного тестирования. // Автоматика и телемеханика. 1995. -№3-С. 179-183.

49. Нурутдинов Ш.Р., Столов Е.Л. Реализация автомата асинхронной сетью. // Кибернетика. Киев, 1988. - №6. - С. 108-109.

50. Захаров В.М., Столов Е.Л., Баранов Г.Г., Комаров Ю.С. Генерирование псевдослучайных сигналов с марковскими свойствами // Тезисы докладов на конференции «Синтез и анализ цифровых алгоритмов обработки сигналов». Новгород, 1981.

51. Захаров В.М. Моделирование сложных цепей Маркова конечным детерминированным автоматом // Тезисы докладов III Всесоюзного симпозиума по вероятностным автоматам. Казань; Изд-во КГУ, 1983.-25 с.

52. Захаров В.М. Представление вероятностных автоматов некоторыми моделями орграфов // Тезисы докладов конф. «Математические методы в задачах исследования сложных систем». Пенза, 1984. - С. 44-45.

53. Захаров В.М. Моделирование 1-сложных цепей Маркова конечным детерминированным автоматом // Кн. Вероятностные автоматы и их приложения. Казань: Изд-во КГУ, 1986. - С. 155-161.

54. Захаров В.М., Баранов Г.Г. Синтез циклических многозначных последовательностей с заданной структурой // Тезисы межреспубликанской н.-т. конф. Вероятностные автоматы и их приложения. Батуми: Мецниереба, 1986. - С. 24.

55. A.c. 943722 СССР. Генератор псевдослучайных чисел / Захаров В.М, Баранов Г.Г., Комаров Ю.С., Столов Е.Л. // Б.И. 1982. - № 26.

56. A.c. 1108614 СССР. Генератор случайных последовательностей / Захаров В.М, Баранов Г.Г., Комаров Ю.С., Латыпов Р.Х., Столов Е.Л. //Б.И. 1984.-№30.

57. A.c. 1224992 СССР. Генератор псевдослучайных чисел / Захаров В.М, Баранов Г.Г., Комаров Ю.С., Латыпов Р.Х., Столов Е.Л. // Б.И. 1986.-№14.

58. A.c. 1327099 СССР. Генератор случайных последовательностей / Захаров В.М, Баранов Г.Г. // Б.И. 1987. - № 28.

59. A.c. 1275434 СССР, МКИ С 06 Г 7/58. Генератор случайной последовательности / Песошин В.А., Кузнецов В.М., Сергеев H.H., Данин О.И., Галеев И.К., Иванов Г.Н., Сафонов В.Л. // Открытия, изобретения. 1986.-№ 45. - С. 167.

60. A.c. 664185 СССР. Генератор случайных чисел / Песошин В.А, Тарасов В.М., Мансуров P.M. // Открытия, изобретения. 1979. - № 19.

61. A.c. 1137477 СССР. Устройство для моделирования марковских потоков сигналов / Финаев В.И., Минаев Г.А.// Открытия, изобретения. 1985. - №4.

62. A.c. 526909 СССР. Устройство для моделирования марковских процессов / Добрыдень В.А. // Открытия, изобретения. 1976. - № 32.

63. А.с. 746479 СССР. Устройство для формирования марковских процессов / Филаретов Г.Ф., Глазунова Н.А., Богданов СВ., Качанов А.Л. // Открытия, изобретения. 1980. - № 25.

64. H.F.Li, RJayakumar and CLow. Restructuring for Fault-Tolerant Systolic Arrays // IEEE Trans, on computer, vol. 38. № 2, February 1989.

65. Jagma Sh., Aramaki T. Autonomously testable programmable logic arrays // Int. Simp, on FICS, Portland. June 1981. P. 41-43.

66. W.Daehn and J.Mucha. A hardware approach to self-testing of large programmable logic arrays // IEEE Trans. Comput., vol. C-80, N 11, pp. 829-833, Nov. 1981.

67. Словарь no кибернетике / Под ред. Академика В.С.Михалевича. -Киев: Главная редакция Украинской Советской Энциклопедии им. М.П.Бажана, 1989. 751 с.

68. Основы теории однородных структур / Б.Б. Кудрявцев, А.С Под-колзин, А.А. Болотов. М.: Наука, 1990. - 293 с.

69. Растригин Л.А., Рипа К.К. Автоматная теория случайного поиска. -Рига : «Зинатне», 1973. 342 с.

70. Мальцев П.П. и др. Программируемые логические ИМС на КМОП-структурах и их применение. М.: Энергоатомиздат, 1998.

71. Xilinx. The Programmable Logic Data Book 1998, Copyright 1998 Xilinx, Inc., Printed in U.S.A.

72. Пономарёв В.И., Шабалин Л.А. Проектирование реконфигурируе-мых устройств обработки цифровых потоков данных. // Информационные технологии. 1996. - №5. - С. 24-28.

73. Березнев А.Г. и др. Применение программируемых логических интегральных схем архитектуры FPGA в проектировании средств вычислительной техники. // Информационные технологии. 1996. -№1.-С. 34-37.

74. D. Runje and M. Kovac, «Universal Strong Encryption FPGA Core Implementation», in Proceedings of Design, Automation, and Test in Europe, (Paris, France), pp. 923-924, February 1998.

75. A. Elbirt, «An FPGA Implementation and Performance Evaluation of the CAST-256 Block Cipher», Technical Report, Cryptography and Information Security Group, ECE Department, Worcester Polytechnic Institute, Worcester, Massachusetts, USA, May 1999.

76. H. Wu, «Low complexity bit-parallel finite field arithmetic using polynomial basis», in Workshop on Cryptographic Hardware and Embedded Systems (CHES '99) (C. Кос and C. Paar, eds.), vol. LNCS 1717, Springer-Verlag, August 1999.

77. M. Riaz and H. Heys, «The FPGA Implementation of RC6 and CAST-256 Encryption Algorithms)), in Proceedings of IEEE Canadian Conference on Electrical and Computer Engineering CCECE'99, (Edmonton, Alberta, Canada), May 1999.

78. A. Elbirt and C. Paar, «Towards an FPGA Architecture Optimized for Public-Key Algorithms)), in The SPIE's Symposium on Voice, Video, and Data Communications, (Boston, MA), September 19-22 1999.

79. G. Orlando and C. Paar. An Efficient Squaring Architecture for GF(2"') and its Applications in Cryptographic Systems. Electronic Letters, June 2000, vol. 36, no. 13, pp. 1116-1117.

80. G. Orlando and C. Paar. A High-Performance Reconfigurable Elliptic Curve Processor for GF(2"'). Workshop on Cryptographic Hardware and

81. Embedded Systems (CHES) 2000, Springer-Verlag, Lecture Notes in Computer Science 1965, 2000.

82. C. Paar, P. Fleischmann, and P. Soria-Rodriguez. Fast arithmetic for public-key algorithms in Galois fields with composite exponents. IEEE Transactions on Computers, 48(10):1025-1034, October 1999.

83. Захаров B.M., Нурутдинов Ш.Р., Шалагин СВ. Полиномиальное представление цепей Маркова над полем Галуа // Вестник Казанского государственного технического университета. Казань: Изд-во КГТУ им. А.Н.Туполева, 2001. - №3. - С.

84. Шалагин СВ. Кластерный анализ стохастических эргодических матриц. Деп. в ВИНИТИ 31.10. 00., № 2750 - BOO. - 42 с.

85. Ким Дж.-О и др. Факторный, дискриминантный и кластерный анализ. М.: Финансы и статистика, 1989. - 215с.

86. Дюран Б., Оделл П. Кластерный анализ. М.: «Статистика», 1977. -128с.

87. Айвазян С.А., Бежаева З.И., Староверов О.В. Классификация многомерных наблюдений.-М.: Статистика, 1974. 240 с.

88. Боровиков В.П., Боровиков И.П. Statistica Статистический анализ и обработка данных в среде Windows - M.: Изд-во «Филинъ», 1997. -600с.

89. Нурутдинов Ш.Р., Шалагин СВ. Минимизация количества элементов однородной вычислительной структуры. // Сб. «Исследования по информатике». Вып. 2. Научно-практическое издание. Институт проблем информатики АН РТ. Казань: Отечество, 2000. - С. 117124.

90. Нурутдинов Ш.Р., Шалагин СВ. Вычисление произведения элементов поля Галуа. // Теория сеточных методов для нелинейных краевых задач. Материалы третьего Всеросс. семинара. Казань: Изд-во Казанского мат. общества, 2000. - С. 144.

91. Шалагин СВ. Синтез генераторов тестов в базисе программируемых логических интегральных схем // Тезисы докладов «Актуальные проблемы авиастроения» VIII Всероссийские Туполевские чтения студентов Казань, 1998. - С. 70.

92. Шалагин СВ. Система анализа и синтеза вероятностных сетей // Тезисы докладов «Актуальные проблемы авиастроения» VIII Всероссийские Туполевские чтения студентов Казань, 1998. - С. 80.

93. Шалагин СВ. Моделирование конечнозначных случайных последовательностей на линейных автоматах // Тезисы докладов. Международная молодёжная научная конференция «XXV Гагаринские чтения». -М.: Изд-во «Латмэс», 1999. С. 179-180.

94. Глова В.И., Захаров В.М., Песошин В. А., Шалагин СВ. Моделирование. Дискретные вероятностные модели. Учебное пособие. Казань: Изд-во АБАК, 1998. - 50 с.

95. Ю.Фёдоров Р.Ф., Яковлев В.В., Добрис Г.В. Стохастические преобразователи информации. Л.: Машиностроение, 1978. - 304с.

96. ТКемени Дж. Снёлл Дж. Конечные цепи Маркова. М. Наука, 1970.

97. Кирьянов Б.Ф. Основы теории стохастических вычислительных машин и устройств. 1976. - Деп. ЦНИИГЭ приборостроения, № 524. - 168с.

98. ИЗ.Захаров В.М. Аппаратно-программная организация специализированных процессоров на основе автономных вероятностных автоматов: Дис. д-ра. техн. наук. Казань. - 1992.

99. А.С. 1524046 СССР. Генератор случайных чисел. / Бухараев Р.Г., Захаров В.М., Баранов Г.Г., Комаров Ю.С, Кузнецов С.Е., Макаров И.И., Пермитин В.В. //Б.И. 1983. - №43.

100. Гилл А. Линейные прследовательностные машины. М.: Наука, 1974. - 288 С.116. lows В.А., Rushforth СК. А cellular-array multiplier for GF(2'"). -IEEE Trans. Comput., 1971, v.C-20, №12, ppl573-1578.

101. Paar C, Fleishmann P., Roelse P, Efficient Multiplier Architectures for Galois Fields GF((2A)"), IEEE Trans. Computers, vol 47, no 2, pp. 162170, Febr. 1998.llS.Trion R.G. Cluster analysis. L.: Ann Arbor Edwards Bros. - 1939. - 139 P

102. Мандель И.Д. Кластерный анализ. М.: Финансы и статистика, 1988.- 176 с.

103. Лоренц A.A. Синтез надёжных вероятностных автоматов. Рига: "ЗинатнеМ975.-- 168 с.

104. Ланкастер П. Теория матриц. Перевод с англ. М.: Наука, 1982. -272с.

105. Феррари Д. Оценка производительности вычислительных систем, -М.: Мир, 1981.-576с.

106. Нурутдинов Ш.Р. Реализация комбинационной схемы при помощи многочлена от нескольких переменных над конечным полем. // Тезисы докладов VIII Всесоюзной конференции по теоретической кибернетике. Горький, июль 1988. - Часть 2. - С. 61-62.

107. Нурутдинов Ш.Р. Обеспечение отказоустойчивой сетевой модели автомата. // Исследования по прикладной математике. Вып. 16. Казань: Изд-во Казанского ун-та. 1989. - С. 138-144.

108. Гери М., Джонсон Д. Вычислительные мащины и труднорещаемые задачи. М.: Мир, 1982.

109. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. Уч пособие. М.: Наука, 1984.

110. Киносита К., Асада К., Карацу О. Логическое проектирование СБИС. / Пер. с японского Д.А. Ковтуна и к.т.н. Поспелова Л.В. Под ред. К.т.н. Поспелова Л.В. М.: Мир, 1988. - 310 с.

111. Раскин Л.Г. Анализ сложных систем и элементы теории оптимального управления. М.: Сов. радио, 1976. - 344 с.

112. Хинчин А.Я. Понятие энтропии в теории вероятностей. // Успехи математических наук. 1953. - №3 (55). - С. 3 - 20.175

113. Николь Н. Альберт Р. Электронные таблицы Excel 5.0 для квалифи цированных пользователей: Практическое пособие / Пер. с нем. М.:ЭКОМ., 1995.-304 с: ил.

114. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. 476 с.

115. Полляк Ю.Г. Вероятностное моделирование на электронных вычис лительных машинах. М.: Советское радио, 1971. - 400 с.