Многоканальный генератор псевдослучайных чисел Советский патент 1980 года по МПК G07C15/00 G06F1/02 

(54) МНОГОКАНАЛЬНЫЙ ГЕНЕРАТОР Изобретение относится к вычислитель ной технике и может быть использовано в решающих блоках стохастических вычислительных машин, а также для моделирования случайных процессов на универсальных вычислительных машинах. Известен генератор псевдослучайных чисел на основе Vn-разрядного регистра сдвига и сумматора по модулю два в цепи обратной связи. Подобный ГПСЧ состоит из генератора тактовых импульсов, tn-разрядного регистра сдвига, сумматора по модулю два в цепи обратной связи, . Как известно, такая схема может генерировать циклическую двоичную последовательность максимальной длины (М-последовательность) с периодом М - 2 .-1, где ш-разрядность регистра сдвига, статистические свойства которой аналогичны свойствам последовательности равновероятных символов О и В случае выборки очередного псевдослучайного числа в каждый такт рабоПСЕВДОСЛУЧАЙНЫХ

ЧИСЕЛ Tbi устройства наблюдается жесткая корреляция между последующими значениями многоразрядных кодов псевдослучайных чдсел. Во избежание наличия корреляако1шой,, зависимости в та1сих устройствах необходимо осуществлять выборку выходных чисел только через тактов, где Е 5vn-разрядность псевдослучайного числа. Следовательно, быстродействие устройства в предельном случае в m раз меньше тактовой частоты И Однако такой генератор позволяет получить только один канал. При использовании псевдослучайных чисел в стохастических ВМ необходимо несколько каналов, независимых псевдослучайных чисел. Быстродействие ГПСЧ, при необходимости получения независимых 6-разрядных псевдослучайных чисел, оказывается в С раз ниже его тактовой частоты. Известен генератор псевдослучайных чисел на основе двух регистров сдвига с различным числом разрядов i к hi , генерирующих последовательности максимальной длины. Генератор содержит задающий генератор импульсов, М -разрядный регистр сЛвига с сумматором по модулю два в цепи обратной связи, -разрядный регистр сдвига с сумматором по. модулю два в цепи обратной сзязи, 1 сумматоров по модул1э два, В таком генераторе при условии, что периоды об,еих последовательностей -N 2Т- 1 иМ 2 1 являются взаимно простыми числами, можно пол;учить некоррелированные в пределах N тактов работы, периода исходной последователь ности большей длины (при ), псев дослучайные последовательности путем сложения по модулю два состояний двух рЙзрядов регистров (по одному от каждого). Свойства таких последователь«эстей близки свойствам М-последовательностей. Максимальное число канаж в одновременно генерируемых таюим ГПСЧ равно И + m - 1. Число независимых каналов на основе двух регистров сдв1Ега равно 11+ Ш - 1, 2. «;-i: При необходимости получения большого числа каналов, надо пропорциональ но ему увеличивать разрядности регистр сдвига VI и т, что приводит к значительным аппаратурным затратам, неравному ностй распределения псевдослучайных чисел, так как генерируемые последовательности являются участкам последовательности С СЧ,Ь,где01ц- последовательность периода N, а Ьц- периода М, уменьшении периода работы генератора в Wi - 1 раз вследствие разбиения последовательности С ц на отдельные участки; однозначности соответствия значений периодов N и М ко торые должны быть только взаимно гфостыми числами. Наиболее близким к изобретению по технической сущности является генератор псевдослучайных чисел (многоканальный), содержащий задающий генера тор импульсов, Vn -разрядный регистр сдвига с cyTviMaTopOM по модулю два в цепи обратной связи, Y многовходовых сумматоров по модулю два. Гнератор од1юврвменно генерирует несколько участков полного кодового коАьца М- последовательности, которое обеспвч;1вается поразрядного еложения по модулю два отдельных последовательностей, снимаемых с ооответстйукдадх разрядов регистра сдвига. В этом генераторе отдельные каналы явл{потся разрядами генерируемого числа. Для сдвига полного числового кольца М-последовательности на любое число символов С выходы опр.едёленных разрядов регистра сдвига подключают ко входу сумматора по модулю два. Структура связей определяется путем моделирования на ЭВМ исходной М-последовательности. Для этого в начальном состоянии генератора необходимо записать единицу в 1+1 разряд регистра сдвига ( i -и разряд подключен ко входу сумматора 3 в цепи обратной связи регистра) и нули в остальные разряды. Тогда после каждых С тактов работы в регистре будут зафиксированы определенные Ж -разрядные коды. Наличие единицы в разряде регистра свидетельствует о том, что его выход подключается ко входу сумматора 4, а наличие нуля - о том, что не подключается. Для каждого канала необходим определенный сдвиг (где К 1,2,... ), а следовательно ему присущ определенный код в регистре, строгчэ определяющий структуру логических связей. Очевидно, что число разрядов, которые надо подключить ко входамсумматоров 4, зависит от числа еданиц в коде регистра, который фиксируют через К-С тактов работы. В среднем число единиц в регистре сдвига за период М работы генератораравно VH/2. .Это значит, что для организации одного канала на основе Hi-разрядного регистра сдвига необходим, сумматор по модулю два с Yn/2 входами. Обычно производят оптимизацию оборудования, что предусматривает при моделировании сдвиг не на КС символов, а число близкое к нему. Целью является получегше кода с минимальным числом единиц. В результате добиваются сокращения удельных затрат на канал до сумматора с Vn/4 входами. Лучшего результата добиться трудно рЗ. Анализ данного генератора показывает, что при необходимости получения большого числа каналов К исходная М-последовательность разбивается на К одновреме1шо генерируемых участков. При Э.ТОМ уменьшается период работы генератора до Недостатком также является увеличение неравномерности распределения чисел при большом числе каналов. Это объясняется неравенством числа единиц И нулей на отдельных участках М-после довательности. Необходимы значительные удельные затраты оборудования на реализацию каждого канала. Для формирования таких каналов требуется использовать в среднем Ж/4 разрядов регистра сдвига, что приводит к необходимости применять либо сложные многовходовые сумматоры по модулю два, либо несколь до двухходовые сумматоров (полусумма торов) . Попытка устранить два предыдущих недостатка путем увеличения разрядност И1 регистра сдвига, а следовательно и периода основной М-йоследовательнос приводит к увеличению числа входов сум матора по модулю два, необходимого дл реализации одного канала. Недостатком также является сложнос подготовки к построению многоканального ГПСЧ, которая предусматривает моделирование на ЭВМ исходной М-последовательности. Цель изобретения - сокращение удельного оборудования на один канал, увеличение периода работы генератора до максимально возможного для данной разрядности hi регистра сдвига, а также уменьшения неравномерности распределения чисел при сохранении прежне корреляционной характеристики генератора. Поставленная цель достигается тем, что в многоканальный генератор псевдослучайных чисел, содержащий, задающий генератор импульсов, vn-разрядный триг герный регистр сдвига с сумматором п6 модулю два в цепи обратной связи, причем выход задающего генератора.подключен ко входам синхронизации триггеров регистра сдвига, вводятся две группы элементов И, группа элементов ИЛИ группа сумматоров по модулю два, причем к первому входу i-ro элемента И первой группы подключен прямой выход первого разряда регистра сдвига, а ко второму входу .- прямой выход 1 + 1-го разряда регистра сдвига ( i 1, 2,3, ..., Vn-l), к первому вх ду 1 -го элемента И второй группы подключен инверсный выход первого разряда регистра сдвига, а ко второму прямой выход -го разряда регистра ( f -2,3,..., И1; j - И1 + 1), причем выходы 1 -X элементов И первой и второй групп подключены ко входам 1 -X элементов ИЛИ, выходы юторых парно подключены ко входам К сумматоров по модулю два, а выход о-го элемента ИЛИ - ко второму входу сум- матора К (где Р--.2,.-.И1-1;с --1Д..., (;: р--....,2,... .). На чертеже приведена схема пред-J лагаемого генератора при Ж-8. Генератор содержит задающий генератор 1 импульсов, 8-разрядный регистр 2 сдвига с сумматором по моцулю два в цепи 3 обратной связи, группу элементов 4 И, группу элементов 5 И; группу элементов 6 ИЛИ, группу сумматоров 7 по модулю два. Задающий генератор импульсов предназначен для синхронизации работы всего устройства, регистр сдвига с сумма- . тором по модулю два в цепи обратной связи - для получения псевдослучайной последовательности единиц и нулей с периодом, равным 2 -1, две группы элементов И и группа элементов ИЛИ для получения последовательностей нулей, и единиц, вероятность появления, которых равна 0,5, а период последо- . вательностей равен 1, группа сумматоров по модулю два - для получения большого числа каналов, генерирующих ПС числа. Независимый канал, генерирующий ПС последоват.ельность, получают, используя свойство М-последовательности, заключающееся в том, что ве|Ьоятность появления двух определенных символов (11,10,01,00) я любых двух разрядах регистра сдвига равно 1/4. Если обозначить прямой выход разряда регистра сдвига X, а инверсный выход X.-f (,2,..., Vn), то реализацию таких последовательностей можно вьфазить математически следующим образом: --,, 5-- -, Получают последоватвгпьности V.-М 1 вероятностью появления 1 или О, равой 1/2. Для получеа:,ч N.,- складывают последовательности iC..y. вероятностью появления одшгицы, равной 1/4. Возможность появленпя одиштцы

7 одйовременно в двух слагаемых исключена, как первое спагаемое равно 1 при Х 1, Чт. - 1, а второе при , У. Число таких последовател.ьностей . Простое сложение 6 выражениях эквивалентно суммированию по модулю два, Функционирование устройства происходит следующим образом. Производят запись начального кода в регистр сдвига и просигналим гене ратора 1 тактовых импульсов в нем начинает происходить смена состояний, определяемая структурой обратной связи В зависимости от состояния разрядов р гистра сдвига на выходах элементов 4,5,6,7 получают последовательности единиц и нулей, которые.в каждом конкретном случае определяются структуро логических связей. Через тактов работы cocTosnora регистра сдвига начн повторяться, а, следовательно, начнут повторяться последовательности на вы, ходах элементов 4,5, 6,7. Отсюда следует, что период работы генератора равен . Величина функции Фц корреляции меж ду отдельными каналами 1.-, - - Mj NvВывод о равномерности распределени .чисел в данном генераторе следует из вывода о минимальной корреляции между каналами.ь Таким образом, введение двух групп элементов И, группы элементов ИЛИ и группы сумматоров по модулю два позволяет значительно сократить затраты оборудования на реализацию многоканалыюго ГПСЧ. Получаемая экономия оборудования будет тем более высокой, чем большее число каналов необ ходимо получить на основе регистра сдвига и чем больше разрядность УМ этого регистра.. Например, для построения ЗО каналов по 15 разрядов на основе 32 разрядного .регистра сдвига, удель.нь1е затраты оборудования в И;3вестном устрой стве равны примерно одному восьмивходовому сумматору по модулю два (число входов равно W4}. Это эквийалентно семи полусумматорам по моду лю два. Удельные затраты предл огаемо го устройства равны примерно одному двухвходовому сумматору по модУто дв С рЬстом разрядного регистра сдвига In они не растут, а несколько уменьшаются.

8 Таким образом, получают семикрат-. ный выигрыш в оборудовании, а также период работы генератора возрастает в 450 раз по сравнению с известным равномерно распределенные и некоррелированные числа. Скорость работы генератора равна тактовой частоте. Формула изобретения Многоканальный генератор псевдослучайных чисел, содержащий задающий генератор импульсов, m -разрядный триггерный регистр сдвига с сумматором .по модулю два в цепи обратной связи, причем выход задающего генератора подключен ко входам синхронизации триггеров регистра сдвига, отличающиис я тем, что, с целью сокращения аппаратурных затрат генератора, он содрржит две группы элементов И, группу элементов ИЛИ, группу сумматоров по модулю два, причем к первому входу i -го элемента И первой группы подключен прямой выход первого разряда регистра сдвига, а ко второму входу - выход i + i -го разряда регистра сдвига (л 1,2,2.. И1- 1) к первому входу i -го элемента И второй группы подключен инверсный выход первого разряда регистра сдвига, а ко второму вь1ход j -К) разряда регистра (;)2,3;111; j-w+l ), кроме того, выходы i -го элемента и первой группы и элемента И второй группы Подключены ко входам 1 -го элемен- та ИЛИ, выход Р-го элемента ИЛИ подключен к первому входу К-го сумматора по модугао два, а выход q, -го элемента ИЛИ - ко второму входу сумматора К (где р 1,2,.., m -1; tV 1,2,... , №-1; р-с ; ,2,...(Источники ин формации, принятые во внимание при экспертизе 1.Яковлев В. В., Федоров Р. Ф. Стохастические вычислительные машины Ленинград, .Машиностро ение, 1974, с. 238-283. 2.Добрис Г. В. Метод синтеза генератора пспдослучайных чисел для стазсостических вычислительных машин на основе двух регистров сдвига, Автоматика и вьгаислитёльная техника , 1973, Ж 2,сГ 1-7. 3.Кирьянов Б. Ф. Многоканальный псевдослучайных символов. Техническая кибернетика. Известия АН СССР, 1970, № 4, с. 197-110 (прототип).