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

 

ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ, содержащий генератор тактовых импульсов, регистр сдвига, в цепь офатной связи которого включен сумматор по модулю два, о тли ч а к щи и с я тем, что, с целью упрощения генератора, содержит :9лемент Й-НЕ, первый вход которого соединен с его выхо- . дом и с тактовым входом регистра сдвига , а второй вход элемента И-НЕ подключен к выходу генерасгора тактовых импульсов .

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

СОф4АЛИСТИЧЕСНИХ

РЕСПУБЛИН .

3(5ц G 06 F 7/58

ОПИСАНИЕ ИЗОБРЕТЕНИ

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ГЮ ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3414278/18-24 (22) 29.03.82 (46) 07.06.83. Бюл. ¹ 21 (72) В. Н. Ярмолик и И. П, Кобяк. (71) Минский радиотехнический институт: (53) 681.325 (088.8) (56) 1. Яковлев В. В» Федоров P. Ф.

Вероятностные вычислительные машины. ,Л., Машиностроение, 1974, с. 228.

2. Кирьянов Б. Ф.. Многоканальный генератор псевдослучайных символов.«Известия АН СССР. Техническая кибер нетика, 1970,. №.4, е. 107.

3. Авторское свидетельство СССР № 572823, .кл. 006K 7/58, .1975 (прототип) .

„„SU„„1022163 А (54) (57) ГЕНЕРАТОР ПСЕВДОСЛУ»

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

1 1022163 2

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

Известны генераторы псевдослучайных чисел, основанные на применении регистров сдвига. Простейшим генератором на базе регистра сдвига является последовательный генератор псевдослучайных чисел t 1) .

Для получения многоразрядного двоичного числа работу данного устройства следует:моделировать Й l Мчисло тактов, где л разрядность регистра сдвига.

Частота выборки псевдослучайных чисел в Й раэ меныце тактовой частоты.

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

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

Наиболее близким к предлагаемому является генератор лтсевдослучайных чисел, содержащий vn триггеров, входы которых подключены к тактовому входу генератора, а выходы являются выходами генератора, и (И -1) сумматоров по модулю два, где 1- номер ячейки регистра сдвига, образующий обратную связь 3 .

Однако данное устройство содержит избыточное количество сумматоров по модулю два, а методика построения

ГПСЧ применима лишь для частного случая, когда цепь обратной связи генератора.состоит только из одного полусумматора.

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

5 да последовательностей.

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

< связи которого включен сумматор по модулю два, введен элемент И-НЕ, первый вход которого соединен с его выходом и с тактовым входом регистра сдвига, а второй вход элемента И-НЕ подключен к выходу генератора тактовых импуль сов.На фиг. 1 показана схема генератора; на фиг. 2 - диаграмма работы генератора.

20 . Генератор содержит генератор 1 тактовых импульсов, элемент 2 И-НЕ и регистр 3 сдвига с сумматором 4 по модулю два в цепи обратной связи. Повь нение. качества выходной псевдослучайной последовательности происходит за счет флуктуации времен задержки фронтов тактовых импульсов генератора 1.

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

40 ток (дробовой Зффект )в тепловом движении этих носителей зарядов (тепловой шум), в изменениях проводимости под воздействием некоторьм случайных факторов (модуляционный шум и r. д..

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

Тактовый импульс от генератора 1 поступает на второй вход элемента

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

55 случайным образом меняться or одного тактового импульса к другому за счет флуктуации длительности тактовых импульсов. Генерация пакета синхросигналов осуществляется элементом И-НЕ

10221 63

Р /

4Ь4 Г

ВНИИПИ Заказ 4045/41. Тираж 706 Подписное

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

3 в связи с логическим противоречием между первым входом элемента и его BblKDдом в момент подачи тактового импуш

ica на второй вход.- Сформированный пакет синхросигналов поступает на синхрожоды триггеров-регистра сдвига, причем на

° средних и низких частотах количество синхросигналов в п акете значительно больше разрядности регистра 3 сдвига.-Поэтому эа один такт информация обновляется полно-10 стью. Кроме того, новое число соответствует числу, случайным образом взятому с кольца М- последовательности. Это .позволяет практически. неограниченно удлинить период формируемых чисел; f5

В элементе 2 можно испольэовать, кроме укаэанного элемента -HE, двухвходовой сумматорпо модутподва и другие алементы с соответствукпцей обратной связью. 20

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

ГПСЧ. Важным достоинством технического решения является то,. что выборка чисел проводится не жестко через определенное число тактов, а достаточно случайно, что позволяет неограниченно увеличить период следования чисел.

По сравнению с прототипом в пред- лагаемом ГПСЧ аппаратный затраты ие зависят от вида обратной связи регистр ра сдвига и составляют дпя любой структуры 1/4 микросхемы К1 58ЛАЗ. Прототин пу же свойственна укаэанная зависимость, и при построении, например, 13-разрядного ГПСЧ на 33-разрядном регистре сдвига избыточность аппаратуры будет составлять 13 элементов сложения по модулю два.

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

Подобные устройства целесообразно использовать для построения генераторов случайных процессов с эаданнымн характеристиками, а также в аппаратуре контроля и диагностики цифровых устройств при выпуске изделий для ЭВМ.