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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 06 З(59 С 06 Р 7 58 ПИСАНИЕ ИЗОБРЕТЕНИ СВИДЕТЕЛЬС АВТОРЧИК Р 13В.Ф. Гусеапин, В,М КузнеФ,и Федоровслительные моение", 197 етельство С 7/58, 1976 етельство С 7/58, 1973 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ(54)(57) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХЧИСЕЛ, содержащий Е Т-триггеров ии-М В-триггеров, о т л и ч а ю -щ и й с я тем, что, с целью расширения его функциональных возможностей за счет управления периодом М-последовательности, он содержит первуюгруппу из Епереключателей, вторуюгруппу из и-Епереключателей,двакоммутатора и блок памяти, группавходов которого является группой входов генератора, первая группа выходов блока памяти подключена к группе.входов первого коммутатора соответвтвенно, а вторая группа выходов,блока памяти подключена к группе.входов второго коммутатора соответственно, первый выход которого подключен к входу первого Р-триггера,а и-Костальных выходов второгокоммутатора подключены соответст-.венно к первым входам и-Епереключателей второй группы, второйвход каждого из которых подключен квыходу. одноименного В-триггера, авыход каждого переключателя второйгруппы подключен к входу последующего В-триггера, первый выход первого коммутатора подключен к входупервого Т"триггера, а 1-1 остальныхвыходов первого коммутатора подключены соответственно к"первымвходам К переключателей первойгруппы, второй вход каждого из ко-.торых подключен к выходу одноименного Т-триггера, а выход каждогопереключателя первой группы подключен к входу последующего Т-триггера,выход (и-Ц-го Р-триггера подключенк входу первого коммутатора, а выход Е-го Т-триггера - к входу второго коммутатора.Изобретение относится к вычислительной технике и может найти применение при статистическом моделировании в цифровых вычислительных машинах.Известен генератор псевдослучай ных чисел (генератор М-последовательности), содержащий сдвиговый регистр с сумматором по модулю два в цепи обратной связи. В этом генераторе очередное 1-разрядное двоич ное число образуется на выходах разрядов регистра через каждые Б тактов (Я 1, С) 113.Недостатками данного генератора являются низкое быстродействие и не возможность последовательности разных,периодов.Известен также генератор псевдослучайной последовательности, содержащий генератор тактовых импульсов, регистры, сумматоры по модулю два, коммутатор, дешифратор, делитель и триггер, позволяющий Формировать последовательности различных периодов 2 .Однако указанный генератор обладает значительной сложностью.Наиболее близким к предлагаемому является генератор псевдослучайных чисел (генератор М-последовательности), содержащий триггеры со счетны ми входами (Т-триггеры) и триггеры с установочными входами (Р-триггеры) 3 1.Недостатком известного генератора является отсутствие воэможности 35 формирования М-последовательностей различных периодов.Цель изобретения - расширение функциональных возможностей генератора псевдослучайных чисел .за счет управления периодом М-последовательностиПоставленная цель достигается тем, что генератор псевдослучайных чисел, включающий в себя к Т-тригге ров и и-К Р-триггеров, дополнительно содержит первую группу из Епереключателей, вторую группу из и-1 переключателей, два коммутатора и блок памяти, группа входов которого является группой входов50 генератора, первая группа выходов блока памяти подключена к группе входов первого коммутатора соответственно, а вторая группа выходов блока памяти подключена к группе 55 входов второго коммутатора, соответственно, первый выход которого подключен к входу первого Р-триггера, а и-1 остальных выходов второго коммутатора подключены соответствен но к первым входам и-Е переключателей второй группы, второй вход каждого из которых подключен к выходу одноименного Р-триггера, а выход каждого переключателя втоРой группы подключен к входу последующего Р-триггера, первый выход первого коммутатора подключен к входу первого Т-триггера, а костальных выходов первого коммутатора подключены соответственно к первым входам Епереключателей первой группы, второй вход каждого из которых подключен к выходу Одноименного Т-триггера, а выход каждого переключателя первой группы подключен к входу последующего Т-триггера, выход(п-Е)-го Р-триггера подключен к входу первого коммутатора, а выход К-го Т-триггера - к входу .второго коммутатора.На фиг,1 показана схема генератора псевдослучайных чисел; на фиг,2 пример технического решения коммутаторов 5 и б; на фиг. 3 - схема генератора с одновременным обновлениемразрядов за такт работы; на фиг,4-7 примеры выполнения генератора псевдослучайных чисел; на фиг. 8 - примеры соединения генераторов; на фиг. 9 - схема генератора с одновременным обновлением информации в К+в разрядах за такт работы.Генератор псевдослучайных чисел содержит Т-триггеры 1, переключатели 2, Р-триггеры 3, переключатели 4, коммутаторы 5 и б, блок 7 памяти с входами 8, входы 9 и 10 и выходы 11 и 12 расширения, а также входы 13 и 14 управления расширением,Каждый коммутатор содержит элементы И 15, элементы ИЛИ 16, элементНЕ 17, входы 18-23 и выходы 24-28,На фиг. 4-7 генераторы содержаттакже суммуторы 29 по модулю дна.На фиг. 8 показаны генераторыпсевдослучайных чисел 30 и 31, выходы 32-35 и входы 36-39 расширения, а также входы 40-43 управлениярасширением.Переключатели 2; (4) могут бытьвыполнены, например, в виде сумматоров по модулю два, при этом, еслина первый вход переключателя подается сигнал "0", то осуществляетсяпередача сигнала по второму входуна выход.Коммутаторы 5 и б для подключения входных сигналов на один из выходов, в соответствии с сигналами,поступающими на управляющие входы,могут быть выполнены, например,какпоказано на фиг,2,При отсутствии сигнала "1" навходе 13 (14) управления расширением сигнал по входу 18 переключается на один иэ выходов 24-28 посигналам управления, поступающимна входы 19-23, причем только наодном из входов должен присутствс -вать сигнал "1", а на остальныхвходах - сигналы "0",(б) 0 0 О О 1 О 0 0 0 0 О О 1 1 По матрице С построим схему генератора (фиг. 4), используя Р-триггеры и сумматоры по модулю два.Схему на фиг. 4 можно изобразитьв другом виде (фиг. 5),Схема на фиг. 5 с переупорядоченной нумерацией изображена на фиг,б,Так как 2 -1 и М взаимопростыечисла (и = 7, Е = 4), то генераторпсевдослучайных чисел .(фиг. 4) формирует М-последовательность (3),Циклические свойства генератораполностью определяются характеристическим многочленом. Если он примитивен и неприводим, то генераторформирует М-последовательность (1),причем каждому характеристическому многочлену соответствует свояМ-последовательность и наоборот,каждой М-последовательности соответствует свой характеристический многочлен (4)Схемы, изображенные на фиг. 4 и б,идентичны. Они формируют одну и туже М-последовательность, следовательно, описываются одним и тем же характеристическим многочленом, неприводимым и примитивным.Функционирование схемы, изображенной на фиг. б, опйсывается матрицей С Матрице С соответствует характеристический многочлен Ч(х), который вычисляется через определитель (1) 0 1 1+х 0 0 0 09(х)=С+хЕ=О 0 1 х 0 0 0 250 0 0 1 1+х 0 0 Используем один из методов преобразования определителей, заключающийся в следующем (5) : определитель не меняется, если к элементамодной из его строк (столбца) прибавить соответствующие элементы другой строки (столбца). Преобразуемопределитель (4). Сложим содержимоеб-го и 7-го столбцов (используяоперацию суммирования по модулю два),и результат запишем в 7-й столбец,затем сложим содержимое б-й и 7-й 40 строк, результат запишем в б-уюстроку. Получим следующий опреде- литель 0 11+х 000 0 О О 1 х О О О (Б) 0 0 0 11+хо о О 0 0 0 1 1+к 0 0 0 0 0 0 1 хПрименяя те же операции над 4-ми 5-м стобцами и 4-й и 5-й строками,а затем над 5-м и 6-м столбцами и55 5-й и б-й строками, получимх 0 0. 0 0 0 1 11+хо 0 О 00 О 1 1+х 0 0 О О 0 0 1 1+х 0 0 О 0 0 0 1 Х+х О 0 0 О О О 1 х 0 00 0 0 01 хВидно, что символ "1", расположенный на главной диагонали на пересечении 7-й строки и 7-го столбца, перемещается на место пересечения 4-й строки и 4-го столбца.Определителю (6) соответствует матрица В, описывающая функционирование генератора псевдослучайных чисел 0000001 1100000 0110000 0011000 0 0 0 1. 1 О 0 0000100 00000103 В=(7) Матрице В соответствует схемана фиг. 7. 51015 Схему на фиг. 7, используя Т- иР-триггеры можно преобразовать в схему, аналогичную изображенной нафиг.З, в которой .все Т-триггеры соединены последовательно друг за другом (Р-триггер с сумматором по модулю два на входе можно заменитьТ-триггером).Такие же преобразования можносделать с и-разрядным генераторомпсевдослучайных чисел (п=Е+1) с одновременным обновлением информациив М разрядах.Более того, используя вышеукаэан- З 5. ные операции над определителями,можно символы "1",. присутствующие наГлавной диагонали определителя, перераспределять в любые места на главной диагонали, не .изменяя их количества, следовательно, получать .генераторы .псевдослучайных чисел слюбым (удобным для разработчика)расположением Т- и Р-триггеров, неизменяя их количества (схема на 45фиг, 3 является одним из возможныхвариантов применения предлагаемогоизобретения).Можно предположить следующую последовательность расчета генераторов псевдослучайных чисел с одновременным обновлением информации в нескольких разрядах за такт,1, Выбирается длина и регистрагенератора (п=Ы+Е).2По и выбирается (из таблицы) 55число К одновременно обновляемых,разрядов, соблюдая при этом условиевзаимной простоты 2 -1 и Е иначегенератор не будет формировать М-по-.следовательность. 603. Берется Е Т-триггеров иЙ Р-триггеров (и-К= Я), соединяютсяпоследовательно друг эа другом,причем выход последнего триггерасоединяется с входом первого триг гера, Вообще говоря, расположение триггеров с установочными входами и триггеров со счетными входами выбирается произвольно.Однако для предлагаемого изобретения необходимо все Т-триггеры соединить последовательно друг за другом и все Р-триггеры также соединить последовательно друг за другом, а выход последнего Т-триггера соединить с входом первого Т-триггера (фиг. 3).На управляющие входы 8 подается код, по которому Т-триггеры в количестве Е+1, начиная с номера соединяются последовательно друг за другом и Р-триггеры в количестве Е+1, начиная с номера 3, также соединяются последовательно друг эа другом, причем )-111 и 2-3 +1-1+2соответствуют таблице (-3+1-1+2=п),(Е-н 1 с+2)а Х+1 и 2-1 взаимнопростыечисла. Образуется генератор псевдослучайных чисел с периодом смены состояний Т, необходимым пользователю исоответствующим управляющему .коду,поданному на входы 8Я-+3 с-+2)Т = 2 . -1,Для нормальной работы генераторанеобходимо, чтобы первые 1-1 Т-триггеры и первые 3-1 Р-триггеры предварительно были установлены в нулевоесостояние,Можно соединить два подобных генератора (см. Фиг. 8) между собой ипблучить один генератор псевдослучайных чисел, соединив расширяющие выходы 32 и 33 первого к расширяющимсявходам Зб и 37 второго и расширяющиевыходы втооого 34 и 34 к расширяющим входам первого. При этом на входы 40-43 управления расширением нацоподать сигнал "1". Эквивалентнаясхема, образующаяся при этом, показана на фиг. 9.В этом генераторе количествоТ-триггеров Е+щ и общее количествотриггеров Е+в+1+г должны соответствовать таблице и обязательно выполнение условия взаимной простотыК+ +Е+г)1 с+в и 2 -1 В этом случае генератор Формирует М-последовательностьс периодомЦ+пнЬ )Т = 2Управление периодом смены состояний генератора аналогично вышеуказанному.Таким же образом можно соединить несколько подобных генераторов в один генератор псевдослучайных чисел.Предлагаемое изобретение в отличие от известного позволяет управлять периодом смены состояний генератора псевдослучайных чисел, что расширяет его Функциональные воэможности, 1010622,Рачкулинец кт ПодписноССР Заказ 2490 Тираж 704И Государственного комитета делам изобретений и открыти Москва, Ж, Раушская наб И