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

 

(iI) 590754

Са3оз Советских

Са(1иалистических

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 05.02.76 (21) 2322247/18-24 с присоединением заявки ¹ (23) Приоритет (43) Опубликовано 30.01.78. Бюллетень № 4 (45) Дата опубликования описания 07.03.78 (51) М. Кл 6 06Г 15/36

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

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

В. М. Захаров, Ю. С. Комаров, Н. В. Одринский и Ф. И, Салимов

Казанский ордена Трудового Красного Знамени государственный университет имени В. И. Ульянова-Ленина (71) Заявитель (54) УСТРОЙСТВО ДЛЯ АНАЛ ИЗА ВЕРОЯТНОСТНЫХ

ХАРАКТЕРИСТИК ДАТЧИКА СЛУЧАЙНЫХ ЧИСЕЛ

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

Известны устройства для анализа вероятности характеристик дят п1ка случайиь1х чисел.

Одно пз известных устройств для япалпзя вероятности характеристик датчика случайных п1сс л содер>кит счетчики, дешифратор, блок сравнения, триггер, усилитель, блок задержки, вентили, элемент III . Однако это устройство IIMccT псвысоку10 To lllocTI (1), Другое пз известных устройств для япялпза вероятиостных характеристик датчика случайных чисел так>ке содержит счетчики, блок сравнения, блок задержки, вентили. Для повышения точности устройство, кроме того, содер>кит генератор импульсов, коммутатор, мультивибратор, элемент ИЛИ и дпфферепцирующую цепь. Однако это устройство имеет малый диапазон проверяемых случайнь1х чисел (2).

Наиболее близким техническим решением к данному изобретению является устройство для анализа вероятностных характеристик датчика случайных чисел, содержащее индикатор, первый вход которого подключен к выходу блока управления, а второй вход — квыходу блока сравнения, первая группа входов которого соединена с выходами коммутатора соответственно, первая группа входов котороГо является входямп устройства (3).

Недостатком этого устройства является ппзкос быстродействие.

11,елью изобретения является повышение быстродействия.

Для достижения поставленной цели устройство содержит первый и второй регистры nai»IITll, входы которых соединены с выходом

1() блока управления, а выходы — — со вторыми группами входов коммутатора п блока сравIII. ппя соответственно.

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

15 Устройство содержит блок управления 1, датчик случайных чисел ДСЧ 2, первый регистр памяти 3, выходы которого соединены со входамп коммутатора 4, другие входы которого соединены с выходамп датчика слу20 IBIIllilx чисел 2, а выходы — со входами блока сравнения 5, другие входы которого соединены с выходамп второго регистра памяти 6, выход которого соединен со входом индикатора 7, другой вход которого соединен со вхо25 дом второго регистра памяти 6 п с выходом блока управления 1.

Регистр памяти 3 представляет собой триггерный регистр, служащий для хранения двоичного числа. Коммутатор 4 является сумма590754 тором IIo модул1о 2 с прямыми и инверсными выходамп в каждом разряде. Коммутатор служит для выбора заданной группы (заданного сочетания) двоичных комбинаций (наборов), поступающих с выхода ДСЧ. При фиксирова IHQ vI числе наборов в группе максимальное число неповторяющихся сочетаний равно, 2, где и — число разрядов ДСЧ. Зта величина определястся тем, что каждому числу, записанному в регистр 3, соответствует одно сочетание.

Блок сравнения 5 служит для изменения числа комбинаций в группе. Число комбинаций в группе можно менять от 0 до 2" — 1.

Регистр памяти 6 служит для хранения заданного числа проверяемых комбинаций.

Индикатор 7 служит для фиксации вероятности появления заданной группы комбинаций. В простейшем случае он может состоять из двух счетчиков: счетчика общего числа обращений к ДСЧ и счетчика числа появлений заданной группы.

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

В регистр памяти 3 записывается число, определяющее проверяемую группу комбинаций.

В регистр 6 записывается число, задающее количество комбинаций в группе.

При подаче синхронизирующих импульсов с выхода датчика случайных чисел на коммутатор поступает случайная последовательность двоичных наборов (комбинаций). Коммутатор, суммируя эту последовательность по модулю

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

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

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

000, 001, 010, 011, 100, 101, 110, 111.

Покажем как можно менять (задавать) число проверяемых комбинаций. Число проверяемых комбинаций определяется двоичным набором, записанным в регистр 6. Для понимания работы блока сравнения предположим, что двоичные наборы с выхода датчика поступают непосредственно на блок сравнения.

Пусть число проверяемых комбинаций равно единице. Запишем двоичное представление этого числа — 001 в регистр 6. Тогда на выходе преобразователя (исходя из логики соединения элементов преобразователя) высокий (единичный) потенциал будет появляться только при поступлении на сго вход набора

001.

Пусть число проверяемых комбинаций f)3Hно двум. Запишем двоичное представлени»

5 этого числа — 010 в регистр 6. Тогда на выходе преобразователя единичный потенциал будет появляться лишь при поступлении на его вход двух наборов — 010 и 001.

То есть схема блока сравнения такова, что

10 при записи в регистр 6 двоичного числа блок сравнения 5 «пропускает» на свой выход число определенных наборов, равное числу, записанному в регистр 6.

Рассмотрим как с помощью коммутатора

15 можно менять вид «пропускаемых» наборов при их фиксированном числе, т. е. как можно

«пропускать» требуемое сочетание наборов с выходов датчика через блок сравнения 5.

Обозначим наборы на выходе ДСЧ через

20 (> « а, ), а наборы, записываемые в регистр 3 через (8, I3, >. Тогда в связи с тем, что коммутатор является сумматором по модулю 2, каждому из восьми наборов (а, а, а,) можно сопоставить на вы25 ходе коммутатора набор, а a) (8i 2 1з)

Содержимое регистра 3

Наборы на выходе коммутатора

Наборы на выходе ДС 1

40 1. 000

001

011

101

111

001

011

101

111

001

011

101

111

2. 001

001

011

101

111

110

55 8. 111

001

011

101

111

111

101

011

001

000

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

2" (z (+,), с = 7, г, где знак () означает суммирование по модулю 2.

Работу коммутатора можно пояснить табл и цей с о от ветств и я.

590754 выходе датчш<а в зависимости от содержи)мого регистра 3. Например, пусть в регистре 6 находится н)сло 01 1 (двоич!!Ос ирсдс !)в. )синс десяти шого числа 3). В этом случае преобразователь с выхода коммутатора будет

«пропускать» иа свой выход l îëüêî следующих три набора: 001, 010, 011, Тогда, если в регистр 3 запишем число 000, то наборы с выхода датчика пройдут на выход коммутатора без перскодировки и ирoBcp c.;Еос со )с)аш)с будет иметь вид 001, О!О, 011. Если ке в регистр G запишем число l i l, то в этом случае наборам 001, 010, 011, поступающим с выхода коммутатора соответстгует (как это видно из табл"щы) проверяемое сочетание вида 110, 101, 100.

Таким образом, сели блок cpBBIicIII!rT 5 «настроен» FIB «пропуск» определенной группы наборов, то меняя содержимое регистра 3, можно проверить заданиос число комбинаций, появляющихся на выходе датчика в различIlBI Y сочетан1)ях.

Если датчик выдает случайпу)о последовательность, идеально cooTBcтствующую равномерному распределсишо, то вероятность появления группы наборов будет одна и та же для любого сочетания íc!)opoB в этой группе. В том случае, когда случайиыс числа име)от корреляционную связь, то для каждого сочетания вероятность будет различна.

Подсчитывая общее число обрашсний к датчику (за фиксированное время) и число появлений заданного сочетания наборов можно оценить качество случайной последовательности, в частности по известной формуле где о — среднее квадрати шос отклонение, пг — число пояьлений заданного счстания наборов, Л вЂ” общее число обращений к датчику.

Дн5! более надежно)! оцс:)ки соотьстстни5! результата эксперимента предполагаемому

pас!1рсдслсиию . )Ожно ис))о l! BQB;)Tь критсрlll! согл асi 5I /

5 В данном случае из 2" воз))ожн),)х сочеташш необходимо выбрать 8 — 10 таки.;, которые отличаются друг от друга всеми наборами.

Число наборов в сочетаниях должно быть примерно одинаково, причем суммарное чис10 ло наборов во всех сочетаниях должно быть равно 2". При соответствующей разрядности

ДСЧ такой Bhl6op Bccl J,B тем подбора оп)редслени!.)х висел в регистры

3»6.

Формула изобрстсция

Устройство для анализа вероятностных ха20 рактеристик датчика слу IBéI!ûY чисел, содержащее индикатор, первьш вход которого подкл)очсп к выходу блока управления, а второй вход — к выходу блока сравнения, первая группа входов которого соединена с выхода:,ш коммутатора соответственно, первая группа входов которого янлястся входами устройства, о тл и ч а ю щ е с с я тем, что, с целью повышения быстродействия ) cTpo!lcTB3> содержит первый и второй регистры памяти, входы которы.: соединены с выходом блока управлс)шя, а выходы — с вторыми группами входов ко)!))утатора и блока срависIIIIFI соOTBCTCTBCkIIIO.

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

1. Лвторскос свидетельство СССР ¹ 235398, кл. С) 06Г 11/00, 1967.

2. Лвторскoc свидетельство СССР ¹ 236851, кл. G 06Е 1/02, 1967.

3. Авторское ггидетельство СССР № 262497, кл. G 06Г 11/00, 1968.

590754

Составитель Э. Сечина

Редактор P. Киселева Техред А. Камышникова Корректоры: Т. Добровольская и О. Тюрина

Подписное

Заказ 3262/3 Изд. № 174 Тираж 818

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

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

Типография, пр. Сапунова, 2