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

 

Союз Советскнх

Соцналнстнческнх

Реснублнк

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИ ВТЕЛЬСТВУ (61) Дополнительное к авт. сеид-ву (22) Заявлено 100180 (21) 2868332/18-24 (51)м

G Об F 7/58 с присоединением заявки N9 (23) Приоритет

Государствеиимй комитет

СССР по делам изобретений и открытий

Опубликовано 23.0881. Бюллетень No 31

Дата опубликования описания 230881

° (53) УДК 681. 325 (088. 8) (72) Автор изобретения

А,А.Êooðò (71) Заявитель (54) ПРЕОБРАЗОЬАТЕЛЬ НЕЗАВИСИМЫХ РАВНОМЕРНО

РАСПРЕДЕЛЕННЫХ СЛУЧАЙНЫХ ЧИСЕЛ В КОРРЕЛИРОВАННУЮ

ПОСЛЕДОВАТЕЛЬНОСТЬ

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

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

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

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

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

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

Наиболее близким техническим решением к предлагаемому изобретению является преобразователь независимых равномерно распределенных случайных чисел в коррелированную последовательность, содержащих тактовый генератор, выход которого соединен, с входами генератора равномерно распределенных случайных чисел и датчиков шага, выход генератора равномерно распределенных случайных чисел соединен с входом устройства срав- 15 нения, выход которого соединен с первым входом сумматора, выход которого соединен с выходной клеммой преобразователя, причем выход датчика шага соединен с вторым входом сумма- 3() тора (2), Этот преобразователь является материальным воплощением хорошо известного в теории случайных процессов принципа случайного блуждания, причем его реализация может быть осуществлена рутинными инженерными приемами путем сочетания известных устройств генерирования чисел, их сравнения и последовательного суммирования.

Принцип случайного блуждаиия традиционно описывается при помощи частицы, через равные промежутки времени движущейся по прямой случайным образом на один шаг в одном или дру35 гом направлении с определенными вероятностями.

Таким образом, координата блуждающВй частицы является случайной вели- 49 чиной, зависящей от ее координаты в предыдущий момент времени. При уменьшении шага, на который частица может двигаться в одном или другом направлении, и соответствующем умень-45 шении промежутков времени в пределе, получается процесс, носящий имя Винера.

Существенным в традиционном прин- 50 ципе случайного блуждания является то, что вероятности движения частицы в одном или другом направлении не зависят от положения частицы. Как результат этого, перемещение движущейся частиць, хотя оно и может быть гомогенным процессом, Не может являться стационарным процессом. Соответственно и наиболее близкое к предлагаемому изобретению техническое решение не позволяет генерировать 6О стационарные коррелированные последовательности. С другой стороны, в технике цифрового моделирования и при решении различных задач методом статистических испытаний весьма час- 65 то требуются последовательно -ти, яв ляющиеся стационарными.

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

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

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

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

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

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

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

На фиг. 1 представлена блок-схема пюеобоазователя, на фиг. 2 - временная диагоамма функционирования устройства.

857986

Выход тактового гене)затора 1 соединен с входами генератора 2 равномерно распределенных случайных чисел и датчика 3 шага. Выход генерато)эа 2 равномерно распределенных случайных чисел соединен с первым входом блока 4 сравнения, выход которого .соединен с первым входом сумматора 5. Выход сумматора 5 соединен с выходной клеммой 6 и с первым входом блока 7 преобразования .уровня. Выход датчика 3 шага соединен с вторым входом сумматора 5 и с вторым входом блока 7. Выход умножителя 8 соединен с входом второго сумматора 9.

На временной диаграмме функционирования преобразователя (фиг.2) представлены: 10 — реализация последовательности равномерно распределенных чисел R, 11 — уровень сравнения р(x), 12 — реализация коррелиронанной после- довательности случайных чисел, 13 момент генерирования независимых равномерно распределенных случайных чисел, 14 — момент сравнения независимого равномерно распределенного Q$ случайного числа с уровнем сравнения, 15 — момент изменения числа в коррелиронанной последовательности чисел и 16 — момент изменения уровня сравнения по новому числу в коррели- yg рованной последовательности.

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

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

Постоянное число ь.х, вырабатынае- 5О мое в том же такте, либо суммируется с алгебраической суммой х предыдущих чисел Д х, обра э уя число х+ A x, либо вычитается иэ него, образуя число х- ьх, в зависимости оТ того, 55 сигнал какой полярности или какого значения вырабатывался после сравнения равномерно распределенного слу:чайного числа с уровнем сравнения.

Алгебраическая сумма чисел (х+ Ьх либо x - - х) поступает дальше для 60 использования при цифровом моделировании: она случайна, поскольку увеличение или уменьшение предыдущего числа х надх зависит от случая, и коррелирована (точнее марковская) 65 поскольку новый сигнал х «,а х или х- д х зависит лишь от предыдущего числа х.

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

Соответственно вычитание постоянного числа i1х иэ гредыдущего числа g производят с большой вероятностью тогда, когда число х (алгебраически) большое и с малой вероятностью тогда, когда это число имеет (алгебраически) малое значение. Кроме того, если число х имеет среднее значение (которое н последующих рассуждениях, а также на приводи) ых фигурах принято равным нулю, чего всегда )ожно добиться путем соответствующегого выбора нач ала отчета ), то сложение и вычитание двух чисел х и h,x происходит с одинаковой вероятностью. Этими приемами обеспечивают стационарность вырабатываемой последовательности случайных чисел.

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

Принцип изменения вероятностей сложения и вычитания чисел х и Ь х путем изменения уровня сраннения можно описывать при помощи зависимости

P(X)- — — — ЬМ 61r (() .1 1

Я 1 где f (x) — монотонно возрастающая (н сторогом смысле) функция„ удовлетворяющая условию к(0)=О, а коэффициент Ь, исходя из свойств вероятности, (при Г(х)ФО) должен отвечать соотношению

О аЯ фд- гх

В частности, можно выбрать )(х)х, .1.- 1 тогда P (x) — — . Ьх-лх,.

2 2

Если обозначить вероятность числа х через р(х), то из разностного уравнения баланса вероятностей

P(x) P(x+hx)(l-р(к+ах)+Р(x-bx)р(-bx) при предельном переходе х-э О получается дифференциальное уравнение

° Яф 2ЬР()=О, () которое имеет решение

P(x)а ехр(-Ьх ), (Ъ)

2 где а — положительная константа, определяемая иэ услония нормировки вероятностей.

857986

c(n)=1-nb(Ьх), (4) 30 с(п )= L -b(X) ) 50

d0

Следовательно, путем выбора специального вида для функции а(х)=х и уменьшения сигнала Ь х можно добиться нормальности (гауссовости) вырабатываемой стационарной последовательности случайных чисел.

Таким образом, блок преобразования уровня имеет передаточную характеристику (рассматринаемую как функцию от х и дх) в виде формулы (1)

Структурно этот блок может состоять, например, из субблока с монотонной возрастающей (в строгом смысле) педеаточной характеристикой f (x), отвечающей условию f (0) О, . вход которого соединен с выходом сумматора 5, а выход — с первым входом субблока умножения, причем второй вход субблока умножения соединен с выходом датчика 3 шага, и из суммирующего субблока, вход KQTopoI соединен с выходом субблока уножения, а выход с вторым входом устройства 4 сравнения.

Нормиронанная конариационная функция с(п) вырабатываемой последовательности случайных чисел имеет вид где n — разность порядковых номеров чисел в последовательности, что для небольших нх приблизительно заменяется на

Отсюда видно, что нормированная ковариационная функция зависит от постоянного числа b.x, на которой происходит увеличение или уменьшение случайного числа х. С другой стороны, в задачах моделирования b,x определяет точность воспрОизведения заданной стационарной коррелированной последовательности чисел при помощи предлагаемого преобразователя: с уменьшением h,x увеличивается точность воспроизведения.

Чтобы при увеличении точности носпронзнедения не изменялась конариационная функция, одновременно с изменением дх изменяют частоту генерирования независимых равномерно распределенных случайных чисел с соблюдением условия (нх) />t = const, (6) В качестве конкретного примера предлагаемого преобразователя укажем на о осуществление при помощи периодических импульсон одинаковой формы, но различной амплитуды и полярности.

В этом случае все отдельные операции (генерирование независимых ранномерно распределенных по амплитуде импульсов, сравнение амплитуд двух импульсов, генерирование импульсов постоянной амплитуды, сложение

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

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

Предлагаемый преобразонатель.позволяет получить коррелированные стационарные последовательности с различным распределением, в зависимости от вида функции f(x). Он позволяет воспроизвести заданную марковскую гауссовскую последовательность с любой заданной точностью.

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

Формула изобретения

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

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

857986

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

9590760, кл. G 06 F 7/58, 1976.

2. Розанов Ю.A. Случайные процессы. М., "Наука", 1979, с. 58 (прототип). входами которого являются соответственно первый и второй входы умножителя.

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

Фиг. /,p(4

Заказ 7245/79

Подписное

Фиа

l!

I! ! I ! ! ! 1!

lll ! l ! ! ! ! !! ! !

l! ! !! ! !

I ! ! ! !!! !!

l ! ! ! !

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