Комбинаторное устройство Советский патент 1981 года по МПК G06F7/00 

(54) КОМБИНАТОРНОЕ УСТРОЙСТВО

Изобретение относится к вычислительной технике и может быть использовано для решения задач оптимизации методами имитационного моделирования систем, а также в качестве генератора проверочных кодов в устройствах, использующих различные вероятностные методы обнаружения отказов в логичес ких схемах. Известно комбинаторное устройство содержащее последовательно включенны счетчики с коэффициентами пересчета, изменяющимися на единицу, схемы И, схемы ИЛИ, линии задержки, триггеры. Такое комбинаторное устройство обеспечивает последовательную генерацию всех сочетаний кодов состояний счетчиков, начиная с Единицы, но не осуществляет , генгерацию псевдослучайных перестановок двоичных кодов п чиселЮ Наиболее близким техническим реше нием к предлагаемому является комбинаторное устройство, содержащее в каждом (-том (i I...-N) разряде регистр, входы которого соединены с выходами элементов И группы того же/ разряда, первый вход каждого из кото рых соединен с соответству1рщим выходом счетчика, а также блок линий задержки, пороговые элементы, блок логики, содержащий сумматор, имплика- тор, ждущий мультивибратор и блок регистрации C3J. Недостатком известного устройства является ограниченный класс решаемых задач - невозможно получить пседдо-. случайные перестановки. Цель изобретения - расширение клас са решаемых задач за счет реализации псевдослучайных перестановок. Предлагаемая цель достигается тем, что в .устройство введень генератор псевдослучайных чисел, блок целоЧис ленного деления, блок памяти и дополнительная группа элементов И, элемент ИЛИ и, кроме того, в каждый -тый разряд введены схема сравнения, вычитающий счетчик, вход блокировки которого соединен с выходом схемы сравнения того же разряда, а счетный вход соединен с выходами схем сравнения j -тых (...i -1) разрядов, выход схемы сравнения каждого разряда соединен со вторыми входами элементов И группы того же разряда, первая Группа входов схемы сравнения каждого разряда соединена с выходами вычитающего счетчика того же разряда, вторая группа входов схемы сравнения каждого разряда соединена с соответствующими выходами элементов И дополнител ной группы, первые входы, которых со динены с группой выходов Рлока целочисленного деления, ,а вторые входы соединены с выходом конца операции блока целочисленного деления, входом счетчика и с первым входом элемента ИЛИ, второй вход которого соединен с входом генератора псевдослучайных чисел и является тактовым входом устройства, выходы генератора псевдо случайных .чисел и блока памяти соединены соответственно с первой и вто рой группами входов блока целочислен ного деления, а вход блока, памяти со динен с выходом элемента ИЛИ. На чертеже представлено комбинаторное устройство. Устройство содержит генератор 1 псевдослучайных чисел 1,блок 2 памят тактовый вход 3 устройство, блок 4 целочисленного деления, группа элементов И 5, выход конца операции бло ка 6 целочисленного програ «4ирования схемы 7-11 сравненияг вычятакшдае сче чики 12-16, группы элементов 17-21 И разрядов, счетчий 22, регистры 23-27 разрядов, элемент ИЛИ 28. Устройство работав следуйядим образом. Вычитакдяий счетчик 12 имеет одно рабочее состояние О и состояние блокировки 5. Вычитакадий счетчик 13 имеет два рабочих состояния О и 1 и состояние влакировки 5. йлчитающий счетчик 14 имеет три рабочих состояния О, 1 и 2 и состояние блокировки 5. Вычитающий счетчик 16 имеет пять рабочих состоя ний О, 1, 2, 3 и состояние блокировки 5. Сигнал, поступакядий на вход блоки ровки i-го (i -1,п) в данном примере вычитаиздего счетчика, устанавливает его в состояние блокировки п . В состоянии блокировки п вычитаквдий счетчик не реагирует на сигналы, поступакяда е на вход, а на выходах вычитакяцего счетчика постоян но присутствуют сигналы соответствующие двоичному коду числа п . Выход из состояния блокировки п производится по тактовому импульсу, который осуществляет начальную установку комбинаторного генератора перестановок . С входа 3 поступает тактовый импульс, который осуществляет начальную установку комбинаторного генератора перестановок: вычитающие счет чики 12-16 устанавливают в состояния , 1, 2, 3 и соответственно в состояние О, ре счетчик 22 гистры 23-27 - в состояния О. На выходы вычитающего счетчика, находящегося в состоянии j (,n поступают сигналы соответствующие двоичному коду числа j. На информационные выходы регистра, находящегося в состоянии I (, п-1), поступают сигналы, соответствующие двоичному коду числа 1 . Кроме того, тактовый импульс поступает на входы генератора 1 псевдослучайных чисел и блока 2 памяти. В качестве примера рассмотрим такт, в котором с выходов генератора 1 псевдослучайных чисел на входы делимого блока 4 целочисленного деления поступают сигналы (О 100 101)2 (37).С выходов блока 2 на входы делителя блока 4 целочисленного деления поступают сигналы (11 000)2 (24)Q. После окончания операции целочисленного деления, остаток (О 001 101) (13)о становится делимым. Единичный сигнал с выхода 6 блока 4 целочисленного деления открывает элемент 5 И группы и разрешает выдачу кода частного (001)2 (1)р на первую группу входов схем 7-11 сравнения. Единичный сигнал, с. выхода 6 проходит на вход блока 2. Кроме того, единичный сигнал выхода 6 поступает на вход счетчика 22 и устанавливает его в.состояние 1. С выходов вычитакядий счетчиков 12-16 на первую группу входов схем сравнения поступают сигналы соответственно 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)2 (6). После окончания операции целочисленного деления остаток (О 000 001)2(1)о становится делимым. Единичный сигнал с выхода 6 блока 4 целочисленного деления открывает элементы И группы 5 и разрешает выдачу кода частного (010)2: (2)(j на первую группу входов схем 7-11 сравнения. Единичный сигнал с выхода конца операции 6 деления проходит на вход блока памяти. Единичный сигнал с выхода кОнца операции Деления 6 поступает на вход счетчика 22 и устанавливает его в состояС выходов вычитающих счетчиков 12-16 на первую группу входов схем 7-11 сравнения поступают сигналы соответственно 000, 101, 001,010 и Oil. Нулевые сигналы с выходов схем 7, 8, 9 и 11 сравнения, закрывают эле менты И групп 17, 18, 19 и 21 соответственно. Единичный сигнал с выхода схемы 10 сравнения открывает элементы И группы .20 и разрешает выдачу кода 010 состояния 2 счетчика 22 на входы установки регистра 26. Таким образом, регистр 26 переходит в состояние 2 и на его информационные выходы поступает сигналы 010. Единичный сигнал с выхода схемы 10 сравнения поступает tia вход блокировки вычитающего счетчика 15 и ус-, танавливает его в состояние блокировки 5. Единичный сигнал с выхода схемы 10 сравнения проходит на вход вычитающего счетчика 16 и устанавливает его в рабочее состояние 2. С выходов блока 2 памяти на входы делителя блока 4 целочисленного деления поступают сигналы (00 010)3 (2 После окончания операции целочисленного деления остаток (О 000 001)2 (1) становится дели№ам. Единичный сигнал с выхода конца операции деления 6 блока 4 целочисленного деления откры вает элементы И группы 5 и разрешает вьщачу кода частного {000) (0)0 на первую группу входов схем 7-11 равенства кодов. Единичный сигнал с вйхода конца операции деления 6 проходит на вход блока 2 памяти. Кроме того, единичный сигнал с выхода б поступает на вход счетчика 22 и устанавливает его в состояние 3 . С вы;ходов вычитающих счетчийов 12-16 .на первую группу входов схем сравнения 7-11 поступают сигналы соответственно 000, 101, 001, 101 и 010. Нулевые сигналы с выходов схем 8-11 сравнения закрывают элементы И групп 18-21 соответственно. Единичный сигнал с выхода схемы 7 сравнения открывает элементы И группы 17 и разрешает выдачу кода 011 состояния 3 счетчика 22 на входы установки регистра 23. Таким образом, регистр 23 переходит в состояние 3 и на его информационные выходы поступают сигналы 011. Единичный сигнал с выхода схема 7 сравнения поступает на вход блокировки вычитающего счетчика 12 и устанавливает его в состояние блокировки 5. Единичный сигнал с выхода схемы 7 сравнения проходит на входы вычитающих счетчиков 14 и 16 и устанавливает их в рабочие состояния соответственно О и 1. С выходов блока 2 памяти на входы делителя блока 4 целочисленного деления поступают сигналы (00 001)2 (1)Q После окончания операции целочисленного деления единичный « игнал с выхода конца операции деления 6 блока 4 целочисленного деления открывает схемы И группы 5 и разрешает выдачу кода частного . (001),; (1)0 на первую группу входов схем 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. Таким образом, регистр 27 переходит в состояние 4 и на его информационные выходы поступают сигналы 100 , Таким образом, генерируется псевдослучайная перестановка 31024, где цифры Б перестановке (слева направо) являются десятичной записью состояний регистров соответственно 23-27. Известное изобретение обеспечива-, ет выбор всех Р, перестановок из результата решения производящей функции. Комбинаторный генератор перестановок расширяет класс решаемых задач, а именно генерирует все Р, псевдослучайные перестановки двоичных кодов п чисел. Это дает возможность использовать предлагаемое изобретение для решения задач оптимизации методами имитационного моделирования систем, а также в качестве генератора проверочных кодов в устройствах, использующих различные вероятностные методы обнаружения отказов в логических схемах. Формула изобретения Комбинаторное устройство, содержащее в каждом i-том (, ..N) разряде регистр, входы которого соединены с выходами элементов И группы того же разряда, первый вход каждого из которых соединен с соответСТБукхцим выходом счетчика., отличающееся тем, что, с целью расширения класса решаемых задач за счет реализации псевдослучайных перестановок, в него введен генератор псевдослучайных чисел, блок целочисленного деления, блок памяти, дополнительная группа элементов И, элемент ИЛИ и, кроме того, в каждый i-тый разряд введены схема сравнения, вычитающий счетчик, вход блокировки которого соединен с выходом схемы сравнения того же разряда, а счетннй вход соединен с выходами схем сравнения i-тых (,...) разрядов, выход схемы сравнения каждого раэрдда соединен со вторыми входами элементов И группы того же разряда, первая группа входов схемы сравнения каждого разряда соединена с выходами вычитающего счетчика того же разряда, вторая группа входов схе мы сравнения каждого разряда соединена с соответствукяцими выходами элементов И дополнительной группы, первые входы, котсфых соединены с группой выходов блока целочисленного деления, а вторые входы соединены с выходом конца операции блока целочисленного деления, входом сч.етчика и с первым входом элемента ИЛИ, второй вход которого соединен с входе генератора псевдослучайных чисел и является тактовым входом устройства, выходы генератора псеводослучайных чисел и блока памяти соединены соответственно с первой и второй группами входов блока целочисленного деления, а вход блока памяти соединен с выходом элемента ИЛИ,

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

№ 374606, кл. а 06 Г 15/32, 09.06.70

2.Авторское свидетельство СССР № 446057, кл. G 06 Р 7/38, 22.11.72 fпрототип).