Устройство для перебора сочетаний,размещений и перестановок Советский патент 1984 года по МПК G06F7/06 

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

24319

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

УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ, РАЗМЕЩЕНИЙ И ПЕРЕСТАНОВОК, содержащее первую группу регистров, блок управления, генератор тактовых импульсов, переключатель, коммутатор, выходной регистр, элемент ИЛИ, причем группа информационных входов коммутатора соединена с выходами регистров первой группы, выход выходного регистра является выходом устройства, отличающееся тем, что, с целью сокращения количества оборудования, оно содержит вторую группу регистров, две группы элементов И, две группы элементов ИЛИ, группу элементов сравнения, счетчик, дещифратор, делитель, три элемента задержки, причем блок управления содержит группу регистров сдвига, группу триггеров, группу элементов И, группу элементов ИЛИ, группу элементов запрета, элемент ИЛИ, причем управляющие входы коммутатора соединены соответственно с выходом перво- го регистра сдвига, выходами элементов запрета группы, выходом предпоследнего регистра сдвига блока управления и выходом первого элемента .задержки, вход которого соединен с выходом делителя, входами размещения приема регистров первой группы и входом первого регистра сдвига блока управления, первые входы элементов ИЛИ группы которого соединены с первым входом элемента ИЛИ, входом установки последнего регистра сдвига блока управления и входом начальной установки устройства, который соединен с входом установки счетчика, тактовый вход которого соединен с входом делителя и выходом генератора (Л тактовых импульсов, управляющие входы коммутатора, начиная с второго, соединены соответственно с группой входов переключателя, группа выходов которого соединена с соответствующими входами элементов ИЛИ первой груп-; пы, выходы которых соединены с первыми входами элементов И первой группы, вторые входы которых соединены с выходами соответствующих регистров первой группы, а выходы являются выходами сочетаний устройства, входы k-ro элемента ИЛИ второй группы соединены соответственно с (k-l)-M выходом первой группы, k-м выходом второй группы, (k+1)-M выходом третьей группы коммутатора и k-м входом устройства, (где , ..., п, п количество элементов перебора), выходы элементов ИЛИ второй группы соединены с входами.соответствующих регистров второй группы, выходы которых соединены с информационными входами соответствующих регистров пер

Изобретение относится к вычислительной технике и может быть использовано для построения спедаализированных вычислительных устройств, пре назначенных для решения задач автоматизированного конструирования ради .электронной и вычислительной аппарат туры. Известно устройство для перебора перестановок, содержащее в каждом разряде регистр, счетчик, элемент ШШ четыре элемента И, элемент задержки и один вспомогательный регистр на все устройство ij . Однако это устройство характеризуется низким быстродействием. Кроме того, оно не позволяет получать размещения и сочетания. Известно устройство для перебора перестановок, содержащее первую и вторую группы циклически соединенных регистров, первую группу элементов И, через которые каждый регистр первой группы соединен с соответствующим регистром второй группы, элемент запрета, группу элементов запрета группу элементов ШШ и вторую группу элементов И, через которые осуществляется связь между регистрами первой группы по длинным либо коротким циклам, последовательно соединенные .счетчики, дешифратор, соединенный с выходами первого счетчика, элементы И, соединенные с выходами дешифратора и с выходами последующих счетчиков, элементы. ШШ, соединенные с одним из выходов дешифратора и выходами упомянутых элементов И, третью группу элементов И, каждый из которых входами соединен с выходами генератора тактовых импульсов и с выходом ;соответствующего элемента ШШ, а выходом - с входом соответствующего регистра первой группы 21, Недостатками известного устройства являются низкая функциональная надежность и невозможность получения сочетаний и размещений. Наиболее близким к предлагаемому по технической сущности является устройство для перебора сочетаний, размещений и перестановок, содержащее запоминающую матрицу, регистр сдвига, два элемента И, два триггеpa, генератор тактовых импульсов, элемент ИЛИ, блок регистров, выходной регистр, переключатель, коммутатор, блок деления и блок управления, причем горизонтальные шины задоминающей матрицы соединены с выходами регистра сдвига, а еевертикаль ные шины через последовательно соеди ненные блок регистров, коммутатор и блок деления подключены к выходному регистру, выходы блока управления соединены с управляющими входами бло ка деления и коммутатора, вход запуска устройства соединен с первьм входом первого триггера,второй вход которого подключен к первому выходу регистра сдвига,выход первого триггера подключен к первым входам второго триггера, злемента ИЛИ и первого эле мента И, второй вход которого подклю чен к первому выходу генератора импульсов, выход первого злемента И подключен к прямому входу регистра сдвига, второй выход генератора импульсов подключен к первому входу второго злемента И, второй вход кото рого подключен к выходу второго триг гера и второму входу злемента ИЛИ, выход которого подключен к входу генератора импульсов, третьи входы первого и второго триггеров через переключатель соединены с соответствующими входами регистра сдвига, выход второго элемента И соединен с инверсным входом регистра сдвига з Недостатком этого устройства явля ется сложность его реализации, а при числе элементов, участвующих в перестановках, больше шести оно оказывается практически нереализуемым. Это вызвано тем, что число разрядов регистра сдвига и соответственно число горизонтальных шин запоминающей матрицы представляют величину-кгде п - число элементов в перестанов ках. Цели изобретения --сокращение количества оборудования. Поставленная цель достигается тем, что устройство для перебора сочетаний, размещений и перестановок содержащее первую группу регистров, блок управления, генератор тактовых импульсов, переключатель, коммутатор., выходной регистр, элемент ИЛИ, причем группа информационных входов коммутатора соединена с выходами реппгистров первой группы, выход выходного регистра является выходом устройства, включает в себя вторую группу регистров, две группы элементов И, две группы элементов ИЛИ, группу элементов сравнения, счетчик, дешифратор, делитель, три элемента задержки, причем блок управления содержит группу регистров сдвига, группу триггеров, группу элементов И, группу элементов ИЛИ, группу элементов запрета и элемент ИЛИ, причем управляющие входы коммутатора соединены, соответственно с выходом первого регистра сдвига, выходами эле1ментов запрета группы, выходом предпоследнего регистра сдвига блока управления и выходом первого злемента задержки, вход которого соединен с выходом делителя,входами размещения приема регистров первой группы и входом первого регистра сдвига блока управления, первые входы элементов ИЛИ группы которого соединены с первым входом элемента ИЛИ, входом установки последнего регистра сдвига блока управления и входом начальной установки устройства, который соединен с ВХОДОМ установки счетчика, тактовый вход которого соединен с входом делителя и выходом генератора тактовых импульсов, управляющие входы коммутатора, начиная с второго, соединены соответственно с группой входов переключателя, группа входов которого соединена, с соответствующими входами элементов ИЛИ первой группы, выходы которых соединены с первыми входами элементов И первой группы, вторые входы которых соединены с выходами соответствующих регистров первой группы, а выходы являются выходами сочетаний устройства, входы k-ro злемента ИЛИ второй группы соединены соответственно с (k-l)-M выходом первой группы, k-м выходом второй группы, (k+1)-M выходом третьей группы коммутатора и k-M входом устройства (где , ..., п, п - количество элементов перебора) , выходы элементов ИЛИ второй группы соединены с входами соответствующих регистров второй группы, выходы которых соединены с информационными входами соответствующих регистров первой группы, первыми входами соответствующих элементов сравнения группы и первыми входами соответствующих элементов И второй группы, выходы которых соединены с соответст вующими входами элемента ШШ, выход которого соединен с входом выходного регистра, выход счетчика соединен с входом дешифратора, выходы которого соединены с вторыми входами соот- . ветствующих элементов И второй группы, выходы перестановок устройства соединены с выходами элементов срав нения группы, вторые входы которых соединены с выходом счетчика, выход первого элемента задержку соединен с входом второго элемента задержки, выход которого соединен с входом третьего элемента задержки и первыми входами элементов И группы блока управления, выход третьего элемента задержки соединен с вторьм входом элемента ИЛИ блока 5гаравлений причем в блоке управления выход элемента ИЛИ соединен с нулевыми входами триггеров группы, выходы которых соединены с вторыми входами соответ ствующих элементов И группы, выходы которых соединены с вторыми входами соответствующих элементов ШШ группы, выходы которых соединены с установочными входами соответствующих последовательно соединенных регистров сдвига группы, единичными входами соответствующих триггеров групп и информационными входами соответствующих элементов-запрета группы, управляющие входы которьпс соединены соответственно с выходами всех регис ров сдвига с большими номерами, кроме последнего, выход которого соединен .с выходом окончания генерирования устройства,. На фиг. 1 приведена структурная схема предлагаемого устройства для перебора сочетаний, размещений и перестановок для случая пяти переставляемых элементов; на фиг. 2 - струк- турнач схема блока управления. Устройство для перебора сочетаний размещений и перестановок содержит первую группу регистров, комму татор 2, состоящий из групп элементов И и групп элементов ИЖ, блок 5 управления, блок 6 переключателей, первую группу ) элементов ШШ, первую группу 8j-8 элементовИ, вторую группу эле ментов ИЛИ с входами , вторую группу 11,-115 регистров, вторую группу 12,-125 элементов И, групп , элементов -сравнения с выходами , счетчик 15, дешифратор 16, элемент ИЛИ 17, выходной регистр 18, генератор 19 тактовых импульсов, делитель 20, элементы 21, 22 и 23 задержки, вход 24 установки исходного состояния, выход 25 окончания генерирования. Блок 5 управления содержит последовательно соединенные регистры 26|А 26 сдвига, триггеры , элементы , запрета, элементы И 29,-293, элементы ШШ 30,-30з и ИЛИ 31, причем число разрядов в регистре 26 сдвига равно двун, а в каждом последующем ца единицу больше, чем в предьщущем-(входы и выходы блока 5 управления на фиг. 2 расположены в строгом соответствии с их расположением на фиг. 1). Устройство для перебора сочетаний, размещений и перестановок может работать в трех режимах: генерирование перестановок,, генерирование размещений и генерирование сочетаний. Для генерирования перестановок по входам 10 в регистре 11 записываются исходные элементы, например числа 1, 2, 3, 4, 5, причем запись этих чисел в регистре 1 может производиться в любом порядке. Для удобства будем считать, что эти числа записаны в возрастающем порядке, начиная с верхнего регистра 11. На вход 24 подается сигнал установки в исходное состояние блока 5 и счетчи-ка 15. Первый тактовый импуйьс с выхода делителя 20 производит перепись элементов , т.е. чисел 1, 2, 3, 4и5, из регистров 11 в соответствующие регистры 1 и одновременно устанавливает единицу на первом выходе блока 5. Благодаря этому задержанный элементом 21 первый тактовый импульс, поступая на входы всех групп элементов И коммутатора 2, переписывает числа из регистра 1,j в регистр 11U, из регистра 1 в регистр 11, из регистра 1 в регистр 11, из регистра 1д в регистр 1Ц и из регистра 1 в регистр 11j. Задержанный эле ментами 22 и 23 первьй тактовый импульс, поступая на второй и третий входы блоков 5, никаких изменений не производит. Тактовые импульсы с генератора 19 тактовых импульсов, частота кото

71

рых в п раз вьппе, чем с выхода делителя 20 (п - число элементов в перестановках) , поступая на счетчик 15, суммируются. Так как выходы счетчика 15 соединены со всеми элементами 13 сравнения, то при поступлении каждого тактового импульса на этот счетчик, в одном из элементов 13 сравнения проис: одит сравнение кодов счетчику 15 и соответствующего регистра 11. На выходе 14 той схемы 13 сравнения, где произошло сравнение, появляется сигнал. Кроме того, производится перепись содержимого соответствующего регистра 11 через элементы И 12 и ИЛИ 17 на выходной регистр 18.

После этого на выходе делителя 20 появляется второй импульс, который переписывает числа из регистров 11,j1Ц в регистры соответственно. Этот же импульс проходит на выход . регистра 26 блока 5 и появляется на втором его выходе, переводит в единичное состояние триггер 27 и поступает с выхода регистра 2в на вход регистра 2б2.

В соответствии с этим задержанный второй импульс с выхода элемента 21 переписывает числа 2, 3, 1, 4, 5 из регистров регистры соответственно. Этот же импульс, пройдя через элемент 22 задержки, поступает на второй вход блока 5 и через открытый элемент И 291 и элемент ИЛИ 30 сбрасывает регистр 26 в исходное состояние, а пройдя через элемент 23 задержки, поступает на третий вход блока 5 и через элемент ИЛИ 31 устанавливает в исходное состояние триггер 27.

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

14- 2 4 5 Одновремен но по сигналам с дешифратора 16 пере писываются числа 2, 3, 1, 4, 5 из ре гйстров Ц в регистр 18. Таким образом, параллельная форма представ ления перестановок в регистрах 114 llj преобразуется в последовательную форму в регистре 18 и пространственно-временную форму последовательности появления сигналов на выходах элементов срав нения.

243198

.После перебора всех 120 перестановок на выходе 25 регистра 264 появляется сигнал, который является сигналом окончания работы в режиме 5 генерирования перестановок.

При генерировании размещений работа не отличается от режима генерирования перестановок. Различие заключается лишь в том, что перед

10 началом работы числа, отличные от нуля, нужно занести не во все регистры 11, а лишь в некоторые. Так, например, при генерировании размещений из 5 по 2 в л.обые два регистра

15 необходимо .записать числа,, отличные от нуля. Сравнение чисел происходит лишь в тех элементах 13 сравнения, на которые поступают, из регистров 11 не нулевые числа. Поэтому

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

5 11 в каждом цикле меняются, то к моменту появления сигнала конца работы устройства (на выходе 25 блока 5) перебираются всевозможные комбинации пар элементов 13 сравнения,

0 в которых происходит сравнение чисел, и на соответствующих выходах 14 появляются сигналы. Все эти комбинации пар элементов сравнения являются размещениями из 5 по 2. Таким образом, получаем все размещения из 5 по . в форме пространственновременной последовательности появления сигналов- на выходах 14.

В режиме генерирования сочетаний

Q информация снимается с выходов элементов И .. Исходная установка такая же, как и в режиме генерирования перестановок. Переключателем 6 задается число элементов из общее ГО числа, которые должны участвовать в формировании сочетаний. Так, если замкнут первьп контакт переключателя 6, то формируются сочетания из 5 по 4, если второй - из 5 по 3,

Q если третий - из 5 по 2.

Принцип формирования сочетаний основан на периодическом исключении из перестановок лишних комбинаций. Так, при замкнутом третьем контакте 5 переключателя 6 на выходах, элементов И 8, и 82 появляются через одну комбинацию все сочетания элементов из 5 по 2. При замкнутом втором контакте 9112А3 ka выходе элементов И 8, Sg, 83 появляются через шесть комбинаций все сочетания из 5 по 3 и т.д. /Таким образом, предлагаемое устройство для перебора сочетаний, раз- 5 мещений и перестановок позволяет генерировать перестановки, размещения и сочетания, причем перестановки представляются в форме не только парал9лельных но и последовательных кодов, форме пространственно-временной последовательности появления .сигналов на выходах элементов сравнения. Исключение из устройства сдвигового регистра, запоминающей матрицы, блока деления и замена их группами элементов И, 1ШИ, обуславливает сокращение количества оборудования.