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

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

Иллюстрации

Показать все

Реферат

 

Союз Советских

Соцналнстнческнх республик

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЙТЙЛЬСТВУ

<»634329 и и . (61) Дополнительное к авт. свил-ву (22) Заявлено 27. 10.76 (2l ) 24 15584/18-24 с присоединением заявки № (23) Приоритет и (5I) М. Кл.

Ст 07 С 15/00

G 06 Р 1/02

Государственный квинтет

Совета ееннкетров СССР во делам нзобретеннй н открытнй (43) Опубликовано25.11.78.Бюллетень %43 (53} УДК 681.325. (088.8) (45) Дата опубликования описания 28,11,78 (72) Авторы изобретения

В. Н. Ярмолик и А. H. Морозевич (71) Заявитель

Минский радиотехнический институт (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

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

Известны генераторы псевдослучайных чисел, основанные на применении регистр ров сдвига. Простейшим генератором псевдослучайных чисел на базе регистра сдвига tO яв ляетс я и ос ле довате льный генератор псевдослучайных чисел (ГПСЧ) (1). В таком re нераторе очередное двоичное число обра» зуется на выходе 1 разрядов регистра сдвига через и -K импульсов сдвига. Частота выборки псевдослучайных чисел в

Й раз меньше, чем тактовая частота.

Другой из известных генераторов псевдослучайных чисел для повышения быстродействия на один разряд содержит

m + m () триггеров, что обуспев пивеет его епперетуриую иооыточвость(2). 2

Наиболее близким техническим решением к данному изобретению является генератор псевдослучайных чисел, содержащий Al сумматоров по модулю два í N триггеров, входы синхронизации которых подключены к выходу генератора тактовых импульсов)3j.

Недостатком этого генератора также является алпаратурная избыточность.

Целью изобретения является упрошение генератора °

Для достижения поставленной цели единичные выходы триггеров подкаочены к первым входам сумматоров по модулю два соответственно, вторые входы старших сумматоров по модулю два подключены . кединичнымвыходам t мпа ших триггеров соответственно, счетные входы 2i- rrr старших триггеров соедине-ны .с единичными выходами 2i - пт младрших триггеров соответственно, счетные входы2а-Zi младших триггеров соединены с выходами2Ю-2 старших сумматоров по модулю два соответственно, вто, 6343 рые входы rrl « «i мпадших. сумматоров по модупю два подключены к выходам е йЧ - 1 старших сумматоров по модулю два соответственно.

Бпок-схема генератора для спучая у

1й - 5 (rrl -число разрядов генератора) приведена на чертеже.

Генератор содержит и триггеров 1, входы синхронизации которых подключены к генератору тактовых импупьсов 2, 16

И сумматоров по модулю два 3, первые входы которых соединены с единичными выходами триггеров, а вторые входы 1 старших сумматоров по модупю два соединены с единичными выходами i мпад- 13 ших триггеров, вторые входыт-i младших сумматоров по модулю два соединены с

N- < выходамистаршихсумматоровцо модупюдва,счетныевходы2 -m старшихтриггеров соединены с единичными выходами 2i - rn е мпадших триггеров, а счетные входы 2rrl -2 младших триггеров соединены с выходами

2m - 2 I старших сумматоров по модулю два.

Работает генератор следующим образом. Начальное псевдослучайное чиспо имеет вид о 1 Ь Ь ° ° ° Ь щ где Ю разрядность регйстра сдвига,йа базе которого основан генератор. Чиспо О < b H ... ... Ь,п снимается с выходов сумматоров о по модулю два слева направо, а чиспо

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

40 число = 0 Ь „, b „ . При поступлении очередного тактового импульса попучаетси спеиуюшее чиспс f > и е. П. Иефуииционирования многоканального генератора псевдоспучайных чисел очевидно, что данное устройство имеет максимальное быст- родействие, т..е. за один такт попучается следующее число. В данном спучае быстродействие определяется только элементной базой. Структурный состав генератора показывает, что при минимальных

Ю затратах оборудования получается 2 rrl разрядное псевдоспучайное число. ElGHHbHR генератор, как и все генераторы на базе регистра сдвига с сумматором по модупю

И два, генерирует М - последовательность, свойства которой хорошо изучены.

Аналитически функциональные связи

gIIB построения многоканального генерато29 4 ра псевдослучайных чисел дпя любого значения легко определить иэ следующей системы уравнений (1): и к .1 „- 2 -, уп+,-, ) = 0,1,2 „.. rrl - 1 +1 к к

2э- 2m-j g j s

МФА где ц <> — содержимое ипи значение

rrl -j разряда ГСПЧ в К+1 такт работы устройства.

Ипя пояснения аналитической зависимости (1) и функционирования генератора на чертеже приведена конкретная структура для m = 5. Легко видеть, что функциональные связи структуры подчиняются вышеприведенной системе уравнений (1). Так, например, дпя m "- 5, = 3 система уравнений (1) имеет вид lQ= lO@ Ь

bqqbq e Ь

Ь8Ь Е b4

b7 7+ 3 ь=ь что попностью соответствует функционапьным связям между узлами многоканального генератора псевдослучайных чисеп, приведенного на чертеже.

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

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

634329 звп, что предлагаемый многоканальный генератор псевдослучайных чисел имеет максимвпьное быстродействие (т. е. это устройство однотактное) и самые миниЮ мвпьные удепьные затраты оборудования по сравнению с известными. причем очередное число получается зв один такт, и разрядность этого числа равняется 10, т. е. в общем случае 2п .

Лпя последовательного генератора последовательность состояний триггеров будет иметь вид:

1, 1 1 1 0 0 1 1 0 1 0

2. 1 1 1 1 0 0 1 1 0 1

4.0 1 1 1 1 1 0 0 1 1

5.0 0 1 1 1 1 1 0 0 1

6. 1 0 0 0 1 1 1 1 1 0

7. 1 1 0 0 0 J 1 1 1 1

80 1 1 0 0 0

9. 1 0 1 1 0 0 0 1 1 1

10,1101100011

Очевидно, что очередным псевдослучайным числом может являеться только такое число, которое получается через И « 10 тактов, т. е. очередным после ф о яв i ляется число с 1 . Иэ вьпцеприведенного пегко видеть, что Е„=g< и Г но получение F сопряжено с большими временными затратами.

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

Если в прототипе удельные затраты оборудования на один разряд составпяпи один триггер со счетным входом, то в предлагаемом генераторе 1/2 триггера плюс 1/2 сумматора по модулю. два. И в то же

Ю время быстродействие такого генератора максимально. РатенFHbN гоиск пока5

Г, Ь1Ь Ь ЬДЬ Ь Ь Ь Ь Ь|д

,=1 оо1 о о

E„-S Î «ООО1 форму па изобретения

Генератор псевдослучайных чисел, содержащий nt сумматоров по модупю два и п1 триггеров, входы синхронизации которых подключены к выходу генератора тактовых импульсов о T п и ч & ю щ и Й» с я тем, что, с целью упрощения генератора, единичные выходы триггеров подключены х первым входам сумматоров по модулю два соответственно, вторые входы старших сумматоров по модулю два подключены к единичным выходам 3 мпадших триггеров соответственпо, счетные входы 21 — Al старших триггеров соединены с единичными выходами 2<-щмпадших триггеров соответственно, счетные входы 2m- 21 младших триггеров соединены с выходами 2 -2 i старших сумматоров по модулю два соответственно, вторые входы л — (младших сумматоров пс модулю два подключены к выходам т-i старших сумматоров по модулю два соответственно.

Источники информации, принятые во внимание при экспертизе, 1. Яковлев В. В.„,Федоров Р. Ф. „

Стахастические вычислительные машины °

Л., Машиностроение, 1974, с. 24625 3.

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

%468231, кп. Я 06 F 1/02, 14..09.73.

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

Л%543962, кп. Cj 07 С 15/00, 16,06.75.

634329

Сос авитепь А Карасов

Редактор jl. Мепуришвипи Техред М. Борисова Корректор А. Гриденко.

Заказ 6767/50 Тираж 688 Подписное

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

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

Фипиап ППП "Патент", г. Ужгород, уп. Проектная, 4