Многоканальный генератор псевдослучайных чисел

 

-.-,-.с- <->н )Я .- АЙ ...,:;,:(. =СНА%

ЯА Й т цБА »739603

ОПИСАН ИЕ

ИЗОБРЕТЕНИЯ

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

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

Республик

Ф л т

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6() jlîïîëíèòåëüíîå к авт. свил-ву (22) Заявлено 25.01.78 (2() 2571997/18-24 (51) М. Кл.

Cj07 С 15/00

Cj 06 F 1/02 с присоединением заявки .%.Гееударстеенный комитет (23 ) Приоритет

Опубликовано 05.06.80, Бюллетень № 21 йо денем изобретений н открытий (53) УДК 681.325 (088.8) йата опубликования описания 08.06.80

I (72) Авторы изобретения

В. Н. Ярмолнк и А. И. Ковалев (7I) Заявитель

Минский радиотехнический институт (54) МНОГОКАНАЛЬНЫЙ ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ

ЧИСЕЛ

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

Известен генератор псевдослучайных чисел на основе ттт-разрядного регистра сдвига и сумматора по модулю два в цепи обратной связи. Подобный ГПСЧ

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

Как известно, такая схема может ге15 нерировать циклическую двоичную последовательность максимальной длины (М-последовательность) с периодом

М = 2 .-1, где ти -разрядность регист111 ра сдвига, стаглстические свойства которой аналогичны свойствам последовательности равновероятных символов 0 и 1.

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

Однако такой генератор позволяет получить только один канал. При использовании псевдослучайных чисел в стохастических ВМ необходимо несколько каналов, независимых псевдослучайных чисел. Быстродействие ГПСЧ, при необходимости получения независимых 5-разрядных псевдослучайных чисел, оказывается в 6 раз ниже его тактовой частоты.

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

3 73960 гейерирующих последовательности ма| симальной длины. Генератор содержит задающий генератор импульсов,,И -разрядный регистр сдвига с сумматором по модулю два в цепи обратной связи, A1 -разрядный регистр сдвига с сумма5 тором по, модулю два в цепи обратной

Связи, " сумматоров по модулю два.

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

- К= 2 - 1 и М 2 = 1 являются взаимно простыми числами, можно получить некоррелированные в пределах Я тактов работы, периода исходной последовательности большей длины (при И 7 п1 ), псевдослучайные последовательности путем сложения по модулю два состояний двух "разрядов регистров (no одному от каждого). Свойства таких последовательностей близки свойствам М-последовательностей. Максимальное число каналов, одновременно генерируемых такта ГПСЧ, равно И + П1 — 1. Число независимых каналов на основе двух регистров сдвига равно ll+ È1 - 1, (21.

При необходимости получения большого числа каналов, надо пропорциональ но ему увеличивать разрядности регистров сдвига п и Ф, что приводит к значитель= ным аппаратурным затратам, неравномерности распределения псевдослучайных чисел, так как генерируемые последовательности являются- участками последовательности С =С1фЬ,где0 — последовательность периода 5, à b — периода М, уменьшении периода работы генератора a ll+ K — 1 раз вследствие разбиения последовательности С на отдельные участки; однозначности соответствия,значений периодов N u Q, ко торые должны быть только взаимно прюстыми числами.

I0 состоянии генератора необходимо записать единицу в 1 + 1 разряд регистра сдвига (1 -й разряд подключен ко. входу сумматора 3 в цепи обратной связи регистра) и нули в остальные разряды.

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

20 входу сумматора 4, а наличие нуля — о том, что не подключается. Для каждого канала необходим определенный сдвиг

К С (где К 1,2,... ), а следовательно ему присущ определенный код в регистре, 25 строго определяющий структуру логи веских связей. Очевидно, что число разрядов, которые надо подключить ко входамсумматоров 4, зависит от числа единиц в коде регистра, который фиксируют че30 реэ К С тактов работы, В среднем число единиц в регистре сдвига за период М работы генератора равно И /2. Это значит, что для организации одного канала на основе N-разрядного регистра сдви35 ra необходим. сумматор по модулю два с hl/2 входами. Обычно производят оптимизацию оборудования, что предусматривает при моделировании сдвиг не на

К"С символов, а число близкое к нему.

40 Целью является получение кода с минимальным числом единиц. В результате добиваются сокращения удельных затрат на канал до сумматора с 1 /4 входами.

Лучшего результата добиться трудно (31.

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

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

При этом уменьшается период работы генератора до

2 -1

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

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

В эжм генераторе отдельные каналы

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

Недостатком также является увеличение неравномерности распределения чисел при большом числе каналов. Это объясняется неравенством числа единиц

03 6 парно подключены ко входам К сумматоров по модулю два, а выход о-го элемента ИЛИ вЂ” ко второму входу сум матора К (где P = и-};е}=,<.-.,п -<;;

5 P=9....,Ъ = },2,... 2 — —., +-} ). . д 3lrl

5 7396 и нулей на отдельных участках М-последовательности.

Необходимы значительные удельные затраты оборудования на реализацию каждого канала. Для формирования таких каналов требуется использовать в среднем М/4 разрядов регистра сдвига, что приводит к необходимости применять либо сложные многовходовые сумматоры по модулю два, либо несколь- t0 до двухходовых сумматоров (полусумматоров).

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

Недостатком также является сложность 20 подготовки к построению многоканального ГПСЧ, которая предусматривает моделирование на ЭВМ исходной М-последовательности.

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

Поставленная цель достигается тем, что в многоканальный генератор псевдо- 35 случайных чисел, содержащий задающий генератор импульсов, }и-разрядный триггерный регистр сдвига с сумматором по модулю два в цепи обратной связи, причем выход задающего генератора под- 40 ключен ко входам синхронизации триггеров регистра сдвига, вводятся две группы элементов И, группа элементов ИЛИ, группа сумматоров по модулю два, причем к первому входу 1-го элемента И 45 первой группы подключен прямой выход первого разряда регистра сдвига, а ко второму входу .— прямой выход 1+ 1-го разряда регистра сдвига (} = 1, 2,3, ..., } п-1), к первому вхо- 50 ду } -го элемента И второй группы подключен инверсный выход первого разряда регистра сдвига, а ко второму— прямой выход g -ro разряда регистра (5 -2,3,..., m; } = И}+ 1), причем выходы - -х элементов И первой и второй групп подключены ко входам

} -х элементов ИЛИ, выходы которых поНа чертеже приведена схема пред- лагаемого генератора при }}}=8.

Генератор содержит задающий генератор 1 импульсов, 8-разрядный регистр 2 сдвига с сумматором по модулю два в цепи 3 обратной связи, группу элементов 4 И, группу элементов 5 И; группу элементов 6 ИЛИ, группу сумматоров 7 по модулю два.

Задающий генератор импульсов предназначен для синхронизации работы всего устройства, регистр сдвига с сумматором по модулю два в цепи обратной связи — для получения псевдослучайной последовательности едчниц и нулей с периодом, равным 2 -1, две группы

Щ элементов И и группа элементов ИЛИ— для получения последовательностей нулей и единиц, вероятность появления, которых равна 0,5, а период последо- .

>И вательностей равен 2 1, группа сумматоров по модулю два — для получения большого числа каналов, генерирующих ПС числа.

Независимый канал, генерирующий

ПС последовательность, получают, используя свойство М-последовательности, заключающееся в том, что ве} оятность появления двух определенных символов (11,10,01,00) и любых двух разрядах регистра сдвига равно 1/4.

Если обозначить прямой выход разряда регистра сдвига Х, а инверсный выход } ., (1=1,2,..., }и), то реализацию таких последовательностей можно выра"зить математически следующим образом:

Ч„=х„х х„х 2.-Х Х+ХХ

Х+ХХ

3 ", 4 } Э

V -XX+X x

4 1 5 } 6

Ч -Х 6 Х Х

Ч =ХХ тХХ

6 1 7

Получают последовательности Ч.,— Ч.} с вероятностью появления 1 или О, равНоН 1/2. Для получен. :«Ч„складывают последовательности Х,„Х и Х„Х, с вероятностью появления единицы, равной

1/4» Возможность появления единицы — -;щ.,»р, . »," .» ., у,:..» ф @»,—.:.-,.„., @фу,;,дну »р@"р .с-.,",;». щ -,„,,д.»;- —,. и:.» ..

739603

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

1 при Х.т= 1, Х2 = 1, а второе

" при X О, Х, =1 Число таких последовательностей N =тн-1. Простое сложение

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

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

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

В зависимости от состояния разрядов регистра сдвига на выходах элементов

4,5, 6,7 получаю г последовательности единиц и нулей, которые.в каждом конкретном случае определяются. структурой логических связей. Через 2 -1 тактов работы состояния регистра сдвига начнут повторяться, а, следовательно, начнут повторяться последовательности на вы, ходах элементов 4,5, 6,7. Отсюда следует,:что период работы генератора равен 2 -1.

Величина функции Фт корреляции между отдельными каналами

Ф

К11 Ь

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

Таким образом, введение двух групп элементов И, группы элементов ИЛИ и группы сумматоров по модущо два позволяет значительно сократить затраты оборудования на реализацию многоканального ГПСЧ. Получаемая экономия оборудования будет тем более высокой, чем большее число каналов необходимо цолучить на основе регистра сдвига и чем больше разрядность М этого регистра.

Например, для построения 30 каналов по 15 разрядов на основе 32 разрядного регистра сдвига, удельные за— траты оборудования в известном устройстве равны примерно"одному восьмивходовому сумматору по модулю два (число входов равно И)/4). Это эквивалентно семи полусумматорам по модулю два. Удельные затраты предлагаемого устройства равны примерно одному двухвходовому сумматору по модулю два.

С ростом разрядного регистра сдвига

И они не растут, а несколько уменьшатотся.

Таким образом, получают семикрат-, ный выигрыш в оборудован, а также период работы генератора возрастает в 450 раз по сравнению с известным равномерно распределенные и некоррелированные числа. Скорость работы ° генератора равна тактовой частоте.

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

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

j -го элемента И первой группы подключен прямой выход первого разряда ре25 гистра сдвига, а ко второму входу — выход т + 1 -го разряда регистра сдвига (т = 1,2,$,... И- 1) к первому входу

1 -го элемента И второй группы подключен инверсный выход первого разря30 да регистра сдвига, а ко второму выход

g -Ьо разрядарегистра (=2,3,:ттт, g =ттт+1 ), кроме того, выходы j -го элемента и первой группы и элемента И второй группы подкщоченьт ко входам т -го элемента ИЛИ, выход Р-го элемента ИЛИ подкщочен к первому входу К -ro сумматора по модулю два, а выход тф-го элемента

ИЛИ вЂ” ко второму входу сумматора К (где р — 1,2,.... ттт -1; Ц = 1,2,..., ттт Зти тт-1; р =с ; к=1,2,... (— 1) ..

2 2

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

45 . 1. Яковлев В. В., Федоров Р. Ф.

Стохастические вьтчислительньте машины

Ленинград, "Машиностроение!, 1974, с. 238-283.

2. цобрис Г. В. Метод синтеза генератора net :-:äîñëó÷àéíûõ чисел для стахостических вычислительных машин йа основе двух регистров сдвига.

Автоматика и вычислительная техника, 1973, №» 2, с. 1-7.

3. Кирьянов Б. Ф. Многоканальный гейератор псевдослучайных символов.

Техническая кибернетика . Известия

АН СССР; 1970, № 4, с. 197-110 (прототип) .

739603

Составитель Загорбиниыа

Редактор Н. Кравцова Техред И. Асталош Корректор М. Пожо

Заказ 3049/8. Тираж 841 Подписное

БНИИПИ Государственного комитета СССР по делам изобретений и открытий

113036, Москва, Ж-35, Раушскаа наб., д. 4/5

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