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

 

Союз Сов

А. И. Кордюмов и И. Е. Фрдлова

l (12) Авторы изобретения

Харьковский ордена Ленина политехни им. В. И. Ленина (7I) Заявитель (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ троля.

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

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

Однако этот генератор не позволяет выявлять неисправности в процессе его работы (1 ).

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

Недостатком является большое чис

IO ло тактов, необходимое для определения наличия неисправности в генераторе псевдослучайных чисел, большие аппаратурные затраты на реализа" цию схемы контроля, неработоспособ1f ность схемы контроля при неисправности, приводящей к появлению "О" на прямом и инверсном выходе i-ão разряда регистра сдвига.

Цель изобретения - упрощение схе20 мы генератора, а также повышение быстродействия при контроле неисправности и повышение достоверности кон90754

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

ИЛИ, элемент задержки, сумматор по модулю два и триггер, выход которого соединен с первым входом сумматора по модулю два, выход которого соеди- tp нен с первым входом элемента И, выход которого через элемент задержки соединен со счетным входом триггера, выход рекурентного регистра сдвига соединен со вторым входом сумматора по модулю два, выход которого соединен с первым входом элемента ИЛИ, выход которого соединен со входом

"Сброс" счетчика, счетный вход которого объединен с тактовым входом 2о рекурентного регистра сдвига, вход

"Установка" которого соединен со вторым входом элемента ИЛИ и через элемент НЕ - со вторым входом элемента И. 25

На чертеже представлена блок-схема генератора, Генератор состоит из и-разрядного рекурентного регистра 1 сдвига, к которому от генератора тактовых им- Elg пульсов по шине 2 подают тактовые сигналы, которые также заведены на тактовый вход 3 счетчика 4. Сигнал установки генератора в исходное состояние подают на установочный вход регистра 1 сдвига и через элемент

ИЛИ 5 - на вход Сброс" б счетчика

4 от входа "Установка" 7 через элемент НЕ 8, элемент И9, элемент 10 задержки - на счетный вход триггера 4

ll. Выход 12 последнего разряда регистра 1 сдвига соединен со входом сумматора 13 по модулю два, выход которого заведен на входы элементов

И9 и ИЛИ 5. Выход триггера 11 подключен ко входу сумматора 13.

Генератор работает следующим образом.

Принцип контроля работы генератора основан на том свойстве псевдослучайной последовательности, что число следующих подряд сигналов одного значения (0 или 1.) в серии, которая снимается с последнего разряда регистра 1 не должно превышать "и".

В исходное положение регистр 1 сдви" га приводят в режиме параллельного занесения информации, при котором

? 4 в регистр записывают исходное число, постоянно заведенное на входы параллельной записи (не показаны), запрещенным является только одно состояние регистра 00...0) Для выполнения этой операции на Шину 7 установки подают сигнал единичного уровня.

Этим же сигналом, проходящим через элемент ИЛИ 5 на шину сброса 6, устанавливают в "0" все разряды счетчика 4. Контур A,ñîñòîÿùèé из сумматора 13 по модулю два, элемента И 9, элемента 10 задержки, триггера EE предназначен для сброса счетчика 4 в "0" при каждом изменении значения информации на шине 12. Для подсчета числа следующих подряд 0 или 1 на шине 12, выход сумматора 13 по модулю два должен быть в состоянии "0". которое позволяет счетчику 4 вести подсчет числа тактов в серии сигналов одного значения (допустим н0") на шине 12. Условия работы счетчика

4 обеспечиваются при равенстве сигналов на обоих входах сумматора 13 по модулю два. При изменении значения сигнала на шине 12 (допустим с "0" на

"1"), на выходе сумматора l3 по модулю два возникает единичный сигнал и сбрасывает все разряды счетчика в "0". Этот же единичный сигнал проходит через элемент И 9, задержку 10 на счетный вход триггера El и положительным фронтом перебрасывает триггер 11 в противоположное состояние.

Изменившийся на выходе триггера 11 сигнал, заведенный на вход сумматора 13, вновь восстанавливает на выходе сумматора 13 по модулю два сигнал "О", позволяющий начать счетчику 4 подсчет числа следующих подряд сигналов другого значения (допустим "1" в серии сигналов, снимаемых с шины 12. Работа счетчика 4 продолжается до момента очередной смены сигнала на шине 12. Величина задержки 10 выбирается такой, чтобы суммарная задержка в элементах контура А была достаточна для сброса в "0" счетчика 4. При подключении питания триггер ll устанавливаетвя в произвольное состояние. Если это состояние обеспечивает сигнал "0" на выходе сумматора 13, позволяющее счетчику вести подсчет, то элемент И 9 блокирует сигнал угтановки в исходное состояние и не позволяет перебросить сигналу установки триггер 11.

Если же на выходе сумматора 13 уста5 90 новится значение "1", то элемент И 9 пропустит сигнал установки в исходное состояние, который положительным фронтом перебрасывает триггер

11 и приводит схему в состояние готовности.

Появление неисправности в регистре 1 приводит к тому, что один или несколько триггеров этого регистра постоянно находятся в одних и тех же (нулевых или единичных) состояниях. Последовательно сдвигаясь, это состояние не позже, чем через и-1 такт проявит себя на выходе последнего разряда регистра 1. Еще через

n+1 такт схема контроля выдаст сигнал наличия неисправности. Таким образом, предлагаемый ГПСЧ обеспечивает выявление константных неисправностей через L тактов после ее возникновений, 2п ) L ), n+1. Величина L зависит от номера разряда регистра 1, в котором произошла неисправность. Максимальное значение

h-2n имеет место при неисправности в первом разряде регистра 1. Длй известного устройства время обнаружения неисправности составляет Р.R, где k - количество триггеров со счетным входом, В " nределъное отклонение числа единиц в последователь- ности 2п (2"

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

n - входового дешифратора представляет собой определенную трудность.

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

Поэтому для реализации генератора потребуется еще определенное число инверторов, которое не требуется в предлагаемом решении. Так как величи" на n+1 (модуль счетчика 4 в предлагаемом решении) меньше предельного отклонения числа появления единиц

7547 (или нулей) в известном устройстве, то счетчик в предлагаемом решении имеет меньшее число разрядов, чем реверсивный счетчик известного изобретения. Размеры схемы генератора практически не зависят от числа разрядов генерируемых чисел (увеличивается только число разрядов счетчика, равное 1од2п, округленного до большого целого числа), увеличение же и в известном устройстве влечет за собой возрастание аппаратурных затрат на реализацию деян4фратора и увеличивает число монтажных св зей, что приводит к превышению стоимости производства известного генератора по сравнению с предлагаемым.

S о

35 формула изобретения

2О

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

4в ный вход которого объединен с тактовым входом рекурентного регистра сдвига, вход "Установка" которого соединен с вторым входом элемента

ИЛИ и через элемент НŠ— с вторым входом элемента И.

Источники информации, принятые во внимание при экспертизе

1. Патент США Ю 3700869, кл. 235-152, 1972.

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

М 674007, кл. G 06 F 1/02, 1977

{прототип).