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

 

Изобретение относится к вычислительной технике и может быть использовано для создания стохастических вычислительных машин и моделей, а также для построения генераторов псевдо случ айных по следо в ательно стей с заданными характеристиками Цель изобретения - расширение функциональных возможностей за счет возможности генерирования символов с заданной условной вероятностьюо Генератор ,содержит генератор 1 тактовых импульсов , регистр 2 сдвига, блок 3 сумматоров по модулю два, регистр 4 кода, мультиплексор 5, счетчик 6, элемент И 7, триггеры 8, 9. 1 ил0

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51)5 С 06 F 7/58

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

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

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

ПО. ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4662846/24 (22) 20.03.89 (46) 07 ° 04.91. Бюп. N- 13 (72) Л.Т.Кирьяк, С.Н.Филимонов и И.Г.Балык (53) 681 ° 3(088.8) (56) Авторское свидетельство СССР

Ф 1249512, кл. G 06 F 7/58, 1985. (54) ГЕНЕРАТОР СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ (57) Изобретение относится к вычислительной технике и может быть использовано для создания стохастичес„„SU „„1640687 A 1

2 ких вычислительных машин и моделей, а также для построения генераторов псевдо случайных последовательностей с заданными характеристиками. Цель изобретения — расширение функциональных возможностей за счет возможности генерирования символов с заданной условной вероятностью. Генератор ,содержит генератор 1 тактовых импульсов, регистр 2 сдвига, блок 3 сумматоров по модулю два, регистр 4 кода, мультиплексор 5, счетчик 6, элемент

И 7, триггеры 8, 9. 1 ил.

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

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

На чертеже. представлена функциональная схема генератора.

Генератор содержит генератор 1 тактовых импульсов, регистр 2 сдвига, блок 3 сумматоров по модулю два, регистр 4 кода, мультиплексор 5, счетчик 6, элемент И 7, триггеры 8 и 9, первую группу входов 10 мультиплексора 5, вторую группу входов 11 мультиплексора 5, группу входов счетчика 12, первую группу входов 13, вторую группу входов 14 блока суммато25 ров по модулю два, переключатель 15„ входы 16 регистра кода, вход 17 задания начального состояния, вход 18 задания режима.

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

Перед началом работы генератора в регистр 2 сдвига заносится через вход 17 и сумматор 3 по модулю два ненулевой код, управляющий сигналом

"Запись" по входу 17, а в регистр 4 через группу входов 16 заносится код, определяющий величину условной вероятности. Случайный режим реализуется переводом переключателя 15 в положе- 40 ние 15 аналогично известному генератору. При этом случайная последовательность снимается с выхода 1. Псевдослучайный режим реализуются переводом переключателя 15 в положение 15!. 45

При этом устройство осуществляет генерацию логических символов лог."1" (лог "0") с заданной условной вероятностью. Величина вероятности р (1/О) генерации (реализации) лог."1" при

>О условии, что предыдущим бып сгенерирован (реализован) лог."0" и вероятности р(1/1) генерации лог."1" при условии, что предыдущей была сгенерирована лог."1", определяется числом- сдвигов содержимого регистра 2, с блоком

55 сумматоров 3 по модулю два в цепи обратной связи. Поскольку вероятности реализации символов лог."1" и лог.-"0"

1640687 4 на выходе блока 3 сумматоров по модулю два одинаковы и равны 0,5, то возможна реализация дискретной шкалы вероятностей вида 0,5 = р = (1-0,5)1, где n — число сдвигов содержимого ре-, гистра 2 сдвига. Причем и генерируемых символов должны последовательно логически перемножаться. Роль последовательного логического умножителя выполняет триггер 9, устанавливаемый

npедварительно в состояние лог."1" на первом выходе, Если на его второй вход будет подано и логических единиц, то он сохранит состояние лог."1", если в последовательности иэ п символов будет хотя бы один логический ноль, триггер 9 установится в состояи ев, ние лог. 0 . Таким образом, вероятность события, заключающегося в том что по окончании и сдвигов регистра

2 сдвига на первом выходе триггера 9

I I I I будет лог. 1, будет определяться выражением р=.0,5. Вероятность, что при тех же условиях на втором выходе триггера 9 будет лог."1" соответственно равна р = 1-0,5. С первого выхода триггера 9 сгенерированный символ поступает на управляющий вход мультиплексора 5, причем если в триггере 9 хранится "лог.1", то к входам счетчи-. ка 6 через мультиплексор 5 подключается первая группа 10 из ш/2 разрядов регистра 4.

Наличие триггера 9, регистра 4, мультиплексора 5 и счетчика 6 позволя" ет управлять числом сдвигов регистра

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

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

Перед генерацией символов с заданной условной вероятностью в регистр

4 через группу входов 16 записывается m-разрядный код, первая группа разрядов которого определяет величину условной вероятности р (1/O), а вторая группа разрядов - величину условной вероятности р (1/1). По линии

"Пуск" подается импульс, передним фронтом которого в счетчик .6 записывается содержимое первой группы разрядов регистра 4, если в триггере 9 хранится лог."1", или второй группы

1640687

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

Составитель В.Орлов

Техред С,Мигунова Корректор H.Ревская

Редактор В.Бугренкова

Заказ 1017 Тираж 401 Подписное

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

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

Производственно-издательский комбинат "Патент", r.Óæãîðîä, ул. Гагарина, 101 разрядов, если в триггере 9 хранится лог."Î". Задним фронтом импульса

"Пуск" триггеры 8 н 9 устанавливаются в состояние лог."1", при этом разрешается прохождение через элемент

И 7 импульсов тактовой частоты от генератора 1, которые поступают параллельно на счетчик 6 и регистр. 2 сдвига, осуществляя сдвиги содержимого регистра После заданного числа импульсов, определяемого записанным в счетчик 6 кодом, счетчик 6 вырабаты- . вает сигнал переполнения Готов", который подается на вход и на вход триг5 гера 8, устанавливая его в состояние лог."О. При этом элемент И 7 запрещает прохождение импульсов тактовой частоты на входы счетчика 6 и регистра 2 сдвига. Сдвиги содержимого ре- 20 гистра сдвига 2 прекращаются. Сгенерированный символ может быть считан с прямого или инверсного выходов триггера 9 при наличии сигнала "Готов" на выходе 2, После появления 25 сигнала "Готов" может быть подан следующий сигнал "Пуск". После подачи следующего импульса по линии "Пуск" процесс повторяется, причем сгенерированный в предыдущем процессе логи- 30 ческий символ будет определять, какой именно код из регистра 4 будет записан в счетчик 6, и, следовательно, с какой вероятностью будет генерироваться следующий логический сим35 вол.

Генератор случайной последователь- 4п ности, содержащий генератор тактовых импульсов, переключатель, блок сумматоров по модулю два, регистр кода регистр сдвига, вход разрешения записи которого является входом зада- 4 ния начального состояния генератора, разрядные выходы регистра сдвига соединены с первой группой входов блока сумматоров по модулю два, вход которого соединен с первым входом переключателя и является входом задания режима генератора, а выход соединен с вторым входом переключателя и информационным входом регистра сдвига и является выходом случайной последовательности генератора, о т л ич а ю шийся тем, что, с целью расширения функциональных возможностей путем обеспечения возможности генерации символов с заданной условной вероятностью, в него дополнительно введены мультиплексор, счетчик, элемент И, первый и второй триггеры,причем входы установки в 1" первого и второго триггеров и вход разрешения записи начапьного состояния счетчика подключены к входу запуска генератора, выход переполнения счетчика соединен с входом установки в "0" первого триггера и является выходом признака окончания формирования очередного символа генератора, прямой выход первого триггера соединен с первым входом элемента И, второй вход которого соединен с выходом генератора тактовых импульсов, а выход — с синхронизирующим входом регистра сдвига и счетным входом счетчика, вход задания начального состояния которого соединен с выходом мультиплексора, первая и вторая группы информационных входов которого соединены соответственно с группами выходов младших разрядов и старших разрядов регистра кода, вход которого является входом задания условной вероятности генератора, выход блока суммирования по модулю два соединен с входом установки в "О" второго триггера, пря-. мой выход которого соединен с управляющим входам мультиплексора и является выходом символов с заданной условной вероятностью генератора, инверсный выход второго триггера является выходом инвертированных символов с заданной условной вероятностью генератора.