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

ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Соеэ Советски кСоциалистическиеРеспублик и 748394но делам изобретений и открытий(72) Авторы изобретения Л. ф. Карачун, В, Н. Королев и А. М, Романкевич Киевский ордена Ленина политехнический институтимени 50-летия Великой Октябрьской социалистическойреволюции(54) И -РАЗРЯДНЫЙ ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙИзобретение относится к области вычислительной техники и может быть использовано в качестве источника случайных последовательностейй символов, необходимыхпри статистическом моделировании физи 5ческих процессов и синтезе вероятностныхавтоматов, а также в качестве датчиковслучайных испытательных сигналов приконтроле логических схем и в качестведатчиков случайных кодов заданного весадля машинного синтеза. койтролируюа 1 ихтестов.Известно устройство для генерациипсевдослучайных чисел, содержащее регистры сдвига с сумматорами по модулю двав цепях обратной связи. С помощью такого устройства невозможно получить случайныедвоичные последовательности с задан-,ной вероятностью 111,Известно также устройство, вырабатывающее случайные сигналы с заданной ве-роятностью. Устройство содержит датчикслучайных импульсов, подключенных к входу регистра сдвига, генератор тактовых импульсов, счетчик, выходы которого связаны с входами дешифратора, подсоединенного выходом к входу наборной панели,подключенной к схемам совпадения коммутатора. Недостатком такого устройстваявляются большие аппаратурные затратыи невозможность оперативного изменениявероятностей появления выходных единичных сигналов )21.Наиболее близким техническим решени- ем к данному изобретению является генератор псевдослучайных двоичных последовательностей, содержащий датчик равномерно распределенных псевдослучайных чисел, регистр кода, разряды которого связанвт с соответствующими разрядами датчика равномерно распределенных псевдослучайных чисещ группы схем ИЛИ и И, через которые разряды регистра кода .связаны друг с другом, схему формирования веса кода 131. Известное устройство обладает ограниченной возможностью изменения вероятностей появления единичных сигналов на своих выходах.3 7483Возможно получение вероятностей толькоиз Ряда значений: - --ооо о фИ. При этом многие значения вероятностей выходных сигналов представляются недостаточно точно.в 5ф С целью повышения точности заданиявероятности в генератор псевдослучайныхдвоичных последовательностей, содержащийрегистр кода, входы которого подключенык выходам датчика равномерно распределен ных псевдослучайных чисел, введены датчик потоков импульсов и в каждом разряде пять элементов И и элемент ИЛИ, выход которого соединен со входом регистра кода последующего разряда, первый 15ййод элемента ИЛИ соединен с выходомйервого элемента И, первый вход которого соединен с выходом регистра .кода своего разряда и с первыми входами второго. и третьего элементов И, вторые входы которых объединены с первыми входамичетвертого и пятого элементов И и подключены к выходам четвертого й пятогоэлементов И предыдущего разряда соответственно," а "выходывторого и третьего 25элементов И соединены со вторыми входами четвертого и пятого элементов И соответствено и первого элемента,И и элемента ИЛИ соответственно, выходы датчика потоков импульсов соединены со вто- З 0рыми входами второго и третьего элементов И первого разряда соответственно.На чертеже изображена функциональнаясхема генератораГенератор состоит из р -разрядногорегистра кода 1, состоящего из триггеров2. Единичный выход триггера 2 в 1 -омразряде соединен со входом элемента И3, выход которого через элемент ИЛИ 4,элемент И 5, элемент ИЛИ 6 подключен 40.к информационному входу 7 триггера 2в (В +1)-ом разряде и к одномувходуэлемента И 8 также в ( +1)-ом разрядеВыходы датчика равномерно распределенных псевдослучайных чисел 9 соединены 45в каждом разряде с инверсным входомэлемента И 8, а также с входом элемента И 3 и с одним входом элемента И 10,второй вход которого соединен с шинойтактовых сигналов 11, а выход элемента 50И .10 подсоединен к тактовому входу 12триггера 2,Выход элемента И 8 подключен ковторому входу элемента ИЛИ 4. Выходэлемента И 13 в-ом разряде соединенс одним входом элемента И 14 и с однимщсодом элемента й 13 в (ъ Ф 1)-ом разряде.- Второй вход элемента Й 13 соеди 94ненс инверсным выходом элемента И 14 и с инверсным входом элемента ИЛИ 6. Инверсный вход элемента И 14 подсоединен к выходу элемента ИЛИ 4, Выход элемента И 15 в 1 -ом разрйде соединен с одним входом элемента И 16 и с одним входом элемента И 15 в (1 +1)-ом разряде. Второй вход элемента И 15 соединен с инверсным выходом элемента И 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 ( "нуль" в соответствующем разряде датчика 9), либо проходят через элемент И 8 дальше по регистру 1(" единица" в соответствующем разрядедатчика 9).Таким образом, при сдвиге, разрядыкода перепрыгивают" через триггеры 2,отмеченные единицами в соответствующихразрядах датчика 9, Отмеченные триггеры сохраняют прежнее состояние, Поскольку расположение единиц и нулей в разрядах датчика 9 в каждом такте изменяется случайным образом, что и "перемешиваниеф нулей и единиц в регистре 1 будетпроисходить в случайном порядке. В силутого, что вес кода в регистре 1 остаетсянеизменным, равным к, математическоеожидание появления "единицы" в двоичной748394з- та ИЛИ 4, Нулевой сигнал с выхода элемента И 16 закрывает элемент И 5 и запрещает прохождение единичного сигнала с выхода триггера 2 разряда,неотмеченного" единицей датчика 9, дальше по регистру, что равносильно передаче нулевого сигнала. последовательности на выходе любого ра ряда регистра 1 будет равно - где 0И число разрядов регистра 1.Для получения значения вероятности выходного сигнала равного Р, при уславии, что - - ,необходимо, чтобы отК +ношение промежутка времени, в течение которого в регистре 1 будет циркулировать К +1 единиц, к промежутку времени, в течение которого в регистре будет К еди- .10 ниц, было равно величине о(:Р -к/и/и -(р-Юо - Величина ь определяется расйоложейием заданного значения вероятности Р между величинами ф иВ датчике 18 вырабатываются две по следовательности импульсов с периодом Т, сдвинутых относительно друг друга наПри этом величина периода Т должна быть краткой величине периода тактовых импульсов сдвига кода в ре гистре 1, Одна из последовательностей импульсов выдается по шине 17, а вторая, запаздывающая на время ЬТ относительно первой, по шине 19, При появлении импульса на шине 17 число единиц в регистре 1 увеличивается на одну, а при появлении импульса на шине 19, число единиц в регистре 1 уменьшается на одну.Дополнительная единица записывается в один из разрядов регистра 1, в который в дан ном такте должен записатьсянуль. Искщочение дополнительной единицы происходит эа счет блокировки передачи единицы из одного из разрядов регистра 1. Например, на выходе 17 блока 18 появился импульс. З 5 Если при этом нв инверсном входе элемента И 14 первого разряда разрешающий сигнал, то на инверсном выходе элемента И 14 появляется нулевой сигнал, закрывающий элемент И 13 и запрещающий этим прохождение импульса выхода 17 дальше. Таким образом, с помощью элементов И 14 и И 13 обнаруживается первый нуль на выходах элементов ИЛИ 4. Через элемент ИЛИ 6 импульс выхода 17 попадаета 5 в соответствующий разряд регистра 1, устанавливая в единицу триггер 2, запись в который разрещенв нулевым сигналомсоответствующего разряда датчика 9.50Если появляется импульс нв выходе 19 датчика 18 и на входе элемента И 16 Фь-го разряда есть разрешающий сигнал, то на инверсном выходе элемента И 16 появляется нулевой сигнал, который закры 55 ввет элемент И 15 и запрещает прохождение импульса с выхода 19 лвльще, Таким образом элементы И 15 и И 16 обнаруживают первую единицу нв выходах элеменДанный генератор позволяет значительно умейьшить погрешность представления заданного значения вероятности символов Формируемой псевдослучайной последовательности. Настраивая датчик 18 таким образом, чтобы величина АТ могла быть изменена с дискретностью - можно поТ1 тлучить заданное значение вероятности с максимальной погрешностью, не превышащей2 п п 3 Это позволяет, не увеличивая количества разрядов регистра генератора О, получить заданное значение вероятности с лю,бой наперед заданной точностью, при этом сложность блока коррекции вероятности растет пропорционально величйне 1 оп 1Формула и э о б р е т е н и я Я -разрядный генератор псевдослучайных двоичных последовательностей, содер-. жащий регистр кода, входы которого подключены к выходам датчика равномерно распределенных псевдослучайных чисел, о т л и ч а ю ш и й с я тем, что, с целью повышения точности задания вероятности, генератор содержит датчик потоков импульсов и в каждом разряде пять элементов И и элемент ИЛИ, выход которого соединен со входом регистра кода последующего разряда, первый вход элемента ИЛИ соединен с выходом первого элемента И, первый вход которого соединен с выходом регистра кода своего разряда и с первыми входами второго и третьего элементов И, вторые входы которых объединены с первыми входами четвертого и пятого элементов И и подключены к выходам четвертого и пятого элементов И предыдущего разряда соответственно, а выходы второго и третьего элементов И соединены со вторыми входами четвертого и пятого элементов И соответственно и первого элемента И и элемента ИЛИ соответственно, выходы датчика потоков импульсов соединены со вторыми входами второго и третьего элементов И первого разряда соответственно.748394 7Источники информащии,принятые во внимание при экспертизе 1, Авторское свидетельство СССРМ 428373, кл. Я 06 Р 1/02, 1974,8 2, Авторское свидетельство СССР М 440777, кл. Н 03 К 3/82, 1974. 3. Авторское свидетельство СССР по заявке % 2447623/24,5 кл. 506 Г 1/02, 27.01.77 (прототип),Подписноемитета СССРрытийая наб., д. 4/5 О/36 Тираж 751 ЦНИИПИ Государственного ко по делам изобретений и отк 13035, Москва, Ж, Раушск