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

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

Известен генератор псевдослучайных чисел (генератор М-последовательности), содержащий сдвиговый регистр с сумматором по модулю два в цепи обратной связи. В этом генераторе очередное t-разрядное двоичное число образуется на выходах разрядов регистра через каждые S такто (S , t) tl.

Недостатками данного i-енератора явлйются низкое быстродействие и невозможность последовательности разных периодов.

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

Однако указанный генератор обладает значительной сложностьюо

Наиболее близким к предлагаемому является генератор псевдослучайных чисел (генератор М-последовательности), содержащий триггеры со счетными входами (Т-триггеры) и триггеры с установочными входами (D-триггеры) СЗ.

Недостатком известного генератора является отсутствие возможности формирования М-последовательностей различных периодов с

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

Поставленная цель достигается тем, что генератор псевдослучайных чисел, включающий в себя k Т-триггеров и n-k D-триггеров, дополнительно содержит первую группу из k-1 переключателей, вторую группу из n-k-1 переключателей, два коммутатора и блок памяти, группа входов которого является группой входов генератора, первая группа выходов блока памяти подключена к группе входов первого коммутатора соответственно, а вторая группа выходов блока памяти подключена к группе входов второго -коммутатора, соответственно, первЕлй выход которого подключен к входу первого D-триггера, а n-k-1 остальных выходов второго коммутатора подключены соответственно к первым входам n-k-1 переключателей второй группы, второй вход каждого из которых подключен к выходу одноименного В-триггерй, а выход каждого переключателя второй группы подключен к входу последующего D-триггера, первый выход первого коммутатора подключен к входу первого Т-триггера, а k-1 остальных выходов первого коммутатора подключены соответственно к первым входам k-1 переключателей первой группы,второй вход каждого из которых подключен к выходу Одноименного Т-триггера, а выход каждого переключателя первой группы подключен к входу последующего Т-триггера, выход n-k)-г D-триггера подключен к входу первого коммутатора, а выход k-го Т-триггера - к входу .второго коммутатора.

На фиго показана схема генератора псевдослучайных чисел; на фиг о пример технического решения коммутаторов 5 и 6; на фиг. 3 - схема генератора с одновременным обновлением k разрядов за такт работы; на фиг„4 примеры выполнения генератора псевдслучайных чисел; на фиг. 8 - примеры соединения генераторов; на фиг. 9 - схема генератора с одновременным обновлением информации в k+m разрядах за такт работы

Генератор псевдослучайных чисел содержит Т-триггеры 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 Л могут быть выполнены, например, в виде сумматоров по модулю два, при этом, если на первый вход переключателя подается сигнал О, то осуществляется передача сигнала по второму входу на выход о

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

При отсутствии сигнала 1 на входе 13 (14) управления расширением сигнал по входу 18 переключается на один из выходов 24-28 по сигналам управления, поступающим на входы 19-23, причем только на одном из входов должен присутствовать сигнал 1, а на остальных входах - сигналы О. При наличии сигнала 1 на входе 13(14) управления расширением коммутатор 5(6) переключает сигнал с входа 9(10) расширения на один из выходов 24(28),а сигнал с входа 18 - на выход 11(12) расширения. Блок 7 памяти служит для хра нения информации, управляющей коммутаторами 5 и б„ Сигналы, появляю1диеся на первой группе выходов блока 7, управляют первым коммутатором 5, а сигналы второй группы выходов вторым коммутатором б. Блок 7 памяти совместно с коммутаторами 5 и б подключает выход 1-т D-триггера 3 к входу одно.го из Т-триггеров (к входу 1-го Т-триггера 1 непосредственно, а к входам 2-го,о о о,k-ro Т-триггера 1 через переключатель 2), а выход k-ro Т-триггера 1 , - к входу одного из D-триггеров 3j (к входу 1-го D-три гера 3 непосредственно, а к входам 2-го,.. о Д-го ( )-триггера 3через переключатель 4)о Генератор работает следующим образом. На входы 8 управления подаются адресные сигналы, спрашивающие блок 7 памяти, на выходах которого появ ляются сигналы,управляющие коммутаторами 5 и б, например, которые так же подключают выход 1-го D-триггера Зе к входу первого D-триггера 3. На первые входы всех переключате- . лей (4.-) подаются сигналы О, что заставляет их работать в режиме повторителей сигналов по вторым входам . . Эквивалентная схема генератора (при данных управляющих сигналах) представлена на фиг-о 3 Данная схема реализует генератор псевдослучайных чисел с одновременным обновлениемk разрядов за такт работы. Предварительно в генератор заносится начальное состояние (цепи синхронизации и установки начального состояния на фиг, 1 и 3-9 не показаны) о С приходом тактового импульса генератор псевдослучайных чисел переходит в следующее состояние о Период смены состояний равен Т 2 - 1, где п k+1, предлагаемый генератор формирует последовательность максимальной длины (М-последовательность)о Доказательство этого утверждения разберем на примере работы 7-разряд;ного () генератора псевдослучайных чисел. Из таблицы выберем Матрица А, описывающая работу генератора псевдослучайных чисел (1), выглядит следукяцим образом 001 О 00 000 О О О (1) 000 100 010 Построим 7-разрядный .генератор с одновременным обновлением 4 разрядов за такт работы (3)

Продолжение таблицы

ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ, содержащий k Т-триггеров и n-k D-триггеров, отличающийся тем, Ч.ТО, с цешью расширения его функциональных возможност й за счет управления периодом М-последовательности, он содержит первую группу из k-1 переключателей, вторую группу из n-k-1 переключателей,два коммутатора и блок памяти, группа входов которого является группой входов генератора, первая группа выходов блока памяти подключена к группе .входов первого коммутатора соответ- . отвенно, а вторая группа выходов, блока памяти подключена к группе входов второго коммутатора соответственно, первый выход которого подключен к входу первого D-триггера, а n-k-1 остальных выходов второго коммутатора подключены соответственно к первым входам n-k-1 переключателей второй группы, второй вход каждого из которых подключен к выходу. Одноименного D-триггера, а выход каждого переключателя второй группы подключен к входу последующего D-триггера, первый выход первого коммутатора подключен к входу первого Т-триггера, а k-1 остальных выходов первого коммутатора под(Л ключены соответственнок первым входам k-1 переключателей первой с группы, второй вход каждого из когторых подключен к выходу одноимен- ного Т-триггера, а выход каждого переключателя первой группы подключен к входу последующего Т-триггера, выход (n-k)-го D-триггера подключен к входу первого коммутатора а выход k-ro Т-триггера - к входу второго коммутатора л ts5

1 О О

о 1 о о о 1 о

С А

о 1 о о По матрице С ратора (фиго 4) ры и сумматоры по модулю двво Схему на фиг. 4 можно изобразить в другом-виде (фиг. 5)с Схема на фиг. 5 с переупорядочен ной нумерацией изображена на фиг.б Так как и k взаимопростые числа ,-(п 7, k 4), то генератор псевдослучайных чисел .(Фиг 4) формирует М-последовательность (3). Циклические свойства генератора полностью определяются характеристическим многочленоМо Если он примитивен и неприводим, то генератор формирует М-последовательность (1), причем каждому характеристическому многочлену соответствует своя М-последовательность и наоборот,каж дой М-последовательности соответствует свой характеристический многочлен (4). Схемы, изображенные на фиг. 4 и идентичны. Они формируют одну и ту же М-последовательность, следовател но, описываются одним и тем же характеристическим многочленом, непри водимым и примитивнымо Функционирование схемы, изображенной йа фиг. 6, описывается матри цай с Используем один из методов преобразования определителей, заключающийся в следующем (5) : определитель не меняется, если к элементам одной из его строк (столбца) прибавить соответствующие элементы другой строки (столбца)о Преобразуем определитель (4)„ Сложим содержимое б-го и 7-го столбцов (используя операцию суммирования по модулю два), и результат запишем в 7-й столбец, затем сложим содержимое б-и и 7-й строк, результат запишем в 6-ую строку. Получим следующий определительПрименяя те же операции над 4-м 5-м стобцами и 4-й и 5-й строками, а затем над 5-м и б-м столбцами и 5-й и б-й строками, получим X О ТУ. о О 01 1 1+х О О О О О о 11+х О О 00 001 1+х О 00 00о 1 1+х О о 00о о 1 X о 00о о о 1 X

Видно, что символ 1, расположенный на главной диагонали на персечении 7-й строки и 7-го столбца, перемещается на место пересечения 4-й строки и 4-го столбца.

Определителю (6) соответствует матрица В, описывающая функционирование генератора псевдослучайных чисел

бООО ОО1

11ОО ООО

О11о .0ОО

В ОО11 ООО (7)

ООО1 1-0О

О О О О 1 О О О О О О О 1 О Матрице В соответствует схема на фиг. 7.

Схему на фиг. 7, используя Т- и D-триггеры можно преобразовать в схму, аналогичную изображенной на фиг.З, в которой .все Т-триггеры соединены последовательно друг за другом (D-триггер с сумматором по модулю два на входе можно заменить Т-триггером).

Такие же преобразования можно сделать с п-разрядным генератором псевдослучайных чисел () с одновременным обновлением информации в k разрядах.

Более того, используя вышеуказанные операции над определителями, можно символы 1,. присутствующие н Главной диагонали определителя, перераспределять в любые места на гла ной диагонали, не изменяя их количества, следовательно, получать генераторы :псевдослучайных чи.сел с любым (удобным для разработчика) расположением Т- и D-триггеров, не изменяя их- количества (схема на фиг. 3 является одним из возможных вариантов применения предлагаемого изобретения)

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

.разрядов, соблюдая при этом условие взаимной простоты 2-1 и kJИнaчe генератор не будет формировать М-по следовательность.

П-триггеров (), соединяются последовательно друг за другом, причем выход последнего триггера соединяется d входом первого триггера. Вообще говоря, расположение триггеров с установочными входами и триггеров со счетными входами выбирается произвольно.

Однако для предлагаемого изобретения необходимо все Т-триггеры соединить последовательно друг за другом и все D-триггера также соединить последовательно друг за другом, а выход последнего Т-триггера соединить с входом первого Т-триггера (фиг. 3).

На управляющие входы 8 подается код, по которому Т-триггеры в количестве k-i-t-1 , начиная с номера i,

5 соединяются последовательно друг за другом и D-триггеры в количестве I-JH-1, начиная с номера j, также соединяются последовательно друг за другом, причем k-ifl и E-j+k-i+2

соответствуют таблице (-j-bk-i-i-2 n),

а Tc-i + 1 и2 1 взаимнопростые числи.Образуется генератор псевдослучайных чисел с периодом смены состояний Т, необходимым пользователю и 5 соответствующим управляющему коду, поданному на входы 8

)

Т 2 . -1. Для нормальной работы генератора 0 необходимо, чтобы первые i-1 Т-триг- , геры и первые j-1 D-триггеры предварительно были установлены в нулевое состояние.

Можно соединить два подобных гес нератора (см. фиг. 8) между собой и получить один генератор псевдослучай-, ных чисел, соединив раолиряющие выходы 32 и 33 первого к расширяющимся входам 36 и 37 второго и расширяющиевыходы ВТОРОГО 34 и 34 к расширяи кадим входам первогоо При этом на входы 40-43 управления расширением надо подать сигнал 1. Эквивалентная схема, образующаяся при этом, показана на фиг. 9. 5 В этом генераторе количество Т-триггеров k+ra и общее количество триггеров k+m+l+r должны соответствовать таблице и обязательно выполнение условия взаимной простоты

0 „(ft+mie+r) . „ .

k+m и2 Л;В этом случае генератор формирует М-поспедов.ательность с периодом

(

Т 2 - 1,

- Управление периодом смены состояний генератора аналогично вышеуказанному.

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

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

||...|

х

SfSf

f3fn)

h

audi

Г8

19 го

2T

22

23

ffff)

) fS T.5 ff

i

2

-g

25

fS

2S

-

№

27

fS

2g

i

In