Генератор псевдослучайных кодов Советский патент 1979 года по МПК G07C15/00 G06F1/02 

Изобретение касается вычислительной техники и может быть использовано для решения широкого класса задач методом статистического моделирования, а также в качестве генератора испытательных пс следовательностей в автоматических системах контроля и диагностики, использующих различные вероятностные методы обнаружения отказов в цифровых схемах. Известен генератор псевдослучайных кодов, содержащий И-разрядшлй сдвигающий регистр, генератор тактовых импульсов, m сумматсфов по юдуйю два и ком мутатор, содержащий П групп переключателей по Vn рядов l. Его недостатки состоят в большой сложи ости, а также в невозможности изменять вероятности сигналов на выходах. Известен также генератор псевдослучайных кодов, содержащий h -разрядный регистр, охваченный цепью обратной связи, в состав которого входит группа триг геров со счетным входом и группа тригг ров с установочными входами 2. Недостатком известного устройств является невозможность изменять вероятности сигналов на его выходах. Наиболее близким по технической сущности к предложенному является генератор псевдослучайных кодов, содержащий рекуррентный регистр сдвига, циклический регистр сдвига, в каждом разряде которого содержится первый элемент И, первый вход которого является входом сдвиг циклического регистра сдвига, а выход первого элемента И соединен с нулевым входом триггера, выход которого является разрядньшг выходом генератора и подключен к первому входу второго элемента И, выход которого подключен к первому входу элемента ИЛИ, второй вход которого соединен с выходом элемента запрет, первый вход которбго объединен с единитаым входом триггера и подключен к выходу элемента ИЛИ предыдущего разряда jp. Недостатком этого устройства является невозможность точно представить ряд

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

р-(о ±- -2 ПЧ Л. И И П П г

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

Для этого генератор содержит регистр числа и в каждом разряде циклического регистра сдвига элемент ИЛИ-НЕ, выход которого соединен со вторыми входами первого и второго элементов И и элемен.тазапрет, а входы элемента ИЛИ-НЕ соединены с выходами соответствующих разрядов рекуррентного регистра сдвига и регистра числа

На чертеже Изображена функциональная схема генератора.

Генератор содержит циклический регистр сдвига 1, состоящий из триггеров 2, единичный выход каждого из которых в каждом i -ом разряде соединен с входом элемента И 3, выход которого через элемент ИЛИ- 4, подключен к информационному входу 5 триггера 2 в ( i+ 1)-юм разряде и к одному входу элемента запрет 6 в ( i +1)-)М разряде. В цепь обратной связи рекуррентного регистра сдвига 7 включен сумматор по модулю два 8. Нулевые выходы триггеров 9 регистра 7 соединены в каждом разряде с одним входом элемента ИЛИ-НЕ 10, другой вход которого соединен с единичным выходом триггера 11 регистра числа 12, а выход элемента ИЛИ-ЛЕ 10 подключен к инверсному входу элемента запрет 6, к одному входу элемента И 3 и к одному входу элемента И 13, второй вход которого подсоединен к шине тактовых сигналов 14, а выход подключен к тактовому входу 15 триггера 2. Выход элемента ИЛИ 4 последнего разряда по шине обратной связи 16 подключен к входу 5 триггера 2 в первом разряде и к одному входу элемента запрет 6 в этом же разряде.

Работу устройства рассмотрим на примере для числа разрядов п 4.

Регистр 7 с сумматором по модулю два 8 генерирует псевдослучайную последовательность равномерно распределенных нулей и единиц, с помощью которых производится управление сдвигом кода в регистре 1. На регистре 1 формируются

h -разрядные коды постоянного веса k, где П - число разрядов регистра 1, а К - количество единиц, записанных в регистр 1. Процесс формирования кодовых комбинаций в регистре 1 при условии, что регистр 12 находится в нулевом состоянии, протекает следующим образом. Например, в данном такте в регистре 7 находится код ОНО, а в прдыдущем такте на регистре 1 был сформирован код 11ОО. В этом случае нулевые сигналы с нулевых выходов триггеров 9 второго и третьего разрядов через соответствующие элементы 10 действуют на входы элемента И 13 в соответствующих разрядах и закрывают их, поэтому тактовые :;игналы 14 не проходят на входы 15 триггеров 2 во втором и третьем разрядах и эти триггеры сохраняют свое состояние независимо от того, какие сигналы поступают на входы 5, Единичный сигнал с единичного выхода триггера 2 первого разряда проходит через элементы И 3, ИЛИ 4 в первом разряде и через открытую нулевым сигналом с нулевого выхода триггера 9 второго разряда элемента 6 поступает на вход элемента ИЛИ 4 второго разряда. С выхода элемента ИЛИ 4 рассматриваемый сигнал проходит через элемент И 6, открытый нулевым сигналом с нулевого выхода триггера 9 третьего разряда и через элемент ИЛИ 4 на вход 5 триггера 2 четвертого разряда. Через элемент 6 четвертого разряда рассматриваемый сигнал не проходит, так как он закрыт единичным сигналом с выхода триггера 9 четвертого разряда. На вход 5 триггера 2 первого разряда действует нулевой сигнал, поступающий по шине 16с выхода триггера 2 четвертог разряда. В момент действия тактового сигнала 14 произойдет запись единицы в четвертый триггер 2 и нуля в первый триггер 2. В результате на регистре сформируется код О1О1. Таким образом, при сдвиге разряды кода перепрыгивают через триггеры 2, отмеченные единицами в соответствующих разрядах регистра 7. Отмеченные триггеры 2 сохраняют прежнее состояние. При этом количество единиц в коде на регистре 1 остается неизменным. Поскольку последовательность нулей и единиц на выходах регистра 7, управляющая сдвигом кода в регисре 1, представляет собой псевдослучайную последовательность (с равными вероятностями появления О и ), то перемешивание единиц в регистре 1 прО исходит в случайном порядке и на выходах регистра 1 формируются псевдослучайные кодовые комбинации постоянного веса, причем математическое ожидание появления 1 равно величине - , где К - вес кода; п- число разрядов регистра 1. Чтобы получить на выходе генератора последовательность - Л- (где ) с вероятностью появления , необходимо уменьшить на g число разря дов регистра 1, в которых осуществляет ся циркуляция символов кода. С этой целью 6 разрядов задающего регистра 12 устанавливаются в . При этом на выходах соответствующих С. элементов 1.0 постоянно присутствует единичный сигнал, с помоццью которого (как было описано выше) 6 триггеров 2 выключены из цепи циркуляции регистра 1. Необ ходимо, чтобы К единиц, которые циркулируют в регистре 1, предварительно были записаны в любые К из И разрядов регистра 1, не отмеченные единицами регистра маски 12. В дальнейшем, под действием управляющих случайных сигналов регистра 9 К единиц циркулируют в регистре1, состоящем уже из hi разрядов. Соответственно, вероятност появления единичного сигнала на выходе генератора будет равна: р - К Г f Генератор позволяет значительно расширить диапазон изменения вероятностей представления выходных единичных сигна лов, по сравненшо с известным генерато ром. Так, например, для И 1О, известный генератор имеет возможность вьщачи выходных единичных сигналов с вероятностями Р. el ,1/10, 2/10, 3/10, ... , 9/10, 1. В то же время; предлагаемый генератор позволяет изменять вероятности выходных единичных сигналов в соответств со следующим множеством значений: Р . 0,1/10, 1/9, . . ., 1/2V 2/10, 2/9., 2/8, . . . , 2/3, 3/1-0, 3/8, 3/7 3/5, 3/4, 4/9, 4/8, 4/7, 4/5, 5/9, 5/8, 5/7, 5/6, 6/7, 7/10, 7/9, 7/8, 9/1О, 1. Всего 33 значения против 11 для известного генератора. Если же моделируемая случайная величина не входит в приведенный ряд значений, то, тем не менее, предлагаемый генератор позволяет реализовать ее с максимальной погрешностью 1 vn-m Формула изобретения Генератор псевдослучайных кодов, содержащий рекуррентный ре гистр. сдвига , циклический регистр сдвига, каждый разряд которого содержит первый элемент И, первый вход которого является входом сдвиг циклического регистра сдвига, а выход первого элемента И соединен с нулевым входом триггера, выход которого является разрядным выходом генератора и подключен к первому входу второго элемента И, выход которого подключен к первому входу элемента ИЛИ, второй вход которого соединен с выходом элемента запрет, первый вход которого-, объединен с единичным входом триггера и подключен к выходу элемента ИЛИ предыдущего разряда, отличающийся тем, что, с целью расширения функциональных возможностей генератора за счет изменения вероятностей сигналов на выходах генератора,он содержит регистр числа и в каждом разряде циклического регистра сдвига элемент ИЛИ-НЕ, выход которого соединен со вторыми входами первого и второго элементов И и элемента запрет, а входы элемента ИЛИ-НЕ соединены с выходами соответствующих разрядов рекуррентного регистра, сдвига и регистра числа. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 375769, кл. (3 06 F 1/02, 1971. 2.Авторское свидетельство СССР № 468231, кл.-Q 06 F 1/О2, 1976. 3.Авторское свидетельство СССР по заявке № 2340415, кл. Q 06 F 1/О2, 29.03.76 (прототип).

jTr

1Л

/5

0

d

t

Rr

Ш Ш

«i

IT

/5

и

/5

Г