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

 

О П И С-А - И- -"И" Е

ИЗОБРЕТЕ Н ИЯ

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

Союз Советскнх

Соцналнстнмеских

Ресяублнк

<п 674007 (gl) дополнительное к авт. свил-ву> 468231 (22) Заявлено 23.03 77(21} 2465664/18- 24

- с присоединением заявки №вЂ” (23) ПриоритетОпубликовано15. 07.79.Бюллетень №26 (Я} М. Кл.

G 06 F 1/02

G, 07 С 15/00

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

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

В. В. Гроль и А. М. Романкевич

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

Изобретение относится к области вь числительной техники и может. быть использовано в стохастических счетнорешаюших устройствах.

Известное изобретение по авт. св. № 468231 содержит rl -разрядный регистр сдвига с сумматором по модулю 2 в цепи обратной связи, часть разрядов регистра сдвига выполнены на триггерах со счетным входоМ, а остальные (а-Al) разрядов - на триггерах с установочными Ч входами, счетные входы первых rn триггеров соединены с единичными выходами соответствуюших (n.— ттт ) триггеров уотанойочные входы которых подключены к выходам первых m триггеров соответсч венно (1) .

Недостатком известного изобретения лвляется невозможность обнаружения неисправности генератора псевдослучайных чисел (ГПС ф проявляюшейся в уменьшении периода последовательности псевпослучайных чисел.

БелЬю изобретения является повышение надежности работы генератора.

Для достижения поставленной цели

ГПСЧ по авт. св. № 486231, содержит дешифратор, делитель, элемент задержки,. элемент НЕ, первый и второй элементы

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

На фиг. 1 представлена блок-схема генератора; на фп. 2 изображено соединение триггеров регистра сдвига для ,й =5, rn 3.

На вход тт -разрядного регистра сдвига 1, состояшего из m триггеров

674007 (2,1) - (2. Го } со счетным входом и (и -Al } триггеров 2 (Гп+1) - (2. fl ) с установочным входом, заведена шина так говых импульсов 3, которая подключена также к входу делителя 4. Выход делителя 4 через элемент задержки 5 сое« динен со входом элемента И 6 и входом элемента И 7. Единичный выход произвольного (2. 3 ) -го григгера регистра, сдвига 1 подключен к входу tl -входового элемента И 8, а также к входу элемента И 6. На остальные (II -1) входы элемента И 8 заведены любые выходы (n -1) триггеров регистра сдвига 1..Выход элемента И 8 через элемент НЕ 9 соединен с третьим входом элемента И 6.

Выходы элементов И 6 и И 7 подключены соо гветственно к входам 10 и ll реаерсивного счетчика 12, выход котоРого соединен с шиной ошибки 13. Нулевой выход (2. 1 )-го триггера регистра сдвига 1 заведен на вход элемента И 7. . Работа устройства осуществляется следующим образом.

Если числа и и rn вйбраны в соот ветствии с индексамиединственных единичных коэффициентов неразложимого и примитивного многочлена степени и и, кроме того, числа Гп и (2 -1) являются взаимно простыми, тогда генерируемая последо- 0 вательность псевдослучайных чисел имеет период (2 -1) тактов при отсутствйи отказов в схеме. Так как нулевое состоайие регистра сдвига 1 является запрещенным, то для любого разряда регистра сдвига 1 число единичных состояний этого разряда за (2 -1} тактов равно 2 а число ..

П Г3"1

:нулевых состояний (2»»1). Текущая

4. разность числа единиц и нулей в 4 -м

"разряде регистр сдвига 1 подсчитывается с помощью реверсивного счетчика 12. На вход ..1О (нацример, вход суммирования) им.пульс с выхода делителя 4 через элемент задержки 5 и элемент И 6 проходит при совпадении единичного уровня с выхода (2. )-го триггера регистра 1 и единичного уровня с выхода элемента HE 9. Нулевой уровень на выходе элемента HE 9 вырабатывается только в течение одного из (2 -1) тактов работы генератора, и так как элемент И 8 дешифрирует только

GAHo HG (2 -1 ), IIIñeII причем для sTQFo числа 3 .-разряд должен находиться в единичном состоянии. Нулевой уровень с выхода элемента HE 9 закрывает на один такт элемент И 6 и блокирует добавление одной единицы в счетчик 12, исключая тем самым накопление единиц в счетчике

Д

12 н переполнение этого счетчика, кото рое может произойти за счет наличия разницы числа нулевых и единичных состояний (2. < )-го триггера регистра 1 в те чение (2 -1) тактов.

fl

"т

При нулевом состоянии (2.l) -го триггера импульс с выхода элемента задержки 5 через элемент И 7 проходит на вычитающий вход 11 реверсивного счетчика

12. Разрядность этого счетчика должна выбираться такой, чтобы при правильнойработе едвигового регистра 1 не проиоходило переполнение счетчика 12 за

3 -1 тактов его работы (так как после этого числа тактов содержимое реверсивного счетчика 12 должно быть равно нуmo, учитывай коррекцию с помощью элемейтов И 8 и HE 9, а также при условии от сутствия отказов в сдвиговом регистре). Появление неисправности в регистре 1 приводит к тому, что один или несколько триггеров этого регистра будут постоянно (независимо от сигналов на их входах) находиться в одних и тех же (единичных или нулевых) состояниях. При этом произойдет уменьшение периода генерируемых чисел но сравнению с величиной (2 -1). : Новый период будет равен 2" тактов (k. =0,1,2,3 ...), величина ощидолаеъ" ся из соотношейия, 2 >щ > 2

:. где k — количество триггеров со счетным входом в регистре сдвига 1. Прн появлении многократных ошибок в этом регистр ре (или же в зависимости от числа, хранящегося в регистре в момент возникновения отказа) цервод левой последователь« ности может быть меньше чем 2 такК тов, однако величина 2 будет кратна этому новому периоду.

Таким образом, если коэффициент де-

; ления частоты 4 выбран (установлен)

К равным 2 (т.е. на выход делителя 4 проходит каждый 2 -й тактовый импульс

K с шины 3), то в реверсивный счетчик 12 будет постоянно добавляться (или вьгчитаться) единица, так как при неисправном регистре сдвига 1 (2 4 )-ый триггер на каждом 2 -также будет находиться в

K одном и том же (единичном или нулевом) состоянии. Это приведет к переполнению счетчика 12 и по шике 13 будет выдан сигнал ошибки.

Элемент задержки 5 введен для устранения влияния на работу устройства задержек дешифратора И 8 и элемента

HE 9, а также переходных процессов при измененин состояния регистра сдвига 1.

674007

В качестве примера рассмотрим ГПСЧ, длЯ котоРого в соответствии с требова ниями, предъявляемыми к соотношению величин г и й,, выбраны о =5 mrs 3.

Для такого ГПСЧ (фиг. 2) триггер (2.1}- 5 (2.3) должны быть выполнены со счетным входом, а (2.4) и (2.5) — с установленным. Так какп1 =3, то k =2 вследствие того, что 2 % 3 > 2 . Пусть в резуль2, тате отказа на единичном выходе триггера (2Л) постоянно присутствует высокий (единичный) уровень, а неисправность возникла на р -м такте, когда триггеры регистра сдвига 1 находились в следуюших состояния."с триггер .2.1 2.2 2.3 2.4 2.5 состояние 1 0 0 1 1

При дальнейшем поступлении тактовых импульсов генератор будет вырабатывать такую последовательность: триггер: 2.1 2.2 2.3 2.4 2.5 (+1) такт 1 1 1 1 1 (+2) " о о о (у+3) " 0 1 1 0 1 (+4) " 1 1 О 0 (+5) 1 1 1 - 1 1 (j+6) " О . О 0 1 1 и т.д.

Из примера видйо, что, начиная с (+1J-го такта, ГПСЧ вырабатывает по.

5О следовательность чисел с периодом в 4 такта. Следовательно, каждый четвертый тактовый импульс, проходя с выюда де.лителя частоты через элемент задержки, будет совпадать с одним и тем же (ну35 левым или единичным) состоянием любого триггера регистра сдвига, что приведет .к переполнению реверсивного счетчика.

° Аналогично можно показать, ч го возникновение неисправности другого типа (например, постоянное единичное состояние нескольких триггеров регистра 1) приведет к выдаче последовательности с периодом, меньшиков чем 4 такта, но Равным делите4 4 лю числа 4 .

Если время использования генератора меньше, чем 2 (2 -1) тактов, то деи шифратор 8 и элемент НЕ 9 могут быть удалены, так как при правильной работе регистра сдвига 1 реверсивный счетчик

12 не переполнится за время работы, вследствие того, что перед началом ис-, пользования генератора счетчик 12 устанавливается в исходное нулевое состояние (на

55 структурной схеме цепи исходной установки не показаны).

В случае, если CA=0 (т.е. если в гене;

Ржарах используются. только триггеры с установочными входами), сушествует возможность дальнейшего упрошения заявляемого устройства путем удаления делителя частоты тактовых импульсов, так как при возникновении неисправности в сдвиговом регйстр»е, триггеры которого выполнены только с установочными входами, период повторения формируемой генератором Ю» последовательности будет составлять один такт, т.е. триггеры регистра не будут изменять свое состояние.

Эффективность применения ГПСЧ повышенной надежности можно обосновать исходя из следующих соображений: в автоматизированных системах контроля функциональных модулей (печатных плат) электронно-вычислительных машин, использование статических методов контроля приводит к построению генератора с большим количеством разрядов (числа входных контактов на таких платах может достигать сотни и более). С ростом сложности генератора увеличивается вероятность появления в нем отказов, приводяших к снижению периода генерируемой последовательности и, как следствие этого, к уменьшению надежности и достоверности работы системы статистического контроля, из-аа уменьшения разнообразия чисел, подаваемых на входные контакты проверяемых печатных плат. В связи с этим уменьшается вероятность обнаружения неисправностнй на плате и функциональный модуль, содержаший неисправные элементы, по результатам статистического контроля может быть признан исправным. Следовательно, введение в ГПСЧ возможности обнаружения в нем неисправностей приводит к повышению надежности и достоверности функционирования системы статистического контроля в целом.

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

Генератор псевдослучайных чисел по авт. св. 3Ф 468231, о т л и ч а ю—

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

674007

Фик 1 pvi.g .

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

Редактор Д. Зубов Гехред Л. Алферова - Корректор, О. Ковинскаи

Заказ 4078/45 Тираж 779 Подписное

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

113038; Москва, Ж36; -Раушскаи--наб.; -n, 4/5

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

7 сдвига, выходы регистра сдвига соединены со входами дешйфратора, выход которого через элемент НЕ соединен с третьим входом первого элемента И.

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

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

¹ 468231, кл. 9 06 F 1/02, 1973.