-Разрядный генератор псевдослучайных двоичных последовательностей Советский патент 1980 года по МПК G06F1/02 G07C15/00 

1

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

датчикбв рпучайньтх кодов заданного веса для MJainHHHdJTo синтеза койтролирукйих

тестов..

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

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

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

Наиболее близким техническимрешением к данному изобретению является генератор псевдослучайных двоичных последовательностей, содержащий датчик -равномерно распределенных псевдослучайных чисел, регистр кода, разряды которого CBJtaaHbi с соответствукмаими разрядами датчика равномерно распределенных псевдослучайных чисел; группы схем ИЛИ и И, через которые разряды регистра кода связаны друг с другом, схему формирования веса кода з. Известное устройство обладает ограниченной возможностью изменения вероятностей появления единичных сигналов на своих Выходах, Возможно получение вероятностей только из ряда значений: А;,..; jTll j . И. При этом многие значения вероятнос|Твй выходных сигналов представляются недостаточно точно. С целью повышения точности задания ( в юятности в генератор псевдослучайных двоичных последовательностей,, содержащий регистр кода, входы которого Подключены к выходам датчика равномерно распределен ных псевдослучайньтх чисел, введены датЧйк потоков импульсов и в каждом разряде пять элементов И и элемент ИЛИ, выход которого соединен со входом регистра кода Последующего разряда, первый вход элемента ИЛИ соединен с выходом первого элемента И, первый вход которого соединен с вызсоДом регистра кода своего разряда и с первыми входами второго . и третьего элементов И, вторые входы которых объединены с первыми вхШайй четвертого и пятого элементов И и подкпючены к выходам четвертого и пятого элементов И предыдущего разряда ствёнйЬ,а выхбды второго и третьего элементов И соединены со вторыми входами четвертого и пятого элементов И соответственво и первого элемента,И и эле-. мента ИЛИ соответственно, выходы датчиKJ9 потоков импульсовсоединены со вторыми входами второго и третьего элементов И первого разряда соответственно. На чертеже изображена функциональная схема генератора.., Генератор состоит из п -разрядного регастра кода 1, состоящего из триггеров 2.Единичный выход триггера 2 в i -ом разряде соединен со входом элемента И 3,выход которого Через элемент ИЛИ 4, элемент И 5, элемент ИЛИ 6 подключен к информационному входу 7 триггера 2 Б (I +1)-ом разряде и к одному входу элемента И 8 также в (i+1)-ом разряде Выходы датчика равномерно распределенных псевдослучайных чисел 9 соединены в каждом раз|ряде с инверсньгм входом элемента И 8, а также с входом элемента И 3 НС одним входом элемента И 1О второй вход которого Соединен с щиной тактовых сигналов 11, а выход элемента И 10 подсоединен к тактовому входу 12 триггера 2. Выход элемента И 8 подключен ко втчэрому входу элемента ИЛИ 4. Выход элемента И 13 в t -ом разряде соединен с одйим входом эпеиента И 14 и с одним входом элемеята И 13 в (г +1)-ом разряде. Второй вхоа элемента И 13 соединен с инверсным выходом элемента И 14 и с инверснйм входом элемента ИЛИ 6. Инверсный вход элемента И 14 подсоединен к выходу элемента ИЛИ 4, Выход элемента И 15 в i -ом разряде соединен с одним входом элемента И 16 и с одним входом элемента И 15 в (t +1)-ом разряде. Второй вход элемента И 15 соединен с И1терсным выходом элемента И 16 и со вторым входом элемента И 5. Второй вход элемента И 16 соединен с выходом элемента ИЛИ 4..В первом разряде генератора один вход элемента И 14 соединен с выходом 17 датчика потоков импульсов 18, а один вход элемента И 16 подключен к выходу 19 датчика потоков импульсов 18. Датчик 9 генерирует псевдослучайную последовательность равномерно распреде- ленньйс нулей и единиц, с помощью которой производится управление сдвигом кода в регистре 1. Предварительно в регистр 1 заносится код заданного веса, В том случае, если на вьтходах блоки 15 нулевые сигналы, процесс формирования кодовых комбинаций в. регистре 1 происхоДит следующимобразом. В тех разрядах регистра кода 1, которым соответствуют единичные состояния разрядов датчика 9, будут запрещающим сигналом с соответствующих выходов датчика 9 элементы И 10. . Поэтому тактовые сигналы не пройдут на входы 12 триггеров 2 в соответствующих разрядах регистра 1 и эти триггеры 2 сохраняют свое состояние. В тех разрядах регистра 1, которым соответствуют нулевые состояния разрядов датчика 9, сигналы с вьрсодов триггеров 2 про ходят через элементы И 3, ИЛИ 4, И 5, ИЛИ 6 и либо поступают в следующий разряд регистра 1 (нуль в cooTBeTcTBl кзщем разряде датчика 9), либо проходят через элемент И 8 дальще по регистру 1 (единица в соответствуквдем разряде датчика 9). Таким образом, при сдвиге, разряды кода перепрыгивают через триггеры 2, отмеченные единицами в соответствующих разрядах йатчика 9. Отмечеиньте триггеры сохранякзТ прежнее состояние. Поскольку расположение единиц и :нулей в разрядах датчика 9 в каждом такте изменяется случайным образом, что и перемешивание нулей и единиц в регистре 1 будет происходить в случайном порядке. В силу того, что вес кода в регистре 1 остается неизменныМ| равным к, математическое ожидание появления единицы в двоичяой последовательности на вь1ходе любого разряда регистра 1 будет равно где П число разрядов регистра 1. Для получения значения вероятности выходного сигнала равного Р , при условии, что ,необходимо, чтобы отношение промежутка времени, в течение которого в регистре 1 будет циркулироват К +1 единиц, к промежутку времени, в течение которого в регистре буцет if, единиц, было равно величине сг -fp xi/hf Величина л определяется расположением заданного значения вероятности Р между величинами - и , В датчике 18 вырабатываются две последовательности импульсов с периодом Т, сдви.нутых относительно друг друга .на AT q;j--T. При этом, величина периода Т должна быть краткой величине периода тактовых импульсов сдвига; кода в регистре 1. Одна из последовательностей импульсов выдается по шине 17, а вторая запаздывающая на время дТ относительно первой, по шине 19. При появлении им пульса на шине 17 число единиц в регистре 1 увеличивается на о дну,-а при появлении импульса на шине 19, число единиц в регистре 1 уменьшается на одну. Дополнительная единица записывается в один из разрядов регистра 1, в который в данном такте должен записаться нуль. Исключение дополнительной единицы происходит за счет блокировки передачи единицы из одного из разрядов регистра 1. Например, на выходе 17 блока 18 появился импульс. Если при этом на инверсном входе элемен та И 14 первого разряда разрешающий сигнал, то; на инверсном выходе элемента И 14 появляется нулевой сигнал, закрывающий элемент И 13 и запрещающий этим прохождение импульса выхода 17 дальше. Таким образом, с помсяцью элементов И 14 и И 13 обнаруживается первый нуль на выходах элементов ИЛИ 4. Через эле мент ИЛИ б импульс выхода 17 попадает в соответствующий разряд регистра 1, устанавливая в единицу триггер 2, запись в который разрешена нулевым сигналом соответствующего разряда датчика 9. Если появляется импульс на выходе 19 датчика 18 и на входе элемента Ц 16 t.-ro разряда есть разрешающий сигнал, то на инверсном вькоде элемента И 16 появляется нулевой сигнал, который закрывает элемент И 15 и запрещает прохождение импульса с выхода 19 дальше. Таким образом элементы И 15 и И 16 обнару кивают первую единицу на выходах элемён та ИЛИ 4. Нулевой сигнал с выхода элемента И 16 закрывает элемент И 5 и запрещает прохождение единичного сигнала с выхода триггера 2 разряда; неотмеченного единицей датчика 9, Дальше по per гистру, что равносильно передаче нулевого сигнала.Данный генератор позволяет значительно умейьшить - погрешность представления заданного значения вероятности символов формируемой псевдослучайной последовательности. Настраивая датчик 18 таким образом, чтобы величина дТ могла быть изменена с дискретностью - можно получить заданное значение вероятности с максимальной погрешностью, не превышающей . 2ПГТ) Это позволяет, не увеличивая количества разрядов регистра генератора П, полуЧить заданное значение вероятности с лю;бой наперед заданной Точностью, при этом сложность блока коррекции вероятности растет пропорционально величине бо И , ф о Р м у л а изобретения hi -разрядный генератор псевдослучайных двоичных последовательностей, содерзКаШий регистр кода, входы которого подключены к выходам датчика равномерно распределенных псевдослу1айных чисел. отличающийся тем, что, с целью повышения точности задания вероятности, генератор содержит датчик потоков импульсов и в каясдом разряде пять элементов И и элемент ИЛИ, выход которого соединен со входом регистра кода последующего разряда, первый вход элемента ИЛИ соединен с выходом первого элемента И, первый вход которого соединен с выходймг регистра кода своего разряда и с первыми входами второго и третьего элементов И, вторые входы которых объединены с первыми входами четвертого и пятого элементов И и подключены к выходам четвертого и пятого, элементов И предыдущего разряда соответственно, а выхоДы второго и третьего элементов И соединены со вторыми входами четвертого и пятого элементов И соответственно и первого элемента И и элемента ИЛИ соответственно, выходы датчика потоков импульсов Соединены со вторыми входами второго и третьего элементов И первого разряда соответственно.

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

1, Авторское свидетельство СССР J 428373, кл, q 06 F 1/02, 1974.

2.Авторское свидетельство СССР № 440777, кд, Н ОЗ К 3/82, 1974.

3.Авторское свидетельство СССР по заявке № 2447623/24,

кл.Q06F 1/02, 27.01.77 (прототип).