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

Союз Советских Социалистических Республик(51) М. Кл, 6 061,02 с присоединением заявки %в 1 асударатаенный комитет Сааата Министров СССР по делам изобретений и атнрытий(32) ПриоритетОпубликовано 25.04.75. Бюллетень15 Дата опубликования описания 1 О.04.7 5(71) Заявитель Ленинградский ордена Ленина институт инженеров железнодорожного транспорта им, акад, В. Н. Образцова(54) ГЕНЕРАТОР РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ индекс 1, - указывает на номер разряда. Изобретение касается вычислительнойтехники и может быть использовано припостроении вероятностных преобразователей.Известны генераторы псевдослучайныхчисел, содрржашие т 1 -разрядные регистры 5с сумматорами по модулю "2" в цепи обратной связи,Целью изобретения является повышениебыстродействия генератора,Это достигается тем, что первые фут разрядов регистра сдвига выполнены на триггерах со счетным входом, а осталькые(П -%) разрядов - на триггерах с установочными входами, причем счетные входыпервых тг 1 триггеров соединены с единичными входами соответствующих ( т 1 -ттт)триггеров, установочные входы которыхподключены к выходам первых % тригге-.ров соответственно.Схема генератора изображена на чертеже.Генератор псевдослучайных чисел представляет собой И, -разрядный регистрсдвига, обхваченный цепью обратной связии содержащий группу триггеров 1 со счет- И 2ным входом 1, 2, 11 и группу триггеров П с шинами установки в "0" и "1"1 П + 1,., т 1, Коммутация разрядов регистра сдвига выполнена следующим образом:счетный вход любого из триггеров 1, 2, гг 1, например с номером 1., соединяется сединичным выходом триггера, имеющего комер ( т 1 -Ф + Ь ), а едини щыйи нулевой установочные входы любого изтриггеров Ю + 113 например с номером ), - с соответствующими выходами триггера, имеющего номер (- 111)Цепи синхронизации работы триггеров и :установки их в начальное состояние на :схеме не показаны, хотя их наличие, каки в любой схеме с элементами памяти, , обязательно.Рассмотрим принцип работы обычного : генератора псевдослучайных чисел в течение тП тактов.Начальное состояние разрядов регистров сдвига обозначим символами 01 й; а, где й(- а;), апосле второго такта 001011101 010110001 100111010 01110110035,.1) числа Щ и й должны соответство:вать индексам единственных единичных коэффициентов неразЛожимого и примитивного многочлена степени Й40. Если указанные операции выполнять на каждом такте работы схемы, от некоторо , го К-того состояния регистра за один такт можно будет перейти к (К+ЙЧ) состоянию, минуя промежуточные, т. е, путем изменения логики работы регистра сдвига можно достичь Щ -кратного ускорения работы генератора псевдослучайных чисел, Такой алгоритм работы генератора и реализуется схемой, показанной на чертеже, В этой схеме триггеры со счетным входом выполняют операцию суммирования по мо, дулю "2" в соответствии с уравйением,а триггеры с установочными входами - функцию хранения предшедствуюших состоМний первых (- 3 П ) разрядов регистра.Генератор псевдослучайных чисел рабо тает следующим образом. В исходном состоянии в регистр сдвигазаносится произвольное, но не нулевое Поскольку каждое последующее састояниерегистра образуется в результате сдвига вправо на один разряд содержимого регистра,в предыдущем такте и записи в освободившийся разряд символа Оф или "1 ф с выхода сумматора цепи обратной связи, в результате действия Щ тактовых импульсов получим следующую после 1 довательность состояний регистра сдвига: после первого такта сдвига ф)гм К-) т О) ") 1 К, ) после тактов сдвига 1, 1 а-щ) ОаОь-т а)" ) иЗдесь знак + означает суммированиепо модулю "2". ФСравнивая конечное состояние регистрасдвига с исходным, затем, чго оно полу;чается путем суммирования по модулюф 2 ф начальных состояний собственного). -того и К -ПЧ+ Ь разрядов для первыхд разрядов регистра сдвига и перезаписьюв остальные начальных состояний первых( Й - РЧ) разрядов регистра -разрядное двоичное число Нулевое со,стояние регистра запрещено, Если нри эксплуатации: устройства не требуется .точного повторения генерируемой последовательности, достаточно установить в единичное состояние один из разрядов регистра, Под действием тактовых импульсов в: регистре формируется последовательность Я -разрядных двоичных чисел, представля ющая собой результат выполнения последо. вательности операций, описываемых уравнением, Эта последовательность будет ко лией последовательности псевдослучайных; чисел, генерируемой обычным генератором, )5 если в последнем чгсло сдвигов Я выб," рать равным ФИ . П р и м е р. Если в исходном состоя, нии в генераторе записано число 1011.00111, последующими числами . :последовательности будут: Для генерирования схемой последовательности равномерно распределенных псев, дс,случайных чисел с максимальным перио, дом И = 2 -1 необходимо выполнениеЮ,следующих условии: 2) числа Щ и И = 2 -1 должныйбыть взаимно простыми,Для получения последовательности пеев; дослучайных чисел с большим числом статистически независимых разрядов желатель-,но также, чтобы величина 1 П была какможно ближе к 1,50тНиже приводится таблица значений )1.ных чисел ,4 Щ, можно выбрать необ, ходимую структуру предложенного генера; тора псевдослучайных чисел,5 о 6 Значения Й 1 Значении И 1023 10 17 20 22 22 28 28 31 20 Предмет изобретенияГенератор равномерно распределенныхпсевдослучайных чисел, содержащийразрядный регистр сдвига с сумматоромпо модулю "2 ф в цепи обратной связи,о т л и ч а ю щ и й с я тем, что, сцелью повышения быстродействия, первыеИ разрядов регистра сдвига выполнены 2047 32767 131071 262143 1048575 2097151 4194303 8388607 33554431 268435455 2147483647 8589934591на триггерах со счетным входом, а остальные 1 Й - %) разрядов - на триггерах с установочными входами, причем счетные входы первых Щ триггеров соединены 30,с единичными выходами соответствующих(Я - Ф) триггеров, установочные входыкоторых подключены к выходам первыхЩ триггеров соответственно.