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

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

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

ВВЕДЕНИЕ

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

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

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

§ 3. Полиномиальная модель простой однородной цепи 25 Маркова

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

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

ГЛАВА 2. Полиномиальное представление автоматных моделей марковских функций над полем Галуа

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

§ 2. Полиномиальные модели и структурные схемы генераторов марковских функций над полем Галуа

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

Марковские последовательности и их функции (марковские функции (МФ) [1-3]) широко используются для построения вероятностных моделей в таких областях как статистическое моделирование [4-9], распознавание автоматов [10-11], передача и защита информации, диагностика и анализ цифровых устройств [12-15] и др. Применение моделей цепей Маркова (ЦМ) в качестве базовых при построении вероятностных моделей автоматного типа, обуславливает интерес ученых к теории моделирования марковских последовательностей, функций конечных ЦМ и построению автоматных моделей генераторов ЦМ.

Использование моделей ЦМ дает возможность получить простое и адекватное описание широкого класса систем. Важностью прикладного значения объясняется большое число публикаций по теории моделирования марковских последовательностей и их функций и построению моделей генераторов ЦМ [1-4, 15-40]. Известен ряд работ по моделированию марковских последовательностей, основанных на автоматном представлении процессов этого класса [1-8, 15-21, 23-33]. При автоматном моделировании ЦМ конечная однородная цепь Маркова обычно представляется в виде конечного детерминированного автомата со случайным входом [29-30]. В работах [1-5, 8, 15, 20, 23, 26, 41] решены вопросы перехода от описания ЦМ в виде стохастической матрицы к описанию в виде стохастической линейной комбинации булевых стохастических матриц, определены условия автоматного преобразования случайных дискретных величин, предложены принципы построения управляемых генераторов случайных кодов, показано, что МФ можно рассматривать как процессы, порождаемые вероятностными автоматами [2-4, 19].

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

Увеличение быстродействия может быть достигнуто с помощью распараллеливания проводимых вычислений.

Одним из перспективных подходов построения автоматных моделей ЦМ, предложенных в последние годы, представляется подход, использующий теорию конечных полей. Этот подход позволяет синтезировать структурные модели генераторов конечных ЦМ, состоящие из однородных блоков, с векторной обработкой данных. Для реализации полученных моделей могут быть использованы технологии производства интегральных схем, например программируемые матрицы логических элементов (ПМЛЭ). Использование ПМЛЭ дает возможность синтезировать устройства с перестраиваемой структурой, что позволяет оперативно менять функциональные возможности вероятностных моделей и приводит к сокращению аппаратных затрат, а следовательно и стоимости разрабатываемого устройства.

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

Идея синтеза дискретных вероятностных моделей автоматного типа в однородных вычислительных средах получила развитие в работах [3, 20, 22, 28, 42-43], а использования арифметики конечных полей [44] для синтеза детерминированных цифровых устройств в однородных структурах в [37, 45-52]. Известны также решения задачи построения генераторов равномерно распределенных случайных и псевдослучайных чисел в поле Га-луа [12, 17-18,53-61].

Большое число публикаций посвящено решению задачи разработки архитектуры схемы умножения элементов поля Галуа для реализации в однородных вычислительных средах, а также решению задачи уменьшения вычислительной сложности схем умножения [62-71], так как вычислительная сложность, при использовании технологии производства интегральных схем, может служить оценкой необходимой площади кристалла [71].

Известно решение задачи построения автоматных моделей генераторов ЦМ в базисе полиномиальных функций над полем Галуа [72-73]: предложены полиномиальная модель и структурная схема генератора простых однородных ЦМ над GF{2")\ предложены альтернативные (по критериям сложности и быстродействия) структурные схемы - параллельного, систолического векторного, систолического и последовательностного типов — для реализации генераторов ЦМ в базисе полиномиальных функций; показана адекватность структуры модели генератора ЦМ над полем Галуа, состоящей из однородных блоков, структуре ПМЛЭ класса FPGA (Field Programmable Gate Array); показано, что аппарат полей GF(2") является эффективным инструментом для синтеза генераторов ЦМ в виде однородных структур.

В связи с отмеченным выше актуальной является задача развития предложенного в работах [72-73] подхода моделирования конечных ЦМ над полем GF(2"): построение полиномиальных моделей для более широкого класса случайных дискретных процессов и представление структурных схем генераторов МФ над полем GF{2"). В прикладном отношении актуальной является задача повышения эффективности предложенного подхода, с целью сокращения используемой площади кристалла и увеличения быстродействия синтезируемых устройств.

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

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

1. разработка полиномиальных моделей случайных процессов, являющихся функциями ЦМ, над полем 2");

2. разработка структурных моделей генераторов МФ над полем 6^(2");

3. исследование возможности применения полей Галуа при реализации автономных вероятностных автоматов с динамически изменяемой стохастической матрицей;

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

5. разработка методики анализа моделей генераторов МФ на основе многомерного статистического анализа для выявления степени различия заданных характеристик рассматриваемых генераторов, их идентификации и тестирования;

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

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

1. Предложены полиномиальные модели случайных процессов вида МФ над полем Галуа из класса, порождаемого автономными вероятностными автоматами с заданными ограничениями на функции перехода и выхода, в частности модели сложных ЦМ, марковского источника и конечноавтоматных случайных последовательностей. Модели МФ представлены в виде суперпозиций полиномиальных функций от одной и двух переменных над полем СР(2").

2. Предложены структурные схемы генераторов МФ на основе полученных полиномиальных моделей над полем СР(2п).

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

I я

4. Предложены алгоритм построения составных полей ^/^((2 ) ),изо

О Ь морфных полю С/<\2 ), и методика построения схем умножения в

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

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

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

Предложенные полиномиальные модели генераторов МФ позволяют использовать аппарат полей Галуа при моделировании рассматриваемых случайных процессов, что дает возможность представить их в виде алгебраических выражений, допускающих параллельную реализацию. Предложенные структурные схемы генераторов МФ над полем СР\2") дают возможность их непосредственного использования при проектировании специализированных автоматных моделей. Предложенная методика построе

2' ния схем умножения в составных полях вида С/^2 ) позволяет сократить необходимую для реализации умножения вычислительную сложность, а рассчитанные по предлагаемой методике схемы умножения могут быть использованы в качестве базовых блоков в широком классе устройств, применяющих алгебру полей Галуа. Разработанная методика многопараметрической классификации и идентификации стохастических матриц и случайных последовательностей позволяет определить степень сходства заданных статистических характеристик различных классов рассматриваемых случайных процессов, оценить их качество (в статистическом смысле). Предложенная методика может быть применена для задач идентификации более широкого класса (идентификация вида генератора псевдослучайной последовательности, шифра и т.д.).

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

Апробация результатов работы.

Основные результаты работы докладывались и обсуждались на итоговой университетской научно-технической конференции студентов КГТУ им. А. Н. Туполева (Казань, 1999г.); научно-технической конференции «IX Всероссийские Туполевские чтения студентов» (Казань, 2000г.); научно-практической конференции по актуальным вопросам информатики, вычислительной техники и информационной безопасности (Казань, 2001г.); Четвертом Всероссийском семинаре «Сеточные методы для краевых задач и приложения» (Казань, 2002г.); научной конференции «Юбилейные X Всероссийские (с международным участием) Туполевские чтения студентов» (Казань, 2002г.); XIII Международной конференции «Проблемы теоретической кибернетики» (Казань, 2002г.); V Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, 2002г.); итоговой научной конференции Казанского государственного университета (Казань, 2002г.); Двенадцатой Международной конференции по вычислительной механике и современным прикладным программным системам (Владимир, 2003г.); городском семинаре «Методы моделирования» (Казань, 2002-2003гг.), ряде семинаров кафедры Теоретической кибернетики Казанского государственного университета (Казань, 2001-2003гг.), VIII Международном семинаре «Дискретная математика и ее приложения» (Москва, 2004г.).

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

1. полиномиальные модели МФ над полем GF(2n)\

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

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

4. алгоритм построения составного поля вида GF((2 ) ), изоморфного полю вида GF(22k);

5. методика построения схем умножения в составных полях Галуа, позволяющая сократить вычислительную сложность и повысить скорость выполнения операции умножения;

6. методика статистического анализа моделей генераторов МФ на основе методов многомерной математической статистики;

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

Основное содержание диссертации опубликовано в 16 работах, включая 6 статей [74-79] и 10 тезисов докладов[80-89].

Структура и объем работы.

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

Результаты работы [70] представлены в виде табл. 4.4 — 4.5.

ЗАКЛЮЧЕНИЕ Основные результаты диссертационной работы:

1. Получены полиномиальные модели случайных процессов из класса МФ на основе суперпозиции полиномиальных функций над полем Галуа

GF{2"). Адекватность предложенных полиномиальных моделей и методика их построения обоснована соответствующими теоремами.

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

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

Предложены структурные схемы генераторов над полем GF{2") для формирования рассматриваемых последовательностей.

I л

4. Предложен алгоритм построения составных полей вида GF((2 ) ),

О h изоморфных полю вида G F {2 ).

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

21 ножения в составных полях GF(2 ), / = 2,3, являющейся базовой операцией при реализации полиномиальных моделей генераторов МФ. Получены соответствующие оценки, показывающие, что предложенные схемы умножения превосходят известные аналоги, как по быстродействию, так и по вычислительной сложности.

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

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

Результаты диссертации использованы в НИР за 2001-2003гг. по гранту РФФИ № 99-01-00163 «Энтропийно-сложностные свойства дискретных вычислительных моделей», по гранту РФФИ № 03-01-00769 «Сложност-ные свойства классических и квантовых вычислений», по проекту № 01504-01-52 «Синтез и сложность детерминированных и вероятностных дискретных вычислительных моделей» программы «Университеты России», в ОАО «КНИАТ» (г. Казань), в Центре новых информационных технологий Республики Татарстан (г. Казань), в ГИБДД МВД Республики Татарстан (г. Казань) и в учебном процессе кафедры Компьютерных систем и информационной безопасности КГТУ им. А.Н. Туполева (КАИ).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19. Альпин Ю.А., Захаров В.М. Моделирование случайных последовательностей автономными автоматными схемами // Вероятностные автоматы и их приложения. Казань: Изд-во Казан, ун-та, 1986. С. 2229.

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

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

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

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

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

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

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

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

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

29. Murray I.E. Consideration of Assumption. "IEEE Trans. Egng Manag." Vol., N 3, 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. 10th Prague Conf. on Inf. Theory, Statist. Decis. Funct., Random Process. Prague, July 7-11, 1986. Vol. A. Prague, 1988, pp. 55-72.

37. Столов ЕЛ. Об одном классе генераторов псевдомарковских цепей // Исследования по прикладной математике. Казань: Изд-во Казан, ун-та, 1985. Вып. 8. С. 66-71.

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

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

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

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

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

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

44. Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т. Пер. с англ. М.: Мир, 1988.

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

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

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

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

49. С. Paar. A new architecture for a parallel finite field multiplier with low complexity based on composite fields. IEEE Trans, on Computers, 45(7):856-861, July 1996.

50. H.F.Li, R.Jayakumar and C.Low. Restructuring for Fault-Tolerant Systolic Arrays // IEEE Trans, on computer, vol. 38. № 2, February 1989.

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

52. 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.

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

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

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

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

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

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

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

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

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

62. Т. Itoh and S. Tsujii. Structure of parallel multipliers for a class of fields GF(2k). Inform, and Сотр., 83:21-40, 1989.

63. E.D. Mastrovito. VLSI design for multiplication over finite fields GF(2m). In Lecture Notes in Computer Science 357, pages 297-309. Springer-Verlag, Berlin, March 1989.

64. M.A. Hasan, M. Wang, and V.K. Bhargava. Division and bit-serial multiplication over GF(qm). IEEE Trans, on Computers, 41(8):972-980, August 1992.

65. M.A. Hasan, М. Wang, and V.K. Bhargava. Modular construction of low complexity parallel multipliers for a class of finite fields GF(2m). IEEE Trans, on Computers, 41(8):962-971, August 1992.

66. S.T.J. Fenn, M. Benaissa, and D. Taylor. GF(2m) multiplication and division over the dual base. IEEE Trans, on Computers, 45(3):319-327, March 1996.

67. Захаров B.M., Нурутдинов Ш.Р. Шалагин С.В. Аппаратная реализация умножения элементов поля Галуа на программируемых микросхемах архитектуры FPGA // Вестник Казан, гос. техн. ун-та им. А.Н. Туполева. 2001. №1. С. 36-41.

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

69. Рааг С., Fleishmann P., Roelse P. Efficient Multiplier Architectures for Galois Fields GF((24)") // IEEE Trans. Computers. 1998. № 2. Vol. 47. P. 162-170.

70. C. Paar and N. Lange. A comparative VLSI synthesis of finite field multipliers. In 3rd International Symposium on Communication Theory and its Applications, Lake District, UK, July 10-14 1995.

71. Захаров B.M., Нурутдинов Ш.Р., Шалагин С.В. Полиномиальное представление цепей Маркова над полем Галуа // Вестник Казан, гос. техн. ун-та им. А. Н. Туполева. 2001. JST» 3. С. 27-31.

72. Захаров В.М., Нурутдинов Ш.Р., Шалагин C.B. Синтез автономных вероятностных автоматов на основе полей Галуа // Исследования по информатике. Вып. 2. Казань: Отечество, 2000. С. 107-116.

73. Захаров В.М., Нурмеев H.H., Салимов Ф.И., Соколов С.Ю., Шалагин C.B. К задаче дискриминантного анализа автоматных марковских моделей // Вестник Казан, гос. техн. ун-та им. А.Н. Туполева. 2001. №3. С. 37-39.

74. Нурутдинов Ш.Р., Соколов С.Ю., Шалагин C.B. Синтез автоматных моделей цепей Маркова и их функций в конечных полях // Труды V Междунар. конф. «Новые информационные технологии и системы». Пенза: Изд-во Пензенск. ун-та, 2002. С. 211-213.

75. Захаров В.М., Нурутдинов Ш.Р., Соколов С.Ю., Шалагин C.B. Полиномиальное представление конечноавтоматных случайных последовательностей над полем Галуа // Вестник Казан, гос. техн. ун-та им. А.Н. Туполева. 2003. -№ 2. - С. 24-28.

76. Соколов С.Ю. Автоматное моделирование случайных процессов с последействием на основе эйлеровых стохастических матриц // Вестник Казан, гос. техн. ун-та им. А.Н. Туполева. 2003. - № 2. — С. 58-62.

77. Соколов С.Ю. К задаче анализа свойств псевдослучайных бинарных последовательностей // Тезисы докладов. «Итоговая университетская научно-техническая конф. студентов» КГТУ им. А. Н. Туполева.-Казань, 1999.-С. 33.

78. Соколов С.Ю. К задаче анализа и синтеза эйлеровых многозначных последовательностей // Тезисы докладов. IX Всероссийские Тупо-левские чтения студентов: Научно-техническая конф. Казань, 2000. - Т 2. - С. 40.

79. Захаров В.М., Нурмеев Н.Н., Салимов Ф.И., Соколов С.Ю., Шалагин C.B. Многомерный статистический анализ автоматных моделей марковского типа // Тез. докл. XIII Междунар. конф. «Проблемы теоретической кибернетики». М.: Изд-во МГУ, 2002. 4.1. С.69.

80. Захаров В.М., Нурутдинов Ш.Р., Шалагин C.B., Соколов С.Ю. Представление марковских функций над полем Галуа // Тез. докл. XIII Междунар. конф. «Проблемы теоретической кибернетики». М.: Изд-во МГУ, 2002. 4.1. С.71.

81. Соколов С.Ю. Моделирование псевдослучайных последовательностей на основе эйлеровых стохастических матриц // Тез. докл. XIII Междунар. конф. «Проблемы теоретической кибернетики». М.: Изд-во МГУ, 2002. 4.2. С.170.

82. Галлагер Р. Теория информации и надежная связь. М.: Сов. радио, 1974.

83. Альпин Ю.А., Захаров В.М. Теоретико-автоматный метод описания и моделирования случайных процессов // Вероятностные методы и кибернетика. Вып. 19. Казань: Изд-во Казан, ун-та, 1983. С. 10-16.

84. D.H. Green and I.S. Taylor. Irreducible polynomials over composite Galois fields and their applications in coding techniques. Proc. IEE, 121(9):935-939, September 1974.

85. Математика. Большой энциклопедический словарь / Главный ред. Ю.В. Прохоров. М.: Большая Российская энциклопедия, 2000. — 848 с.

86. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.

87. Ким Дж.-О., Мьюллер Ч.У., Клекка У.Р., Олдендерфер М.С., Блэш-филд Р.К. Факторный, дискриминантный и кластерный анализ / Пер. с англ. Под ред. И.С. Енюкова. М.: Финансы и статистика, 1989. -215с.

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

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

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

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

92. ЮО.Романовский В.И. Дискретные цепи Маркова. M.-JI.: Гостехиздат, 1949.-436 с.

93. Кемени Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука, 1970. -272 с.

94. Лоренц А.А. Синтез надёжных вероятностных автоматов. Рига: «Зинатне», 1975. - 168 с.

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

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

97. Мубаракзянов Р.Г. Автомат, оставляющий инвариантным класс случайных последовательностей с конечным множеством состояний // Математика. 1985. №7. С. 21 25. (Изв. высш. учеб. заведений).

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

99. Шалагин C.B. Марковские автоматы над полем Галуа и их моделирование в базисе программируемых матриц логических элементов: Дисс. кандидата техн. наук. Казань, 2001. - 175 с.

100. Боровиков В. П. Популярное введение в программу «STATISTICA».- М.: КомпьютерПресс, 1998.

101. Турин В.Я. Передача информации по каналам с памятью. М.: Связь, 1977.

102. Ю.Карлайл Е.У. Приведенные формы стохастических последовательностных машин // Кибернетический сборник. Вып. 3. М: ИЛ, 1966. С. 101-110.

103. Кознов A.B. Процессы авторегрессии над полем GF(1) II Прикладная математика. Межвуз. сб. / Новгородск. гос. ун-т. Новгород, 1994. Вып. 1.С. 20-23.

104. Нурутдинов Ш.Р. Умножение в поле Галуа GF(16) в базисе поля GF(4). // Сборник трудов IX Всероссийской школы-семинара «Современные проблемы математического моделирования». Ростов-на-Дону: Изд-во Ростовского гос. ун-та, 2001. С. 272-274.

105. Пб.Феллер В. Введение в теорию вероятностей и ее приложения. М.: Мир, 1984. Т. 1.

106. Zacharov V.M., Kuznetsov S.E. Complexity of the problem of approximation of stochastic matrix by rational elements // International Conference FCT'87. Kazan, June 1987. Springer-Verlag Berlin, 1987. Vol. 278. P. 483-487.

107. Баранов Г.Г., Захаров B.M., Кузнецов C.E. Синтез циклических многозначных последовательностей с заданной структурой // Кибернетика. 1989. № 1.С. 15-18.

108. Бурков В.Н., Горгидзе И.А., Ловецкий С.Е. Прикладные задачи теории графов / Под ред. А. Я. Горгидзе. Тбилиси: Мецнеереба, 1974. С. 76-80.

109. Бусленко Н.П., Шрейдер Ю.А. Метод статистических испытаний (Монте-Карло) и его реализация на цифровых вычислительных машинах. М.: Физматгиз, 1961.

110. Уиттл П. Вероятность. М.: Наука, 1982.

111. Вероятностное прогнозирование в деятельности человека / Под ред. И.М. Фейгенберга, Г.Е. Журавлева. М.: Наука, 1977.

112. A. J. Menezes, Р. С. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997.

113. C.C. Wang and D. Pei. A VLSI design for computing exponentiation in GF(2m) and its application to generate pseudorandom number sequences. IEEE Trans, on Computers, C-39(2):258-262, Febr. 1990.

114. S.B. Wicker and V.K. Bhargava, editors. Reed-Solomon Codes and Their Applications. IEEE Press, 1994.

115. Кнут Д.Э. Искусство программирования для ЭВМ. Получисленные алгоритмы. Т. 2. М.: Мир, 1976.

116. Болотов A.A., Гашков С.Б., Фролов А.Б., Часовских A.A. Алгоритмические основы эллиптической криптографии. М.: МЭИ, 2000.128.3ензин О.С., Иванов М.А. Стандарт криптографической защиты — AES. Конечные поля / Под ред. М.А. Иванова М.: КУДИЦ-ОБРАЗ, 2002.

117. Xilinx. The Programmable Logic Data Book 1998, Copyright 1998 Xil-inx, Inc., Printed in U.S.A.

118. 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.

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

120. Захаров B.M., Нурмеев H.H., Салимов Ф.И., Шалагин C.B. Классификация стохастических эргодических матриц методами кластерного и дискриминантного анализа // Исследования по информатике. Казань: Отечество, 2000. Вып. 2. С. 91-106.