Комбинаторное устройство

 

(72) Автор изобретения

В. М. Полищук (7I) Заявитель (54) КОМБИНАТОРНОЕ УСТРОЙСТВО

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

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

n, начиная с единицы 1).

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

Наиболее близким по технической. сущности является комбинаторное уст. ройство,содержащее и групп элементов

И, и. счетчиков, и-1 блоков сравнения и блок режима, содержащий группу эле-2о ментов ИЛИ, элемент ИЛИ и четыре элемента И, причем тактовый вход первого счетчика является первым входом .устройства, а тактовый вход j-ro

2 ()2,...n) счетчика соединен с так" товым выходом j-1-го счетчика, при этом выходы i-1-о (11.. .,n) счетчика подключены соответственно к первым входам элементов И 1-й группы, выходы которых являются выходами . устройства, входы q-го (q 1 и"1) блока сравнения соединены соответственно с выходами q-го и 9+I-го счетчика, при этом первые выходы блоков сравнения соединены с первыми входами элементов ИЛИ группы, выходы которых подключены к аходам первого элемента И, выход которого соединен с первым входом второго элемента И, выход которого подключен к первому входу элемента ИЛИ, выход ко" торого соединен с вторыми входами элементов И каждой из и групп, вторые выходы блоков сравнения подключены к вторым входам соответствующих элементов ИЛИ группы и к соответствующим входам третьего элемента

И, выход которого соединен с первым

3, 9914 входом четвертого элемента И, выход которого подключен к второму входу элемента ИЛИ, вторые входы второго и четвертого элементов И объединены и являются вторым входом устройства $2)

Недостатком этого устройства является его сложность, обусловленная наличием и-1 блоков сравнения и блока режима, а также низкое его быстродействие. 10

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

Поставленная цель достигается тем, что устройство, содержащее и групп элементов И, и счетчиков, причем тактовый вход и-го счетчика соединен с, тактовым выходом п-1-ro счетчика, выходы i-го счетчика подключены к пер20 вым входам элементов И i-й группы, выходы которых являются выходами устройства, содержит и-1 групп элементов И, 2п-3 элементов ИЛИ, Zn-3 элементов И, 2 (n-1) элементов задержки и триггер режима, причем выходы J-го счетчика подключены к первым входам элементов И P-ой (P n+1,...,2n-1) группы, выходы которых соединены с единичными входами триггеров (3-1)-го

30 счетчика, первый вход первого элемен- та ИЛИ и вторые входы элементов И

1-û групп подключены к тактовой шине устройства, тактовый вход q-ro счетчика подключен к выходу q-го элемента ИЛИ соответственно, первый

35 вход которого подключен через элемент задержки к выходу q-ro элемента И соответственно, первый вход К-го К1;., и-2) элемента И и вторые входы элементов И L-ой (=п+1,...2n-2) группы подключены через элемент задержки к выходу m-ro (m=n,...,2n"3) элемента ИЛИ, а первый вход (n-1)"го элемента И и вторые входы элементов

И (2п-1)-ой группы подключены через элемент задержки к тактовому выходу и-1-го счетчика, второй вход q-го элемента И подключен к единичному выходу триггера режима, первый вход

-m-ro элемента ИЛИ подключен к выходу S-го (S=2,...n-l) элемента ИЛИ, а второй вход - к выходу m-ro элемента И, первый вход в-ro элемента

И соединен с входом S-ro элемента

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

32 4 с повторениями, единичный вход триггера режима и третий вход (n-1)-го элемента ИЛИ подключены к управляющей шине генерации сочетаний, тактовый выход и-го счетчика подключен к шине окончания работы устройства, тактовые выходы К-ых счетчиков (К1, и-2) соединены с вторыми входами

S-ых элементов ИЛИ.

На чертеже представлена функциональная схема комбинаторного устройства для m=5 и n=3 (при изменении значения m соответственно изменяется коэффициент пересчета счетчиков, а при увеличении n - увеличивается количество счетчиков, которые подключаются аналогично первому счетчику).

Комбинаторное устройство состоит из трех счетчиков 1-3, групп элементов И 4, групп элементов И 5, элементов ИЛИ 6-8, элементов И 9-11, элементов 12 задержки, триггера 13, уп. равляющей шины 14 генерации сочетаний с повторениями, управляющей шины 15 генерации сочетаний, шины 16 тактового входа, шины 17 окончания работы

5 устройства.

Комбинаторное устройство работает в двух режимах..

В режиме генерации сочетаний с повторениями и в режиме генерации сочетаний. В исходном состоянии счетчики должны быть установлены в 0.

В режиме генерации сбчетаний с повторениями на шину 14 поступает импульс, который устанавливает триггер 1:3 в нулевое состояние. Сигнал с единичного выхода триггера 13 закрывает элементы И 9-10, а с нулевого выхода триггера открывает элемент И 11.

Работа устройства в режиме генерации сочетаний с повторениями иллюстрируется табл. 1, в которой представлены состояния счетчиков. !

На шину 16 тактового входа поступает первый тактовый импульс. Поскольку счетчики 3, 2, 1 находятся в нулевом состоянии, то поступивший на входы элементов И 4 тактовый импульс выдает .на выход устройства первое сочетание с повторением 000, где номера позиций цифр в сочетании соответствуют номерам счетчиков, а цифры, стоящие на этих позициях, соответствуют десятичной записи двоичных кодов состояний соответствующих

99!432

На шестом такте на выход устройства будет выдано сочетание "034".

Счетчик 1 перейдет в состояние "0", .сформирует на тактовом выходе импульс, который через элемент ИЛИ запишет в счетчик 2 число "4", затем перепишет состояние счетчика 2 в счетчик 1, скорректирует его состоя5 счетчиков. Этот же тактовый импульс через элемент ИЛИ 6 поступит на тактовый вход счетчика 1 и изменит его состояние на единицу, т.е. запишет в него число "1". Второй тактовый импульс аналогичным образом выдаст на выход устройства второе =сочетание 001 и запишет в счетчик 1 следующее число "2" и т.д. до пятого тактового импульса.

1О

На пятом такте будет выдано на выход устройства пятое сочетание

"004", после чего импульсом с выхода элемента ИЛИ 6 счетчик 1 установится в состояние "0" и на его тактовом 15 выходе сформируется сигнал, Этот сигнал, пройдя элемент ИЛИ 7, поступит на тактовый вход счетчика 2 и запишет в нем число "1". Этот же сигнал, пройдя через элемент ИЛИ 8, 20 задержится (на время переходных про цессов в счетчике) на элементе 12 задержки, поступит на входы элементов И 5 и перепишет содержимое счетчика 2 в счетчик l. Таким обра- 25 зом, в счетчиках 2 и 1 будет записано число "1". На шестом такте, .в связи с этим, на выход устройства будет выдано шестое сочетание с повторением "011". С шестого по четыр- зв надцатый такт включительно (табл.!)

- устройство работает аналогично о.1исанному.

На пятнадцатом. такте будет выдано на выход устройства пятнадцатое сочетание с повторением "044",, счетчик 1 установится в состояние

"0", затем импульсом с тактового выхода счетчика 1, прошедшим через элемент ИЛИ 7 на тактовый вход счетчика 2, последний установится также в "0", поэтому состояние счетчика 1 тока останется без изменения. После перехода счетчика 2 в состояние "0" . на его тактовом выходе сформируется импульс, который поступит на тактовый вход счетчика 3 и запишет в нем

1 число "1". Этот же импульс, задержанный на элементе задержки, перепишет содержимое счетчика 3 в счетчик 2, sî а затем пройдет открытый элемент И 11 и элемент ИЛИ 8,задержится еще раз на другом элементе задержки и перепишет состояние счетчика 2 в счетчик

1. После чего на счетчиках 3,2,1 будет сформировано шестнадцатое сочетание с повторением "111". В дальнейшем устройство работает аналогично описанному.

На тридцать пятом такте на выход устройства будет выдано последнее сочетание с повторением "444", а с тактового выхода счетчика 3 на шину

17 будет выдан сигнал окончания работы устройства.

В режиме генерации сочетаний на шину 15 поступает сигнал, который установит триггер 13 режима в единичное состояние, а результате чего элементы И 9-10 откроются, а элемент

И 11 закроется. Этот же импульс поступит через элемент ИЛИ 7 на тактовый вход счетчика 2, запишет в нем число

1, затем пройдет через элемент ИЛИ 8, задержится на элементе задержки, перепишет состояние счетчика 2 в счетчик 1, пройдет через открытый элемент

И 9, задержится еще раз на элементе задержки, поступит через элемент

6 ИЛИ на тактовый вход счетчика 1 и скорректирует его состояние на "+1" т ° е. запишет в нем число "2". Тем самым на счетчиках устройства будет сформировано первое сочетание "012".

Дальнейшая работа устройства поясняется табл.2,.

На первом и втором такте устройство работает так же, как и в режиме генерации сочетаний с повторениями.

На т рет ьем (табл. 2. ) такте на .выход устройства будет выдано третье сочетание "0 14 !. Затеи счетчик 1 установится в состояние "0", на его тактовом выходе сформируется импульс, который пройдет элемент ИЛИ 7, поступит на тактовый вход счетчика 2, запишет в нем число "2" и, кроме того, пройдет через, элемент ИЛИ 8, задержится на элементе задержки, перепишет содержимое счетчика 2 в счетчик 1, а также пройдет через открытый элемент И 9, задерживается еще раз на элементе задержки, поступит через элемент 6 ИЛИ на тактовый вход счетчика 1 и скорректирует его состояние на "+1". После этого на счетчиках будет сформировано четвертое сочетание "023". До шестого такта устройство работает аналогично.

7 991432 8

Таблица 1

Такт, Состояние счет- Такт, H чиков 3,2,1 Р

Состояние счетчиков 3,2,1

Состояние счетчиков

3 2,1

-Такт, У

144

033

000

034

26

222

001

223

15

002, 28

224

003

004

233

112

30

234

113

011

012

114

244

333

334

20

013

122

014

123

344

124

22

022

444

133

35

023

134.

024 ние на "+1", после чего счетчик 1 снова перейдет в состояние "0". С выхода счетчика 1 импульс снова.rioступит на тактовый вход счетчика 2 и переведет его в состояние "0". После этого на выходе счетчика 2 появится импульс, который последовательно осуществит следующее: запишет в . счетчик 3 число "1", задержится и перепишет содержимое счетчика 3 в счет- 10 чик 2, пройдет через открытый элемент И 10, поступит с задержкой на элемент ИЛИ 7 и далее на тактовый вход счетчика 2, скорректирует его состояние на "+1", т.е. запишет в нем число "2", пройдет через элемент

ИЛИ 8, перепишет содержимое счетчика 2 в счетчик 1, и, наконец, пройдет через открытый элемент. И 9 и эле- мент ИЛИ 6, поступит на тактовый вход счетчика 1 и скорректирует его состояние на "+1", что будет соответствовать записи в нем числа "3". Та" ким образом, в счетчиках будет сформировано седьмое сочетание "123". С седьмого такта по десятый устройство

J работает аналогично описанному. На десятом такте на выход устройства будет выдано последнее сочетание

"234", а на шину 17 - сигнал окончания работы устройства.

Технико-экономический эффект от использования устройства состоит в следующем. Во-первых, устройство проще, поскольку вместо каждой схемы сравнения используется 1+2 элемента И (l - количество разрядов счетчиков устройства), 2 элемента ИЛИ и 2 элемента задержки, а вместо блока режима - триггер, то есть по количеству элементов существенно меньше, что повышает надежность устройства.

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

m тактов, что во много раз больше количества генерируемых сочетаний. !

991432

Таблица- 2

Состояние счетчиков

3, 2,1

Такт,й

Состояние счетчиков 3, 2, 1

Такт, It

034

123

013.3

124

014

134

023

234

024

10 формула изобретения к выходу m-ro элемента ИЛИ, первый вход (n-1)-ro элемента И и вторыевходы элементов И (2п-1)-ой группы подключены через 2(n-1) элемент задержки .к.тактовому выходу (n-1)-го счетчика, вторые входы q-ых элементов И подключены к единичному выходу триггера режима, первый вход

m-ro элемента ИЛИ подключен к выходу S-го (32,...,n-1) элемента ИЛИ, а второй его вход подключен к выходу

m-ro элемента И, первый вход m-ro элемента И соединен с входом S"ro элемента И, второй его вход подключен к нулевому выходу триггера режима, нулевой вход триггера режима подключен к управляющей шине генерации сочетаний с повторениями, единичный вход триггера режима и третий вход (n-1)-ro элемента ИЛИ подключены к управляющей шине генерации сочетаний, тактовый выход и-го Счетчика подключен к шине окончания работы устройства, тактовые выходы К-ых счетчиков соединены соответственно с вторыми входами S-ых элементов, ЗЛИ.

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

И с (и+1)-ой по (2n-1)-ую, (2п-3) элементов ИЛИ, (2n-3) элементов И, 2(n-1 элементов задержки, триггер режима, причем выходы j-ro счетчика (J2,. n) ss подключены к первым входам элементов

И P-ой группы (P n+1,...,2n-1),выходы которых соединены с единичными входами триггеров (j-1)-го счетчика соответственно, первый вход первого эле-40 мента ИЛИ и вторые входы элементов

И i-ых групп подключены к тактовой шине устройства, тактовый вход q-ro (<р*1,...,n"1) счетчика подключен к выходу q-ro элемента ИЛИ соответст- 43 венно, первый вход которого подключен через соответствующий элемент задержки к выходу q-го элемента И соответственно, первый вход К-ro (К1 и-2) элемента И и вторые входы эле- so ментов И L-ой (L n+1) 2п-2) группы.подключены соответственно через

m-ый элемент задержки (m n 2n-3) Источники информации, принятые во внимание при экспертизе

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

И 374606, кл. G 06 F 15/20, I9732. Авторское свидетельство СССР

It 760108, кл. G 06 F 15/20, 1978 (прототип).

991432

Составитель А. Клюев

Редактор С, Патрушева Техред Т.Иаточка Корректор М. Демчик

Заказ 136/68, Тираж 704 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5 филиал ППП "Патент", г. Ужгород, ул. Проектная, 4