Устройство для перебора сочетаний Советский патент 1989 года по МПК G06F7/06 

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

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

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

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

Устройство работает следующим образом,

На вход 12 начальной установки устройства подается импульсный сигнал, который на всех кольцевых регистрах 1 устанавливает двоичный код 10,,,10, На вход 13 подается и записывается в регистр 7 код признака m для отбора сочетаний. На вход 14 первой серии импульсов подается первый импульс, который обну- ляет счетчик 5 и поступает на син- хровход кольцевого регистра 1, в результате чего код в кольцевом регистре 1, сдвигается вправо на один разряд и становится равным 010о,оОо При этом переноса из последнего разряда кольцевого-регистра 1 не происходит, в результате чего не запуск ется формирователь 2 импульса по заднему фронту, С выходов кольцевых регистров 1 двоичные коды поступают на информационные выходы 17 устройства и на элементы ИЛИ 3, на выходе которых формируется двоичный код ПО,, „О, который записывается в ре- гистр 4 сдвига по сигналу с выхода элемента 9 задержки„ С задержкой, равной максимальному времени перехоного процесса по сдвигу кодов в колцевых регистрах 1, первьш импульс со входа 14 yctpoйcтвa через элемент 9 задержки поступает на единичный вход триггера 10 и устанавливает его в единичное состояние. Единичный сигна с выхода триггера 10 поступает на вход элемента И 1I и разрешает подачу со входа 15 устройства второй серии импульсов на синхровход регистра 4 сдвига. По приходу очередного импульсного сигнала содержимое регистра 4 сдвига сдвигается на один разря вправо и с последнего разряда поступает на счетный вход счетчика 5, который подсчитывает количество единиц И в регистре 4, Импульсы второй серии проходят через элемент И 11 до тех пор, пока все разряды регистра 4 не станут равными нулю. При этом единичный сигнал с выхода элемента ИЛИ-НЕ 8, на вход которого поступает содержимое всех разрядов регистра 4, подается на нулевой вход триггера 10 и переводит его в нулевое состояние. Нулевой сигнал с выхода триггера 10 подается на вход элемента И 11 и блокирует вьщачу импульсов второй серии на синхровход регистра 4 Единичный сиг нал с выход элемента ИЛИ-НЕ 8 поступает также на синхровход схемы 6 сравнения и разрешает сравнение кодов, поступающих от счетчика 5 и регистра 7, В случае равенства кодов с выхода схемы 6 сравнения выдается единичный сигнал, поступающий на выход 18 достоверности выходной информации устройства. Единичный сигнал на выходе 18 означает, что на информационных выходах 17 устройства находятся двоичные коды, соответствующие заданному в регистре 7 коду.

По приходу следующего импульса с входа 14 происходи: сдвиг кода Б кольцевом регистре 1 на один разряд вправо и цикл повторяется. При сдвиге вправо в i-м кольцевом регистре двоичного кода О.,,01 по сбросу единичного сигнала с последнего разряда кольцевого регистра запускается i-й формирователь 2 импульса по заднему фронту, который подает импульсный сигнал на синхровход (i-bl)-ro (,l,n-l) кольцевого ре гистра 1 и сдвигает содержимое прс- леднего при этом код в i-м кольцевом регистре 1 становится равным 10...О. Полный перебор всех п комбинаций заканчивается выдачей единичного сигнала с выхода п-го формирователя 2 импульса по заднему фронту, который поступает на выход 16 устройства. При этом на выходе всех кольцевых регистров I устанавливается код 10...0. Таким образом, предлагаемое устройство выделяет из всех п комбинаций такие, в которых число одноименных единичных разрядов равно заданному числу т. При устройство выделяет все п1 перестановок из п комбинаций.

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

0

5

5

0

5

подключен по входу i-ro формирователя импульса, выход j-го j«I ,п-1 ) формирователя импульса подключен к синхронизирующему входу (j + l )-го кольцевого регистра сдвига, i-e разрядные выходы всех кольцевых регистров сдвига подключены к входам i-ro элемента ИЛИ, выход i-ro элемента ИЛИ подключен к i-му разрядному входу регистра сдвига, последовательный выход регистра сдвига подключен к счетному входу счетчика, разрядные выходы регистра сдвига соединены с входами элемента ИЛИ-НЕ, выход элемента ИЛИ-НЕ подключен к синхронизирующему входу схемы сравнения и к нулевому входу триггера, выход элемента задержки подключен к управляющему входу записи регистра сдвига и к единичному входу триггера, выход триггера подключен к первому входу элемента И, второй вход которого является вторым тактовым входом утройства, выход элемента И подключен к синхронизирующему входу регистра сдвига, вход регистра признака является входом признака устройства, выход регистра признака и выход счетчика подключены соответственно к первому и второму информационным входам схемы сравнения, выход схемы сравнения является выходом достоверности результата устройства, разрядные выходы всех кольцевых регистров сдвига являются информационными выходами устройства, выход п-го формирователя импульса является выходом окончания работы устройства.

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