Устройство для контроля генератора случайных чисел

 

Изобретение относится к вычисолительной технике и может быть использовано для быстрого обнаружения сбоев в генераторе случайных чисел. Цель изобретения - повышение тЬчиости. Устройство содержит генератор 1 тактовых импульсов, генератор 2 случайных чисел, регистр 3 сдвига, группу сумматоров 4 по модулю два, группу элементов НЕ 5, регистры памяти на триггерах 6, 7, элемент ИЛИ 8, счетчик 9, триггеры 10, 11. 1 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5D 4

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3998190/24-24 (22) 29.12.85 (46) 07.04.87. Бюл. У 13 (72) Н.Н. Сергеев, О.И. Дапин, В.И. Глова, В.М. Кузнецов, В.В. Моисеев, В.А, Песошин и Е.К.Шаронова (53) 681.325(088.8) (56) Авторское свидетельство СССР

11 796856, кл. G 06 Р 7/58, 1679.

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

У 1088011, кл. G 06 F 7/58, 1982. (54) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ ГЕНЕРАТОРА СЛУЧАЙНЫХ ЧИСЕЛ (57) Изобретение относится к вычис0лительной технике и может быть использовано для быстрого обнаружения сбоев в генераторе случайных чисел.

Цель изобретения — повышение точности. Устройство содержит генератор 1 тактовых импульсов, генератор 2 случайных чисел, регистр 3 сдвига, группу сумматоров 4 по модулю два, группу элементов НЕ 5, регистры памяти на триггерах 6, 7, элемент ИЛИ 8, счетчик 9, триггеры 10, 11. 1 ил.

1302274

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

Цель изобретения — повышение точности.

На чертеже приведена блок-схема устройства. 10

Устройство содержит генератор 1 тактовых импульсов, контролируемый генератор 2 случайных чисел, регистр

3 сдвига, группу сумматоров по моду- лю два 4, 4, ..., 4„„,, группу элементов НЕ 5,, 5, ..., 5,„1, первый регистр 6 памяти на триггерах

6,, 6, ..., 6щ1, второй регистр 7 памяти на триггерах 7„, 7

?,„ц, .элемент ИЛИ 8, счетчик 9, 2р

D-триггер 10, RS-триггер 11, вход

12 запуска устройства, информационный выход 13, контрольный выход 14.

Устройство работает следующим образом. 25

Генератор 2 случайных чисел по каждому импульсу генератора 1 тактовых импульсов формирует символ случайной бинарной последовательности, который поступает на информационный 30 выход 13.

Символы случайной последовательности воспринимаются пользователем в том случае, если на контрольном выходе 14 присутствует сигнал логического "0".

Перед началом работы устройства однократной подачей единичного сигнала (например, при помощи переключателя П) на вход 12 устанавливают 4р счетчик 9 и регистр 3 сдвига в нулевое состояние, а триггер 11 — в единичное состояние. Триггер 10 блокирован единичным логическим уровнем на его асинхронном единичном устано- 45 вочном входе. Поэтому первые N символов (N — модуль пересчета счетчика

9) после запуска бракуются (обычно начальный участок случайной последовательности ГСЧ является нестационарным). э

По фронту N-го синхроимпульса на выходе счетчика 9 формируется единичный импульс, который сбрасывает триггет 11 в "0" и устанавливает триггеры 6, 6 ° ° ° 6тlг и 7 7

7 п гервого 6 и второго 7 регистров в единичные состояния. На

S-входе триггера 10 действует сигнал логического "0", поэтому триггер 10 переходит в режим работы синхронного

D-триггера.

Если за время между (N-m)-м и

2N-м тактовыми импульсами на выходе генератора 2 присутствуют только единичные символы, то на выходах всех сумматоров по модулю два 4„, 4

4 1 постоянно действуют уровни логического "0" (1®1=0), а на выходах всех элементов НЕ 5,, 5, ..., 5 сигналы логической "1". Поэтому к моменту появления импульса на выходе счетчика 9 (импульса опроса) все триггеры 6,, 6, ..., 6 находят в единичных состояниях, а все триггеры 7,, ?, ..., 7„, — в нулевых.

Следовательно, по фронту импульса опроса в триггер 10 запишется единица, т.е. на контрольном выходе 14 появится сигнал логической "1 свидетельствующий о „сбое в генераторе 2 и бракующий выборку случайной последовательности длиной.

Если за время между (N-m)-м и

2N-м тактовыми импульсами на выходе генератора 2 появится хотя бы один нулевой символ, а остальные символыединичные, то по фронту синхроимпульса на. выходах всех сумматоров по модулю два группы 4,, 4, . ° ., 4 появятся уровни логической "1" (991=1) и соответственно по срезу синхроимпульса все триггеры 6, 6, бщ сбросятся в "0", а триггеры 7, 7, ..., 7 p)(останутся в состоянии "0". Поэтому импульс опроса запишет в триггер 10 "0", следовательно, на KOHTpoJIbHQM выходе 14 появится сигнал логического "0" и ситуация считается нормальной.

Аналогичные результаты получаются и в случае пачек нулевых (преимущественно) символов генератора 2.

Если за время между (N-ш)-м и

2N-м тактовыми импульсами на выходе генератора 2 присутствует устойчивая периодическая последовательность, период Т которой не превышает m то на выходе хотя бы одного сумматора по модулю два 4, номер k которого удовлетворяет условию

m/2+k

Т где Р— целое (Р=1, 2, ..., m), будет постоянный сигнал логического "0".

1302

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

Если за время между (N-m)-м и

2N-м тактовыми импульсами на выходе генератора 2 присутствует устойчивая меандро-инвертированная последовательность с периодом Т « 2ш, то на выходе хотя бы одного сумматора по модулю два 4„, номер k которого удовлетворяет условию

m/2+k

Тес72

15 будет постоянный сигнал А,=0,1 (А =0 при P четных и А =-1 при P нечетных) к

Здесь под меандро-инвертированными последовательностями понимаются последовательности, составленные из чередующихся последовательностей (ъ,! и jb; 2, где (ъ; ) — последовательность, противоположная (Ь;);

Ь< =0,1. Например, если (Ъ,) ,=1101011010..., то меандро-инвертированная последовательность

11010001011101000101 ..., где b;

0010100101

Например, если генератор 2 в результате сбоя формирует простейшую меандро-инвертированную последовательность вида и и

111...1 000...0 и п

111...1 000...0... где n=T m то на выходе сумматора по модулю два 4„, сдвиг c„ =m/2+k между последовательностями (1) на входах которого кратен периоду Т„„ = — 2 и последовательности (1) (Р— четные), будет постоянно присутст вовать сигнал А„=О (191=0 или 0+0=0).

Если сдвиг с кратен половине периок да Т „ /2 последовательности (1) (Р нечетные), то на выходе сумматора по модулю два 4 будет постоянно присут-. ствовать сигнал А =1(1®О=! или 091=1) к 50

Следовательно, в этом случае хотя бы один триггер бк первого регистра

6 (AKO) либо хотя бы один триггер

7 второго регистра 7 (A„=l) к приходу опрашивающего импульса останет- 5

55 ся в единичном состоянии. Поэтому на выходе 14 появится сигнал "1", т.е. зафиксируется сбой в генераторе 2.

274 4

Если за время между (N-m)-м и

2N-м тактовыми импульсами на выходе генератора 2 будет формироваться последовательность, отличающаяся от периодичности хотя бы в одном такте, то на выходах всех сумматоров по модулю два 41, 4, ..., 4ъ,I будет хотя бы один перепад из "1" в "0" либо из

"0" в "1". Поэтому все триггеры 6,, 62 ... 6щ! и 7,, 7, ..., 7л1 первого и второго регистров на RSтриггерах к приходу импульса опроса будут в нулевых состояниях, следовательно, на выходе 14 сформируется сигнал "0", что свидетельствует о нормальной работе генераторе 2 °

Объем выборки N (так же, как и для известного устройства) и значение ш определяются на основе статистических критериев в зависимости от требуемых уровней доверия.

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

Устройство для контроля генератора случайных чисел, содержащее генератор тактовых импульсов, выход которого является выходом устройства для подключения к входу "Опрос" контролируемого генератора случайных чисел, D-триггер, элемент ИЛИ, счетчик, о т л и ч а ю щ е е с я тем, что, с целью повьппения точности, оно содержит регистр сдвига, группу сумматоров по модулю два, группу элементов НЕ, RS-триггер, два регистра памяти, выходы разрядов которых подключены к входам. элемента ИЛИ соответственно, выход которого соединен с D-входом D-триггера, синхронизирующий вход которого объединен с установочными входами первого и второ"о регистров памяти и подключен к выходу счетчика, счетный вход которого объединен с синхронизирующими входами первого и второго регистров памяти и регистра сдвига и подключен к выходу генератора тактовых импульсов, вход устройства подключен к выходу контролируемого генератора, соединен с информационным входом регистра сдвига и с первыми входами сумматоров по моду. ю два группы, вто- рой вход каждого .с-ro сумматора по модулю два группы соединен с (m/2+ °

+k)-м выходом регистра сдвига (k=1, ш/2, ш — разрядность регистра сдвига, m=2, r=l, 2, ...), а выход каждого k-го сумматора по модулю два

274

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

Редактор Л. Гратилло Техред Л.Олейник Корректор А. Ильин

Заказ 1217/48 . Тираж 673 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

5 1302 группы подключен к входу k-го разряда первого регистра памяти и входу

k-го элемента НЕ группы, выход которого соединен с входом k-ro разряда второго регистра памяти, установочный 5 вход D-триггера соединен с единичным выходом ББ-триггера, К-вход которого подключен к выходу переполнения счетчика, а S-вход RS-триггера объединен с входом "Сброс" счетчика, с установочным входом регистра сдвига и является входом "Пуск" устройства, выходом "Ошибка" которого является выход

D-триггера.