Генератор марковской последовательности случайных чисел

 

1. ГЕНЕРАТОР МАРКОВСКОЙ ПО. СЛЕДОВАТЕЛЬНОСТИ СЛУЧАЙНЫХ ЧИСЕЛ, СО .держащий генератор тактовых импульсов , выход которого соединен с входами генератора независимых нормальных случайных чисел и счетчика тактовых импуль сов,первый умножи тель,первый вход которого соединен с выходом генератора независимых нормальных случай ных чисел, а выход первого умножителя соединен с пе{)вым входом сумматора , выход которого через KBаДратор соединен с первым входом блока последовательного суммирования, последовательно соединенные блок памяти и элемент задержки, причем вход блока памяти соединен с выходом сумматора , а выход элемента задержки соединен с первым входом второго умножителя , первый датчик чисел, первый и второй выходы которого соединены со вторыми входами соответственно первого и второго умножителей, блок сравнения, первый и второй входы которого соединены с выходгили соответственно счетчика тактовых импульсов и второго датчика чисел, а выход блока сравнения соединен со -втррь1М входом блока последователь нового суммирования,третий умножитель, первый вход которого соединен с выходом третьего датчика чисел, а выход третьего умножителя является выходом генератора, марковской последовательности случайных чисел, отличающийся тем, что, с целью расширения функциональных возможноСТей генератора за счет увеличения количества параметров воспроизводимого закона распределения, он содержит четвертый датчик чисел, преобразователь десятичных чисел в двоичные, кодовый преобразователь, блок извлечения квадратного корня и блок возведения в степень, первый вход которого соединен с выходом блока последовательного суммирования , а выход блока возведения в сте- § пень соединен с первымвходом блока (Л извлечения квадратногЪ корня, выход которого соединен со вторым входом С третьего умножителя, выход четвертого датчика чисел через преобразователь десятичных чисел в двоичные соединен со входом кодового преобразователя , первый и второй выходы которого соединены соответственно со вторыми входами блока возведения в степень и блока извлечения квадрат .ного корня. 2,Генератор по п.1,0 т л и ч а ю щи и с я тем,чт9, кодовый преобразователь содержит узел возведения В степень, умножи тель и счетчик, счетный вход которого является входом кодового преобразователя и соединен с первым входом умножителя,выход которого является первым выходом кодового преобразователя,вторым выходом которого является выход счетчикаtсоединенный также через узел возведения в степень оо вторым входом умножителя.

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„1 4 О14

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

Il0 ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPbITHA

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3360242/18-24 (22) 05.12.81 (46) 15.09.83. Вюл. В 34 (72) A.A. Коорт (53) 681 325(088.8) (56) l. Авторское свидетельство СССР

9 552628@ кл. G 06 F 7/58ю 1976 °

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

9 590790, кл. G 06 F 7/58, 1977 (прототип). (54) (57) 1. ГЕНЕРАТОР MAPKOBCKOA ПО:

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

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

2.Генератор поп.1,о т л и ч а юшийся тем,что, кодовый преобразователь содержит узел возведения

В степень,умножитель и счетчик, счетный вход которого является входом кодового преобразователя и соединен с первым входом умножителя,выход которого является первым выходом кодового преобразователя, вторым выходом которого является выход счетчика, соединенный также через узел возведения в степень со вторым входом умножителя. с выходом третьего датчика чисел, а выход — с выходной клеммой всего устройства (2) .

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

Цель изобретения — расширение функциональных возможностей генератора за счет увеличения, количества

10 параметров воспроизводимого закона распределения. бО

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

Известен генератор марковских последовательностей случайных чисел с бета-распределением. Это устройство использует принцип авторегрессии и содержит соответствующие блоки для его осуществления. Они основаны на соотношениях между случайными числами с нормальным распределением и случайными числами с бета-распреде- 5 лением. Существенные свойства этого распределения характеризуются двумя параметрами $1) .

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

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

Наиболее близким техническим решением к изобретению является генератор случайных чисел, содержащий генератор тактовых импульсов1, выход . 40 которого соединен с входами генера тора независимых нормальных случайных чисел и счетчика тактовых импульсов, первый умножитель, первый вход которого соединен с выходом генера- 45 тора независимых нормальных случайных чисел, а выход — с первым входом сумматора, выход которого через квадратор соединен с первым входом блока последовательного суммирования, последовательно соединенные блок памяти и узел задержки, причем вход . блока памяти соединен с выходом сумматора, а выход элемента задержкис первым входом втоРого умножителя, первый датчик .чисел, первый и второй выходы которого соединены со вторыми входами соответственно первого и второго умножителей, блок сравнения, первый и второй входы которого сое динены с выходами соответственно счетчика тактовых импульсов и второго датчика чисел, а выход — со вторым входом блока последовательного суммирования, и третий умножитель, псрвый вход которого соединен 5

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

1042014

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

На фиг. 1 приведена схема предла+ гаемого гейератора; на фиг. 2 - схема кодового преобразователя1 на фиг. 3 - схема блока возведения s степенЫ на фиг.. 4 - схема блока извлечения квадратного корня.

Генератор содержит (фиг. 1) ге нератор 1 тактовых импульсов, генератор 2 независимых нормальных случайных чисел, счетчик 3 .тактовых импульсов, первый умножитель 4, сумматор 5, квадратор 6, блок 7 последовательного суммирования, блок 8 памяти, элемент 9 задержки, второй умножитель 10, первый датчик ll чисел., блок 12 сравнения, второй датчик 13 чисел, третий умножитель 14,: третий датчик 15 чисел, выходную, клемму 16, блок 17 возведения в сте-, пень, блок 18 извлечения квадратно« го корня, четвертый датчик 19 чисел, преобразователь 20 десятичных чисел в двоичные, кодовый преобразователЬ

21, который содержит вход 22, счетчик .23, умножитель 24, узел 25 возведения в степень, первый выход 26 преобразователя и второй выход 27 преобразователя (фиг. 2).

Блок 17 возведения в степень (фиг. 3) состоит.из умножителя 48, управляемого ключа 29, схемы 30 сравнения и счетчика 31 тактовых импульсов.

Блок 18 извлечения квадратного корня (фиг. 4) содержит делитель 32, управляющий ключ 33, схему 34 сравнения и счетчик 35 тактовых имйуль сов.

Генератор 1 тактовых импудьсов синхронизирует работу всего устройства. Генератор 2 в такт с синхфонИ- зирующими импульсами вырабатывает независимые нормально распределенные случайные числа со средним 0 .и, с дисперсией 1 в выбранном масштабе.

В квадраторе 6 нормальные случайнйе числа возводятся в квадрат, но для обеспечения марковости вырабатываемой последовательности случайных чисел с выходной клеммой 16 возводи-: мые в квадрат случайные числа обра эуются в сумматоре 5 как сумма неко торой части независимого нормального случайного числа с выхода генератора 2 и некоторой части соответствующего числа с выхода сумматора 5 на предыдущем такте. Запоминание и задержка соответствующего числа с выхода сумматора 5 на предыдущем так-. те обеспечиваются блоком 8 памяти и элементом 9 задержки. Независимое нормальное случайное число с выхода генератора 2 умножается в первом умножителе 4 на число, меньшее единицы, с первого выхода первого датчика 11, а соответствующее число с

10 выхода сумматора 5 на предыдущем такте умножается во втором умножителе 10 на число, меньщее единицы, со второго выхода первого датчика 11 °

Квадраты случайных чисел с выхода !

5 квадратора 6 суммируются .s блоке 7 последовательного сумьптрования, причем количество слагаемых в сумме унравляется сигналом на втором входе блока 7. Для фиксирования количества слагаемых в сумме во втором датчике 13 устанавливается положительное целое число. При совпадении этого числа .с числом тактовых meпульсов, считаемых счетчиком 3, блок

12 сравнения вырабатывает сигнал, поступающий яа второй вход блока 7 н прекращающий суммирование.

Расширение функциональных возможностей в предлагаемом изобретении достигается возведением случайного числа с выхода блока 7 последовательного суммирования в степень., причем показатель степени не обязательно должен. быть целым числом. Показатель степени можно записать в виЗ5 де обыкновенной дроби hi/n, где Vn и Пцелые числа. Возведение числа в дробную степень заключается в возведении его в целую степень Е и в.последующем извлечении корня с целочис40 ленным показателем корня rl. Однако прямое техническое осуществление этого правила наталкивается на трудности. Поскольку И может быть любым целым числом, то имеется большой на45 бор различных узлов извлечения корня, по одному для каждого n . .Если однако р является,степенью числа

2, т.е. П=2,0=1, 2, 3...,. то извлечение корня с показателем П можно заменить 3 -кратньы извлечением квадратного корня. В этом случае показатель стеиунн должен быть записан. в виде щ+/2, где N+- целое число. .Тогда возведение числа в дрОбную степень будет заключаться ва -крат 5;ном взятии:числа в качестве сомно:жителя и 0 -кратном извлечении из ре.зультата квадратного корня.

Показатель степени в виде десятич-

:ного числа устанавливается в четвер-, 60 том датчике 19. В преобразователе 20 показатель степени преобразуется из десятичной системы в двоичную.

Таким образом, на выходе преобразователя 20.имеется двоичная дробь, Я например, в виде цепочки иипульсов

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

В преобразователе 21 двоичное число преобраэовывается к виду,m /2, где.nl и 8 - целые числа, причем числа,m+ и 3 в отдельности образуются на выходах преобразователя. Число N+ с первого выхода преобразователя 21.поступает на второй вход 10 первого узла 17 возведения в степень и обеспечиваетщ -кратное умножение числа на .первом его входе на самого себя. Число » со второго выхода преобразователя 21 поступает на второй 15 вход узла 18 извлечения квадратного корня и управляет » -кратным извлечением квадратного корня .из числа, поступающего на первый вход узла 18.

Третий умножитель 14 осуществляет изменение масштаба числа, поступающего с выхода блока 18 извлечения квадратного корня на его .первый вход, путем умножения на число, задаваемое третьим датчиком 15 и пода25 ваемое Hà его второй вход. Поеле выполнения перечисленных операций устройство приступает к выработке следующего числа в марковской последовательности, снимаемой с выходной клеммы 16. . 30

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

- Если обозначить черех х < случаййое число с выходной клеммы 16, то 35 оно образуется согласно формуле

g к цф

)(»»=, 8 = (С»Н » С И:«

2 )»

:40 ,rpeg< » .- независимые нормальные случайные числа с выхода . генератора 2;

М) » - случайные числа с выхода сумматора 5;

С - число, меньшее единицы на 45 первом выходе первого датчика lit

С вЂ” число, меньшее единицы на: втором выходе первого датчика ll 50

К - целое положительное число на выходе, второго датчика 13, 1/8 - число на выходе четвертого датчика 19, 55 /2 - число на выходе третьего датчика 15.

Можно показать, что плотность f (х) распределения каждого из чисел х; дается формулой 60

eк1= — е" евра") ),Ое".î

Г(д)) коГда в общем случае положительный параметр О(имеет целочисленное зна- ф5 чение К. Как видно из этой формулы, оно действительно имеет три параметра g g,о . Из, этой формулы вытекает ряд частных случаев, в частности при й"- К =2 получается распределение

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

13 устанавливать .число 2. Случайное число. с таким распределением в математической литературе ранее не встречалось и поэтому это распределение обладает элементом новизны.

Вариант исполнения преобразователя 21 работает следующим образом.

Счетчик 23 считает количество цифр в дробной части двоичного числа, поступающего на вход 22 преобразователя 21, например в виде импульсов различной полярности или импульсов двух различных амплитуд. Количество двоичных цифр в дробной части двоичного числа и определяет кратность извлечения квадратного корня. Сигнал с выхода счетчика 23 поступает на второй выход 27 преобразователя и далее на второй вход блока 18 извлечения квадратного корня. Во втором узле 25 возведения в степень происходит возведение числа 10 в двоичной системе, чему в .двоичной системе соответствует число 2 в степень, причем показатель степени определяется числом с выхода счетчика 23. Полученное число перемножается в умножителе 24 с дробным двоичным числом с входа 22 преобразователя 21, вследствие чего число .на выходе четвертого умножителя 24 уже целое. Оно поступает на первый вход 26 преобразователя 21 и далее на второй вход первого блока 17 возведения в степень для управления последовательным умножителем числа с первого входа блока 17 на самого себя.

Работу варианта исполнения преобразователя 21 можно пояснить также с использованием математической символики»

Пусть имеется дробное двоичное число

» 2 ° ° )" "» the»g»

В этой записи каждая буква Ь обозначает одну из двоичных цифр 0 и 1.

Число двоичных цифр в дробной части равно Г . Если теперь это число помножить и разделить на 10 (число 10 здесь в двоичной системе), что йолучится обыкновенная дробь. оgbg . «. ) р

1000...0 где. количество нулей подле единицы в знаменателе равно . Если эта дробь выступает показателем степени, то

1"420,14,возведение в эту степень заключает ся во взятии основания степени в качестве сомножителя Ь Ь ... b»g раз и во взятйн квадратного корня иэ результата 1 раз.

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

Алгоритм, лежащий в основе Функ- ционирования генератора, также каки функция распределения получаемых случайных чисел ранее неизвестен и может быть применен, помимо стохас тического моделирования на универ-, . сальных электронных цифровых мащи-» ; нах, в теории случайных процессов и в теории вероятности.

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

Случайные и постоянные числа, генерируемые и преобразуемые в предлагаемом изобретении, могут быть представлены различными параметрами.

10 электрических, а также других физических сигналов. В качестве конкретной реализации предлагаемого устройства служит представление слу" чайных чисел электрическими импуль)5 сами случайной амплитуды, следующими с постоянной частотой. Оно может . быть осуществлено также в микропроцессорном исполнении.

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

1042014

1042014 ч

СоставиТель A. Карасов

Редактор М. Келемеш Техред, А,.Бабинец Корректор О. Тигор

Заказ 7l29/49 Тираж 706 Подписное

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

113035, Noctcsa @35, Раушская наб., д..4/5

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