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

1

(21)4753362/24 (22)24.10.89 (46)23.10.91. Бюл. №39

(71)Ленинградский научно-исследовательский радиотехнический институт

(72)В.А.Федорович и М.Н.Григорьев (53)681.3(088.8)

(56)Авторское свидетельство СССР № 1056205,кл. G 06 F 15/31. 1982.

Авторское свидетельство СССР № 514295. кл. G 06 F 15/20. 1975. (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ

(57)Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных вычислительных устройств, предназначенных для решения топологических и комбинаторных задач, задач автоматизированногоконструированиярадиоэлектронной и вычислительной аппаратуры, а также для генерации кодовых последовательностей в тестирующей и контрольной аппаратуре. Цель изобретения - расширение функциональных возможностей за счет изменения параметров сочетания. Устройство содержит блок 1 управления, регистр 2, элемент задержки 3, элемент И 4. блоки 5, 6 элементов И, счетчики 8, 7, элемент ИЛИ-НЕ 9, ждущий мультивибратор 10, элементы НЕ 11. 12. В составе блока 1 управления имеется генератор 13 одиночного импульса, генератор 14 тактов, делитель частоты 15, триггер 16, элементы И 17, 18, ИЛИ 19, И-НЕ 29, группы 20, 21 входных ключей, элементы задержки 22-25, счетчик 26, ждущие мультивибраторы 27, 28, узлы 30-33 элементов И, группы 34 элементов НЕ, регистры . Ввод двух счетчиков в состав блоков устройства, а также конструктивное решение блока управления позволяет программировать параметры сочетания - число комбинируемых элементов и число элементов в сочетании. 2 ил.

(Л

С

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг. 2 - функциональная схема блока управления.

Устройство содержит блок 1 управления, регистр 2, элемент задержки 3, элемент И 4, блоки 5, 6 элементов И. счетчики 7, 8, элемент ИЛИ-НЕ 9, ждущий мультивибратор 10, элементы НЕ 11, 12. Блок 1 управления содержит генератор 13 одиночного импульса, генератор 14 тактов, делитель частоты 15, триггеры 16, элементы И 17, 18, ИЛИ 19, группы 20, 21 входных ключей, элементы задержки 22-25, счетчик 26, ждущие мультивибраторы 27, 28, элементы И-НЕ 29, узлы 30-33 элементов И, группу 34 элементов НЕ, регистр 35, регистр сдвига 36, регистры 37, 38, выходы 39-42, вход 43, выходы 44, 45, вход 46. Устройство последовательно формирует все сочетания из М элементов по

о

00

о

±

СП 00

N (N M . -. M0. где MO - наибольшее значение М, определяемое разрядностью регистров). При переборе сочетаний значений М значения N хранятся в регистрах 37,38, куда они предварительно заносятся при помощи групп ключей 21, 20 (например, наборные поля). Коды в регистрах 37, 38 содержат соответственно М и N единиц в младших разрядах. Сочетания формируются счетчиком 7 и представляются наборами единичных разрядов в двоичном коде. Считывание сочетаний через блок 6 элементов И в выходной регистр 2 осуществляется только при наличии единиц в разрядах счетчика 7. Состояние счетчика 7 анализируется блоком 1 управления. Текущее сочетание поступает в блок 1 по шине 43. Обнаружение N единиц в коде сочетания сопровождается выдачей управляющего сигнала с выхода 41 блока 1 на управляющий вход блока б элементов И. Счетчик 8, работающий в режиме вычитания, задает общее число 2м перебираемых сочетаний. Его начальная установка (М единиц в младших разрядах) осуществляется путем считывания содержимого регистра 37 в блоке 1 управления через блок 5 элементов И. Обнуление счетчика 8 свидетельствует об окончании перебора сочетаний и сопровождается появлением сигнала на выходе элемента ИЛИ-НЕ 9. Срабатывание элемента ИЛИ-НЕ 9 запрещается при обработке первого сочетания в формируемой последовательности управляющий сигнал с выхода 44 блока 1. Темп перебора сочетаний задается частотой тактовых импульсов с выхода 45 блока 1. Тактовые импульсы поступают через элемент задержки 3 (обеспечивает временное согласование работа блоков) и элемент И 4 на счетные входы счетчиков 7, 8 и вход 46 блока 1. Подача тактовых импульсов с выхода элемента И 4 прерывается по сигналу от ждущего одно- вибратора 10 на время, необходимое для считывания очередного счетчика из М элементов по N выходной регистр 2, и прекращается по сигналу с выхода элемента ИЛИ-НЕ 9 (окончание работы устройства) Блок 1 управления работает следующим образом. Генератор 13 формирует стартовый импульс, осуществляющий предустановку всех счетчиков и регистров в О. Этим же импульсом, задержанным элементами 22, 23,запускается генератор 14 тактов, разрешается передача содержимого регистра 38 через узел 30 элементов И в регистр сдвига единиц в младших разрядах параллельным кодом) и осуществляется установка триггера 16 в состояние 1. Генератор 14 вырабатывает импульсы с периодом Т0. Эти импульсы используются для синхронизации

внутреннего цикла блока 1 управления - анализа текущего сочетания. Импульсы на выходе 45 делителя частоты 15 с периодом Т - 2М0Т0 задают темп перебора сочетаний.

Первый цикл блока 1 управления инициируется стартовым импульсом, поступающим на вход элемента ИЛИ 19 от генератора 13 через элементы задержки 22, 23. Начало последующих циклов обусловливается им0 пульсами на входе 46 блока 1, которые через элемент задержки 24 поступают на второй вход элемента ИЛИ 19. Каждому циклу блока 1, кроме первого цикла, соответствует обработка одного сочетания. Признаком

5 первого цикла является состояние 1 триггера 16. Установка триггера 16 в состояние О обеспечивается первым импульсом на входе 46 блока 1. На первом этапе каждого внутреннего цикла блока 1 импульсом от

0 элемента ИЛ И 19 запускается ждущий одно- вибратор 27. Через открытый элемент И 17 с выхода генератора 14 на сдвигающий вход Mo-разрядного регистра сдвига 36 проходит пачка Мо импульсов, вызывающая цикличе5 ский сдвиг содержимого регистра. Разряды сдвигаемого кода поступают на счетный вход счетчика 26, поэтому к началу второго этапа цикла счетчик 26 получает приращение, равное числу единиц в сдвигаемом ко0 де. В результате содержимое счетчика 26 в первом цикле блока 1 оказывается равным N (начальное состояние - О, приращение - N), а в каждом последующем цикле - результату анализа текущего сочетания. На

5 втором этапе каждого внутреннего цикла блока 1 срезом импульса одновибратора 27 запускается ждущий одновибратор 28. В первом цикле импульс одновибратора 28, проходя через элемент задержки 25 и эле0 мент И 18 (открытый сигналом Г на выходе триггера 16) на управляющий вход узла 33 элементов И, обусловливает считывание числа N из счетчика 26 в регистр 32. Число N хранится в регистре 35 до окончания ра5 боты устройства. В последующих циклах блока 1 выходной импульс одновибратора 28 используется для стробирования результата анализа, поступающего на выход элемента И-НЕ 29. В начале второго и

0 последующих циклов блока 1 в регистр сдвига 36 через узел 31 элементов И заносится код текущего сочетания с параллельного выхода 43 счетчика 7. В счетчик 26 с параллельного выхода регистра 35 через

5 узел 32 элементов И и группу 34 элементов НЕ записывается поразрядно проинверти- рованный код N. Управление этими операциями осуществляется импульсом на входе 46 блока 1. В результате сдвига в регистре сдвига 36 и подсчета числа единичных разрядов в счетчике 26 формируется число, которое представляется кодом 111 только

при наличии N единиц в разрядах анализируемого сочетания. Это событие обозначается сигналом 1 на выходе 41 элемента И-НЕ 29. Работа элемента И-НЕ 29 блокируется только в первом цикле блока 1 - сигнал О на инверсном выходе триггера 16.

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

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

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

5

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

Редактор Н.Шаповалова

Составитель В.Байков Техред М.Моргентал

Фиг. 2

Корректор М.Шароши