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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК ЯК 1013 7 ОСУДАРСТВЕННЫЙ КОМИТЕПО ДБЛАМ ИЗОБРЕТЕНИЙ ТС ТИЙ ОПИСАНИЕ ИЗОБРЕТЕНИЯ д ВВавй а- я:(71) Ленинградский ордена Ленинаинститут инженеров железнодорожноготранспорта им. акад.В,Н.Образцова(56) 1Федоров Р.Ф.,Яковлев В.В, - ,Добрис Г.В. Стохастические преобразователи информации. Л., "Машиностроением, 1978.2, Авторское свидетельство СССРР 693408, кл. 6 06 Г 7/58, 1976(54)(57) 1. ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ, содержащий. -разрядный регистр памяти, выходы которого являются выходами генератора, блок.- сумматоров по модулю два, элементэквивалентности, первый и второйвходы которого соединены соответст-.венно с )-м (1 с 2) и й-м выходамий-разрядного регистра памяти, а выход элемента эквивалентности соединен с информационным входом Й-разряд-.ного регистра памяти, блок памяти,блок задания режимов и счетчик адреса, выходы которого подключены кадресным входам блока памяти соответственно, о т л и ч а ю щ и й с ятем, что, с целью повышения точностии упрощения генератора, он содержитК-разрядный (1 с 2) регистр памяти,разрядные входы которого соединеныс соответствующими выходами младших М разрядов 1-разрядного регистрапамяти, а выходы 1-разрядного регистра памяти соединены с разряднымивходами М старших разрядов блока памяти соответственно, младшие й-Е раз. рядных входов блока памяти соединены. с соответствующими выходаьщ старших 3- разрядов В-разрядного регистра памяти,выходов блока памяти соеди; нены с первой группой 1 входов блока сумматоров по модулю два соответст-; венно, вторая группа входов которога подключена к Ф выходам Й-разрядного регистра памяти соответственно, а ,выходы блока сумматоров по модулюдва подключены к соответствующим входам В-разрядного регистра памяти, первый и второй входы блока задания режимов являются соответственно вхо- дами "Пуск" и "Стопе генератора, а первый выход, блока задания режимов подключен к входам синхронизации-разрядного и -разрядного регистров памяти, второй выход блока задания режимов подключен к входам фустановкаф -разрядного и М-.раэря ного регистров памяти и счетчика адреса, третий выход блока задания режимов:подключен к входу управления режимом 2-разрядного регистра памяти, четвертый и пятый выходы блока задания режимов соединены соответственно с входами управления чтением и записью. блока памяти шестой вы- ход блока задания режимбв соединен со счетным входом счетчика адреса2. Генератор по п.1, о т л и ч ю щ и й с я тем, что блок эадани режимов. содержит два триггера, два счетчика, одновибратор, три элемен- та НЕ,. элемент ИЛИ, шесть, элементов И и генератор импульсов, выход которого соединен с первым входом первого элемента И, второй вход которого подключен к выходу первого триггера, единичный вход которого является входом фПуск" блока, а также соединен с первым входом элемента ИЛИ и единичным входом второго триггера, нулевой вход которого соединен с вторым входом элемента ИЛИ и с выходом первого счетчика, счетный вход которого подключен к выходу второго элемента И, первый вход. которого соединен с выходом третьего элемента И и является первым выходом блока, вторым, тре"1013955 10 15 го 25 30 35 40 тьим и четвертым выходами которогоявляются соответственно выходы четвертого, пятого и шестого элементов И, единичный выход второго триггера соединен с вторым входом второго элемента И и является пятымвыходом блока, входом "Стоп" которого является нулевой вход первоготриггера, выход элемента ИЛИ соединен с входом одновибратора, выходкоторого является шестым выходом,блока, а также соединен с установоч-.ными входами первого и второго счетчиков и через пятый элемент НЕ сое.динен с третьим входом первого эле-,Изобретение относится к вычислительной технике и может быть ис" пользовано при построении стохастических и специализированныхвычислительных машин и устройств,Известен генератор псевдослучайных чисел, содержащий регистр сдвига с сумматором по модулю 2 в цепи обратной связи (1.Однако этот генератор обладает малой длиной псевдослучайной последовательности.Наиболее близким по технической сущности к изобретению является ге. нератор псевдослучайных чисел, содержащий блок памяти, регистры памяти, элементы эквивалентности счетчика, регистры памяти, блок сумматоров по модулю два, блок управления (2 Я.Однако известный генератор сло" жен по технической реализации. Кроме того, использованный способ установки начального состояния генератора (занесения информации в па" мять) не обеспечивает оптимальных корреляционных свойств генерируемой последовательности, так как в силу случайного (псевдослучайного) характера заполнения ячеек памяти в начальном состоянии интервалы сдвига между бинарными последовательностями, формируемые в отдельных разрядах -разрядных псевдослучайных чисел в режиме генерации, получаются произвольными и могут быть существенно меньше величины М/0, где М - период последовательности, и даже меньше заданного объема выборки, что, в конечном счете, отра-, жается на точности генерирования.Цель изобретения - повышение точности генератора и сокращение аппаратурных затрат на его реализацию. мента И, выход которого соединен сосчетным входом второго счетчика,:первый выход которого соединен спервыми входами первого и шестогоэлементов И непосредственно и черезвторой элемент НЕ соединен с первымвходом четвертого элемента И,.нулевой выход второго триггера соединенс первым входом пятого элемента И,второй выход второго счетчика соединен с вторыми входами третьего ичетвертого элементов И непосредст-венно и через третий элемент НЕ сое.динен с вторыми входами пятого и шестого элементов И. Для достижения поставленной цели в генератор псевдослучайных чисел, содержащий 2-разрядный регистр памяти, выходы которого являются выходами генератора, блок сумматоров по модулю два, элемент эквивалентности, первый и второй входы которого соединены соответственно с -м (1 )В) и С-м выходами Ю-разрядно" го регистра памяти, а выход элемента эквивалентности соединен с информационным входом В-разрядного регистра памяти, блок памяти, блок задания режимов и счетчик адреса, выходы которого подключены к адресным входам блока памяти соответстзенно, введены М-разрядный (1 с ) регистр памяти, разрядные входы которого соединены с соответствующими выходами младших 1 разрядов В-разрядного регистра памяти, а выходы 1 сразрядного регистра памяти соединены с разрядными входами 1 старших разрядов блока памяти соответственно, младшие Р- разрядных входов блока памяти соединены с соответствующими выходами старших Ъ-М разрядов 1-раэряднЬго регистра памя.ти, В выходов блока памяти соединены с первой группой входов блбкаеумматоров по модулю два соответственно, вторая группа входов которогоподключена к 0 выходам В-разрядного регистра памяти соответственно,а выходы блока сумматоров по модулю два подключены к соответствующимвходам В-разрядного регистра памяти,первый и второй входы блока задания режимов являются соответственновходами "Пускф и "Стоп" генератора,а первый выход блока задания режимов подключен ко входам синхронизации 1-разрядного и М-разрядного регистров памяти, второй вход блока задания режимов подключен коУстройство работает следующимобразом,В начал.ном режиме блок б вырабатывает начальный сигнал"Уст,Оф, который устанавливает внулевое состояние счетчик 7 адреса и регистры 2 и 4, Начиная спервого такта, блок б вырабатываетпоследовательности из трех импульсов: "ЗН", "ЗП" и "+1", поступающих соответственно на входы синхронизации регистров 2 и 4, вход уп"равлеиия записью. блока 5 памяти исчетный вход счетчика 7 адреса. Дляуправления работой регистра 2 блок бвырабатывает потенциальный сигналрежима сдвига инФормации фВР=1 ф.При наличии потенциала сдвига фВРщ 1 фи поступлений импульсов фЗН" регистр2 работает в режиме сдвига записанной информации в сторону старших раз"рядов. При этом запрещена запись врегистр 2. информации, присутствующей на выходах блока 1 сумматоровпо модулю два, и разрешена записьсигналов, поступающих на последовательный вход первого разряда регистра 2 с выхода элемента 3 эквивалентности. Таким образом, в начальном режиме регистр 2 и элемент 3 представляют собой генератор двоичной последовательности .с псевдослучайным порядком следования нулей и единиц, Следует заметить, что в отличие от известныхгенераторов псевдослучайных последовательностей на регистре сдвигав данном устройстве нулевое состоя-ние регистра 2 не является запре-.щенным, что достигается включениемв цепь обратной связи регистра 2элемента эквивалентность вместо сум"матора по еоЬ 2.Работа генератора в начальномрежиме происходит следующим образом.Импульсы фЗН" и потенциал фВР=1 ф,поступая на регистр 2,приводят к то.му, что последний совместно с элементом 3 Формирует -разрядные псев. входам "Установкаф 7.-разрядного и 1 с;разрядного регистров памяти и счетчика адреса, третий выход блока задания режимов подключен ко входу управления режимом. -разрядного регистра памяти, четвертый и пятый выходы блока задания режимов соединены соответственно со входами управления чтением и записью блока памяти, шестой выход блока задания режимов соединен со счетным входом счетчика адреса.Кроме того, блок задания режимов содержит два триггера, два счетчика, одновибратор, три элемента НЕ, элемент ИЛИ, шесть эле ментов И и генератор импульсов; выходкоторого соединен с первым входом первого элемента И, второй ,вход которого подключен к дыходу первого триггера, единичный вход которого является входом Пуск блока,а также соединен с первым входом эле:мента ИЛИ и единичным входом второго триггера,.нулевой вход которого соединен со вторым входом элемен- . 25 та ИЛИ и с выходом первого счетчика, счетный вход которого подключен к выходу второго элемента И, первый вход которого соединен с Выходом третьего элемента И и является первым выходом блока, вторым, третьим и четвертым выходами которого являются соответственно Выходы четвертого, пятого и шестого элементов И, единичный выход второго триггера соединен со вторым входом второго элемента И и является пятым выходом блока, входом "Стоп" которогоявляется нулевой вход первого триггера,. Вцход элемента ИЛИ соединен со входом одновибратора, выход кото рого является шестым выходом блока, а также соединен с установочными входами первого и второго счетчиков и через первый элемент НЕ соединен с третьим входом первого элемента И, 45 выход которого соединен со счетным входом второго счетчика, первый вы- ход которого соединен с первыми входами третьего и шестого элементов И непосредственно и через второй эле мент НЕ соединен с первым входом четвертого элемента И, нулевой выход второго триггера соединен с первым входом пятого элемента И, ВТОРОЙ ВыхоД ВТОРОГО счетчика сОе динен со вторыми входами третьего .и четвертого элементов И непосредственно и через третий элемент НЕ соединен со вторыми входами пятого и шестого элементов И.На фиг.1 дана блок-схемагенера тора; на Фиг,2 - схема блока задания режимов; на Фиг.3 - диаграмма работы генератора.Генератор содержит блок 1 сумматоров по модулю два, У-разрядный ре гистр 2 памяти, элемент 3 эквивалентности, 1 с-разрядный регистр 4 памяти, блок 5 памяти, блок б задания режимов и счетчик 7 адреса.Блок б задания режимов содержит генератор 8 импульсов, триггеры 9 элемент ИЛИ 10, одновибратор 11, счетчики 12, элементы И 13, элементы НЕ 14.Устройство имеет два основных режима: начальный режим формирования псевдослучайной информации и рабочил режим - режим форьирования ивыдачи й"разрядных псевдослучайных чисел. Режимы работы задаются соответствующими сигналами с выходов блока б (фиг,2).10 В рабочем режиме генератор работает следующим образом,В первом такте по сигналу обращения к памяти "Чт" производится выборка содержимого нулевой ячейки55блока 5. Сигналы, соответствующиеразрядам считанного числа, появляются на выходных разрядных шинахблока 5 и поступают на первые входысумматоров по щод 2 блока 1. , бОНа. вторые входы сумматоров повод 2 этого блока поступают разрядычисла, хранящегося в регистре 2,В,результате на выходах блока 1 появляется читало, представляющее со- б 5 дослучайные числа, которые по сигналу "ЗПф в каждом такте записываются в ячейки блока 5 памяти, после чего содержимое счетчика 7 адреса по сигналу "+1" увеличивается на5 единицу. То обстоятельство, что младшие 1 разрядов сформированного в регистре псевдослучайного числа вначале переписываются в регистр 4, а затем заносятся в ячейку блока 5 памяти на место старших разрядов одновременно с - старшими разрядами вновь сформированного псевдослучайного числа иэ регистра 2 принципиального значения в начальном режиме работы не имеет, поскольку 15 главная задача работы генератора в начальном режиме - заполнение ячеек памяти блока 5 ненулевыми псевдослу- чайными комбинациями. Эта задача полностью реализуется с помощью ре гистра 2 с элементом 3 в цепи обрат. ной связи.Минимально необходимое количество тактов работы генератора в начальном режиме определяется числом ячеек25 блока памяти ц. Следует однако заметить, что на начальном участке генерации псевдослучайной последовательности в регистре 2 формируются числа с малым количеством еди- . 30 ниц. В .связи с этим во избежание заполнения блока памяти комбинациями с малым числом единиц время работы генератора в начальном режиме целесообразно увеличить по меньшей З 5 мере до 2 1 тактов (как правило, 0)ц).По окончании начального режима (переключение сигнала ВР с единицы на ноль) регистр 2 переходит в ре,жим записи информации параллельным кодом, В этом режиме сигналы с выхода элемента 3 эквивалентности не воспринимаются первым разрядом регистра 2,После переключения сигнала "ВР" в фО" блок б выдает второй сигнал 45 фуст.О", осуществляющий сброс регистров 2,4 и счетчика 7 в ноль. Со следующего такта начинается рабочий режим формирования 2-разрядных псевдослучайных чисел. 50 бой поразрядную сумму входных чисел. Эта поразрядная сумма является первым псевдослучайным числом, которое по сигналу "ЗН" записывается в регистр 2 и одновременно появляется на выходах генератора 8. По этому же сигналу первыеразрядов прежнего числа иэ регистра 2 переписыва" ются в регистр 4. Задержка между сигналами "4 Тф и "ЗНп необходима для завершения операций выборки числа иэ блока 5 памяти и поразрядного суммирования его с числом иэ регистра 2 блока 1 сумматоров.Во второй половине первого такта по сигналу обращения к памяти "ЗП" информация, присутствующая на входных разрядных шинах блока 5, записывается в ту же нулевую ячейку, Записанное в память число представляет собой комбинацию младших 1 разрядов предыдущегопсевдослучайного числа из регистра 4 и старших М-К разрядов нового псевдослучайного числа из регистра 2. Первый такт работы генератора заканчивается увеличением содержимого счетчика 7 адреса на единицу по сигналу "+1 фот блока б.Во. втором такте выполняются те же операции, что и в первом, с той лишь разницей, что чтение и запись информации осуществляется уже не из нулевой, а иэ первой ячейки блока 5 памяти.В дальнейшем в каждом новом такте последовательно изменяется состояние счетчика 7.и происходит последовательное обращение к ячей кам блока 5 памяти, При этом в первой половине такта осуществляется считывание 1-разрядного числа из . выбранной ячейки памяти, его поразрядное сложение с числом, хранящимся в регистре 2, запись полученного результата в регистр 2 и выдача его на выход устройства и одновременно передача младших К разрядов прежнего содержимого регистра 2 в регистр 4Во второй половине такта в выбранную ячейку памяти на Место младших разрядов записываются старшие 1"К разрядов вновь сформированного псевдослучайного числа из регистра 2, а на место старших разрядов - младшие разрядов предыдущего псевдослучайного числа иэ регистра 4, после чего содержимое счетчика 7 увеличивается на единицу.После завершения ц тактов работы генератора происходит. обнуление счетчика 7 адреса, имеющего модулем пересчета величину о,и обращение вновь к нулевой ячейке блока 5 памяти. Даль" нейший процесс формирования псевдослучайных чисел очевиден.Блок б задания режимов работает следующим образом.521 521 127 151 175 201 48 32 1617 9 41 8 10 16 10 10 По сигналу "Пуск 1 оба триггераустанавливаются в единичное состоя .1ние и запускается одновибратор;формирующий выходной .сигнал "Уст,Оф,Сигналом с выхода одновибратора устанавливаются в исходное состояниея счетчики. По окончании сигналафуст.О" с помощью элемента НЕ, подклюЧенного к:выходу.одновибратора,формируется единичный потенциал навход элемента И, разрешающий прохождение тактовых импульсов от генератора импульсов на вход счетчика.Тем саьим инициализируется начальный: режим работы генератора псевдослучайных чисел. Значение сигнала"ЬРф, снимаемого с единичного выхода триггера, в этом режиме равно 1,а на выходе распределителя формируется только три последовательностиуправляющих сигналов "3 Нф .дЗПцф+1" (сигнал "4 Тф блокируется нулевым потенциалом с инверсного выхода триггера), По окончании каждого такта по сигналу "+1" содержимое счетчика увеличивается на единицу,Так происходит до тех пор, пока старший разряд счетчика не переключится в единичное состояние, вызывая сброс триггера в ноль и повторный запуск одновибратора и фикси-. руя тем самым переход генератора в рабочий режим. В рабочем режиме сигнал фВР=О", а на выходе распределителя последовательно формируются импульсы всех четырех унравляющих последовательностей ф 4 Тф,ффЗНф "ЗП", "+1". Выработка управляющих сигналов прекращается,.когда на . вход блока поступает сигнал останоэа. Преимуществом предлагаемого генератора по сравнению с известным явля-.ется то, что объем выборки, на котором отсутствует корреляция между-разрядными псевдослучайными числами, максимален и равен величине М/Втактов.Другим преимуществом данного генератора является сокращение аппа-ратурных затрат на реализацию. Необходимый объем памяти в известномустройстве определяется величинойв 1 1 ит (или в 9-разрядных ячеек),а в данном устройстве он равен ц .2 бит(или ц 1;разрядных ячеек), причем15 в(ц 7 В. Например, при в = 127, й = 15и ц = 8 отношение вц 16, т.е. имеет место 16-кратное сокращениеобъема памяти. Кроме того, сокращаются затраты на реализацию второ 20 го буферного регистра (к=7 разрядов вместо= 15), второго счет.,чика и второго элемента эквивалентности (в предлагаемом устройстве отсутствуют).Таким образом, техникО-экономический эффект предлагаемого устрой"ства по сравнению с известным, заключается в повышении точности генерирования псевдослучайных чисел,что проявляется в увеличении интервала, на котором отсутствует корреляция между числами, до М/В тактови уменьшении аппаратурных затрат, в:частности, в сокращении необходимогообъема памяти в в/ц раз,В таблице приведены основные параметры, рекомендованные для реализации генераторов псевдослучайнйхчисел, полученные в результате отбора характеристических полиномов40 хп+х+1 с подходящими для практических случаев значениями в и В1013955 Нацаиьный режим Ра 5 счии реяим Ьоакт Хлиют. оставитель А,Карасовехред К.Иыцьо Кор С. Шекм дактор Н.Егор ПодписноеСР 58 Тираж 704ВНИИПИ Государственного комитета Спо делам изобретений и открытий 113035, Москва, Ж, Раушская наб Заказ 300 Дв ектная,илиал ППП фПатентф, г. Ужгород, у