Устройство для контроля генератора случайных чисел Советский патент 1987 года по МПК G06F7/58 

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

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

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

устройства.

Устройство содержит генератор 1 тактовых импульсов, контролируемьй генератор 2 случайных чисел, регистр 3 сдвига, группу сумматоров по модулю два 4,, 4, ..., 4,2, группу элементов НЕ 5,, 5, , mli первый регистр 6 памяти на триггерах 6,, 6, ..., 6г„|2. второй регистр 7 памяти на триггерах 7, 7, ..., m/i .элемент ШШ 8, счетчик 9, D-триггер 10, RS-триггер 11, вход 12 запуска устройства, информационны Выход 13, контрольный выход 14.

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

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

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

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

на его асинхронном единичном устано- 45 щественно) символов генератора 2.

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

По фронту N-ro синхроимпульса на выходе счетчика 9 формируется единичный импульс, который сбрасывает триг- гёт 11 в О и устанавливает триггеры 6 , 6,j, ..., 6, и 7, , 7, ..., первого 6 и второго 7 регистров в единичные состояния. На S-входе триггера 10 действует сигнал

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

55

где Р - целое (, 2,

т), бу

постоянный сигнал логическ го О.

логического

всех элементов НЕ 5,, J2 m/г

логического О, поэтому триггер 10 переходит в режим работы синхронного D-триггера.

Если за время между (N-m)-M и 2N-M тактовыми импульсами на выходе генератора 2 присутствуют только единичные символы, то на выходах всех сумматоров по модулю два 4, Д 4, постоянно действуют уровни О ), а на выходах

,2

1. Поэтому к моменту появления импульса на выходе счетчика 9 (импульса опроса) все г

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

Если за время между (N-m)-M и 2N-M тактовыми импульсами на выходе генератора 2 появится хотя бы один нулевой символ, а остальные символы- 0 единичные, то по фронту синхроимпульса на выходах всех сумматоров по по- (0®1 1)

и соответственно по срезу синхроим- 5 пульса все триггеры 6(, 6, 6т;-9 сбросятся в О,

дулю два группы 4, , 4, ..., явятся уровни логической 1

ры

7

Itn

7i,

тоянии о запишет в триггер

а тригге..с, 7 1 останутся в сос- Поэтому импульс опроса 10 О, следова40

тельно, на контрольном выходе 14 появится сигнал логического О и ситуация считается нормальной.

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

Р - целое (, 2,

т), будет

постоянный сигнал логического О.

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

Если за время между (N-m)-M и 2N-M тактовыми импульсами на выходе генератора 2 присутствует устойчивая меандро-инвертированная последовательность с периодом Т i 2т, то на выходе хотя бы одного сумматора по модулю два 4ц, номер k которого удовлетворяет условию

m/2+k р

Т ТТ

1лп

будет постоянньй сигнал , ( при Р четных и Aj,-l при Р нечетных)

Здесь под меандро-инвертированны- ми последовательностями понимаются последовательности, составленные из чередующихся последовательностей

г, 7 Гт-нечТ b;J и Ъ. , где Ь; j - последовательность, противоположная I ; ,l, Например, если bj| .1101011010..., то меандро-инвертированная последовательность 11010001011101000101 ..., где ь 0010100101 ...

ней

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

п . п п п

111...1 000...О 111...1 000...0...

где

,т.

то на выходе сумматора

по модулю два 4 , сдвиг б in/2+k между последовательностями (1) на входах которого кратен периоду Т. 2 П последовательности (I) (Р - четные), будет постоянно присутствовать сигнал ( или ) Если сдвиг с , кратен половине периода последовательности (1) (Р 40

Устройство для контроля генератора случайных чисел, содержащее генератор тактовых импульсов, выход которого является выходом устройства для подключения к входу Опрос контролируемого ген ератора случайных чисел, D-триггер, элемент ИЛИ, счетчик, отличающееся тем, что, с целью повьшения точности, оно содержит регистр сдвига, группу сумматоров по модулю два, группу элементов НЕ, RS-триггер, два регистра памяти, выходы разрядов которых подключены к входам.элемента ИЛИ соответственно, выход которого соединен с D-входом D-триггера, синхронизирующий вход которого объединен с установочными входами первого и второго регистров памяти и подключен к выходу счетчика, счетный вход которо- с го объединен с синхронизирующими входами первого и второго регистров памяти и регистра сдвига и подключен к выходу генератора тактовых импульсов, вход устройства подключен к вынечетные), то на выходе сумматора по модулю два 4ц будет постоянно присутствовать сигнал ( или 0@1 1) ходу контролируемого генератора, соеСледовательно, в этом случае хотя динен с информационным входом реги- бы один триггер 6к первого регистра 6 () либо хотя бы один триггер второго регистра 7 () к приходу опрашивающего импульса останет- сг ся в единичном состоянии. Поэтому на выходе 14 появится сигнал 1, т.е. зафиксируется сбой в генератора 2.

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

10

f5

0

5

30

35

40

Если за время между (N-m)-M и 2N-M тактовыми импульсами на выходе генератора 2 будет формироваться последовательность, отличающаяся от периодичности хотя бы в одном такте, то на выходах всех сумматоров по модулю два 4,, 42, ..., будет хотя

бы один перепад из 1 в О либо из

I111t

1 I

О 6

в 1. Поэтому все триггеры 6, ,

2, гп/г м 4 J rt/ Z первого и второго регистров на КЗ- триггерах к приходу импульса опроса будут в нулевых состояниях, следовательно , на выходе 14 сформируется сигнал О, что свидетельствует о нормальной работе генераторе 2.

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

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

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

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

5 . 13022746

группы подключен к входу k-ro разря-подключен к выходу переполнения счетда первого регистра памяти и входучика, а S-вход RS-триггера объединен

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

выходом КЗ-триггера, R-вход которогоD-триггера. .

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