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

 

Изобретение относится к вычислительной технике и может быть использовано для статистического моделирования и диагностики цифровых систем. Целью изобретения является расширение функциональных возможностей генератора путем обеспечения возможности изменения периода и вида формируемой последовательности. Генератор содержит i-разрядный регистр, выходы которого являются выходами генератора , блок сумматоров по модулю два, вторая группа входов которого подключена к i-выходам i-разрядного регистра, блок памяти и блок задания режимов, первый вход которого является входом Пуск генератора , четвертый и пятый выходы блока задания режимов соединены соответственно с синхровходом и входом управления режимом i-разрядного регистра. Новым является введение в генератор второго и третьего блоков памяти, первого и второго блоков элементов И, мультиплексора, i-входового сумматора по модулю два, двухвходового сумматора по модулю два и триггера с соответствующими связями. Работа генератора псевдослучайных чисел основана на принципе эмуляции регистра сдвига длиной по N1 разрядов, состоящего из D- и Т-триггеров. 1 з.п. ф-лы, 6 ил. ел С

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

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

РЕСПУБЛИК (я)л G 06 F 7/58

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕН

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4843406/24 (22) 25.06.90 (46) 30.03.93. Бюл, № 12 (71) Казанский авиационный институт им. А.Н.Туполева (72) М.И.Бурнашев и Г.Н.Порфирьев (56) Федоров P.Ô., Яковлев В,В., Добрис

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

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

¹ 1013955, кл. G Об F 7/58, 1983, (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано для статистического моделирования и диагностики цифровых систем. Целью изобретения является расширение функциональных возможностей генератора путем обеспечения возможности изменения периода и вида формируемой последовательности, Изобретение относится к вычислительной технике и может быть использовано для статистического моделирования и диагностики цифровых систем.

Цель изобретения — расширение функциональных возможностей генератора путем обеспечения возможности изменения периода и вида формируемой последовательности, На фиг.1 представлена схема генератора; на фиг,2 — схема блока управления; на фиг.3 и 4 показано расположение разрядов в блоках памяти; на фиг.5 — временные диаграммы работы генератора; на фиг.б — схема генератора, построенного на модулях операций сдвига и суммирования по модулю два.. Ж 1805465 А1

Генератор содержит i-разрядный регистр, выходы которого являются выходами генератора, блок сумматоров по модулю два, вторая группа входов которого подключена к i-выходам i-разрядного регистра, блок памяти и блок задания режимов, первый вход которого является входом "Пуск" генератора, четвертый и пятый выходы блока задания режимов соединены соответственно с синхровходом и входом управления режимом i-разрядного регистра, Новым является введение в генератор второго и третьего блоков памяти, первого и второго блоков элементов И, мультиплексора, i-входового сумматора по модулю два, двухвходового сумматора по модулю два и триггера с соответствующими связями, Работа генератора псевдослучайных чисел основана на принципе эмуляции регистра сдвига длиной по

NI разрядов, состоящего из D- u T-триггеров, 1 з.п. ф-лы, б ил.

Генератор содержит (фиг.1) триггер 1, первый сумматор 2 по модулю два, первый блок памяти 3, первый блок элементов И 4. блок 5 сумматоров по модулю два. мультиплексор 6, регистр 7, второй блок элементов

И 8, второй сумматор 9 по модулю два. выход

10 генератора, второй блок памяти 11. третий блок памяти 12 и блок 13 управления.

Блок 13 управления содержит первый регистр 14. второй регистр 15, счетчик адреса 16, мультиплексор 17. сумматор 18, третий регистр 19, генератор 20 тактовых импульсов. счетчик тактов 21. дешифратор

22, триггер 23, элементы И 24, элементы НЕ

25 и элементы ИЛИ 26.

Первый блок памяти 3. второй блок памяти 11 и третий блок памяти 12 организо1805465 ваны в виде (N+1)l-разрядных ячеек (I-разрядность выхода генератора). Первый блок памяти 3 эмулирует регистр сдвига длиной по Nlразрядов,,состоящий из D- и Т-триггеров. Расположение разрядов эмулируемого регистра сдвига в ячейках первого блока памяти 3 показано на фиг,3. Местоположение D-триггеров определяется нулями в соответствующих разрядах второго блока памяти 11, единицы определяют местоположение Т-триггеров. Третий блок памяти 12 определяет структуру обратной связи таким образом, что в формировании суммы обратной связи участвуют только разряды эмулируемого регистра сдвига, помеченные единицами в третьем блоке памяти 12. В начальный момент в нулевых ячейках всех блоков памяти записаны логические нули.

Для упрощения цепи занесения исходной информации в блоки памяти не показаны.

Уп ра влен ие работой устройства осуществляет блок 13 управления. По первому выходу блока 13 поступают сигналы на синхровход регистра 7, запись в который производится по переднему фронту синхросигнала. По второму выходу блок 13 задает режим записи (при логическом нуле) или сдвига (при логической единице) регистра 7.

По третьему выходу блока 13 поступают сигналы на синхровход триггера 1, запись в который производится по переднему фронту синхросигнала. По четвертому выходу блок 13 управления передает сигнал установки в нулевое состояние триггера 1 (при логической единице). 1lo пятому выходу блок 13 задает адрес ячейки первого блока памяти 3, второго блока памяти 11 и третьего блока памяти 12, По шестому выходу блок 13 управления задает режим записи/

/ чтения первому блоку памяти 3 (логический ноль задает режим записи, логическая единица — режим чтения), По седьмому выходу блок 13 управляет передачей данных через мультиплексор 6 (при логической единице передаются данные с первого информационного входа, при логическом нуле — со второго информационного входа мультиплексора 6).

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

По сигналу "Сброс", поступающему на второй вход блока 13 управления, производится установка в начальное состояние блока 13 и установка в нулевое состояние триггера 1 по сигналу, поступающему по четвертому выходу блока 13 на вход сброса триггера 1.

По сигналу "Пуск", поступающему на второй вход блока 13 управления, он начинает выдавать управляющие сигналы по своим выходам в каждом такте. В первом такте (фиг.5) по сигналам с выходов блока 13 производится следующее; из первого блока памяти 3 считывается содержимое N-й ячей5 ки и через первую группу входов мультиплексора 6 записывается врегистр 7,,Во втором такте считывается содержимое N-й ячейки из третьего блока памяти 12 и поступает на второй вход второго блока элемен"0 тов И 8, на первый вход которого поступает информация с выхода регистра 7. На выходе второго сумматора 9 по модулю два формируется сумма обратной связи от N-й ячейки первого блока памяти 3, которая через пер15 вый сумматор 2 по модулю два записывается в триггер 1 в конце такта. В третьем такте из первого блока памяти 3 считывается содержимое нулевой ячейки и поступает на первый вход первого блока элементов И 4, из второго блока памяти 11 считывается содержимое нулевой ячейки и поступает на второй вход первого блока элементов И 4, информация с выхода которого поразрядно суммируется в блоке 5 сумматоров по модулю два с содержимым регистра 7. Результат суммирования через второй вход мультиплексора 6 записывается в регистр 7, Так как во всех разрядах нулевой ячейки второго блока памяти 11 записаны логические нули, то содержание регистра 7 не изменяется. В четвертом такте информация с выхода регистра 7 записывается в нулевую ячейку первого блока памяти 3. Таким образом, содержимое N-й ячейки первого блока памяти 3 переписывается в нулевую ячейку.

В пятом такте из первого блока памяти 3 считывается содержимое (N-1)-й ячейки и через первый вход мультиплексора 6 записывается в регистр 7. В шестом такте из

40 третьего блока памяти 12 считывается содержимое (N-1)-й ячейки и поступает на второй вход второго блока элементов И 8, на первый вход которого поступает информация с выхода регистра 7, На выходе второго

45 сумматора 9 по модулю два формируется сумма обратной связи от (N-1)-й ячейки первого блока памяти 3, которая поступает на второй вход первого сумматора 2 по модулю два, на первый вход которого поступает сумма обратной связи от N-й ячейки первого блока памяти 3 с выхода триггера 1, На выходе первого сумматора 2 по модулю два формируется сумма обратной связи от N-й и (N-1)-й ячеек первого блока памяти 3, которая записывается в триггер 1 в конце шестого такта. В седьмом такте из первого блока памяти 3 считывается содержимое Nй ячейки и поступает на первый вход первого блока элементов И4, из второго блока памяти 11 считывается содержимое N-й

1805465 ячейки и поступает на второй вход первого блока элементов И 4, информация с выхода которого поразрядно суммируется в блоке 5 сумматоров по модулю два с содержимым регистра 7. Результат суммирования через 5 второй вход мультиплексора 6 записывается в регистр 7. В восьмом такте информация с выхода регистра 7 поступает на выход 10 генератора в качестве разрядов псевдослучайного числа и записывается в N-ю ячейку первого блока памяти 3. Таким образом, в тактах с четвертого по восьмой формируется новое содержимое N-й ячейки первого блока памяти 3 и выдается на выход 10 генератора, В следующих четырех тактах (с девятого по двенадцатый) аналогично формируется новое содержимое (N-1)-й ячейки первого блока памяти 3, и так далее (по четыре такта) до второй ячейки первого блока памяти 3. Новое содержимое первой ячейки первого блока памяти 3 формируется следующим образом. В (4N+1)-м такте из первого блока памяти 3 считывается содержимое нулевой ячейки и через первый вход мультиплексора 6 записывается в регистр 7. (В (4N+2)-м такте блока 13 управления по своему второму выходу задает режим сдвига в регистре 7, В освобождающийся разряд заносится сумма обратной связи, поступающая с выхода триггера 1 на последовательный информационный вход регистра 7. B (4N+3)-м такте из первого блока памяти 3 считывается содержимое первой ячейки и поступает на первый вход первого блока элементов И 4, из второго блока памяти 11 считывается содержимое первой ячейки и поступает на второй вход первого блока элементов И 4, информация с выхода которого поразрядно суммируется в блоке 5 сумматоров по модулю два с содержимым регистра 7, Результат суммирования через второй вход мультиплексора 6 записывается в регистр 7, В (4M+4)-м такте содержимое регистра 7 поступает на выход 10 генератора в качестве разрядов псевдослучайного числа и записывается в первую ячейку первого блока памяти 3. В этом же такте триггер

1 устанавливается в нулевое состояние по сигналу, поступающему по четвертому выходу блока 13 управления на вход сброса триггера 1. Таким образом, эмуляция сдвига информации в N-разрядном регистре завершена. Далее генератор работает аналогично.

В общем случае в первом блоке памяти

3 может эмулироваться несколько независимых регистров сдвига (см. фиг.4). Для каждого из этих регистров отводится по одной дополнительной ячейке (в данном случае нулевая для регистра сдвига А. i-я для регист10

55 ра сдвига В и (N-3)-я для регистра сдвига С.

В О-й, i-й и (N-3)-й ячейках второго блока памяти 11 записаны логические нули во всех разрядах. Каждый из эмулируемых в первом блоке памяти 3 регистров сдвига можно охарактеризовать двумя величинами; количеством занимаемых ячеек первого блока памяти 3 и адресом первой (младшей) из этих ячеек, Для примера на фиг.4 регистр сдвига А характеризуется так: количество занимаемых ячеек равно двум, адрес первой ячейки равен нулю, регистр сдвига B характеризуется так: количество занимаемых ячеек равно трем, адрес первой из них равен i, регистр сдвига С характеризуется так; количество занимаемых ячеек равно четырем, адрес первой из них равен (N-3), Блок 13 управления работает следующим образом.

Предварительно во второй регистр 15 заносится количество занимаемых ячеек первого блока памяти 3, в третий регистр 19 заносится адрес первой из этих ячеек, Для упрощения цепи занесения информации во второй регистр 15 и третий регистр 19 не показаны. Счетчик адреса 16 работает как вычитающий счетчик по модулю, задаваемому во втором регистре 15. Ilo сигналу, поступающему на вход "Сброс" генератора, триггер 23. счетчик тактов 21 и счетчик адреса 16 устанавливаются в нулевое состояние. Через элемент ИЛИ 261 этот сигнал поступает на четвертый выход блока 13.

Логический ноль с прямого выхода триггера 23 блокирует прохождение синхроимпульсов (СИ) с выхода генератора 20 тактовых импульсов через элемент И 24, а также запрещает дешифрацию дешифратору 22. По сигналу. поступающему на вход

"Пуск" генератора. триггер 23 устанавливается в единичное состояние и разрешает прохождение СИ через элемент И 24>. а также разрешает дешифрацию дешифратору 22, С выхода элемента И 24 СИ поступают на первый вход элемента И 242 и на счетный вход счетчика тактов 21. На выходах с первого по четвертый дешифратора 22 формируются импульсы соответственно в каждый первый, второй. третий и четвертый такты. В самом первом такте содержимое счетчика адреса 16 (в данном случае нулевое) переписывается в первый регистр 14, а в счетчик адреса 16 заносится модуль счета из второго регистра 15. Мультиплексор 17 первые два такта из каждых четырех передает данные со счетчика адреса 16. последующие два такта — с выхода первого регистра

14, в котором хранится предыдущее состояние счетчика адреса 16. Сумматор 18 обес1805465

8 печивает сложение адреса с выхода мультиплексора с адресом первой занимаемой ячейки первого блока памяти 3, поступающим с выхода третьего регистра 19. С выхода сумматора 18 результат сложения поступает на пятый выход блока 13. Последующие импульсы с первого выхода дешифратора 22 вызывают уменьшение на единицу содержимого счетчика адреса 16 вплоть до нулевого. Следующий импульс снова приведет к загрузке в счетчик адреса

15 модуля счета. При нулевом содержимом счетчика адреса 16 на его выходе окончания счета появляется логическая единица. Импульсы с первого выхода дешифратора 22 поступают на вход элемента НЕ 252 и на третий выход блока 13, на седьмой выход которого поступают импульсы с третьего выхода дешифратора 22. СИ с выхода элемента И 241 поступают через элемент И

242 на первый выход блока 13 в каждом первом и третьем из четырех тактов, а также во втором такте из четырех и ри наличии сигнала окончания счета счетчика 16. Этот сигнал формируется в начале первого из четырех тактов, в которых завершается сдвиг информации B эмулируемом в первом блоке памяти 3 регистре сдвига. Во втором из этих четырех тактов формируется логическая единица на выходе элемента И 24з и поступает на второй выход блока 13. В четвертом из этих четырех тактов формируется логическая единица на выходе элемента И

244 и через элемент ИЛИ 26 поступает на четвертый выход блока 13. По второму входу элемента ИЛИ 26 на четвертый выход блока 13 поступают сигналы со входа "Сброс" генератора.

В случае эмуляции нескольких регистров сдвига в первом блоке памяти 3 для

"перехода" от одного регистра сдвига к другому подается сигнал по входу "Сброс" генератора, во второй регистр 15 и третий регистр

19 заносится информация о выбранном регистре сдвига и по сигналу "Пуск" осуществляется вышеописанным образом сдвиг информации в этом регистре.

Первый блок 4 элементов И, блок 5 сумматоров по модулю два, мультиплексор 6, регистр 7, второй блок 8 элементов И и второй сумматор 9 по модулю два образуют

1-разрядный модуль 27 операций сдвига и суммирования по модулю два, первый вход которого соединен с выходом первого блока памяти 3, второй вход — с выходом второго блока памяти 11, третий, четвертый и пятый входы соединены соответственно с седьмым, первым и вторым выходами блока 13 управления, шестой вход соединен с прямым выходом триггера 1. седьмой вход соединен с выходом третьего блока памяти 12.

Первый выход модуля 27 операций сдвига и суммирования по модулю два соединен с выходом генератора и с информационным

5 входом первого блока памяти 3, второй выход соединен со вторым входом первого сумматора 2 по модулю два, На фиг.6 представлена схема генератора псевдослучайных чисел, построенного с использованием

10 m модулей 27 операций сдвига и суммирования по модулю два. Шестой вход первого модуля 27 операций сдвига и суммирования по модулю два соединен с выходом триггера 1, шестой вход i-го (i = 2, m ) модуля

15 27; операций сдвига и суммирования по модулю два соединен с 1-м разрядом первого выхода (i-1)-го модуля 27ьi операций сдвига и суммирования по модулю два. Количество входов первого сумматора 2 по модулю два

20 увеличивается до (m+1). На выходе 10 генератора формируются ml разрядов псевдослучайного числа, Формула изобретения

25 1. Генератор псевдослучайных чисел, содержащий регистр, выход которого является выходом генератора, блок сумматоров по модулю два, первый вход которого подключен к выходу регистра, первый блок па30 мяти и блок управления, первый выход которого соединен с синхровходом регистра, вход управления режимом которого соединен с вторым выходом блока управления, первый вход которого является вхо35 дом "Пуск" генератора, о т л и ч а ю щ и йс я тем, что, с целью расширения функциональных возможностей генератора путем обеспечения изменения периода и вида формируемой последовательности, в него

40 дополнительно введены второй и третий блоки памяти, первый и второй блоки элементов И. первый и второй сумматоры по модулю два, мультиплексор и триггер, синхровход которого соединен с третьим выхо45 дом блока управления, четвертый выход которого соединен с входом сброса триггера, информационный вход которого соединен с выходом первого сумматора по модулю два, первый вход которого соеди50 нен с прямым выходом триггера и с последовательным информационным входом регистра, параллельный информационный вход которого соединен с выходом мультиплексора, первый информационный вход

55 которого соединен с выходом первого блока памяти и первым входом первого блока элементов И, второй вход которого соединен с выходом второго блока памяти, адресный вход которого соединен с адресными входами второго и третьего блоков памяти и с

1805465

10 пятым выходом блока управления, шестой выход которого соединен с входом управления записью-чтением первого блока памяти, информационный вход которого соединен с выходом регистра и с первым 5 входом второго блока элементов И, второй вход которого соединен с выходом третьего блока памяти, а выход — с входом второго сумматора по модулю два, выход которого соединен с вторым входом первого сумма- 10 тора по модулю два, второй вход блока управления является входом "Сброс" генератора, а седьмой выход соединен с управляющим входом мультиплексора, второй информационный вход которого 15 соединен с выходом первого блока элементов И.

2. Генераторпо п.1,отличающийс я тем, что блок управления содержит генератор тактовых импульсов, счетчик тактов, 20 дешифратор, три регистра, счетчик адреса, мультиплексор, сумматор, четыре элемента

И, три элемента НЕ, два элемента ИЛИ и триггер, вход установки в "1" которого является входом "Пуск" блока. вход "Сброс" ко- 25 торого соединен с входами сброса счетчика тактов, счетчика адреса, первым входом первого элемента ИЛИ и входом установки в "0" триггера, прямой выход которого соединен с входом разрешения дешифрато- 30 ра и с первым входом первого элемента И, второй вход которого соединен с выходом генератора тактовых импульсов, а выход— со счетным входом счетчика тактов и первым входом второго элемента И, выход ко- 35 торого является первым выходом блока, выход которого соединен с выходом третьего элемента И и первым входом второго элемента ИЛИ, выход которого соединен с вторым входом второго элемента И, а второй вход — с выходом первого элемента НЕ, вход которого соединен с младшим разрядным выходом счетчика тактов и с первым информационным входом дешифратора, первый выход которого соединен со счетным входом счетчика адреса и синхровходом первого регистра, второй выход дешифратора соединен с входом второго элемента НЕ и с третьим выходом блока, четвертый выход которого соединен с выходом первого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента И, первый вход которого соединен с выходом окончания счета счетчика адреса и с первым входом третьего элемента И, второй вход которого соединен с выходом второго элемента Н Е, выход второго регистра соединен с информационным входом счетчика адреса, выход которого соединен с первым информационным входом мультиплексора и с информационным входом первого регистра, выход которого соединен с вторым входом дешифратора и старшим разрядным выходом счетчика тактов, выход мультиплексора соединен с перВым входом сумматора, BTopQA ВхОд которого соединен с выходом третьего регистра, а выход является пятым выходом блока, шестой выход которого соединен с третьим выходом дешифратора и с входом третьего элемента Н Е, выход которого соединен с вторым входом четвертого элемента И, четвертый выход дешифратора является седьмым выходом блока.

1805465

1805465 +1 >+2

7 ко

1805465 е, е, Составитель М. Бурнашев

Техред М.Моргентал Корректор В. Петраш

Редактор

Заказ 943 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101