Генератор псевдослучайных последовательностей импульсов
Патент 640344
Авторы
Генератор псевдослучайных последовательностей импульсов
Иллюстрации
Реферат
.l. (11 } 646344
ОП КСАН И Е изоы ятения
Сова Советскик
Социалистических
Республик
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 29.03.76 (21) 2340415/18-24 с присоединением заявки Kе (23) Приоритет (43) Опубликовано 30.12.78. Бюллетень Ме 48 (45) Дата опубликования описания 30.12.78 (51) М. Ь;л. Ci 07С 15 00
G 06F 1/02
Государственный комитет (53) УДК 681.325 (088.8) по делам изобретений н открытий (72) Авторы изобретения М. С. Берштейн, Л. Ф. Карачун, А. M. Романкев. ч и О. Д. Руккас (71) Заявитсль Киевский ордена Ленина политехническик институт имени
50-летия Великой Октябрьской социалистической революции (54) ГЕНЕРАТОР П СЕ ВДОСЛ УЧА Й Н Ь1Х
ПОСЛ ЕДОВАТЕЛ ЬНQCTEA ИМ П УЛ ЬСО В
Изобретение относится к области вычислительной техники и может быть использовано для решения широкого класса задач методом статистического моделирования, а также в качестве генератора испытательных последовательностей в автоматических системах контроля и диагностики, использующих различные вероятн ости ыс методы обнаружения отказов в цифровых схемах. 10
Известен генератор псевдослучайных импульсов, содержащий и-разрядный сдвигающий регистр, генератор тактовых импульсов, т-сумматоров по модулю два и коммутатор, содержащий и групп переключате- 15 лей по т рядов (1).
Недостатки известного состоят в большой сложности, а также в невозможности изменять вероятности сигналов на выходах.
Известен также генератор псевдослучайных последовательностей импульсов, содержащий основной регистр с сумматором по модулю два в цепи обратной связи (2).
Недостатком известного генератора является невозможность изменять вероятности сигналов на его выходах.
Целью изобретения является расширение функциональных возможностей генератора псевдослучайных последовательностей импульсов за счет изменения вероятностей сигналов на выходах генератора.
Генератор псевдослучайных последовательностей импульсов содержит первый и второй блоки эле кентов И, первый и второй блоки триггеров, первый и второй элементы ИЛИ, дополнительный регистр и регистр маски, по числу разрядов которого введены первый и второй элементы И и элемент ИЛИ, выход каждого из которых подключен к первому входу второго элемента И соответствующего разряда и к входу трпггсра по:,.сдующего разряда основного регистра, а входы элемента ИЛИ через первый и второй элементы И соответствующего разряда подключен к выходам триггеров того же разряда регистра маски и основного регистра соответственно, вход основного регистра подключен к выходу второго элемента ИЛИ, входы которого соединены с выходами второго блока элементов И, входы которого подключены к выходам второго блока триггеров и к второй группе выходов дополнительного регистра соответственно, первый вход второго блока элементов И подключен к выходу первого элемента -ИЛИ, входы которого соединены с выходами первого блока элементов И, входы которого подключены
640344
1О
65 к выходам первого блока триггеров н к первой группе выходов дополнительного регистра соответственно, вход которого соединен с выходом сумматора по модулю два.
На чертеже представлена функциональная схема предлагаемого генератора.
Генератор псевдослучайных последовательностей импульсов содержит п-разрядный основной регистр 1 с сумматором 2 по модулю два в цепи обратной связи, состоящий из тактируемых счетных триггеров 3 (триггеры Т вЂ” V-типа); блок 4 элементов И
5; блок 6 элементов И 7; блок 8 триггеров 9; блок 10 триггеров 11; элементы
ИЛИ 12 и ИЛИ 13; дополнительный регистр 14, разделенный на 1-разрядные группы 15 и содержащий одну (последнюю) группу из 1 — 1 триггеров 16; регистр маски
17, к выходам разрядов которого подключены элементы И 18 и И 19, связанные с элементами ИЛИ 20, выход каждого из которых подключен к первому входу элемента И 19 соответствующего разряда и к входу триггера 3 последующего разряда основного регистра 1, а входы элемента ИЛИ 20 через элементы И 18 и И 19 соответствующего разряда подключены к выходам триггеров 21 того же разряда регистра маски 17 и к выходам триггеров 3 основного регистра 1 соответственно. Вход основного регистра 1 подключен к выходу. элемента ИЛИ 13, входы которого соединены с выходами блока 6 элементов И 7. Входы блока 6 подключены к группе выходов 22 дополнительного регистра 14 и к выходам блока 10 триггеров 11 соответственно, причем нулевой выход триггера 11.1 связан с входом элемента И 7.1 блока 6, а единичный выход этого триггера связан с входом элемента И
7,2, нулевой выход триггера 11.2 связан с входом элемента И 7.2, а единичный выход этого триггера с входом элемента И 7.3 и т. д. Вход 23 блока 6 подключен к входу элемента ИЛИ 12, входы которого соединены с выходами блока 4. Входы блока 4 подключены к группе выходов 24 дополнительного регистра 14 и к выходам блока 8 триггеров 9 соответственно, причем нулевой выход триггера 9,1 связан с входом элемента И 5.1 блока 4, а единичный выход этого триггера связан с входом элемента
И 5.2, нулевой выход триггера 9.2 связан с входом элемента И 5.2, а единичный выход этого триггера с входом элемента И
5.3 и т. д. Вход дополнительного регистра
14 соединен с выходом сумматора 2 по модулю два. Каждая группа 15 дополнительного регистра состоит из триггеров 25 (Т вЂ” V-типа), выходы каждого из которых связаны со счетным входом триггера 25 следующего разряда.
На входы триггеров 21 заведены шины
26 установки кода маски, на входы триггсров 9 н 11 заведены шины 27 настройки групп 15 и триггеров 16 дополнительного регистра 14. На все синхровходы триггеров
3, ?5 и 16 заведена шина 28 синхроимпульсов.
Предлагаемый генератор псевдослучайных последовательностей работает следующим образом.
В начальный момент времени в основной регистр 1 записывается (от ЭВМ либо с клавиатуры пульта) любое п-разрядное число, отличное от нуля, Производится также заполнение регистра маски 17, предназначенного для фиксации тех разрядов регистра 1, которые в дальнейшем будут сохранять записанные в них предварительно состояния «1» или «О», т. е. будут пассивными, дополнительного регистра 14, предназначенного для дополнения количества активных триггеров регистра 1 до и разрядов (при этом сохраняется условие генерирования последовательности максимального периода), триггеров 9 блока 8 и триггеров 11 блока 10, предназначенных для настройки групп 15 и триггеров 16 дополнительного регистра 14. В том случае, если все разряды регистра 1 предполагается оставить активными, во все триггеры 21 регистра 17 по шинам 26 заносятся «единицы», а во все триггеры 9 блока 8 и 11 блока 10 по шинам 27 заносятся «нули».
При такой настройке устройства сигнал с единичного выхода триггера 3 в любом разряде проходит через элемент И 18, на второй вход которого поступает потенциал
«1» с единичного выхода триггера 21, и через элемент ИЛИ 20 поступает на счетный вход (V — входы) триггера 3 следующего по номеру разряда регистра 1. Через элемент И 19 этого разряда сигнал не проходит, так как элемент 19 закрыт потенциалом «О» с нулевого выхода триггера 21 этого же разряда. В момент действия тактового сигнала, поступающего по шине 28 на синхровходы (Т вЂ” входы) всех триггеров 3, в каждом триггере 3 происходит установка «нового» состояния, которое представляет собой сумму по модулю два «старого» состояния данного триггера 3 и «старого» состояния триггера 3 предыдущего по номеру разряда, Установка в очередное состояние триггера 3 первого разряда регистра 1 отличается от установки других триггеров 3. Так как «новое» состояние первого разряда регистра 1 получается в результате суммирования по модулю два «старого» состояния триггера 3 в этом разряде и «нового» состояния последнего (n-ro) разряда, на счетный вход триггера 3 в первом разряде необходимо подать сигнал с выхода сумматора 2. Сигнал с выхода сумматора 2 проходит через элементы И 5.1, ИЛИ 12, И 7.1, ИЛИ 13 (элементы № 5.1 и И 7.1 открыты потенциалом «1» с нулевых выходов
640344 триггеров 9.1 11.1 соответственно) и поступает на счетнь1й вход триггера 3 в первом разряде регистра 1.
11усть необходимо -й разряд генератора сделать пассивным и удерживать его постоянно в фиксированном состоянии «1» или «О». «1» или «О» заносится в триггер 3 i-го разряда регистра 1, а в соответствующий 1-й разряд регистра маски 17 заносится «О». 11ри этом сигнал с единичного выхода триггера 3 (i — 1) -ro разряда проходит через элементы И ib и ИЛИ 20 этого разряда и поступает на одну пару Ч-вхoдов триггера 3 i-го разряда. 11оскольку на вторую пару Ч-входов триггера 3 i-го разряда с единичного выхода триггера 21 этого же разряда регистра маски 17 подается потенциал «О», триггер 3 не изменяет своего состояния и становится пассивным, а рассматриваемый сигнал проходит через элемент И 19, открытый потенциалом «1» с нулевого выхода триггера 21 и далее через элемент ИЛИ 20 поступает на счетный вход триггера 3 в (i+1)-ом разряде. Таким образом осуществляется обход i-й ячейки генератора в процессе работы, а в самой
i-й ячейке сохраняется «1» или «О» предварительно туда записанные.
Если в регистре 1 некоторые триггеры 3 переведены в пассивный режим, необходимо подключить к выходу регистра 1 цепочку из такого >ке количества триггеров дополнительного регистра 14 (оощее число триггеров регистра, охваченного обратной связью должно быть равным n), триггер
3 в последнем разряде регистра 1 всегда является активным. Для этого устанавливаются в «1» соответствующие триггеры 9 блока 8 и 11 блока 10. Например, если в
«1» установлен триггер 9.1, то к основному регистру 1 будет подключена цепочка из триггеров 25, входящих в первую группу
15. В этом случае сигнал с выхода сумматора 2 проходит через триггеры 25 первой группы 15 и поступает на вход элемента
И 5.2, который открыт, так как на его второй и третий входы поступают потенциалы
«1» с единичного выхода триггера 9.1 и нулевого выхода триггера 9.2. С выхода элемента И 5.2 рассматриваемый сигнал проходит через элементы 12, 7.1 и 13 на счетный вход триггера 3 в первом разряде регистра 1. Если в «1» будут установлены триггеры 9.1 и 9.2, то откроется элемент И
5.3, связанный с выходом второй группы 15 и в этом случае к регистру 1 будет подключена цепочка триггеров 25, составляющих первую и вторую группу 15.
Наконец, если все триггеры 9 блока 8 установлены в «1», откроется элемент И 24 и будут подключены все группы 15 регистра 14.
Если необходимо подключить цепочку, число триггеров которой не кратно числу триггеров в группе, дополнительно исполь5
65 зуются триггеры 16, подключением каждого из которых управляют триггеры 11 блока
10. Подключение триггеров 16 осуществляется по такому же принципу как и подключение групп 9.
Для того чтобы не происходило искажения сигнала при прохождении его через схемы И и ИЛИ, в случае необходимости обхода большого количества расположенных подряд пассивных разрядов, основной регистр i может быть разбит на группы и вместо обхода отдельных пассивных разрядов осуществлен обход всей группы, состоящеи только из пассивных разрядов.
Обход групп осуществляется по такому же принципу как и обход отдельных разрядов.
Гlредлагаемый генератор обладает возможностью перестройки, благодаря которой можно получать псевдослучайные сигналы на произвольно выбранных разрядах основного регистра генератора. Используя это свойство, можно реализовать генератор с различным числом разрядов и, выбранным из ряда чисел и=2, 3, 4, б, 7, 15, 22, 60, 63, 127,..., не изменяя структуры генератора. При этом обеспечивается максимальная длина периода последовательности для соответствующих значений и.
Предлагаемый генератор обладает возможностью изменения вероятностей сигналов на выходах генератора (по любым заданным выходам могут быть выданы сигналы с математическим ожиданием О, 5, О, или 1). При использовании предлагаемого генератора в качестве генератора псевдослучайных тестовых последовательностей в устройствах контроля цифровых схем свойство изменения вероятностей сигналов позволяет сократить время проверки и во многих случаях исключить подачу комбинаций входных сигналов, вызывающих критические гонки.
Формула изобретения
Генератор псевдослучайных последовательностей импульсов, содержащий основной регистр с сумматором по модулю два в цепи обратной связи, отличающийся тем, что, с целью расширения функциональных возможностей генератора за счет изменения вероятностей сигналов на выходах генератора, он содержит первый и второй блоки элементов И, первый и второй блоки триггеров, первый и второй элементы ИЛИ, дополнительный регистр и регистр маски, по числу разрядов которого введены первый и второй элементы И и элемент ИЛИ, выход каждого из которых подключен к первому входу второго элемента И соответствующего разряда и к входу триггера последующего разряда основного регистра, а входы элемента ИЛИ через первый и второй элементы И соответствующего разряда подключены к выходам триггеров того же разряда регистра маски и основного
640344
Составнiелн А. t(àðàcîâ
Техред С. Антипенко
Корректор E. Хмелева
Редактор Ю. Челюканов
Заказ 2360/14 Нзд. М 613 Тираж 692 Подписное
НПО Гocy„"àðñòâåíного ко:птета СССР -.о делам изобретений и открытий
113035, Москва Я(-35, Р",óøñêçÿ наб., д. 4/5
Типография, пр. Сапунова, 2 регистра соответственно, вход основного регистра подключен к выходу второго =,".ñмента ИЛИ, входы которого соединены с выходами второго блока элементов И, в ;оды которого подключены к выходам второго блока триггеров и к второй группе гыходов дополнительного регистра соответственно, первый вход второго блока элементов И подключен к выходу первого элемента ИЛИ, входы которого соединены с выходами первого блока элементов И, входы которого подключены к выходам первого олока триггеров и к первой группе выходов дополнительного регистра соответственно, вход которого соединен с выходом
5 сумматора по модулю два.
Источники информации, принятые во внимание при экспертизе
1. Авторское свидетельство СССР № 375769, кл. G 06 F 1/02, 1971.
10 2. Авторское свидетельство СССР № 468231, кл. G 06 F 1/02, 1973.