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

 

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

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

РЕСПУБЛИК (я)л G 06 F 15/31

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4?53362/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 — функциональная схема блока управления.

„„БЦ „„1686458 А1 следовательностей в тестирующей и контрольной аппаратуре. Цель изобретения— расширение функциональных возможностей за счет изменения параметров сочетания. Устройство содержит блок 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 элементов НЕ, регистры 35 — 38. Ввод двух счетчиков в состав блоков устройства, а также конструктивное решение блока управления позволяет программировать параметры сочетания — число комбинируемых элементов и число элементов в сочетании. 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 элементов HE. регистр 35, регистр сдвига 36, регистры.37, 38, выходы 39-42, вход 43, выходы

44, 45, вход 46. Устройство последовательно формирует все сочетания из М элементов по

1686458

N (N < М .. .Mo, где М вЂ” наибольшее значение М, определяемое разрядностью регистров). При переборе сочетаний значений M значения N хранятся в регистрах 37, 38, куда они предварительно заносятся при помощи групп ключей 21, 20 (например, наборные поля). Коды в регистрах 37, 38 содержат соответственно М и N единиц в младших разрядах, Сочетания формируются счетчиком 7 и представляются наборами единичных разрядов в двоичном коде. Считывание сочетаний через блок 6 элементов И в выходной регистр 2 осуществляется только при наличии единиц в разрядах счетчика 7, Состояние счетчика 7 анализируется блоком 1 управления, Текущее сочетание поступает в блок 1 по шине 43. Обнаружение N единиц в коде сочетания сопровождается выдачей управляющего сигнала с выхода 41 блока 1 на управляющий вход блока 6 элементов И.

Счетчик 8, работающий в режиме вычитания, задает общее число 2 перебираемых сочетаний. Его начальная yc",дновка (М единиц в младших разрядах) осуществляется путем считывания содержимого регистра 37 в блоке 1 управления через блок 5 элементов И. Обнуление счетчика 8 свидетельствует об окончании перебора сочетаний и сопровождается появлением сигнала на выходе элемента ИЛИ-IHE 9. Срабатывание элемента ИЛИ-НЕ 9 запрещается при обработке первого сочетания в формируемой последовательности — управляющий сигнал с выхода 44 блока 1, Темп перебора сочетаний задается частотой тактовых импульсов с выхода 45 блока 1. Тактовые импульсы поступают через элемент задержки 3 (обеспечивает временное согласование работа блоков) и элемент И 4 на счетные входы счетчиков 7, 8 и вход 46 блока 1. Подача тактовых импульсов с выхода элемента И 4 прерывается по сигналу от ждущего одновибратора 10 на время, необходимое для считывания очередного счетчика из M элементов по N выходной регистр 2, и прекращается по сигналу с выхода элемента

ИЛИ-НЕ 9 (окончание работы устройства).

Блок 1 управления работает следующим образом. Генератор 13 формирует стартовый импульс, осуществляющий предустановку всех счетчиков и регистров в "0". Этим же импульсом, задержанным элементами 22, 23, запускается генератор 14 тактов, разрешается передача содержимого регистра 38 через узел 30 элементов И в регистр сдвига

36(N единиц в младших разрядах параллельным кодом) и осуществляется установка триггера 16 в состояние "1", Генератор 14 вырабатывает импульсы с периодом Т . Эти импульсы используются для синхронизации внутреннего цикла блока 1 управления— анализа текущего сочетания. Импульсы на выходе 45 делителя частоты 15 с периодом

Т = 2MoTo задают темп перебора сочетаний.

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

15 первого цикла является состояние "1" триггера 16. Установка триггера 16 в состояние

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

20 элемента ИЛИ 19 запускается ждущий одновибратор 27. Через открытый элемент И 17 с выхода генератора 14 на сдвигающий вход

М -разрядного регистра сдвига 36 проходит пачка М импульсов, вызывающая цикличе25 ский сдвиг содержимого регистра, Разряды сдвигаемого кода поступают на счетный вход счетчика 26, поэтому к началу второго этапа цикла счетчик 26 получает приращение, равное числу единиц в сдвигаемом ко30 де. В результате содержимое счетчика 26 в первом цикле блока 1 оказывается равным

N (начальное состояние — "0", приращение — N), а в каждом последующем цикле — результату анализа текущего сочетания. На

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

N хранится в регистре 35 до окончания ра45 боты устройства. В последующих циклах блока 1 выходной импульс одновибратора

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

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

55 узел 32 элементов И и группу 34 элементов

НЕ записывается поразрядно проинвертированный код N. Управление этими операциями осуществляется импульсом на входе

46 блока 1. В результате сдвига в регистре сдвига 36 и подсчета числа единичных раз1686458 рядов в счетчике 26 формируется число, которое представляется кодом 11....,1 только при наличии N единиц в разрядах анализируемого сочетания, Это событие обозначается сигналом "1" на выходе 41 элемента

И-Н Е 29. Работа элемента И-НЕ 29 блокируется только в первом цикле блока 1 — сигнал

"0" на инверсном выходе триггера 16.

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

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

ИЛИ-Н Е, выход которого через первый элемент

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

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

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

25 четвертого узла элементов И, выходы четвертого узла элементов И через элементы

НЕ группы соединены с соответствующими информационными разрядными входами счетчика числа единиц, выход генератора

30 одиночного импульса соединен с входами первого и третьего элементов задержки и входами начальной установки счетчика тактов, счетчика сочетаний, счетчика числа единиц, регистра сочетаний, регистра числа

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

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

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

55 соединен с входом второго ждущего мультивибратора, выход которого соединен с входом третьего ждущего мультивибратора и вторым входом второго элемента И, выход второго элемента И соединен со сдвигающим входом регистра сдвига, выход третьего

1686458

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

1686458

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

Редактор Н.Шаповалова Техред М.Моргентал Корректор M.ùàðoUjè

Заказ 3599 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101