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

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

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик оп949788 (61) Дополнительное к авт. свид-ву (22) Заявлено 29. 12. 80 (21) 3225213/18-21 с присоединением заявки № (23) Приоритет

Опубликовано 070882. Бюллетень ¹29

Дата опубликования описания 07. 08. 82

151) М. Кл.з

Н 03 К 3/84

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

СССР по делам изобретений и открытий (53) УДК 621. 373. .4(088.8) 7

A.È.Âîâ÷åöêèé, И.В.Кудрявцев, Е.Г.Никандров, С.С.Поспелов и В.С.Рабкин: ( (72) Авторы изобретения

* с

1 (71) Заявитель (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

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

Известен генератор псевдослучайных чисел, принцип работы которого основан на суммировании выходных сигналов (1) .

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

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

В данном генераторе при достаточно больших n (n — количество разрядов счетчика импульсов) распределение генерируемых чисел стремится к нормальному. Математическое ожидание

Е = n/2 — М о, где М о — число, соответствующее исходному состоянию счетчика в начале каждого цикла. Время корреляции генерируемой последовательности определяется числом ш.

Дисперсия D n/4. Из данной формулы видно, что, изменяя величину и, можно получить числа с различной дисперсией. Однако такая регулировка возможна лишь в ограниченных пределах.

Действительно, как отмечено выше, 949788

10

4Q закон распределения генерируемых чисел хорошо согласуется с нормальным при достаточно больших и (п ), 32-40). При этом дисперсия

D ) и-10, что и является нижней границей D изменения дисперсии. При увеличении и прямо пропорционально растет время формирования каждого псевдослучайного числа, т.е. снижается быстродействие генератора, что накладывает ограничение на изменение дисперсии сверху, кроме того, при регулировке дисперсии путем изменения величины и происходит смещение величины математического охлаждения E = п/2 - Мо. 15

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

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

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

На чертеже представлена функциональная схема генератора псевдослучайных чисел, Генератор псевдослучайных чисел содержит регистры 1 и 2 сдвига, счетчик 3 импульсов, сумматор 4 по модулю два, коммутатор 5, первый делитель 6 частоты, генератор 7 импульсов, второй делитель 8 частоты, блок

9 задания знака, преобразователь 10 кода, первый преобразователь 11 кодчисло импульсов, буферный регистр

12 сдвига, элемент 13 задержки, блок 14 записи кода и второй преобразователь 15 код-число импульсов.

Генератор псевдослучайных чисел работает следующим образом.

В начале цикла работы по сигналу с выхода генератора 7 импульсов, задержанному элементом 13 задержки, происходит запись кода исходного состояния иэ преобразователя 10 кода через блок 14 записи кода в счетчик

3 и начальная установка первого делителя б, На тактовый вход регистра

1 сдвига поступает пачка из и ) импульсов, где k — разрядность регистра 1 сдвига, Первые m(m < п) тактов регистр 1 с сумматором 4 по модулю два работают как генератор бинарной псевдослучайной последовательности. Затем с выхода делителя

6 приходит сигнал на коммутатор 5, который переключает выходы сумматора

4 по модулю два регистра 2 так, что регистр 1 и регистр 2 оставшиеся n-m тактов работают в режиме кольцевого регистра сдвига. При этом из регистра 2 в кольцевой регистр включаются только n-k+m разрядов.

Таким образом, на вход счетчика 3 поступают и символов псевдослучайной последовательности (ПСП) и по окончании цикла работы генератора в счет,чике 3 сформировано псевдослучайное число, равное числу единиц в этом отрезке ПСП, а в регистре записана фаза ПСП, отличающаяся от исходной на в тактов.. Следующий отрезок ПСП имеет и-m символов, общих с предыдущим. Сформированное в счетчике 3 число по сигналу с генератора 7 импульсов переписывается в буферный регистр 12, в котором осуществляется сдвиг этого числа по сигналам, посту949788 пающим с первого преобразователя 11 код-число импульсов. Описанный цикл работы генератора повторяется при формировании каждого нового числа.

Цсходное состояние счетчика 3 определяет .математическое ожидание

Е распределения формируемых псевдослучайных чисел. Коэффициент деления

m делителя б задается по управляющему входу и определяет время корреляции.

При достаточно больших п распреде-10 ление весов отрезков (числа единиц в отрезках) ПСП стремится к нормальному. Математическое ожидание Е этого распределения определяется зависимостью

Е = — — М и

50 где Мо - число, соответствующее исходному состоянию счетчика

3 в начале каждого цикла формирования псевдослучайного числа.

Изменяя исходное состояние счетчика 3, получаем различные значения математического ожидания распределения.

Если m n, то генерируемые числа коррелированы, Второй делитель 8 и блок 9 задания знака также служат для получения колебательного характера автокорелляционной функции.

Изменение дисперсии распределения чисел, формируемых предлагаемым генератором, происходит следующим образом. 35

При сдвиге чисел в буферном регистре 12 сдвига происходит изменение этих чисел в .+ раз, где число тактовых импульсов, поступающих на буферный регистр 12 с преобраэо- 40 вателя 11 код-число импульсов и соответствующее коду, поступающему иэ преобразователя 10 кода. Знак "+" соответствует сдвигу влево, знак сдвигу вправо. 45

Как известно, дисперсия равна и

D P (х,. - x )

1= где х- случайные числа; х — математическое ожидание распределения; р - вероятность появления чи1 сел х..

Из формулы видно, что при изменении всех чисел x„- в 2-. " раз происходит изменение дисперсии в 4 " раз, т.е. каждый сдвиг изменяет дисперсию в 4 раза. Таким образом, введение в генератор буферного регистра 12 сдвига позволяет простыми средствами изменять дисперсию формируемых чисел в широких пределах.

Дискрет изменения дисперсии зада-. ется вторым преобразователем 15 кодчисло импульсов, который изменяет длину пачки тактовых импульсов, по- 65 ступающих на регистры 1 и 2 .сдвига и первый делитель б частоты, в соответствии с кодом, поступающим иэ преобразователя 10 кода. При этом изменяется длина m отрезков ПСП, из которых формируются псевдослучайные числа, и, следовательно, дисперсия чисел, равная в случае биномиального распределения

D = np(l — р), где n — объем выборки (длина отрезка ПСП); р — вероятность появления единицы на выходе регистра, равная

Х- 1

2к где k — число разрядов основного регистра.сдвига 1.

При больших К р — 1/2 В практических случаях k 7 30.

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

ПСП изменяется в ограниченных пределах пп, „/п,п,п= 4, а широкий диапазон изменения дисперсии обеспечивается введением буферного регистра 12 сдвига.

Так как при изменении п изменяется и величина математического ожидания распределения, которая равна

n/2, для компенсации этого изменения с помощью преобразователя 10 кода, формирующего код начальной установки, и блоком 14 записи производится начальная установка счетчика 3 так, что математическое ожидание остается постоянным при любом изменении и.

Так, например, при начальной записи в счетчик 3 кода n/2 математическое ожидание распределения генерируемых чисел равно нулю.

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

Диапазон изменения псевдослучайных чисел равен п„,„х2 ", где п максимальная длина отрезка ПСП. дискрет изменения дисперсии h+

V(l - Р).

Минимальное значение дисперсии

Пр1п пщ1п Р(" Р) 4

Максимальное значение. дисперсии

0 „п „.Р(1 - »4

ДЕ Пп1 11 nn, „

949788 быявд f а

Следов ательно, дисперсия формируемых псевдослучайных чисел может изменяться в широких пределах и при, этом время формирования чисел нв превосходит величины 1, „= 4й„,„„„;

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

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

Генератор псевдослучайных чисел, содержащий последовательно соединен- 2р ные первый делитель частоты, коммутатор, первый регистр сдвига, второй регистр сдвига и счетчик импульсов, второй вход коммутатора через сумматор по модулю два соединен с первым выходом первого регистра сдвига, второй вход которого соединен с вторым входом первого делителя частоты и второго регистра сдвига, группа выходов которого соединена с группой входов коммутатора, а также генера" тор импульсов,:второй делитель час-, тоты, вход которого соединен с первым входом первого делителя частоты, а выход второго делителя частоты соединен с первым входом блока задания знака, второй вход сумматора по модулю два соединен с первым выходом первого регистра сдвига, о т л и ч а ю шийся тем, что, с целью

ВНИИПИ Заказ 5768/46

Тираж 959 Подписное

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

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

1. Патент Франции Р 2239817, кл. Н 03 К 3/84, 1976.

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

Р 656086, кл. G 07 С 15/00, 09.02.77.