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

ОПИСАНИИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик(22) Заявлено 11. 05. 81 (21) 3293633/18 с присоединением заявки Мо Государственный комитет СССР по делам изобретений и открытий3) Приоритет убликовано 1 Ы 2,82, Бюллетень М та опубликования описания 15. 12. ина и Е.Г.Косарева 2) Авторыизобретения 1 абиноч, РГ,А М. жатвенны ий етей щ ющ Оюэный ГосЯЪьр исследовательс электрических т" Ордена Октябрьской революции Все проектно-изыскательский и научно институт энергетических систем и(54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕ во генерации чисел с заданным ром (или с заданой функцией) 1. йство не может е гауссовские заданной формой вания заданного тра последоваслучайных чисел Известно устройс гауссовых случайных энергетическим спек ной автокорреляционОднако это устр формировать случайн числа с произвольно спектра. Для формир энергетического спе тельности гауссовых Изобретение относится к вычислительной технике и, в частности, к устройствам и системам вероятностного цифрового моделирования процессов и динамических систем, и позволяет получать гауссовые случайные числа с заданным энергетическим спектром.При решении многих задач анализа и синтеза динамических систем широко применяют цифровое вероятностное моделирование. В этом случае на вычислительном устройстве не только моделируется исследуемый объект, но и формируется внешнее возмущение на этот объект. Как правило, внешнее возмущение представляет собой стационарный случайный процесс с известным энергетическим спектром. используют метод канонических разложений.Однако этот период требует очень больших вычислительных затрат. В 1.21 предложен эффективный способ формирования гауссовых случайных чисел с заданным энергетическим спектром, основанный на применении метода быстрого преобразования Фурье и вычислению канонического разложения гауссова случайного процессаЭтот метод заключается в вычислении дискретного преобразования фурье от последовательности равномерно распределенных случайных чисел, взятых с весами, определенными частотной характеристикой формирующего фильтра.Наиболее близким техническим решением к изобретению является устройство, построенное на базе метода быстрого преобразования Фурье, которое содержит тактовый генератор, к первому выходу которого подключены последовательно соединенные генератор равномерно распределенных чисел, перемножитель, блок буферной тамяти и блок быстрого преобразования фурье, а ко второму выходу подсоединен управляющий вход блока выборки, на первый вход которого вклю 981999чен первый блок резисторов памяти, авыход соединен со вторым входом перемножителя ( 2 ),При работе прототипа по сигналамтактового генератора формируется одно равномерно распределенное число(в общем случае комплексное) и осуществляется выборка из первого блокарегистров памяти очередного значениявесового коэффициента (также в общемслучае комплексного). В перемножи 1 Отеле эти два числа перемножаются, арезультат записывается в буфернуюпамять. На следующих тактах работытактового генератора указанная процедура повторяется до тех пор покане заполнится вся буферная память,содержащая 9 регистров. После заполнения буферной памяти включается в работу блок быстрого преобразования Фурье, на выходе которого 20формируется последовательность гауссовых случайных чисел с заданным энер"гетическим спектром. Для успешнойработы прототипа значения весовых коэффициентов должны быть пропорциональны корню квадратному из значений энергетического спектра на соответствующих частотах.Несмотря на то, что устройствопрототип является наиболее естрым из известных устройств генерации гауссовских случайных чисел спроизвольно заданным спектром, вычислительные затраты в нем достаточновелики. Эти затРаты составляют для 35последовательности из Н гауссовыхчисел примерно БоИ комплексныхарифметических операций сложенияИ(1+1/21 од Н) комплексных операцийумножения. Недостатком прототипа . 40таким образом, является большойобъем вычислительных затрат (малоебыстродействие) при генерации гауссовых случайных чисел с заданнымэнергетическим спектром45Цель изобретения - повышениебыстродействия устройства.Цель достигается тем, что в известный генератор случайных чисел,содержащий генератор тактовых импульсов, первый выход которого соединен со входом генератора равномерно распределенных случайных чисел,выход которого соединен с первымвходом блока умножения, второй входкоторого подключен к выходу ключа,выход блока умножения соединен совходом первого блока памяти, второйблок памяти, введены блок формирования весовых коэффициентов, блокбыстрого преобразования Уолша и 60элемент задержки, вход которого подключен ко второму выходу генераторатактовых импульсов, третий выходкоторого соединен со входом блокаФормирования весовых коэффициентов, 65 группа входов которого соединена с группой выходов второго блока памяти соответственно, выход блока формирования весовых коэффициентов соединен с информационным входом ключа, управляющий вход которого подключен к выходу элемента задержки, выход первого блока памяти соединен со входом блока быстрого преобразования Уолша, выход которого является выходом генератора.Кроме того, блок формирования весовых коэффициентов содержит два блока памяти, два коммутатора, квадратор, сумматор, нелинейный преобразователь и умножитель, группа выходов первого блока памяти соединена с группой входов первого коммутатора соответственно, вход которого объединен со входом второго коммутатора и является входом блсгка, группой входов которого является группа входов второго коммутатора, выход которого соединен с первым входом умножителя, выход которого соединен со входом второго блока памяти, выход которого является выходом блока, выход первого коммутатора через последовательно соединенные квадратор, сумматор и.нелинейный преобразователь соединен со вторым входом умножителя.На фиг.1 приведена блок-схема предлагаемого генератора случайных чисел с заданным энергетическим спектром; на фиг.2 - схема блока формирования весовых коэффициентов.Устройство содержит генератор 1 тактовых импульсов, к первому выходу которого подключены последовательно соединенные генератор равномерно распределенных случайных чисел 2, блок умножения 3, первый блок памяти 4 и блок быстрого преобразования Уолша 5. Второй выход генератора 1 соединен с управляющим входом блока формирования весовых коэффициентов б, на информационные входы которого подключены выходы второго блока памяти 7. Третий выход генератора 1 через элемент задержки 8 подсоединен к ключу 9. Блок формирования весовых коэффициентов б состоит из последовательно соединенных первого блока памяти 10, первого коммутатора 11, квадратора 12, сумматора 13, нелинейного преобразователя 14, выполняющего извлечение квадратного корня из входной величины, умножителя 15 и второго блока памяти 1 б. На второй вход Умножителя 15 включен выход второго коммутатора 17, Второй выход генератора 1 подключен к управляющим входам коммутаторов 11 и 17, а на входы второго коммутатора 17 включены выходы блока памяти 7, Выход бло 981999тельные затраты в прототипе составляют примерно Б комплексных опера 1 ций сложения и М(1+-1;од И) комплекс 2 ных операций умножения. Более удобно,перейти к арифметическим операциям над действительными числами. При работе прототипа необходимо. реализовать примерно 2 Н+ЗИоуИ арифметических операций сложения и 2 И(2+од И) арифметических операций умножения (с учетом того обстоятель ства, что последовательностьдействительных чисел О :Х -)у - последовательность ком- К К Кплексных чисел).В предлагаемом устройстве комплексная последовательность случайных чисел 2 К, К = 0,1Мумножается соответственна на действительныЕ числа . На это требуется 2 И операций умножения,Для выполнения дискретного преобразования Уолша над комплексной последовательностью 4.КЗ Гк к = 01 ,(И) необходимо выполнить примерно 2 М 3 о 9 Б операций сложения.Обозначим время выполнения операции сложения сл, а время операции умножения действительных чиселСс . Константа С для современных вычйслительных устройств лежит в пределах,1-10.Выигрыш Т, даваемый предлагаемым устройством, составляет + ЕОЧ" -у,(РфЕ 0 Я ф 21"фсл сл . умсл гЬ 1 ЧЕОР,хи+ -двумисл а. Для вычислительных устройств с фиксированной арифметикой . с 5 , В этом случаеум и.иииииИии ииигяоуу миНаиболее типичные значения М лежат в пределах 128-1024. Для таких значений И выигрыш Т в вычислительных затратах составляет примерно 3-4 раза,Блок формирования весовых коэффициентов 6 работает следующим образом (см,фиг,2), Сигнал генератора 1 поступает на управляющие входы первого и второго коммутаторов 11 и 17. По этому сигналу из блока памяти 10 осуществляется последовательная выборка первым коммутатором 11 значений ядер Фурье Ф(п,К) для различных значений ) и фиксированного значения и, равного номеру генерируемого равномерно распределенного числа. Эти значения Ф(п возводят ся в квадрат квадратора 12 и суммируются сумматором 13. После завершения определения - (Ф(п,)с для35 где с 1 К) - отсчеты требуемого энергетического спектра последовательности гауссовых чисел и Ф(п,К) 40 значения функции ядер Фурье Я(К иФ(п,К) считаются заданнымиДля наиболее тийичных последовательностей длительностью 128-1024чисел выигрыш в вычислительных за тратах предлагаемым устройством посравнению с прототипом составит3-4 раза.Таким образом, основным преимуществом заявляемого устройства является уменьшение вычислительныхзатрат при генерации гауссовскихслучайных чисел с заданным энергетическим спектром из равномерно распределенных.Все блоки, входящие в предлагаемоеустройство, хорошо известны. Их реализация не вызывает затруднений.Предлагаемое устройство найдет применение в цифровых системах моделирования динамических объектов. Эко 6 О номический эффект от примененияпредлагаемого устройства составитпорядка 20-30 тыс.руб в год.Формула изобретения1. Генератор случайных чисел, 65 содержащий генератор тактовых им 5 10 15 20 25 30 всех и = 0,1,2,И, из полученной суммы извлекается квадратный корень нелинейным преобразователем 14. Результирующее значение поступает на первый вход умножителя 15. На второй вход умножителя 15 поступает выбранное вторым коммутатором 17 значением,(К), численно равное корню квадратному из требуемого значения энергетического спектра последовательности гауссовых случайных чисел. Полученные весовые коэффициенты накапливаются в блоке памяти 16.Накопленные в блоке памяти 4 значения случайных равномерно распределенных чисел, умноженных на весовые коэффициенты, подвергаются быстрому преобразованию Уолша в блоке 5. На выходе этого блока образуется последовательность гауссовых случайных чисел с заданным энергетическим спектромПри практическом использовании предлагаемого устройства для генерации большого числа последовательностей из И гауссовых чисел с заданным энергетическим спектром, формирование весовых коэффициентов не. - обходимо,выполнить только один раз, после чего их выборку осуществляют из блока памяти 16. Формирование весовых коэффициентов осуществляется согласно выражению ь(к)=А(к)" 1 Ф(и к)и=опульсов, первый выход которого соединен с входом генератора равномерно распределенных случайных чиселвыход которого соединен с первым входом блока умножения, второй вход которого подключен к выходу ключа, выход блока умножения соединен с входом первого блока памяти, второй блок памяти, о т л и ч а ю щ и йс я тем, что, с целью повышения быстродействия, он содержит блок формирования весовых коэффициентов,блок быстрого преобразования Уолша и элемент задержки, вход которого подключен к второму выходу генератора тактовых импульсов, третий 15 выход которого соединен с входом блока.формирования весовых коэффициентов, группа входов которого соединена с группой выходов второго .блока памяти соответственно, выход блока 20 формирования весовых коэффициентов соединен с информационным входом ключа, управляющий вход которого подключен к выходу элемента задержки, выход первого блока памяти сое динен с входом блока быстрого преобразования Уолша, выход которого является входом генератора.2. Генератор по п.1, о т л и - ч а ю щ и й с я тем, что блок 30 формирования весовых коэффициентовсодержит два блока памяти, два коммутатора, квадратор, сумматор, нелинейный преобразователь н умножитель,группа выходов первого блока памятисоединена с группой входов первогокоммутатора соответственно, входкоторого объединен с входом второгокоммутатора и является входом блока,группой входов которого являетсягруппа входов второго коммутатора,выход которого соединен с первымвходом умножителя, выход которогосоединен с входом второго блока памяти, выход которого является выходом блока, выход первого коммутатора через последовательно соединенные квадратор, сумматор и нелинейный преобразователь соединен с вторым входом умножителя.Источники информации,принятые во внимание при экспертизе1. Кори Г. Моделирование случай-,ных процессов на аналоговых и аналого-цифровых машинах. М., фМир,1968.2, Миркин Л.И., Рабинович М.А. иЯрославский Л.П. Метод генерирования коррелированных гауссовских псевдослучайных чисел на ЭВМ. ЖВМ и Мфт.12 Р 5, 1972 (прототип) .иу грк Составитель А.Карасов дактор М.Товтин Техред К,Мыцьо Корректор С.Шекмараказ Филиал ППП фПатент, г. Ужгород, ул. Проектн 13/69 Тираж 731 ВНИИПИ Государственно по делам изобретен. 113035, Москва, Ж, Подписноео комитета СССРй и открытийРауюская наб., д, 4/5