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

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советскмк

Соцмапмстмческмк республик (iii 95721 5 (6() Дополнительное к авт, свид-ву (22) Заявлено 19.03.81 (21.) 3262047/18-24 с присоединением заявки М (5i)М. Кл .

Ц 06 F 15/20 Ьоударотваанвй комитат

СССР

40 лолам изобретений и открытий (23) Приоритет

Опубликовано 07.09.82. Бюллетень М 33

1 (53) УДК681.. 3 (088. 8) Дата опубликования описания 07.09.82 юсг(; щ р; „. (72) Авторы изобретения

Г. А. Ерсипко и Н. Н. Шубина

1 ь.".

1 (71) Заявитель

« .«» : « (54) УСТРОЙСТВО ДДЯ ПЕРЕБОРА

ПЕРЕСТАН ОВ ОК

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

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

Недостатком устройства является низ- кое быстродействие (перебор всех и!

15 перестановок из и кодов обеспечивается эа n" "тактов).

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

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

И последнего разряда, первый и второй инверсные входы четвертого э иьтента И соединены с выходами счетчика соответственно последукнцего и предыдущего раз5 4 ходом элемента запрета, управляющий вход которого соединен с первым выходом дешифратора, а информационный — с тактовым входом устройства, выходы регистров с и +1-ого по 2п -й являются выходами устройства, кроме того, выходы предыдущего регистра соединены соответственно с информационными входами последующего, причем выходы 2п -ого ре гис тра соед нне ны с .информационными входами и +1-or"о регистра, выход предыдущего счетчика соединен с âõîäîì последующего счетчика, вход первого счетчика соединен с тактовым входом устройства, выход и -1-oro счетчика соединен с выходом окончания работы устройства, входы дешифратора соединены с разрядньми выходами первого счетчика, а второй выход подключен к второму входу первого, элемента И и к первым входам элементов ИЛИ с первого по и -З-й, выходы дешифратора с третьего по и -1-ый подключены к пер- вым входам элементов И с и -1-oro по 2п -5-й соответственно, остальные входы которых соединены с разрядными выходами счетчиков с второго по и -2-й соответственно и выходами всех предыдуших счетчиков, кроме первого, а выхо-. ды элементов И с и -1-ого по 2п -5-й соединены с вторыми входами элементов ИЛИ с первого по и -3-й сооТаеТ ственно, остальные входы которых соединены с выходами всех предыдущих элементов И, кроме торо, выходы элементов И с и -1-oro. по 2п -5-й подключены к вторым входам грутщ элементов И с первой по и 3-тью соответственно и к управляющим входам групп элементов запрета с первой по и -3 гью соответственно, выходы элементов ИЛИ с первого по и -3-й подключены к вторым входам элементов И с второго по и -2-ой соответственйо.

На чертеже представлена схема устрой ства для перебора перестановок (для п -5).

Устройство содержит регистры 1 -1, 21-25, группы элементов И 31-3, эль/ мент 4 запрета, группы элементов.5. -5, запрета, группы элементов И 6 -6,, элементы И 7 -74., 8 и 9, группы эле-, ментов ИЛИ 10 -10, элементы ИЛИ 1 1 и 12, дешифратор 13, счетчики 14- .

17, вход 18 тактовых импульсов, выход

19 окончания работы уствойства и ип— формационные выходы 20.

При этом счетчик 14 работает по модулю 5, счетчик 15 — по модулю 4, 3 95721 рядов, третий выход четвертого элемента И каждого разряда через соответствующий элемент задержки подключен к тактовому входу устройства, выход счетчика каждого разряда соединен с вторым инверсным входом первого и третьего элементов И и с. вторым входом второго элемента И того же разряда, причем выходы счетчиков первого и последнего разрядов и разрядные выходы регистров 10 являются выходами устройства.

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

15 за,)1! тактов) .

1= 1 цель изобретения — повышение быстродействия устройства.

Идя достижения указанной цели устройство, содержащее и -1 счетчиков, 20 регистров, 2 и -5 элементов И, и -3 элементов ИЛИ (n -3) групп элементов

ИЛИ, и -3 групп элементов запрета, причем первые входы элементов И с первого по и-2-й подключены к тактовому И входу устройства, а их выходы соединены с тактовыми входами регистров с второго по и -1-й соогветственно, выход и -2oro элемента И подключен к тактовому входу и -ого регистра, выходы регистров 30 . с второго по и -2-й подключены к информационным входам элементов запрета с первой по п. -3-тью группы соответственно, выходы которых соединены с первыми входами элементов ИЛИ с пер- 35

° вой по и -3-тью группы соответственно, подключенных своими выходами. к информационным входам регистров с третьего по и-1-й соответственно, вторые входы которых соецйнены с выходами элементов И с первой по и -3-тью группу соответственно, первые входы которых соединены с выходами п -Ого регистра, информационные входы которого подипочены к выходам и -1-ого регистра, и

45 информационными входами второго регистра, допатнительно содержит дешифра тор. элемент запрета, группы элементов

И с и -2-ой по 2п-3-тью, регистры с

n+1oro по 2п-й, причем первые входы элементов И с и -2-ой по 2п -3-тью

S0 группу соединены с выходами регистров с первого по n--й соответственно,,вторые входы подипочены к первому выходу дешифратора, третьи входы подипочены -к тактовому входу устройства, а выходы соединены с информационными входами регистров с n+1-orо но 2п-й, тактовые входы кьторых соединены с вы, 9572 счетчик 16 — по модулю 3, счетчик 17по модулю 2.

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

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

Перед началом работы в регистры . 10

1 -l5 занесены коды переставляемх величин, счетчики 14-17 находятся в состоянии "0", элемент 4 запрета закрыт, а элементы И 31-3 открыты. Работа устройства начинается с подачей на Ч вход 18 тактовых импульсов. При поступ- лении aepaoro тактового импульса происходит перепись кодов из регистров 1„-T g в соответствующие регистры 2 -25 через элементы И 3.,-35. переключейие 20 счетчика 14 в состояние «1, по которому закрываются элементы И 3.,-3 и открывается элемент 4 запрета, разрешающий поступление тактовых импульсов на тактовые входы регистров 21-2; 2З

Появляется сигнал на втором выходе дешифратора 13, открывающий элемент И 7 элементы И 7 и 74 через элементы

ИЛИ 11 и 12 и разрешающий поступление второго тактового импульса на так- щ товые входы регистров 1 -15. При поступлении тактовых импульсов с второго но четвертый коды, записанные в регист рах 21-25, сдвигаются при каждом тактовом импульсе в соседние справа регистры, причем из регистра. 25 сдвиг происход:ит в регистр 2,, а состояние счетчика 14 изменяется от «2" до "4".

Кроме этого, одновременно при поступлении второго тактового импульса коды, записанные в регистрах 1 -1, сдвигаются в соседние справа регистры через открытые элементы 5 -5+ запрета и элементы ИЛИ 10 -10, причем из регист15 сдвиг происходит в регистр 1 .

При поступлении пятого тактового импульса происходит сдвиг кодов в реестрах

2 -25 в соседние справа регистры, счетчик 14 переключается в «О", соответственно счетчик 15 в состояние 1, т.е.

S0 усганан;.:ивается исходное состояние счетжка 14 н работа устройства повторяется до тех пор, пока счетчик 14 не будет в состоянии 1, а счетчик 15 — в состоянии "3 . При поступлении 17-го

SS тактового импульса происходит сдвиг ко дов в регистрах 1 -15, 2<-2 в соседние жрава регистры, счетчик 14 переключается в состояние 2, на выходе

15 d элемента И 8 появляется сигнал, закрывакиций элемент запрета 5Э и открывающий элемент И 6 и элементы И 7 и

7, через элементы ИЛИ 11 и 12. При поступлении 18-го тактового импульса происходит сдвиг кодов в регистрах 2„25 и 1 - 1 через открытые элементы

И 6, запрета 54 и элементы ИЛИ 10 1 04 в соседние справа регистры,,счетчик

14 переключается в состояние 3," открывается элемент запрета 5,а элемент

6> закрывается. При поступлении 19-го тактового импульса происходит сдвиг кодов в регистрах 2 Kg, а счетчик 14 переключается в состояние «4». При поступлении 20-го тактового импульса ко ды в регистрах 2,,-2 сдвигаются, счетчики 14 и 15 переключаются в 0", а счетчик 16. - в 1, т.е. устанавливает ся исходное состсяние счетчиков 14 и

15 и работа устройства повторяется сна чала аналогично описанной. При поступ-. лении 58-го тактового импульса устройство работает также как при поступлении

18-го тактового импульса, кроме этого, появляется сигнал на выходе элемента

И 9, так как счетчики 14, 15 в состоянии 3, а счетчик 16 в состоянии 2, закрываккций элемент запрета 54 и открывающий элемент И 64 и элемент И 74 через элемент ИЛИ 1 2. При поступлении з 9-го тактового импульса происходит сдвиг кодов в регистрах 2„-25 в соседние справа регистры и в регистрах

14-15 через открытый элемент И 64 и элемент ИЛИ 10+. При поступлении

60-го тактового импульса происходит сдвиг кодов в регистрах 2„-2, счетчики 14-16 переключаются в "О», счетчик

17 — в «1, т.е. устанавливается исходное состояние счетчиков 14-16 и работа устройства повторяется сначала аналогично описанной. При поступлении последнего 120-ro тактового импульса происходит сдвиГ кодов в регистрах 2„2, счетчики 14-17 перекюпочаются в О и на выходе устройства 19 появляется сигнал об окончании перебора перестанвок, т.е. об окончании работы устройстТехнико4экономический эффект заключается в том, что- предлагаемое устройство обладает большим быстродействием по сравнению с известным. Количество тактов для перестановки и чисел в предо-1 лагаемом устройстве уменыцено на — — 1 ° по сравнещпо с прототипом и равно,.1, Кроме этого, в предлагаемом устройстве

7 95721 исключены и -1 линий задержки, используемых в известном устройстве. Это обеспечивает возможность дальнейшего увеличения быстродействия устройства за счет повышения частоты тактовых им1 пульсов.

Формула изобретения

19

Устройство для перебора перестановок, . содержащее и -1 счетчиков, и -регист-. ров, 2п-5 элементов И, .п -3 элемвн« тов ИЛИ, пМ групп элементов И, и -3 групп элементов ИЛИ, п»3 групп эле- 1 ментов запрета, причем первые входы элементов И с первого по и -2-й подключены к тактовому входу устройства, а их выходы соединены с тактовыми входами регистров с второго по и -1-й соответственно, выход и -2-ого элемента И подключен к тактовому входу

oro регистра, выходы регистров с второго rro n -2-й подключены к информационным входам элементов запрета с первой по и -3-гью группы соответственно, выходы которых соединены с первыми входами элементов ИЛИ с первой по

-3-тью группы соответственно, подключенных своими выходами к информа- О ционным входам регистров с третьего по и -1-й соответственно, вторые входы которых соединены с выходами элементов

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

40 дешифратор, элемент запрета, группы элементов И с и -2-ой по 2п -З-тью, регистры c n+l-ого по 2п-й, причем первые входы элементов И с и-2-ой по

2п -3-тью группу соединены с выходами

45 регистров с первого по и -й соответственно, вторые входы подключены к первому выходу дешифратора, третьи входы подключены к тактовому входу устройства, а выходы соединены с информационными входами регистров с и +1-oro по 2п -й, тактовые входы которых соединены с выходом элемента запрета, управляющий вход которого соединен с первым выходом дешифратора, а информационный - с тактовым входом -устройства выход ре гистров с и +1-ого по Бп-й являются выходами устройства, кроме того, выходы предыдущего регистра соединены соответственно с информационными входами последующего, причем выходы 2п -ого регистра соединены с информационными входами и +1-or о регистра, выход предыдущего счетчика соединен с входом последующего счетчика, вход первого счетчика соединен с тактовым входом устройства, выход и -1-ого счетчика с соединен с выходом окончания работы устройства, входы дешифратора соединены . с разрядными выходами первого счетчика, а второй выход подключен к второму вхо-. ду первого элемента И и к первым входам элементов ИЛИ с первого по и -З-й, выходы дешифратора с третьего по и -1ый подключены к первым входам элементов И с и -1-ого по 2 -5-й соответственно, остальные входы которых соединены с разрядными выходами счетчиков с второго по и -2»й соответственно и выходами всех предыдущих счетчиков, кроме первого, а выходы элементов И с и-1-ого по 2п-5-й соединены с вторыми входами элементов ИЛИ с первого по и -3-й соответственно, остальные входы которых соединены с выходами всех предыдущих элементов И, кроме того, выходы элементов И с п -1-ого по 2п-5-й подключены к вторым входам групп элементов И с первой по и -3-гью соответственно и к управляющим входам групп элементов запрета с первой по и -3-тью соответственно, выходы элементов ИЛИ с первого по n -; -й подключены к вторым входам элементов И с второго по и -2-ой соответственно. !

Исто ники информации, принятые во внимание при экспертизе

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

% 446057, кл. G 06 F 7/38, 1974.

2, Авторское свидетельство СССР

hb 748416, кл. G 06 F 15/20, 1S80 (прототип) .

957215

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

Редактор И. Тыкей Техред С.Мигунова Корректор М. Коста

Заказ 6600/38 Тираж 731 Подписное

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

113035; Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул, Проектная, 4