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

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

Союз Советскик

Социалистические

Республик

< 748394 (6I ) Дополнительное к авт. свид-ву (22) Заявлено 12 ° 12.77 (21) 2554492/18-24 с присоединением заявки ¹ (23) Приоритет .Опубликовано15.07.80. тиоллетень №26

Дата опубликования описания 15.07.80 (5I)M. Кл. (06 Г 1/02

5 07 С 15/00

Гооударстееннык комитет

СССР но делам изобретений и открытий (53) УДК681.325 (088.8) (72) Авторы изобретения

Л. Ф. Карачун, В, Н. Королев и А. М. Романкевич

Киевский ордена Ленина политехнический институт имени 50-летия Великой Октябрьской социалистической революции (7l) Заявитель (54) И -РАЗРЯДНЫЙ ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ

ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

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

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

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

Наиболее близким техническим решением к данному изобретению является генератор псевдослучайных двоичных последовательностей, содержащий датчик равномерно распределенных псевдослучайных чисел, регистр кода, разряды которого связанвт с соответствующими разрядами датчика равномерно распределенных псевдослучайных чисетч группы схем ИЛИ . a И, через которые разряды регистра кода .связаны друг с другом, схему формирования веса кода )3), Известное устройство обладает ограниченной возможностью изменения вероятностей появления единичных сигналов на своих выходах.

3 7483 „Возможно получение вероятностей только ряда значений: -е ° ° ° р

И. При этом многие значения вероятнос тей выходных сигналов представляются недостаточно точно. в 5

С целью повышения точности задания вероятности в генератор псевдослучайных1 двоичных последовательностей,, содержащий регистр кода, входы которого подключены к выходам датчика равномерно распределен- 2О ных псевдослучайных чисел, введены датчик потоков импульсов и в каждом разряде пять элементов И и элемент ИЛИ, выход которого соединен со входом регистра кода последующего разряда, первый ййод элемента ИЛИ соединен с выходом йервого элемента И, первый вход которого соединен с выходом регистра .кода своего разряда и с первыми входами второго . и третьего элементов И, вторые входы ко- 20 торых объединены с первыми входами четвертого и пятого элементов И и подключены к выходам четвертого и пятого элементов И предыдущего разряда cog TBeT» ственно," а "выходы второго и третьего 25 элементов И соединены со вторыми входами четвертого и пятого элементов И соответстве;- :;о и первого элемента,И и элемента ИЛИ соответственно, выходы датчика потоков импульсов соединены со вторыми входами второго и третьего элементов И первого разряда соответственно.

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

Генератор состоит из р -разрядного регистра кода l, состоящего из триггеров

2. Единичный выход триггера 2 в 1 -ом разряде соединен со входом элемента И

3, выход которого через элемент ИЛИ 4, элемент И 5, элемент ИЛИ 6 подключен .к информационному входу 7 триггера 2 в (t +1)-ом разряде и к одному входу элемента И 8 также в (j, +1)-ом разряде

Выходы датчика равномерно распределенных псевдослучайных чисел 9 соединены 45 в каждом разряде с инверсным входом элемента И 8, а также с входом элемента И 3 и с одним входом элемента И 10, второй вход которого соединен с шиной тактовых сигналов 11, а выход элемента

И .10 подсоединен к тактовому входу 12 триггера 2.

Выход элемента И 8 подключен ко второму входу элемента ИЛИ 4. Выход элемента И 13 в j. -ом разряде соединен с одним входом элемента И 14 и с одним щсодом элемента Й 13 в (i Ф1)-ом разраАе.- Второй вход элемента И 13 соеди94 нен с инверсным выходом элемента И 14

H c инверсным входом элемента ИЛИ 6.

Инверсный вход элемента И 14 подсоеди нен к выходу элемента ИЛИ 4, Выход элемента И 15 в 4 -ом разряде соединен с одним входом элемента И 16 и с одним входом элемента И 15 в (4 +1)-ом разряде. Второй вход элемента И 15 соединен с инверсным выходом элемента И 16 и со вторым входом элемента И 5. Второй вход элемента ff 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 ("нуль" в соответствующем разряде датчика 9), либо проходят через элемент И 8 дальше по регистру 1 ("единица" в соответствующем разряде датчика 9).

Таким образом, при сдвиге, разряды кода перепрыгивают" через триггеры 2, отмеченные единицами в соответствующих разрядах датчика 9. Отмеченные триггеры сохраняют прежнее состояние. Поскольку расположение единиц и нулей в разрядах датчика 9 в каждом такте изменяется случайным образом, что и перемешивание нулей и единиц в регистре 1 будет происходить в случайном порядке. В силу того, что вес кода в регистре 1 остается неизменным, равным K математическое ожидание появления "единицы" в двоичной

748394 з- та ИЛИ 4. Нулевой сигнал с выхода элемента И 16 закрывает элемент И 5 и запрещает прохождение единичного сигнала с выхода триггера 2 разряда, неотмеченного" единицей датчика 9, дальше по ре гистру, что равносильно передаче нулевого сигнала. последовательности на выходе любого ра ряда регистра 1 будет равно — где 0

К п число разрядов регистра 1.

Для получения значения вероятности выходного сигнала равного Р, при уславии, что — „(P(—,необходимо, чтобы отК +4 ношение промежутка времени, в течение которого в регистре l будет циркулировать

K+1 единиц, к промежутку времени, в течение которого в регистре будет К еди- .10 ниц, было равно величине о =

Р -K/rI

1/и -(Р- к/ т

Величина а определяется расйоложейием заданного значения вероятности Р между величинами —" и

В датчике 18 вырабатываются две по- H следовательности импульсов с периодом

Т, сдвинутых относительно друг друга на

T. При этом величина периода

Т должна быть краткой величине периода тактовых импульсов сдвига кода в ре- 20 гистре 1. Одна из последовательностей импульсов выдается по шине 17, а вторая, запаздывающая на время hT относительно первой, по шине 19, При появлении импульса на шине 17 число единиц в регист-25 ре 1 увеличивается на одну,. а при появлении импульса на шине 19, число единиц в регистре 1 уменьшается на одну.дополнительная единица записывается в один из разрядов регистра l, в который в дан- З0 ном такте должен записаться нуль. Исключение дополнительной единицы происходит эа счет блокировки передачи единицы из одного из разрядов регистра 1. Например, на выходе 17 блока 18 появился импульс. З5

Если при этом на инверсном входе элемента И 14 первого разряда разрешающий сигнал, то на инверсном выходе элемента

И 14 появляется нулевой сигнал, закрывающий элемент И 13 и запрещающий этим прохождение импульса выхода 17 дальше.

Таким образом, с помощью элементов И

14 и И 13 обнаруживается первый нуль на выходах элементов ИЛИ 4. Через элемент ИЛИ 6 импульс выхода 17 попадает

45 в соответствующий разряд регистра 1, устанавливая в единицу триггер 2, запись в который разрешена нулевым сигналом соответствующего разряда датчика 9.

Если появляется импульс на выходе 19 датчика 18 и на входе элемента И 16

l -ro разряда есть разрешающий сигнал, то на инверсном выходе элемента И 16 появляется нулевой cHFHQJI, который закры55 вает элемент И 15 и запрещает прохождение импульса с выхода 19 дальше. Таким образом элементы И 15 и И 16 обнаруживают первую единицу на выходах элемен-

Данный генератор позволяет значительно умейьшить . погрешность представления заданного значения вероятности символов формируемой псевдослучайной последовательности. Настраивая датчик 18 таким образом, чтобы величина АТ могла быть изменена с дискретностью — можно поT

1т лучить заданное значение вероятности с максимальной погрешностью, не превышаей

2п FR

Это позволяет, не увеличивая количества разрядов регистра генератора т, получить заданное значение вероятности с лю,бой наперед заданной точностью, при этом сложность блока коррекции вероятности растет пропорционально величйне(Ьф тт» Формула изобретения

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

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

И и элемента ИЛИ соответственно, выходы датчика потоков импульсов соединены со вторыми входами второго и третьего элементов И первого разряда соответственно.

748394

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

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

М 428373, кл. Я 06 F 1/02, 1974.

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

М 440777, кл. Н 03 К 3/82, 1974.

3. Авторское свидетельство СССР по заявке % 2447623/24, s кл. 906 F 1/02, 27.01.77 (прототип).

Составитель A. Карасов

Редактор Н. Каменская Техред M. Петко . Корректор В. Бутяга

Заказ 4240/36 тираж 751 Подписное

ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Филиал ППП Патент, r. Ужгород, ул. Проектная, 4