Генератор псевдослучайных кодов

Союз Соаетсммн 9533 оциалнстнческин Респубнии и 6 ЗОБРЕТЕН ДЕТЕ ЛЬС К АВТОРСКОМУ(22)Заявлено 1 24 (53 ) 77 (21) 2508754 07 С 15/О 06 Г 1/02 нсоеринениеи заявки рстввнньй нвСССРлам нзвбрвтвн втнритнй 3) Приоритет 5.11,79. Бюллетень М 3) УДК 681.325( 088.8) публикова та опубликования описания 28.1 1 М, С. Берштейн, О, В, Викторов, Л, ф. Карачун и А. М. Романкевич(72) Авторы изобретения Киевский ордена Ленина политехнический институтим. 50-летия Великой Октябрьской социалистической.революции 7) Заявитель ЕРАТОР ПСЕВДОСЛУЧАЙНЫХ КОДО(5 Изобретение касается вычислительной техники и может быть использовано для решения широкого класса задач методом статистического моделирования, а также в качестве генератора испьгтательных последовательностей в автоматических системах контроля и диагностики, использующих различные вероятностные методы обнаружения отказов в цифровых схемах.Известен генератор псевдослучайных кодов, содержащий и-разрядный сдвигающий регистр, генератор тактовых импульсов,ттт сумматоров по модуйто два и ком мутатор, содержащий тт групп переключателей по ттт рядов 1.Его недостатки состоят в большой сложности, а также в невозможности изменять вероятности сигналов на выходах.Известен также генератор псевдослучайных кодов, содержащий тт -разрядный регистр, охваченный цепью обратной свя зи, в состав которого входит группа триггеров со счетным входом и группа триггеров с установочными входами 2,Недостатком известного устройств является невозможность изменять вероятности сигналов на его выходах.Наиболее близким по технической сущ-. ности к предложенному является генератОр псевдослучайных кодов, содержащий рекур рентный регистр сдвига, циклический ре гистр сдвига, в каждом разряде которо го содержится первый элемент И, первый вход которого является входом сдвиг" циклического регистра сдвига, а выход первого элемента И соединен с нулевым входом триггера, выход которого является разрядным выходом генератора и подключен к первому входу второго элемента И, выход которого подключен кпервому входу элемента ИЛИ, второй вход которого соединен с выходом элемента "запрет", первый вход которбго объединен с единичным входом триггера и под ключен к выходу элемента ИЛИ предыду щего разряда 3.Недостатком этого устройства является невозможность точно представить рядЦель изобретения - расширение функциональных возможностей генератора псевдослучайных последовательностей импульсов за счет изменения вероятностей сигналов на выходах генератОра.Для этого генератор содержит регистрчисла и в каждом разряде циклическогорегистра сдвига элемент ИЛИ-НЕ, выходкоторого соединен со вторыми входами 5первого и второго элементов И и элемен.та "запрет", а входы элемента ИЛИ НЕсоединены с выходами соответствующихразрядов рекуррентного регистра сдвигаи регистра числа,На чертеже изображена функциональная схема генератора,Генератор содержит циклический регистр сдвига 1, состоящий иэ триггеров2, единичный выход каждого из которыхв каждом 1-ом разряде соединен с входом элемента И 3, выход которого черезэлемент ИЛИ 4, подключен к информационному входу 5 триггера 2 в ( 1+ 1)-омразряде и к одному входу элемента 130"запрет" 6 в (1+1)-ом разряде. В цепьобратной связи рекуррентного регистрасдвига 7 включен сумматор по модулюдва 8. Нулевые выходы триггеров 9 регистра 7 соединены в каждом разряде содним входом элемента ИЛИ-НЕ 10, другой вход которого соединен с единичнымвыходом триггера 11 регистра числа 12,а выход элемента ИЛИ-НЕ 10 подключенк инверсному входу элемента "запрет 6,к одному входу элемента И 3 и к одномувходу элемента И 13, второй вход которого подсоединен к шине тактовых сигналов 14, а выход подключен к тактовому входу 15 триггера 2. Выход элемен 45та ИЛИ 4 последнего разряда по шинеобратной связи 16 подключен к входу 5триггера 2 в первом разряде и к одному входу элемента "запрет 6 в этомже разряде.Работу устройства рассмотрим напримере для числа разрядов И = 4.Регистр 7 с сумматором по модулюдва 8 генерирует псевдослучайную после 55довательность равномерно распределенныхнулей и единиц, с помощью которых производится управление сдвигом кода в регистре 1. На регистре 1 формируются 20 3 6995 значений вероятностей появления единичного выходного сигналя, не принадлежащих множеству:З -1ро,и И О 33 4О -разрядные коды постоянного веса М, где И - число разрядов регистра 1, а К - количество единиц, записянных.в регистр 1. Процесс формирования кодовых комбинаций в регистре 1 при условии, что регистр 12 находится в нулевом состоянии, протекает следующим образом. Например, в данном такте в регистре 7 находится код 0110, а в предыдущем такте на регистре 1 был сформирован код 1100. В этом случае нулевые сигналы с нулевых выходов триггеров 9 второго и третьего разрядов через соответствующие элементы 10 действуют на входы элемента И 1 3 в соответствующих разрядах и закрывают их, поэтому тактовые сигналы 14 не проходят на входы 15 триггеров 2 во втором и третьем разрядах и эти триггеры сохраняют свое состояние независимо от того, какие сигналы поступают на входы 5, Единичный сигнал с единичного выхода триггера 2 первого разряда проходит через элементы И 3, ИЛИ 4 в первом разряде и через открытую нулевым сигналом с нулевого выхода триггера 9 второго разряда элемента 6 поступает на вход элемента ИЛИ 4 второго разряда. С выхода элемента ИЛИ 4 рассматриваемый сигнал проходит через элемент И 6, открытый нулевым сигналом с нулевого выхода триггера 9 третьего разряда и через элемент ИЛИ 4 на вход 5 триггера 2 четвертого разряда. Через элемент 6 четвертого разряда рассматриваемый сигнал не проходит, так как он закрыт единичным сигналом с выхода триггера 9 четвертого разряда, На вход 5 триггера 2 первого разряда действует нулевой сигнал, поступающий по шине 1 6 с выхода триггера 2 четвертого разряда. В момент действия тактового сигнала 1 4 произойдет запись единицы в четвертый триггер 2 и нуля в первый триггер 2. В результате на регистре сформируется код 0101. Таким образом, при сдвиге разряды кода перепрыгивают через триггеры 2, отмеченные единицами в соответствующих разрядах регистра 7. Отмеченные триггеры 2 сохраняют прежнее состояние, При этом количество единиц в коде на регистре 1 остается неизменным. Поскольку последовательность нулей и единиц на выходах регистра 7, управляющая сдвигом кода в регистре 1, представляет собой псевдослучайную последовательность (с равными вероятностями появления "0" и 1), то5 6995перемешивание единиц в регистре 1 происходит в случайном порядке и на выходах регистра 1 формируются псевдослучайные кодовые комбинации постоянноговеса, причем математическое ожиданиепоявления 1 равно величинеи и(где К - вес кода; п- число разрядоврегистра 1.Чтобы получить на выходе генератора последовательность Р: К ( где 1 О1 тгп= и) с вероятностью появления "1",необходимо уменьшить начисло разрядов регистра 1, в которых осуществляется циркуляция символов кода, С этоицелью 6 разрядов задающего регистра1 2 устанавливаются в "1", При этом навыходах соответствующих с элементов1 0 постоянно присутствует единичныйсигнал, с помощью которого (как былоописано выше) 6 триггеров 2 выключены из цепи циркуляции регистра 1. Необходимо, чтобы К единиц, которые циркулируют в регистре 1, предварительнобыли записаны в любые К иэ и разря 25дов регистра 1, не отмеченные единицами регистра маски 12. В дальнейшем,под действием управляющих случайныхсигналов регистра 9 К единиц циркулируют в регистре 1, состоящем уже из30и разрядов, Соответственно, вероятностьпоявления единичного сигнала на выходегенератора будет равна:жКпГенератор позволяет значительно расширить диапазон изменения вероятностей35представления выходных единичных сигналов, по сравнению с известным генератором. Так, например, для Ъ 10, известный генератор имеет воэможность выдачи выходных единичных сигналов с вероятностями Р 1,1/10, 2/10, 3/10,9/10, 1,В то же время предлагаемый генератор позволяет изменять вероятности выходных единичных сигналов в соответствиисо следующим множеством значений;Р = 0,1/10) 1/9, 1/2, 2/10,2/9 2/8 2/3, 3/10 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/10, 1. 33 6Всего 33 значения против 11 для известного генератора, Если же моделируемая случайная величина не входит в приведенный ряд значений, то, тем не менее, предлагаемый генератор позволяет реализовать ее с максимальной погрешностью ивФормула изобретенияГенератор псевдослучайных кодов, содержащий рекуррентный регистр сдвига 1 циклический регистр сдвига, каждый разряд которого содержит первый элемент И, первый вход которого является входом "сдвиг" циклического регистра сдвига, а выход первого элемента И соединен с нулевым входом триггера, выход которого являетая разрядным выходом генератора и подключен к первому входу второго элемента И, выход которого подключен к первому входу элемента ИЛИ, второй вход которого соединен с выходом элемента "запрет", первый вход которого. объединен с единичным входом триггера и подключен к выходу элемента ИЛИ предыдущего разряда, о т л ич а ю щ и й с я тем, .что, с целью расширения функциональных возможностей генератора за счет изменения вероятностей сигналов на выходах генератора,он содержит регистр числа и в каждом разряде циклического регистра сдвига элемент ИЛИ-НЕ, выход которого .соединен со вторыми входами первого и второго элементов И и элемента "запрет", а входы элемента ИЛИ-НЕ соединены с выходами соответствующих разрядов рекуррентного регистра. сдвига и регистра числа.Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР Мо 375769, кл. б 06 Г 1/02, 1971, 2. Авторское свидетельство СССР И 0 468231,кл.б 06 Е 1/02 ю 1976. 3, Авторское свидетельство СССР по заявке М 2340415,кл. б 06 Г 1/02, 29.03.76 (прототип).по делам изобретений и открыти035, Москва, Ж, Раушская на Заказ 7230/52 Тираж 669 Подписное ЦНИИПИ Государственного комитетаСССР д, 4/5 лиал ППП "Патент, г. Ужгород, ул. Проектная, 4 Составитель А.дактор В, Сапирштейн Техред О. Лнд совкоКорректор Ю. Макаренко