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

Союз Советскнх Соцналнстнческнх РеснублнкОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОВСКОМУ Сви ВТЕЛЬСТВУ(22) Заявлено 100180 (21) 28 б 8332/18-24 (51)М л 6 Об Г 7/58 с присоединением заявки НР(23) Приоритет Государствеиимй комитет СССР по ведам изобретений и открытий(54) ПРЕОБРАЗОЬАТЕЛЬ НЕЗАВИСИМЫХ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ СЛУЧАЙНЫХ ЧИСЕЛ В КОРРЕЛИРОВАННУЮ ПОСЛЕДОВАТЕЛЬНОСТЬИзобретение относится к вычислительной технике и может найти приме-ненне в технике цифгового моделирования и решения различных задач методом статистических испытаний наэлектронных цифровых вычислительныхмашинах,Известно устройство преобразования независимых нормально распределенных случайных чисел в коррелированную нормальную последовательность,основанное на принципе авторегрессиии хорошо приспособлено для целейпреобразования нормально распределенных независимых случайных чиселв марковскую последовательность нормально распределенных чисел, а такжев коррелированные последовательности с памятью более высокого порядка 11 .Однако часто независимые случайные числа, которые необходимо преобразовать в коррелированную последовательность чисел, имеют не нормальное распределение, а равномерноераспределение в каком-либо интервалезначений. Часто требуется также,чтобы возможные значения чисел вкоррелированной последовательностибыли квантованы, т.е. чтобы их воэ. можные значения менялись небольшимишагами. В этом случае не представляется возможным применять известныеустройства беэ существенных изменений.Вместо авторегрессии в известныхустройствах можно было бы применятьпринцип скользящего среднего, воплощая в материальных блоках при помощи обычных инженерных приемов известную математическую связь междутекущим и предыдущим значениямисигналов в коррелированной последовательности. Однако и в этом случаевозникают трудности и сохраняютсянедостатки, присущие устройствам,основанным на принципе авторегрессии,Если ставится цель преобразоватьнезависимые случайные числа в мар ковскую последовательность случайных квантованных по уровню чисел,имеющих определенное распределениев любой момент времени, то в принципе это всегда можно осуществить ввиде. цепи Маркова. В этом случаенадо каким-то образом осуществитьзапоминание матрицы вероятностейперехода с уровня на уровень значений чисел, причем если имеется К 30 уровней, то матрица в общем случае 857986содержит К" .элементов. Если уровнеймного, то осуществление запоминанияэлементов матрицы является отнюдьне простым делом и сильно ограничивает применимость таких устройств.Наиболее близким техническим решением к предлагаемому изобретениюявляется преобразователь независимых равномерно распределенных случайных чисел в коррелированную последовательность, содержащих тактовыйгенератор, выход которого соединен,с входами генератора равномерно распределенных случайных чисел и датчиков шага, ныход генератора равномерно распределенных случайных чиселсоединен с входом устройства сравнения, выход которого соединен с первым входом сумматора, выход которого соединен с выходной клеммой преобразователя, причем выход датчикашага соединен с вторым входом сумматора 2,Этот преобразователь является материальным воплощением хорошо известного в теории случайных процессовпринципа случайного блуждания, причем его реализация может быть осуществлена рутинными инженерными приемами путем сочетания известных устройств генерирования чисел, ихсравнения и последовательного суммирования.Принцип случайного блуждаииятрадиционно описывается при помощичастицы, через равные промежутки времени движущейся по прямой случайнымобразом на один шаг н одном или дру 35гом направлении с определенными вероятностями.Таким образом, координата блуждающей частицы является случайной величиной, зависящей от ее координатыв предыдущий момент времени, Приуменьшении шага, на который частицаможет двигаться н одном или другомнаправлении, и соответствующем умень шении промежутков времени н пределе,получается процесс, носящий имя Винера,Существенным в традиционном принципе случайного блуждания является то, что вероятности движения частицы в одном или другом направлении не зависят от положения частицы, Как результат этого, перемещение движущей ся частиць, хотя оно и может быть гомогенным процессом, Не может являться стационарным процессом. Соответственно и наиболее близкое к предлагаемому изобретению техническое решение не позволяет генерировать 60 стационарные коррелиронанные последовательности, С другой стороны, в технике цифрового моделирования и при решении различных задач методом статистических испытаний весьма час то требуются последовательности, яв ляющиеся стационарными.Во многих случаях, например при моделировании процессов изменения во времени прочности элементов технических систем и действующей на эти элементы нагрузки, при помощи которых моделируется возникновение отказов, важна не только стационарность случайных процессов, но и принадлежность их распределения к тому или иному классу.Среди различных распределений выдеЛяется нормальное распределение, важное для моделирования технических систем тем свойством, что при заданных среднем значении и дисперсии случайные числа с нормальным распределением обладают наибольшей неопределенностью в смысле Шеннона. В случае традиционного процесса случайного блуждания нормальность процесса обеспечивается автоматически. В то же время обеспечение нормальности стационарного коррелированного процесса далеко не является очевидным как не очевиден и путь преобразования независимых равномерно распределенных случайных чисел в стационарную коррелированную последовательность, обладающую нормальностью.Цель изобретения - расширение функциональных возможностей преобразователя за счет получения стационарных последовательностей случайных чисел.Для достижения поставленной цели в преобразователь, содержащий тактовый генератор, выход которого соединен с входами генератора равномерно распределенных случайных чисел и датчика шага, выход генератора равномерно распределенных случайных чисел соединен с первым входом блока сравнения, выход которого соединен с первым входом сумматора, выход которого является выходом преобразователя, выход датчика шага соединен с вторым входом сумматора, введен блок преобразования уровня, первый вход которого соединен с выходом сумматора, второй вход блока преобразования уровня соединен с выходом датчика шага, а выход блока преобразования уровня соединен со вторым входом блока сравнения. Кроме того, блок преобразованияуровня содержит последовательно соединенные умножитель и сумматор,выход которого является выходом блока, первым и вторым входами которого является соответственно первыйи второй выходы умножителя,На фиг, 1 представлена блок-схемапюеобоазователя, на фиг, 2 - временная диагоамма функционирования устройства.Выход тактового генератора 1 соединен с входами генератора 2 равномерно распределенных случайныхчисел и датчика 3 шага. Выход генератора 2 равномерно распределенныхслучайных чисел соединен с первымвходом блока 4 сравнения, выход которого .соединен с первым входомсумматора 5. Выход сумматора 5 соединен с выходной клеммой 6 и с первымвходом блока 7 преобразования .уровня. Выход датчика 3 шага соединен свторым входом сумматора 5 и с вторымвходом блока 7. Выход умножителя 8соединен с входом второго сумматора 9,15На временной диаграмме функционирования преобразователя (Фиг.2) представлены: 10 - реализация последовательности равномерно распределенныхчисел х, 11 - уровень сравнения р(х),12 - реализация коррелиронанной после-фдовательности случайных чисел, 13момент генерирования независимыхравномерно распределенных случайныхчисел, 14 - момент сравнения независимого равномерно распределенного 25случайного числа с уровнем сравнения,15 - момент изменения числа в коррелиронанной последовательности чисели 16 - момент изменения уровнясравнения по новому числу в коррели- Зорованной последовательности.Преобразование независимых равномерно распределенных случайных чиселв коррелированную стационарную последовательность происходит следующимобразом.Генерированные в определенном такте через промежуток времени д с независимые, равномерно распределенныена интервале значений в соответствующем масштабе от 0 до 1, случайныечисла сравниваются с уровнем сравнения р(х). В результате сравнениявырабатывается сигнал одной полярности или одного значения, если случайное число превышает уровень сравнения, и сигнал другой полярностиили другого значения, если случайное число не превышает уровня сравнения.Постоянное число д.х, нырабатынае Омое в том же такте, либо суммируется с алгебраической суммой х предыдущих чисел дх, обраэуя число х+ дх,либо вычитается иэ него, образуя число х- дх, в зависимости от того, 55сигнал какой полярности или какогозначения вырабатывался после сравнения равномерно распределенного слу:чайного числа с уровнем сравнения,Алгебраическая сумма чисел (х+ Ьхлибо х - д,х) поступает дальше для 60использования при цифровом моделировании: она случайна, поскольку увеличение или уменьшение предыдущегочисла х надх зависит от случая,и коррелирована (точнее марковская) 65 поскольку новый сигнал х д х или х- д х зависит лишь от предыдущего числа х.Изменение уровня сравнения происходит таким образом, что сложение постоянного числа дх к предыдущему числу х происходит с большей вероятностью тогда, когда предыдущее число х (алгебраически) мало и с меньшей вероятностью, когда оно имеет (алгебраически) большое значение. Соответственно вычитание постоянного числа дх иэ гредыдущего числа Х производят с большой вероятностью тогда, когда число х (алгебраически) большое и с малой вероятностью тогда, когда это число имеет (алгебраически) малое значение, Кроме того, если число х имеет среднее значение (которое н последующих рассуждениях, а также на приводимых Фигурах принято равным нулю, чего всегда ожно добиться путем соответствующего выбора начала отчета), то сложение и вычитание двух чисел х и дх происходит с одинаковой вероятностью. Этими приемами обеспечивают стационарность вырабатываемой последовательности случайных чисел.В известном преобразователе отсутствует изменение уровня сравнения нод управлением чисел вырабатываемой последовательности.Принцип изменения вероятностей сложения и вычитания чисел х и Ь х путем изменения уровня сраннения можно описывать при помощи зависимостиРЬ- -- ьЫТгде с (х) - монотонно возрастающая (всторогом смысле) функцияудовлетворяющая условиюк(0)=О, а коэффициент Ь,исходя из свойств вероятности, (при Г(х)ФО) должен отвечать соотношениюос 8 фд-кхВ частности, можно выбрать с(х)х,.1.- 1тогда Р(х) в- ,Ьх ьх2 2Если обозначить вероятность числа х через р(х), то из разностного уравнения баланса вероятностейР(х) Р(х+ЬхН 1-р(х+Ьх)+Р(х-дх)р(-Ьх)при предельном переходе дх-э 0 получается дифференциальное уравнениеф " ЩХ ЙЬР(Х)щО (Й)которое имеет решениеР(х) а ехр(-Ьх ) (Ъ)йгде а - положительная константа,определяемая иэ услония нормировки вероятностей.857986 с(п)=1-п 5( Ьх),30 с(п)= 5 -Ь(ах)Ч 50 60 б 5 Следовательно, путем выбора специального вида для Функции а(х)=хи уменьшения сигнала Ь х можно добиться нормальности (гауссовости)вырабатываемой стационарной последовательности случайных чисел,Таким образом, блок преобразования уровня имеет передаточную характеристику (рассматринаемую какфункцию от х и Дх) в виде формулы (1)Структурно этот блок может состоять,например, из субблока с монотоннойвозрастающей (в строгом смысле) педеаточной характеристикой т(х), отвечающей условию 1(0)0 вход которого соединен с выходом сумматора 5,а выход - с первым входом субблокаумножения, причем второй вход субблока умножения соединен с выходомдатчика 3 шага, и из суммирующегосубблока, вход которого соединен свыходом субблока уножения, а выходс вторым входом устройства 4 сравнения.Нормиронанная конариационнаяфункция с(п) вырабатываемой последовательности случайных чисел имеетвид где и - разность порядковых номеровчисел в последовательности, что длянебольших дх приблизительно заменяется на Отсюда видно, что нормированнаяковариационная функция зависит отпостоянного числа Ьх, на которойпроисходит увеличение или уменьшениеслучайного числа х. С другой стороны,в задачах моделирования Ьх определяет точность воспрОизведения заданной стационарной коррелированнойпоследовательности чисел при помощипредлагаемого преобразователя: суменьшением Ьх увеличивается точностьвоспроизведения,Чтобы при увеличении точностиноспронзнедения не изменялась конариационная функция, одновременно с изменением дх изменяют частоту генерирования независимых равномерно распределенных случайных чисел с соблюдением условия(Нх)/Ьс = сопкой, (6) В качестве конкретного примера предлагаемого преобразователя укажем на его осуществление при помощи периодических импульсон одинаковой формы, но различной амплитуды и полярности.В этом случае все отдельные операции (генерирование независимых ранномерно распределенных по амплитуде импульсов, сравнение амплитуд двух импульсов, генерирование импульсов постоянной амплитуды, сложение 5 10 15 О 5 35 40 55 идти вычитание амплитуд двух импульсов, умножения амплитуд двух импульсов, в совокупности составляющие предлагаемое изобретение, технически осуществимы многочисленными известными путями.Таким образом, преобразователь позволяет получить стационарные коррелированные последовательности случайных чисел из независимых равномерно распределенных случайных чисел, т.е. обеспечивает достижение поставленной перед ним цели.Предлагаемый преобразователь.позволяет получить коррелированные стационарные последовательности с различным распределением, в зависимости от вида функции т(х), Он позволяет воспроизвести заданную марковскую гауссовскую последовательность с любой заданной точностью.К достоинствам преобразователя относится также воэможность получить коррелированную стационарную последовательность случайных чисел с одно- модальным распределением прямо иэ последовательности независимых равномерно распределенных чисел, минуя. их промежуточное преобразование н последовательность независимых чисел с одномодальным распределением,Формула изобретения 1. Преобразователь независимых равномерно распределенных случайных чисел в коррелированную последовательность, содержащий тактовый генератор, выход которого соединен с входами генератора равномерно распределенных случайных чисел и датчика шага, выход генератора равномерно распределенных случайных чисел соединен с первым входом блока сравнения, выход которого соединен с первым входом сумматора, выход которого является выходом преобразователя, выход датчика шага соединен с вторым входом сумматора, о т л и ч а ю щ и й с я тем, что, с целью расширения функциональных возможностей преобразователя за счет получения стационарных последовательностей случайных чисел, он содержит блок преобразования уровня, первый вход которого соединен с выходом сумматора, второй вход блока преобразования уровня соединен с выходом датчика шага, а выход блока преобразования уровня соединен со вторым входом блока сравнения. 2. Преобразователь по п.1, о т л и ч а ю щ и й с я тем, что блок преобразования уровня содержит последовательно соединенные умножитель и сумматор, выход которого является выходом блока, первым и вторым9 857986 входами которого являются соответственно первый и второй входы умножителя.Источники информации, принятые во внимание при экспертизе г. / рЯ Заказ 7245/7 Подписноеи г.1 11 11 11 111 1 1. Авторское свидетельство СССР 9590760, кл. С 06 Г 7/58, 1976.2. Розанов Ю.А. Случайные процессы. М., "Наука", 1979, с. 58 (прототип). ПП "Патентф,Род, ул. Проектная, 4