Комбинаторное устройство

 

(72) Авторы изобретения

О. В. Викторов, С. И. Орел и А. М. Романкевич

Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (73) Заявитель (54) КОМБИНАТОРНОЕ УСТРОЙСТВО

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

16

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

Такое комбинаторное устройство обеспечивает последовательную генерацию всех сочетаний кодов состояний счетчиков, начиная с единицы, но не осуществляет:генерацию псевдослучайных перестановок двоичных кодов и чисел01 20

Наиболее близким техническим peuleнием к предлагаемому является комбинаторное устройство, содержащее в каждом t-том (i =1...N) разряде регистр, входы которого соединены с выходами элементов И группы того же. разряда, первый вход каждого из которых соединен с соответствующим выходом счетчика, а также блок линий за-, держки, пороговые. элементы, блок ло- ЗО гики, содержащий сумматор, имплика— тор, ждущий мультивибратор и блок регистрацииС23.

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

Цель изобретения — расширение клас-. са решаемых задач за счет реализации псевдослучайных перестановок.

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

ИЛИ и, кроме того, в каждый i-тый разряд введены схема сравнения, вычитающий счетчик, вход блокировки которого соединен с выходом схемы сравнения того же разряда, а счетный вход соединен с выходами схем сравнения

-тых (j=1...i -1) разрядов, выход схемы сравнения каждого разряда соединен со вторыми входами элементов

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

ИЛИ, второй вход которого соединен с входом генератора псевдослучайных чисел и является тактовым входом устройства, выходы генератора псевдослучайных .чисел и блока памяти сое- 1О динены соответственно с первой и второй группами входов блока целочисленного деления, а вход блока памяти соединен с выходом элемента ИЛИ.

На чертеже представлено комбинаторное устройство. устройство содержит генератор 1 псевдослучайных чисел 1,блок 2 памяти, тактовый вход 3 устройство, блок 4 целочисленного деления, группа эле- щ ментов И 5, выход конца операции блока 6 целочисленного программирования, схемы 7-11 сравнения, вычнтающие счетчики 12-16, группы элементоз 17-21 и разрядов, счетчик 22, регистры 23-27 разрядов, элемент ИЛИ 28, Устройство работает слЕдуЮщим образом.

Вычитающий счетчик 12 имеет одно рабочее состояние "О" и состояние блокировки "5". Вычитающий счетчик, ®

13 имеет два рабочих состояния "0" и

"1" и состояние блокировки "5"- Вычитающий счетчик 14 имеет три рабочих состояния "0", "1" н. "2" н состояние блокировки "5 . Эычнтающий 35 счетчик 16 имеет пять рабочих состояний "О", "1", "2", "3" и состояние блокировки "5".

Сигнал, поступающий иа вход блокировки 1-го (1 -1,n) в данком примере n-=4 вычитающего счетчика, устанавливает его в состоянне блокировки "и ". В состоянии блркировки "n вычитающий счетчик не реагирует на сигналы, поступакФМе на вход а на 4 выходах вычитающего счетчика постоянно присутствуют сигналы, соответствующие двоичному коду числа "n

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

С входа 3 поступает тактовый импульс, который осуществляет начальную Установку комбинаторного генератора перестановок: вычитающие счетчихи 12-16 устанавливают в состбяния соответственно "О", "1", "2", "3" и

"4"; счетчик 22 — в состояние "О"; регистры 23-27 — в состояния "О".

На выходы вычитающего счетчика, находящегося в состоянии ."j " (j=0 n) поступают сигналы соответствующие двоичному коду числа j. На информационные выходы регистра, находящего- 65 ся в состоянии "! " 1=0, и -1), поступают сигналы, соответствующие двоичному коду числа "1

Кроме того, тактовый импульс поступает на входы генератора 1 псевдослучайных чисел и блока 2 памяти. В качестве примера рассмотрим такт, в котором с выходов генератора 1 псевдослучайных чисел на входы делимого блока 4 целочисленного деления поступают сигналы (О 100 101)2= (374o С выходов блока 2 на входы делителя бло. ка 4 целочисленного деления поступают сигналы (11 000) = (24)„р. После окончания операции целочисленного деления остаток (О 001 101) = (13) о становится делимым. Единичный сигнал с выхода

6 блока 4 целочисленного деления открывает элемент 5 И группы и разрешает выдачу кода частного (001)2 =(1 на первую группу входов схем 7-11 сравнения . Единичный сигнал с. выхода

6 проходит на вход блока 2. Кроме того„ единичный сигнал выхода б поступает на вход счетчика 22 и устанавливает его в; состояние "1" . С выходов вычитающий счетчиков 12-16 на первую группу входов схем 7-11 сравнения поступают сигналы соответственно

000, 001, 010, 011 и 100 . Нулевые сигналы с выходов схем сравнения кодов 7-11 закрывают элементы 17-21 И групп соответственно. Единичный сигнал с выхода схемы 8 сравнения открывает элементы И группы 18 и разрешает выдачу кода 001 состояния "1" счетчика 22 иа входы установки регистра 24 . Таким образом регистр 24 переходит в состояние "1" и на его информационные выходы поступают сигналы 001 . Единичный сигнал с выхода схемы 8 сравнения поступает на вход блокировки вычитающего счетчика 13 и устанавливает его в состояние блокировки "5". Единичный сигнал с выхода схемы 8 сравнения проходит иа входы вычитающих счетчиков 14, 15 н

16 и устанавливает их в рабочие состояния соответственно "1"„ "2" и "3" .

С выходов блока 2 памяти на входы делителя блока 4 целочисленного деления поступают =игналы (00 110) =(б) б.

После окончания операции целочисленного деления остаток(0 000 001) =(1)( становится делимым. Единичный сигнал с выхода б блока 4 целочисленного деления открывает элементы И группы 5 и разрешает выдачу кода частного (010)g =(2) на первую группу входов схем 7-11 сравнения. Единичный сигнал с выхода конца операции б деления проходит на вход блока памяти . Единичный сигнал с выхода конца операции деления б поступает на вход счетчика 22 и устанавливает его в состояние "2". С выходов вычитающих счетчиков 12-16 на первую группу входов схем 7-11 срав.нения поступают сигналы.

798807 соответственно 000, 101, 001,010 и

011 . Нулевые сигналы с выходов схем

7, 8, 9 и 11 сравнения, закрывают элементы И групп 17, 18, 19 и 21 соответственно. Единичный сигнал с выхода схемы 10 сравнения открывает элементы И группы 20 и р зрешает выдачу кода 010 состояния "2" счетчика 22 на входы установки регистра 26. Таким образом, регистр 26 переходит в состояние "2" и на его информационные выходы поступает сигналы 010.

Единичный сигнал с выхода схемы 10 сравнения поступает на вход блокировки вычитающего счетчика 15 и ус-. танавливает его в состояние блокировки "5". Единичный сигнал с выхода !5 схемы 10 сравнения проходит на вход вычитающего счетчика 16 и устанавливает его в рабочее состояние "2".

С выходов бпока 2 памяти на входы делителя блока 4 целочисленного де- Я ления поступают сигналы (00 010) =(2) . о

После окончания операции целочисленного деления остаток(0 000 001)2 (1) становится делимым. Единичный сигнал. с выхода конца операции деления 6 блока 4 целочисленного деления открЫвает элементы И группы 5 и разрешает выдачу кода частного (000) =(О), на первую группу входов схем 7-11 равечства кодов. Единичный сигнал с нйхода конца операции деления б проходит на вход блока 2 памяти . Кроме того, единичный сигнал с выхода 6 поступает на вход счетчика 22 и устанавливает его в состояние "3". С вы-. ходов вычитающих счетчиков 12-16 . на Э первую группу входов схем сравнения

7-11 поступают сигналы соответственно 000, 101, 001, 101 и 010 . Нулевые сигналы с выходов схем 8-11 сравнения закрывают элементы И групп 18-21 со- 40 ответственно. Единичный сигнал с выхода схемы 7 сравнения открывает элементы И группы 17 н разрешает выдачу кода 011 состояния "3" счетчика 22 на входы установки регистра 23. Таким 4 образом, регистр 23 переходит в состояние "3" н на его информационные выходы поступают, сигналы 011. Единичный сигнал с выхода схемы 7 сравнения поступает на вход блокировки вычитавщего счетчика 12 и устанавливает его в состояние блокировки "5" . единичный сигнал с выхода схемы 7 сравнения проходит на входы нычитающих счетчиков 14 и 16 и устанавливает их в ра" бочке состояния соответственно "О" и N н1и

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

i-тый разряд введены схема сравнения, нычитающнй счетчик, вход блокировки которого соединен с выходом схемы сравнения того же разряда, а счетный вход соединен с выходами схем сраннення i òíõ (j=i,...i=1) разрядов, выход схемы сравнения каждоС выходов блока 2 памяти на входы делителя блока 4 целочисленного деления поступают сигналы (00 001)g ={1)<<.

После окончания операции целочислЕНного деления единичный игнал с выхода конца операции деления 6 блока 4 целочисленного деления открывает схемы И группы 5 и разрешает выдачу кода частного . (001) = 1)„о на первую группу входов схем 7-11 сравнения.

Единичный сигнал с выхода конца операции деления 6 проходит на вход блока 2 памяти. Единичный сигнал с выхода 6 поступает на вход счетчика 22 и устанавливает его н состояние "4".

С выходов нычитающих счетчиков 12-16 на вторую группу входов схем 7-11 сравнения поступают сигналы соответственно 101, 101, 000, 101 и 001. Нулевые сигналы с выходов схем сравнения 7-10 закрывают элементы И групп соответственно 17-20 . Единичный сигнал с выхода схемы 11 сравнения открывает элементы И группы 21 и разрешает выдачу кода 100 состояния "4" счетчика 22 на входы установки ре— гистра 27. Таким образом, регистр 2 переходит в состояние "4" и на его инфсрмационные выходы поступают сигналы 100.

Таким образом, генерируется псевдослучайная перес-..ановка 3 1 О 2 4, где цифры в перестановке (слева направо) являются десятичной записью состояний регистров соответственно

23-27.

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

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

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

798В07

Составитель Е . Пупырев

Редактор Н. Рагулич Техред Т.Маточка Корректор С Ком»

Заказ 10047/65 Тираж 756 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", r. Ужгород, ул . Проектная, 4 ю го разряда соединен со вторыми входамн элементов И группы того же разряда, первая группа входов схемы сравнения каждого разряда соединена с выходами вычитающего счетчика того же разряда, вторая группа входов схе мы сравнения каждого разряда соединена с соответствующими выходами элементов И дополнительной группы, первые входы, которых соединены с группой выходов блока целочисленного деления, а вторые входы соединены с выходом конца операции блока целочисленного деления, входом счетчика и с первым входом элемента ИЛИ, второй вход которого соединен с входом reнератора псевдослучайных чисел и является тактовым входом устройства, выходы генератора псеводослучайных чисел и блока памяти соединены соответственно с первой и второй группам входов блока целочисленного деления, а вход блока памяти соединен с выходом элемента ИЛИ.

Источники инФормации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

Р 374606, кл . 8 06 Г 15/32, 09 .06 .70 .

2 . Авторское свидетельство СССР

9 446057, кл. G 06 F 7/38, 22.11.72 (прототип).