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

4; :л Изобретение относится к специализированной вычислительной технике, в частности к вычислительным системам с вероятностным представлением информации, и может быть испольэовано в качестве машинных переменных в устройствах обработки параметров случайных процессов. Известен генератор случайных импульсов, содержащий генератор импуль сов, источник шума, подключенный к. входу счетчика, выходы которого соединены с дешифратором, коммутатор, управляющий вход которого соединен с выходом дешифратора, а выходы с входами установки счетчика, и упра ляемый счетчик, счетньй вход которог соединен с выходом источника шума, управляющий вход - с выходом генератора импульсов, а выходы подключены к входам коммутатора lj . Недостаток данного генератора заключается в том, что принцип стабили зации интенсивности выходных импульсов в нем основан на автоматическом уменьшении интенсивности до некоторо го минимального значения, что неизбежно приводит к уменьшению быстродействия. Кроме того, данные устройства не обеспечивают равновероятност ногр закона распределения и не могут быть реализованы по интегральной тех нологии вследствие наличия реактивных элементов. Известные устройства имеют большой уровень потребляемой мощности и низкую эксгшуатационную надежность. Известен также генератор случайны чисел, содержащий последовательно Соединенные источник шума, видеоусилитель и запоминающее устройство, последовательно соединенные формирователь кодов и формирователь импульсов, а также генератор стробирующих импульсов, преобразователь напряжения в. частоту, формирователь чисел и усилитель мощности 2j , . Известное устройство имеет низкую эксплуатационную надежность, низкое быстродействие, не обеспечивает равновероятностного закона распределения чисел и не может быть реализовано по интегральной технологии вследствие наличия реактивных элементов. Наиболее близким к предлагаемому по технической сущности и достигаемому положительному эффекту является генератор случайных чисел, содержащий последовательно соединенные источник шума, видеоусилитель и запоминающее устройство, последовательно соединенные формирователь кодов и формирователь импульсов, а также генератор стробирующих импульсов, усилитель мощности и последовательно соединенные элемент И, счетчик единиц, регистр коррекции и цифроаналоговый преобразователь, при этом информационный вход элемента И подключен к выходу запоминающего устройства и входу усилителя мощности, выход формирователя импульсов подключен к входам начальной установки формирователя кодов и счетчика единиц и к информационному входу регистра коррекции, а выход генератора стробируюш 1х импульсов соединен со счетным входом формирователя кодов и с тактовым входом запоминающего устройства з. В известном устройстве точность анализа равновероятности случайных чисел, поступающихс выхода генератора, и точность поддержания их равновероятности пропорциональны разрядности счетчика единиц и формирователя . Так, если случайная последовательность на выходе генератора случайной последовательности (ГСП) характеризуется некоторым отклонением от равновероятностие PI- РО, (1) где Р и РО - вероятность появления логических сигналов 1 и О на выходе ГСП, то математическое ожидание числа логических сигналов 1 после появления N разрядов случайной последовательности должно иметь вид М,., f (1 +f), Фактическое число логических сигналов 1, содержащихся в N разрядах случайной последовательности Q,), отличается от М , а знак разности (Q(.f( - ) лишь с некоторой вероятностью Р соответствует знаку € . Вероятность того, что значение Q. находится в интервале от (М. ц - N ) до (М, ц+ Ng), (т.е. знак разности N (Qvv т) верно характеризует знак ), определяется теоремой Лапласа. Расчеты показывают, что для оценки знака с достоверностью 0,95 при jEl 1СГ необходимо пересчитать число единиц в 6,710 разрядах случайной последовательности, а для случая IEI 1(Г в 6,740 разрядах. Для записи этих чисел необходимо использовать счетчики емкостью 16 и 23 разряда соответственно, что значительно усложняет схему ГСЧ. В известном ГСЧ сигнал, поступающий на регистр коррекции, вьфабатывается периодически, через интервалы времени, равные времени заполнения счетчиков. Таким образом, чем точнее требуется информация об отклонении от равновероятности, тем больше должна быть разрядност счетчиков, сложнее их конструкции и тем продолжительнее осуществляется процесс замера, т.е. реже корректируется значение равновероятности. Если принять значение тактовой частоты ff 1 мГц, то время заполнения счетчиков известного ГСЧ при оценке знака ( и|Е)-10 с достоверностью 0,95 для описанных условий составит 0,67 с и 67 с соответственно, причем эти отрезки времени не зависят от реальной величины отклонений-. При значительном отклонении от равновероятности случайной последовательност схема коррекции известного ГСЧ может восстановить равновероятность за несколько циклов коррекции, что требует значительных затрат времени, так как схема коррекции изменяет сигнал коррекции за один цикл на малую величину S . Это ограничивает возможности системы автоподстройки равновероятности случайных чисел, поскольку внешние воздействующие факторы, приводящие к отклонению от равновероятности (окружающая температура, величина питающего напряжения, процессы старения компонентов и т.д.) изменяются с некоторой конечной скоростью вследствие чего скорость формировани сигнала коррекции должна быть вьте скорости указанных изменений, так ка в противном случае отклонение, от рав новероятности случайных чисел окажет ся вьш1е допустимой величины. Таким образом, воздействие внешних дестабилизированных факторов ограничивает разрядность счетчика единиц и формирователя кодов, что неизбежно ухудшает точность авт оподстройки равновероятности случайных чисел. Увели112, 4 чение точности автоподстройки в пределах указанного ограничения требует значительного увеличения емкости счетчика единиц и формирователя кодов, что усложняет конструкцию и снижает ее надежность, причем дальнейшее увеличение точности автоподстройки возможно лишь при снижении быстродействия. Так, например, суммирование двух последовательных разрядов по модулю 2 приводит -к двукратному снижению быстродействия ГСЧ. Даже при идеальной равновероятности случайных чисел сигнал коррекции в ГСЧ вырабатывается и периодически изменяет содержание регистра коррекции, что вызывает увеличение коэффициента автокорреляции последовательности случайных чисел. Для построения сложных вероятностных автоматов, например стохастических вьмислительных устройств, используются многоканальные или многоразрядные ГСЧ, причем наибольшим быстродействием обладают ГСЧ, которых каждый разряд случайного двоичного числа формируется отдельным генератором случайной двоичной последовательности (ГСП) Интегральная микроэлектроника позволяет создавать ГСЧ в виде одной, или нескольких микросхем, что значительно снижает стоимость и улучшает эксплуатационные характеристики ГСЧ. При этом наиболее сложным и занимающим наибольшую часть площади кристалла микросхемы является блок автоподстройки равновероятности случайных чисел. Наиболее эффективным представляется использование в ГСЧ одного блока автоподстройки с несколькими ГСП таким образом, чтобы коррекция равновероятности всех ГСП производилась поочередно с высоким быстродействием, что практически несуществимо в известном ГСЧ. Цель изобретения - повышение быстродействия и упрощение конструкции ГСЧ при улучшении характеристики равновероятности случайной последовательности. Поставленная цель достигается тем, что в генератор случайных чисел, содержащий источник шума, выход которого соединен с информационным входом первого усилителя, выход которого со единен с D-входом D-триггера, выход которого соединен с входом второго усилителя, выход которого является

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

На фиг. 1 приведена блок-схема генератора; на фиг, 2 - .временные диаграммы работы генератора; на фиг.3 и А - сравнительные характеристики параметров систем автоподстройки известного и предлагаемого генераторов .

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

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

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

N - емкость счетчика.

число -Г-, где

В процессе работы содержимое реверсивного счетчика 9 некоторым образом меняется и в тот момент, когда в реверсивном счетчике будет содержаться число О или N, на выходе переполнения появится высокий уровень (фиг. 2д, время t), а на информационном выходе - высокий или низкий уровень в зависимости от наличия N или О в реверсивном счетчике. Под воздействием высокого уровня с выхода переполнения реверсивного счетчика 9 на выходе элемента 5 И вырабатывается импульс (фиг. 2е), по переднему фронту которого увеличивается содержимое регистра 6 на единицу в том случае, если С информационного выхода реверсивного счетчика 9 на реГистр 6 поступает логический сигнал или уменьшается содержимое регистра на единицу, если с информационного выхода реверсивного счетчика 9 на регистр 6 поступает логический сигнал 1 (фиг. 2ж, время . По заднему фронту импульса, поступающего с выхода элемента 5 И, реверсивный счетчик 9 устанавливается в исходное состояние, после чего на его выходе переполнения появляется низкий уровень и начинается новый цикл коррекции (фиг. 2г, е, время to).

Рассмотрим более подробно работу системы коррекции предлагаемого ГСЧ. Пусть случайная последовательность на входе реверсивного счетчика 9 характеризуется некоторым отклонением от равновероятности f Р - РО ОВ этом случае вероятность заполнения реверсивного счетчика 9 будет превышать вероятность его обнуления, причем вероятность того, что состояние реверсивного счетчика 9 в конце цикла коррекции будет соответствовать знаку Е , является вероятностью правильной оценки знака и зависит от величины |t( и емкости реверсивного счетчика.

Емкость реверсивного счетчика, необходимая для оценки знака с определенной достоверностью, увеличивается с уменьшением величины и с увеличением достоверности оценки Расчет необходимой величины емкости реверсивного счетчика производится по следующей методике. В соответстви с формулой Стирлинга вероятность появления m единиц на выходе ГСП после N. тактов равна -(m-Npi1 2NPoP, л12мМр„р, Если в формуле (3) принять m емкость реверсивного счетчи величина будет выражать вероятность заполнения реверсивного счетчика на N-OM такте случайной последовательности. Вероятность заполнения реверсивного счетчика после N .тактов случайной последовательности будет равна сумме вероятностей запол нения его во всех предшествующих так тах. При этом следует учесть, что вероятность заполнения реверсивного счетчика на Nj-ом такте равна произведению вероятностей собственно запо нения счетчика, умноженному на вероятность того, что счетчик не будет заполнен во всех предшествуюш 1х тактах.. Принцип расчета необходимой величины емкости реверсивного счетчи ка заключается в последовательном суммировании вероятностей заполнения реверсивного счетчика вообще и его заполнения, при котором содержимое соответствует знаку € . Расчет зависимости необходимой емкости реверсивного счетчика и времени цикла анализа от величины 6 для вероятности правильной оценки Р 0,95 производится на ЭВМ. На фиг.З показаны зависимости необходимого числа N двоичных разрядов счетчика в блоке коррекции от величины отклонения от равновероятности для известного ГСЧ (кривая А) и для предла гаемого ГСЧ (кривая Б), а на фиг. 4 зависимость времени, необходимого на один шаг цикла коррекции при тактовой частоте f 1 мГц, от величины отклонения от равновероятности б1 для известного ГСЧ (кривая А,), и для предлагаемого ГСЧ (кривая Б). Приведенные на фиг. 3 и А сравнитель ные характеристики параметров систем автоподстройки показывают, что для 1 - 10 и вероятности правильного решения в цикле коррекции Р 0,95 необходимая емкость лвоичного счетчика известного ГСЧ, вьфаженная в числе двоичных разрядов, должна в 3,5 раза превышать емкость реверсивного счетчика предлагаемого ГСЧ, а время, затрачиваемое на один шаг цикла коррекции в известном ГСЧ, в 4,5 раза больше времени, необходимого для той же Операции в предлагаемом ГСЧ. Технические преимущества ГСЧ заключаются в том, что в 3,5-кратное уменьшение емкости реверсивного счет чика позволяет во столько же раз упростить схему коррекции, что имеет большое практи 1еское значение, поскольку именно схема коррекции определяет сложность схемы всего ГСЧ, его надежность, быстродействие и другие тактико-технические показатели. 4,5-кратное сокращение времени, затрачиваемого на один шаг цикла анализа, позволяет обеспечить работумногоразрядного ГСЧ таким образом, чтобы одна коррекция обслуживала поочередно несколько генераторов случайной последовательности (ГСП) безухудшения параметров случайной последовательности, а также значительно снизить влияние внешних дестабилизирующих факторов на равновероятность случайной последовательности. Преимуществом предлагаемого ГСЧ является то, что при фиксированной емкости реверсивного счетчика время анализа уменьшается с ростом величины 6 . Это позволяет значительно сократить время, необходимое на восстановление требуемой равновероятности при резком отклонении вследствие воздействия внешних дестабилизирующих факторов. Так, в известном ГСЧ время одного цикла анализа зависит только от емкости счетчика единиц и формирователя кодов. При резком скачкообразном отклонении от равновероятности выходной случайной последовательности необходимое на,восстановление равновероятности время может достигать значительной величины. Например, при f-r 1 мГц необходимая длительность цикла анализа для поддержания величины1€1 10 составляет для известного ГСЧ 67 с, а для предлагаемого ГСЧ 15 с. Если по каким-либо причинам величина скачкообразно изменится до Ю.

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

Применение предлагаемого ГСЧ в вычислительных устройствах с вероятност

110451210

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

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

Фиг1

а

,/

I I I

I

м- I 1

ш

3

Н

ii tz t3

/

Фиг, 2

50 ЦО W20- Ю

г-ю

-.т/Г 5

5-ю

Фиг.З

Ю