Генератор псевдослучайных чисел Советский патент 1983 года по МПК G06F7/58 

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

мента И, выход которого соединен со счетным входом второго счетчика, первый выход которого соединен с первыми входами первого и шестого элементов И непосредственно и через второй элемент НЕ соединен с первым входом четвертого элемента И, нулевой выход второго триггера соединен с первым входом пятого элемента И, второй выход второго счетчика соединен с вторыми входами третьего и четвертого элементов И непосредс твенно и череэ третий элемент НЕ соединен с вторыми входами пятого и шестого элементов И,

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

1

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

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

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

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

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

Цель изобретения - повышение точности генератора и сокращение аппаратурных затрат на его реализацию.

Для достижения поставленной цели в генератрр псевдослучайных чисел, содержащий Е-разрядный регистр па мяти, выходы которого являются выходами генератора, блок сумматоров по модулю два, элемент эквивгшентности, первый и второй входы которого соединены соответственно с j-м () и tr-M выходами В-разрядно0 го регистра памяти, а выход элемента эквивалентности соединен с информационным входом Е-разрядного регистра памяти, блок памяти, блок задания режимов и счетчик адреса,

5 выходы которого подключены к адресным входам блока памяти соответственно, введены k-разрядный () регистр памяти, разрядные входы которого соединены с соответствующими

выходами младших k разрядов Е-разрядного регистра памяти, а выходы kразрядного регистра Пс1мяти соединены с разрядными входами k стаЕяиих разрядов блока памяти соответственно, младшие E-k разрядных входов

блока памяти соединены с соответствующими выходами старших Г-k разрядов Е-раэряднЪго регистра памя.ти, I выходов блока памяти соединены с первой группой входов блс5ка

0 сумматоров по модулю два соответственно, вторая группа входов которого -подключена к С выходам Е-разрядного регистра памяти соответственно, а выходы блока сумматоров по модулю

5 два подключены к соответствующим

ВХОД61М Е-разрядного регистра памяти, первый и второй входм блока задания режимов являются соответственно входами Пуск и Стоп генератора,

0 а первый выход блока задания режимов подключен ко входам синхронизации Е-разрядного и k-разрядного регистров памяти, второй вход блока задания режимов подключен ко входам Установка -разрядного и К-разрядного регистров памяти и счетчика адреса, Третий выход блока задания режимов подключен ко входу управления режимом. -разрядно гр регистра памяти, четвертый и пятый выходы блока задания режимов соединены соответственно со входами управления чтением и записью блока памят, шестой выход блока задания режимов соединен со счетным входом счетчика адреса. Кроме того, блок задания режимов содержит два триггера, два счётчика, одновибратор, три элемента НЕ, элемент ИЛИ, шесть элементов И и генератор импульсов выход которого соединен с первым входом первого элемента И, второй .вход которого подключен к выходу пе вого триггера, единичный вход котор го является входом Пуск блока,а также соединен с первым входом эле1мента ИЛИ и единичным входом второг триггера, нулевой вход которого соединен со вторым входом элемента ИЛИ и с выходом первого счетчика, счетный вход которого подключен к выходу второго элемента И, первый вход которого соединен с выходом третьего элемента И и является первым выходом блока, вторым, тр тьим и четвертым выходами которого являются соответственно выходы четвертого, пятого и.шестого элементов И, единичный выход второго три гера соединен со вторым входом второго элемента И и является пятым вы ходом блока, входом Стоп которого является нулевой вход первого триггера,, выход элемента ИЛИ соединен со входом одновибратора, выход кото рого является шестым выходом блока а также соединен с установочными вх дами первого и второго счетчиков и через первый элемент НЕ соединен с третьим входом первого элемента И, выход которого соединен со счетным входом второго счетчика, первый вы ход которого соединен с первыми вх дами третьего и шестого элементов непосредственно и через второй эле мент НЕ соединен с первым входом четвертого элемента И, нулевой выход второго триггера соединен с первым входом пятого элемента И, второй выход второго счетчика соединен со вторыми вхаца1иш третьего и четвертого элементов И непосредственно и через третий элемент НЕ соединен со вторыми входами пятого и шестого элементов И. На фиг.1 дана блок-схема генера тора; на фиг.2 - схема блока задания режимов на фиг.З - диаграявл работы генератора. Генератор содержит блок 1 сумма ров по модулю два, Р-разрядный реистр 2 памяти, элемент 3 эквивалентости, k-разрядный регистр 4 памяи, блок 5 памяти, блок б задания ежимов и счетчик 7 адреса. Блок 6 задания режимов содержит енератор 8 импульсов, триггеры 9 лемент ИЛИ 10, одновибратор 11,. счетчики 12, элементы И 13 элемены НЕ 14. Устройство имеет два основных ежима: начальный режим формирования псевдослучайной информации и рабочил режим - режим форккрования и выдачи Е-разрядных псевдослучайных исел. Режима работы задаются соответствующими cигнaлa aI с выходов блока б (фиг.2). Устройство работает следующим образом. В начальном режиме блок б вырабатывает начальный сигнал Уст.О, который устанавливает в нулевое состояние счетчик 7 адреса и регистры 2 и 4. Начиная с первого такта блок 6 вьфабатыаает последовательности из трех импульсов: ЗН, ЗП и 4-1, поступающих соответственно на входы синхронизации регистров 2 и 4, вход управления записью, блока S памяти и счетный вход счетчика 7 адаеса. Для управления работой регистра 2 блок 6 вырабатывает потенциальный сигнал режима сдвига информсщии 8. При наличии потенциала сдвига и поступлений импульсов ЗН регистр 2 работает в режиме сдвига записанной информации в сторону старших разрядов. При этом запрещена запись в регистр 2 информации, присутствующей на выходах блока 1 сумматоров по модулю два, и запись сигналов, поступаюпдах на йоследовательный вход первого разряда регистра 2 с выхода элемента 3 эквивалентности. Таким образом, в начальном режиме регистр 2 и элемент 3 щ едставляют собой генератор двоичной последовательности с псевдослучайным порядком следования нулей и единиц. Следует заметить, что в отличие от известных генераторов псевдослучайных последовательностей на регистре сдвига в данном устройстве нулевое состояние регистра 2 не является запрет щенным, что достигается включением в цепь обратной связи регистра 2 элелюнта эквивалентность вместо сумматора по fflod2. Работа генерат ч а в начальном режиме происходит следующим образом. Импульсы ЗН и потенциал , поступая на регистр 2,приводят к тог му, что последний совместно с элементом 3 формирует t-разрядные псев

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

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

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

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

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

В первом такте по сигналу обращения к памяти Чт производится выборка содержимого нулевой ячейки блока 5. Сигналы, соответствуняцие разрядам считанного числа, появляются на выходных разрядных шинах блока 5 и поступают на первые входы сумматоров по mod 2 блока 1.

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

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

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

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

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

Блок 6 задания режимов работает следующим образом. По сигналу Пуск оба триггера у станавливаются в единичное состояние и запускается одновибратор формирующий выходной сигнал Уст.О Сигналом с выхода одновибратора устанавливаются в исходаое состояние и счетчики. По окончании сигнала Уст.О с помощью элемента НЕ, подключенного к выходу одновибратора, формируется единичный потенциал на вход элемента И, разрешающий прохож дение тактовых импульсов от генератора импульсов на вход счетчика. Тем самым инициализируется начальныв: режим работы генератора псевдослучайных чисел. Значение сигнала БР, снимаемого с единичного выхода триггера, в этом режиме равно 1 а на выходе распределителя формируется только три последовательности управляющих сигналов , ЗП, +1 (сигнал 4Т блокируется нулевым потенциалом с инверсного выхода триггера). По окончании каждого такта по сигналу +1 содержимое счетчика увеличивается на единицу. Так происходит до тех пор, пока старший разряд счетчика не переключится в единичное состояние, вызывая сброс триггера в ноль и повторный запуск одновибратора и фиксиРУ9-тем самым переход генератора в рабочий режим. В рабочем режиме сигнал , а на выходе распределите ля последовател(ьно Формируются импульсы всех четырех управляницих последовательностей 4Т,ЗН ЗП, +1. Выработка управляющих сигналов прекращается, когда на . вход блока поступает сигнал остано ва. .

127

151

15

15

10

201

521

521

175

32

48

16 17

41

14

10

16

11

10 Преимуществом предлагаемого генератора по сравнению с известным является то, что объем выборки, на котором отсутствует корреляция между Е-разрядными псевдослучайными числами, максимален и равен величине М/Е тактов. Другим преимуществом данного генератора является сокращение аппаратурных затрат на реализацию. Необходимый объем памяти в известном устройстве определяется величиной m-l ит (или mЕГразрядныхячеек) , а в данном устройстве он равен q-Е бит (или q .-разрядных ячеек) , причем . Например, при m 127, 15 и q 8 отношение m/q-я Хб, т.е. имеет место 16-кратное сокращение объема памяти. Кроме того, сокращаются затраты на реализацию второго буферного регистра ( разрядов вместо I 15), второго счет ,чика и второго элемента эквивалентности (в предлагаемом устройстве отсутствуют) . Таким образом, технико-экономический эффект предлагаемого устройства по сравнению с известным, заключается в повышении точности генерирования псевдослучайных чисел, что проявляется в увеличении интервала, на котором отсутствует корреляция между числами, до М/И тактов и уменьшении аппаратурных затрат, в частноёти, в сокращении необходимого объема памяти Е m/q раз. В таблице приведены основные параметры, рекомендованные для реализации генераторов псевдослучайН1 х чисел, полученные в результате отбора характеристических i полиномов с подходящими для практических случаев значениями m и :

Паск

Ост.

tr/

аст.0

0Ut.l