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

Размещено на http://www.allbest.ru/

Автореферат

диссертации на соискание учёной степени

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

05.13.05 - Элементы и устройства

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

кандидата технических наук

Гришкин Андрей Сергеевич

Казань, 2006

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

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

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

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

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

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

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

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

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

Ученый секретарь диссертационного совета кандидат технических наук, доцент Козлов В.А.

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

, i = 1, 2, ....

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

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

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

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

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

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

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

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

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

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

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

, i = 1, 2, ...

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

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

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

Краткое содержание работы

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

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

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

(х) = xⁿx^m1

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

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

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

(1)

Характеристический многочлен f(x), являющийся определителем матрицы , равен

(х)

где многочлен (х) соответствует матрице, определяющей связи в цепи обратной связи при коэффициенте .

Для матрицы (1) многочлен (х) имеет вид:

(2)

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

Особенность в периодическую структуру ЛРП при вносит множитель . Поэтому мы рассмотрим недостаточно исследованные и наиболее интересные для практики случаи, когда многочлен (х) имеет вид

(3)

где - неприводимые многочлены степени , , .

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

(4)

где многочлен степени (n - 1) 2 неприводим и примитивен.

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

В ГПСC на регистре сдвига с внутренними сумматорами по модулю два при не на всех выходах формируются -последовательности. В качестве примера рассмотрен многочлен (x), который имеет следующий вид:

= (5)

причем многочлен - неприводим и примитивен.

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



Рис. 2. Схема ГПСC на основе многочлена (5)

Работа ГПСC описывается с помощью квадратной матрицы

С = (6)

Определим запрещенные состояния регистра сдвига из условия . Для триггеров q₁ - q₉ получим соотношения:

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

Состояниям 0 1 или 1 0 триггеров q₂ и q₈ выражения (7) могут соответствовать состояния 0 0 и 1 0 триггеров q₆ и q₉ выражения (8). Комбинации состояний остальных триггеров определим из выражений (12) - (13):

q₁ q₂ q₃ q₄ q₅ q₆ q₇ q₈ q₉

0 0 0 1 1 0 1 1 0, (16)

1 0 0 0 1 1 0 1 1, (17)

0 1 0 0 0 0 0 0 0, (18)

1 1 0 1 0 1 1 0 1. (19)

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

q₁ q₂ q₃ q₄ q₅ q₆ q₇ q₈ q₉

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-го триггеров, и по состоянию 1 1 - -последовательности на выходах 5-го и 8-го триггеров.

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

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

(20)

где многочлен степени (n - 2) 2 неприводим и примитивен.

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

В ГПСC на регистре сдвига с внутренними сумматорами по модулю два при не на всех выходах формируются -последовательности. В качестве примера рассмотрен многочлен (x), который имеет следующий вид:

= (21)

причем многочлен - неприводим и примитивен.

Рассмотрим схему ГПСС рис. 3, построенного на основе многочлена (21).



Рис. 3. Схема ГПСС на основе многочлена (21)

Работа ГПСС описывается с помощью квадратной матрицы С

С = (22)

Определим запрещенные состояния регистра сдвига из условия . Для триггеров q₁ - q₉ получим соотношения:

(23)

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

Состояниям 0 1 или 1 0 триггеров q₄ и q₇ выражения (23) могут соответствовать две комбинации состояний триггеров q₁ и q₆ (при известном значении q₇) выражения (24) и две комбинации состояний триггеров q₅ и q₉ (при известном значении q₆) выражения (25). Комбинации состояний остальных триггеров определим из выражений (26) - (28):

q₁ q₂ q₃ q₄ q₅ q₆ q₇ q₈ q₉

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)

0 0 1 1 0 1 0 0 1, (36)

0 1 0 1 1 1 0 1 0, (37)

1 0 1 1 0 0 0 1 0, (38)

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

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

q₁ q₂ q₃ q₄ q₅ q₆ q₇ q₈ q₉

1 0 1 1 0 0 0 1 0,

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 1 1 с периодом 4 идентифицируем -последовательности на выходах 1-го, 3-го, 4-го, 5-го, 7-го и 9-го триггеров, по состояниям 0 1, 0 1 и 1 0, 1 0 с периодом 2 определяем две -последовательности на выходах 2-го и 8-го триггеров, и по состоянию 0, 0, 0, 0 с периодом 1 - четыре М-последовательности на выходе 6-го триггера.

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

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

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

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

(40)

когда равен , i = 1, 2, ... .

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

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

(41)

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

Рис. 4. Схема ГПСC на основе многочлена (42)

Работа ГПСC описывается с помощью матрицы

С = (43)

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

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

q₁ q₂ q₃ q₄ q₅ q₆ q₇ q₈

1 0 0 1 0 1 0 0 ,

1 1 0 0 1 0 1 0 ,

1 1 1 0 0 1 0 1 (44)

0 1 0 1 1 0 0 1 ,

0 0 0 0 0 1 1 1 ,

0 0 1 0 1 0 0 0 .

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

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

Пусть в многочлене (40) i = 2, т.е.

Тогда периодическая структура ЛРП имеет вид [1(4), 1(4М₂), 1(4М₃), 1(4М₂М₃)]. Последовательность с периодом (4М₂М₃) названа (4ММ)-последовательностью.

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

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

=. (45)

Рис.5. Схема ГПСC на основе многочлена (45)

Работа ГПСС описывается с помощью матрицы С

С = (46)

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

Основные результаты работы

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

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

где многочлен неприводим и примитивен, то при i = 1 при сложении по модулю два на внутренних сумматорах -последовательностей формируются две М- или - последовательности, а при i = 2 при сложении по модулю два -последовательностей могут формироваться две -последовательности или четыре М- или - последовательности.

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Размещено на Allbest.ru

...