Генератор равномерно распределенных псевдослучайных чисел Советский патент 1975 года по МПК G06F1/02 

1

Изобретение касается вычислительной ToxidHKK и может быть использовано при построении вероятностных преобразователей.

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

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

Это достигается тем, что первые In разрядов регистра сдвига выполнены на триггерах со счетным входом, а остальные (П -- Тп} разрядов - на триггерах с установочными входами, причем счетные входы первых Ш триггеров соединены с e iHHt-s ными входами соответствующих (ТХ-Ш) триггеров, установочные входы которых подключены к выходам первых 1Т1 тригге- : ров соответственно.

Схема 1енератора изображена на чертеже.

Генератор псевдослучайных чисел пред ставляет собой П. -разрядный регистр сдвига, обхваченный цепью обратной связи и содержащр1й группу триггеров 1 со счет

ным входом 1, 2, ,.., ft и группу триггеров П с шинами установки в О и 1 т+ 1,...,11. . Коммутация разрядов рет-ис ра сдвига выполнена следуюищм образом: счетный вход любого из триггеров 1, 2 ..., fn , например с номером L , соединяется с единичным выходом триггера, имеющего номер ( И-ТП + L ), а единичный и нулевой установочные входы любого нз триггеров m + 1, ,..,П, например с номером J , - с соответствующими выходами триггера, имеющего номер ( j t7l) : Цепи синхронизации работы триггеров и установки их в начальное состояние на схеме не показаны, хотя их наличие, как и в любой схеме с элементами памяти, .обязательно.

Рассмотрим принцип работы обычного ; генератора псевдослучайных чисел в тече ние m тактов.

Начальное состояние разрядов регистров сдвига обозначим символами Q| ,

CL2 .- i tl« L L

индекс t - указывает на номер разряда. Поскольку каждое последующее состояние регистра образуется в результате сдвига вправо на один разряд содержимого ре- (Гистра. в предыдущем такте и записи в освобод1шшийся. разряд символа О или I с выхода сумматора цепи обратной связи, Б результате действия m тактовых импульсов получим следующую после- tдовательность состояний регистра сдвига: ;после первого такта сдвига П) после второго такта f m-i-Q-n- m- anv-) f ti-uV после тактов сдвига - n-m+i, .,..., а„.п Здесь знак + означает суммирование по модулю 2. Сравнивая конечное состояние регистра сдвига с исходным, затем, что оно получается путем суммирования по модулю 2 начальных состояний собственного I -того и H-fn+L разрядов для первых у разрядов регистра сдвига и перезапись в остальные начальных состояний первых ( tl - ТП) разрядов регистра. Если указанные операции выполнять на каждом такте работы схемы, от некоторо, го К-того состояния регистра за один такт можно будет перейти к (К + tn) сост янию, промежуточные, т. е, путем изменения логики работы регистра сдвига можно достичь УП -кратного ускорения : работы генератора псевдослучайных чисел. I Такой алгоритм работы генератора и реализуется схемой, показанной на чертеже, В этой схеме триггеры со счетнЫм входом вьшолняют операцию суммирования по модулю 2 в соответствии с ypaBiieHHeMf, а триггеры с установочными входами функцию хранения предщедствующих состо4 и НИИ первых (tV -tn) разрядов регистра. Генератор псевдослучайных чисел рабо тает следующим образом, В исходном состоянии в регистр сдвига заносится произвольное, но не нулевое YI -разрядное двоичное число. Нулевое со- .стояние регистра запрещено. Если при эксплуатации устройства не требуется точного повторения генерируемой последовательности, достаточно установить в еданичное состояние один из разрядов регистра. Под действием та1 товых импульсов в регистре формируется последовательность -разрядных двоичных чисел, представляющая собой результат выполнения последовательности операций, описьтаемых уравнением. Эта последовательность будет копией последовательности псевдослучайных чисел, генерируемой обычным генератором, если в последнем число сдвигов выбрать равным 1Т1 Пример. Если в исходном состояНИИ в генераторе записано число 101100111, последующими числами последовательности будут: OplOlllOl 010110001 100111010 О11101100 Для генерирования схемой последовательности равномерно распределенных псевДОСлучайных чисел с максимальным периодом N -2 -1 необходимо вьшолнение следующих условий: 1) числа m и 11 должны соответствовать индексам единственных единичных ко- эффициентов неразЛожимого и примитивного многочлена степени П. ; 2) числа fn и N 2 -1 должны быть взаимно простыми. Для получения последовательности псев- дослучайных чисел с большим числом ста тистически независимых разрядов желатель-; но также, «ггобы величина tn была как можно ближе к tl . Ниже приводится таблица значений Н и W , составленная с соблюдением перечисленных условий. Пользуясь этой таблйцей, по : за данному периоду пос ледов атель ности N и разрядности псевдослучгайных чисел 1,4 tn можно выбра-Кз нёобходимую структуру предложенного генера тора псевдослучайных чисел.

П р е дм ет зобре тения Генератор равномерно распределённь1Х псевдослучайных чисел, содержащий tl разрядный регистр сдвига с сумматором но модулю 2 в цепи обратной связи, отли чающийся тем, что, с целью повышения быстродействия, первые tH разрядов регистра сдвига выполнены

на триггерах со счетным входом, а остальные (t -Ш) разрядов - на триггерах с установоч;1ыми входами, причем счетные входы первых tYl триггеров соединены ,«с единичными выходами соответствующих (Tl -Ш) триггеров, установочные входы

которых подключены к выходам первых

Ш триггеров соответственно.

Д-О.