Генератор случайной последовательности

Генератор случайной последовательности

Иллюстрации

Показать все

Реферат

 

ГЕНЕРАТОР СЛУЧАЙВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ , содержащий блок задержки , сумматор по модулю два, отличающийся тем, что, с целью повышения ef о быстродействия, он содержит -элемент НЕ, вход которого подключен к выходу сумматора по модулю два, а выход элемента НЕ соединен с входом асинхронного блока задержки, выходы которого соединены с входами сумматора по модулю два соответственно.

СОЮЗ СОВЕТСКИХ

Э,И Л

РЕСА)УБЛИК

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 2822848/18-24 (22) 03.10.79. (46) 07.09.83. Бюл, 9 33 (72) В.A.Ïåñoøèí, B.М.Кузнецов и О.И.Дапин (71) Казанский ордена Трудового Красного Знамени авиационный институт ,им. A.Н.Туполева (53) 681.325(088 ° 8) (56) 1. Корн Г.A. Моделирование случайных процессов на аналоговых и аналого-цифровых машинах. М., Мир -,, 1968 °

2. Авторское свидетельство СССР

9 391556, кл. G 06 F 1/02, 1972.

3. Авторское свидетельство СССР .

9 337776, кл. G 06 F 1/02, 1969 (прототип).

„„SU „„1040486 A

3(51) G 06 F 7/58 У G 07 С 15/00 (54)(57) ГЕНЕРАТОР СЛУЧАЙНОЙ ПОСЛЕДОBATEJIbHOCTH, содержаший блок задержки, сумматор по модулю два, о т. л ич а ю щ н и с я тем, что, с целью по" вышения его быстродействия, он содержит элемент НЕ, вход которого подключен к выходу сумматора по модулю два, а выход элемента НЕ соединен с входом асинхронного блока задержки, выходы которого соединены с входами сумматора по модулю два соответственно.

1040486

Изобретение относится к вычислительной технике, тохнике измерения и связи, может быть использовано В стохастических вычислительных машинах, при построении генераторов случайных чисел для ЦВМ, а также для имитаторов случайных помех при испытании различной аппаратуры и каналов связи

° Известен генератор случайной последовательности, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи (1) .

Недостатком этого генератора является наличие детерминизма в формируемой последовательности, свойственно- 15 ro всем псевдослучайным сигналам.

Известен также генератор случайной последовательности, содержащий регистр сдвига с сумматором по моду-. лю два в цепи обратной связи. В этом gp генераторе частота тактовых импульсов, осуществляющих сдвиг информации в регистре, изменяется по случайному закону (2) .

Символы в выходной последовательности такого генератора изменяются в случайные моменты времени, но порядок смены этих символов детерминированный, что составляет основной недостаток açâåñòíoão устройства.

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

ОДнако быстродействие этого генератора.ограничено максимальной частотой импульсов сдвига регистра, Обычно для надежной работы таких синхрон-45 ных цифровых устройств тактовая .частота должна выбираться примерно с

5-10-кратным запасом по отношению к реальным частотным возможностям схемы (3) .

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

HE соединен с входом асинхронного блока задержки, выходы которого соединены с входами сумматора по модулю 60 два соответственно, На чертеже представлена структурная схема генератора. генератор случайной последователь .ности содержит асинхронный блок 1 за« 65 держки, который нечетным количеством

ВыхОДОВ 1 12 °, ° 1 > пОДООеДинен к входам сумматора по модулю два. Выход сумматора 2 подключен через элемент НЕ 3 к входу асин*ронного блока

1 задержки.

В качестве асинхронного блока задержки 1 могут быть использованы, например, линия задержки или асинхронный регистр сдвига, т.е. такой блок задержки, у которого время задержки есть величина непрерывная и флуктуирующая во времени. Необходимо также, Чтобы время задержки было значительно .больше величины, обратной верхней граничной частоте асинхронного блока задержки.

Обозначим через с„, 72,... ь,временные задержки по соответствукщим выходам асинхронного блока 1 задержки. Тогда флуктуации этих задержек можно оценить через среднеквадрати" ческие отклонения соответственно

@C<<13,4Г"21,.—, 6Г- j

Для работы ус тройс тв а в к ачес тв е генератора случайной последовательности необходимо, чтобы отношения математических ожиданий времени задержки М (,Д N C 2 j,..., М „ между. собой выражались ирраци6нальными числами или практически равнялись взаимно несократимым отношением достаточно больших целых чисел м ".„ - ;.;

Г 2) 2"

>E ë2 > где K« K<..., K„- целые взаимно несократимые числау Ф 4 - единая мера измерения М(Д(1=1, n)

В идеальном случае, когда отношения М(С, M(i>),..., М(Гп)между собой.

Выражаются иррациональнйки числами, Зс, — <а, а -з 6.

Чем больше относительные величины флуктуаций d(t ) М(Ъ;.), тем слабее требования K иррациональности отношений математических ожиданий времен задержки.

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

Предположим, что флуктуации времен- ных .задержек отсутствуют, т.е.4C -1ijQ; следовательно,М ; ) ь;. Тогда функцио нирование данного устройства можно описать как работу генератора псевдослучайных последовательностей, основанного на регистре сдвига с линей ной обратной связью, т.е. можно ус-ловно счи ать, что блок 1 задержки выполнен в виде синхронного регистра.10404В6 сдвига, являющегося синхронным блоком задержки, с числом разрядов

Ф= " (К„), С разрядов k; сигналы поступают на входы сумматора по модулю два. Частота импульсов сдвига ре-. .гистра F l/Г. В этом случае устрой- S ство будет формировать псевдослучайную последовательность с периодом

Структура и длина этой послвдова тельности определяется конкретными значениями )с,1, к, .,. kgb т.е. могут, быть как последовательности маКсимальной длины (М - последователь- 15 ности), так и последовательностичастных циклов . В идеальном случае условие иррациональности выполняет-, ся полностью L ce и С- О, так как, К,- св. 20

Прахтически .же Y„, i>,..., i.„иепрерывно флуктуируют во времени. В этом случае устройство будет вырабатывать случайную последовательность.

Так как в течении времени k и ь бу- 25 дут постоянно изменяться, следовательно будет изменяться случайным образом и структура выходной после, довательности, т,е, последователь" ность на выходе будет состоять из щ случайных по длительности отрезков псевдослучайных, последовательностей различных структур с различными .(случайными) масштабами по времени Ф..

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

При этом частота сдвиговых импульсоврегистра также должна изменяться согласно формуле .45 . F = с = м ФД

I .Таким образом, путем предельного . >щ .перехода от синхронной модели генератора псевдослучайной последовательностИ получается асинхронная модель предлагаемого устройства. Функции такого бесконечно длинного регистра со случайно изменяющейся частотой сдвига и случайными подключениями к суммато-, ру по модулю два может выполнить асинхронный блок задержки, например широкополосная линия задержки с отводами. В рабочем диапазоне температур ® линия задержки.небольшими флуктуацй» ми времени задержки 6(7;)/М(г;) порядка тысячных долей вдинйцы. Ъри реальной воэможности выбора степени иррациональности отношений Mpi;$ и Я,... », 45

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

Пусть на выходе сумматора 2 сформировался сигнал х(х=0,1 — логическая переменная), тогда сигнал х с выхода элемента HE 3 поступает на вход асинхронного блока 1 задержки.

С,выходов 1 блока данный сигнал х будет поступать на входы сумматора 2 последовательно, через соответствующие отводам 1,, 1,..., 1> промежутки времени. В любой момент времени на входах сумматора 2 действуют логические сигналы, соответствующие сигналам, сформированным в разные моментЫ времени элементом HE 3. ЕСли количество сигналов 1 на входах сумматора по модулю два 2 четное, то на выходе элемента HE 3 формируется сигнал ™1, если нечетное, тосигнал 0 . Порядок смены логических уровней и длительность каждого элемента выходной последовательности определяется на каждый момент времени соотношениями времен задержки по одам 1., 12 ° 1 > блока 1 задержки. Следовательно; в каждый момент времени выходная последовательность будет иметь псевдослучайный характер. Но, так как соотношения этих времен задержки в силу их флуктуаций постоянно изменяются случайным образом, то каждому последуницему моменту времени будет соответствовать другая. псевдослучайная последовательность, и в течение всего, времени выходная последовательность устройства будет представляться уже случайной. .Минимальная длительность действия логического сигнала, определякщая ширину спектра выходной последовательности, определяется реальным быстродействием элементов схемы.

Чем больше и тем легче добиться высокой степени иррациональности отношений М(. ), М(1),..., М C „ между собой и тем эффективяве .действуют малые временные флуктуации асйнхронного блока 1 задержки на процесс формирования случайной последовательности. Но, если и четное, то генератор может перейти в устойчивое состояние (0 на выходе и 1 на всех входах сумматора 2) и генерация случайной последовательности прекратится.

Благодаря выбору нечетного и и наличию элемента НЕ 3 схема генератора устойчивого состояния не имеет.

Действительно, если на выходе сумма-. тора 2 установится 0",.то на всех вго входах в устойчивом состоянии. 1040486

Составитель A.Êàðàñåâ, Редактор И . Ков альчук Техред М. Кузьма Корректор Ю.Макаренко

Заказ 6930/53 Тираж 706 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП Патент ., г.ужгород, ул.Проектная, 4 должны сформироваться 1, но так как и нечетное число, это потребует установления . на выходе сумматора 2. Пусть на выходе сумматора 2 установилась 1, тогда в. устойчивом состоянии на его входах должны сформироваться 0, что привело бы к изменению сигнала на 0 на выходе сумматора 2 и т.д. Таким образом, подобная схема при нечетном и не может списываться статическими ло-1О гическими уравнениями, что доказывает невозможность существования устойчивых состояний схемы.

Асинхронный режим работы устройства позволяет, во-первых, эффективно 15 влиять малым флуктуациям временных параметров элементов схемы на формирование выходной последовательности без участия дополнительного источника случайного процесса„ что упрощает устройство, во-вторых, надежно работать элементам схемы с предельным быстродействием, что, в конечном итоге, увеличивает быстродействие всего генератора примерно в 5-10 раз по сравнению с быстродействием прототипа. Увеличение быстродействия устройства в данном случае аналогично расширению спектра формируемой случайной последовательности,