Устройство для перебора перестановок

ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскмкСоцмалмстмчвскмкРесттублмк и)957215 нительное к авт, саид-ву) Заявлено 19 рисоединением 3) ПриоритетОпубликован Дата опубл 15/20 ударствеецИ комит СССРнкования описания 07,09, ао дела теник УДК 681, .3(088.8) и епрцтий 2) Авторь изобрете ЙЩЩт," ,. Ерсацко и Н. Н. Шуб 1) Заявите 54) УСТРОИСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК1 2Изобретение относится к автоматике . чем первый вход первого элемента И и Вычислительной технике, предназначенокаждого разряда соединен с тактовым для получения всех и перестановок иэ входом устройства, а выход подключен к о величин и может использоваться для тактовому входу регистра того же разряда , решения хомбинаторных задач, а такжеинформационный вход которого соединен в системах контроля для генерации кодо с первым входом второго элемента И вых последовательностей.того же разряда и с выходом элементаИзвестно устройство для выбора пе- , ИЛИ следующего разряда, выход регистра рестановок, содержащее кольцевые регист- каждого разряда соединен с первым входом ры, ании задержки, пороговьв элементы, третьего элемента И того же разряда,огенератор импульсов и блок логики, в выход которого соединен с первым вхосостав .оторого входят сумматор, импли- дом элемента ИЛИ того же разряда, втокатор и ждуший мультивибратор 1. рой вход которого подключен к выходуНедостатком устройства является низ-второго элемента И того же разряда, кое быстродействие (перебор всех о т актовый вход вспомогательного регист 5перестановок из и кодов обеспечивается ра является тактовым входом устройства,эа о" тактов). информационный вход которого подключенНаиболее близким по темической сущ- к выходу элемента ИЛИ первого разряда, ности к изобретению является устройство а выход дополнительного регистра соедидля перебора перестановок, содержащее що нен с первым входом второго элемента вспомогательный регистр, а также в каж- И последнего разряда, первый и второй дом 1-вом (= 1,2,о ) разряде инверсные входы четвертого эюимета И регистр, элементы И, ИЛИ, счет як по соединены с выходами счетчика соответмодулю ( + 2), элемент задержки, при- ственно последупщего и предыдуего раз54ходом элемента запрета управляющийвход которого соединен с первым выходом дешифратора, а информационный - стактовым входом устройства, выходы регистров с и +1-ого по 2 и -й являютсявыходами устройства, кроме того, выходы предыдущего регистра соединены соответственно с информационными входамипоследующего, причем выходы 2 и -огорегистра соединены с .информационнымиВходами и +1-ого регистра, выход предыдущего счетчика соединен с,входомпоследующего счетчика, вход первогосчетчика соединен с тактовым входомустройства, выход и -1-ого счетчикасоединен с выходом окончания работыустройства, входы дешифратора соединены сразрядными выходами первого счетчика, а второй выход подключенк второму входу первого, элемента И и к первым входам элементов ИЛИ с первогопо и -З-й, выходы дешифратора с третьего по и -1-ый подключены к пер-вым входам элементов И с и -1-огопо 2 и -5-й соответственно, остальныевходы которых соединены с разряднымивыходами счетчиков с второго по и -2-йсоответственно и выходами всех предыдущих счетчиков, кроме первого, а выхо-.ды элементов И с и -1-ого по 2 и -5-йсоединены с вторыми входами элементов ИЛИ с первого по и -3-й соотвеч.ственно, остальные входы которых соединены с выходами всех предыдущихэлементов И, кроме того, выходы элементов И с и -1-ого, по 2 и -5-й подключены к вторым входам грутщ элементов И с первой по и -3-тью соответственно и к управляющим входам группэлементов запрета с первой по и -3-гьюсоответственно, выходы элементов ИЛИс первого по и -3-й подключены к вторым входам элементов И с второго пои -2-ой соответственйо. 3 95721рядов, третий выход четвертою элемента И каждого разряда через соответствующий элемент задержки подключен ктактовому входу устройства выход счетчика каждого разряда соединен с вторыминверсным входом первого и третьего,элементов И и с. вторым входом второгоэлемента И того же разряда, причем выходы счетчиковпервого и последнегоразрядов и разрядные выходы регистров 10являются выходами устройства,Недостатком устройства являетсянизкое быстродействие (перерор всех и.перестановок из о кодов осуществляется15за1 тактов) е1 фцель изобретения - повышение быстродействия устройства.Для достижения указанной цели устройство, содержащее и -1 счетчиков, 20регистров, 2 иэлементов И, и элементов ИЛИ (и -3) групп элементовИЛИ, и -3 групп элементов запрета,причем первые входы элементов И с первого по и-й подключены к тактовому 25входу устройства, а их выходы соединеныс тактовыми входами регистров с второгопо и -1-й соогветственно выход и -2 ого элемента И подключен к тактовомувходу и -ого регистра, выходы регистров 30. с второго по и -2-й подключены к информационным входам элементов запретас первой по и. -3-тью группы соответственно, выходы которых соединены спервыми входами элементов ИЛИ с пер вой по и -3-тью группы соответственно,подключенных своими выходами. к информационным входам регистров с третьегопо и-й соответственно, вторые входы которых саецйнены с выхоцами элементов И с первой по и -3-тью группусоответственно, первые входы которыхсоединены с выходами и -пго регистра,информационные входы которого подключены к выходам и -1-ого регистра, и45информационными входами второго регистра, допатнительно содержит дешифра- тор. элемент запрета, группы элементовИ с и-ой по 2 и-З-тью, регистры си+1-ого по 2 и-й, причем первые входы элементов И с и -2-ой по 2 и -3-тью50группу соединены с выходами регистровс первого по и -й соответственно, вторые входы подключены к первому выходу дешифратора, третьи входы подключены к тактовому входу устройства, а выходы соединены с информационньъщ входами регистров с и +1-ого но 2 и -й,тактовые входы кьторых соединены с выНа чертеже представлена схема устрой ства для перебора перестановок (для и -5),Устройство содержит регистры 1 -121-25, группы элементов И 31-3, эльIмент 4 запрета, группы элементов.5. -5,запрета, группы элементов И 6. -6элементы И 7-74., 8 и 9, группы эле-, ментов ИЛИ 10 -1 О, элементы ИЛИ 1 1и 12, дешифратор 13, счетчики 14-,17, вход 18 тактовых импульсов, выход19 окончания работы устройства и в. -формационные выходы 20,При этом счетчик 14 работает помодулю 5, счетчик 15 - по модулю 415 бэлемента И 8 появляется сигнал, закрыт запр Э кр щий элемент И 6 и элементы И 7 и 7, через элементы ИЛИ 11 и 12. При поступлении 18-го тактового импульса происходит сдвиг кодов в регистрах 2- 2и 1- 1 через открытые элементы И 6, запрета 5 д, и элементы ИЛИ 10- 104 в соседние справа регистрысчетчик 14 переключается в состояние 3," открывается элемент запрета 5 а элемент 6 закрывается. При поступлении 19-го тактового импульса происходит сдвиг кодов в регистрах 2 25; а счетчик 14 переключается в состояние 4. При поступлении 20-го тактового импульса ко ды в регистрах 2-2 сдвигаются, счетчики 14 и 15 переключаются в 0, а счетчик 16 - в "1, т.е. устанавливает ся исходное состсяние счетчиков 14 и 15 и работа устройства повторяется сначала аналогично описанной. При поступ-.лении 58-го тактового импульса устройство работает также как при поступлении18-го тактового импульса, кроме этого,появляется сигнал на выходе элементаИ 9, так как счетчики 14, 15 в состоянии 3, а счетчик 16 в состоянии 2",закрываккций элемент запрета 54 и открывающий элемент И 64 и элемент И 74,через элемент ИЛИ 12. При поступлении 59-го тактового импульса происходит сдвиг кодов в регистрах 2-25 всоседние справа регистры и в регистрах14-1 через открытый элемент И 64 иэлемент ИЛИ 10,. При поступлении60-го тактового импульса происходитсдвиг кодов в регистрах 2-2, счетчики 14-16 переключаются в "0, счетчик17 - в 1", т.е. устанавливается исходное состояние счетчиков 14-16 и работа устройства повторяется сначала аналогично описанной. При поступлении последнего 120-го тактового импульса происходит сдвиг кодов в регистрах 2- 2, счетчики 14-17 перекюпочаюгся в О и на выходе устройства 19 появляется сигнал об окончании перебора перестановок, т.е. об окончании работы устройстТехникокэкономический эффект заключается в том, что предлагаемое устройство обладает большим быстродействием по сравнению с известным. Количество тактов для перестановки и чисел в предолагаемом устройстве уменьшено на-- 1 по сравнещпо с прототипом и равно -1,Кроме этого, в предлагаемом устройстве, 9572 счетчик 16 - по модулю 3, счетчик 17- по модулю 2.Количество элементов в группах и разрядность регистров соответствует количеству двоичных разрядов, необходимых для представления в двоичном коде максимального из переставляемых чисел.Устройство работает следующим образом.Перед началом работы в регистры . 1 О 1-15 занесены коды переставляемых величин, счетчики 14-17 находятся в состоянии "0", элемент 4 запрета закрыт, а элементы И 31-3 открыты. Работа устройства начинается с подачей на Ч вход 18 тактовых импульсов. При поступ-лении первого тактового импульса происходит перепись кодов из регистров 1-1 в соответствующие регистры 2, -2 через элементы И 3.,-35, переключейие 20 счетчика 14 в состояние 1, но которому закрываются элементы И 3.,-3 и открывается элемент 4 запрета, разрешающий поступление тактовых импульсов на тактовые входы регистров 21-2; .23 Появляетсясигнал на втором выходе дешифратора ЪЗ, открывающий элемент И 7 элементы И 7 и 74 через элементы ИЛИ 11 и 12 и разрешающий поступление второго тактового импульса на так- ЗО товые входы регистров 1-1. При поступлении тактовых импульсов с второго но четвертый коды, записанные в регист рах 21-2, сдвигаются при каждом тактовом импульсе в соседние справа регистры, причем из регистра. 2 сдвиг происходит в регистр 2 а состояние счетчика 14 изменяется от 2 до 4".Кроме этого, одновременно при поступлении второго тактового импульса коды, записанные в регистрах 11-1, сдвигаютсяв соседние справа регистры через открытые элементы 5-5+ запрета и элементы ИЛИ 10-10, причем из регистра 1 сдвиг происходит в регистр 1.При поступлении пятого тактового импульса происходит сдвиг кодов в реестрах 2-2 в соседние справа регистры, счетчик 14 переключается в О, соответственно счетчик 15 в состояние "1", т.е.Я устанан;.:ивается исходное состояние счетчика 14 н работа устройства повторяется до тех пор, пока счетчик 14 не будет в состоянии 1, а счетчик 15 - в состоянии 3". При поступлении 17-го55 тактового импульса происходит сдвиг ко дов в регистрах 1-15, 2-2 в соседние трава регистры, счетчик 14 переключается в состояние 2, на выходе7 95721 исключены и -1 линий задержки, используемых в известном устройстве. Это обеспечивает возможность дальнейшего увеличения быстродействия устройства за счет повышения частоты тактовых импульсов. Формула изобретения19Устройство для перебора перестановок, . содержащее и -1 счетчиков, и -регист-, ров, 2 иэлементов И; и -3 алеман тов ИЛИ, и 3 групп элементов И, и -3 групп элементов ИЛИ, иЗ групп эле ментов запрета, причем первые входы элементов И с первого по и -2-й подключены к тактовому входу устройства,а их выходы соединены с тактовыми входами регистров с второго по и -1-й соответственно, выход и -2-ого элемента И подключен к тактовому входу иого регистра, выходы регистров с второго по и -2-й подключены к информационным входам элементов запрета с первой по и -3-гью группы соответственно, выходы которых соединены с первыми входами элементов ИЛИ с первой по-3-тью группы соответственно, подключенных своими выходами к информа- ЗО ционным входам регистров с третьего по и -1-й соответственно, вторые входы которых соединены с выходами элементов И с первой по и -3-тью группу соответственно, первые входы которых соединены с выходами и -ого регистра, информационные входы которого подключены к выходам и -1-ого регистра, и информационными входамивторого регистра, о тл и ч а ю ш е е с я тем, что, с целью повышения быстродействия, оно содержит40 дешифратор, элемент запрета, группы элементов И с и -2-ой по 2 и-З-тью, регистры с и+1-ого по 2 и-й, причем первые входы элементов И с и-ой по 2 и -3-тью группу соединены с выходами45 регистров с первого по и -й соответственно, вторые входы подключены к первому выходу дешифратора, третьи входы подключены к тактовому входу устройства,а выходы соединены с информационнымивходами регистров с и +1-ого по 2 и -й,тактовые входы которых соединены с выходом элемента запрета, управляющийвход которого соединен с первым выходом дешифратора, а информационный - стактовым входом .устройства, выходю регистров с и +1-ого по Эи-й являютсявыходами устройства, кроме того, выходыпредыдущего регистра соединены соответственно с информационными входами последующего, причем выходы 2 и -ого регистра соединены с информационнымивходами о +1-ого регистра, выход предыдущего счетчика соединен с входомпоследующего счетчика, вход первогосчетчика соединен с тактовым входомустройства, выход и -1-ого счетчикассоединен с выходом окончания работыустройства, входы дешифратора соединены .с разрядными выходами первого счетчика,а второй выход подключен к второму вхо.ду первого элемента И и к первым входам элементов ИЛИ с первого по и -З-й,выходы дешифратора с третьего по и -1 ый подключены к первым входам элементов И с и -1-ого по 2-5-й соответственно, остальные входы которых соединены с разрядными выходами счетчиковс второго по и -2 й соответственно ивыходами всех предыдущих счетчиков,кроме первого, а выходы элементов И си-ого по 2 и-й соединены с вторыми входами элементов ИЛИ с первогопо и -3-й соответственно, остальныевходы которых соединены с выходамивсех предыдущих элементов И, крометого, выходы элементов И с и -1-огопо 2 и-й подключены к вторым входамгрупп элементов И с первой по о -3-тьюсоответственно и к управляющим входамгрупп элементов запрета с первой под -.3-тью соответственно,выходы элементов ИЛИ с первого по и й подключенык вторым входам элементов И с второгопо и -2-ой соответственно.Исто ники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРЖ 446057, кл. Ь 06 Р 7/38, 1974.2, Авторское свидетельство СССР957215 ставитель А. Клюев хред С,Мигунова Корректор М. Ко актор И. Тыкей Заказ 6600/ НИИПИ 130 юпил ППП "Патент", г. Ужгород, , П ираж 731осударственногоелам изобретениМосква, ЖПодписноекомитета СССРи открытийРаушская набд. 4/5