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

(46) 23.07.84, Бю ра, выход которого соединен с входом второго усилителя, выход которого является выходом генератора, генератор тактовых импульсов, выход которого соединен с С-входом П-триггера и с первым входом элемента И, регистр кода, выход которого через цифроаналоговый преобразователь соединен с управляющим входом первого усилителя, о т л и ч а ю щ и й с я тем, что, с целью повышения точности, он соержит реверсивный счетчик, информаионный выход которого соединен с информационным входом регистра кода, синхронизирующий вход которого объединен с входом "Установка" реверсивного счетчика и подключен к выходу элемента И, второй вход которого подключен к выходу переполнения реверсив ного счетчика, счетный вход которого объединен с С-входом Э-триггера, выход которогс соединен с управляющим входом реверсивного счетчика. У 2(57 ГЕНЕРАТОР Сй источник АИНЫХ ЧИСЕЛ,а, выход комационным с одержащи торого со входом пе единен с и ля, выход коодом 0-триггевого усилидинен с Прог ЗВ) С 06 Р 7/58ОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙОПИСАНИЕ ИЗОБРЕТЕНИЯ. Изобретение относится к специализированной вычислительной технике, в частности к вычислительным системам с вероятностным представлениеминформации, и может быть использовано в качестве машинных переменныхв устройствах обработки параметровслучайных процессов,Известен генератор случайных импульсов, содержащий генератор импуль Осов, источник шума, подключенный к,входу счетчика, выходы которого со. единены с дешифратором, коммутатор,управляющий вход которого соединенс выходом дешифратора, а выходы - 15с входами установки счетчика, и управ-ляемый счетчик, счетный вход которогосоединен с выходом источника шума,управляющий вход - с выходом генера-,тора импульсов, а выходы подключены 20к входам коммутатора И .Недостаток данного генератора заключается в том, что принцип стабилизации интенсивности выходных импульсов в нем основан на автоматическом 25уменьшении интенсивности до некоторо го минимального значения, что неизбежно приводит к уменьшению быстродействия,. Кроме того, данные устройства не обеспечивают равновероятност- ЗО ного закона распределения и не могут быть реализованы по интегральной тех.нологии вследствие наличия реактивных элементов. Известные устройства имеют большой уровень потребляемой мощности и низкую эксплуатационную надежность.Известен также генератор случайных чисел, содержащий последовательно соединенные источник шума, видеоуси О литель и запоминающее устройство, последовательно соединенные форМирователь кодов и формирователь импульсов, а .также генератор стробирующих импульсов, преобразователь напряже ния в частоту, формирователь чисел и усилитель мощности 121Известное устройство имеет низкую эксплуатационную надежность, низкое быстродействие, не обеспечивает равновероятностного закона распределения чисел и не может быть реализовано по интегральной технологии вследствие наличия реактивных элементов.Наиболее близким к предлагаемому 55по технической сущности и достигаемому положительному эффекту является генератор случайных чисел, содержащий последовательно соединенные источник шума, видеоусилитель и запоминающее устройство, последовательно соединенные формирователь кодов и формирователь импульсов, а также генератор стробирующих импульсов, усилитель мощности и последовательно соединенные элемент И, счетчик единиц, регистр коррекции и цифроаналоговый преобразователь, при этом информационный вход элемента И подключен к выходу запоминающего устройства и входу усилителя мощности, выход формирователя импульсов подключен к входам начальной установки формирователя кодов и счетчика единиц и к информационному входу регист. ра коррекции, а выход генератора стро бирующих импульсов соединен со счетным входом формирователя кодов и с тактовым входом запоминающего устройства 3 .В известном устройстве точность анализа равновероятности случайных чисел, поступающих с выхода генератора, и точность поддержания их равно- вероятности пропорциональны разрядности счетчика единиц и формирователя коров. Так, если случайная последовательность на выходе генератора случайной последовательности (ГСП) характеризуется некоторым отклонением от равновероятностиЕ= Р 1 - Ро,где Р и Рд - вероятность появления логических сигналов "1" и "0" на выходе ГСП, то математическое ожидание числа логических сигналов "1" после появления И разрядов случайной последовательности должно иметь видМ, = - (1+Г),И(2) Фактическое число логических сигналов "1", содержащихся в И разрядах случайной последовательности Я отличается от М 1,1 а знак разностиИ(Я. - в ) лишь с некоторой вероят 2ностью Р соответствует знаку с . Вероятность того, что значение Я 1, находится в интервале от (М, - Я ) до (М,+ М), (т.е, знак разностиИЯ - в ) верно характеризует знак С ), определяется теоремой Лапласа. Расчеты показывают, что для оценки знака Е с достоверностью 0,95 при Е 1 =10 необходимо пересчитать число единиц в 6,7 ф 10 разрядах случайной последовательности а для случая 6 ф 10 4 в 6,710 разрядах. Для записи этих чисел необходимо испольэовать счетчики емкостью 16 и 23 разряда соответственно, что значительно усложняет схему ГСЧ, В известном ГСЧ 10 сигнал, поступающий на регистр коррекции, вырабатывается периодически, через интервалы времени, равные времени заполнения счетчиков. Таким образом, чем точнее требуется информа дия об отклонении от равновероятности, тем больше должна быть разрядность счетчиков, сложнее их конструкции и тем продолжительнее осуществляется процесс замера, т.е. реже корректиру ется значение равновероятности. Если принять значение тактовой частоты Г.=1 мГц, то время заполнения счетчиков известного ГСЧ при оценке знака Е 1 - 10и 11 =10 с достоверностью 2540,95 для описанных условий составит 0,67 с и 67 с соответственно, причем эти отрезки времени не зависят от реальной величины отклонений -Е . При значительном отклонении от равновероятности случайной последовательности схема коррекции известного ГСЧ может восстановить равновероятность за несколько циклов коррекции, что требует значительных затрат времени, так как схема. коррекции изменяет сигнал коррекции эа один цикл на малую величину Г . Это ограничивает возможности системы автоподстройки равновероятности случайных чисел, поскольку 40 внешние воздействующие факторы, при- водящие к отклонению от равновероятности (окружающая температура, величина питающего напряжейия, процессы "старения" компонентов и т.д.) изме- п 5 няются с некоторой конечной скоростью вследствие чего скорость формирования сигнала коррекции должна быть вьппе скорости указанных изменений, так как в противном случае отклонение от равновероятности случайных чисел окажется вьппе допустимой величины. Таким образом, воздействие внешних деста. билизированных факторов ограничивает разрядность счетчика единиц и форми рователя кодов, что неизбежно ухудшает точность автоподстройки равно- вероятности случайных чисел. Увеличение точности автоподстройки в пределах указанного ограничения требует значительного увеличения емкости счетчика единиц и формирователя ко-. дов, что усложняет конструкцию и снижает ее надежность, причем дальнейшее увеличение точности автоподстройки возможно лишь при снижении быстродействия. Так, например, суммирование двух последовательных разрядов по модулю 2 приводит к двукратному снижению быстродействия ГСЧ. Даже при идеальной равновероятности случайных чисел сигнал коррекции в ГСЧ вырабатывается и периодически изменяет содержание регистра коррекции, что вызывает увеличение коэффициента автокоррелйции последовательности случайных чисел.Для построения сложных вероятностных автоматов, например стохастических вычислительных устройств, используются многоканальные или многоразрядные ГСЧ, причем наибольшим быстродействием обладают ГСЧ, которых каждый разряд случайного двоичного числа формируется отдельным генератором случайной двоичной последовательности (ГСП) Интегральная микроэлектроника позволяет создавать ГСЧ ввиде одной, или нескольких микросхем, что значительно снижает стоимость и улучшает экс-. плуатационные характеристики ГСЧ. При этом наиболее сложным и занимающим наибольшую часть площади кристал. ла микросхемы является блок автоподстройки равновероятности случайных чисел. Наиболее эффективным представляется испол зование в ГСЧ одного блока автоподстройки с несколькими ГСП таким образом, чтобы коррекция равновероятности всех ГСП производилась поочередно с высоким быстродействием, что практически несуществимо в известном ГСЧ.Цель изобретения - повышение быстродействия и упрощение конструкции ГСЧ при улучшении характеристики равновероятности случайной последовательности.Поставленная цель достигается тем, что вгенератор случайных чисел, содержащий источник шума, выход которого соединен с информационным входом первого усилителя, выход которого соединен с 0-входом Р-триггера, выход которого соединен с входом второго усилителя, выход которого являетсяторов.Генератор содержит источник 1 шума, усилитель 2, Л-триггер 3, усилитель 4, элемент 5 И, регистр 6 кода,цифроаналоговый преобразователь 7,генератор 8 тактрвых импульсов, реверсивный счетчик 9.Генератор работает следующим образом,30 Напряжение шума, вырабатываемое источником 1 шума, усиливается усилителем 2 (фиг, 2 а) и поступает на вход 0-триггера с определенным порогом срабатывания. Одновременно на тактовый вход В-триггера 3 с выхода генератора 8 тактовых импульсов поступают импульсы (фиг. 2 б),. по отрицательному фронту которых в О-триггер 3 записывается логический сигнал "1", если напряжение шума в данный момент превысило пороговое значение или логический сигнал "О" (фиг, 2 в), если напряжение шума не достигло порогового значения, Двоичная информация с выхода О-триггера 3 через усилитель 4 поступает на выход. Одновременно двоичная информация с выхода 0-триггера 3 поступает на управляющий вход реверсивного счетчика 9, На тактовый вход реверсивного 55 счетчика 9 с выхода генератора 8 тактовых импульсов поступают импульсы, под действием которых содержимое ревыходом генератора, генератор тактовых импульсов, выход которого соединен с С-нходом Р-триггера и с первым входом элемента И, регистр кода, выход которого через цифроаналоговый 5 преобразователь соединен с управляющим входом первого усилителя, введен реверсивный счетчик, информационный выход которого соединен с информационным входом регистра кода, син 10 хронизирующий вход которого объединен с входом установка" реверсивного счетчика и подключен к выходу элемента И, второй вход которого подключен к выходу переполнения ренерсив15 ного счетчика, счетный вход которого объединен с С-входом Р-триггера, выход которого соединен с управляющим входом реНерсивного счетчика,На фиг. 1 приведена блок-схема генератора; на фиг. 2 - временные диаграммы работы генератора; на фиг.3 и 4 - сравнительные характеристики параметров систем автоподстройки известного и предлагаемого генераверсивного счетчика 9 увеличивается или уменьшается на единицу н зависимости от информации, поступающей на управляющий вход ренерсивного счетчика 9 (фиг. 2 г). В начальный момент в реверсивный счетчик 9 записываетсяИчисло - где М - емкость счетчика.2 УВ процессе работы содержимое реверсивного счетчика 9 некоторым образом меняется и в тот момент, когда н реверсивном счетчике будет содержаться число О или М, на выходе переполнения появится высокий уровень (фиг. 2 д, время ), а на информационном выходе - высокий или низкий уровень в зависимости от наличия М или О в реверсивном счетчике. Под воздействием высокого уровня с выхода переполнения реверсивного счетчика 9 на выходе элемента 5 И вырабатынается импульс (фиг. 2 е), по переднему фронту которого увеличивается содержимое регистра 6 на единицу в том случае, если с информационного выхода реверсивного счетчика 9 на регистр 6 поступает логический сигнал О или уменьшается содержимое регистра 6 на единицу, если с информационного выхода реверсивного счетчика 9 на регистр 6 поступает логический сигнал "1" (фиг, 2 ж, время С), По заднему фронту импульса, поступающего с выхода элемента 5 И, ренерсивный счетчик 9 устанавливается в исходное состояние, после чего на его выходе переполнения появляется низкий уровень и начинается новый цикл коррекции (фиг. 2 г, е, время 1 3).Рассмотрим более подробно работу системы коррекции предлагаемого ГСЧ. Пусть случайная последовательность на входе реверсивного счетчика 9 характеризуется некоторым отклонением от ранновероятности Г = Р 4 - Р ) О. В этом случае вероятность заполнения реверсивного счетчика 9 будет превышать вероятность его обнуления, причем вероятность того, что состояние реверсивного счетчика 9 в конце цикла коррекции будет соотнетствовать знаку Г, является вероятностью правильной оценки знака Е и зависит от величиныи емкости ренерсинного счетчика.Емкость реверсивного счетчика, необходимая для оценки знака Е с определенной достоверностью, увеличивается с уменьшением величины Ги с увеличением достоверности оценки.Расчет необходимой величины емкостиреверсивного счетчика производитсяпо следующей методике. В соответствии 5с формулой Стирлинга вероятность появления тп единиц на выходе ГСП послеИ.тактов равна(3) Расчет зависимости необходимой емкости реверсивного счетчика и вре мени цикла анализа от величины с для вероятности правильной оценки Р0,95 производится на ЭВМ. На фиг.3 показаны зависимости необходимого числа И двоичных разрядов счетчика45 в блоке коррекции от величины отклонения от равновероятности 6 для известного ГСЧ (кривая А) и для предла гаемого ГСЧ (кривая Б), а на фиг. 4 зависимость времени, необходимого 50 на один шаг цикла коррекции при тактовой частоте Гт = 1 мГц, от величины отклонения от равновероятности Е для известного ГСЧ (кривая А), и для предлагаемого ГСЧ (кривая Б). 55 Приведенные на фиг. 3 и 4 сравнительные характеристики параметров систем автоподстройки показывают, что для н Если в формуле (3) принять тп = - + 1.15 где Ь - емкость реверсивного счетчиРка, то величина Рп,И будет выражать вероятность заполнения реверсивного счетчика на М-ом такте случайной последовательности. Вероятность заполнения реверсивного счетчика после М .тактов случайной последовательности будет равна сумме вероятностей заполнения его во всех предшествующих тактах. При этом следует учесть, что вероятность заполнения реверсивного счетчика на И, -ом такте равна произведению вероятностей собственно заполнения счетчика, умноженному на вероятность того, что счетчик не будет заполнен во всех предшествующих тактах Принцип расчета необходимой величины емкости реверсивного счетчи ка заключается в последовательном суммировании вероятностей заполнения реверсивного счетчика вообще и его35 заполнения, при котором содержимое соответствует знаку Г Г = 10- 10 ф и вероятности правильного решения в цикле коррекции Р = 0,95 необходимая емкость двоичного счетчика известного ГСЧ, выраженная в числе двоичных разрядов, должна в 3,5 раза превышать емкость реверсивного счетчика предлагаемого ГСЧ, а время, затрачиваемое на один шаг цикла коррекции в известном ГСЧ, в 4,5 раза больше времени, необходимого для той же Операции в предлагаемом ГСЧ.Технические преимущества ГСЧ заключаются в том, что в 3,5-кратное уменьшение емкости реверсивного счет чика позволяет во столько же раэ упростить схему коррекции, что имеет большое практическое значение, поскольку именно схема коррекции определяет сложность схемы всего ГСЧ, его надежность, быстродействие и другие тактико-технические показатели. 4,5-кратное сокращение времени, затрачиваемого на один шаг цикла анализа, позволяет обеспечить работу. многоразрядного ГСЧ таким образом, чтобы одна коррекция обслуживала поочередно несколько генераторов случайной последовательности (ГСП) без ухудшения параметров случайной послЕдовательности, а также значительно снизить влияние внешних дестабилизирующих факторов на равновероятность случайной последовательности.Преимуществом предлагаемого ГСЧ является то, что при фиксированной емкости реверсивного счетчика время анализа уменьшается с ростом величины 1- . Это позволяет значительно сократить время, необходимое на восстановление требуемой равновероятности .при резком отклонении вследствие воздействия внешних дестабилизирующих факторов. Так, в известном ГСЧ время одного цикла анализа зависит только от емкости счетчика единиц и формирователя кодов. При резком скачкообразном отклонении от равновероятности выходной случайной последовательности необходимое на.восстановление равно- вероятности время может достигать значительной величины. Например, при Ет = 1 мГц необходимая длительность цикла анализа для поддержания величины 6410составляет для известного ГСЧ 67 с, а для предлагаемого ГСЧ 15 с, Если по каким-либо причинам величина Е скачкообразно изменится до 101104512 10 то длительность цикла анализа в предлагаемом ГСЧ уменьшится до б,б с,тогда как в известном ГСЧ она останется неизменной. 5Применение предлагаемого ГСЧ в вычислительных устройствах с вероятност ным представлением информации позволит значительно повысить их надем- ф ность, экономичность, увеличить быстродействие, производительность и точность, упростить конструкцию и улучшить характеристику равновероятности случайной последовательности.