Генератор случайных чисел

 

ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ, содержащий источник шума, выход которого соединен с информационным входом первого усилителя, выход которого соединен с D-входом D-триггера , выход которого соединен с входом второго усилителя, выход которого является выходом генератора, генератор тактовых импульсов, выход которого соединен с С-входом D-триггера и с первым входом элемента PI, регистр кода , выход которого через цифроаналоговый преобразователь соединен с управляющим входом первого усилителя, отличающийся тем, что, с целью повышения точности, он содержит реверсивный счетчик, информационный выход которого соединен с информационньм входом регистра кода, синхронизирующий вход которого объединен с входом Установка реверсивного счетчика и подключе к выходу элемента И, второй вход которого подключен к выходу переполнения реверсивного счетчика, счетный вход которого объединен с С-входом D-триггера, выход которого соединен с управляющим входом реверсивного счетчика.

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

РЕСПУБЛИК аю (и) 3Ш С 06 F 7/58!

Ъ

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

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

ЬМЬЛаОИ::ЕА (21) 3584276/18-24 (22) 22.04.83 (46) 23.07.84. Бюл. № 27 (72) А.Я. Гаршин, Л.П. Домнин, А,В. Грибанов и N.Н. Гаршина

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (53) 681.325(088.8) (56) 1. Авторское свидетельство СССР

¹ 502489, кл. Н 03 К 3/84, Н 03 В 29/00, 1974.

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

518859, кл. Н 03 В 29/00, 1974.

3. Авторское свидетельство СССР № 871!64, кл. С 06 F 7/58, Н 03 В 29/00, 1980 (прототип). (54)(57) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ, содержащий источник шума, выход которого соединен с информационным входом первого усилителя, выход которого соединен с D-входом D-триггера, выход которого соединен с входом второго усилителя, выход которого является выходом генератора, генератор тактовых импульсов, выход которого соединен с С-входом D-триггера и с первым входом элемента И, регистр кода, выход которого через цифроаналоговый преобразователь соединен с управляющим входом первого усилителя, отличающийся тем, что, с целью повышения точности, он содержит реверсивный счетчик, информационный выход которого соединен с информационным входом регистра кода, синхронизирующий вход которого объединен с входом "Установка" реверсив- Я ного счетчика и подключен к выходу элемента И, второй вход которого подключен к выходу переполнения реверсивного счетчика, счетный вход которого объединен с С-входом D-триггера, вы- О ход которогс соединен с управляющим входом реверсивного счетчика.

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

Известен генератор случайных импульсов, содержащий генератор импуль- 10 сов, источник шума, подключенный к, входу счетчика, выходы которого со. единены с дешифратором, коммутатор, управляющий вход которого соединен с выходом дешифратора, а выходы - 15 с входами установки счетчика, и управ- ляемый счетчик, счетный вход которого соединен с выходом источника шума, управляющий вход — с выходом генера-, тора импульсов, а выходы подключены 20 к входам коммутатора j1) .

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

Известен также генератор случайных чисел, содержащий последовательно соединенные источник шума, видеоуси- 4О

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

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

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

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

Е= Р - Pg, где P и Рд — вероятность появления логических сигналов "1" и "0" на выходе ГСП, то математическое ожидание числа логических сигналов "1" после появления N разрядов случайной последовательности должно иметь вид

Фактическое число логических сигналов "1", содержащихся в N разрядах случайной последовательности Я ., отличается от М,., а знак разности

N (Q .g — †) лишь с некоторой вероят2 ностью P соответствует знаку E . Вероятность того, что значение g<,g находится в интервале от (N, — Ng ) до (М„, + N ), (т.е, знак разности

N (Я,, — †) верно характеризует знак ), определяется теоремой Лапласа. Расче1104512 ты показывают, что для оценки знака Е с достоверностью 0,95 при Е1 = t0 необходимо пересчитать число единиц в 6,7 10 разрядах случайной последовательности а для случая — I0 4 в 6,7 10 разрядах. Для записи этих чисел необходимо испольэовать счетчики емкостью 16 и 23 разряда соответственно, что значительно усложняет схему ГСЧ. В известном ГСЧ 10 сигнал, поступающий на регистр коррекции, вырабатывается периодически, через интервалы времени, равные времени заполнения счетчиков. Таким образом, чем точнее требуется информа- 15 дия об отклонении от равновероятности, тем больше должна быть разрядность счетчиков, сложнее их конструкции и тем продолжительнее осуществляется процесс замера, т.е. реже корректиру- 20 ется значение равновероятности. Если принять значение тактовой частоты f

1 мГц, то время заполнения счетчиков известного ГСЧ при оценке знака (Е110 и )g) -10Г с достоверностью 25

0 95 для описанных условий составит

0,67 с и 67 с соответственно, причем эти отрезки времени не зависят от реальной величины отклонений -Е . При значительном отклонении от равновероятности случайной последовательности схема коррекции известного ГСЧ может восстановить равновероятность за несколько циклов коррекции, что требует значительных затрат времени, так как схема коррекции изменяет сигнал коррекции -эа один цикл на малую величину Г . Это ограничивает возмож-ности системы автоподстройки равновероятности случайных чисел, поскольку 40 внешние воздействующие факторы, приводящие к отклонению от равновероятности (окружающая температура, величина-питающего напряжейия, процессы старения компонентов и т.д.) изме- 45 няются с некоторой конечной скоростью вследствие чего скорость формирования сигнала .коррекции должна быть вьппе скорости указанных изменений, так как в противном случае отклонение от рав-50 новероятности случайных чисел окажется вьппе допустимой величины. Таким образом, воздействие внешних дестабилизированных факторов ограничивает разрядность счетчика единиц и форми- gg рователя кодов, что неизбежно ухудшает точность автоподстройки равновероятности случайных чисел. Увеличение точности автоподстройки в пределах указанного ограничения требует значительного увеличения емкости счетчика единиц и формирователя ко-. дов, что усложняет конструкцию и снижает ее надежность, причем дальнейшее увеличение точности автоподстройки возможно лишь при снижении быстродействия. Так, например, суммирование двух последовательных разрядов по модулю 2 приводит -к двукратному снижению быстродействия ГСЧ.

Даже при идеальной равновероятности случайных чисел сигнал коррекции в ГСЧ вырабатывается и периодически изменяет содержание регистра коррекции, что вызывает увеличение коэффициента автокоррелйции последовательности случайных чисел.

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

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

Интегральная микроэлектроника позволяет создавать ГСЧ в виде одной, или нескольких микросхем, что значительно снижает стоимость и улучшает экс-. плуатационные характеристики ГСЧ.

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

Цель изобретения — повышение быстродействия и упрощение конструкции

ГСЧ при улучшении характеристики равновероятности случайной последовательности.

Поставленная цель достигается тем, что в генератор случайных чисел, содержащий источник шума, выход которого соединен с информационным входом первого усилителя, выход которого соединен с D-входом D-триггера, выход которого соединен с входом второго усилителя, выход которого является! 104512 торов.:

Генератор содержит источник 1 шума, усилитель 2, D-триггер 3, усилитель 4, элемент 5И, регистр 6 кода, цифроаналоговый преобразователь 7, генератор 8 тактрвых импульсов, реверсивный счетчик 9.

Генератор работает следующим образом.

30.Напряжение шума, вырабатываемое источником 1 шума, усиливается усилителем 2 (фиг. 2а) и поступает на вход D-триггера с определенным порогом срабатывания. Одновременно на тактовый вход D-триггера 3 с выхода генератора 8 тактовых импульсов поступают импульсы (фиг. 2б),. по отрицательному фронту которых в D-триггер 3 записывается логический сигнал

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

15 ного счетчика, счетный вход которого объединен с С-входом D-триггера, выход которого соединен с управляющим входом реНерсивного счетчика.

На фиг. 1 приведена блок-схема генератбра; на фиг. 2 — .временные диаграммы работы генератора; на фиг.З и 4 — сравнительные характеристики параметров систем автоподстройки известного и предлагаемого генераверсивного счетчика 9 увеличивается или уменьшается на единицу н зависимости от информации, поступающей на управляющий вход ренерсивного счетчика 9 (фиг. 2г). В начальный момент в реверсивный счетчик 9 записывается

N число — где М вЂ” емкость счетчика.

В процессе работы содержимое реверсивного счетчика 9 некоторым образом меняется и в тот момент, когда н реверсивном счетчике будет содержаться число 0 или N, на выходе переполнения появится высокий уровень (фиг. 2д, время t<), а на информационном выходе — высокий или низкий уровень в зависимости от наличия М или О в реверсивном счетчике. Под воздействием высокого уровня с выхода переполнения реверсивного счетчика 9 на выходе элемента 5 И вырабатынается импульс (фиг. 2е), по переднему фронту которого увеличивается содержимое регистра 6 на единицу в том случае, если с информационного выхода реверсивного счетчика 9 на регистр 6 поступает логический сигнал О или уменьшается содержимое регистра 6 на единицу, если с информационного выхода реверсивного счетчика 9 на регистр 6 поступает логический сигнал

"1" (фиг. 2ж, время t<). По заднему фронту импульса, поступающего с выхода элемента 5 И, ренерсивный счетчик 9 устанавливается в исходное состояние, после чего на его выходе переполнения появляется низкий уровень и начинается новый цикл коррекции (фиг. 2г, е, время t >) .

Рассмотрим более подробно работу системы коррекции предлагаемого ГСЧ.

Пусть случайная последовательность на входе реверсивного счетчика 9 характеризуется некоторым отклонением от ранновероятности Г = Р4 — Р ) О.

В этом случае вероятность заполнения реверсивного счетчика 9 будет превышать вероятность его обнуления, причем вероятность того, что состояние реверсивного счетчика 9 в конце цикла коррекции будет соотнетствовать знаку Я, является вероятностью правильной оценки знака и зависит от величины (и емкости ренерсинного счетчика.

Емкость реверсивного счетчика, необходимая для оценки знака E c опредепенной достоверностью, увеличи1104512 вается с уменьшением величины Г! и с увеличением достоверности оценки.

Расчет необходимой величины емкости реверсивного счетчика производится по следующей методике. В соответствии S с формулой Стирлинга вероятность появпения тп единиц на выходе ГСП после

N.òàêòîâ равна (» -11 i дахр

Гагнр.р, (3) Расчет зависимости необходимой емкости реверсивного счетчика и вре- 4О мени цикла анализа от величины с для вероятности правильной оценки P

0,95 производится на 3ВМ. На фиг.3 показаны зависимости необходимого числа N двоичных разрядов счетчика

45 в блоке коррекции от величины откло.нения от равновероятности )El для известного ГСЧ (кривая А) и для предла. гаемого ГСЧ (кривая Б), а на фиг. 4 зависимость времени, необходимого на один шаг цикла коррекции при тактовой частоте f = 1 мГц, от величины отклонения от равновероятности !Е! для известного ГСЧ (кривая AI), и для предлагаемого ГСЧ (кривая Б ). SS

Приведенные на фиг. 3 и 4 сравнительные характеристики параметров систем автоподстройки показывают, что для

Если в формуле (3) принять m = — «+ L ! „ где Ь вЂ” емкость реверсивного счетчиР ка, то величина РшИ будет выражать вероятность заполнения .реверсивного счетчика на М-ом такте случайной последовательности. Вероятность заполнения реверсивного счетчика после N тактов случайной последовательности будет равна сумме вероятностей заполнения его во всех предшествующих тактах. При этом следует учесть, что вероятность заполнения реверсивного счетчика на N -ом такте равна произведению вероятностей собственно заполнения счетчика, умноженному на вероятность того, что счетчик не будет заполнен во всех предшествующих тактах.. Принцип расчета необходимой величины емкости реверсивного счетчи ка заключается в последовательном суммировании вероятностей заполнения реверсивного счетчика вообще и его

35 заполнения, при котором содержимое соответствует знаку Г (F(= 10 >— - 10 4 и вероятности пра— вильного решения в цикле коррекции

P = 0,95 необходимая емкость двоичного счетчика известного ГСЧ, выраженная в числе двоичных разрядов, должна в 3,5 раза превышать емкость реверсивного счетчика предлагаемого

ГСЧ, а время, затрачиваемое на один шаг цикла коррекции в известном ГСЧ, в 4,5 раза больше времени, необходимого для той же Операции в предла.гаемом ГСЧ.

Технические преимущества ГСЧ заключаются в том, что в 3,5-кратное уменьшение емкости реверсивного счет чика позволяет во столько же раэ упростить схему коррекции, что имеет большое практическое значение, поскольку именно схема коррекции определяет сложность схемы всего

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

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

Ет = 1 мГц необходимая длительность цикла анализа для поддержания величины Е!4 1О составляет для известного

ГСЧ 67 с, а для предлагаемого ГСЧ 15 с.

Если по каким-либо причинам величина EI скачкообразно изменится до 10

1104512

Фиг.1 то длительность цикла анализа в предлагаемом ГСЧ уменьшится до 6,6 с, тогда как в известном ГСЧ она останется неизменной.

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

11945)

Фиг.2

1104512

СОК

ФигЯ

ВНИИПИ Заказ 5261/35 Тирам 699 Подписное

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