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

На правах рукописи

ГРИШКИН АНДРЕЙ СЕРГЕЕВИЧ

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

Специальность 05.13.05 - Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

Казань 2006

Диссертация выполнена на кафедре компьютерных систем Казанского государственного технического университета ям. А. Н. Туполева.

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

Официальные оппоненты:

Ведущая организация

доктор технических наук, профессор Песо шин Валерий Андреевич

заслуженный деятель науки и техники РФ, доктор технических наук, профессор Кирьянов Борис Федорович

доктор технических наук, профессор Ильин Герман Иванович

ГУП ФНПЦ « Радиоэлектроника» им. В. И. Шимко (г. Казань)

Защита состоится «*&"» ^¿¿рь^^А 2006 г. в 3часов на диссертационном совете Д 212.079.04 при Казанском государственном техническом университете им. А. Н. Туполева в зале заседаний ученого совета по адресу: 420111, г. Казань, ул. К. Маркса, д. 10.

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

Автореферат разослан «¿4» 2006 г.

Ученый секретарь диссертационного сов«»

шмгтекш^меппсячпс.д» ^^ Козлов В.А.

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

Актуальность исследования. В настоящее время известны несколько областей, где случайные и псевдослучайные числа широко используются в процессе решения задач. К таким областям относятся статистическое моделирование (методы Монте-Карло), системы передачи - информации, вероятностное тестирование, системы формирования случайных вибропроцессов, защита информации в ЭВМ и сетях и другие. Для решения этих задач необходимо вырабатывать огромные количества случайных чисел с самыми разнообразными свойствами. Наибольшее значение для практики имеют числа с равномерным законом распределения.

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

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

Однако периодические структуры двоичных последовательностей, генерируемых ГПСС с внутренними сумматорами по модулю два, а также статистические характеристики ГПСС изучены еще недостаточно.

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

Объектом исследования являются ГПСС на основе регистра сдвига с внутренними сумматорами по модулю два.

Предметом исследования являются периодические структуры ГПСС и статистические характеристики псевдослучайных двоичных

последовательностей.

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

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

1. Провести сравнительный анализ ГПСС на регистрах сдвига;

2. Исследовать периодические структуры последовательностей на разных выходах регистра сдвига с внутренними сумматорами по модулю два при использовании инверсных выходов триггеров.

3. Исследовать статистические свойства последовательностей.

4. Разработать аппаратно-программное средство и провести экспериментальные исследования цифровых ГСС на асинхронных регистрах сдвига с внутренними сумматорами по модулю два на основе ПЛИС.

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

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

Научная новизна работы заключается в следующем:

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

2. Определены свойства двоичных рекуррентных последовательностей не максимальной длины, порождаемых приводимыми многочленами, причем один из них имеет вид (л © 1)', i = 1,2,

3. Получены экспериментальные оценки вероятностных и корреляционных свойств ГСЧ на асинхронных регистрах сдвига с внутренними сумматорами по модулю два на основе ПЛИС.

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

Практическая ценность. Полученные результаты использованы в проекте ГСЧ в виде полузаказной БИС для применения в реальной аппаратуре.

Публикации и апробация результатов. Основное содержание диссертационной работы опубликовано в 12 работах, из них 1 статья в журнале, рекомендованном ВАК.

Основные положения и результаты диссертационной работы докладывались и обсуждались на: III Всероссийской НТК «Методы и средства измерений физических величин» (Н. Новгород, 1998г.); V Всероссийской НТК «Методы и средства измерений физических величин», (Н. Новгород, 2000г); 2-й международной НПК "Инфокоммуникационные технологии глобального информационного общества» (Казань, 2004г.); международной молодежной научной конференции «ХИ Туполевскне чтения» (Казань, 2004); 3-й международной НПК "Инфокоммуникационные технологии глобального информационного общества» (Казань, 2005г.).

реализация результатов работы. Результаты проведенных исследований использованы в ГУП ФНПЦ «Радиоэлектроника» им. В.И. Шимко (г, Казань) в НИР по построению генераторов случайных символов и в учебном процессе КГТУ им. А.Н. Туполева (КАИ) при чтении лекций, курсовом и дипломном проектировании. ^ ■

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

В дальнейшем целесообразно исследовать статистические характеристики ГПСЧ на регистре сдвига с внутренними сумматорами по модулю два при использовании инверсных, выходов триггеров.

На защиту выносятся;

— периодические структуры последовательностей на разных выходах регистра сдвига с внутренними : сумматорами по модулю два при использовании инверсных выходов триггеров;

— свойства двоичных рекуррентных последовательностей не максимальной длины, порождаемых приводимыми многочленами, причем один из них имеет

— вероятностные и корреляционные свойства ГСЧ на асинхронных регистрах сдвига с внутренними сумматорами по модулю два на основе ПЛИС.

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

Автор выражает благодарность научному консультанту профессору кафедры компьютерных систем ЮТУ им. А.Н. Туполева к.т.н., доценту Кузнецову В.М.

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

Сведения о личном вкладе автора. Автором сделан обзор методов построения ГПСС на регистрах сдвига. Исследованы периодические структуры и свойства последовательностей на разных выходах ГПСС с внутренними сумматорами по модулю два при использовании инверсных выходов триггеров и предложена методика идентификации формируемых последовательностей на разных выходах из анализа запрещенных состояний ■ регистра сдвига. Создано аппаратно-программное средство на основе 'ПЛИС фирмы ХИЛЫХ, проведены экспериментальные исследования ГСЧ на асинхронных регистрах сдвига с внутренними сумматорами по модулю два, обработка и анализ результатов, сделаны выводы. ! .

Во введении обосновывается актуальность темы диссертации, формулируются цель и вопросы для исследования, приводится перечень

основных результатов, выносимых на защиту. Приведена структура диссертации.

В первой главе сделан обзор методов построения ГПСС иа регистрах сдвига с линейной обратной связью и с внутренними сумматорами по модулю два. В общем случае схемы ГПСС с сумматорами по модулю два в цепи обратной связи могут быть преобразованы в схемы ГПСС с внутренними сумматорами по модулю два за счет изменения нумерации триггеров, когда характеристический многочлен представляет собой трехчлен ф(х) = х"ФУяФ1,

Во второй главе рассмотрены ГПСС на основе и-разрядного регистра сдвига с внутренними сумматорами по модулю два при использовании инверсного выхода (рис. 1).

Рис. 1. Схема ГПСС на регистре сдвига с внутренними сумматорами по

модулю два

Поведение генератора можно описать в виде матрицы С (м+1)-го порядка:

0 0 0 ... 0 0 С0

1 0 0 ... 0 0 0

0 1 0 ... 0 0 Ся.5 0

0 0 0 ... 1 0 с, 0

0 0 0 ... 0 ] с, 0

0 0 0 ... 0 0 0 1

Характеристический многочлен Дх), являющийся определителем матрицы С—*Е, равен /(*) = (1®*)<р(*). где многочлен соответствует матрице, определяющей связи в цепи обратной связи при коэффициенте С0 =0, Для матрицы (1) многочлен (р{*) имеет вид:

=ф ф сгх"~г © ...е с„_,* ф 1. С2)

Известно, что есш многочлен (2) неприводнм и примитивен и Со"™ О, то на выходах регистра формируются М-посл едовател ьности м-го порядка, а состояние регистра (0 0 ... 0) является изолированным (запрещенным). При С0 =1 на выходах ГПСС формируются М- или М-после до вате лькости. Показано, что при сложении по модулю два на внутренних сумматорах

регистра М- и М-последовательностей формируется М-последовательность, а при сложении М-последовательностей формируется М-последовательность, которые определяются из анализа запрещенных состояний регистра сдвига. Особенность в периодическую структуру ЛРП при С0 = 1 вносит множитель

(дгФ1). Поэтому мы рассмотрим недостаточно исследованные и наиболее, интересные для практики случаи, когда многочлен <р(х) имеет вид

4>(*) = [ф1(*)]' •^М'-ФД*)-"?/*). ~ (3)

где <РУ(*)- неприводимые многочлены степени , <р1(*)='(*Ф1),

г

Исследован случай, когда многочлен (3) степени п £ 3 имеет вид

Ф<х) = (хв1)ч>2(х):, (4)

где многочлен ф2(х) степени (и — 1) & 2 неприводим и примитивен. Известно, что при С0=1 и многочлене (4) классический ГПСС на всех выходах формирует (М-1)-последовательности и-го порядка. Периодическая структура ЛРП имеет вид [1(2), 1(2"- 2)].

В ГПСС на регистре сдвига с внутренними сумматорами по модулю два при Ср =1 не на всех выходах формируются (М -1)-последовательности. В качестве примера рассмотрен многочлен (р(х), который имеет следующий вид: ЧЧ*)=х*Фх'Фл:7Фх1Фх4©11ФхФ1=(хФ1Х*®Ф*6Ф*1Ф*3Ф1), (5) причем многочлен = Ф*6 Ф*1 Фх3 ©1 - неприводим и

примитивен.

Схема ГПСС, построенного на основе многочлена (5), приведена рис. 2.

М2 I

£Ы

М2 О

2 2 3

М2 3

ГУ

я*

г1

М2Ц, 4

п иг Т> % п Ч 7 М2 О 4% М2 т>

5 Г* 5 6 7 г* 6 8 Г 7 9

Рис. 2. Схема ГПСС на основе многочлена (5) Работа ГПСС описывается с помощью квадратной матрицы

0 0 0 0 0 0 0 0 1 1

1 0 ,0 0 0 0 0 0 1 0

0 1 0 0 0 0 0 0 0 о1

0 0 1 0 0 0 0 0 1 0

0 0 0 1 0 0 0 0 I 0

0 0 0 о' 1 0 0 0 1 0

0 0 0 0 0 1 0 0 0 0

0 0 0 0 0 0 1 0 1 0

0 0 0 0 0 0 0 1 1 0

0 0 0 0 0 0 0 0 0 1

Определим запрещенные состояния регистра сдвига из условия (}(* + 2) = 0(0. Для триггеров - ф« получим соотношения:

(7)

(8)

(9)

€,(') = 3.(0® (10)

(11)

(12)

(13)

(14)

<?3 (')ф 04 (0 ® 4% (') © 9» С) » (15)

Состояниям 0 1 или 1 0 триггеров цг и зд выражения (7) могут соответствовать состояния О О и 1 0 триггеров ц<, и Цц выражения (8). Комбинации состояний остальных триггеров определим из выражений (12) —(13):

: • 91 Яг Я% Я* Чь 41 9> Яч * 0 0 0 1 1 0 1 1 0, (16) 1 0 0 0 1 1 0 1 1, (17)

01000000 0, (18) 110 10 110 1. (19)

Анализ показал, что состояния (18) и (19) не удовлетворяют условиям (14) и (15). Поэтому находим два запрещенных состояния (16) и (17):

<?< Чг 4% <7з <?1 <?8 0 0 0 1 1 0 1 1 0, 1 0 0 0 1 1 0 1 1. По состояниям 0 1 или 1 0 идентифицируем {М~1 ^последовательности на выходах 1 -го, 4-го, 6-го, 7-го и 9-го триггеров, по состоянию 0 0 определяем М-последовательностн на выходах 2-го и 3-го триггеров, и по состоянию 11 — М-последовательности на выходах 5-го и 8-го триггеров.

Показано, что при сложении по модулю два (М — ^-последовательностей формируются две М- или М-последовательности.

Исследован случай, когда многочлен ф(лг) в (3) степени п 2; 4 имеет вид:

фСх)-^®!)1«^), (20)

где многочлен <рг(х) степени (и-2) >2 неприводим и примитивен. Известно, что при С0 = 1 и многочлене (20) классический ГПСС на всех выходах формирует (М —3) -последовательностями я-го порядка. Периодическая структура ЛРП имеет, вид [1 (4), 1(2"- 4)].

В ГПСС на регистре сдвига с внутренними сумматорами по модулю два при С0 = 1 не на всех выходах формируются {М - 3) -последовательности. В качестве примера рассмотрен многочлен <р(х), который имеет следующий вид:

9(Je) = xíФJCiФi:тФx!Фд:, Фх1 ФхФ1=(*г Ф1Х*7 Ф*4 Ф*3 Ф*Ф1), (21)

причем многочлен <р2(л) = х7 ® х6 Фх3 ФхФ1 - неприводим и примитивен. Рассмотрим схему ГПСС рис. 3, построенного на основе многочлена (21).

М2 1

9]

М2 2

«2

МЗ 3

Ь —>1

—>

ь

М2 О

4 6

«6

М2 5

¿У

Щ

М2 6

ХУ

М2 7

Рис. 3. Схема ГПСС на основе многочлена (21) Работа ГПСС описывается с помощью квадратной матрицы С

С =

0 0 0 0 0 0 0 0 1 1

1 0 0 0 0 0 0 0 1 0

0 1 0 0 0 0 0 0 1 0

0 0 1 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0 0

0 0 0 0 1 0 0 0 1 0

0 0 0 0 0 1 0 0 1 0

0 0 0 0 0 0 1 0 1 0

0 0 0 0 0 0 0 1 1 0

0 0 0 0 0 0 0 0 0 1

(22)

Определим запрещенные состояния регистра сдвига из условия (К? + 4) = 0(0. Для триггеров — получим соотношения:

т(')=1. (23)

9, (О®?. (О® Л (')=>. (24)

(25)

д, (')«?!(') Ф 9! (О = , (26)

(27)

9э(0®4.(')Ф^(0=1. (28)

= (29)

' = (30)

= (31)

Состояниям О 1 или 1 0 триггеров ^и выражения (23) могут соответствовать две комбинации состояний триггеров Ц\ и (при известном значении выражения (24) и две комбинации состояний триггеров ^ и (при известном значении ^б) выражения.(25). Комбинации состояний остальных триггеров определим из выражений (26) - (28);

Ч\ Яг <?э Ч* Ч) Чь <}1 4» 9»

0 1 1 0 0 0 1 0 0, (32) 0 0 0 0 1 0 1 1 1, (33)

1 1 1 0 0 1 1 1 1, (34) 1 0 0 0 1 1 1 0 0, (35) 00110100 1, (36)

-01011101-0, (37)

10 11 0 0 0 1 0, (38)

1 1 0 1 1 0 0 0 1. (39)

Анализ показал, что состояния (34) — (37) не удовлетворяют условиям (29) и (30). Поэтому находим четыре запрещенных состояния (32), (33), (38) и (39):

91 Яг ЧъЧ* Яз ЧьЙпЧгЧъ 1 0 110 0 0 10, 1 1 0 1 1 0 0 0 1, 0 0 0 0 1 0 1 1 1, 0 1 1 0 0 0 1 0 0.

По состояниям 1 1 0 0, 1 0 0 1, 0 1 1 0 или 0 0 11с периодом 4 идентифицируем (М - 3) -последовательности на выходах 1-го, 3-го, 4-го, 5-го, 7-го и 9-го триггеров, по состояниям 0 1, 0 1 и 1 0,1 0 с периодом 2 определяем две (М -1)-последовательности на выходах 2-го и 8-го триггеров, и по состоянию 0, 0, 0,0 с периодом 1 - четыре М-последовательности на выходе 6-го триггера.

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

?

В третьей главе исследованы свойства одного класса двоичных рекуррентных последовательностей не максимальной длины.

Известно, что если многочлен <р(х) (3) разлагается на 2 различных неприводимых и примитивных сомножителя «рД*) и <М*), причем периоды последовательностей М2 и Мг - взаимно простые числа, то периодическая структура ЛРП имеет вид [1(1), 1 (А/г), 1(М)< 1(Л/2Л/з)]. Последовательность с периодом МгЩ названа (ММ)-последовательностью.

Рассмотрен класс последовательностей, порождаемый приводимыми многочленами (3), разлагающимися на 3 различные множители;

<К*) = [<Р.(*)Ь<Р:(*)-<М*), (40)

когда 9)(х) равен {-*©!), ¡= 1,2.....

Пусть в многочлене (40) / = 1. Тогда периодическая структура ЛРП имеет вид: [1(2), 1(2Ма), 1(2Мэ), 1{2М2Л^)]. Последовательность с периодом <2МгМ%) названа (2ММ)-последовательностью.

Показано, что . вероятность появления символов 1 и 0 в этой последовательности равна 0,5, а периодическая АКФ г змм(т) определится как:

при т " 0 (шой2Л/гЛУ3), . ' при т=аЛ/3, л = 1,2,...,Л/1-1,

(-1)'

Мг 1

(-!)'*'— при г = Шг, 3=1,2,...,-I,

(-1Г

М3 1

(41)

в остальных случаях.

В качестве примеров рассмотрены два ГПСС на регистре сдвига с линейкой обратной связью и с внутренними сумматорами по модулю два (рис. 4) с использованием инверсного выхода на основе многочлена

I,

М2 Р Ч] О Чг М2 о

) 2 г

5

о О М2 п

5 6 ■Г 4 7

М2

о I9«

Рис. 4. Схема ГПСС на основе многочлена (42) Работа ГПСС описывается с помощью матрицы

0 0 0 0 0 0 0 1 1

1 0 0 0 0 0 0 0 0

0 ] 0 0 0 0 0 1 0

0 0 1 0 0 0 0 0 0

0 0 0 1 0 0 0 1 0

0 0 0 0 1 0 0 0 0

0 0 0 0 0 1 0 1 0

0 0 0 0 0 0 I 1 0

0 0 0 0 0 0 0 0 1

Периодическая структура последовательности имеет вид [1(2), 1(6), 1(62), 1(186)]. Показано, что в отличие от классического ГПСС, при Со= 1 в ГТ1СС на основе регистра с внутренними сумматорами по модулю два не на всех выходах формируются (2ММ)-последовательностн. На выходах триггеров могут формироваться последовательности, определяемые произведением многочленов Ф1М и 4>3(х), Ф((х) и <р3(л), а также ф2(ж) и Ф3(х).

Анализ показал, что по двум запрещенным состояниям регистра сдвига не удается идентифицировать последовательности на выходах триггеров. Поэтому рассмотрены другие запрещенные состояния регистра сдвига с периодической структурой 11(6)]:

ЧI Ч2 Яъ Ч* Яъ <¡6 <¡1 ?8 10 0 10 10 0, 110 0 10 10,

1 1 1 0 0 1 0 1, (44)

0 10 110 0 1, 0 0 0 0 0 1 ] 1 , 0 0 1 0 1 0 0 0.

На выходах.триггеров 9), и формируются последовательности ...,1 1 1 0 0 0,...с разными сдвигами, которые позволяют определить (2ММ)-последоватсльностн.

Подобным . же образом могут быть исследованы (2МММ)-последоватсльности, (2ММММ)-последовательности и т.д.

Пусгё в многочлене (40) ¡ = 2, т.е. [ф [(*)]' = (хФ1)3. Тогда периодическая структура ЛРП имеет вид [1 (4), 1(4Мз), 1(4Л/3), 1(4Л/^Л/э)]. Последовательность с периодом (4А/гМ) названа (4ММ)-последовательностью.

Показано, что вероятность появления символов 1 и 0 в этой последовательности также равна 0,5, а периодическая АКФ знакопеременная, причем равна 0 при нечетном значении аргумента т.

В качестве примеров рассмотрены два П1СС на регистре сдвига с линейной обратной связью и с внутренними сумматорами по модулю два (рис. 5) на основе многочлена

ф(х) = х1 © х* ® х1 ® л4 в X1 е 1 =(х ® I)1 (хг © * ФIX*' Ф*Ф1). (45)

м? % п </| л Чг м? Г> р

1 1 2 Г» 2 3 4

У

3

М? Г> V1 м? п М? п

3 5 {* 4 6 Г 5 7

Ч-,

о

Рис.5. Схема ГПСС на основе многочлена (45) Работа ГПСС описывается с помощью матрицы С

0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0

С =

0 0

1 0

0 1

0 0

0 0

0 0

0 0

0 0

о о

(46)

0 0 0 0 0 1 1 0 0 0 0 0 0 1

Периодическая структура последовательности имеет вид [1(4), 1(12), 1(28), 1(84)1. Показано, что в отличие от классического ГПСС, при Со = 1 в ГПСС на регистре с внутренними сумматорами по модулю два не на всех выходах формируются (4ММ)-последовательности, и что могут формироваться последовательности, определяемые различными произведениями многочленов

и [ф](л)]1 с многочленами (*) и ф2(*) 'Фэ(*)-

Анализ показал, что по 4 запрещенным состояниям регистра не удается идентифицировать последовательности на выходах триггеров. Поэтому рассмотрены запрещенные состояния со структурой [1(12)], по которым выделены (4ММ)-последовательности на выходах 1 -го и 7-го триггеров.

Подобным же • образом могут быть исследованы' >(4МММ)-последовательности, (4ММММ)-последовательности и т.д.

При многочлене [фДя)]1, 1 > 2, период последовательностей ие максимальной длины также чётный, но вероятности появления символов 1 и 0 не всегда равны 0,5. Используя равновероятные последовательности, можно получать также равновероятные последовательности с различными АКФ.

Применение операции инверсии и асинхронных элементов задержки позволяет использовать рассмотренный метод построения ГПСС для создания датчиков случайных символов (ДСС).

В четвертой главе рассматривается аппаратно-программное средство для исследования цифровых ГСЧ на основе ПЛИС фирмы Х11Л№< и экспериментальные исследования ГСЧ на основе асинхронных регистров сдвига с внутренними сумматорами по модулю два.

В работах Кузнецова В.М. и Песошина В.А. предложена асинхронная организация взаимодействия между цифровыми элементами ГПСС. Тогда схема устройства вырождается в схему генератора асинхронного случайного процесса (ГАСП) многоконтурного типа (рис. 6). Такой генератор может служить основным задающим элементом комбинированного ГСЧ (КГСЧ).

Рис.6. Схема ГАСП многоконтурного типа

Теоретический анализ статистических свойств ГАСП представляет на сегодня очень сложную задачу. Поэтому предлагается экспериментальное исследование ГСЧ в форме физических моделей. Наиболее удобной элементной базой в плане проведения экспериментов являются ПЛИС. Для этой цели были разработаны, собраны и отлажены две макетные платы на основе ПЛИС серии ХС4003 и ХС95108 фирмы XILINX. Эти разработки в форме платы расширения работают в составе ПЭВМ через системный интерфейс ISA. Функциональная схема макета приведена соответственно на рис. 7.

ГСС основан на 4 ГАСП, структуры которых задаются конфигурационным файлом. Аналогично конфигурируется н ГПСС.

Для реализации интерфейса загрузки ПЛИС написана программа «XLoader 32». Для статистической обработки результатов экспериментов разработаны 2 программы под общиц названием «Анализатор ГСЧ». Все программы работают в составе ОС Windows 95/98/NT/2000. 1

Разработаны экранные окна: управления процессом работы генераторов; «График ОЗУ», схематично демонстрирующий процесс флуктуации задержек цифровых элементов; «Данные»,' показывающие считанную случайную выборка из буферного ОЗУ ГСЧ, обновляемую в реальном режиме; «Статистические характеристики», отображающие в реальном режиме времени основные статистические данные; «Интегральные характеристики», показывающие зависимости интервала корреляции и максимального значения модуля нормированной АКФ от частоты работы тактового генератора; «Гистограмма распределения», - на которой отображается гистограмма распределения 4-х разрядного числа ГСЧ.

Рис. 7. Функциональная схема КГСЧ

Получены экспериментальные оценки вероятностных и корреляционных свойств ГСЧ на основе ГАСП простейшей кольцевой структуры и многоконтурного типа. Определены предельные скоростные возможности генераторов на элементной базе ПЛИС XIПЫХ.

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

Эксперименты по оцениванию основных статистических характеристик ГСС проводились при различных вариантах расположения элементов ГАСП на кристалле ПЛИС при фиксированном базовом многочлене. На рис. К приведены результаты экспериментального оценивания погрешности Г СС по

равновероятности в зависимости от порядка выбранного базового многочлена 4 £ и £ 20 и 5 различных вариантов конфигурирования элементов ГАСП, Аналогичные зависимости получены и для нормированной АКФ.

X N * I 4

- -

4 5 в Т 8 1* 1вЭДп

Рис. 8. Результаты экспериментального оценивания погрешности по равновероятности ДСС в зависимости от порядка базового многочлена ГАСП

{F= 10 МГц)

Определена степень влияния на статистические характеристики выходных последовательностей топологического расположения отдельных фрагментов ГСЧ на площади кристалла ПЛИС. Экспериментально замечено, что расположенный на кристалле микросхемы рядом с основным ГАСП кольцевого типа изолированный дополнительный генератор в среднем улучшает корреляционные свойства формируемых последовательностей. Отрицательный эффект проявляется в случае размещения дополнительного изолированного генератора рядом с тактовым генератором. Однако эти эффекты довольно незначительны. При много контурной организации асинхронных структур эта зависимость становится несущественной.

Заключение содержит основные результаты диссертационной работы.

В приложен и и приведены исходный листинг программы «XLoader 32» дня реализации интерфейса загрузки ПЛИС, взаимодействие с системной магистралью ISA и разработанные экранные окна.

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

1. Сделан обзор методов построения ГПСС на регистрах сдвига. Рассмотрены ГПСС с линейной обратной связью (с сумматорами по модулю два в цепи обратной связи) и с внутренними сумматорами по модулю два.

2. Исследованы периодические структуры последовательностей на разных .выходах регистра с внутренними сумматорами по модулю два при использовании инверсного выхода. Показано, что если характеристический

многочлен ф(х) неприводим и примитивен, то при сложении по модулю два на внутренних сумматорах М- и М-последовательностей формируется М-последовательность, а при сложении. М-последовательностей - М-последовательность, Если характеристический многочлен ф(*) = (д: Ф1}' Ф2(х), где многочлен 4>г(х) неприводим и примитивен, то при » = 1 при сложении по модулю два на внутренних сумматорах (М—1)-последовательностей формируются две М- или М- последовательности, а при / = 2 при сложении по модулю два (М-3)-последовательностей могут формироваться две (Непоследовательности или четыре М- или М- последовательности.

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

3. Проведен анализ одного класса равновероятных двоичных рекуррентных последовательностей' не максимальной длины. Показано, что если характеристический многочлен где многочлены

93(я) и Фз(х) непрнводнмы и примитивны, то при I = 1 классический ГПСП формирует (2ММ)-последовательности. Их отличительными особенностями являются равновероятность появления двоичных символов и знакопеременные периодические АКФ. В ГПСС с внутренними сумматорами по модулю два при использовании инверсного выхода не на всех триггерах формируются (2ММ)-последовательности. В этом случае могут формироваться последовательности, определяемые произведением многочленов ф,(х) и ф;(*). фД*) и ф3(х), а также Ф2(*) и Ф3(х). При числе сомножителей более 3 будут получены (2МММ)-последовательности, (2ММММ)-последовательности и т.д. При 1 = 2 классический ГПСП формирует (4ММ)-последовательности. Их ' отличительными особенностями также являются равновероятность появления двоичных символов и знакопеременные периодические АКФ, причем равные О при нечетном значении аргумента т. В ГПСП с внутренними сумматорами по модулю два при использовании инверсного выхода не на всех триггерах формируются (4ММ)-последовательности. В этом случае могут формироваться последовательности, определяемые различными произведениями многочленов ф](х) и [фД*)]1 с многочленами Фа(*),Фа{*) и ФгОО * Фэ(х). При числе сомножителей более 3 будут получены (4МММ>-последовательности, (4ММММ)-последовательности и т.д.

4. Разработано аппаратно-программное средство для экспериментального исследования цифровых ГСЧ на основе ПЛИС фирмы ХИЛЫХ, имеющее удобный пользовательский интерфейс и наглядное представление результатов исследований. Получены экспериментальные оценки вероятностных и корреляционных свойств ГСЧ на основе ГАСП простейшей кольцевой структуры и многоконтурного типа. Определены предельные скоростные возможности генераторов на элементной базе ПЛИС ХТЫМХ.

Получены экспериментальные зависимости вероятностных и корреляционных свойств многоконтурных ГАСП от порядка базового многочлена. Предложено использовать полученные зависимости при решении задач синтеза реальных ГАСП в среде ПЛИС XIL1NX.

Определена степень влияния на статистические характеристики выходных последовательностей топологического расположения отдельных фрагментов ГСЧ на' площади кристалла ПЛИС. Замечено, что при многоконтурной организации асинхронных структур эта зависимость становится несущественной.

Основное содержание диссертации опубликовано в следующих работах:

1. Бахарев, ,А.Н. Оценка степени предсказуемости поведения цифровых генераторов случайных чисел / А.Н. Бахарев, A.C. Гришкин, В.М. Кузнецов,

B.А,;Песошин //Тезисы докладов III Всероссийской НТК «Методы и средства измерений физических величин». Часть 8,-Н. Новгород: Изд-во НГТУ, 1998,-С .29-30.

2. Гришкин, A.C. Оценка корреляционных свойств случайных цифровых последовательностей в среде программируемых БИС /A.C. Гришкин, BJvl. Кузнецов //Тезисы докладов V Всероссийской НТК «Методы и средства измерений физических величин», Часть З.-Н, Новгород: Изд-во НГТУ, 2000,-

C.32. ■

3. Гришкин, A.C. Двоичные линейные рекуррентные последовательности на основе регистров сдвига /A.C. Гришкин //Материалы международной молодежной научной конференции «XII Туполеаские чтения», Т.Ш, Казань: Изд-во КГТУ, 2004.-С.68-69.

4. Гришкин, A.C. Псевдослучайные двоичные последовательности на основе регистров сдвига /A.C. Гришкин //Материалы международной молодежной научной Конференции «XII Туполевские чтения», Т.Ш, Казань: Изд-во КГТУ, 2004.-С.69-70.

5. Гришкин, A.C. Линейные рекуррентные последовательности не максимальной длины на основе регистров сдвига /A.C. Гришкин, В.М. Кузнецов, В,А. Песошин /Тезисы докладов 2-ой международной НПК «Инфокоммуникационные технологии глобального информационного общества», Казань*. Изд-во КГТУ, 2004.-С.197-198.

6. Гришкин, A.C. Рекуррентные последовательности не максимальной . длины, на основе регистров сдвига /A.C. Гришкин, В.М. Кузнецов,

В. А. Песошин //Инфокоммуникационные технологии глобального информационного общества. Сборник трудов 2-й ежегодной международной НПК, Казань, 2004.М.: Изд-во «Новые технологии», 2004.-С.475-476.

7. Песошин, В.А. Генераторы псевдослучайных последовательностей на регистрах сдвига с использованием инверсных выходов /В.А. Песошин,

B.М. Кузнецов, A.C. Гришкин //Инфокоммуникационные технологии глобального информационного общества. Сборник трудов 2-й ежегодной международной НПК, Казань, 2004.М.: Изд-во «Новые технологии», 2004.-

C.480-491.

8. Бахарев, АЛ. Генератор случайных чисел на программируемых логических интегральных схемах /А.Н. Бахарев, A.C. Гриш кип, Д.В. Каштанов, В.М. Кузнецов, В. А. Песошин// Тезисы докладов 3-ей международной НПК «Инфокоммуннкационные технологии глобального информационного общества», Казань: Изд-во КГУ, 2Q05.-C.35-37.

9. Бахарев, А.Н. Цифровые генераторы случайных чисел на программируемых микросхемах и базовых матричных кристаллах / А.Н. Бахарев, A.C. Гришкин, Д.В. Каштанов, В.М. Кузнецов, В.А. Песошин //Инфокоммуннкационные технологии глобального информационного общества. Сборник трудов 3-Й ежегодной международной НПК, Казань, 2005.-С.343-349.

Ю. Гришкин, A.C. Экспериментальные исследования декоррелирующих и выравнивающих свойств комбинированного генератора случайных чисел / A.C. Гришкин, В.М, Кузнецов //Социально-экономические и технические системы: Онлайновый электронный научно-технический журнал, №3, 2006. (http://kampi лл/sets)

11. Гришкин, A.C. Экспериментальное исследование взаимного влияния стохастически генерирующих элементов на кристалле БИС /A.C. Гришкин //Социально-экономические к технические системы: Онлайновый электронный научно-технический журнал, №3,2006. (http://kampi,ru/sets)

12.Гришкин, A.C. Синхронная интерпретация работы генератора асинхронного случайного сигнала /A.C. Гришкин, В.М. Кузнецов, В .А. Песошин//Вестник КГТУ им. А.Н. Туполева, J&3,2006.-С. 19-21.

Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Печл. 1,0. Усл.печл. 0,93. Усл.кр.-отт. 0,98. Уч.издл. 1,0. _Тираж 100. Заказ И200._

Типография Казанского государственного технического университета им, А.Н, Туполева. 420111, Казань, К. Маркса, 10.

ВВЕДЕНИЕ.

ГЛАВА 1. МЕТОДЫ ПОСТРОЕНИЯ ГЕНЕРАТОРОВ

ПСЕВДОСЛУЧАЙНЫХ СИМВОЛОВ НА РЕГИСТРАХ СДВИГА.

1.1. Генераторы псевдослучайных символов на регистре сдвига с линейными обратными связями.

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

1.3. Генераторы псевдослучайных символов на регистре сдвига с внутренними сумматорами по модулю два.

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

1.5. Генератор псевдослучайных чисел на двух регистрах с объединением выходов через сумматоры по модулю два.

1.6. Генераторы псевдослучайных чисел с многошаговым сдвигом.

1.7. Выводы.

ГЛАВА 2. ГЕНЕРАТОРЫ ПСЕВДОСЛУЧАЙНЫХ СИМВОЛОВ НА

РЕГИСТРЕ СДВИГА С ВНУТРЕННИМИ СУММАТОРАМИ ПО МОДУЛЮ ДВА.

2.1. Генераторы псевдослучайных символов на регистре сдвига с внутренними сумматорами по модулю два и с использованием инверсного выхода.

2.2. Характеристический многочлен ф(х) неприводим и примитивен.

2.3. Характеристический многочлен ф(х) разлагается на различные множители.

2.3.1. Характеристический многочлен ф(х) = (х© 1)ф2(х).

2.3.2. Характеристический многочлен ф(х) = (д:Ф I)2 Ф2(Х).

2.4. Выводы.

ГЛАВА 3. ДВОИЧНЫЕ РЕКУРРЕНТНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ

НЕ МАКСИМАЛЬНОЙ ДЛИНЫ.

3.1. Характеристический многочлен ф(х) = (х01)-ф2(х)-ф3(х).

3.2. Характеристический многочлен ф(х) = [ф,(х)]2-ф2(х)-ф3(х).

3.3. Характеристический многочлен ф(х) = [ф,(х)]' -ф2(х)-ф3(х).^

3.4. Выводы.

ГЛАВА 4. ГЕНЕРАТОРЫ СЛУЧАЙНЫХ ЧИСЕЛ НА АСИНХРОННЫХ

РЕГИСТРАХ СДВИГА С ВНУТРЕННИМИ СУММАТОРАМИ

ПО МОДУЛЮ ДВА.

4.1. Генераторы асинхронных случайных процессов на цифровых элементах.

4.2. Комбинированный ГСЧ.

4.3. Технические и программные средства экспериментального исследования ГСЧ.

4.3.1. Технические средства.

4.3.2. Программа загрузки конфигурационного файла.

4.3.3. Программное обеспечение для анализа ГСЧ.

4.4. Экспериментальные исследования ГСЧ на ПЛИС.

4.4.1. Влияние порядка базовой модели ГАСП на основные статистические характеристики.

4.4.2. Декоррелирующие и выравнивающие свойства комбинированной структуры ГСЧ.

4.4.3. Исследование топологических свойств размещения сконфигурированных фрагментов ГСЧ на поверхности кристалла ПЛИС.

4.5. Выводы.

Вскоре после создания ЭВМ начались поиски эффективных методов получения случайных чисел, пригодных для использования в программах» [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 2 характеристический многочлен 35 степени f(x) = x Ф х Ф1, определяющий функционирование регистра сдвига, очень широко использовался при генерировании чисел в ЭВМ IBM-7094 [42].

Г. Корп в работе [63] рассматривает цифровой метод формирования шума при разработке аналоговой машины ASTRAC II в Аризонском университете (США), предназначенной для статистической обработки реализаций случайных процессов. Генератор двоичной последовательности состоит из 25-разрядного сдвигового регистра и одного сумматора по модулю 2, т.е. это ГПСЧ, формирующий М-последовательность.

В работе [67] приводится интересный пример сочетания цифровых и аналоговых методов при формировании аналогового сигнала в виде белого шума. Существует стандартный "цифровой источник шума", выполненный в виде интегральной микросхемы (National ММ5837), в которой используется 17-разрядный регистр сдвига с обратной связью. «Достаточно несколько кристаллов для того, чтобы сформировать последовательности, которые буквально целые века могут идти без повторения». Сигнал ГПСЧ после прохождения низкочастотного фильтра порождает аналоговый сигнал в виде белого шума. Такой метод цифровой фильтрации последовательностей максимальной длины использован в генераторе шума Hewlett-Packard 3722А.

Таким образом, приведенные примеры говорят о широком использовании ГПСЧ, формирующих М-последовательности.

Известно построение ГПСС и ГПСЧ с использованием инверторов в цепи обратной связи регистра сдвига [24, 32-35, 67] и известны структуры последовательностей, формируемых в этом случае [68]. Однако периодические структуры и статистические характеристики двоичных последовательностей, генерируемых ГПСС с внутренними сумматорами по модулю два, изучены еще недостаточно.

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

Объектом исследования являются ГПСС на основе регистра сдвига с внутренними сумматорами по модулю два.

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

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

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

1. Провести сравнительный анализ ГПСС на регистрах сдвига.

2. Исследовать периодические структуры последовательностей на разных выходах регистра сдвига с внутренними сумматорами по модулю два при использовании инверсных выходов.

3. Исследовать статистические свойства последовательностей.

4. Разработать аппаратно-программное средство и провести экспериментальные исследования цифровых ГСЧ на асинхронных регистрах сдвига с внутренними сумматорами по модулю два на основе ПЛИС.

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

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

Научная новизна работы заключается в следующем:

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

2. Определены свойства двоичных рекуррентных последовательностей не максимальной длины, порождаемых приводимыми многочленами, причем один из них имеет вид (х ® 1)', / = 1, 2,.

3. Получены экспериментальные оценки вероятностных и корреляционных свойств ГСЧ на асинхронных регистрах сдвига с внутренними сумматорами по модулю два на основе ПЛИС.

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

Практическая ценность. Полученные результаты использованы в проекте ГСЧ в виде полузаказной БИС для применения в реальной аппаратуре.

Публикации и апробация результатов. Основное содержание диссертационной работы опубликовано в 12 работах, из них 1 статья в журнале, рекомендованном ВАК. Часть материалов опубликована в научно-техническом отчете.

Основные положения и результаты диссертационной работы докладывались и обсуждались на: III Всероссийской НТК «Методы и средства измерений физических величин» (Н. Новгород, 1998г.); V Всероссийской НТК «Методы и средства измерений физических величин», (Н. Новгород, 2000г); 2-й международной НПК "Инфокоммуникационные технологии глобального информационного общества» (Казань, 2004г.); международной молодежной научной конференции «XII Туполевские чтения» (Казань, 2004); 3-й международной НПК "Инфокоммуникационные технологии глобального информационного общества» (Казань, 2005г.).

Реализация результатов работы. Результаты проведенных исследований использованы в ГУП ФНПЦ «Радиоэлектроника» им. В.И. Шимко (г. Казань) в НИР по построению генераторов случайных символов и в учебном процессе КГТУ им. А.Н. Туполева (КАИ) при чтении лекций, курсовом и дипломном проектировании.

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

В дальнейшем целесообразно исследовать статистические характеристики ГПСЧ на регистре сдвига с внутренними сумматорами по модулю два при использовании инверсных выходов триггеров.

На защиту выносятся:

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

- свойства двоичных рекуррентных последовательностей не максимальной длины, порождаемых приводимыми многочленами, причем один из них имеет вид (х© 1)', i - 1, 2,.;

- вероятностные и корреляционные свойства ГСЧ на асинхронных регистрах сдвига с внутренними сумматорами по модулю два на основе ПЛИС.

Работы проводились по госбюджетной теме «Микроэлектронные методы формирования кодовых последовательностей для информационного обмена и защиты в вычислительных и телекоммуникационных системах» и хоздоговору с КНИИРЭ по теме «Исследование и разработка методов построения генераторов случайных чисел на программируемых логических интегральных схемах».

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

Основные результаты работы заключаются в следующем:

1. Сделан обзор методов построения ГПСС на регистрах сдвига. Рассмотрены ГПСС с линейной обратной связью (с сумматорами по модулю два в цепи обратной связи) и с внутренними сумматорами по модулю два.

2. Исследованы периодические структуры последовательностей на разных выходах регистра сдвига с внутренними сумматорами по модулю два при использовании инверсного выхода.

Показано, что если характеристический многочлен ф(х) неприводим и примитивен, то при сложении по модулю два на внутренних сумматорах регистра М- и М-последовательностей формируется М-последовательность, а при сложении М-последовательностей - М-последователыюсть. Если характеристический многочлен ф(л:) = (х©1)' Ф2(Х), где многочлен Ф2(х) неприводим и примитивен, то при i = 1 при сложении по модулю два на внутренних сумматорах регистра (М-^-последовательностей формируются две М- или М- последовательности, а при i = 2 при сложении по модулю два (М - 3)-последовательностей могут формироваться две (М-1)последовательности или четыре М- или М- последовательности.

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

3. Проведен анализ одного класса двоичных рекуррентных последовательностей не максимальной длины. Показано, что если характеристический многочлен ф(х) = [ф,(х)]'-ф2(х)-ф3(х), где многочлены

Ф2(х) и ф3(х) неприводимы и примитивны, то i = 1 классический ГПСС формирует (2ММ)-последовательности. Их отличительными особенностями являются равновероятность появления двоичных символов и знакопеременные периодические АКФ.В ГПСС с внутренними сумматорами по модулю два при использовании инверсного выхода не на всех триггерах формируются (2ММ)-последователыюсти. В этом случае могут формироваться последовательности, определяемые произведением многочленов ф, (лг) и Ф2(*), Ф|(Х) и ф3(Х), а также Ф2(*) и ф3(Х). При числе сомножителей более 3 будут получены (2МММ)-последовательности, (2ММММ)-последовательности и т.д.

При / = 2 классический ГПСП формирует (4ММ)-последовательности. Их отличительными особенностями также являются равновероятность появления двоичных символов и знакопеременные периодические АКФ, причем равные 0 при нечетном значении аргумента т. Показано, что в ГПСП с внутренними сумматорами по модулю два при использовании инверсного выхода не на всех выходах регистра формируются (4ММ)-последователыюсти. В этом случае могут формироваться последовательности, определяемые различными произведениями многочленов Ф|(*) и [ф](*)]2 с многочленами

Ф2 (х)» Ф3(х) и ф2(Х)' Фз(*) • При числе сомножителей более 3 будут получены (4МММ)-последовательности, (4ММММ)-последовательности и т.д.

4. Разработано аппаратно-программное средство для экспериментального исследования цифровых ГСЧ па основе ПЛИС фирмы XILINX, имеющее удобный пользовательский интерфейс и наглядное представление результатов исследований.

Получены экспериментальные оценки вероятностных и корреляционных свойств ГСЧ на основе ГАСП простейшей кольцевой структуры и многоконтуриого типа. Определены предельные скоростные возможности генераторов на элементной базе ПЛИС XILINX.

Получены экспериментальные зависимости вероятностных и корреляционных свойств многоконтурных ГАСП от порядка базового многочлена. Предложено использовать полученные зависимости при решении задач синтеза реальных ГАСП в среде ПЛИС XILINX.

Определена степень влияния на статистические характеристики выходных последовательностей топологического расположения отдельных фрагментов ГСЧ на площади кристалла ПЛИС. Замечено, что при многоконтурной организации асинхронных структур эта зависимость становится несущественной.

120

ЗАКЛЮЧЕНИЕ

1. Кнут, Д. Искусство программирования для ЭВМ /Д. Кнут.- М.: Мир, Т. 2, 1977.-724с.

2. Иванова, В.М. Случайные числа и их применение /В.М. Иванова.- М.: Финансы и статистика, 1984.-111с.

3. Клейнен, Д. Статистические методы в имитационном моделировании /Д. Клейнен. М.: Статистика, 1978.-221с.

4. Методы генерации псевдослучайных чисел: Дзехо серес /Fushimi Masanori //ВЦП,-1980.-№Г-32668, Vol.21 ,№9.-Р.968-974.

5. Амиантов, И.Н. Избранные вопросы статистической теории связи /И.Н. Амиантов.- М.: Советское радио, 1971.-477с.

6. Бобнев, М.П. Генерирование случайных сигналов /М.П. Бобнев.- М.: Энергия, 1971.-240с.

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

8. Варакин, J1.E. Теория сложных сигналов /J1.E. Варакин.- М.: Советское радио, 1970.-376с.

9. Винокуров, В.И. Дискретно кодированные последовательности /В.И. Винокуров, В.Е. Гантмахер.- Ростов-на-Дону: РГУ, 1990.-288с.

10. Гилл, А. Линейные последовательные машины /А. Гилл.- М.: Наука, 1974.-288с.

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

12. Глова, В.И. Вычислительные средства для статистического моделирования: Дис.докт. техн наук: 05.13.05 /В.И. Глова.- Казань, 1995.-419с.

13. Голенко, Д.И. Моделирование и статистический анализ псевдослучайных чисел на электронных вычислительных машинах /Д.И. Голенко.- М.: Наука, 1965.-228с.

14. Дядюнов, Н.Г. Ортогональные и квазиортогопальные сигналы /Н.Г. Дядюнов, А.И. Сенин.- М.: Связь, 1977.-224с.

15. Ермаков, С.М. Курс статистического моделирования /С.М. Ермаков, Г.А. Михайлов.- М.: Наука, 1976,-ЗЗОс.

16. Ермаков, С.М. Метод Монте-Карло и смежные вопросы /С.М. Ермаков.- М.: Наука, 1975.-472с.

17. Захаров, В.М. К проблеме эффективизации аппаратурных методов получения случайных кодов: Дис.канд. техн. наук: 05.13.01 /В.М. Захаров.-Казань, 1972.-149с.

18. Иванов, М.А. Криптографические методы защиты информации /М.А. Иванов,- М.: КУДИЦ-ОБРАЗ, 2001.-368с.

19. Иванов, М.А. Теория, применение и оценка качества генераторов псевдослучайных последовательностей /М.А. Иванов, И.В. Чугунов.- М.: КУДИЦ-ОБРАЗ, 2003 .-240с.

20. Кирьянов, Б.Ф. Аппаратурные методы вычислений на основе стохастического принципа: Дис.докт. техн. наук: 05.13.01 /Б.Ф. Кирьянов.- Казань, 1985.-408с.

21. Кирьянов, Б.Ф. Генератор псевдослучайных чисел с многоразрядным сдвигом /Б.Ф. Кирьянов, P.M. Мансуров; Каз. авиац. ин-т.- Казань, 1978.-7с.-Деп. в ЦНИИТЭИ приборостроения, №923.

22. Кирьянов, Б.Ф. К проблеме формирования некоррелированных псевдослучайных чисел на основе М-последовательностей /Б.Ф. Кирьянов, В.А. Песошин, С.Г. Гришкин //Автоматика и вычислительная техника.-1984,- № 4.-С.70-75.

23. Кирьянов, Б.Ф. Микропроцессорные средства в задачах имитации и обработки случайных сигналов: Учеб. пособие /Б.Ф. Кирьянов.- Новгород: НПИ, 1988.-52с.

24. Кирьянов, Б.Ф. МикроЭВМ как средство имитации и обработки случайных процессов в радиоэлектронных системах /Б.Ф. Кирьянов.- Новгород: НПИ, 1986.-21 Зс.- Деп. В ВИНИТИ 10.11.86, №7646-В86.

25. Кирьянов, Б.Ф. Многоканальный генератор псевдослучайных символов / Б.Ф. Кирьянов //Изв. АН CCCP.-1970.-Cep. Техническая кибернетика.- №4.-С.107-110.

26. Кирьянов, Б.Ф. Основы теории стохастических вычислительных машин / Б.Ф. Кирьянов; Каз. авиац. ин-т,- Казань, 1975.-186с.- Деп. в ЦНИИТЭИ приборостроения 21.05.76, №524.

27. Кузнецов, В.М. Цифровые устройства формирования случайных сигналов с неавтономным источником шума: Дис.канд. техн. наук: 05.13.05 /В.М. Кузнецов.- Казань, 1986.-225с.

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

29. Лидл, Р. Конечные поля /Р. Лидл, Г. Нидеррайтер,- М.: Мир, Т. 2, 1988.-822с.

30. Мансуров, P.M. Разработка и исследование комбинированных генераторов случайных чисел с равномерным законом распределения: Дис.канд. техн. наук: 05.13.01 /P.M. Мансуров.- Казань, 1979.-169с.

31. Метод статистических испытаний (метод Монте-Карло) /Под ред. Ю.А. Шрейдера.-М.: Физматгиз, 1962.-331с.

32. Песошин, В.А. Генераторы псевдослучайных двоичных последовательностей /В.А. Песошин, В.М. Кузнецов //Вычислительные и управляющие системы летательных аппаратов.- Казань: КАИ, 1983.-С.51-56.

33. Песошин, В.А. Линейные рекуррентные последовательности /В.А. Песошин // Тез. докл. III Всесоюзного симпозиума по вероятностным автоматам.-Казань: КГУ, 1983.-С.45.

34. Песошин, В.А. Псевдослучайные последовательности со знакопеременными автокорреляционными функциями /В.А. Песошин // Тез. докл. конф.'.Вероятностные методы и средства.- Новгород: НПИ, 1983.-С.34.

35. Песошин, В.А. Устройства вычислительной техники для генерирования случайных и псевдослучайных последовательностей и чисел: Дис.докт. техн. наук: 05.13.05 /В.А.Песошин.- Казань, 1985.-408с.

36. Петрович, Н.Т. Системы связи с шумоподобными сигналами /Н.Т. Петрович, М.К. Размахнин,- М.: Советское радио, 1969.-232с.

37. Питерсон, У. Коды, исправляющие ошибки /У. Питерсон.- М.: Мир, 1964.-338с.

38. Питерсон, У. Коды, исправляющие ошибки /У. Питерсон, Э. Уэлдон,- М.: Мир, 1976.-594с.

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

40. Самойленко, С.И. Помехоустойчивое кодирование /С.И. Самойленко.- М.: Наука, 1966.-240с.

41. Свердлик, А.Н. Некоторые вопросы образования случайных величин в цифровых вычислительных машинах /А.Н. Свердлик.-Л.:ЛВИКА, 1965.-155с.

42. Таусворт, Р. Случайные числа, порождаемые линейными рекуррентными соотношениями по модулю 2 /Р. Таусворт // Кибернетический сборник.- М.: Мир, 1979, вып. 16.- С.62-73.

43. Теория и применение псевдослучайных сигналов /А.И. Алексеев, А.Г. Шереметьев, Г.И. Тузов, Б.И. Глазов.- М.: Наука, 1969.-367с.

44. Тихонов, В.И. Статистическая радиотехника /В.И. Тихонов.- М.: Советское радио, 1966.-678с.

45. Фараджев, Р.Г. Линейные последовательностные машины /Р.Г. Фараджев.-М.: Советское радио, 1975.-248с.

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

47. Хаффмен, Д.А. Синтез линейных многотактных кодирующих схем /Д.А. Хаффмен //Теория передачи сообщений.- М.: ИЛ, 1957.-С.52-81.

48. Хоффман, JI. Современные методы защиты информации /Л. Хоффман.- М.: Советское радио, 1980.-264с.

49. Цирлер, Н. Линейные возвратные последовательности /Н. Цирлер // Кибернетический сборник.- М.: ИЛ, 1963, № 6.- С.55-79.

50. Цифровые методы в космической связи /Под ред. С.Голомба.- М.: Связь, 1969.-272с.

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

52. Шумоподобные сигналы в системах передачи информации / В.Б. Пестряков, В.П. Афанасьев, В.Л. Гурвиц и др.- М.: Советское радио, 1973.- 424с.

53. Элспас, Б. Теория автономных линейных последовательных сетей / Б. Элспас //Кибернетический сборник,- М.: ИЛ, 1963, № 7. -С.90-128.

54. Яковлев, В.В., Стохастические вычислительные машины /В.В. Яковлев, Р.Ф. Федоров.- Л.: Машиностроение, 1974.-344с.

55. Ярмолик, В.Н. Генерирование и применение псевдослучайных сигналов в системах испытаний и контроля /В.Н. Ярмолик, С.Н.Демиденко.- Минск: Наука и техника, 1986.-200с.

56. Добрис, Г.В. Метод синтеза генератора псевдослучайных чисел для стохастических вычислительных машин на основе двух регистров сдвига /Г.В. Добрис //Автоматика и вычислительная техника.- 1973.- №2.-С.1-7.

57. Добрис, Г.В. Новый принцип построения генератора псевдослучайных чисел на регистре сдвига /Г.В. Добрис // Информационные и измерительные устройства в радиоэлектронике: Докл. конф,- Рига: Зинатне, 1974.-С.109-111.

58. Добрис, Г.В. Об улучшении характеристик генератора случайных чисел с циклическим регистром сдвига /Г.В. Добрис, В.В. Яковлев //Методы и средства преобразования сигналов.- Рига: Зинатне, 1976.-С. 130-133.

59. Добрис, Г.В. О некоторых свойствах генератора псевдослучайных чисел с регистром сдвига /Г.В. Добрис //Труды ЛИИЖТа: Применение ЭВМ при решении железнодорожных задач.- Л.: ЛИИЖТ,1972, вып.335.-С.70-86.

60. Доценко, В.И. Анализ и свойства последовательностей максимальной длины /В.И. Доценко, Р.Г. Фараджев //Автоматика и телемеханика.- 1969.-№11.-С.119-127.

61. Доценко, В.И. Получение ПСДС и его использование для идентификации объектов / В.И. Доценко, Г.С. Чхартишвили //Докл. конф.- М.: МЭИ, 1967.-С. 180-192.

62. Кирьянов, Б.Ф. Об анализе последовательности псевдослучайных чисел, генерируемых устройством с многоразрядным сдвигом / Б.Ф. Кирьянов, P.M. Мансуров //Методы и средства преобразования сигналов.- Рига: Зинатне, 1978, Т.2.-С.56-58.

63. Корн, Г. Моделирование случайных процессов на аналоговых и аналого-цифровых машинах/Г. Корн,- М.: Мир, 1968.-315с.

64. Лезин, Ю.С. Оптимальные фильтры и накопители импульсных сигналов /Ю.С. Лезин.- М.: Советское радио, 1969.-448с.

65. Осмоловский, С.А. Стохастические методы защиты информации /С.А. Осмоловский.- М.: Радио и связь, 2003.-320с.

66. Watson, E.J. Primitive polynomials (mod 2) /J.E. Watson //Mathematics of computation.-1962.- Vol. 16.- P.368-369.

67. Хоровиц, П. Искусство схемотехники /П. Хоровиц, У. Хилл.- М.: Мир, Т.2, 1983.-590с.

68. Кугураков, B.C. Множество длин циклов взаимно-однозначных афинных отображений пространства Vn (GF(p)) на себя /B.C. Кугураков, О.Б. Соколов //Ученые записки КГУ, 1969, Т.129,к.4.-С.74-79.

69. Букреев, И.Н. Микроэлектронные схемы цифровых устройств /И.Н. Букреев, Б.М. Мансуров, В.И. Горячев.- М.: Советское радио, 1975.-368с.

70. Шнайер, Б. Прикладная криптография /Б. Шнайер //http://www.ssl.stu. neva.ru/psw/cripto.html.

71. Andrew, A.M. Counting to 1099508482050 without carries /А. Andrew //Electron. Eng.- I960.- Vol.38,№ 457.- P.172-175,203,210.

72. Кирьянов, Б.Ф. Об анализе последовательности псевдослучайных чисел, генерируемых устройством с многоразрядным сдвигом / Б.Ф. Кирьянов, P.M. Мансуров //Методы и средства преобразования сигналов.- Рига: Зинатне, 1978, Т.2.-С.56-58.

73. Песошин, В.А. Комбинированный генератор случайных чисел /В.А. Песошин, P.M. Мансуров, В.М. Кузнецов //Вероятностные методы и кибернетика.-Казань: КГУ, 1982, вып. 19.-С.88-99.

74. Neuman, F. Autocorrelation peaks in congruential pseudorendom number generators /F. Neuman, R.B. Merrick //IEEE Transactions on Computers.- 1976.-Vol.25,-№5.-P.457-460.

75. Neuman, F. The autocorrelation structure of Tausworthe pseudorendom number generators /F. Neuman, C.F. Martin //IEEE Transactions on Computers.- 1976.-Vol.25,-№5.-P.460-464.

76. Гришкин, А.С. Двоичные линейные рекуррентные последовательности на основе регистров сдвига /А.С. Гришкин //Материалы международной молодежной научной конференции «XII Туполевские чтения», T.III, Казань, КГТУ, 2004.-С.68-69.

77. Гришкин, А.С. Псевдослучайные двоичные последовательности на основе регистров сдвига /А.С. Гришкин //Материалы международной молодежной научной конференции «XII Туполевские чтения», T.III, Казань, КГТУ, 2004.-С.69-70.

78. А.с. 1040486 СССР. Генератор псевдослучайной последовательности /В.А. Песошин, В.М. Кузнецов, О.И. Дапин//Б.И. 1983. - №33.

79. Песошин, В.А. Генераторы случайных чисел на микропрограммируемых БИС /В.А. Песошин, М.И. Бурнашев, В.М. Кузнецов //Вопросы радиоэлектроники, сер. ЭВТ, вып.6, 1991.-С.77-88.

80. Песошин, В.А. Цифровые генераторы случайных сигналов для защиты информационных средств телекоммуникации /В.А. Песошин, В.М. Кузнецов //Вопросы радиоэлектроники, сер. ЭВТ, вып.4, 1993.-С.95-113.

81. Бахарев, А.Н. Оценка степени предсказуемости поведения цифровых генераторов случайных чисел / А.Н. Бахарев, А.С. Гришкин, В.М. Кузнецов, В.А. Песошин //Тезисы докладов III Всероссийской НТК, Часть 8.-Н. Новгород, НГТУ,1998.-С.29-30.

82. Бахарев, А.Н. Разработка методов построения генераторов случайных кодов на программируемых СБИС /А.Н. Бахарев, А.С. Гришкин //Раздел отчета, КГТУ; Руководитель работы В.А. Песошин; № ГР 01990000840; Инв.№ 02.200.107450. Казань, 2000.-25с.

83. Гришкин, А.С. Оценка корреляционных свойств случайных цифровых последовательностей в среде программируемых БИС /А.С. Гришкин, В.М. Кузнецов //Тезисы докладов 5 Всероссийской НТК, Часть З.-Н. Новгород, НГТУ,2000.-С.32.

84. Гришкин, А.С. Статистическое исследование генераторов случайных чисел на программируемых логических интегральных схемах: Магистерская дис. работа /А.С. Гришкин.- Казань, 2001.-125с.

85. Гришкин, А.С. Синхронная интерпретация работы генератора асинхронного случайного сигнала /А.С. Гришкин, В.М. Кузнецов, В.А. Песошин// Вестник КГТУ им. А.Н. Туполева, №3, 2006.-С. 19-21.