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

Изобретение относится к вычислител ной технике и может найти применение в технических средствах модел рования и при решении различных задач методом стохастического моделирования на электронных цифровых вычислительных Мс1Шинах. Известен генератор марковских последовательностей случайных чисел с бета-распределением. Это устройство использует принцип авторегрессии и содержит соответствующие блоки для его осуществления. Они основаны на соотношениях между случайными числами с нормальным распределением и случайными числами с бета-распределением. Существенные свойства этого распределения характеризуются двумя параметрами l . Однако известный генератор ие позволяет получить случайные числа с распределением ВейбуЛла, которое име ет важное значение в теории надежности, не позволяет также вырабатывать марковские последовательности случайных чисел с распределением, сцщественные свойства которого характеризовались бы более, чем двумя параметрами,В то же время с осло нением задач, решаемых стохастическими моделирующими устройствами и стохастическим моделированием на универсальных электронных цифровых вычислительнь х машинах, в частности 351Дач моделирования прочности, нагрузки и отказов элементов, узлов и систем, необходимость в них все более ощущается. Наиболее близким техническим решением к изобретению является генератор случайных чисел, содержащий генератор тактовых импульсов выход которого соединен с входами генератора независимых нормальных cлsrчaйных чисел и счетчика тактовых импул сов, первый умножитель, первый вход которого соединен с выходом генератора независимых нормальных случайных чисел, а выход - с первым входом сумматора, выход которого через квсщратор соединен с первым входом блока последовательного суммировани последовательно соединенные блок па мяти и узел задержки, причем вход блока памяти соединен с выходом сум матора, а выход элемента задержки с первым входом второго умножителя, первый датчик -чисел, первый и второ выходы которого соединены со вторым входами соответственно первого и втр рого умножителей, блок сравнения, первый и второй входы которого сое динены с выходами соответственно счетчика тактовых импульсов и второго датчика чисел, а выход - со вторым входом блока последовательно го суммирования, и третий умножитель, первый вход которого соединен с выходом третьего датчика чисел, а выход - с выходной клеммой всего устройства 2 , Недостатком данного генератора является то, что он позволяет получить только двухпараметрические законы распределения вероятностей. Цель изобретения - расширение функциональных возможностей генератора за счет увеличения .количества параметров воспроизводимого закона распределения. Для достижения поставленной цели в Генератор марковской последовательности случайных чисел, содержащий генератор тактовых импульсов, выход которого соединен с входами генератора независимых нормальных случайных чисел и счетчика тактовых импульсов, первый умножитель, первый вход которого соединен с выходом генератора независимых нормальных случайных чисел, а выход первого умножителя соединен с первым входом сумматора, выход которого через квадратор соединен с первым входом блока последовательного суммирования, последовательно соединенные блок памяти и элемент задержки, причём вход блока памяти со единен с выходом сумматора, а выход элемента задержки соединенс первым входом второго умножителя, первый датчик чисел, первый и второй выходы которого соединены со вторыми входами соответственно первого и второго умножителей, блок сравнения, первый и второй входы которого соединены с выходами соответственно счетчика тактовых импульсов и второго датчика чисел, а выход блока сравнения соединен со. вторым входом блока последовательноГо суммирования, третий умножитель, . первый вход которого соединен с выходом третьего датчика чисел, а выход третьего умножителя является выходом генератора марковской последовательности случайных чисел, введены четвертый датчик чисел, преобразователь десятичных чисел, в двои ные, кодовый преобразователь, блок извлечения квадратного корня и блок возведения в степень, первый вход которого соединен с выходом блока последовательного суммирования/ а выход блока возведения в степень соединен с первым входом блока кз влечения квадратного корня, выход которого соединен со вторым входом третьего умножителя, выход четвертого датчика чисел через преобразователь десятичных чисел в двоичные соединен со входом кодового преобразователя, первый и второй выходы которого соединены соответственно со вторьами входами блока возведения в степень и блока извлечения квадратного корня. Кроме того, кодовый преобразователь содержйт узел возведения в степень, умножитель и счетчик, счетный вход которого является входом кодового преобразователя и соединен с первьм входом умножителя, выход ко- торого является первым выходом кодового преобразователя, вторым выходЬМ которого является выход счетчика, соединенный также через узел возведе ния в степень со вторьам входом умнржителя. На фиг. 1 прив.едена схема прёйла гаемого генератора; на фиг, 2 - схема кодового преобразователя; на Фиг. 3 - схема блока возведения в степень; на фиг:. 4 - схема блока извлечения квадратного корня. Генератор содержит (Фиг. 1) г нёратрр 1 тактовых импульсов, reHe-ратор 2 независимых нормальных случайршх чисел, счетчик 3 тактовых импульсов, умножитель 4, сум матор 5, квадратор б, блок 7 последовательйого суммирования, блок 8 памяти, элеялент 9 задержки второй умножитель 10, первый датчик 11 чисел, блок 12 сравнения, второй дат чик 13 чисел, третий умножитель 14; третий датчик 15 чисел, выхрдную клемму 16, блок 17 возведения в стёг пень, блок 18 извлечения квадрйтного корня, четвертый датчик 19 , пpeoбpaзpвiaтeль 20 десятичных чисел в двоичные, кодовый прербразоватёйь 21, который содержит вход 22, счетчик .23, хтлножитель 24, узел 25 возведения в степень, первый выход 26 преобразователя и второй выход 27 преобразователя (фиг. 2). . Блок 17 возведения в степень (фиг. 3) состоит из 5 лножителя W, управля1вмого Ключа 29/ схемы 30 срав нения и счетчика 31 тактовых иютуЛьсов.- -,; ,. - ,. :-.: . . ;; Блой 18 извлечения квадратного корня (фиг. 4) сбдержит делитель 32, управляющий ключ 33, схему 34 срайнения и счетчик 35 тактовых импуль- . ., , .- . .. . ;.,.. .-Генератор 1 тактовых импульсор синхронизирует работу всего устрой ства. Генератор 2 в такт с зирующими импульсайи вырабатывает независимые нормгшьно распределенные случайные числа со средним О и с дисперсией 1 в выбранном масштабе, В квадраторе 6 ноЕИлальные случайные числа возводятся в крадрат, но для обеспечения марковости вырабатыва-. емой последовательности случайных чисел с выходной клеммой 16 возводи мые в квадрат случайные числа обр4 зутотся в сумматоре 5 как сумма неко/торой части независимого нормального случайного числа с выхода генератора 2 и и еде 6 торой части соответству ющего числа с выхода сумматора 5 на предыдущем такте.Запоминание и задержка соответствующего числа с выхода сумматора 5 на предыдущем такте обеспечиваются блоком 8 памяти и элементом 9 задержки. Независимое нормальное случайное число с выхода генератора 2 умножается в первом умножителе 4 на число, меньшее единицы, С первого выхода первого датчика 11, а соответствующее число с выхода суМматрра 5 на предыдущем такте 5 ножается во втором умножителе 10 на число, меньшее единицы, со второго выхода первого датчика 11. Квадраты случайных чисел с выхода квадратора 6 суммируются в блоке 7 последовательного суммирования, причем количество слагаекслх в сумме управляется сигналом, на втором входе блРка 7. Для фиксирования количества слагаемых в Сумме во втором датчике 13 устанавливается положительное целое число. При совпадении этого числа, .с числом тактовых им пульсов, считаемых счетчиком 3, блок 12 сравнения вырабатывает сигнал, поступающий на второй вход блока 7 и пре ращакедий Суммирование. Расширение функциональных возможностей в предлагаемом изобретении достигается возведением случайногочисла с выхрда блока 7 последовательного суммирования в степень, причем показатель степени не обязательно дРлжен быть целш1 числом. Показатель Ртепени можно записать в виде обыкновенной дроби Iti /п ; где гм и И целые числа. Возведение числа в дробную степень заключается в врзведе- , НИИ его в целую степень ,(тт и в последующем извлечении корня с целочисленньм показателем корня п. ОдНако прямое техническое осуществление этого правила наталкивается на трудности. Поскольку (1 может быть лкзбым целым числрм, то имеется большой набор различных узлов извлечения корня, по одному для каждого п , Если однако р является.;.;тепеньючи.сла 2, т.е. fli2,s1, 2, 3...,. то извлечение корня с показателем h можно заменить t -кратньоу извлечением квадратного корня. В этом случае показатель стенени дрлвкен быть записан в виде , где т - целое число. Тогда возведение числа в дробную степень будет заключаться вт -кратном взятии адсла в качестве сомножителя и € -кратном извлечении из результата квадратного корня. Показатель степени в- виде десятич- кого числа устанавливается в четвер-. том датчике 19. В преобразователе 20 показатель степени преобразуется из десятичной системы в двоичную. Таким образом, на выходе преобразователя 20.имеется двоичная дробь, например, в виде цепочки шшульсов двух полярностей или двух различных амплитуд с известным положением запятой среди цифр, изображаемых этим импульсами. В преобразователе 21 двоичное чи ло преобразовывается к виду , , где т и и - целые числа, причем числа ,п и 6 в oтдeльkocти образуют ся на выходах преобразователя. Число т р первого выхода преобразователя 21 поступает на второй вход первого узла 17 возведения в степен и обеспечиваетт -кратное умножение числа на первом его входе на самого себя. Число 1 со второго выхода пре образователя 21 поступает на второй вход узла 18 извлечения квадратного корня и управляет i -кратным извлечением квадратного корня из чис,л поступающего на первый вход узла 18 Третий умножитель 14 осуществляет изменение масштаба числа, поступающего с выхода блока 18 извлечения квадратного кория на его первый вход, путем умножения на число, задаваемое третьим датрчиком 15 и пода ваемое на его второй вход. После выполнения перечисленных операций устройство приступает к выработке следующего числа в марковской после довательности, снимаемой с выходной клеммы 16. Работу предлагаемого изобретения можно пояснить также с использованием математической символики. Если обозначить черех х случай ное число с выходной клеммы 16, то оно образуется согласно формуле l.r(c,Nii,,iC,Ni,iV) , .гдёН ,- независимые нормальные случайные числа с выхода генератора 2; случайные числа с выхода сумматора 5; число, меньшее единицы н первом выходе первого датчика 11; число, меньшее единицы н втором выходе первого датчика 11; целое положительное числ на выходе второго датчика 13, 1/6 число на выходе четверто го датчика 19, iVa число на выходе третьего датчика 15. Можно показать, что плотность {( распределения каждого из чисел х дается формулой :iW;-,-j « -«f(-(7f)« когда в общем случае положительный параметр об имее целочисленное значение К, Как видно из этой формулы, оно действительно имеет три параметра оС , У , . Из. этой формулы вытекает ряд частных случаев, в частности при «г К-2 пол5 1ается распределение Вейбулла. Таким образом, для генерирования марковских последовательностей случайных чисел с распределением Вейбулла при помощи предлагаемого изобретения нужно во втором датчике 13 устанавливать .число 2. Случайное число, с таким распределением в математической литературе ранее не встречалось и поэтому это распределение обладает элементом новизны. Вариант исполнения преобразователя 21 работает следующим образом. Счётчик 23 считает количество цифр в дробной части двоичного числа, поступающего на вход 22 преобразователя 21j например в виде импульсов различной полярности или импульсов двух различных амплитуд. Количество двоичных цифр в дробной части двоичного числа и определяет кратность извлечения квадратного корня. Сигнал с выхода счетчика 23 поступает на второй выход 27 преобразователя и далее на второй вход блока 18 извлечения квадратного корня. Во втором узле 25 возведения в степень происходит возведение числа 10 в двоичной системе, чему в -двоичной системе соответствует число 2 в степень, причем показатель степени определяется числом с выхода счетчика 23. Полученное число перемножается в умножителе 24 с дробным двоичным числом с входа 22 преобразователя 21, вследствие чего число на выходе четвертого умножителя 24.уже целое. Оно поступает на первый вход 26 преобразователя 21 и далее на второй вход первого блока 17 возведения в степень для управления последовательным умножителем числа с первого входа блока 17 на самого себя. Работу варианта исполнения преобразователя 21 можно пояснить также С использованием математической символики. Пусть имеется дробное двоичное число I rbffbfn , I , В этой записи каждая ёуква Ь обознё:чает одну из двоичных цифр О и 1. Число двоичных цифр в дробной части равное . Если теперь это.число помнОжить и разделить на ю (число 10 здесь в двоичной системе), что получится обыкновенная дробь. ... loooTTTo где количество нулей единицы в знаменателе равно .Если эта дробь выступает показателем степени, то

,возведение в эту степень заключается во взятии осиования степени в качестве сомножителя ,.. .bf( раз и во взятии квадратного корня из результата раз.

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

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

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

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

Экономический- эффект изобретения

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

Л

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