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

 

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

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

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

РЕСПУБЛИК

{Я)5 6 06 F 7/58

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4777322/24 (22) 03,01.90 (46) 15.08,92, Бюл. ¹ 30 (71) Таганрогский радиотехнический институт им, B. Д. Калмыкова (72) В, M. Глушань и Г. Н, Иванков (56) Авторское свидетельство СССР

¹ 1319027, кл, G 06 F 7/58, 1986; (54) ГЕНЕРАТОР СЛУЧАЙНЫХ СОЧЕТАНИЙ

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

Цель изобретения — повышение быстродействия устройства.

На чертеже приведена структурная схема генератора, Устройство содержит генератор 1 тактовых импульсов, генератор 2 случайных кодов, группы 3 элементов И, первый регистр

4 памяти, группу 5 дешифраторов, матрицу

6 элементов И, группу 7 элементов ИЛИ, второй регистр 8 памяти, блок 9 для перебора сочетаний, формирователь 10 импульсов, элемент ИЛИ 11, вход 12 установки начального состояния.

Принцип работы генератора состоит в следующем. Генератор 2 формирует случайные двоичные коды в диапазоне (0„,2 -1),,,5U, 1755277 Al (57) Изобретение относится к вычислительной технике. Цель изобретения — повышение быстродействия, Генератор содержит генератор тактовых импульсов. генератор случайных кодов, группу элементов И, регистр памяти, группу дешифраторов, матрицу элементов И, группу элементов ИЛИ, регистр памяти, блок перебора сочетаний, формирователь импульсов, элемент ИЛИ вход установки начального состояния. 1 ил., 2 табл, Блок 9 задает. верхний индекс в Сгп, т.е, индекс I. В то же время нижний индекс 2" уже определен числом и, ограничивающим число разрядов генератора 2. Поэтому в блоке 9 нужно предусмотреть автоматическое ограничение числа его разрядов на уровне

2". Это обеспечивается регистром 8 и формирователем 10, Для этого в регистр 8 нуж- Л но первоначально записать (Я соответствующую комбинацию нулей и единиц.

Дешифраторы группы 5 обеспечивают возбуждение по одному выходу в каждом дешифраторе и номера этих выходов все будут разные, если в сочетании участвует максимальное число разрядов 2 . Если регистром 4 подключаются не все п1 разрядов генератора 2, а на f меньше (f- 1, m-1), то возбуждаться будут одинаковые выходы у 2 подгрупп дешифраторов, но у каждой подгруппы дешифраторов все возбужденные выходы будут разные. В этом как раз и состоит главный принцип работы генератора.

1755277

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

Сущность такого подключения состоит в следующем.

Все выходы генератора 2 и соответственно элементов И группы 3 нумеруются в порядке возрастания. При этом прямые выходы получают нечетные номера, а инверсные —.четные. Затем выписываются

m-разные комбйнации прямых и инверсных выходов генератрра 2 в виде возрастающей последовательности двоичных чисел. При этом вес разрядов увеличивается справа налево и в разряд записывается "1", если он соответствует одному из выходов генератора 2, и "0" — если прямому выходу. Другими словами, это будет последовательность кодов, снимаемых с соответствующих комбинаций из m прямых и инверсных выходов генератора 2 при условии, что все его разряды находятся в нулевом состоянии. После этого полученную последовательность нужно переставить так, чтобы получилась возр, -тающая последовательность двоичных чисел, но веса разрядов возрастали бы слева направо. После выполнения такой операции получим отраженные двоичные коды (т.е. зеркально симметричные относительно исходных). Переведя эти коды в соответствующие номера прямых и инверсных выходов генератора 2, получим комбин;-.öèâ номеров тех выходов элементов И группы 3, которые должны быть соединены с информационными входами соответствующих дешифраторов, При этом номер отраженного кода в последовательности определяет номер дешифратора, .

Описанную процедуру определения порядка выходов злемечтов И группы 3 к входам дешифраторов группы 5 проиллюстрируем для случая m = 3, соответствующего приведенному на чертеже. Результаты выполнения этой процедуры представлены в виде таблицы 1, в которой в первом столбце расположены коды двоичных чисел (исходные), у которых вес разрядов увеличивается справа налево; во втором столбце расположены отраженные двоичные коды, в третьем столбце — номера элементов И группы 3, в четвертом столбце— номера дешифраторов.

Анализируя столбец 3 приведенной таблицы, можно заметить, что при подключении к входам дешифратора 5 только двух разрядов генератора 2 в первой и во второй четверках дешифраторов будут возбуждатьСя Одинаковые выходы, так как на выходах

5 и 6 элементов И группы 3 будут нулевые

40 потенциалы. Это означает, что в генерации случайных сочетаний будут принимать участие дешифраторы 1, 2, 3, 4.

Генератор работает следующим образом.

Пусть необходимо формировать случайные сочетания С я. Тогда в регистр 4 нужно

Л записать три единицы, т,е, код 111, в регистр 8 нужно записать комбинацию

11 "00000 и переписать ее в блок 9 перебора сочетания. Предположим, что генератор 2 сформировал случайный код 110. Тогда соответствие между номерами дешифраторов и номерами их выходов будет задаваться табл.:цей 2 (первая и вгорая строки).

Допустим, что в блоке 9 установилось сочетание 00010011, Тогда произойдет совпадение единиц на элементах Ибц, Ибз2, Иб5т. Поэтому единицы появятся на выходах элементов ИЛИ7з, 74, 7, т.е. сформируется сочетание 00111000. Если генератор 2 сформирует случайный код 100, а блок 9 останется в прежнем состоянии, то будут возбуждены выходы разрядов дешифраторов, соответствующие третьей строке приведенной таблицы, а на выходах элементов

ИЛИ группы 6 появится сочетание 11001000 и T,ä.

Формула изобретения

Генератор случайных сочетаний, содержащий генератор тактовых импульсов, генератор случайных кодов, элемент iJlN, группу элементов И и первый регистр памяти, .отличающийся тем, что, с целью повышения быстродействия, 8 него дополнительно ввсдены матрица элементов И, группа элементов ИЛИ, блок для перебора сочетаний, второй регистр памяти, формирователь импульсов и группа дешифраторов, причем информационные входы каждого дешифратора группы соединены с соответствующими выходами элементов И группы, выходы j-го дешифратора (j = 1, 2,..., 2, m — число разрядов генератора случайных кодов) соединены с первыми входами соответствующих элементов И j-й строки матрицы, вторые входы элементов И к-го столбца (k = 1, 2,..., 2 ) матрицы соединены с к-м выходом блока для перебора сочетаний, выходы элементов И )-A строки матрицы соединены с соответствующими входами

j-ro элемента ИЛИ группы, выход второго регистра памяти соединен с входом задания числа импульсов блока для перебора сочетаний, выход окончания цикла формирования сочетаний которого через формирователь импульсов соединен с первым входом элемента ИЛИ, выход которого соединен с входом установки в начальное состояние блока для перебора сочетаний, 1755277

Таблица 1

Таблица 2 вход запуска которого соединен с выходом генератора тактовых импульсов и входом опроса генератора случайных кодов, прямой и инверсный выходы 1-го () = 1, 2,..., m) разряда которого соединены соответственно с первыми входами (2i-1)-го и 2 i-ro злементов И группы, вторые входы которых соединены с i-м выходом первого оегистра памяти, вход разрешения считывания которого соединен с вторым входом элемента

5 ИЛИ и является входом установки в начальное состояние генератора.