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

(11739603 О П И С А НИ Е ИЗОБРЕТЕНИЯ Союз СоветскикСоциалистическиеРеспублик Ф л ть К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(23 ) П р нор и тет Опубликовано 05,06.80, Бюллетень21 йо делам изобретений н открытийЛата опубликования описания 08.06,80(71) Заявитель Минский радиотехнический институт(54) МНОГОКАНАЛЬНЫЙ ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХЧИСЕЛ 1Изобретение относится к вычислительной технике и может быть использовано в решающих блоках стохастических вычислительных машин, а также для моде- лирования случайных процессов на универсальных вычислительных машинах,Известен генератор псевдослучайных чисел на основе В-разрядного регистра сдвига и сумматора по модулю два в цепи обратной связи. Подобный ГПСЧ)о состоит из генератора тактовых импульсов, )т 1-разрядного регистра сдвига, сумматора по модулю два в цепи обратной связи.Как известно, такая схема может генерировать циклическую двоичную последовательность максимальной длины (М-последовательность) с периодом М = 2 .-1, где тп -разрядность регисттпра сдвига, стаглстические свойства которой аналогичны свойствам последовательности равновероятных символов 0 и 1.В случае выборки очередного псевдослучайного числа в каждый такт работы устройства наблюдается жег:ткая корреляция между последующими значениями многоразрядных кодов псевдослучайных чисел. Во избежание наличия корреляпнонной, зависимости в таких устройствах необходимо осуществлять выборку выходных чисел только через КМ тактов,где"-и-разрядность псевдослучайного числа. Следовательно, быстродействие устройства в предельном случае в Ю раз меньше тактовой частоты Ц.Однако такой генератор позволяет получить только один канал. При использовании псевдослучайных чисел встохастических ВМ необходимо несколько каналов, независимых псевдослучайных чисел. Быстродействие ГПСЧ, при необходимости получения независимых -разрядных псевдослучайных чисел, оказывается в 6 раз ниже его тактовой частоты.Известен генератор псевдослучайных чисел на основе двух регистров: сдвига с различным числом разрядов 11 к 1 тт03 6парно подключены ко входам К сумматоров по модулю два, а выход о-го элемента ИЛИ - ко второму входу сум-" матора К (где Р=в;=1,2,т;5 Р= уЪ =12,, - --+ 1 ),п Ът 5 7396 и нулей на отдельных участках М-последовательности.Необходимы значительные удельные затраты оборудования на реализацию каждого канала. Для формирования таких каналов требуется использовать в среднем и/4 разрядов регистра сдвига, что приводит к необходимости применять либо сложные многовходовые сумматоры по модулю два, либо несколь до двухходовых сумматоров (полусумма- торов).Попытка устранить два предыдущих недостатка путем увеличения разрядности Ф регистра сдвига, а следовательно и периода основной М-последовательности, приводит к увеличению числа входов сум-, матора по модулю два, необходимого для реализации одного канала.Недостатком также является сложность 20 подготовки к построению многоканального ГПСЧ, которая предусматривает моделирование на ЭВМ исходной М-последовательности.Цель изобретения - сокращение удельного оборудования на один канал, увеличение периода работы генератора до максимальнс. возможного для данной разрядности н регистра сдвига, а также уменьшения неравномерности рас- З 0 пределения чисел при сохранении прежней корреляционной характеристики генератора.Поставленная цель достигается тем, что в многоканальный генератор псевдо случайных чисел, содержащий задающий генератор импульсов, И-разрядный триггерный регистр сдвига с сумматором п 6 модулю два в цепи обратной связи, причем выход задающего генератора под- . 40 ключен ко входам синхронизации триггеров регистра сдвига, вводятся две группы элементов И, группа элементов ИЛИ, группа сумматоров по модулю два, причем к первому входу 1-го элемента И 45 первой группы подключен прямой выход первого разряда регистра сдвига, а ко второму входу . - прямой выход 1+ 1-го разряда регистра сдвига( 1 = 1, 2 ф 3, , И 1-1), к первому вхо ду 1 -го элемента И второй группы подключен инверсный выход первого разряда регистра сдвига, а ко второму - прямой выход ) -го разряда регистра (-2 3,"., Ю; ) = И 1+ 1), причем выходы-х элементов И первой и второй групп подключены ко входам 1 -х элементов ИЛИ, выходы которых по . На чертеже приведена схема пред-лагаемого генератора при 1 и=8.Генератор содержит задающий генератор 1 импульсов, 8-разрядный регистр 2 сдвига с сумматором по модулю два в цепи 3 обратной связи, группу элементов 4 И, группу элементов 5 И;группу элементов 6 ИЛИ, группу сумматоров 7 по модулю два.Задающий генератор импульсов предназначен для синхронизации работы всего устройства, регистр сдвига с сумматором по модулю два в цепи обратнойсвязи - для получения псевдослучайнойпоследовательности едчниц и нулей спериодом, равным 2 -1, две группыЩэлементов И и группа элементов ИЛИ -для получения последовательностей нулей и единиц, вероятность появления,которых равна 0,5, а период последо- ./вательностей равен 21, группа сумматоров по модулю два - для получения большого числа каналов, генерирующих ПС числа.Независимый канал, генерирующийПС последовательность, получают, используя свойство М-последовательности,заключающееся в том, что вероятностьпоявления двух определенных символов(11,10,01,00) и любых двух разрядахрегистра сдвига равно 1/4,Если обозначить прямой выход разряда регистра сдвига Х, а инверсныйвыход Х,; (1=1,2 И 1), то реализациютаких последовательностей можно выра"зить математически следующим образом:Ч=хх Кх=Х Х+Х Х1 5 1 бЧ 5 -Х 1 Ь Х 1 ХЪЧ =Х Х 1 Х Х6 1 7Получают последовательности Ч., - Чс вероятностью появления 1 или О, равной 1/2. Для получен." Чскладываютпоследовательности Х,Хи Х Х, свероятностью появления единицы, равной1/4. Возможность появления единицы739603 одновременно в двух слагаемых исключена, так как первое слагаемое равно1 при Х= 1, Х= 1, а второе" при Х= 0 Х,=1.Число таких последовательностей Й=н. Простое сложениев выражениях эквивалентно суммированию по модулю два,функционирование устройства происходит следующим образом.Производят запись начального кодав регистр 2 сдвига и по сигналам генератора 1 тактовых импульсов в нем начинает происходить смена состояний,определяемая структурой обратной связи.В зависимости от состояния разрядов регистра сдвига на выходах элементов4,5,6,7 получают последовательностиединиц и нулей, которые.в каждом конкретном случае определяются структуройлогических связей. Через 2 -1 тактовработы состояния регистра сдвига начнутповторяться, а, следовательно, начнутповторяться последовательности на вы, ходах элементов 4,5, 6,7. Отсюда следует,:что период работы генератора равен 2 -1.Величина функции фк корреляции между отдельными каналамиФК) йВывод о равномерности распределения.чисел в данном генераторе следует извывода о минимальной корреляции меж-:ду каналами.Таким образом,введение двух группэлементов И, группы элементов ИЛИи группы сумматоров по модулю двапозволяет значительно сократить затраты оборудования на реализацию многоканального ГПСЧ. Получаемая экономия оборудования будет тем более высокой, чем большее число каналов необходимо получить на основе регистрасдвига и чем больше разрядйость Мэтого регистра.Например, для построения 30 каналов по 15 разрядов на основе 32 разрядного регистра сдвига, удельные за -- траты оборудования в известном устройстве равны примерно" одному восьмивходовому сумматору по модулю два(число входов равно й/4). Это эквивалентно семи полусумматорам по модулю два. Удельные затраты предлагаемого устройства равны примерно одномудвухвходовому сумматору по модулю два,С ростом разрядного регистра сдвигаИ 1 они не растут, а несколько уменьшаются е 8Таким образом, получают семикрат-, ный выигрыш в оборудовании, а также период работы генератора возрастает в 450 раз по сравнению с известным равномерно распределенные и некоррелированные числа. Скорость работыгенератора равна тактовой частоте,формула изобретения10 Многоканальный генератор псевдослучайных чисел, содержащий задающийгенератор импульсов, И -разрядный триггерный регистр сдвига с сумматором,помодулю два в цепи обратной связи, при 15 чем выход задающего генератора подключен ко входам синхронизации триггероврегистра сдвига, о т л и ч а ю щ и йс я тем, что, с целью сокращенияаппаратурных затрат генератора, он со 20 держит две группы элементов И, группуэлементов ИЛИ, группу сумматоров помодулю два, причем к первому входут -го элемента Й первой группы подключен прямой выход первого разряда ре 25гистра сдвига, а ко второму входу - выход 1 + 1 -го разряда регистра сдвига (1 =1,2,5, и) к первому входу1 -го элемента И второй группы подключен инверсный выход первого разря 30да регистра сдвига, а ко второму выход-о разряда регистра (=2,.3,:щ; :и+1 ),кроме того, выходы т -го элемента ипервой группы и элемента И второй группы подключены ко входам 1-го элемен 35 та ИЛИ, выход Р-го элемента ИЛИ подключен кпервому входу К -го сумматорапо модулю два, а выход Ч,-го элементаИЛИ - ко второму входу сумматора К(где р - 1,2,". п -1; Ц = 1,240 п3 нИ 1 - 13 р =Як=12,( 1),2 2Источники информации,принятые во внимание при экспертизе4 1, Яковлев В. В., Федоров Р. ф.Стохастические вычислительные машиныЛенинград, "Машиностроение, 1974,с. 238-283.2. Добрис Г. В. Метод синтезагенератора псе:;дослучайных чисел длястахостических вычислительных машинна основе двух регистров сдвигаАвтоматика и вычислительная техника ,1973,2, с. 1-7.3. Кирьянов Б. Ф. Многоканальныйгейератор псевдослучайных символов.Техническая кибернетика, ИзвестияАН СССР; 1970,4,с. 197-110Сос гор биниыащ Корректор М, Пож т Редактор Н, Кр Заказ 3049/8. И. ова Т Подписно та СССРтийнаб., и,Тираж 841 ЦНИИПИ Государственного коми по делам изобретений и откр 113035, Москва, Ж-ЗБ, Раушск