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

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

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

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

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

15 возникают трудности и сохраняются недостатки, присущие устройствам, основанным на принципе авторегрессии.

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

25 виде цепи Маркова. В этом случае надо каким-то образом осуществить запоминание матрицы вероятностей перехода с уровня на уровень значений чисел, причем если имеется К

30 .уровней, то матрица в общем случае содержит К2 элементов. Если уровней много, то осуществление запоминания элементов матрицы является отнюдь не простым делом и сильно ограничивает применимость таких устройств. Наиболее близким техническим решением к предлагаемому изобретению является преобразователь независимых равномерно распределенных случай ных чисел в коррелированную последовательность, содержащих тактовый генератор, выход которого соединен, с входами генератора равномерно распределенных случайных чисрл и датчиков шага, выход генератора равномерно распределенньах случайных чисел соединен с входом устройства срав-. нения, выход которого соединен с пер вым входом сумматора, выход которого соединен с выходной клеммой преобразователя, причем выход датчика шагя1 соединен с вторым входом сумматора 2 . Этот преобразователь является материальным воплощением хорошо известного в теории случайных процессо принципа случайного блуждания, причем его реализация может быть осуществлена рутинными инженерньми при емами путем сочетания известных уст ройств генерирования чисел, их сравнения и последовательного сумми рования. Принцип случайного блуждания традиционно описывается при помощи частицы, через равные промежутки вр мени движущейся по прямой случайным образом на один шаг в одном или дру гом направлении с определенными вероятностями. Таким образом, координата блужда щ§й частицы является случайной вели чиной, зависящей от ее координаты в предыдущий момент времени. При уменьшении шага, на который частица может двигаться в одном или другом направлении, и соответствующем умен шении промежутков времени в пределе получается процесс, носящий имя Винера. Существенным в традиционном прин ципе случайного блуждания является то, что вероятности движения частицы в одном или другом направлении не за висят от положения частицы. Как результат этого, перемещение движущей ся частицьг, хотя оно и может быть гомогенным процессом, не может являться стационарным процессом. Соответственно и наиболее близкое к предлагаемому изобретению техническое решение не позволяет генерирова стационарные коррелированные последовательности. С другой стороны, в технике цифрового моделирования и при решении различных задач методом статистических испытаний весьма часто требуются последовательности, яв ляющиеся стационарными. Во многих случаях, например при моделировании процессов изменения во времени прочности элементов технических систем и действующей на эти элементы нагрузки, при помощи которых моделируется возникновение отказов, важна не только стационарность случайных процессов, но и принадлежность их распределения к тому или иному классу. Среди различных распределений выделяется нормальное распределение, важное для моделирования технических систем тем свойством, что при заданных среднем значении и дисперсии случайные числа с нормальным распределением обладают наибольшей неопределенностью в смысле Шеннона. В случае традиционного процесса случайного блуждания нормальность процесса обеспечивается автоматически. В то же время обеспечение нормальности стационарного коррелированного процесса далеко не является очевидным как не очевиден и путь преобразования независимых равномерно распределенных случайных чисел в стационарную коррелированную последовательность, обладакндую нормальностью. Цель изобретения - расширение функциональных возможностей преобразователя за счет получения стационарных последовательностей случайных чисел. Для достижения поставленной цели в преобразователь, содержащий тактовый генератор, выход которого соединен с входами генератора равномерно распределенных случайных чисел и датчика шага, выход генератора равномерно распределенных случайных чисел соединен с первым входом блока сравнения, выход которого -соединен с первым входом сумматора, выход которого являет1ря выходом преобразователя, выход датчика шага соединен с вторым входом сумматора, введен блок преобразования уровня, первый вход которого соединен с выходом сумматора, второй вход блока преобразования уровня соединен с выходом датчика шага, а выход блока преобразования уровня соединен со вторьии входом блока сравнения. Кроме того, блок преобразования уровня содержит последовательно соединенные умножитель и сумматор, выход которого является выходом блока, первым и вторым входами КОТОРОГО является соответственно первый и второй выходы умножителя. На фиг. 1 представлена блок-схема преобразователя; на фиг. 2 - временная диагоамма функционирования устройства. Выход тактового генератора 1 соединен с входами генератора 2 равномерно распределенных случайных чисел и датчика 3 шага. Выход генератооа 2 равномерно распределенных случайных чисел соединен с первым входом блока 4 сравнения, выход которого .соединен с первым входом сумматора 5. Выход сумматора 5 соеди нен с выходной клеммой бис первым входом блока 7 преобразования .уровня. Выход датчика 3 шага соединен с вторым входом сумматора 5 и с вторым входом блока 7. Выход умножителя 8 соединен с входом второго сумматора 9 . На временной диаграмме функционирования преобразователя (фиг.2) пред ставлены: .10 - реализация последова тельности равномерно распределенных чисел R, 11 - уровень сравнения р(х 12 - реализация коррелированной посл довательности случайных чисел, 13 момент генерирования независимых равномерно распределенных случайных чисел, 14 - момент сравнения независимого равномерно распределенного случайного числа с уровнем сравнени 15 - момент изменения числа в корре лированной последовательности чисел и 16 - момент изменения уровня сравнения по новому числу в коррели рованной последовательности. Преобразование независимых равно мерно распределенных случайных чисе в коррелированную стационарную после довательность происходит следующим образом. Генерированные в определенном так те через промежуток времени а t неза висимые, равномерно распределенные на интервале значений в соответствую щем масштабе от О до 1, случайные числа сравниваются с уровнем сравне ния р(х). В результате сравнения вырабатывается сигнал одной полярнос ти или одного значения, если случайное число превышает уровень сравнения, и сигнал другой полярности или другого значения, если случайное число не превышает уровня сравнения. Постоянное число л. X, вырабатываемое в том же такте, либо суммируется с алгебраической суммой х предыдущих чисел дх, образуя число х+Д х либо вычитается из него, образуя чис ло х- Дх, в зависимости от того, сигнал какой полярности или какого значения вырабатывался после сравнения равномерно распределенного слу.чайного числа с уровнем сравнения. Алгебраическая сумма чисел (х+ Лх либо х- Лх) поступает дальше для использования при цифровом моделировании: она случайна, поскольку увеличение или уменьшение предыдущего числа X надх зависит от случая, и коррелирована (точнее марковская) поскольку новый сигнал х или х-л X зависит лишь от предыдущего числа X. Изменение уровня сравнения происходит таким образом, что сложение постоянного числа дх к предыдущему числу X происходит с большей вероятностью тогда, когда предыдущее число X (алгебраически) мало и с меньшей вероятностью, когда оно имеет (алгебраически) большое значение. Соответственно вычитание постоянного числа Д X из предыдущего числа )( производят с большой вероятностью тогда, когда число х (алгебраически) большое и с малой вероятностью тогда, когда это число имеет (алгебраически) малое значение. Кроме того, если число х имеет среднее значение (которое в последующих рассуждениях, а также на приводимых фигурах принято равным нулю, чего всегда можно добиться путем соответствующего выбора начала отчета), то сложение и вычитание двух чисел X и д,х происходит с одинаковой вероятностью. Этими приемами обеспечивают стационарность вырабатываемой последовательности случайных чисел. В известном преобразователе отсутствует изменение уровня сравнения под управлением чисел вырабатываемой последовательности. Принцип изменения вероятностей сложения и вычитания чисел х и Л х путем изменения уровня сравнения можно описывать при помощи зависимости РСх)- -уЬтсдх,в) где f(x) - монотонно возрастающая (в сторогом смысле) функция, удовлетворяющая условию х(0)0, а коэффициент Ь, исходя из свойств вероятности, (при f(x)) должен отвечать соотношению .JS В частности, можно выбрать f тогда P(x) у .Ьх-дх,. Если обозначить вероятность числа X через р(х), то из разностного уравнения баланса вероятностей Р(х)Р(х+дх)Г1 -р(х+йх)+Р(х-Дх)р(-Дх) при предельном пеЕ еходе дх- О получается дифференциальное уравнение 4,(х)-о,(й) dx « которое имеет решение Р(х)аехр(-Ьх ) , где а - положительная константа, определяемая из условия нормировки вероятностей. Следовательно, путем выбора специального вида для функции а(х)х и уменьшения сигнала Д х можно добиться нормальности (гауссовости) вырабатываемой стационарной последо вательности случайных чисел. Таким образом, блок преобразования уровня имеет передаточную харак теристику (рассматриваемую как функцию от X и Дх) в виде формулы Структурно этот блок может состоять например, из субблока с монотонной возрастающей (в строгом смысле) педеаточной характеристикой f(x), отвечающей условию f(0)0,.вход которого соединен с выходом сумматора 5 а выход - с первым входом субблока умножения, причем второй вход субблока умножения соединен с выходом датчика 3 шага, и из суммирующего субблока, вход которого соединен с выходом субблока уножения, а выход с вторым входом устройства 4 сравнения. Нормированная ковариационная функция с(п) вырабатываемой последо вательности случайных чисел имеет вид с{п)1 -пЬ( Дх), где п - разность порядковых номеров чисел в последовательности, что для небольших Дх приблизительно заменяется на с(п-) tl -Ь{ДХ). Отсюда видно, что нормированная ковариационная функция зависит от постоянного числа Дх, на которой происходит увеличение или уменьшени случайного числа х. С другой сторон в задачах моделирования Дх определяет точность воспроизведения заданной стационарной коррелированной последовательности чисел при помощи предлагаемого преобразователя; с уменьшением Дх увеличивается точнос воспроизведения. Чтобы при увеличении точности воспроизведения не изменялась ковар ационная функция, одновременно с и менением Дх изменяют частоту генери рования независимых равномерно рас пределенных случайных чисел с соблю дением условия (Дх) /Д1 const , в качестве конкретного примера предлагаемого преобразователя укаж на ef-o осуществление при помощи периодических импульсов одинаковой формы, но различной амплитуды и по лярности . В этом случае все отдельные one рации (генерирование независимых равномерно распределенных по ампли туде импульсов, сравнение амплитуд двух импульсов, генерирование импу сов постоянной амплитуды, сложение или вычитание амплитуд двух импульсов, умножения амплитуд двух импульсов , в совокупности составляющие предлагаемое изобретение, технически осуществимы многочисленными известными путями. Таким образом, преобразователь позволяет получить стационарные коррелированные последовательности случайных чисел из независимых равномерно распределенных случайных чисел, т.е. обеспечивает достижение поставленной перед ним цели. Предлагаемый преобразователь позволяет получить коррелированные стационарные последовательности с различным распределением, в зависимости от вида функции f(x). Он позволяет воспроизвести заданную марковскую гауссовскую последовательность с любой заданной точностью. К достоинствам преобразователя относится также возможность получить коррелированную стационарную последовательность случайных чисел с одномодальным распределением прямо из последовательности независимых равномёрно распределенных чисел, минуя. их промежуточное преобразование в последовательность независимых чисел с одномодальным распределением. Формула изобретения 1.Преобразователь независимых равномерно распределенных случайных чисел в коррелированную последовательность, содержащий тактовый генератор, выход которого соединен с входами генератора равномерно распределенных случайных чисел и датчика шага, выход генератора равномерно распределенных случайных чисел соединен с первым входом блока сравнения, выход которого соединен с первым входом сумматора, выход которого . является выходом преобразователя, выход датчика шага соединен с вторым входом сумматора, отличающийся тем, что, с целью расширения функциональных возможностей преобразователя за счет получения стационарных последовательностей случайных чисел, он содержит блок преобразования уровня, первый вход которого соединен с выходом сумматора, второй вход блока преобразования уровня соединен с выходом датчика шага, а выход блока преобразования уровня соединен со вторым входом блока сравнения. 2.Преобразователь по п.1, о т личающийся тем, что блок преобразования уровня содержит последовательно соединённые умножитель и сумматор, выход которого является выходом блока, первым и вторым

входами которого являются соответственно первый и второй входы умножителя .

Источники информации, принятые во внимание при экспертизе

1.Авторское свидетельство СССР №590760 кл. G 06 F 7/58, 1976.

2.Розанов Ю.А. Случайные процессы. М., Наука, 1979, с. 58 (прототип) .