Генератор случайных чисел

 

ОПИСАНИ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

Республик (61)Дополнительное к авт. свид-ву (22) Заявлено 11. 05. 81 (21) 3293633/18с присоединением заявки Мо (23) Приоритет

Опубликовано 1Ы282, Бюллетень 11о

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

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

Дата опубликования описания 15. 12.

3M.A.Рабинович, P.Г.Апокина и E.Г.Косарева

l -с „

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

"Энергосетьпроект" (72) Авторы изобретения (71 ) 3a яв и тель (54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ

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

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

Известно устройство генерации гауссовых случайных чисел с заданным энергетическим спектром (или с заданной автокорреляционной функцией) fl).

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

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

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

При работе прототипа по сигналам тактового генератора формируется одно равномерно распределенное число (в общем случае комплексное) и осуществляется выборка из первого блока регистров памяти очередного значения весового коэффициента (также в общем случае комплексного). В перемножи1О теле эти два числа перемножаются, а результат записывается в буферную память. На следующих тактах работы тактового генератора указанная процедура повторяется до тех пор пока не заполнится вся буферная-память, содержащая М регистров. После заполнения буферной памяти включается в работу блок быстрого преобразования Фурье, на выходе которого 20 формируется последовательность гауссовых случайных чисел с заданным энергетическим спектром. Для успешной работы прототипа значения весовых коэффициентов должны быть пропорцио- 25 нальны корню квадратному из значений энергетического спектра на соответствующих частотах.

Несмотря на то, что устройствопрототип является наиболее ест- 30 рым из известных устройств генерации гауссовских случайных чисел с произвольно заданным спектром, вычислительные затраты в нем достаточно велики. Эти затРаты составляют для 35 последовательности из Н гауссовых чисел примерно N(og N комплексных арифметических операций сложения

N(1+1/26oñó Н) комплексных операций умножения. Недостатком прототипа, . 40 таким образом, является большой объем вычислительных затрат (малое быстродействие) при генерации гауссовых случайных чисел с заданным энеРгетическим спектРом. 45

Цель изобретения - повышение быстродействия устройства.

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

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

На фиг.l приведена блок-схема предлагаемого генератора случайных чисел с заданным энергетическим спектром; на фиг.2 — схема блока формирования весовых коэффициентов.

Устройство содержит генератор 1 тактовых импульсов, к первому выходу которого подключены последовательно соединенные генератор равномерно распределенных случайных чисел 2, блок умножения 3, первый блок памяти 4 и блок быстрого преобразования Уолша 5. Второй выход генератора 1 соединен с управляющим входом блока формирования весовых коэффициентов б, на информационные входы которого подключены выходы второго блока памяти 7. Третий выход генератора 1 через элемент задержки 8 подсоединен к ключу 9. Блок формирования весовых коэффициентов б состоит из последовательно соединенных первого блока памяти 10, первого коммутатора 11, квадратора

12, сумматора 13, нелинейного преобразователя 14, выполняющего извлечение квадратного корня из входной величины, умножителя 15 и второго блока памяти lб. На второй вход

Умножителя 15 включен выход второго коммутатора 17. Второй выход генератора 1 подключен к управляющим входам коммутаторов ll и 17, а на входы второго коммутатора 17 включены выходы блока памяти 7. Выход бло981999 ка памяти 16 подключен ко входу ключа 9.

Генератор работает следующим образом.

По сигналам генератора 1 в гене5 ратор 2 генерируются случайные независимые равномерно распределенные числа, которые поступают на первый вход блока умножения 3. Сигналы тактового генератора поступают также на управляющий вход блока формирования весовых коэффициентов б. По этому сигналу в блоке б формируется очередной весовой коэффициент, который ключом 9 по сигналу тактового генератора 1 отправляется на второй вход блока умножения 3. Элемент задержки 8 введен для того, чтобы сигналы тактового генератора 1 поступали на ключ 9 только после того как в блоке 6 закончилось формирование очередного весового коэффициента.

Для пояснения работы устройства приведем математическое обоснование

его работы, Пусть F(2) обобщенное дискретное преобразование Фурье взвешенной последовательнЬсти N комплексных случайных ограниченных и независимых величин

2„= Хк+1У„, К = 0,1,..., Ы-1 й- I (1)

"(2)=Я „=,„i 1 р= „ф Y. L ZV (N )K), к=о" где 4 1 - последовательность век совых коэффициентов; 35

Qf}1,K) — полная,ортонормированная система базисных функций при разложении последовательности „ в обобщенный ряд Фурье.. 40

В p) показано, что если

Ч(И,К) =eXpg —" — 1система дискретных

/ 27 (К1 н экспоненциальных функций-,n,K=0,1,..., N-1, то функция распределения случайных величин p>, n = 0,1,...,N- -1 сходится к функции гауссовского закона, как 0 (1/-/Й)..

Автокорреляционная функция последовательности ) р 1 равна:

И

® Х + 2 Р ><+(((2) и — m, Р= 0 1,..., N — l.

Значения L имеют физический смысл

К отсчетов энергетического спектра.

В предлагаемом устройстве вместо дискретного преобразования Фурье используется дискретное преобразование Уолйа. При этом ставится и реша- 0 ется задача получения последовательности гауссовых случайных величин с энергетическим спектром ) L, К = — 0,1,...,И-1) или, что тоже, с корреляционной функцией R(t). 65

Разложим последовательность р по базису дискретных экспоненциальных функций на интервале (О, N-11 и по базису дискретных функций Уолша

Й-л к -к з(ИуК)

4 и 3

Р= -2 p„Z„q„(,к), где коэффициенты разложения представлены в виде (К) =Ь 2к и y (K) =

Я.

=g2к соответственно. Известно, что спектральные коэффициенты разложения связаны друг с другом соотношением

Р (К) = y 9„(и)Ф(И,К), 1=О (4) где

1 ф(и,к)= и Y. 9>(w т)9 (4,e) (5) Функция называемая ядром Фурье. Ядра

Фурье составляют ортонормированную систему функций

0 если тп у и

Из (4) имеем ,д Й-(й-4

И,(к) (= y „(Р)ф (Р,К)2 "„(Е)ф (Е,К)=

Р 0" eO (7)

=2,S„(()Sф (Е) ф(Р,К)Е (ЕК) =

15 (Р)! !С (рК)!

Усредняя последнее равенство по множеству получаем н л (к) (1(к) (= 57-(к) Z g Ь)1ф(Р,К)! (8) р=о (К)= / 2 ь Ы ф(р,к)((9) р=о

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

Эти значения хранятся в блоке памяти 7.

Вычисление весовых коэффициентов )1(к) необходимо выполнить только один раз. Поэтому, их можно считать заданными и пренебречь вычислительными затратами на их получение.

Оценим выигрыш в числе арифмети-. ческих операций, даваемый предлагаемым устройством, при генерации

N гауссовских случайных чисел со значениями энергетического спектра

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

981999

1 тельные затраты в прототипе составляют примерно N комплексных опера1 ций сложения и N(1+-fog N) комплекс2 ных операций умножения. Более удобно.перейти к арифметическим опера- . циям над действительными числами.

При работе прототипа необходимо. Реализовать примерно 2N+3Nfog

2N(2+gog

0(y X +jy — последовательность комК плексных чисел).

В предлагаемом устройстве комплексная последовательность случайных чисел 2К, К = 0,1,...,N 1 умножается соответственна на действительныЕ числа . На это требуется 2N операций умножения., Для выполнения дискретного преобразования Уолша над комплексной последовательностью с(К ;,Г,, k = 0,1,,(N-1) необходимо выполнить примерно 2N8og

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

Ct . Константа С для современных вычйслительных устройств лежит в пределах 1-10.

Выигрыш Т, даваемый предлагаемым устройством, составляет + О Ч - „,(1 (og >)(н. 1 сл сл 1 м сл

Ы МОР,2 М+ 2- ЧМН сл а.

Для вычислительных устройств с фиксированной арифметикой . t 5t „ .

В этом случае

Чм . 2йжа ъж М1о а N+20N

Наиболее типичные значения N лежат в пределах 128-1024. Для таких значений N выигрыш Т в вычислительных затратах составляет примерно 3-

4 раза.

Блок формирования-весовых коэффициентов 6 работает следующим образом (см.фиг.2), Сигнал генератора 1 поступает на управляющие входы первого и второго коммутаторов 11 и 17.

По этому сигналу из блока памяти 10 осуществляется последовательная выборка первым коммутатором 11 значений ядер Фурье Ф(п,К) для различных значений k и фиксированного значения и равного номеру генерируемого равномерно распределенного числа. Эти значения Ф(п k) возводят ся в квадрат квадратора 12 и суммируются сумматором 13. После завершения определения „- (Ф(п,k))+для

35 где o((K) — отсчеты требуемого энергетического спектра последовательности гауссовых чисел и Ф(п,К)

40 значения фУнкции ядер ФУРье (cL(K)) и

C(n,К) считаются заданными °

Для наиболее тийичных последовательностей длительностью 128-1024 чисел выигрыш в вычислительных за45 тратах предлагаемым устройством по сравнению с прототипом составит

3-4 раза.

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

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

Предлагаемое устройство найдет применение в цифровых системах моделирования динамических объектов. Эко60 номический эффект от применения предлагаемого устройства составит порядка 20-30 тыс.руб в год.

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

1. Генератор случайных чисел, 65 содержащий генератор тактовых им5

30 всех n = 0,1,2,...N-1, из полученной суммы извлекается квадратный корень нелинейным преобразователем

14. Результирующее значение поступает на первый вход умножителя 15. На второй вход умножителя 15 поступает выбранное вторым коммутатором 17 значением.(К), численно равное корню квадратному из требуемого значения энергетического спектра последовательности гауссовых случайных чисел.

Полученные весовые коэффициенты накапливаются в блоке памяти 16.

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

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

p(x)=d(<)4Q )ф(.и,к)! -, и=о

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

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

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

1. Кори Г. Моделирование случай-. ных процессов на аналоговых и анало« го-цифровых машинах. М., Мир, 1968.

2. Миркин Л.И., Рабинович М.A. u

Ярославский Л.П. Метод генерирования коррелированных гауссовских псевдослучайных чисел на ЭВМ. ЖВМ и МФ т.12 Р 5, 1972 (прототип) .

981999

Юит. tom оку угу

Составитель A.Êàðàñoâ

Техред К. Мыцьо Корректор С.Шекмар

Редактор М.Товтин

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

Заказ 9713/69 Тираж 731 Подписное

ВНИИПК Государственного комитета СССР по делам изобретений н открытий. 113035, Москва, Ж-35, Раушская наб., д. 4/5