Устройство для перебора комбинаторныхВыбОРОК Советский патент 1981 года по МПК G06F7/00 

.. , 1 ,

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

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

Наиболее близким к предлагаемому 20 изобретению является комбинаторное устройство, содержащее п последовательно соединенных К-разрядных счетчиков и группу элементов И, выходы которых являются выходами устройства, а хо- 25 дом устройства является вход п-го счетчика. Такое комбинаторное устройство обеспечивает, последовательный пребор сочетаний С при всех значениях п, начиная с единицы. 2. 30

Недостатком устройства является невозможность генерирования перестановок с повторениями и размещений.

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

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

Блок разрешения выдачи содержит (к-1) группы элементов И, (е-1) пвходовых сумматора и элемент И, причем входы каждого i-ro элемента И j-Я (. к-1) группы соединены со входамиi-й группы блока разрешения выдачи, а выходы элементов И J-и группы подключены ко входам j-rd сумматора, при этом выходы всех сумматоров подсоединены ко входам элемента И, выход которого, является выходом блока разрешения выдачи.

разрешения выдачи содержит Сп, схем сравнения и элемент ИЛИ-НЕ, причем входы Е-й (i 1, cj ) схем рравнения первой и второй групп являются входами соответств но S-й (, п) и t-й (t I,,) групп блока разрешения выдачи, при этом S t и для любых двух схем сравнен пары S., t не равны между собой, а выходы всех схем сравнения подключе ны ко входам элемента ИЛИ-НЕ, выход которого является выходом блока раз решения выдачи. На фиг. 1 изображена структурная схема устройства для перебора комби наторных выборок; на фиг. 2 - функциональная схема устройства для генерирования перестановок с повторениями из пяти элементов (п 2, п,- 1, п 2, п п 3 5) на фиг. 3 представлена функциональная схема устройства для генерирова ния размещений из пяти элементов по три (т 5, п 3); на фиг. 4 вариант 5-ти входового сум%1атора. Устройство для перебора комбинаторных вЬаборок (фиг. 1) содержит ,п последовательно соединенных счетчиков 1, группу 2 элементов И, блок разрешения выдачи. Выходы элементов И группы 2 являются выходами устройства, а входом устройства являет ся вход п-го счетчика 1. Выходы i-r (i 1, n) счетчика 1 подключены ко входам i-й группы блока 3 разрешени выдачи, при этом каждый выход счетчика 1 подсоединен к первому входу соответствующего элемента И группы второй вход которого соединен с вы ходом блока 3 разрешения выдачи. Устройство для генерирования пер становок с повторениями Р(2,1,2) (фиг. 2) содержит пять счетчиков 4-8, группу 9 элементов И, блок 10 разрешения выдачи, в состав которог входят группа 11 элементов И 12-16, группа 17 элементов И 18-22,два 5входовых сумматора 23 и 24, элемент И 25. Коэффициенты пересчета всех счетчиков равны 3.Выход каждого последующего счетчика подключен ко входу предыдущего, а вход последнег счетчика соединен с шиной 26 тактовых импульсов. Каждый выход счетчика подсоединен к первому входу соот ветствующего элемента И группы 9, второй вход которого соединен с выходом блока 10 разрешения выдачи. (ы счетчика 4 подключены ко вхо дам .элементов И 12 группы 11, И 18 rpyiifM 17. Выходы счетчика 5 подсое динены ко входам элементов И 13 группы 11, И 19 группы 17. Выходы счетчика 6 подключены ко входам эле ментов И 14 группы 11, и 20 группы 17. Выходы счетчика 7 подсоединены ко входам элементов И 15 группы 11, И 21 группы 17. Йлходы счетчика ,8 подключены ко входам элементов И 16 группы 11, И 22 группы 17. Один из возможных вариантов построения 5-входового сумматора показан на фиг. 4. Сумматор содержит два одноразрядных сумматора 27 и 28 на два входа, два одноразрядных сумматора 29 и 30 на три входа. аыходы элементов И 12-16 группы . 11 подключены ко входам 5-входового сумматора 23. Выходы элементов И 1822 группы 17 подсоединены ко входам 5-входового сумматора 24. Выходы сумматоров 23 и 24 подключены ко входам элемента И 25, выход которого является выходом блока 10 разрешения, выдачи. Устройство для генерирования размещений А 5 (фиг. 3) содержит три счетчика 31-33, группу 34 элементов И, блок 35 разрешения выдачи, в состав которого входят три cxeivEJ сравнения 36-38, элемент ИЛИ-НЕ 39. Один из возможных вариантов построения схемы сравнения представлен на фиг.З, Коэффициенты пересчета равенств кодов всех счетчиков равны 5. Выход каждого последующего счетчика подключен ко входу предыдущего, а вход последнего счетчика соединен с шиной тактовых импульсов 40. Каждый выход счетчика подсоединен к первому входу соответствующего элемента И группы 34, второй вход которого, соединен с выходом блока 35 разрешения выдачи. Выходы счетчика 31 подключены к первой группе входов 36и 37 схем сравнения. Выходы счетчика 32 подключены ко второй группе входов 36.схемы сравнения и подсоединены к первой группе входов 38 схемы сравнения. Выходы счетчика 33 подключены ко второй группе входов 37и 38 схем сравнения. Выходы 36-38 схем сравнения подсоединены ко входам элемента ИЛИ-НЕ 39,- выход которого является выходом блока 35 разрешения выдачи. В режиме генерирования перестановок с повторениями устройство работает следующим образом (фиг. 2). На выход 5-входового сумматора поступает двоичный код числа входов, на которые поступили единичные сигналы. На вход 8 счетчика с шины 26 поступает первый тактовый импульс и устанавливает счетчики 4, 5, 6, 7, и 8 .соответственно в состояния ,1,2 и, 2. На выходы старших и младших разрядов счетчиков 4,5,6,7 и 8 поступают соответственно сигналы 00,00,01,10 и 10. Нулевые сигналы с выходов счетчиков 4 и 5 поступают на инверсные входы соответственно элементов И 12, И 13, единичные сигналы с выходов которых поступают на первый и второй входы сумматора 23. Единичный сигнал с выхода младшего разряда счетчика 6 закрывает элемент И 14. Единичные

сигналы с выходов старших разрядов счетчиков 7 и 8 закрыв.гиот соответйтвенно элементы И 15, И 16. Нулевые сигналы с выходов элементов И 14, И 15, И 16 поступают соответственно на третий, четвертый и пятый входы сумматора 23. С выходов сумматора

23сигналы 0,1 и О поступают на входы элемента И 25.

Нулевые сигналы с выходов младших разрядов счетчиков 4, 5, 7 и 8 закрывают соответственно элементы И 18, и 19, И 21, И 22, нулевые сигналы с выходов которых пoctyпaютJнa первый/ второй, четвертый и пятый входы сумматора 24. Нулевой сигнал с выхода старшего разряда счетчика 6 открывает элемент И 20, через который единичный сигнал с выхода младаего разряда счетчика 6 проходит на третий вход сумматора 24, С выходов сумматора 24 сигналы 1, О и О поступают на входы элемента И 25,

Единичный сигнал с выхода элемента И 25 открывает элементы И группы 9 и разрешает выдачу кодов состояний счетчиков 4-8, Таким образом, на первом такте работы реализуется первая перестановка с повто рениями 00122, где номера позиций цифр в перестановке соответствуют номерам счетчиков, а цифры, стоящие на этих позициях, соответствуют десятичной записи двоичных кодов состояний счётчиков.

На.вход счетчика 8 с шины 26 поступает второй тактовый импульс и устанавливает счетчики 4-8 соответственно в состояния 0,0,2,0 и О, На выходы счетчиков 4-8 поступают соответственно сигналы 00,00,10,00 и 00.

Нулевое сигналы .с выходов младших разрядов счетчиков 4-8 закрывают соответственно элементы И 18-22, нулевые сигналы с выходов которых поступают на все входы сумматора24. Нулевые сигналы с выходов сумматора

24закрывают элемент И 25, нулевой сигнсш с выхода которого запрещает выдачу кодов состояний счетчиков 4-8.

На вход 8 счетчика с шины 26 поступает третий тактовый импульс и устанавливает счетчики 4-8 соответственно в состояния 0,0,2,0 и 1,

На выходы счетчиков 4-8 поступают соответственно сигналы 00,00,10,00 и 01,

Нулевые сигнашы с выходов 4,5 и счетчиков поступают на инверсные входы соответственно элементов И 12 И 13, И 15, единичные сигналы с выходов которых поступают на первый, второй и четвертый входы сумматора 23, Сигналы 1,1 и Ос выходов суЗМматора 23 закрывают элемент И 25, нулевой сигнал с выхода которого зап5«цает выдачу кодов состояний счетчиков 4-8,

На Егход счетчика 8 с шины 26 поступает седьмой тактовый импульс. На выходы счетчиков 4-8 поступают соответственно сигналы 00,00,10,01 и 10. Нулевые сигналы с выходов счетчиков 4 и 5 поступают на инверсные входы соответственно элементов И 12, И 13, единичные сигналы с выходов которых поступают на первый и второй входы сумматора 23.

С выходов сумматора 23 сигналы

0 0,1 и О поступают на входы элемента И 25,

Нулевой сигнал с выхода старшего разряда счетчика 7 открывает элемент И 21, через который единичный сигнал с выхода младшего разряда счетчика 7

5 проходит на четвертый вход сумматора 24, С выходов сумматора 24 сигналы 1,0 и О поступают на входы элемента И 25.

Единичный сигнал с выхода элемен0та И 25 открывает элементы И группы 9 и разреиает выдачу кодов состояний счетчиков 4-8, Таким образом, на седьмом такте работы реализуется вторая перестановка с повторениями 00212.

5

Работа устройства иллюстрируется табл. 1, в которой представлены состояния счетчиков 4-8, Те такты, в которых устройство генерирует перестановки с пocтopeния и Р(2,1,2), про0нумерованы.

На последнем такте работы устройства, реализуется тридцатая перестанов- ка с повторениями 22100,

В режиме генерирования размещений устройство работает следующим обра;5зом (фиг, 3) ,

На выход схемы равенства поступает единичный сигнал в случае равенства кодов, поступающих на входы схемы равенства первой и второй групп.

0

На вход счетчика 33 с щины 40 поступает пер1аый тактовый импульс и устанавливает счетчики 31-33 соответственно в состояния 0,1 и 2. На вцходы старших, средних и младших разрядов

5 счетчиков 31-33 поступают соответственно сигналы 000, 001 и 010,

С выходов счетчиков 31 и 32 сигналы 000 и 001 поступают соответственно на первую и вторую группы входов схемы 36 сравнения, С выходов счет0чиков 31 и 33 сигнала 000 и 010 поступают соответственно на первую и вторую группы входов схемы 37 срав, нения. С выходов счетчиков 32 и 33-сигналы 001 и 010 поступают соответст5венно на первую и вторую группы вхо.дов схеглл сравнения 38, Нулевые-сигналы с выходов схем 36-38 сравнения поступают на входы элемента ИЛИ-НЕ 39, единичный сигнал с.выхода которого

0 открывает элементы И группы 34- и разрешает выдачу кодов состояний счетчиков 31-33,

Таким образом, на первом такте работы реализуется первое размещение

5 012, где номера позиций цифр в р змещении соответствуют номерам счетч ков, а цифры/ стоящие на этих позиц ях, соответствуют десятичной записи двоичный кодов состояний счетчиков. На вход 33 счетчика с шины 40 по тупает второй тактовый импульс и ус танавливает счетчики 31-33 соответс венно в состояние 0,1 и 2. На выход старших, средних и младших разрядов счетчиков 31-33 поступают соответст венно сигналы 0.00, 001 и 011, С выходов счетчиков 31 и 32 сигналы 000 и 001 поступают соответственно на первую и вторую группы вхо дов схемы равенства кодов 26. С выходов счетчиков 31 и 33 сигналы 000 и 011 поступают соответственно на пе вую и вторую группы входов схемы 13 сравнения; С выходов счетчиков 32 и 33 сигналы 001 и 011 поступают соответственно на первую и вторую группы входов схемы 38 сравнения. Нулевые сигналы с выходов схем 36-38 сравнения поступают -на входы элемента ИЛИ-НЕ 39, единичный сигнал с выхода которого открывает элементы И группы 34 и разрешает выдачу кодов состояний счетчиков 31-33. Таким образом, на втором такт® работы реализуется второе размещение 013. На вход счетчика 33 с шины 40 поступает четвертый тактовый импульс и устанавливает счетчики 31-33 соответственно в состояния 0,2 и 0. На выходы старших, средних и младших разрядов счетчиков 31-33 поступают соответственно сигналы 000, 010 и 000. С выходов счетчиков 31 и 32 сигналы 000 и 010 поступают соответственно на первую и вторую группы входов схемы 36 сравнения. G выходов счетчиков 31 и 33 сигналы 000 и 000 поступают соответственно на первую и вторую группы входов схелы 37 сравнения. С выходов счетчиков 32 и 33 сигналы 010 и 000 поступают соответственно на первую и вторую группы входов схемы 38 сравнения. С выходов схем 36-38 сравнения сигналы 0,1 и О поступают на входы элемента ИЛИ-НЕ 39, нулевой сигнал с выхода которого закрывает элементы И группы 34 и запрещает выдачу кодов состояний счетчиков 31-33. Работа устройства иллюстрируется табл. 2, в которой представлены состояния счетчиков 31-33. Те такты, в которых устройство генерирует размещения А , пронумерованы. На последнем такте работы устройства реализуется шестидесятое размещение 432. Известное устройство обеспечивает последовательный перебор сочетаНИИ С при всех значениях п, начиная с единицы. По сравнению с ним предлагаемое устройство расширяетфункциональные возможности, за счет реализации всех Р (п , п,.,,. ,,« ,) перестановок с повторениями кодов состояний п + п 2. ..+ п у счетчиков с коэффициентами пересчета, равными к, всех А размещений кодов состояний п счетчиков с коэффициентами перес«ета, равными т. В случае равенства коэффициента, пересчета к (или га) числу счетчиков )п, предлагаемое устройство реализует все nf перестановок кодов состояний счетчиков. Предлагаемое изобретение может быть использовано при решении комбинаторных задач (перечисление полиномиальных коэффициентов,, вычисление перманентов),.а также задач вычислительной математики (раскрытие определителей матриц). Указанные задачи известное устройство решить не может. Предлагается внедрение изобрёте-. ния в производство на ПО ЭЛЕКТРОННАШ, а также в систему обработки данных , разрабатываемую кафедрой вычислительной техники совместно с СКВ ММС ИК АН УССР.

Перестановки с повторениями

i:f::i:i:r::f::: :j:i:L:i:: ::::i

Таблица

Продолжение табл. 1 Формула изобретения 1.Устройство для перебора комбинаторных выборок, содержащее п последовательно соединенных к-разряд ных счетчиков и группу элементов И, выхо ды которых являются выходами устройст ва, а входом устройства является вход п-го счетчика, о тличающеес я тем, что, с целью расширения функциональных возможностей за счет реализации, всех перестановок с повторениями и всех размещений, устройство содержит блок разрешения выдачи,причем выходы i-ro(,...п) счетчика подключены к входам i-й группы блока разрешения выдачи, при этом каждый выход счетчика подсоединен к первому входу соответствующего Элемента И групгйл, второй вход которого соединен с выходом блока разрешения выдачи. 2.Устройство по п. 1, о т л и ч а ю щ ее с я тем, что блок разре шения выдачи содержит (к-1) группы элементов И, (к-1) п-входовых сумматора и элемент И, причем входы каждого i-ro элемента И j-й (, к-1) группы соединены с входами i-й группы блока разрешения выдачи, а выходы

Продолжение табл, 2 элементов И j-й группы подключены к входам j-ro сумматора, при этом выходы всех сумматоров подсоединены ко входам элемента И, выход которого является выходом блока разрешения выдачи, 3. Устройство поп,1, отличающееся тем, что блок разрешения илдачи содержит С схем сравнения и элемент ИЛИ-НЕ, причем входы 8-й(, С схема сравнения перво и второй групп являются входами соответственно (S l,.njl И t-й (t 1, n) групп блока разрешения выдачи, при этом S t и для любых двух схем сравнения пары S, t не равны между собой, а выходы всех схем сравнения подключены к входам элемента ИЛИ-НЕ, выход которого является выходом блока разрешения выдачи. Источники информации, при112тые во внимание при экспертизе 1.Авторское свидетельство СССР № 446057, кл. G Об F 15/20, 1974. 2.Авторское свидетельство CCCI №374606, кл. G 06 F 15/20, 1973 (прототип). A /

/. V

/ /

i

5

u

/f

I/

2J

.J

--

2f

iJL

L.

LIL I 2