Комбинаторное устройство Советский патент 1983 года по МПК G06F1/02 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения комбинаторных задач, а также для генерации кодовых последовательностей в .устройствах контроля. Известно комбинаторное- устройство содержащее последовательно включен,ные счетчики, элементы И и обеспечивающее последовательный перебор сочетаний (С )при всех значениях п, начиная с единицы l. Недостатком известного устройства Является невозможность генерации сочетаний с повторениями. Наиболее близким по технической сущности является комбинаторное устройство, содержащее п групп элементов И, п счетчиков, п-1 блоков сравнения и блок режима, содержащий группу эле ментов ИЛИ, элемент ИЛИ и четыре элемента И, причем тактовый вход первого счетчика является первым входом .устройства, а тактовый вход j-ro (,...n) счетчика соединен с тактовым выходом j-1-го счетчика, при этом выходы i-ro (...,п) счетчика подключены соответственно к первым входам элементов И i-й группы, выходы которых являются выходами устройства, входы q-ro (,...n-l) блока сравнения соединены соответственно с выходами q-ro и g+1-ro счетчика, при этом первые выходы блоков сравнения соединены с первыми входами элементов ИЛИ группы, выходы которых подключены к входам- первого элемента И, выход которого соединен с первым входом второго эле- мента И, выход Которого подключен к первому входу элемента ИЛИ, выход которого соединен с вторыми входами элементов И каждой из п групп, вторые выходы блоков сравнения подключены к вторым входам соответствующих элементов ИЛИ группы и к соответствующим входам третьего элемента И, выход которого соединен с первым входом четвертого элемента И, выход которого подключен к второму входу элемента ИЛИ, вторые входы второго и четвертого элементов И объединены и являются вторым входом устройства (2 Недостатком этого устройства является его сложность, обусловленная наличием п-1 блоков сравнения и блока режима, а также низкое его быстродействие. Целью изобретения является упроще ние устройства и повышение его быстродействия. Поставленная цель достигается тем что устройство, содержащее п групп элементов И, п счетчиков, причем так товый вход п-го счетчика соединен с , тактовым выходом п-1-го счетчика, выходы i-ro счетчика подключены к пе вым входам элементов И i-й группы, выходы которых являются выходами уст ройства, содержит п-1 групп элементов И, 2п-3 элементов ИЛИ, 2п-3 элементов И, 2 (п-1) элементов задержки и триггер режима, причем выходы j-ro счетчика подключены к первым входам элементов И Р-ой (,.,.,2п-1) группы, выходы которых соединены с единичными«входами триггеров (j-1)-r счетчика, первый вход первого элемен та ИЛИ и вторые входы элементов И i-ы групп подключены к тактовой шине устройства, тактовый вход q-ro счетчика подключен к выходу q-ro эле мента ИЛИ соответственно, первый вход которого подключен через элемен задержки к выходу q-ro элемента И со ответственно, первый вход К-го , п-2) элемента И и вторые входы элементов И L-ой ( ,.. .2п-2) группы подключены через элемент задержки к выходу т-го (,...,2п-3) элемента ИЛИ, а первый вход (п-1)-го элемента И и вторые входы элементов И {2п-1)-ой группы подключены через элемент задержки к тактовому выходу п-1-го счетчика, второй вход q-ro элемента И подключен к единичному выходу триггера режима, первый вход т-го элемента ИЛИ подключен к вы.ходу S-ro (,...n-l) элемента ИЛИ, а второй вход - к выходу т-го элемента И, первый вход т-го элемента И соединен с входом 5-го элемента И, а второй вход подключен к нулевому выходу триггера режима, нулевой вход триггера режима подключен к управляющей шине генерации сочетаний с повторениями, единичный вход три|- гера режима и третий вход (п-1)-го элемента ИЛИ подключены к управляющей шине генерации сочетаний, тактовый выход п-го счетчика подключен к шине окончания работы устройства, тактовые выходы К-ых счетчиков (, п-2) соединены с вторыми входами S-ых элементов ИЛИ. На чертеже представлена функциональная схема комбинаторного устройства для и ( при изменении значения m соответственно изменяется коэффициент пересчета счетчиков, а при увеличении п - увеличивается количество счетчиков, которые подключаются аналогично первому счетчику). Комбинаторное устройство состоит из трех счетчиков 1-3, групп элементов И 4, групп элементов , элементов ИЛИ 6-8, элементов И 9-11, элементов 12 задержки,триггера 13 , управляющей шины 14 генерации сочетаний с повторениями, управляющей шины 15 генерации сочетаний, шины 16 тактового входа, шины 17 окончания работы устройства. Комбинаторное устройство работает в двух режимах. . В режиме генерации сочетаний с повторениями и в режиме генерации сочетаний. В исходном состоянии счетчики должны быть установлены в 0. В режиме генерации сочетаний с повторениями на шину 14 поступает импульс, который устанавливает три|- гер 13 в нулевое состояние. Сигнал с единичного выхода триггера 13 закрывает элементы И , а с нулевого выхода триггера открывает элемент И 11. Работа устройства в режиме генерации сочетаний с повторениями иллюстрируется табл. 1, в которой представлены состояния счетчиков. I На шину 16 тактового входа пЬступает первый тактовый импульс. Поскольку счетчики 3, 2, 1 находятся в нулевом состоянии, то поступивший на входы элементов И 4 тактовый импульс выдает .на выход устройства первое сочетание с повторением 000, где номера позиций цифр в сочетании соответствуют номерам счетчиков, а цифры, стоящие на этих позициях, соответствуют десятичной записи двоичных кодов состояний соответствующих счетчиков. Этот же тактовый импульс через элемент ИЛИ 6 поступит на тактовый вход счетчика 1 и изменит его состояние на единицу, т.е. запишет в него число 1. Второй тактовый импульс аналогичным образом выдаст на выход устройства второе-сочетание 001 и запишет в счетчик 1 следующее число 2 и т.д. до пятого тактового импульса. На пятом такте будет выдано на выход устройства пятое сочетание 004, после чего импульсом с выхода элемента ИЛИ 6 счетчик 1 установится в состояние О и на его -тактовом выходе сформируется сигнал. Этот сигнал, пройдя элемент ИЛИ 7 поступит на тактовый вход счетчика 2 и запишет в нем число 1. Этот же сигнал, пройдя через элемент ИЛИ 8, задержится (на время переходных про цёссов в счетчике) на элементе 12 задержки, поступит на входы элементов И 5 и перепишет содержимое счетчика 2 в счетчик 1. Таким образом, в счетчиках 2 и 1 будет записано число 1. На шестом такте, -в. связи с этим, на выход устройства будет выдано шестое сочетание с повторением 011. С шестого по четыр надцатый такт включительно (табл.1) устройство работает аналогично описанному. На пятнадцатом, такте будет выдано на выход устройства пятнадцатое сочетание с повторением ОЦЦ, счетчик 1 установится в состояние О, затем импульсом с тактового вы хода счетчика 1, прошедшим через эл мент ИЛИ 7-на тактовый вход счетчика 2, последний установится также в О, поэтому состояние счетчика 1 тока останется без изменения. После перехода счетчика 2 в состояние О нЗ его тактовом выходе сформируется импульс, который Поступит на тактовый вход счетчика 3 и запишет в нем .число 1. Этот же импульс, задержа ный на элементе задержки, перепишет содержимое счетчика 3 в счетчик 2, а затем пройдет открытый элемент И и элемент ИЛИ 8,задержится еще раз на другом элементе задержки и перепишет состояние счетчика 2 в счетчи 1. После чего на счетчиках 3,2,1 бу дет сформировано шестнадцатое сочетание с повторением 111. В дальне шем устройство работает аналогично описанному. На тридцать пятом такте на выход устройства будет выдано последнее сочетание с повторением kkk а с тактового выхода счетчика 3 на шину 17 будет выдан сигнал окончания работы устройства. В режиме генерации сочетаний на шину 15 поступает сигнал, который установит триггер 13 режима в единичное состояние, в результате чего элементы И 9-10 откроются, а элемент И 11 закроется. Этот же импульс поступит через элемент ИЛИ 7 на тактовый вход счетчика 2, запишет в нем число 1, затем пройдет через элемент ИЛИ 8, задержится на элементе задержки, перепишет состояние счетчика 2 в счетчик 1, пройдет через открытый элемент И 9 задержится еще раз на элементе задержки, поступит через элемент 6 ИЛИ на тактовый вход счетчика 1 и скорректирует его состояние на +1 т.е. запишет в нем число самым на счетчиках устройства будет сформировано первое сочетание 012. Дальнейшая работа устройства поясняется табл. 2. На первом и втором такте устройство работает так же, как и в режиме генерации сочетаний с повторениями. На третьем (табл.2)такте на выход устройства будет выдано третье сочетание 01 А. Затем счетчик 1 установится в состояние О, на его тактовом выходе сформируется импульс, который пройдет элемент ИЛИ 7, поступит на тактовый вход счетчика 2, запишет в нем число 2 и, кроме того, пройдет через,элемент ИЛИ 8, задержится на элементе задержки, перепишет содержимое счетчика 2 в счетчик 1, а также пройдет через открытый элемент И 9, задерживается еще раз на элементе задержки, поступит через элемент 6 ИЛИ на тактов1ый вход счетчика 1 и скорректирует его состояние на 4-1. После этого на счётчиках будет сформировано четвертое сочетание 023. До шестого такта устройство работает аналогично. На шестом такте на выход устройства будет выдано сочетание ОЗ. Счетчик 1 перейдет в состояние О, сформирует на тактовом выходе импульс, который через элемент ИЛИ 7 запишет в счетчик 2 число 4, затем перепишет состояние счетчика 2 в счетчик 1V скорректирует его состояние на +1, после чего счетчик 1 снова перейдет в состояние О. С выхода счетчика 1 импульс снова.поступит на тактовый вход счетчика 2 и переведет его в состояние О. После этого на выходе счетчика 2 появи ся импульс, который последовательно осуществит следующее: запишет в счетчик 3 число 1, задержится и пе репишет содержимое счетчика 3 в счет чик 2, пройдет через открытый элемент И 10, поступит с задержкой на элемент ИЛИ 7 и далее на тактовый вход счетчика 2, скорректирует его состояние на 41, т.е. запишет в нем число 2, пройдет через элемент ИЛИ 8, перепишет содержимое счет- . чика 2 в счетчик 1, и, наконец, прой дет через открытый элемент. И 9 и элемент ИЛИ 6, поступит на тактовый вход счетчика 1 и скорректирует его состояние на +1 , ЧТО будет соответ 3. Таствовать записи в нем числа КИМ образом, в счетчиках будет сформировано седьмое сочетание 123. С седьмого такта по десятый устройство работает аналогично описанному. На десятом такте на выход устройства будет выдано последнее сочетание 23V, а на шину 17 - сигнал окончания работы устройства. Технико-экономический эффект от использования устройства состоит в следующем. Во-первых, устройство проще, поскольку вместо каждой схемы сравнения используется 1+2 элемента И (1 - количество разрядов счетчиков устройства), 2 элемента ИЛИ и 2 элемента задержки, а вместо блока режима - триггер, то есть по количеству элементов существенно меньше, что повышает надежность устройства. Во-вторых, данное устройство обладает более высоким быстродействием, поскольку для получения сочетаний с повторениями или сочетаний требуется столько тактов, сколько соответственно,самих сочетаний с повторениями или сочетаний, в то время как в известном устройстве всегда требуется тактов, что во много раз больше количества генерируемых сочетаний. 1. Таблица 1

000 001 002 003 011 012 013

022 023 024

1Ц 222 223 22Ц 233 23 2 333 34

ЦЦl Формула изобретения Комбинаторное устройство, содержащее п групп элементов И, п счетчиков, причем тактовый «ход п-го счетчика соединен с тактовым выходом п-1-го счетчика, выходы i-ro счетчика подкпю чены к первым входам элементов И -и группы (is1,...n), выходы которых являются выходами устройства, отличающееся тем, что, с целью уп рощения и повышения быстродействия, устройство содержит группы элементов И с (п+1)-ой по (2п-1)-ую, (2п-3) эле ментов ИЛИ, (2п-3) элементов И, 2(п-1 элементов задержки, триггер режима, причем выходы j-ro счетчика (..n) подключены к первым входам элементов И Р-ой группы ( ,... ,2п-1) .выходы которых соединены с единичными входами триггеров (j-l)-ro счетчика соответственно, первый вход первого эле мента ИЛИ и вторые входы элементов И i-ых групп подключены к тактовой шине устройства, тактовый вход q-ro (q«l,...,п-1) счетчика подключен к выходу q-ro элемента ИЛИ соответственно, первый вход которого подключен через соответствующий элемент задержки к выходу q-ro элемента И соответственно, первый вход К-го (Кв1.., п-2) элемента И и вторые входы элементов И L-ой (),... ,2п-2) группы .подключены соответственно через т-ый элемент задержки (,.. .2п-3)

10 Таблица- 2 к выходу т-го элемента ИЛИ, первый вход (n-l)-ro элемента И и вторые входы элементов И (2п-1)-ой группы подключены через 2{п-1) элемент задержки к тактобому выходу (n-l)-ro счетчика, вторые входы q-ых элементоэ И подключены к единичному выходу триггера режима,первый вход т-го элемента ИЛИ подключен к выходу S-ro (S«2,...) элемента ИЛИ, а второй его вход подключен к выходу т-го элемента И, первый вход т-го элемента И соединен с входом S-ro элемента И, второй его вход подключен к нулевому выходу триггера режима, нулевой вход триггера режима подключен к управляющей шине генерации сочетаний с повторениями, единичный вход триггера режима и третий вход (n-l)-ro элемента ИЛИ подключены к управляющей шине генерации сочетаний, тактовый выход п-го счетчика подключен к шине окончания работы устройства, тактовые выходы К-ых счетчиков соединенысоответственно с вторыми входами S-ых элементов .ИЛИ. Источники информации, принятые во Внимание при экспертизе 1.Авторское свидетельство СССР IT , кл. G 06 F 15/20, 1973. 2.Авторское свидетельство СССР f 760108, кл. G 06 F 15/20, 1978 (прототип).