Содержание к диссертации
Введение
Глава 1 Методы построения генераторов псевдослучайных символов на регистрах сдвига 12
1.1. Генераторы псевдослучайных символов на регистре сдвига с линейными обратными связями 13
1.2. Генераторы псевдослучайных символов на регистре сдвига с линейными обратными связями и с использованием инверсных выходов 15
1.3. Генераторы псевдослучайных символов на регистре сдвига с внутренними сумматорами по модулю два 18
1.4. Генератор псевдослучайных чисел на регистре сдвига с линейной обратной связью с блоком сумматоров по модулю два 20
1.5. Генератор псевдослучайных чисел на двух регистрах с объединением выходов через сумматоры по модулю два 22
1.6. Генераторы псевдослучайных чисел с многошаговым сдвигом... 23
1.7. Выводы 26
Глава 2. Генераторы псевдослучайных символов на регистре сдвига с внутренними сумматорами по модулю два 27
2.1. Генераторы псевдослучайных символов на регистре сдвига с внутренними сумматорами по модулю два и с использованием инверсного выхода 27
2.2. Характеристический многочлен ср(х) неприводим и примитивен... 29
2.3. Характеристический многочлен ф(х) разлагается па различные множители 33
2.3.1. Характеристический многочлен ф(х) = (х Ф1) (р2 (л:) 34
2.3.2. Характеристический многочлен <р(х) = (х1) <р2(х)
2.4. Выводы 60
Глава 3. Двоичные рекуррентные последовательности не максимальной длины 62
3.1. Характеристический многочлен ф(х) = (хФ1)'ф2(х)'ф3(х) 64
3.2. Характеристический многочлен ф(х) = [ф,(х)] 'ФгСхО'ФзМ
3.3. Характеристический многочлен ф(х) = [ф,(х)\ Ф2(х) ф3(х)
3.4. Выводы 84
Глава 4. Генераторы случайных чисел на асинхронных регистрах сдвига с внутренними сумматорами по модулю два 86
4.1. Генераторы асинхронных случайных процессов на цифровых элементах 86
4.2. Комбинированный ГСЧ 88
4.3. Технические и программные средства экспериментального исследования ГСЧ 89
4.3.1. Технические средства 89
4.3.2. Программа загрузки конфигурационного файла 96
4.3.3. Программное обеспечение для анализа ГСЧ 97
4.4. Экспериментальные исследования ГСЧ па ПЛИС 98
4.4.1. Влияние порядка базовой модели ГАСП на основные статистические характеристики 98
4.4.2. Де коррелирующие и выравнивающие свойства комбинированной структуры ГСЧ 105
4.4.3. Исследование топологических свойств размещения сконфигурированных фрагментов ГСЧ на поверхности кристалла ПЛИС 109
4.5. Выводы 115
Заключение 117
Список литературы 120
- Генераторы псевдослучайных символов на регистре сдвига с линейными обратными связями и с использованием инверсных выходов
- Генератор псевдослучайных чисел на регистре сдвига с линейной обратной связью с блоком сумматоров по модулю два
- Характеристический многочлен ф(х) разлагается па различные множители
- Влияние порядка базовой модели ГАСП на основные статистические характеристики
Введение к работе
«Вскоре после создания ЭВМ начались поиски эффективных методов получения случайных чисел, пригодных для использования в программах» [1]. В настоящее время известны несколько областей, где случайные и псевдослучайные числа широко используются в процессе решения задач. К таким областям относятся статистическое моделирование (методы Монте-Карло), системы передачи информации, идентификация объектов управления, вероятностное тестирование, системы формирования случайных вибропроцессов, защита информации в ЭВМ и сетях и другие.
Для решения этих задач необходимо вырабатывать «несметные количества случайных чисел с самыми разнообразными свойствами» [2, 3]. По сообщению японских учёных, «согласно статистическим данным, количества использовании подпрограмм математической библиотеки большого ВЦ Токийского университета, подпрограммы генерации равномерно распределённых случайных чисел в последнее время находятся в группе самого высокого ранга использования» [4]. Наибольшее значение для практики имеют числа с равномерным законом распределения.
Одними из основных элементов в таких системах являются генераторы псевдослучайных и случайных символов (ГПСС и ГСС) и чисел (ГПСЧ и ГСЧ), от качества и быстродействия которых существенно зависят результаты решения поставленных задач. Известны фундаментальные работы в области генерирования псевдослучайных последовательностей символов и чисел [1-3, 5-55], а также большое количество патентов и авторских свидетельств, которые говорят о большом интересе к этим областям. Решению таких задач посвящены работы ученых: Амиантова И.П., Бакановича Э.А., Бобнева М.П., Бондаренко Б.П., Буриашева М. И., Бусленко Н.П., Варакина Л.Б., Гантмахера В.Е., Гилла А., Гладкого B.C., Глова В.И.,
Голенко Д.И., Гришкина С.Г., Данильченко И.А., Дапипа О.И., Добриса Г.В., Дядюнова Н.Г., Ермакова СМ., Захарова В.М., Иванова М.А., Кирьянова Б.Ф., Клейнена Д., Кузнецова В.М., Латыпова Р.Х., Левина В.К., Лсусенко А.Е., Мансурова P.M., Менькова А.В., Морозевича А.Н., Морозова A.M., Орлова М.А., Песошина В.А., Пестрякова В.Б., Полляка Ю.Г., Романкевича A.M., Свердлика А.Н., Сергеева Н.Н., Соболя И.М., Столова Е.Л., Судакова Д.М., Тарасова В.М., Таусворта Р., Хамитова Г.П., Четверикова В.М., Чугункова И.В., Шрейдера Ю.А., Яковлева В.В., Ярмолика В.Н. и других.
В отечественной и зарубежной литературе основное внимание при формировании псевдослучайных чисел уделено ГПСЧ, построенных на основе регистра сдвига с линейной обратной связью (с сумматорами по модулю два) [5, 6, 8-12, 14, 18-27, 29-33, 35-40, 42-47, 49-66], причем в большинстве работ рассматриваются последовательности максимальной длины или М-последовательности.
Известны примеры успешного применения таких ГПСЧ. Так, характеристический многочлен 35 степени/(х) =х х 1, определяющий функционирование регистра сдвига, очень широко использовался при генерировании чисел в ЭВМ ІВМ-7094 [42].
Г. Кори в работе [63] рассматривает цифровой метод формирования шума при разработке аналоговой машины ASTRAC II в Аризонском университете (США), предназначенной для статистической обработки реализаций случайных процессов. Генератор двоичной последовательности состоит из 25-разрядного сдвигового регистра и одного сумматора по модулю 2, т.е. это ГПСЧ, формирующий М-последовательность.
В работе [67] приводится интересный пример сочетания цифровых и аналоговых методов при формировании аналогового сигнала в виде белого шума. Существует стандартный "цифровой источник шума", выполненный в виде интегральной микросхемы (National ММ5837), в которой используется 17-разрядный регистр сдвига с обратной связью. «Достаточно несколько кристаллов для того, чтобы сформировать последовательности, которые буквально целые века могут идти без повторения». Сигнал ГПСЧ после
7 прохождения низкочастотного фильтра порождает аналоговый сигнал в виде белого шума. Такой метод цифровой фильтрации последовательностей максимальной длины использован в генераторе шума Hewlett-Packard 3722А.
Таким образом, приведенные примеры говорят о широком использовании ГПСЧ, формирующих М-последовательности.
Известно построение ГПСС и ГПСЧ с использованием инверторов в цепи обратной связи регистра сдвига [24, 32-35, 67] и известны структуры последовательностей, формируемых в этом случае [68]. Однако периодические структуры и статистические характеристики двоичных последовательностей, генерируемых ГПСС с внутренними сумматорами по модулю два, изучены еще недостаточно.
Поэтому исследование периодических структур и статистических характеристик двоичных последовательностей, формируемых ГПСС на основе регистра сдвига с внутренними сумматорами по модулю два, является актуальной задачей, имеющей существенное значение для статистического моделирования.
Объектом исследовании являются ГПСС на основе регистра сдвига с внутренними сумматорами по модулю два.
Предметом исследовании являются периодические структуры ГПСС и
статистические характеристики псевдослучайных двоичных
последовательностей.
Целью работы является расширение функциональных возможностей аппаратных средств генерирования псевдослучайных символов на регистрах сдвига с внутренними сумматорами по модулю два.
Для достижения поставленной цели необходимо решить следующие подзадачи:
1. Провести сравнительный анализ ГПСС на регистрах сдвига.
2. Исследовать периодические структуры последовательностей на
разных выходах регистра сдвига с внутренними сумматорами по модулю два
при использовании инверсных выходов.
3. Исследовать статистические свойства последовательностей.
4. Разработать аппаратно-программное средство и провести
экспериментальные исследования цифровых ГСЧ на асинхронных регистрах
сдвига с внутренними сумматорами по модулю два на основе ПЛИС.
Методы исследований. Для решения поставленной цели использован аппарат теории вероятностей и математической статистики, линейной алгебры, теории цифровых автоматов. При исследовании генераторов применялось статистическое моделирование на ЭВМ, а также экспериментальная проверка лабораторных макетов.
Достоверность полученных результатов обеспечивается
теоретическими решениями, результатами компьютерного моделирования и экспериментальными данными, полученными в работе, и не противоречат результатам, полученными другими авторами.
Научная новизна работы заключается в следующем:
Исследованы периодические структуры последовательностей на разных выходах регистра сдвига с внутренними сумматорами по модулю два при использовании инверсных выходов триггеров. Предложена методика для идентификации формируемых последовательностей на разных выходах триггеров из анализа запрещенных состояний регистра сдвига.
Определены свойства двоичных рекуррентных последовательностей не максимальной длины, порождаемых приводимыми многочленами, причем
один из них имеет вид (х1)', /^ 1,2,....
3. Получены экспериментальные оценки вероятностных и
корреляционных свойств ГСЧ на асинхронных регистрах сдвига с
внутренними сумматорами по модулю два на основе ПЛИС.
Теоретическая значимость работы заключается в том, что определены периодические структуры последовательностей ГПСС па разных выходах регистра сдвига с внутренними сумматорами по модулю два при использовании инверсных выходов триггеров и выделен класс равновероятных двоичных последовательностей не максимальной длины.
Практическая ценность. Полученные результаты использованы в проекте ГСЧ в виде полузаказной БИС для применения в реальной аппаратуре.
Публикации и апробации результатов. Основное содержание диссертационной работы опубликовано в 12 работах, из них 1 статья в журнале, рекомендованном ВАК. Часть материалов опубликована в научно-техническом отчете.
Основные положения и результаты диссертационной работы докладывались и обсуждались на: III Всероссийской НТК «Методы и средства измерений физических величин» (Н. Новгород, 1998г.); V Всероссийской НТК «Методы и средства измерений физических величин», (Н. Новгород, 2000г); 2-й международной НПК "Инфокоммуникационные технологии глобального информационного общества» (Казань, 2004г.); международной молодежной научной конференции «XII Туполевские чтения» (Казань, 2004); 3-й международной НПК "Инфокоммуникационные технологии глобального информационного общества» (Казань, 2005г.).
Реализации результатов работы. Результаты проведенных исследований использованы в ГУП ФНПІД «Радиоэлектроника» им. В.И. Шимко (г. Казань) в НИР по построению генераторов случайных символов и в учебном процессе КГТУ им, А.Н. Туполева (КАИ) при чтении лекций, курсовом и дипломном проектировании.
Пути дальнейшей реализации результатов работы. Научные и практические результаты, полученные в диссертации, могут быть использованы для формирования псевдослучайных и случайных символов при статистическом моделировании.
В дальнейшем целесообразно исследовать статистические характеристики ГПСЧ на регистре сдвига с внутренними сумматорами по модулю два при использовании инверсных выходов триггеров.
10 На защиту выносятся:
- периодические структуры последовательностей па разных выходах
регистра сдвига с внутренними сумматорами по модулю два при
использовании инверсных выходов триггеров;
- свойства двоичных рекуррентных последовательностей не
максимальной длины, порождаемых приводимыми многочленами, причем
один из них имеет вид (хФ1)', /= 1, 2,...;
- вероятностные и корреляционные свойства ГСЧ на асинхронных
регистрах сдвига с внутренними сумматорами по модулю два на основе
ПЛИС.
Работы проводились по госбюджетной теме «Микроэлектронные методы формирования кодовых последовательностей для информационного обмена и защиты в вычислительных и телекоммуникационных системах» и хоздоговору с КНИИРЭ по теме «Исследование и разработка методов построения генераторов случайных чисел на программируемых логических интегральных схемах».
Диссертация состоит из введения, четырех глав, заключения, списка литературы и 3-х приложений.
Во введении обосновывается актуальность темы диссертации, формулируются цель и подзадачи исследования, приводится перечень основных результатов, выносимых на защиту.
В первой главе сделан обзор методов построения генераторов псевдослучайных символов, построенным на основе регистров сдвига с сумматорами по модулю два.
Во второй главе исследуются периодические структуры последовательностей, формируемых ГПСС на основе n-разрядного регистра сдвига с внутренними сумматорами по модулю два при использовании инверсных выходов, причем инверсный выходной сигнал с последнего триггера подается на первый триггер, а прямой выходной сигнал - на некоторые сумматоры по модулю два между триггерами. Рассмотрены
случаи, когда многочлен ф(х) неприводим и примитивен, а также имеет вид ф(х) = [(р|(х)|-(р2(х)---фу(д:)"-(рДх) где 9;(х)- неприводимые многочлены.
Рассмотрены примеры схем ГПСС.
При использовании инверсных выходов регистра сдвига оказалось возможным формировать последовательности не максимальной длины с равновероятными двоичными символами. В третьей главе исследуются свойства одного такого класса двоичных равновероятных последовательностей и рассматриваются схемы ГПСС, формирующие эти последовательности.
В четвертой главе рассмотрены аппаратно-программное средство и результаты экспериментального исследования цифровых ГСЧ на асинхронных регистрах сдвига с внутренними сумматорами по модулю два с использованием ПЛИС.
В заключение формулируются выводы и приводится перечень основных результатов.
В приложения вынесены программы загрузки ПЛИС, взаимодействие с магистралью ISA и разработанные экранные окна.
Диссертация выполнена в Казанском государственном техническом университете им. А.Н.Туполева (КАИ) и является результатом научных исследований, проводимых совместно кафедрой КС (ЭВМ) с ГУП ФНПЦ «Радиоэлектроника» им. В.И. Шимко (г. Казань).
Автор выражает искреннюю благодарность научному руководителю доктору технических наук, профессору Песошину Валерию Андреевичу и научному консультанту кандидату технических наук, доценту Кузнецову Валерию Михайловичу за постоянное внимание и ценные советы при выполнении диссертационной работы.
Генераторы псевдослучайных символов на регистре сдвига с линейными обратными связями и с использованием инверсных выходов
Известен оригинальный способ построения ГПСЧ, предложенный в работах [25, 59]: использование в качестве независимых последовательностей различных участков одной и той же М-последователыюсти. В основе способа лежит известное свойство «сдвига и сложения», согласно которому при поразрядном сложении по модулю два символов последовательности максимальной длины с символами этой же последовательности, но сдвинутой относительно исходной на г символов, получается та же самая последовательность, но сдвинутая относительно исходной на s Ф г символов.
При использовании ГПСЧ на регистре сдвига R с линейной обратной связью формирование различных участков одной и той же последовательности, сдвинутых относительно друг друга на s символов, осуществляется блоком сумматоров по модулю два (рис. 1.9). В общем случае провести расчет подключений сумматоров по модулю два по заданному значению S достаточно сложно [54]. Для частного случая, когда в цепи обратной связи ҐПСП используется сумматор по модулю два только на два входа, Кирьянов Б.Ф. предложил простой метод расчета соединений дополнительных сумматоров по модулю два [25].
Схема ГПСЧ состоит из двух регистров сдвига R1 и R2 с сумматорами по модулю два в цепи обратной связи (рис. 1.10). Каждый регистр формирует последовательности максимальной длины с разными периодами
Для получения /-разрядных псевдослучайных двоичных чисел вводятся / сумматоров по модулю два, которые соединяются с отдельными разрядами обоих регистров сдвига. Если значения периодов последовательностей максимальной длины М\ и М2 являются взаимно простыми числами, то на выходах / сумматоров по модулю два будут формироваться одинаковые, но сдвинутые относительно друг друга псевдослучайные двоичные последовательности, близкие по своим свойствам к последовательностям максимальной длины.
Схема ГПСС приведена на рис. 1.11. В данном случае D-триггер и сумматор по модулю два на его входе представляют собой Т-триггер. Поэтому эту схему можно преобразовать к виду рис. 1.12, т.е. она может быть построена только на D- и Т-триггерах, соединенных в кольцо. при сдвиге S = D С тт4 Т С тт3 т с тт2 т с тт 1 с Рис. 1.12. Схема ГПСС на регистре сдвига с линейной обратной связью при сдвиге s = 3 на Т- и D-триггерах, соединенных в кольцо При s = 4 матрица функционирования ГПСС имеет вид Схема ГПСС в этом случае может быть построена только на Т-триггерах и одном сумматоре по модулю два (рис. 1.13). Схема ГПСС на регистре сдвига с линейной обратной связью при сдвиге s = 4 на Т-триггерах Представляет интерес многошаговый сдвиг в ГПСС на регистре сдвига с внутренними сумматорами по модулю два. Пример 1.5. Рассмотрим случай, когда многочлен (р(дг) = х4 х Ф1, а работа ГПСС описывается матрицей (1.18) us = 3. Матрица функционирования ГПСС в этом случае имеет вид: По матрице (1.25) схема ГПСС на регистре сдвига с внутренними сумматорами по модулю два может быть построена, как и схема ГПСС рис. 1.12, также на трех Т-триггерах и одном D-триггере, соединенных в кольцо. Отличие схем состоит только в нумерации D- и Т-триггеров. При 5 = 4 схема ГПСС на регистре с внутренними сумматорами по модулю два, также как и схема ГПСС рис. 1.13, может быть построена на четырех Т-триггерах и одном сумматоре по модулю два. Отличие состоит в нумерации Т-триггеров. В общем случае, когда характеристический многочлен представляет собой трех член (1.19), ГПСС с многошаговым сдвигом, построенный как на регистре с линейной обратной связью, так и на регистре с внутренними сумматорами, при числе шагов $ = т будет состоять из т Т-триггеров и (и - т) D-триггеров, соединенных в кольцо, а при s = п, будет состоять из п последовательно соединенных Т-триггеров и одного сумматора по модулю два, на вход которого подаются сигналы с выходов я-го и (л-т)-го триггеров. Проведен обзор методов построения ГПСС на регистрах сдвига с линейными обратными связями и с внутренними сумматорами по модулю два. В общем случае схемы ГПСС с сумматорами в цепи обратной связи могут быть преобразованы в схемы ГПСС с внутренними сумматорами за счет изменения нумерации триггеров, когда характеристический многочлен представляет собой трех член ф (х) = х" х" 1. Исследованы ГПСЧ с многошаговым сдвигом. В общем случае, когда характеристический многочлен представляет собой трех член (1.19), ГПСС с многошаговым сдвигом, построенный как на регистре с линейной обратной связью, так и на регистре с внутренними сумматорами, при числе шагов s = т будет состоять из т Т-триггеров и (л - т) D-триггеров, соединенных в кольцо, а при s = п, будет состоять из п последовательно соединенных Т-триггеров и одного сумматора по модулю два, на вход которого подаются сигналы с выходов п го и (и-ш)-го триггеров.
Генератор псевдослучайных чисел на регистре сдвига с линейной обратной связью с блоком сумматоров по модулю два
Каждой из двух комбинаций состояний триггеров q4 и 97 0 1 или 1 0 выражения (2.104) могут соответствовать две комбинации состояний триггеров 9i и q6 (при известном значении qj) выражения (2.105) и две комбинации состояний триггеров q5 и 99 (при известном значении 9г.) выражения (2.106).
Поэтому поиск 4 запрещенных состояний регистра сдвига необходимо производить из 8 комбинаций состояний триггеров 94, Яъ Ц\, 9f , Чь и 99 Комбинации состояний остальных триггеров определим из выражений (2.107) -(2.109): По этим запрещенным состояниям идентифицируем последовательности на выходах триггеров. Как видим, на выходах 1-го и 4-го триггеров формируется последовательность ..., 1 10 0,..., на выходе 3-го триггера-..., 100 1,..., на выходе 5-го триггера-..., 0 110,..., на выходе 7-го триггера-..., 001 1,... и на выходе 9-го триггера-..., 0 1 1 0,... с периодом 4, по которым можно судить о формировании (М-3) -последовательности. На выходе 2-го триггера формируется последовательность ..., 0 1,..., на выходе 8-го триггера-..., 1 0, ....... с периодом 2, по которым можно судить о формировании двух (М-1) -последовательностей. На выходе 6-го триггера формируется последовательность ..., 0, ... с периодом 1, по которой можно судить о формировании четырех М-последовательностсй. Следовательно, на выходах 1-го, 3-го, 4-го, 5-го, 7-го и 9-го триггеров формируются (М -3)-последовательности, на выходах 2-го и 8-го триггеров -две (М-1)-последовательности, а на выходе 6-го триггера - четыре М-последовательности. Таким образом, в отличие от классического ГПСС при Со- 1, в ГПСС на основе регистре сдвига с внутренними сумматорами по модулю два с использованием инверсного выхода не на всех выходах формируются (М - 3) -последовательности. При сложении по модулю два (М - 3) -последовательностей могут формироваться различные последовательности: - последовательности, имеющие период в 2 раза меньший, чем у (М - 3) -последовательности и состоящие из двух (М -1) -последовательностей, порядок которых на 1 меньше порядка (М - 3) -последовательности; - последовательности, имеющие период в 4 раза меньший, чем у (М - 3) -последовательности и состоящие из четырех прямых или инверсных М-последовательностей, порядок которых па 2 меньше порядка (М-3)-последовательности. Формируемые (М - 3) -последовательности, (М -1) -последовательности, прямые или инверсные М-последовательности на выходах триггеров определяются из анализа запрещенных состояний регистра сдвига. Исследование приводимых многочленов (2.18) отличающихся по виду от многочленов (2.21) и (2.68), показало, что во всех случаях они порождают линейные последовательности, имеющие более двух периодов (последовательности не максимальной длины). Один класс таких последовательностей не максимальной длины будет рассмотрен в главе 3.
Исследованы периодические структуры последовательностей на разных выходах регистра сдвига с внутренними сумматорами по модулю два при использованием инверсного выхода. Показано, что если характеристический многочлен ф(х) степени п неприводнм и примитивен, то при сложении по модулю два на внутренних сумматорах регистра М- и М-последовательностей формируется М-последовательность, а при сложении по модулю два М-последователыюстей формируется М-последовательиость. Если характеристический многочлен ср(х) степени п 3 приводим, причем ф(х)-(.кФ1)(р2(. ), где многочлен Ф2С 0 степени {п - 1) 2 неприводим и примитивен, то в отличие от классического ГПСС при С()= 1, в ГПСС на основе регистре сдвига с внутренними сумматорами по модулю два с использованием инверсного выхода не на всех выходах формируются (М-1)-последовательности. Показано, что при сложении по модулю два (М -1) -последовательностей формируется последовательность, имеющая период в два раза меньший, чем у (М-1)-последовательности и состоящая из двух или М- или М-последовательностей, порядок которых на 1 меньше порядка (М -1) -последовательности. Если характеристический многочлен ty(x) степени и 4 приводим, причем ф(х) = (д:Ф1)2ф2(л:), где многочлен ф2(х) степени (п - 2) 2 неприводим и примитивен, то в отличие от классического ГПСС при Со= 1, в ГПСС на основе регистре сдвига с внутренними сумматорами по модулю два с использованием инверсного выхода не на всех выходах формируются (М -3)-последователыюсти. Показано, что при сложении по модулю два (М-3)-последовательностей могут формироваться различные последовательности:
Характеристический многочлен ф(х) разлагается па различные множители
Предложена методика идентификации формируемых последовательностей на разных выходах триггеров из анализа запрещенных состояний регистра сдвига. Таким образом, ГПСС с внутренними сумматорами по модулю два при использовании инверсных выходов имеет расширенные функциональные возможности по сравнению ГПСС с линейной обратной связью, так как позволяет формировать различные последовательности на разных выходах регистра. При моделировании определенный интерес представляют двоичные рекуррентные последовательности не максимальной длины. Однако в общем случае такие последовательности имеют разные вероятности появления двоичных символов, а их АКФ не обладают регулярными свойствами [14]. При использовании инверсных выходов регистра сдвига оказалось возможным формировать последовательности не максимальной длины с равновероятными двоичными символами [35, 83, 84]. В данной главе исследуются свойства одного такого класса двоичных равновероятных последовательностей. В параграфе 1.5 рассмотрен генератор псевдослучайных чисел на двух регистрах с объединением выходов через сумматоры по модулю два, т.е. частный случаи многочлена ф(х) (2.18), когда он разлагается на различные неприводимые и примитивные сомножители р2(х) и Фз(х) и когда периоды М2 и Мз - взаимно простые числа. В этом случае периодическая структура последовательности имеет вид [1(1), 1 (М2), 1 (Мз), 1 (М2М3)]. Обычно последовательности с периодами 1, М2 и Мз считаются запрещенными. На практике нашли применение последовательности с периодом L = М2Мз. Свойства этих последовательностей рассмотрены в параграфе 1.5. Пример. Рассмотрим схему ГПСС (рис.3.1) на регистре сдвига с линейной обратной связью при коэффициенте Со - 0 на основе многочлена
Последовательность состояний регистра сдвига представлена на рис. 3.2. В этом случае формируются последовательности ..., 0, ... с периодом 1, с периодом 2" - 1 - 3 - 7 = 25 - 11 = 21. Периодическая структура имеет вид [1(1), 1(3), 1(7), 1(21)]. Состояния регистра сдвига для последовательностей с периодами 1, 3 и 7 запрещены. Последовательности с периодом 21 назовем составными (ММ)-последовательностями 5-го порядка. Рассмотрим класс двоичных последовательностей, порождаемый приводимыми многочленами (2.18), разлагающимися на 3 различные множители когда ф(х) равен (хФ\) , /= 1,2,.... Пусть в выражении (3.3) /.= 1, тогда ф(х) = ф)(х) ф2(х) ф3(х) = (хФ1)-ф2(х)-ф3(х). При коэффициенте Со = 1 сомножителю (х1) при схемной реализации соответствует триггер со счетным входом, а периодическая структура последовательности имеет вид [1(2)] (1.16). Вероятность появления символов 0 и 1 и периодическая АКФ этой последовательности будут равны: где Ц23...І и L23...1 определяются по аналогии с (2.20). В этом случае последовательности не максимальной длины будут обладать следующими свойствами [35]: 1. Последовательности являются периодическими, причем, как видно из (3.5), период последовательностей - четное число. 2. В периоде всех последовательностей число единичных символов совпадает с числом нулевых, т.е. вероятности появления символов равны 0,5. Это свойство следует из следующего факта. Последовательность {q,} представляет собой результат сложения по модулю два каждого элемента последовательности, соответствующей сомножителю ( 1), со всеми элементами последовательностей, соответствующими сомножителям ф?( ), Фз(х), ... , ф,(х). Поскольку в последовательности, соответствующей сомножителю (хФ1), число символов 1 равно числу символов 0, то независимо от остальных последовательностей в результирующей последовательности число единичных символов совпадает с числом нулевых. 3. В общем случае и при использовании инверсных выходов регистра сдвига периодическая АКФ формируемых последовательностей {q,} не обладает регулярными свойствами. Однако, если сомножители ф2(х),...,ф,-(х) примитивны и (М,„-, М„у) = 1, тогда в (3.5) а для периодической АКФ справедливы следующие соотношения: В качестве примера рассмотрим схему ГПСС на регистре сдвига с линейной обратной связью на основе многочлена ф(х) = х х Фх1 при п = 6 и коэффициенте Со = 1 (рис.3.3). Многочлен ф(х) = х6х4х1 приводим и разлагается на 3 различные неприводимые множителя: Тогда из (2.20) определим периодическую структуру последовательности, порождаемой многочленом (3.9): т.е. периодическая структура последовательности имеет вид [1(2), 1(2М2), 1(2М3), 1(2М2Мз)]. Назовем последовательность с периодом (2ММ) составной (2ММ)-последователыюстыо).
Влияние порядка базовой модели ГАСП на основные статистические характеристики
Синхронная модель мгновенного состояния ГАСП по существу является базовой при гипотезе отсутствия временных флуктуации и равенства средних задержек всех сумматоров по модулю два в ГАСП многоконтурного типа. Такая модель может служить не только средством описания (анализа) генератора, но и инструментом синтеза. Известно, что если базовая модель описывается многочленом (М-1 последовательности, то формирование случайного асинхронного сигнала является устойчивым и качество вероятностных и корреляционных характеристик формируемых процессов достигается наиболее высоким. Эти обстоятельства обосновывают необходимость настройки (синтеза) ГАСП на (М-І)-последовательность.
Исследуем простейшую структуру ГАСП с использованием инверсного выхода и многочлена (М-1 последовательности вида где многочлен х х1 неприводим и примитивен. Понимая под единой мерой измерения задержек 2т (для сдвоенных цифровых элементов), конфигурируем на ПЛИС кольцевой генератор из одного инвертора (на сумматоре по модулю два) и 5 повторителей. В такой структуре условие устойчивости формирования процесса за счет инверсии сохраняется. Реальный асинхронный сигнал формируется в виде меандра со слабо флуктуирующими фронтами. Тем не менее, на этой основе можно построить -ДСС достаточно простой конструкции.
Непосредственные исследования сигналов с ГАСП в ПЛИС с помощью внешней аппаратуры, например ПЭВМ, практически невозможны, поэтому используем косвенные методы оценки посредством дискретизации по времени. Для этого дополним схему ГАСП фиксирующим D-триггером, что фактически превращает его в ДСС. На рис.4.12 изображена сконфигурированная схема такого датчика.
Экспериментальные исследования ДСС на основе кольцевого ГАСП показали, что с доверительной вероятностью 0,95 абсолютная погрешность по равновероятности не превышает величины 0,05 в диапазоне изменения частоты синхронизации до 10 МГц.
Автокорреляционные свойства существенно зависят от частоты синхронизации F, На предельной частоте = 10 МГц для данного измерительного комплекса интервал корреляции т достигает 250 тактов (при пороговом нормированном уровне автокорреляции 0,15).
Более заметное стохастическое поведение обнаруживается при F = 50 кГц. На рис. 4.13 изображен в качестве примера график оценки НАКФ для этой частоты при объеме испытаний 10240 бит.
Практическая пригодность исследуемого ДСС обнаруживается при F 4 кГц, так как в этих случаях достигается тк = 0 тактов. На уровне ГАСП интервал корреляции характеризуется следующим ограничением:
Наибольший практический эффект достигается применением многоконтурных ГАСП (раздел 4.1), которые были конфигурированы на основе следующих базовых характеристических многочленов:
Все приведенные многочлены формируют (М-1 последовательности при наличии результирующей инверсии в структуре ГАСП. Эксперименты по оцениванию основных статистических характеристик ДСС проводились при различных вариантах расположения элементов ГАСП на кристалле ПЛИС при фиксированном базовом многочлене. При этом проявлялся в той или иной мере эффект повторяемости результатов. На рис. 4.14 приведены результаты экспериментального оценивания погрешности ДСС по равновероятности в зависимости от выбранного базового многочлена порядка 4 п 20 и 5 различных вариантов конфигурирования элементов ГАСП. Аналогичные зависимости для нормированной автокорреляционной функции приведены нарис. 4.15
