Генератор случайной последовательности Советский патент 1991 года по МПК G06F7/58 

Выход 2 .

(П

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

оо

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

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

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

Генератор содержит генератор 1 тактовых импульсов, регистр 2 сдвига блок 3 сумматоров по модулю два, регистр 4 кода, мультиплексор 5, счетчик 6, элемент И 7, триггеры 8 и 9,

первую группу входов 10 мультиплек- сора 5, вторую группу входов 11 мультиплексора 5, группу входов счетчика 12, первую группу входов 13, вторую группу входов 14 блока сумматоров по модулю два, переключатель 15, входы 16 регистра кода, вход 17 задания начального состояния, вход 18 задания режима,,

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

Перед началом работы генератора в регистр 2 сдвига заносится через вход 17 и сумматор„3 по модулю два ненулевой код, управляющий сигналом Запись по входу 17, а в регистр 4 через группу входов 16 заносится код определяющий величину условной вероятности Случайный режим реализуется переводом переключателя 15 в положе- ние 15 Ј аналогично известному генератору При этом случайная последовательность снимается с выхода 10 Исев

зависимости от сгенерированного символа, что обеспечивает генерацию логических символов на первом и втором

дослучайный режим реализуются переводом переключателя 15 в положение 15 45 выходах триггера 9 с заданным значе- При этом устройство осуществляет ге- нием условной вероятности нерацию логических символов Перед генерацией символов с задан- (лог О) с заданной условной вероят- ной условной вероятностью в регистр ностьюо Величина вероятности р (1/0) генерации (реализации) при условии, что предыдущим был сгенерирован (реализован) и вероятнос4 через группу входов 16 записывается га-разрядный код, первая группа разрядов которого определяет величину условной вероятности р (1/0), а вторая группа разрядов - величину условной вероятности р (1/1) По линии Пуск подается импульс, передним фронтом которого в счетчик 6 записывается содержимое первой группы разрядов регистра 4, если в триггере 9 хранится , или второй группы

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

0

5

5

0

,Q

5

на выходе блока 3 сумматоров по модулю два одинаковы и равны 0,5, то возможна реализация дискретной шкалы вероятностей вида 0,5 р (1-0,5) где п - число сдвигов содержимого ре-, гистра 2 сдвига Причем п генерируемых символов должны последовательно логически перемножаться Роль последовательного логического умножителя выполняет триггер 9, устанавливаемый предварительно в состояние на первом выходе, Ксли на его второй вход будет подано п логических единиц, то он сохранит состояние , если в последовательности из п символов будет хотя бы один логический ноль, триггер 9 установится в состояние лог Таким образом, вероятность события, заключающегося в том, что по окончании п сдвигов регистра 2 сдвига на первом выходе триггера 9 будет лого М, будет определяться выражением ,50 Вероятность, что при тех же условиях на втором выходе триггера 9 будет лого М соответственно равна р 1-0,5. С первого выхода триггера 9 сгенерированный символ поступает на управляющий вход мультиплексора 5, причем если в триггере 9 хранится лого, то к входам счетчит- ка 6 через мультиплексор 5 подключается первая группа 10 из т/2 разрядов регистра 4

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

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

3по модулю два на триггере 9, управлять переключением мультиплексора 5 в

зависимости от сгенерированного символа, что обеспечивает генерацию логических символов на первом и втором

45 выходах триггера 9 с заданным значе- нием условной вероятности Перед генерацией символов с задан- ной условной вероятностью в регистр 5 выходах триггера 9 с заданным значе- нием условной вероятности Перед генерацией символов с задан- ной условной вероятностью в регистр

5

4 через группу входов 16 записывается га-разрядный код, первая группа разрядов которого определяет величину условной вероятности р (1/0), а вторая группа разрядов - величину условной вероятности р (1/1) По линии Пуск подается импульс, передним фронтом которого в счетчик 6 записывается содержимое первой группы разрядов регистра 4, если в триггере 9 хранится , или второй группы

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

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

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

25

30

35

40

45

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

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

5

0

5

0

5

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