Устройство для перебора сочетаний

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для имитации режимов контроля функционирования многопроцессорных систем с распределенной памятью, а также для решения комбинаторных задач. Цель изобретения - расширение функциональных возможностей устройства за счет отбора сочетаний с заданным признаком. Устройство содержит кольцевые регистры сдвига 1, регистр сдвига 4, счетчик 5, регистр признака 7, схему сравнения 6, триггер 10, элементы И 11, ИЛИ 3, ИЛИ-НЕ 8, задержки 9, формирователи 2 импульсов. Введение триггера, элементов ИЛИ, ИЛИ-НЕ, регистра признака и формирователей импульса позволяет выработать сигнал, указывающий на соответствие формируемого сочетания требуемому признаку. 1 ил.

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

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

РЕСПУБЛИК (51) 4 С 06 F 15/20

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

К А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

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

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

ГРИ ГННТ СССР

1 (21) 4331375/24-24 (22) 23.11.87 (46) 15.07.89. Бюл. Ф 26 (72) М.Т.Акуленок и М.В.Буянов (53) 681.3(088.8) (56) Авторское свидетельство СССР

В 1262520, кл. G 06 F 15/20, 1984.

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

М. 826339, кл. G 06 F 7/06, 1979. (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАЦИЙ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для имитации режимов контроля функционирования многопроцессорных систем с распреде„„SU„„1494015 А 1

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

1 сдвига, регистр 4 сдвига, счетчик

5, регистр признака 7, схему 6 сравнения, триггер 10, элементы И ll, ИЛИ 3, ИЛИ-НЕ 8, элемент. 9 задержки, формирователи 2 импульсов. Введение триггера, элементов ИЛИ, ИЛИ-НЕ, регистра признака и. формирователей импульса позволяет выработать сигнал, указывающий на соответствие формируемого сочетания требуемому признаку.

1 ил.

1494015

Изобретение относится к автоматике и вычислительной технике и может быть использовано для имитации режимов контроля многопроцессорной сис5 темы (МПС) с:разделенной памятью, а также при решении комбинаторных задач.

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

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

Устройство содержит и кольцевых регистров 1 сдвига, п формирователей 2 импульса по заднему фронту, и элементов ИЛИ 3, регистр 4 сдвига, счетчик 5, схему 6 сравнения, регистр 7 признака, элемент ИЛИ-НЕ 8, 2О элемент 9 задержки, триггер 10, элемент И 11, вход 12 начальной установки устройства, вход 13 признака отбираемых сочетаний, тактовые входы

14 и 15, выход 16 конца перебора, 25 информационные выходы !7»-17 „ и выход 18 достоверности выходной информации устройства, Устройство работает следующим об1 разом, 30

На вход 12 начальной установки устройства подается импульсный сигнал, который на всех кольцевых регистрах 1 устанавливает двоичный

35 код 10...10. На вход 13 подается и записывается в регистр 7 код признака »»» для отбора сочетаний. На вход 14 первой серии импульсов подается первый импульс, который обну- 40 ляет счетчик 5 и поступает на синхровход кольцевого регистра 1», в результате чего код в кольцевом регистре 1» сдвигается вправо на один разряд и становится равным 010...0. 45

При этом переноса иэ последнего разряда кольцевого регистра 1, не происходит, в результате чего не запуска" ется формирователь 2, импульса по заднему фронту. С выходов кольцевых регистров 1 двоичные коды поступают на информационные выходы 17 устройства и на элементы ИЛИ 3, на выходе которых формируется двоичный код

110...0, который записывается в регистр 4 сдвига по сигналу с выхода элемента 9 задержки. С задержкой, равной максимальному времени переходного процесса по сдвигу кодов в кольцевых регистрах 1, первый импульс со входа 14 устройства через элемент 9 задержки поступает на единичный вход триггера 10 и устанавливает его в единичное состояние. Единичный сигнал с выхода триггера 10 поступает на вход элемента И 11 и разрешает подачу со входа 15 устройства второй серии импульсов на синхровход регистра

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

"1» в регистре 4. Импульсы второй серии проходят через элемент И

ll до тех пор, пока все разряды регистра 4 не станут равными нулю, Пр»» этом единичный сигнал с выхода элемента ИЛИ-HE 8, на вход которого поступает содержимое всех разрядов регистра 4, подается на нулевой вход триггера 10 и переводит его в нулевое состояние, Нулевой сигнал с выхода триггера 10 подается на вход элемента И 11 и блокирует выдачу импульсов второй серии на синхровход регистра 4. Единичный сигнал с выхода элемента ИЛИ-НЕ 8 поступает также на синхровход схемы 6 сравнения и разрешает сравнение кодов, поступающих от счетчика 5 и регистра 7. В случае равенства кодов с выхода схемы

6 сравнения выдается единичный сигнал, поступающий на выход 18 достоверности выходной информации устройства. Единичный сигнал на выходе 18 означает, что на информационных выходах 17 устройства находятся двоичные коды, соответcTsó îùèå заданному в регистре 7 коду.

По приходу следующе"o импульса с входа 14 происходи.- сдвиг кода ь кольцевом регистре 1» на один разряд вправо и цикл повторяется. При сдвиге вправо в i-м кольцевом рег1»стре двоичного кода 0...01 по сбросу единичного сигнала с последнего разряда кольцевого регистра запускается i-й формирователь 2 импульса по заднему фронту, который подает импульсный сигнал на синхровход (i+1)-го (i I 1,ï-1) кольцевого регистра 1 и сдвигает содержимое прследнего,при этом код в i-м кольцевом регистре 1 становится равным

10...0. Полный перебор всех n " "ком14940

Составитель ВвБайков

Редактор А.Ревин Техред Л.Сердюкова Корректор И.Муска

Заказ 4111/45 Тираж 668 Подписное

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

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

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101 бинаций заканчивается выдачей единичного сигнала с выхода и-го формиро" вателя 2 импульса по заднему фронту. который поступает на выход 16 устрой5 ства. При этом на выходе всех кольцевых регистров I устанавливается код

10...0. Таким образом, предлагаемое устройство вьщеляет иэ всех n" комбинаций такие, в которых число одно- 10 именных единичных разрядов равно заданному числу m. При m=n устройство вьщеляет все и1 перестановок иэ n" комбинаций.

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

Устройство для перебора сочетаний, содержащее и кольцевых и-разрядных регистров сдвига (п — число сочетаний), п-разрядный регистр сдвига, 20 счетчикр схему сравнения, элемент И, причем установочные входы всех кольцевых регистров сдвига соединены с установочным входом устройства, о тл и ч а ю щ е е с я тем,что, с це- 25 лью расширения функциональных возможностей устройства за счет отбора ссчетаний с заданным признаком, он содержит регистр признака, триггер, элемент задержки, п элементов ИЛЕ, 30 элемент ИЛИ-НЕ и п формирователей импульса, причем вход элемента задержки является первым тактовым входом устройства и соединен с установочным

ВходОм счетчика и с синхрОниэирующим входом первого кольцевого регистра сдвига, последовательный выход i-ro (i=1,n) кольцевого регистра сдвига

6 подключен по входу i-го формирователя импульса, выход )-го ДТ,п-Т) формирователя импульса подключен к синхронизирующему входу (j+I )-го кольцевого регистра сдвига, i-е разрядные выходы всех кольцевых регистров сдвига подключены к входам i-го элемента ИЛИ, выход i-го элемента ИЛИ подключен к

i-му разрядному входу регистра сдвига, последовательный выход регистра сдвига подключен к счетному входу счетчика, разрядные выходы регистра сдвига соединены с входами элемента

ИЛИ-НЕ, выход элемента ИЛИ-НЕ подключен к синхронизирующему входу схемы сравнения и к нулевому входу триг" гера, выход элемента задержки подключен к управляющему входу записи регистра сдвига и к единичному входу триггера, выход триггера подключен к первому входу элемента И, второй вход которого является вторым тактовым входом утройства, выход элемента

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