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

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

Иллюстрации

Показать все

Реферат

 

0 Il И Е <,699533

ИЗОБРЕТЕНИЯ

Союз Соаетсммн

Социвлнстнчесиин

Респубнии

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (51)м. Кл.

5 07 С 15/00

G 06 F 1/02 (22)Заявлено 18.07.77 (21) 2508754/18-24 с присоединение@ заявки J% (23) Приоритет

Гвсудерстеннньй неинтет

СССР нн делам нзобрнтвннй н нтнритнй

ОпУбликовано 25.11.79. Бюллетень М 43 (53) ДК 681 325 (088.8) Дата опубликования описания 28.11.79

М. С. Берштейн, О. В, Викторов, Л. Ф. Карачун и A. М. Романкевич (72) Авторы изобретения

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

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

Известен генератор псевдослучайных

10 кодов, содержащий 11-разрядный сдвигающий регистр, генератор тактовых импульсов, ттт сумматоров по модуйто два и ком мутатор, содержащий тт групп переключателей по ттт рядов (1).

Его недостатки состоят в большой сложности, а также в невозможности изменять вероятности сигналов на выходах.

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

Недостатком известного устройств является невозможность изменять вероятности сигналов на его выходах.

Наиболее близким по технической cymности к предложенному является генератОр псевдослучайных кодов, содержащий рекур» рентный регистр сдвига, циклический ре» гистр сдвига в каждом разряде которо го содержится первый элемент И, первый вход которого. является входом сдвиг циклического регистра сдвига, а выход первого элемента И соединен с нулевым входом триггера, выход которого являет» ся разрядным выходом генератора и подключен к первому входу второго элемента И, выход которого подключен к первому входу элемента ИЛИ, второй вход которого соединен с выходом элемента

1 запрет", первый вход которбго объединен с единичным входом |риггера и под ключен к выходу элемента ИЛИ предыду« щего разряда (3).

Недостатком этого устройства является невозможность точно представить ряд

99533 4

Uenb изобретения — расширение функциональных возможностей генератора псевдослучайных последовательностей импульсов за счет изменения вероятностей сигналов на выходах генератОра.

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

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

Генератор содержит циклический регистр сдвига 1, состоящий иэ триггеров

2, единичный выход каждого из которых в каждом 1-ом разряде соединен с вхо« дом элемента И 3, выход которого через элемент ИЛИ- 4, подключен к информационному входу 5 триггера 2 в (1+ 1)-оМ разряде и к одному входу элемента«

"запрет" 6 в (1 +1)-юм разряде. В цепь обратной связи рекуррентного регистра сдвига 7 включен сумматор по модулю два 8. Нулевые выходы триггеров 9 регистра 7 соединены в каждом разряде с одним входом элемента ИЛИ-НЕ 10, другой вход которого соединен с единичным выходом триггера 11 регистра числа 12, а выход элемента ИЛИ-НЕ 10 подключен к инверсному входу элемента "запрет 6, к одному входу элемента И 3 и к одному входу элемента И 13, второй вход которого подсоединен к шине тактовых сигналов 14, а выход подключен к тактовому входу 15 триггера 2. Выход элемента ИЛИ 4 последнего разряда по шине обратной связи 16 подключен к входу 5 триггера 2 в первом разряде и к одному входу элемента "запрет 6 в этом же разряде.

Работу устройства рассмотрим на примере для числа разрядов h = 4.

Регистр 7 с сумматором по модулю два 8 генерирует псевдослучайную последовательность равномерно распределенных нулей и единиц, с помощью которых производится управление сдвигом кода в регистре 1. На регистре 1 формируются з 6 значений вероятностей появления единичного выходного сигналя, не принадлежащих множеству: (з

О ъ «ь

} )Ч l1 П ,«

1О !

zo

25 зо

4О

55 A -разрядные коды постоянного веса, где И вЂ” число разрядов регистра 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 четвертого разряда. B момент действия тактового сигнала 1 4 произойдет запись единицы в четвертый триггер 2 и нуля в первый триггер 2. В результате на регистре сформируется код О101. Таким образом, при сдвиге разряды кода перепрыгивают через триггеры 2, отмеченные единицами в соответствующих разрядах регистра

7. Отмеченные триггеры 2 сохраняют прежнее состояние, При этом количество единиц в коде на регистре 1 остается неизменным. Поскольку последовательность нулей и единиц на выходах регистра 7, управляющая сдвигом кода в регистре 1, представляет собой псевдослучайную последовательность (с равными вероятностями появления "0" и 1 ), то

5 6995 перемешивание единиц в регистре 1 про« исходит в случайном порядке и на выходах регистра 1 формируются псевдослучайные кодовые комбинации постоянного веса, причем математическое ожидание появления 1 равно величине и и % где К вЂ” вес кода; ц- число разрядов регистра 1.

Чтобы получить на выходе генератора последоватеЛьность p = (где 10

1 rn

nl=n-6) с вероятностью появления "1", необходимо уменьшить на 0 число разрядов регистра 1, в которых осуществляется циркуляция символов кода. С этои целью 6 разрядов задающего регистра

1 2 устанавливаются в "1 . При этом на выходах соответствующих 6 элементов

1 О постоянно присутствует единичный сигнал, с помощью которого (как было описано выше) (, триггеров 2 выключены из цепи циркуляции регистра 1. Необходимо, чтобы К единиц, которые циркулируют в регистре 1, предварительно были записаны в любые К иэ ll разря25 дов регистра 1, не отмеченные единицами регистра маски 12. В дальнейшем, под действием управляющих случайных сигналов регистра 9 К единиц циркулируют в регистре 1, состоящем уже из

30 и разрядов. Соответственно, вероятность появления единичного сигнала на выходе генератора будет равна:

P = —.

К

it1

Генератор позволяет значительно расширить диапазон изменения вероятностей

35 представления выходных единичных сигналов, по сравнению с известным генератором. Так, например, для ll 10, известный генератор имеет воэможность выдачи выходных единичных сигналов с вероятностями Р „"-1,1/1 О, 2/1 О, 3/1 О, 9/10, 1.

В то же время предлагаемый генератор позволяет изменять вероятности выходных единичных сигналов в соответствии со следующим множеством значений:

P = 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 для известного генератора. Если же моделируемая случайная величина не входит в приведенный ряд значений, то, тем не менее, предлагаемый генератор позволяет реализовать ее с максимальной погрешностью

nrn

Формула изобретения

Генератор псевдослучайных кодов, содержащий рекуррентный регистр сдвига циклический регистр сдвига, каждый разряд которого содержит первый элемент

И, первый вход которого является входом "сдвиг" циклического регистра сдвига, а выход первого элемента И соединен с нулевым входом триггера, выход которого являетая разрядным выходом генератора и подключен к первому входу второго элемента И, выход которого подключен к первому входу элемента

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

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

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

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

N 337755776699, кл. 6 06 Г 1/02, 1971. 2. Авторское свидетельство СССР

И9 468231, кл, б 06 F 1/02, 1976.

3. Авторское свидетельство СССР по заявке No 2340415, кл. G 06 F 1/02, 29.03.76 (прототип).

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

Редактор В. Сапирштейн Техред О. ЛндрейкоКорректор Ю. Макаренко

Заказ 7230/52 Тираж 669 Подписное

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

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

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