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

 

1. ГЕНЕРАТОР ПСЁВДОСЛУЧАЙ-. НЫХ ЧИСЕЛ, содержащий -раэрядный регистр , памяти, илходы которого являются выходами генератора, блок сумматоров по модулю два, элемент эквивалентности, первый и второй входы которого соединены, соответртвенно с J-M () и Е-м выходами Е-разрядного регистра памяти, а выход элемента эквивалентности соединен с информационным входом 2-разрядного регистра памяти, блок памяти, блок задания режимов исчетчик .адреса , выходы которого подключены к адресным входам блока памяти соответственно , отлйч а ющи йся тем, что, с целью повышения точности и упрощения генера.тора, он содержит k-разрядный (k) регистр памяти, разрядные входы крторбго соединены с соответствующими выходами младших k разрядов f-разрядного регистра памяти, а выходы k-разрядного регистра памяти соединены с разрядными входами k старших разрядов блока памяти соответственно, младшие Е-k разрядных входов блока памяти соединены с соответствующие выходаьда g-k разрядов Е-разрядного регистра памяти, Е выходов блока памяти соеди; нены с первой группой входов блока сумматоров по модулю два соответст-, венно, вторая группа входов которого подключена к В выходам 1-разрядногр регистра памяти соответственно, а .выходы блока сумматоров по модулю два подключены к соответствую&сим входам Е-разрядного регистра памяти, первый и второй axojsi блока задания режимов являются соответственно входами Пуск и Стоп генератора, а первый выход, блока задания режимов подключен к входам синхронизации Е-разрядного и k-разрядного регистров памяти, второй выход блока задания режимов подключен к входам Установка Е-разрядного и kJpaзpядного регистров памяти и счетчика адреса, третий выход блока задания режимов подключен к входу управления режимом 2-разрядного регистра памяти , четвертый и пятый выходы блоКа задания режимов соединены соответст§ венно с входами управления чтением и записью.блока памяти шестой выход блока задания режимов соединен со счетным входом счетчика адреса. 2. Генератор по п.1, о т л и ч аю W 9 и с я тем, что блок Задания режимов содержит два триггера, два м счетчика, ода рвибратор, три .элеменQQ СП та НЕ, элемент ИЛИ, шесть .элементов И и генератор импульсов, выход котсфого соединен с первым входом СП первого элемента И, второй вход которого подключен квыходу первого триггера, единичный вход которого является входом Пуск блока, а также соединен с перилм входом элемента ИЛИ и единичным входом второго триггера, нулевой вход которого соедивеа с вторым входом элемента ИЛИ я с выжодом первого счетчика , счетный вход которого подключен к выходу второго элемента И, . первый вход которого соединен с выходом третьего элемента И и является ; первым выходом блока, вторым, тре

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН

ySDG 06 F 758

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬС ГВУ

4 ( (l

1 (21) 3373618/18-24 (22) 29.12.81 .(46) 23.04.83. Бюл. Р 15 (72) Г.В.Добрис, P.Ô.Ôåäîðoâ

:и В.В.Яковлев

:(71) Ленинградский ордена Ленина институт инженеров железнодорожного транспорта им. акад.В.Н.Образцова (53) 681;325(088.8 ) (56) 1 ° Федоров Р.Ф.,Яковлев В.В. —,- .

Добрис Г.В. Стохастические преобразователи информации. Л., "Машиностроение", 1978.

2. Авторское -свидетельство СССР

Р 693408, кл. G 06 F 7/58, 1976 (прототип). (54)(57) 1. ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ, содержащий. 2-разрядный регистр памяти, выходы которого являются выходами генератора, блок.сумматоров по модулю два, элемент эквивалентности, первый и второй входы которого соединены соответст-. венно с j-м (3<) с Р) и й-м выходами

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

k-разрядный (k<2) регистр памяти, разрядные входы которого соединены с соответствующими выходами младших . k разрядов 1-разрядного регистра памяти, а выходы k-paayapsoro регистра памяти соединены с разрядными входами k старших разрядов блока памяти соответственно, младшие й-Е разрядных входов блока памяти соединеныI с соответствующими выходаья старших

3-k разрядов В-разрядного регистра памяти, выходов блока памяти соеди; нены с первой группой1 входов блока

„„80„„1013955 А сумматоров по модулю два соответст-; венно, вторая группа входов которого, подключена к У выходам t-разрядного регистра памяти соответственно, а .выходы блока сумматоров по модулю два подключены к соответствующим входам В-разрядного регистра памяти, первый и второй входы блока задания режимов являются соответственно вхо- дами "Пуск" и "Стоп" генератора, а первый выход, блока задания режимов подключен к входам синхронизации

f,-разрядного и k-разрядного регистров памяти, второй выход блока задания режимов подключен к входам "Установка" Й-разрядного и k-.ðàýðÿä- ного регистров памяти и счетчика Щ адреса, третий выход блока задания режииов:подключен к входу управления режимом 2-разрядного регистра памяти, четвертый и пятый выходы блока задания режимов соединены соответственно с входами управления чтением рз н записью блока памяти шестой вы- ход блока задания режиибв-соединен 9ае4 со счетным входом счетчика адреса.

2. Генератор по п.1, о т л и ч а- 1аиФ ю щ н и с я тем, что блок задания .ум режимов содержит два триггера, два счетчика, одиовибратор, три элемен- та НЕ,. элемент ИЛИ, шесть,элементов Щ

И и генератор импульсов, выход которого соединен с первым входом первого элемента И, второй вход . фЯ которого подключен к выходу первого триггера, единичный вход которого является входом "Пуск" блока, а также соединен с первым входом эле- ) мента ИЛИ и едииичиым входом второго триггера, нулевой вход которого соединен с вторым входом элемента ИЛИ и с выходом первого счетчика, счетный вход которого подключен к выходу второго элемента И, первый вход. которого соединен с выходом третьего элемента И и является.. первым выходом блока, вторым, тре"

1013955

30

40 тьим и четвертым выходами которого являются соответственно выходы четвертого, пятого и шестого элементов И, единичный выход второго триг. гера .соединен с вторым входом второго элемента И и является пятым выходом блока, входом "Стоп" которого является нулевой вход первого триггера, выход элемента ИЛИ соединен с входом одновибратора, выход которого является шестым выходом ,блока, а также соединен с установоч-. ными входами первого и второго счетчиков и через пятый элемент НЕ сое:динен с третьим входом первого эле-, Изобретение относится к вычислительной технике и может быть использовано при построении стохастических . и специализированных вычислительных машин и устройств.

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

Однако этот генератор обладает малой длиной псевдослучайной последовательности.

Наиболее близким по технической сущности к изобретению является ге. нератор псевдослучайных чисел, содержащий блок памяти, регистры памяти, элементы эквивалентности счетчика, регистры памяти, блок сумматоров по модулю два, блок управления (2Я.

Однако известный генератор сложен по технической реализации. Кроме того, использованный способ установки начального состояния генератора (занесения информации в память) не обеспечивает оптимальных корреляционных свойств генерируемой последовательности, так как в силу случайного (псевдослучайного) характера заполнения ячеек памяти в начальном состоянии интервалы сдвига между бинарными последовательностями, формируемые в отдельных разрядах Ф-разрядных псевдослучайных чисел в режиме генерации, получаются произвольными и могут быть существенно меньше величины М/Д, где М - период последовательности, и даже меньше заданного объема выборки, что, в конечном счете, отра- . жается на точности генерирования.

Цель изобретения — повышение точности генератора и сокращение аппаратурных затрат на его реализацию. мента И, выход которого соединен со счетным входом второго счетчика, :первый выход которого соединен с первыми входами первого и шестого элементов И непосредственно и через второй элемент НЕ соединен с первым входом четвертого элемента И,.нулевой выход второго триггера соединен с первым входом пятого элемента И, второй выход второго счетчика соединен с вторыми входами третьего и четвертого элементов И непосредственно и через третий элемент НЕ сое. динен с вторыми входами пятого и шестого элементов И.

Для достижения поставленной цели в генератор псевдослучайных чисел, содержащий К-разрядный регистр памяти, выходы которого являются выходами генератора, блок сумматоров по модулю два, элемент эквивалентности, первый и второй входы которого соединены соответственно c j-м (1< j < E) и t.-м выходами E-разрядного регистра памяти, а выход элемента эквивалентности соединен с информационным входом E-разрядного регистра памяти, блок памяти, блок задания режимов и счетчик адреса, выходы которого подключены к адресным входам блока памяти соответстзенно, введены k-разрядный (kc E) регистр памяти, разрядные входы которого соединены с соответствующими выходами младших k разрядов Е-разрядного регистра памяти, а выходы kразрядного регистра памяти соединены с разрядными входами k старших разрядов блока памяти соответственно, младшие К-k разрядных входов блока памяти соединены с соответствующими выходами старших t-k pasрядов E-раэряднЬго регистра памя.ти, E выходов блока памяти соединены с первой группой входов блбка сумматоров по модулю два соответственно, вторая группа входов которого подключена к Р выходам E-раарааного регистра памяти соответственно, а выходы блока сумматоров по модулю два подключены к соответствующим входам E-разрядного регистра памяти, первый и второй входы блока задания режимов являются соответственно входами "Пуск" и "Стоп" генератора, а первый выход блока задания режимов подключен ко входам синхронизации 0-разрядного и k-разрядного регистров памяти, второй вход блока задания режимов подключен ко

1013955. входам "Установка" R-разрядного и

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

Кроме того, блок задания режимов содержит два триггера, два счетчика, одновибратор, три элемента НЕ, элемент ИЛИ, шесть эле- 15 ментов И и генератор импульсов; выход которого соединен с первым входом первого элемента И, второй ,вход которого подключен к выходу первого триггера, единичный вход которо-gg го является входом Пуск блока,а также соединен с первым входом эле:мента ИЛИ и единичным входом второго триггера,.нулевой вход которого соединен со вторым входом элемен- . 25 та ИЛИ и с выходом первого счетчика, счетный вход которого подключен к выходу второго элемента И, первый вход которого соединен с выходом третьего элемента И и является первым выходом блока, вторым, третьим и четвертым выходами которого являются соответственно выходы четвертого, пятого и.шестого элементов И, единичный выход второго триггера соединен со вторым входом второго элемента И и является пятым выходом блока, входом "Стоп" которого является нулевой вход первого триггера,. вщход элемента ИЛИ соединен со входом одновибратора, выход кото- 40 рого является шестым выходом блока, а также соединен с установочными вхо4 дами первого и второго счетчиков и через первый элемент НЕ соединен с третьим входом первого элемента И, 45 выход которого соединен со счетным входом второго счетчика, первый вы-.. ход которого соединен с первыми входами третьего и шестого элементов И непосредственно и через второй эле- 5й мент НЕ соединен с первым входом четвертого элемента И, нулевой выход второго триггера соединен с первым входом пятого элемента И, второй выход второго счетчика соединен со вторыми входами третьего .и четвертого элементов И непосредственно и через третий элемент НЕ соединен со вторыми входами пятого и шестого элементов И.

На фиг.1 дана блок-схема генератора; на фиг.2 - схема блока задания режимов; на фиг.3 — диаграмма работы генератора.

Генератор содержит блок 1 сумматоров по модулю два, У-разрядный ре- 65 гистр 2 памяти, элемент 3 эквивалентности, k-разрядный регистр 4 памяти, блок 5 памяти, блок б задания режимов и счетчик 7 адреса.

Блок б задания режимов содержит генератор 8 импульсов, триггеры 9 элемент ИЛИ 10, одновибратор 11, счетчики 12, элементы И 13, элементы НЕ 14.

Устройство имеет два основных режимаг начальный режим формирования псевдослучайной информации и рабочил режим - режим форьирования и выдачи t-разрядных псевдослучайных чисел. Режимы работы задаются соответствующими сигналами с выходов блока 6 (фиг.2).

Устройство работает следующим образом.

В начал-..ном режиме блок б вырабатывает начальный сигнал

"Уст.О", который устанавливает в нулевое состояние счетчик 7 адреса и регистры 2 и 4. Начиная с первого такта, блок б вырабатывает последовательности из трех импульсов: "3H", "ЗП" и "+1", поступающих соответственно на входы синхронизации регистров 2 и 4, вход управления записью блока 5 памяти и счетный вход счетчика 7 адреса. Для управления работой регистра 2 блок б вырабатывает потенциальный сигнал режима сдвига информации "БР=1".

При наличии потенциала сдвига "ВР=1" и поступлений импульсов "3H" .регистр

2 работает s режиме сдвига записанной информации в сторону старших разрядов. При этом запрещена запись в регистр 2, информации, присутствующей на выходах блока 1 сумматоров по модулю два, и разрешена запись сигналов, поступающих на последовательный вход первого разряда регистра 2 с выхода элемента 3 эквивалентности. Таким образом, в начальном режиме регистр 2 и элемент 3 представляют собой генератор двоичной последовательности . с псевдослучайным норядком следования нулей и единиц. Следует заметить, что в отличие от известных генераторов псевдослучайных последовательностей на регистре сдвига в данном устройстве нулевое состоя- ние регистра 2 яе является запре-. щенным, что достигается включением в цепь обратной связи регистра 2 элемента эквивалентность вместо сумматора по mod2.

Работа генератора в начальном режиме происходит следующим образом.

Импульсы "ЗН" и потенциал "ВР=1", поступая на регистр 2,приводят к то.му, что последний совместно с элементом 3 формирует В-разрядные псев

1013955

В рабочем режиме генератор работает следующим образом.

В первом такте по сигналу обращения к памяти "Чт" производится выборка содержимого нулевой ячейки

55 блока 5. Сигналы, соответствующие разрядам считанного числа, появляются на выходных разрядных шинах блока 5 и поступают на первые входы сумматоров по mod ? блока 1. . бО

На. вторые входы сумматоров по .mod 2 этого блока поступают разряды числа, хранящегося в регистре 2.

В.результате на выходах блока 1 появляется число, представляющее со- б5 дослучайные числа, которые по сигналу "ЗП" в каждом такте записываются в ячейки блока 5 памяти, после чего содержимое счетчика 7 адреса по сигналу "+1" увеличивается на

5 единицу. То обстоятельство, что младшие k разрядов сформированного в регистре псевдослучайного числа вначале переписываются в регистр 4, а затем заносятся в ячейку блока 5 памяти на место старших разрядов одновременно c f-k старшими разрядами вновь сформированного псевдослучайного числа иэ регистра 2 принципиального значения в начальном режиме работы не имеет, поскольку главная задача работы генератора в начальном режиме — заполнение ячеек памяти блока 5 ненулевыми псевдослу- чайными комбинациями. Эта задача полностью реализуется с помощью ре- 20 гистра 2 с элементом 3 в цепи обрат. ной связи.

Минимально необходимое количество тактов работы генератора в начальном режиме определяется числом ячеек 25 блока памяти q ° Следует однако заметить, что на начальном участке генерации псевдослучайной последовательности в регистре 2 формируются числа с малым количеством еди- 30 ниц. В .связи с этим во избежание заполнения блока памяти комбинациями с малым числом единиц время работы генератора в начальном режиме целесообразно увеличить по меньшей З5 мере до 2 К тактов (как правило-, E)q).

По окончании начального режима (переключение сигнала BP с единицы на ноль) регистр 2 переходит в ре.жим записи информации параллель- 40 ным кодом. В этом режиме сигналы с выхода элемента 3 эквивалентности не воспринимаются первым разрядом регистра 2.

После переключения сигнала "ВР" в "0" блок б выдает второй сигнал 45

"Уст.0", осуществляющий сброс регистров 2,4 и счетчика 7 в ноль. Со следующего такта начинается рабочий режим формирования К-разрядных псевдослучайных чисел. 50 бой поразрядную сумму входных чисел.

Эта поразрядная сумма является первым псевдослучайным числом, которое по сигналу "ЗН" записывается в регистр 2 и одновременно появляется на выходах генератора 8. По этому же сигналу первые k разрядов прежнего числа иэ регистра 2 переписываются в регистр 4. Задержка между сигналами "4Т" и "ЗН" необходима для завершения операций выборки числа иэ блока 5 памяти и поразрядного суммирования его с числом иэ регистра 2 блока 1 сумматоров.

Во второй половине первого такта по сигналу обращения к памяти "ЗП" информация, присутствующая на входных разрядных шинах блока 5, записывается в ту же нулевую ячейку. Записанное в память число представляет собой комбинацию младших k разрядов предыдущего псевдослучайного числа из регистра 4 и старших М-k разрядов нового псевдослучайного числа из регистра 2. Первый такт работы генератора заканчивается увеличением содержимого счетчика 7 адреса на единицу по сигналу "+1 "от блока б.

Во. втором такте выполняются те же операции, что и в первом, с той лишь разницей, что чтение и запись информации осуществляется уже не из нулевой, а иэ первой ячейки блока 5 памяти.

В дальнейшем в каждом новом такте последовательно изменяется состояние счетчика 7.и происходит последовательное обращение к ячей кам блока 5 памяти. При этом в первой половине такта осуществляется считывание 8-разрядного числа из . выбранной ячейки памяти, его поразрядное сложение с числом, хранящимся в регистре 2, запись полученного результата в регистр 2 и выдача его на выход устройства и одновременно передача младших k разрядов прежнего содержимого регистра 2 в регистр 4 °

Во второй половине такта в выбранную ячейку памяти на Место младших разрядов записываются старшие В" k разрядов вновь сформированного псевдослучайного числа из регистра 2, а на место старших разрядов - младшие разрядов предыдущего псевдослучайного числа иэ регистра 4, после чего содержимое счетчика 7 увеличивается на единицу.

После завершения ц тактов работы генератора происходит. обнуление счетчика 7 адреса, имеющего модулем пересчета величину q,è обращение вновь к нулевой ячейке блока 5 памяти. Дальнейший процесс формирования псевдослучайных чисел очевиден.

Блок б задания режимов работает следующим образом.

1013955

521

521

127 151 175 201

32

9 41

8 10

16 10

По сигналУ "Пуск" оба триггера устанавливаются в единичное состояние и запускается одновибратор; формирующий выходной .сигнал "Уст.О".

Сигналом с выхода одновибратора устанавливаются в исходное состояние я счетчики.- По окончании сигнала

"Уст.О" с помощью элемента НЕ, подклюЧенного к:выходу.одновибратора, формируется единичный потенциал на вход элемента И, разрешающий прохождение тактовых импульсов от генератора импульсов на вход счетчика.

Тем садним инициализируется начальный: режим работы генератора псевдослучайных чисел. Значение сигнала

"ЬР", снимаемого с единичного выхода триггера, в этом режиме равно 1, а на выходе распределителя формируется только три последовательности управляющих сигналов "ЗН", "ЗП", "+1" (сигнал "4T" блокируется нулевым потенциалом с инверсного выхода триггера). По окончании каждого такта по сигналу "+1" содержимое счетчика увеличивается на единицу.

Так происходит до тех пор, пока старший разряд счетчика не переключится в единичное состояние, вызывая сброс триггера в ноль и повторный запуск одновибратора и фикси-. руя тем самым переход генератора в рабочий режим. В рабочем режиме сигнал "ВР=О", а на выходе распределителя последовательно формируются импульсы всех четырех унравля« ющих последовательностей "4Т","ЗН"

"ЗП", "+1". Выработка управляющих сигналов прекращается,.когда на . вход блока поступает сигнал останоэа.

Преимуществом предлагаемого генератора по сравнению с известным явля-. ется то, что объем выборки, на котором отсутствует корреляция междуЙ-разрядными псевдослучайными числами, максимален и равен величине М/К тактов.

Другим преимуществом данного генератора является сокращение аппа- ратурных затрат на реализацию. Необходимый объем памяти в известном устройстве определяется величиной

m 1 ит (или вД-разрядных ячеек), а в данном устройстве он равен q -Убит (или q E. — разрядных ячеек), причем

15 m(q> E. Например, при m = 127,9. = 15 и q = 8 отношение mfq 16, т.е. имеет место 16-кратное сокращение объема памяти. Кроме того, сокращаются затраты на реализацию второ20 го буферного регистра (k=7 разрядов вместо t = 15), второго счет.,чика и второго элемента эквивалентности (в предлагаемом устройстве отсутствуют).

Таким образом, техникО-экономический эффект предлагаемого устройства по сравнению с известным, заключается в повышении точности генерирования псевдослучайных чисел, что проявляется в увеличении интервала, на котором отсутствует корреляция между числами, до М/В тактов и уменьшении аппаратурных затрат, в: частности, в сокращении необходимого объема памяти в mfq раз.

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

40 х +х +1 с подходящими для практических случаев значениями m и 2:

1013955

1013955

Нанаиьный режим

Pudovuu режим

Усад

1такт, .2вакт 3яакя.-.

fтакш Zmusm

Составитель A.Êàðàñîâ

Техред К.Иыцьо Корректор С. Шекмар

Редактор Н.Егорова

Заказ 3006/58 Тираж 704 Подписное

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

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

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