Содержание к диссертации
Введение
1. Кольцевые генераторы 30
1.1. Частотный подход к анализу кольцевых генераторов 31
1.2. Временной анализ моделей кольцевых генераторов 36
1.2.1. Анализ генератора-повторителя 36
1.2.2. Анализ генератора-инвертора 42
1.2.3. Сравнительный анализ кольцевых генераторов 47
Выводы по главе 1 49
2. Оценка статистических характеристик сигналов во временной области 51
2.1. Общие замечания о статистическом анализе случайных и периодических процессов 52
2.2. Условия баланса значений периодических корреляционных функций 54
2.3. Особые значения периодических корреляционных функций 55
2.3.1. Особенности АКФ периодических последовательностей 56
2.3.2. Особенности АКФ инверсно-сегментных последовательностей 58
2.3.3. Особенности ВКФ периодических последовательностей 62
Выводы по главе 2 66
3. Генераторы псевдослучайных последовательностей 68
3.1. Типичные построения ГПСП и их алгебраическое описание 70
3.2. Циклические свойства ЛПМ с учетом действия констант 74
3.2.1. Анализ циклических свойств посредством производящей функции 76
3.2.2. Анализ циклических свойств посредством характеристического многочлена для случая однородных ЛРП.. 79
3.2.3. Анализ циклических свойств для случая неоднородных ЛРП 81
3.3. Генератор Фибоначчи. Свойства псевдослучайных последовательностей 86
3.3.1. М-последовательность 86
3.3.2. М--последовательность 88
3.3.3. М-3 последовательность 94
3.4. Генератор Галуа. Последовательности состояний ГПСП 101
3.4.1. Характеристический многочлен неприводим и примитивен . 101
3.4.2. Характеристический многочлен \|/(*) = (іЄ*)\|/'(*) 106
3.4.3. Характеристический многочлен \|/(JC) = (1JC)V'M 109
3.4.4. Особенности решения системы линейных уравнений в классе переключательных функций 112
Выводы по главе 3 114
4. Асинхронные элементы задержки цифровых генераторов 115
4.1. Задержки элементов асинхронных цифровых устройств 115
4.1.1. Чистая задержка 116
4.1.2. Модель элемента инерциальной задержки 120
4.1.3. Передаточно-временные характеристики моделей инерциальной задержки 129
4.2. Стохастические свойства временных задержек 137
4.2.1. Вероятностные характеристики задержек групп элементов 139
4.2.2. Экспериментальные оценки средних задержек 142
4.2.3. Методы фазового сканирования для оценки величин временных флуктуации 145
4.2.4. Оценка величин временных флуктуации элементов БИС методом тепловой нестационарности 149
Выводы по главе 4 157
5. Генераторы асинхронных случайных процессов 159
5.1. Типичные структуры автоматных моделей ГАСП 161
5.2. Значения задержек соизмеримы, временных флуктуации нет 164
5.3. Значения задержек несоизмеримы, временных флуктуации нет 165
5.3.1. Двумерная модель 166
5.3.2. Фрактальная размерность алгоритма двумерной модели 177
5.3.3. Многомерные модели 178
5.4. Влияние фильтрующих свойств АЭЗ 180
5.5. Значения задержек соизмеримы, временные флуктуации присутствуют 183
5.6. Значения задержек несоизмеримы, временные флуктуации присутствуют 186
5.6.1. Вероятностный автомат асинхронного типа 189
5.6.2. Марковская модель ГАСП 192
5.7. Условия генерации процесса 199
5.7.1. Отсутствие устойчивых состояний как условие генерации 201
5.7.2. Полностью и частично неустойчивые состояния 205
5.7.3. Блочная организация ГАСП 214
5.8. Анализ стохастических свойств элементарного цифрового генератора. Когерентный случай 216
5.8.1. Вероятностные свойства 219
5.8.2. Автокорреляционные свойства 222
5.8.3. Вероятностные свойства генераторов-инверторов 224
5.9. Краткие замечания о некогерентной фиксации сигнала элементарного цифрового генератора 231
5.10. Программное моделирование ГАСП 233
5.10.1. Влияние уровня временных флуктуации на периодические свойства ГАСП 237
5.10.2. Влияние фильтрующих свойств элементов на автокорреляционную функцию 239
5.10.3. Исследование вероятностных свойств 241
5.11. Физическое моделирование ГАСП 242
5.11.1. Исследование временного представления процессов, формируемых ГАСП 243
5.11.2. Эффекты синхронизации и самосинхронизации 244
5.11.3. Влияние базовых настроек структуры моделей на устойчивость формирования асинхронного процесса
5.11.4. Исследование статистических характеристик ГАСП 248
Выводы по главе 5 252
6. Основы построения генераторов случайных последовательностей на цифровых элементах задержки 254
6.1. Композиционное построение и свойства датчика случайных символов 254
6.1.1. ДСС как элементарный вероятностный автомат 255
6.1.2. Структурная схема 256
6.1.3. Вероятностные и корреляционные свойства 256
6.1.4. Свойство непредсказуемости 260
6.2. Синтез цепи обратной связи ГАСП 266
6.2.1. Схемотехническое представление ГАСП 266
6.2.2. Формирование контуров обратной связи на основе свойств базовых образующих многочленов 268
6.2.3. Максимизация плотности базовых образующих многочленов . 271
6.2.4. Методики настройки структуры ГАСП на максимально плотные базовые многочлены 276
6.3. Синтез ДСС 280
6.3.1. Цепи фиксации и съема символов 282
6.3.2. Эвристический синтез 285
6.3.3. Основы формального синтеза 290
6.3.4. Методика синтеза 294
6.4. Практические разработки генераторов 297
6.4.1. Датчики случайных символов на микросхемах малой степени интеграции 297
6.4.2. Генераторы случайных и псевдослучайных чисел на микросхемах большой степени интеграции 301
6.5. Нетипичные примеры реализации генераторов 316
Выводы по главе 6 318
Заключение 321
Список литературы 324
- Особенности АКФ инверсно-сегментных последовательностей
- Вероятностные характеристики задержек групп элементов
- Отсутствие устойчивых состояний как условие генерации
- Формирование контуров обратной связи на основе свойств базовых образующих многочленов
Введение к работе
Актуальность темы диссертации. При построении электронных устройств широкого и специального назначения часто требуется включение в состав основного оборудования генераторов случайных или псевдослучайных сигналов. Это аппаратура для статистического и имитационного моделирования, системы испытаний на надежность и помехоустойчивость, специальные средства измерения и тестирования, системы радио- и гидролокации. В настоящее время особенно актуальным является использование источников случайных сигналов для систем защиты информации в ЭВМ, телекоммуникационных и сетевых средствах, в частности, аппаратуре опознавания. Нетипичность подходов к синтезу таких источников и специфические технологии их производства в целом существенно усложняют выполнение проектов.
Традиционно сложилось разделение тематик по формированию случайных и псевдослучайных последовательностей.
Известны многочисленные публикации, посвященные вопросам анализа и построения устройств формирования дискретных случайных сигналов, в частности генераторов случайных последовательностей (ГСП), основанных на использовании сложных физических явлений. Среди отечественных авторов следует отметить М.П. Бобнева, который впервые обобщил опыт применения генераторов случайных сигналов. Заметный вклад в становление теории и практики применения физических ГСП внес A.M. Морозов. За последние 50 лет интерес к этой теме не снижается как у нас в стране, так и за рубежом. При этом основной технической проблемой является схемотехническая уникальность каждого аппаратного решения, требующая применения специфических компонентов, заметно усложняющих конструкцию и технологию изготовления изделий при недостаточно высоких качественных показателях и быстродействии.
В части исследования и аппаратного построения генераторов псевдослучайных последовательностей (ГПСП) следует отметить фундаментальные работы отечественных ученых - А.И. Алексеева, Л.Е. Варакина, В.Е. Гантмахера, Б.И. Глазова, В.И. Доценко, Н.Г. Дядюнова, М.А. Иванова, Р.Х. Латыпова, С.А. Осмоловского, А.И. Сенина, Г.И. Тузова, Р.Г. Фа-раджева, А.Г. Шереметьева, а также зарубежных - А. Гилла, СВ. Голомба, Г. Нидеррайтера, Р. Таусворта, Д.А. Хаффмена, Н. Цирлера, Б. Шнайера, Б. Элспаса и др.
Заслуживают особого внимания методы совместного использования ГСП и ГПСП в так называемых комбинированных генераторах (КГСП). Существенный вклад в разработку таких устройств внесли Я. Гавел, В.И. Глова, Г.В. Добрис, В.М. Захаров, Б.Ф. Кирьянов, P.M. Мансуров, В.А. Песошин, Е.Л. Столов, Р.Ф. Федоров, Г.П. Хамитов, В.В. Яковлев, В.Н. Ярмолик. Методы комбинирования сложных физических явлений и математических алгоритмов в процессах формирования случайных чисел
были использованы в данной работе, что позволило, во-первых, тематически объединить вопросы построения и анализа ГСП и ГПСП. Во-вторых, идея описания комбинированных структур посредством автоматных моделей синхронных и асинхронных цифровых генераторов привела к техническим решениям, вполне адаптированных к технологиям цифровых интегральных схем, включая БИС.
Одним из результатов совместного использования физических флуктуации и математических алгоритмов формирования псевдослучайных и де-терминированно-хаотических сигналов явилось построение генератора асинхронного случайного процесса (ГАСП), допускающего полную цифровую реализацию. Это техническое решение автором работы защищено изобретениями (приоритет от 1979 г.), использование которых привело к ряду инженерных разработок, внедренных в реальные проекты. Аналогичная схемотехническая идея, спустя 25 лет, описана в статье Й.Ж. Голича. Однако достаточно полных теоретических исследований такого рода устройств предложено не было. Несмотря на простое схемотехническое построение ГАСП, возникает ряд вопросов практического использования в реальных разработках, решение которых требует обобщенного описания. Для такого описания предлагаются модельные представления автономных цифровых осциллирующих структур синхронного и асинхронного типов, основанных на задержках цифровых элементов.
Несмотря на наличие большого количества работ по техническим средствам формирования физически случайных процессов, значимых теоретических результатов, ориентированных на цифровую практическую реализацию, получено не было. Таким образом, элементы теории цифровых генераторов и методы их инженерных приложений в задачах построения физических устройств формирования случайных и псевдослучайных процессов на цифровой элементной базе является вкладом в решение научно-технической проблемы, актуальной для областей статистического моделирования и защиты информации.
Объект исследования - элементы и устройства формирования цифровых случайных и псевдослучайных сигналов.
Предметом исследования являются генераторы случайных и псевдослучайных последовательностей на цифровых элементах задержки.
Цель диссертационной работы - развитие научных основ и методов построения цифровых генераторов случайных и псевдослучайных последовательностей с повышенным быстродействием и точностью.
Научная проблема заключается в разработке основ теории, принципов построения, методов анализа и синтеза генераторов случайных и псевдослучайных сигналов на цифровой элементной базе.
Для достижения поставленной цели и решения научной проблемы сформулированы следующие основные задачи диссертационного исследования:
анализ современного состояния основ схемотехнического построения цифровых генераторов случайных и псевдослучайных сигналов; определение базовых моделей элементарных цифровых генераторов, частотный и временной анализ их поведения;
выявление типичных закономерностей формирования корреляционных зависимостей для периодических процессов;
анализ циклических свойств синхронных моделей генераторов, формирующих линейные рекуррентные последовательности однородного и неоднородного вида;
исследование свойств элементов задержки двоичных сигналов в непрерывном времени как основных компонентов цифровых генераторов асинхронного типа;
-теоретическое и экспериментальное исследование генераторов асинхронных случайных процессов, их структурных, вероятностных и корреляционных свойств; определение условий автогенерации цифровых сигналов в непрерывном времени;
описание свойств датчиков случайных символов и особенностей их применения в технических средствах защиты информации; автоматные представления датчиков и разработка методов их синтеза;
практические разработки генераторов случайных и псевдослучайных последовательностей.
Методы исследования. При выполнении работы использовались методы математического анализа и математической логики, алгебраическая теория, теория чисел, теория автоматов, теория вероятностей, основы цифровой схемотехники, методы математического, физического и имитационного моделирования.
Научная новизна диссертационной работы состоит в разработке основ теории и методов построения генераторов случайных и псевдослучайных последовательностей на цифровых элементах задержки, аппаратные реализации которых отличаются высокотехнологичными схемотехническими решениями, быстродействием и точностью формирования основных параметров случайных и псевдослучайных сигналов.
Новыми научными результатами, выносимыми на защиту, являются:
закономерности формирования реперных точек периодических корреляционных функций; минимизация длины выборки и оценочных процедур для сложно-периодических сигналов;
структурные, вероятностные и автокорреляционные свойства (М-1)- и (М-З)-последовательностей и условия их получения;
аналитические оценки нелинейности и свойств фильтрации асинхронных элементов задержки в цепочечном и циклическом использовании в цифровых генераторах;
фрактальные свойства моделей асинхронных генераторов в случае формирования детерминированно-хаотического процесса при несоизмери-
мых и нефлуктуирующих задержках; вероятностный автомат асинхронного типа; метод вероятностного анализа марковской модели асинхронного генератора с учетом флуктуации задержек; метод анализа и формализованные условия устойчивости генерации асинхронного процесса;
метод условных вероятностей и дисперсий для оценки степени непредсказуемости формируемых генераторами случайных процессов;
синхронно-асинхронные автоматные описания датчика случайных символов и методы их синтеза.
Практическая ценность работы заключается в создании схемотехнических основ построения генераторов дискретных случайных сигналов на цифровой элементной базе, допускающих применение технологий интегральных микросхем, включая БИС. Это основано на разработках
- принципов построения генератора асинхронного случайного процесса и
инженерных методик настройки его структуры на максимально плотный базовый многочлен (М-1 ^последовательности; программных и физических моделей генераторов для экспериментальных исследований статистических и структурных свойств формируемых процессов;
- основных функциональных схем датчиков случайных символов; формаль
ного метода построения датчика посредством структурного синтеза асин
хронного автомата;
-характерных построений реальных датчиков, генераторов случайных и псевдослучайных последовательностей на цифровых микросхемах малой и большой степени интеграции.
Реализация и внедрение результатов работы. Материал диссертации представляет собой теоретическое обобщение ряда НИР и ОКР, выполненных на кафедре ЭВМ (Компьютерных систем) КГТУ им. А.Н. Туполева более чем за 30-летний период работы автора в данном направлении.
Основными объектами внедрения являются полузаказные БИС ГСП Н1582ВЖ2-0105, 1537ХМ2У-135 и 1537ХМ2АУ-215, выпускаемые мелкосерийными партиями с 1992 г. по настоящее время (г. Зеленоград, ОАО «Ангстрем»). Датчики случайных символов на микросхемах малой степени интеграции внедрены в блок статистического моделирования (г. Казань, каф. ЭВМ КАИ, 1978 г.), устройство ввода случайных чисел ЕС 6903 (установочная серия, г. Казань, Казанский завод ЭВМ (КЗ ЭВМ), 1981 г.), терминальную ЭВМ ЕС 1007 (г. Казань, КЗ ЭВМ, 1986 г.). Одноплатные ГСП внедрены в специализированное техническое средство защиты информации (г. Ленинград, НИИ «Нептун», 1987 г.) и специализированную вычислительную систему (г. Минск, НИИ ЭВМ, 1990 г.). Для экспериментальных целей были изготовлены ГСП в виде БИС: по гибридной технологии (г. Казань, каф. МиК КАИ, 1986 г.), на микропроцессорных секциях К1804ВС2 (г. Казань, каф. ЭВМ КАИ, 1990 г.), на ПЛИС фирмы ХШпх (г. Казань, каф. КСИБ КГТУ-КАИ, 2001 г.), микросхема Н1537ХМ1-192 на базовых матричных кристаллах (экспериментальная партия, г. Зеленоград, ОАО «Ангстрем», 2005 г.).
Результаты диссертации использованы при выполнении НИР:
- «Нетрадиционные принципы формирования случайных сигналов для
цифровой техники», «Цифровые методы и средства формирования слу
чайных сигналов для систем защиты информации» по единому заказ-
наряду Министерства образования и науки Российской Федерации (1989-
2004 гг.);
- «Система авторской защиты информации в ПЭВМ на основе полисин
хронных генераторов рекуррентных последовательностей» (договор под
ряда № 04-22), а также темы по договорам подряда №№ 06-26, 06-16.3.2,
06-6.8.2 согласно плану приоритетных фундаментальных и прикладных
исследований Академии наук Республики Татарстан (1997-2006 гг.);
«Цифровые технологии построения и исследования стохастических уст
ройств с выраженными свойствами непредсказуемости» (договора подря
да №№ 06-6.8-199 в период 2001-2005 гг.) по программе развития при
оритетных направлений науки в Республике Татарстан (фонд НИОКР
АНРТ);
«Исследование процессов формирования случайных чисел и методов контроля их стохастических свойств» (1996 г.), «Исследование и разработка методов построения генераторов случайных чисел на программируемых логических интегральных схемах» (1999 г.) по хоздоговорам с Казанским научно-исследовательским институтом радиоэлектроники;
«Исследование и разработка перспективных вычислительных структур для ЕС ЭВМ. Разработка блока статистического моделирования (1977 г.), «Исследование и разработка специализированных процессоров ЕС ЭВМ (Ряд 2 и 3) для сети ЭВМ» (1981-1984 гг.), «Устройства вычислительной техники для статистического моделирования» (1987 г.) по хоздоговорам с Казанским заводом ЭВМ.
Научные и практические результаты диссертации используются в учебном процессе КНИТУ-КАИ при изучении студентами и магистрантами схемотехнических дисциплин. Разработан лабораторный практикум «Генераторы случайных чисел».
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на международных конференциях: «Проблемы теоретической кибернетики» (г. Москва, 2002 г.). «Инфокомму-никационные технологии глобального информационного общества» (г. Казань, 2003, 2004 и 2005 гг.), «Информационные и телекоммуникационные системы и технологии» (г. Санкт-Петербург, 2007 г.), «Физика и технические приложения волновых процессов» (г. Казань, 2007 г.), «Проблемы техники и технологий телекоммуникаций» (г. Казань, 2008 г.); всесоюзных, всероссийских конференциях и симпозиумах: «Вероятностные вычислительные методы и средства» (г. Москва, 1978 г.), «Проблемы создания преобразователей формы информации» (г. Киев, 1980 г.), «Вероятностные автоматы и их приложения» (г. Казань, 1983 г., г. Тбилиси, 1986 г.), «Методы и средства измерения физических величин» (Н. Новгород, 1998, 2000 гг.);
республиканской конференции «Вероятностные методы и средства» (г. Новгород, 1983 г.); всесоюзных и российских школах-семинарах: «Вероятностные автоматы и их приложения» (п. Славск, 1978 г., г. Иркутск, 1981 г., г. Киев, 1984 г.), «Флуктуации и шумы в сложных системах» (г. Казань, 2004 г.); городских семинарах «Методы моделирования» (г. Казань, 2004, 2006, 2009 гг.) и регулярных научно-технических конференциях КГТУ-КАИ.
Публикации. По теме диссертации опубликовано 80 научных работ, в том числе: 1 монография, 19 статей в научных журналах и сборниках, из них 11 в журналах, рекомендованных ВАК для опубликования результатов докторских диссертаций, 29 авторских свидетельств и патентов.
Структура и объем диссертационной работы. Диссертация состоит из введения, шести глав, заключения и списка литературы, включающего 247 наименований. Материал работы изложен на 347 страницах текста компьютерной верстки, в том числе основная часть- на 313 страницах. Работа содержит 105 рисунков и 22 таблицы.
Особенности АКФ инверсно-сегментных последовательностей
Наличие физических флуктуации задержек элементов генераторов приводит к необходимости введения стохастических моделей. В этих случаях асинхронный хаотический режим, сохраняя апериодический характер, частично или полностью теряет детерминированную основу. Псевдослучайный (сложно-периодический) режим синхронной модели за счет случайных временных соотношений своих параметров лишается не только периодичности, но и детерминированности. В обоих случаях уместно представление стохастических объектов физическими моделями и устройствами формирования случайных процессов, в частности ГСП. Приведенная система абстрактных представлений и технических реализаций генераторов позволяет систематизировать как вопросы анализа поведения стохастических объектов, так и задачи синтеза устройств формирования случайных сигналов.
Заслуживает особого внимания методы совместного использования ГСП и ГПСП в так называемых комбинированных ГСП (КГСП). Существенный вклад в разработку таких генераторов внесли Я. Гавел (J. Havel), В.И. Глова, Г.В. Добрис, В.М. Захаров, Б.Ф. Кирьянов, P.M. Мансуров, В.А. Песошин, Е.Л. Столов, Р.Ф. Федоров, Г.П. Хамитов, В.В. Яковлев, В.Н. Ярмолик. Методы комбинирования сложных физических явлений и математических алгоритмов в процессах формирования случайных чисел являются наиболее плодотворными в деле создания высокотехнологичных изделий. Это направление было использовано в данной работе, что, во-первых, способствовало тематическому объединению вопросов построения и анализа ГСП и ГПСП. Во-вторых, идея описания комбинированных структур авто 22 матными представлениями синхронных и асинхронных генераторов привела к техническим решениям, вполне адаптированных к технологиям цифровых интегральных схем, включая БИС.
Несмотря на наличие многочисленных работ по техническим средствам формирования физически случайных процессов, значимых теоретических результатов, ориентированных на цифровую реализацию, получено не было. Не освещены, в частности, с единых методологических позиций общие свойства генераторов на цифровых элементах задержки, работающих в дискретном и непрерывном времени, формирующих структурно-сложные периодические и случайные сигналы. Все это затрудняет получение эффективных инженерных решений, допускающих применение современных технологий цифровых микросхем, включая БИС, в проектах создания стохастических систем. Таким образом, элементы теории цифровых генераторов и методы их инженерных приложений в задачах построения физических устройств формирования случайных и псевдослучайных процессов на цифровой элементной базе является вкладом в решение научно-технической проблемы, актуальной для областей статистического моделирования и защиты информации.
Объектом исследования в данной работе являются элементы и устройства формирования цифровых случайных и псевдослучайных сигналов. Предмет исследования - генераторы случайных и псевдослучайных последовательностей на цифровых элементах задержки. Цель диссертационной работы - развитие научных основ и методов построения цифровых генераторов случайных и псевдослучайных последовательностей с повышенным быстродействием и точностью. Эта цель достигается решением научной проблемы, заключающейся в разработке основ теории, принципов построения, методов анализа и синтеза генераторов случайных и псевдослучайных сигналов на цифровой элементной базе, для чего сформулированы основные задачи диссертационного исследования: - анализ современного состояния основ схемотехнического построения цифровых генераторов случайных и псевдослучайных сигналов; определение базо 23 вых моделей элементарных цифровых генераторов, частотный и временной анализ их поведения; - выявление типичных закономерностей формирования корреляционных зави симостей для периодических процессов; -анализ циклических свойств синхронных моделей генераторов, формирующих линейные рекуррентные последовательности однородного и неоднородного вида; -исследование свойств элементов задержки двоичных сигналов в непрерывном времени как основных компонентов цифровых генераторов асинхронного типа; -теоретическое и экспериментальное исследование генераторов асинхронных случайных процессов, их структурных, вероятностных и корреляционных свойств; определение условий автогенерации цифровых сигналов в непрерывном времени; - описание свойств датчиков случайных символов и особенностей их применения в технических средствах защиты информации; автоматные представления датчиков и разработка методов их синтеза; - практические разработки генераторов случайных и псевдослучайных последовательностей. Для решения перечисленных задач использовались следующие методы исследования: аппарат математического анализа, математическая логика, алгебра, теория чисел, теория автоматов, теория вероятностей, основы цифровой схемотехники, методы математического, физического и имитационного моделирования. Научная новизна диссертационной работы состоит в разработке основ теории и методов построения генераторов случайных и псевдослучайных последовательностей на цифровых элементах задержки, аппаратные реализации которых отличаются высокотехнологичными схемотехническими решениями, быстродействием и точностью формирования основных параметров случайных и псевдослучайных сигналов. Новыми научными результатами, выносимыми на защиту, являются: - закономерности формирования реперных точек периодических корреляци онных функций; минимизация длины выборки и оценочных процедур для сложно-периодических сигналов; -структурные, вероятностные и автокорреляционные свойства (М-1)- и (М-3 последовательностей и условия их получения; -аналитические оценки нелинейности и свойств фильтрации асинхронных элементов задержки в цепочечном и циклическом использовании в цифровых генераторах; - фрактальные свойства моделей асинхронных генераторов в случае формирования детерминированно-хаотического процесса при несоизмеримых и нефлуктуирующих задержках; вероятностный автомат асинхронного типа; метод вероятностного анализа марковской модели асинхронного генератора с учетом флуктуации задержек; метод анализа и формализованные условия устойчивости генерации асинхронного процесса; - метод условных вероятностей и дисперсий для оценки степени непредсказуемости формируемых генераторами случайных процессов; -синхронно-асинхронные автоматные описания датчика случайных символов и методы их синтеза.
Вероятностные характеристики задержек групп элементов
Наличие физических флуктуации задержек элементов генераторов приводит к необходимости введения стохастических моделей. В этих случаях асинхронный хаотический режим, сохраняя апериодический характер, частично или полностью теряет детерминированную основу. Псевдослучайный (сложно-периодический) режим синхронной модели за счет случайных временных соотношений своих параметров лишается не только периодичности, но и детерминированности. В обоих случаях уместно представление стохастических объектов физическими моделями и устройствами формирования случайных процессов, в частности ГСП. Приведенная система абстрактных представлений и технических реализаций генераторов позволяет систематизировать как вопросы анализа поведения стохастических объектов, так и задачи синтеза устройств формирования случайных сигналов.
Заслуживает особого внимания методы совместного использования ГСП и ГПСП в так называемых комбинированных ГСП (КГСП). Существенный вклад в разработку таких генераторов внесли Я. Гавел (J. Havel), В.И. Глова, Г.В. Добрис, В.М. Захаров, Б.Ф. Кирьянов, P.M. Мансуров, В.А. Песошин, Е.Л. Столов, Р.Ф. Федоров, Г.П. Хамитов, В.В. Яковлев, В.Н. Ярмолик. Методы комбинирования сложных физических явлений и математических алгоритмов в процессах формирования случайных чисел являются наиболее плодотворными в деле создания высокотехнологичных изделий. Это направление было использовано в данной работе, что, во-первых, способствовало тематическому объединению вопросов построения и анализа ГСП и ГПСП. Во-вторых, идея описания комбинированных структур автоматными представлениями синхронных и асинхронных генераторов привела к техническим решениям, вполне адаптированных к технологиям цифровых интегральных схем, включая БИС.
Несмотря на наличие многочисленных работ по техническим средствам формирования физически случайных процессов, значимых теоретических результатов, ориентированных на цифровую реализацию, получено не было. Не освещены, в частности, с единых методологических позиций общие свойства генераторов на цифровых элементах задержки, работающих в дискретном и непрерывном времени, формирующих структурно-сложные периодические и случайные сигналы. Все это затрудняет получение эффективных инженерных решений, допускающих применение современных технологий цифровых микросхем, включая БИС, в проектах создания стохастических систем. Таким образом, элементы теории цифровых генераторов и методы их инженерных приложений в задачах построения физических устройств формирования случайных и псевдослучайных процессов на цифровой элементной базе является вкладом в решение научно-технической проблемы, актуальной для областей статистического моделирования и защиты информации.
Объектом исследования в данной работе являются элементы и устройства формирования цифровых случайных и псевдослучайных сигналов. Предмет исследования - генераторы случайных и псевдослучайных последовательностей на цифровых элементах задержки. Цель диссертационной работы - развитие научных основ и методов построения цифровых генераторов случайных и псевдослучайных последовательностей с повышенным быстродействием и точностью. Эта цель достигается решением научной проблемы, заключающейся в разработке основ теории, принципов построения, методов анализа и синтеза генераторов случайных и псевдослучайных сигналов на цифровой элементной базе, для чего сформулированы основные задачи диссертационного исследования: - анализ современного состояния основ схемотехнического построения цифровых генераторов случайных и псевдослучайных сигналов; определение базовых моделей элементарных цифровых генераторов, частотный и временной анализ их поведения; - выявление типичных закономерностей формирования корреляционных зави симостей для периодических процессов; -анализ циклических свойств синхронных моделей генераторов, формирующих линейные рекуррентные последовательности однородного и неоднородного вида; -исследование свойств элементов задержки двоичных сигналов в непрерывном времени как основных компонентов цифровых генераторов асинхронного типа; -теоретическое и экспериментальное исследование генераторов асинхронных случайных процессов, их структурных, вероятностных и корреляционных свойств; определение условий автогенерации цифровых сигналов в непрерывном времени; - описание свойств датчиков случайных символов и особенностей их применения в технических средствах защиты информации; автоматные представления датчиков и разработка методов их синтеза; - практические разработки генераторов случайных и псевдослучайных последовательностей. Для решения перечисленных задач использовались следующие методы исследования: аппарат математического анализа, математическая логика, алгебра, теория чисел, теория автоматов, теория вероятностей, основы цифровой схемотехники, методы математического, физического и имитационного моделирования. Научная новизна диссертационной работы состоит в разработке основ теории и методов построения генераторов случайных и псевдослучайных последовательностей на цифровых элементах задержки, аппаратные реализации которых отличаются высокотехнологичными схемотехническими решениями, быстродействием и точностью формирования основных параметров случайных и псевдослучайных сигналов. Новыми научными результатами, выносимыми на защиту, являются: - закономерности формирования реперных точек периодических корреляци онных функций; минимизация длины выборки и оценочных процедур для сложно-периодических сигналов; -структурные, вероятностные и автокорреляционные свойства (М-1)- и (М-3 последовательностей и условия их получения; -аналитические оценки нелинейности и свойств фильтрации асинхронных элементов задержки в цепочечном и циклическом использовании в цифровых генераторах; - фрактальные свойства моделей асинхронных генераторов в случае формирования детерминированно-хаотического процесса при несоизмеримых и нефлуктуирующих задержках; вероятностный автомат асинхронного типа; метод вероятностного анализа марковской модели асинхронного генератора с учетом флуктуации задержек; метод анализа и формализованные условия устойчивости генерации асинхронного процесса; - метод условных вероятностей и дисперсий для оценки степени непредсказуемости формируемых генераторами случайных процессов; -синхронно-асинхронные автоматные описания датчика случайных символов и методы их синтеза.
Отсутствие устойчивых состояний как условие генерации
Рассмотрим вопрос организации схем из набора нескольких взаимосвязанных ГАСП, сохраняющих автогенераторные свойства. Этот вопрос в формальном отношении всегда может быть решен путем выражения схемы любого блока генераторов через схему однородной среды (см. рис. 5.19) и применения аналитических подходов, предложенных в пунктах 5.7.1 и 5.7.2. Однако в практических задачах могут возникнуть трудности, связанные с большими размерностями используемых матричных форм, описывающих все СМ2 заданного блока генераторов. На примере ГАСП, представленных цепочечными схемами в форме генераторов Галуа, рассмотрим характерные особенности связей в блоке, обеспечивающих формирование процесса в любой точке схемы за счет отсутствия устойчивых состояний.
Метод введения опорного процесса в последовательную цепочку ГАСП. На рис. 5.22 а изображена схема из двух генераторов. Верхний генератор, размерностью п, работая в автономном режиме, характеризуется выполнением условия (5.7.2) отсутствия устойчивых состояний. Нижний неавтономный ГАСП, размерностью п , получает опорный процесс a{t) от верхнего на нечетное число входов вместо постоянных коэффициентов (на схеме это один вход я, 0). Независимо от выполнения условий отсутствия устойчивых состояний, второй ГАСП (и все последующие в цепочке) будет формировать изменяющийся процесс а!{{), если пМх3 средние задержки ЦЭ первого и второго генераторов.
Для формирования стохастических сигналов верхний ГАСП предпочтительно настроить на базовый многочлен (М- -последовательности или выполнить его в виде элементарного генератора-инвертора. Нижний генератор (и все последующие) допускает настройку на М-последовательность при любых значениях констант а\ 0 є {0, 1}(/ = 1, п). Метод кольцевого соединения ГАСП предполагает два варианта организации. Вариант «М-1». Структуры обратных связей в отдельных ГАСП блока настраиваются на базовые многочлены (М- -последовательностей. Число контуров у каждого генератора при этом получается нечетным. Четная часть свободных входов в сумматоры каждого генератора является входом возбуждения от соседнего генератора. Так образуется кольцевая схема соединения всех ГАСП блока. По причине четности числа подключений генератора к возбуждающему сигналу от соседнего генератора, нарушения условия формирования оператора инверсии в процессе настройки на базовую (М-1)-последовательность не происходит. Каждый ГАСП в кольце образованного блока автономно сохраняет условия возбуждения (5.7.2) процесса. В общем случае блок образуется из к ГАСП. Схема на рис. 5.22 б иллюстрирует минимальный вариант кольцевого блока из двух взаимосвязанных генераторов. При к 2 структура блока предполагает однонаправленные кольцевые связи между ГАСП по четному числу входов. При этом вы ni полнение условия (5.7.2) для констант обеспечивается записью a//0 =1 для каждого у = 1, к, где и. и пк - число сумматоров ву-ом и А:-ом ГАСП. Вариант «М». Структуры обратных связей в отдельных ГАСП блока настраиваются на базовые многочлены М-последовательностей. Число контуров у каждого генератора при этом получается четным. Нечетная часть свободных входов в сумматоры каждого генератора является входом возбуждения от соседнего генератора. Также как и в предыдущем варианте образуется кольцевая схема соединения всех ГАСП блока. Однако по причине нечетности числа подключений генераторов к возбуждающему сигналу от соседнего генератора в целях устойчивого формирования процесса требуется к nj обеспечить выполнение общего для всего блока условия ] Г а 7 0 = 1 . По существу это означает, что в кольце образованного блока необходимо настроить на базовые М -последовательности нечетное количество ГАСП. Рис. 5.22 в представляет данный вариант для к = 2. Многомерный случай при к 2 также соответствует образованию однонаправленных кольцевых связей между генераторами, но, в отличие от варианта «М-1», по нечетному числу входов. Рассмотренные методы организации блока ГАСП, обеспечивающие автогенераторные свойства, допускают его сведение к автономному виду. Очевидно, что такая автономная структура на уровне ЛПМ будет описываться составным многочленом, содержащим примитивный многочлен лишь в качестве сомножителя. Альтернатива выбора в качестве базовой (М-1)- или (М-3 последовательности разрешается в пользу первой, имеющей при одинаковых условиях и размерностях структуры меньший уровень автокорреляционного фона. 5.8. Анализ стохастических свойств элементарного цифрового генератора. Когерентный случай В главе 1 представлены элементарные цифровые генераторы, известные как кольцевые генераторы (КГ). Показано, что простейшей модой колебания двоичных уровней в описанных устройствах является последовательность прямоугольных импульсов с параметрами: Т}, Т0 и Т = ТХ +Т0 - длительности соответственно единичного импульса, нулевой паузы и периода следования. В частном случае, когда Г, = Г0, эти колебания превращаются в меандр. Известным аппаратным решением КГ с указанными модами колебаний является генератор-инвертор (ГИ). Учитывая, что отмеченные временные параметры импульсов являются случайными величинами (см. главу 4), исследуем вероятностные и автокорреляционные свойства формируемого ГИ сигнала а в зависимости от временного аргумента т. Схема исследования представлена на рис. 5.23. Схема исследования сигнала кольцевого генератора: Ф- оператор фиксации из асинхронного сигнала а выборочных значений z Отсчет величины т производится с определенной фазы исследуемого сигнала a(t) до момента его фиксации на уровне z(x). Пусть начальная фаза ГИ при каждом факте фиксации постоянна, что составляет суть когерентного режима. В каждый момент фиксации значение бинарного сигнала z может быть случайным. Причиной случайности a(t) являются временные (фазовые) флуктуации естественного характера или внесенные искусственно. Цель исследования - получение функций вероятности и автокорреляции сигнала a(f) в зависимости от аргумента т посредством анализа выборок z(x). В предложенной схеме полагается, что аргумент х задается точечным процессом, не подверженным временным флуктуациям. Однако без потери общности для математической модели будем считать исследуемый сигнал a(t) детерминированным, а процесс фиксации - случайным, с фазовыми флуктуациями, перенесенными с исследуемого сигнала.
Формирование контуров обратной связи на основе свойств базовых образующих многочленов
Крайние точки АЭЗ будут соответствовать максимальному отклонению относительной длительности от 0,5 независимо и от количества повторителей в цепочке п, и от свойства его четности. Для промежуточных точек влево от середины знак 8г будет совпадать со знаком дта3а , а вправо - будет обратным. Другие варианты построения кольца ГИ приводят к более сложным функциональным зависимостям, но выявленные тенденции в формировании вероятностных свойств при этом сохранятся. Из формул (5.8.37) и (5.8.38) видно, что линейность задержек Ьха3а = 0 сводит все рассмотренные условия к равновероятному случаю независимо от варианта набора ЦЭ в АЭЗ и числовых свойств п и і. Исходя из вышеизложенного, устанавливаем очевидное равенство для модуля относительной погрешности по равновероятности результирующей последовательности в форме \др\ = \Ьг\. 5.9. Краткие замечания о некогерентной фиксации сигнала элементарного цифрового генератора Независимая работа генераторов не предполагает когерентного режима фиксации сигнала одного генератора другим. Это соответствует организации асинхронного взаимодействия двух и более КГ.
Попытка рассмотреть такое взаимодействие при гипотезе отсутствия временных флуктуации приводит к задачам о почти периодических функциях (Harald В or, 1925 г.). Несоизмеримость т и Г как действительных величин применительно к цифровым ГИ приводит к тому, что зафиксированные одним генератором символы другого образуют, строго говоря, непериодическую последовательность нулей и единиц. НАКФ такой последовательности не будет содержать предельно экстремальных значений 1 и -1 (за исключением начальной реперной точки 1), что заметно снизит корреляционную связь в результирующем процессе. Кроме этого, точки фиксации s(x) процесса a{f) по оси времени, не накладываясь друг на друга, равномерно заполняют интервал, равный периоду Т. Частота зафиксированных символов 1 как вероятность единичного уровня в исходном процессе, в дополнение к влиянию временных флуктуации, выразится относительной длительностью импульсов г.
Реальная среда КГ и их элементная база содержит источники флуктуации, прежде всего временных. В сочетании с некогерентностью процесса фиксации периодический (синусно-косинусный) характер нестационарности формируемого сигнала, как по вероятности, так и по автокорреляции, перейдет в стохастический. При относительно малых временных флуктуациях периодичность еще будет просматриваться в сочетании со спонтанными непериодическими изменениями, а при значительных - полностью исчезнет.
Абсолютные отклонения анализируемой вероятности от г и автокорреляционной функции от 0 существенно снизятся при совместном действии флуктуации и фактора некогерентности. Время установления стационарности сократится. Аналитические оценки влияния некогерентности на степень отклонения вероятности и корреляции от своих финальных значений, а также на сокращение времени их установления сложным образом связаны с фактором взаимной синхронизации двух или более генераторов. Задачи получения этих оценок в настоящее время требуют своего решения не только в отношении сложных ГАСП, но и применительно к элементарным ГИ. Тем не менее, удается получить конкретные численные значения статистических оценок вероятности и корреляции при реализации экспериментальных исследований на физических моделях. Эти значения концентрируются в доверительных интервалах, располагающихся существенно ближе соответственно к г и 0, чем это следует из математических моделей раздела 5.8.
Наибольшей гибкостью в исследовании обладают программные реализации имитационных моделей. Применительно к ГАСП основой для имитации происходящих в генераторах асинхронных процессов выбрана эмуляция АЭЗ в виде регистра сдвига. Такое синхронное представление асинхронных событий является неизбежным при выборе в качестве инструмента моделирования цифровой ЭВМ, предусматривающей дискретное измерение времени. Подобные интерпретации были продемонстрированы в разделах 5.2, 5.4 и 5.5 данной работы.
Количество разрядов регистра т должно быть достаточно большим. Это необходимо для подробного представления случайно изменяющимися целыми числами kt непрерывных флуктуации х- во времени, а также возможности учета с достаточной степенью точности разброса средних значений этих задержек по ансамблю.
Максимальной чувствительностью к предложенной процедуре дискретизации обладает х3 {і) - случайная задержка одного ЦЭ как исходного компонента всех АЭЗ. Для пересчета временных параметров и аргументов т в целочисленные кТ предложено использовать масштабный коэффициент где каєм+ - число разбиений существенно ненулевых значений оценки плотности /(т3) в пределах интервала Lvi3. Тогда целочисленное представление непрерывной временной величины т выразится операцией округления до ближайшего большего целого в виде кт = ]х/тст[. Обобщенная схема синхронной модели ГАСП в форме генератора Фибоначчи, предназначенная для алгоритмической реализации в программном виде, представлена на рис. 5.28. Регистр сдвига, имитирующий работу БАЭЗ, изображен в целях упрощения без цепи синхронизации. Каждому разряду регистра можно поставить в соответствие ячейку памяти ЭВМ.
