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

 

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

(1% (И!

СОКИ СОВЕТСНИХ санци|

РЕСПУБЛИН у у G 06 F 7/58

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ":

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

Н АВТОРО4ОВВУ СВИДЕТЕЛЬСТВУ (21) 3408623/18-24 (22) 12 ° 03.82 (46);30.06.83. БюлУ24 (72 )- А.С. Анншин и Е. И. Губин (53) 681.325(088.8) (56) 1. Авторское свидетельство СССР

9 210471, кл. 906 Г 7/58, 1967.

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

Р 193163, кл. 006 f 7/58, 1966.

3. Авторское свидетельство .СССР Р 195711, кл. ц06 F 7/58, 1966 (прототип) . (54 ) (57 ) ГЕНЕРАТОР PABH0REPH0 PAC- i

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

1О2Ы42

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

Известен генератор случайных дво- счет обеспечения равномерности рас.-» ичных чисел, построенный по схеме пределения и их независимости. с параллельным генерироваиием разря- Для достижения поставленной цели доз и содержащий группу элементов, в генератор, содержащий генератор равновероятных.двоичных цифр, регистр 10 пуассоновского потока иьшульсов, двоичного числа и вентили, 1акой выход которого соединен с единичным генератор характеризуется высоким входом первого разряда регистра сдви ,,быстродействием и высоким качеством ra и первым входом элемента ИЛИ, случайных чисел 1 . второй вход которого соединен с нуОднако генератор требует большого 15 левым входом первого разряда регистобъема электронного оборудования. ра сдвига и генератор тактовых имИзвестен простой по устройству пульсов., выход которого подключен генератор равномерно Распределенных к пеРвым Входам элементбв И группы, двоичных чисел, содержащий генера- вторые входы которых соединены с едитор случайных импульсов, триггер, 2О ничными выходами,соответствующих. ра . регистр сдвига, вентили 2 . рядов регистра сдвига, а выходы элеНа формирование одного Разряда ментов И группы образуют группу выдвоичного числа, затрачивается в ходов генератора, введены первый и среднем 3-4 импульса случайяого второй элементы задержки, вход котопотока генератора, что является при» 2 рого соединен с выходом генератора чиной сравнительно низкого его ы- пуассоновского потока импульсов, стродействия . а выход второго элемента задержки

Наиболее близким по технической соединен с вторым входом элемента сущности и достигаемому результату - ИЛИ, выхоД котоРого через пеРвый к предлагаемому является устройство элемент задержки соединен с вхо дл генерирования равномзрно. распре" Зо Дом "СДвиг" РегистРа сДвига. деленных случайных двоичных чисел, В пРедложенном УстРойстве формисодержащее два генератора случайных рование второго потока, статистичесимпульсов, выходы которых подключены ки независимого и идентичного по раздельно к выхода»» "О" и "1 первого .,интенсивности потоку, осуществля» триггера регистра сдвига и через эле З ется линией временной задержки, ко.. мент ИЛИ к продвигающей шине регистра,торая выполняет Роль статистичеси генератора тактовых импульсов,под кой Развязки. Из-за отсутствия Меченный к схемам совпадений, откры- последействия в пуассоновском потоке ваемым триггерами регистра, устройст импульсов необходимая величина временво обладает высокой скоростью геяери-40 . ной задержки незначительна и составрования случайных двоичных чисел. для ляет (4-5) :1/g средних периодов слеформироваяия одного разряда двоич- . дования случайных импульсов первичноного числа затрачивается один случай- го потока ° ный импульс (.3 . На чертеже приведена структурная

Недостатком устройства является 4 схема предложенного устройства. низкое качество случайных двоичных > Генератор содержит генератор 1 чисел, обусловленное двумя причинами. .пуассояовского потока О импульсов, Во-первых, известна принципиальная элемент 2 задержки, элемент 3 ИЛИ, трудность построения двух идентичных,, элемент 4 задержки, регистр 5 сдвига, генераторов случайных импульсов, фор- 50 генератор б тактовых импульсов, груп-, мирующих потоки с равными интенсив- пу 7 элементов H.

1 ностями, в особенности на больших интервалах времени их работы. устройство работает следующим обЛоейф интенсивностей потоков двух, Ра ом. используемых в устройстве генераторов Генератор 1 вырабатывает пУассоприводит к нарушению баланса вероит-, <новский поток О импульсов с интенсивностей появления "O и "1" B произ- ностью Л . Ha выходе элемента 2 завальном разряде двоичного числа р(0) держкя каждый импульс первичного пою

P(1),"oTâe÷àþùåão" за равномерное тока смещается по времени на величину .распределение случайных чисел. . (4:5) 43 i прн которой импульсные

46 потоки на единичном и нулевом входах

Во-вторых, использование в уст- первого Разряда регистра 5 сдвига ройстве генераторов случайных импуль" . являются. статистически независимыми. сов с произвольными вероятностными .На выходе элемента ИЛИ 3 формируется свойствами (характеристиками) не . .. суммарный поток интенсивностью 2)L гарантирует независимости состояний у :импульсы которого через элемент.4

1026142

ВИИИПИ Заказ 4560/41 Тираж 706 Подписное

° ю ааюю

Филиал ППП "Патент"„ r. ужгород, ул. Проектная, 4 задержки осуществляют продвижение инФормации, записываемой в первый (приемный) разряд регистра 6 сдвига.

Элемент 4 задержки служит целям временного разделения записи информации и продвижения ее по разрядам.регист» ра 5, осуществляемых одним импульсом.

Реальный спектр флвктуаций (дрейфа) интенсивности ) (1) генератора 1 примыкает к области "нулевых" частот,,поэтому изменение интенсивности .Л(4 ) за время Vy=(4:5) 1(g (равное 8-10 мкс прн А5106 нмп/с) является незначитель ныл н соотношение Р.(4) = А(т; ь Ч: ) выполняется с высокой степенью точности. Равенство интенсивностей пото-15 коэ на единичном и нулевом .входах первого разряда регистра 5 сдвига обеспечивает абсолютное выравнивание вероятностей появления "0" н "1" в разрядах регистра 5 Р (1) = Р(0) 20 0,5, и следовательно, равномерное распределение случайных двоичных чисел.

Для обеспечения независимости случайных чисел требуется выполнение двух условий: полная смена информации, записанной в разрядах регистра

5, и независимость состояний разрядов регистра сдвига.

Первое условие выполняется выбором соответствуксаей частоты Fo такто- вых импульсов генератора 6 Го NP> где И- число разрядов формируемого двоичного числа.

Выполнение второго условия обеспечивается использованием в качестве генератора 1 датчика пуассоновского потока импульсов, который обеспечивает Иезависнмость состояний разрядов двоичного числа.

Признаком независимости элемен- 40 тарных событий, появляющихся с вероятностями P = ф =0,5, является геомет-, рическое распределение серий амежных успехов ф (фнеуспехов ф (N)) заданнойй длины 8 1,2<3i ° ° ° . ° 45

p()=q4)*(i )" и=4,4„., Ц), В предлагаемом устройстве вероятности (й) появления в разрядах ре гистра 5 сдвига, серии МЭ (i 1,2,;

"едвниц" ("нулей" ) равны вероятностям Q появления и импульсов пер- . вичного (задержанного,) потока на случайном интервале между импульса« ми задержанного (первичного) потока. ОпРеделнм веРоЯтности фи . ВРеменной интервал Ф между ш пульсаии уассоновского потока распределен по экспонеициальному закону

k(e)=Re, Ч," О, <1) а вероятности появления И=0,1 2 ... импульсов эа фиксированный отрезок :« Г определяются выражением

+ +o) ЮА ь и (,) = н -e ; T, ÚÎ, (ъ)

Вероятности РИ находим с помощью операции осреднения 9 (Ц ) по всем возможньм значениям интервала ОФГо<Ф

Оь 1+4

Р„(Ю) ()6 Г= „, Р е л (4): о

По таблице интегралов

Фь

1 -""е - 1(1л) "" (в)

В результате подстановки (В) и (4/: распределейие -Р, принимает вид геометрической прогресаии О/И" "= д,з... «>l что:с учетом (1) свицетельствует о независимости состояний разрядов региСтра 5 сдвига. При этом получен ный результат в виде соотношения (6) справедлив только для пуассоновского потока.

Отсюда следует, что для обеспечения независимости двоичных чисел генератор .1 должен. быть выполнен в виде датчика пуассоновского потока импульсов. Для обеспечения пуассонов-., аких.свойств потока импульсов генератора 1 уррвень Ц отсечки порого» вого элемента должен выбираться Из условия

"о

I где Г- действукщее значение напряжения шума на входе порогового элемента.

Таким образом, введение новых элементов и связей обеспечивает рав намерное распределение и,независимость случайных двоичных чисел;

При этом методическая погрешность устройства определяется только .величиной С .задержки элемента 2 и практически сводится к нулю при Т е

= (4-5)"1 /,3---Необходимая,.абсолютная величина

С уменьшается с возрастанием интенсивности ., гейератора 1. При

= 5 10 имп/с составляет 8-10 мкс и может быть получена с помощью элементов задержек с сосредоточен ными. параметраиц, По быстродействию предложенное устройство не :уступает прототипуг каждый импульс генератора 1 формируетI два независимых разряда случайного двоичного числа.