Устройство для перебора сочетаний, перестановок и размещений

 

Изобретение относится к вычислительной технике и позволяет значительно повысить быстродействие при формировании сочетаний и размещений. Устройство содержит генератор I тактовых иь1пульсов, п узлов 4 выделения первой едини1Уз1, каждый из которых состоит из группы 5 элементов ИЛИ и группы 6 элементов И, п - 1 групп 7 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и п элементов И-ИЛИ 8, выходы 9. В режиме перебора перестановок сигналы снимаются с выходов блока 2 формирования перестановок , в режиме перебора сочетаний сигналы снимаются с выходов блока 3 формирования сочетаний,в режиме перебора размещений сигналы снимаются с выходов 9. Блоком 3 выбирается сочетание элементов И-ИПИ 8, а блок 2 осуществляет все перестановки очередности появления импульсов на выходах выбранных элементов И-ИЛИ 8. 1 ил. 1C (Л

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

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

РЕСПУБЛИН

„„BU„„ At (д) с1 G 06 F 15/20

5, 1

t М

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (2!) 4144318/24-24 (22) 10.11.86 (46) 15.04.88. Бюл. М 14 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.М.Глушань и М.В.Рыбальченко (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

i9- 643883, кл. С 06 F 7/00, 1977.

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

1124319, кл. С 06 F 15/20, 1983.. (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ, ПЕРЕСТАНОВОК И РАЗМЕЩЕНИЙ (57) Изобретение относится к вычислительной технике и позволяет значительно повысить быстродействие при формировании сочетаний и размещений.

Устройство содержит генератор 1 тактовых импульсов, и узлов 4 выделения первой единицы, каждый из которых состоит иэ группы 5 элементов ПИ и группы б элементов И, и — 1 групп 7 элементов ИСКЛ10ЧА10ЩЕЕ ИЛИ и и элементов If-ИЛИ 8, выходы 9. В режиме перебора перестановок сигналы снимаются с выходов блока 2 формирования перестановок,в режиме перебора сочетаний сигналы снимаются с выходов блока 3 формирования сочетаний,в режиме перебора размещений сигналы снимаются с выходов 9. Блоком 3 выбирается сочетание элементов И-ИЛИ 8, а блок 2 осуществляет все перестановки очеред40 ности появления импульсов на выходах выбранных элементов И-ИЛИ 8. 1 ил.

1388887

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

Целью изобретения является повышение быстродействия устройства при формировании сочетаний и размещений.

На чертеже приведена структурная схема устройства,цля перебора сочета-

15 ний, перестановок и размещений для п=4.

Устройство содержит генератор тактовых импульсов, блок 2 формирования перестановок, блок 3 формирования сочетаний, и .узлов 4 выделения первой единицы, каждый из которых состоит из группы 5 элементов ИЛИ и группы б элементов И, n-I групп 7 элементов ИСКЛ!ОЧЙОЩЕЕ ИЛИ и и элементов И-ИЛИ 8, в»|ходы 9.

Принцип работы устройства состоит в следующем.

В режиме перебора перестановок сигналы снимаются с выходов блока 2 формирования перестановок. При этом очередность появления импульса в tIpp делах каждой серии из и тактовых импульсов на выходах блока 2 определяет каждую новую перестановку. Так„ при формировании перестановок из 3-х элементов каждая серия из 3"х тактовых импульсов формирует последовательность импульсов на выходах блока

2 в таком виде: 1„2!3; 2,!,3; 2,3,1;

3,1,2; 1,3,2, т.е„ приведен|гые последовательности означают„ что в первой по=ледовательности первый импульс появляется на первом выходе, второй— на втором и третий -- на третьем, во

45 второй последовательности первый импульс появляется на втором выходе, второй — на первом и третий — на третьем и т.п.

В режиме перебора сочетаний сигналы снимаются с выхода блока 3. Г!ри этом перебор сочетаний из п по ш означает, что перебираются такие всевозможные комбинации, в которых на гп выходах, блока 3 будут "I", а на

n-m выходах — "0". Так, всевозможны— ми сочетаниями из 4 по 2 будут следующие комбинации: 1100, 1010, 0110, 1001, 01 01,. 0011.

В режи !е пер <.!,ðï рлзме!лений устройств

Сигнллы в этом с.nyaле снимл!птся с выход!эв 9. !!локом 3 формирования сочетаний выбирается сочетание элементов И-И!И 8, а блок 2 формирования перестановок осуществляет все перестлнг вкн очередности появления импульсов на выходах выбранных элементов И-И !И 8. Например, формирование размещений из 4 по 3 осуществляется следующим образом. редложим, что в блоке 3 зафиксировапа такая комбинация единичных сигналов на его выходах — 1!01. Первый узел 4 выделения первой единицы и все последующие узлы 4 совместно с соединенными с ними группами 7 элементов HCK ÏÎ×AIOllIEF. ИЛИ осуще=твляет расслоение сочетаний, т.е. на выходах соответствующих узлов 4 появляются унитарные коды. Так, для рассматриваемого случая на выходах первого узла 4 злфиксируется код 1000. Этот код поступает на входы 1-й группы 7 элементов

ИСКХПОЧЛ101!!ЕЕ ИЛИ, на другие входы которых поступает полное сочетание с выходов блока 3. Поэтому через первый элемент ИСКЛ1ОЧЛ1О111ЕЕ ИЛИ единичный сигнал Hp проходит и на входы второго узла 4 поступает код 0101.

Б свою очередь, элементы ИЛИ 5 и 6 второго узла 4 выделяют только пер-!! вую 1 этого кодл, л остлльные !! !! просеивают . Поэтому на выходах второго узла 4 появляется код 0100.

Этот код и код 0101 с выходов элемейтов ИСК1ПОЧЛ1ОЩЕЕ ИЛИ ? первой группы поступают на входы элементов ИСКТПОЧЛIОЩЕЕ ИЛИ 2-й группы. Поэтому на выходе 3-ro узла 4 появляется код 0001.

На выходах 4-го узла 4 формируется нулевой код 0000. Таким образом, единичные сигналы присутствуют на 2-м входе первого элемента И-ИЛ!1, на 4-м входе второго элемента И-1Ь1И и на

6-M входе четвертого элемента И-ИЛИ.

Последовательность перестановок, формируемая на выходах блока 2 в виде очередности появления импульсов в каждой серии из 3-х импульсов, проходит на выходы l-го, 2-ro и 4-го элементов И-ИЛИ. Эта последовлтельность имеет вид: 1,2,4; 2,1,4; ?,4,1; 4,2, I; 1,4,2. После перебора всех шести перестановок при сочетании 1101 с вьгхода блока 2 на блок 3 поступает сигнал, по которому в нем формирует1388887 ся сочетание 1011. Поэтому в слудующем цикле перебора перестановок единичные сигналы в соответствующем порядке появляются на выходах I-ro, 3-ro и 4-го элементов И-ИЛИ. Так происходит до тех пор, пока не переберутся все. размещения и на выходе блока 3 не появится сигнал окончания перебора. формула изобретения

Составитель О.Березикова

Техред М.Ходанич Корректор Г.Решетник

Редактор E.Êîï÷à

Заказ 1582/51 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Устройство для.перебора сочетаний, перестановок и размещений, содержащее блок формирования перестановок и п групп элементов И, причем тактовый вход устройства соединен с тактовым входом блока формирования перестановок, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия при формировании сочетаний и размещений, оно содержит блок формирования сочетаний, и групп элементов ИЛИ (п — число элементов перебора), п-1 групп элементов HCKSIIO×AIOÙÅE

ИЛИ и п элементов И-ИЛИ, причем выход признака окончания формирования перестановок блока формирования перестановок, соединен с входом запуска блока формирования сочетаний, выход признака окончания формирования сочетаний которого является одноименным выходом устройства, выходы размещений которого соединены с выходами элементов И-.ИЛИ, (2К-1)-е входы которых (K=I, n) соединены с К-м выходом блока формирования перестановок, 2К-й вход (i-ro элемента И-ИЛИ (i=

=1, и) соединен с выходом i ãî элемента И К-й группы, выход 1 † элемента j é группы (j=l, n-1) соединен с первым входом i-ro eMeH HCKJIIOЧАЮЩЕЕ ИЛИ 1 — и группы (1=2, n), второй вход i-го элемента ИСКЛЮЧАЮЩЕЕ

ИЛИ р-й группы (р=3, n) соединен с выходом i-ro элемента ИСКЛОЧАIОЩЕЕ

ИЛИ предыдущей группы, второй вход

i-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ

2р первой группы соединен с 1-м выходом блока формирования сочетаний и с соответствующими входами элементов ИЛИ первой группы и элементов И первой группы, выход элемен25 та ИСКЛОЧА10ЩЕЕ ИЛИ 1 — и группы соеди.ен с соответствующими входами элементов ИЛИ и первыми входами элементов И 1 — и группы, вторые входы кото— рых соединены с выходами элементов

3р ИЛИ 1 — и группы.