Устройство для выбора перестановок из результата решения производящей функции

 

,„- (\

" М тР, Г,,„ © Ням

« блло «Г 4Ф . Гл@- еПЕЕЕ

ОТЕка а

ОПИСАНИЕ

И ЗОБРЕТЕ Н ИЯ

Союз Советских

Социалистииесюа

Реслублин (11) 446057

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Зависимое от авт. свидетельства (22) Заявлено 22.11. 72(21) 1830242/18-24 (51) М. Кл. G 06 1 7/38 с присоединением заявки %Гасударственный конетет

Совета Министров СССР па делам изооретений и открытий (32) Приоритет

Опубликовано 05.10.74, Бюллетень № 37

Дата опубликования описания 24.04.75 (оо) ÀK 681.325.65 (088. 8) (72) Авторы изобретения

П. E. Чистяков и В. И. Яновский (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫБОРА ПЕРЕСТАНОВОК

ИЗ РЕЗУЛЬТАТА РЕШЕНИЯ ПРОИЗВОЙЯШЕИ

ФУНКЦИИ

2 . ("= 1,2, ..., fL ), имеют результат ре. шения:

В=а,ь,..,r, а ь,...r, ...+а„ь ...г +С1ет1 тт- "n. ь (2) Однако такое устройство обладает относительно невысоким быстродействием при формировании множества сочетаний.

Сушность предлагаемого устройства за- 15 ключается в том, что производяшие функции вида, У=(и, а,...а„),(ь1ь,»" ь4,"

r -, r„)+ (1) 20 ,где Q„, Ь |,..., 1< одноименйью пере менные (элементы) функции;. у1 - число одноименных ттеременных в скобках и число скобок.

1 - индека одноименных переменных

Изобретение относится к автоматике и вычислительной технике и может использо-! ваться в системах контроля.

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

; импульсов, дифференцируюшую цепочку, схе-,: мы передачи, генератор, ключи, ячейки, тумблер и кнопку.

l0 который представляет множество комбина-: ций из тъ одноименных переменных (элементов) аjhj ... Г.„. Каждая комбинация множества (2) отличается от другой хотя бы одной переменной с другим индексом.

Если индексы переменных функций (1) условно приравнять местам переменных в перестановке, то среди множества комбинаций решения (2) сушествует такое подмножество комбинаций, у которых все т индексов одноименных переменных различны. Можно показать, что подмножество комбинаций с указанными свойствами составляет все перестановки из тс, элеменI тов.

Пример, Определить множество перестановок для переменных (элементов)

Q, b, С, пользуясь производяшей функцией (1).

Решение. Каждая пережженная С, Ь представляется в виде одноименных переменных с индексами а (а,+ай О->) ф — ж-(«hg «Qg) y

C — (С,+ С2 C ):

> и по функции (1) определяется резуль-:, тат решения

У=(а,а2а,)(Ъ,+Ь2+Ь ),«С «С )

С Ь С +G2h1C1+О Ь1С С ЬйС +02Ü2Ñ G ЗЬ2С, + а Ь,С, + azhqC, «а Ь С,+а, Ь„СУ !

+ айЬ С +-а Ь С +а,Ь2С j+ а2Ь2С2ау2С2

t 0)hgC2+ 0.2Ь С2+Ю Ь 2+© 5 С ф

<.а ь<с,+а,<,с + в,ь,с<.аяь,с », +а ь<с +а,<> с <>д><<с +а ь«е«.

В <.получение . го результата все три индекса одноимен> ных переменных различны и эти комбинации составляют множество перестановок, Р=З! =6

Р= Ь2С О йЬ С +О gbqC2+О ф ЗС2

+ О sb Cs ч" ХСъ

В полученном<выражении по индексам одноименных переменных, указываюшнх места в перестановках, запишем множество перестановок

Р= С,Ь2а,+С<айЬ +Ь С,а «а,С Ь

« фО 2,Сg Оч Ь2С

Опустив индексы, пОлучим перестановки: переменных (элементов) А,, Ь, С

Р= СЬО. «-СВь+ЬСа.аСЬ+Ьао+ аЬС, В устройстве каждый выход блока формирования комбинаций переменных подклю-!

: чен к одному из входов соответствуюшего

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

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

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

П, кольцевых регистров 2 с числом ра

5 бочих ячеек в каждом регистре1 @ и вы-. ходы 3; блок линий задержек ф ьблок

< ключей 5 с рабочими 6 и управляюшим

7 входами и выходами 8;. блок регистра ции 9;, ф - пороговых элементов 10, 19 каждый из которых настроен на два минимальных входа возбуждения; блок логики . 11, включаюший сумматор 12,: импликатор

13 и ждуший мультивибратор 14; генератор импульсов 15.

Ы Выходы 3 блока формирования комбинаций переменных 1, первый вход которого соединен с первым входом устройства, соединены через, >последовательно включен» ные блок пиний да,цержек 4 и блок клю20 чей 5 с соответствуюшими входами блока регистрации 9 и параллельно — со входами пороговых элементов 10, выходы ,которых через сумматор 12 подключены ко, входу g импликатора 13, выход

25.— — -, импликатора 13 через ждущий мультивиб-.

1 ратор 14 подключен z управляюшему входу 7 блока ключей 5, выход генератора импульсов 15 соединен со вторым входом блока формирования комбинаций перемен. ных 1 и входом (импликатора 13.

Работа устройства состоит в следующем.

Блок формирования комбинаций переменных

1 представляет собой кольцевой счетчик,, работаюший в режиме генератора параллель-! ных кодовых импульсов. Каждый кольцевой, . регистр генератора д", ", ..., р имеет ячеек, выходам которых приора-: I иваются беременны>е с индексами, Например, выходам регистра "Q " при4 сваиваются переменные с индексами "(", !

Э

Q ", . ":(. 1 выходам регистра >

"h" — переменные " b ", b », ..., Ь

45 ит»д<

Выходы регистров, которым присвоены переменные с одинаковыми индексами бу-; дем называть одноименными выходами регистров. Например, выходы блока 1

» Р»» »»К», » - »» < »

> >

" и т, д, будут одноименными выходами, По команде "Исходное" все начальные ("Н") рабочие ячейки кольцевых регион ров 2 устанавливаются в "единичные" состояния и с выходов ("Н") блока 1 снима-:

446057

5 . ется параллельный импульсный кодовый

: сигнал, соответствуюший первой комбина-! 1 ции элементов результата (2) 9<, Ь, ! ,>> 1 °

По команде ПУСК генератор импуль

5 сов 15 начинает формировать заданное число импульсов частоты f О . Импульсы последовательно поступают на второй вход блока 1 и вход )f блока логики 11.

Первый импульс с генератора 15 перево

I дит в нулевое. и единичное" состояния соответственно начальную (Н") и вторую: ячейки первого кольцевого регистра «(А», с выходов 3 блока 1 снимается второй кодовый сигнал 0 g ° " Й > Реализу™ .! юший вторую комбинацию результата (2);

g -й импульс с генератора 15 переводит, конечную ("К") и начальную (Н") ячейки регистра а соответственно в нулевое" и "единичное" состояния, а началь ную ("Н») и вторую ячейки регистра " р " соответственно в "нулевое" и "единичное" состояния. С выходов> 3 блока 1 снимаетс; ся кодовый сигнал G> Ь ... . Таким а " образом, каждый импульс с генератора

15 будет формировать на выходах 3 блоf ка 1 параллельный кодовый сигнал, соо — J..

I ветствуюший отдельной комбинации Q) g p. результата (2).

ЗО

Кодовые сигналы с выходов 3 блока 1 подаются в двух направлениях: через блок лин и задержек 4 на рабочие входы 6 бло ка ключей 5 и на входы пороговых элементов 10. К выходам каждого отдельного порогового элемента 10 подключены одно» именные выходы регистров блока 1. При этом (см. чертеж) на первый сверху поро:говый элемент 10 подключены одноименные г Р g Q ° " f> 4P на второй пороговый элемент 10 - одноименные выходы регистров "Q, "Ь ", " р " и т. д.

Е

Если кодовые сигналы с выходов 3 4> . блока 1 не соответствуют комбинациям перестановок результата (2), то на один или несколько пороговых элементов, по двум или более их входам будут поступать сигналы и соответствуюшие пороговые эле-, @ менты будут возбуждаться; на их выходах будут формироваться единичные» сигналы и поступать на входы сумматора 12 и с

его выхода на первый вход 4< имплика.тора 13 блока логики 11. Одновременно

6 на второй вход g> импликатора 13 поступает единичный"= сигнал с выхода генератора 15. На выходе импликатора 13 формируется "единичный сигнал, который возбуждает ждуший мультивибратор 14. С выхода ждушего мультивибратора на управляюший вход 7 блока ключей 5 поступает

"единичный сигнал и закрывает блок ключей 5, кодовые сигналы с выхода блока

1 не проходят.

Если кодовые сигналы с выходов 3 блока 1 соответствуют комбинациям пере становок результата (2), то ни один пороговый элемент 10 не возбуждается. На входы Х1 и Хй импликатора 13 поступают соответственно нулевой" и "единичный сигналы. Импликатор 13 не возбуж дается, ждуший мультивибратор 14 не срабатывает, блок ключей 5 остается открытым. Кодовые сигналы через блок линий задержек 4 и открытый блок ключей

5 с выходов 8 поступает на блок регистрации 9.

При всех остальных значениях сигналов на входах ) и g< импликатора 13 на управляюший вход 7 блока ключей 5 будет подаваться «единичный» сигнал, который будет закрывать блок ключей 5.

П р е д м е т и э о б р.е т е н и я

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

446057

>99 Изд. l4+gg Тираж В24

Подписное

Заказ

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

Москва, )!3035, Раугнская наб., 4

Предприятие «Патент», Москва, Г-59, Бережковская наб., 24

Составитель С.Громова

Редактор В.фельдман ТехредИ.КарандвшоввКорректор Л.Денисова