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

Йиг./

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

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

Для получения многоразрядного двоичного числа работу данного устройства следует моделировать Ы7/)1число тактов, где Ум эаарядность регистра сдвига. Частота выборки псевдослучайных чисел в Ы раз меньше тактовой частоты.

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

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

Наиболее близким к предлагаемому явуляется генератор псевдослучайных чисел, содержащий Ш триггеров, входы которых подключены к тактовому входу генератора, а выходы являются выходами генератора, и (m-i) сумматоров по модулю два, где i - номер ячейки регистра сдвига, образукшшй обратную связь f3 .

Однако данное устройство содержит избыточное количество сумматоров по модулю два, а методика построения ГПСЧ применима лишь для частного случая, когда цепь обратной связи генератора состоит только из одного полусумматора. . Цель изо фетения - упрощение генератора за счет уменыиения объема используемого оборудования, повьш1ёш1я надежности устройства, повышения качества выходной последовательности и росширения функциональных возможностей устройства, за счет увеличения разрядности псевдослучайных кодов, увеличения периода последовательностей.

Поставленная цель достигается тем, что в генератор псевдослучайных чисел, содержаший генератор тактовых импутп сов, регистр сдвига, в цепь обратной связи которого включен сумматор по модулю два, введен элемент И-НЕ, первый вход которого соединен с его выходом и с тактовым входом регистра сдвига, а второй вход элемента И-НЕ подключен к ВЫХОДУ генератора тактовых импульсов. На фиг. 1 показана схема генератора; на фиг. 2 - диаграмма работы генератора.

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

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

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

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

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

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

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

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

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

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

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

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