Устройство для перебора перестановок
Оп ИСАНИЕ
ИЗОБРЕТЕНИЯ
Союз Советских
Социалистических
Республик
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву
Р )М К з
G 06 F 15/20 (22) Заявлено 11.0881 (21) 3331309/18-24 с присоединением заявки HP
Государственный комитет
СССР по делам изобретений и открытий
{23) Приоритет
)$3) УДК б81.31 (088.8) Опубликовано 07.02.83. Бюллетень М 5
Дата опубликования описания 07,0 83 (72) Автор изобретения
Крылов (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК
Изобретение относится к автоматйке и вычислительной технике и может использоваться для решения комбинаторных задач, а также в системах конт- 5 роля для генерации кодовых последовательностей.
Известно устройство для выбора перестановок, содержащее кольцевые регистры, линии зацержки, пороговые элементы, генератор импульсов и блок логики, в состав которого входят сумматор, импликатор и ждущий мультивибратор (1).
Недостатком известного устройства является низкое быстродействие (перебор всех п. перестановок из и кодов обеспечивается за Il тактов), h
Наиболее близким по технической сущности к предлагаемому является устройство для перебора перестановок-, содержащее вспомогательный регистр, а также в каждом i-м (i = 1,2,..., и) разряде регистр, элементы И, ИЛИ, счетчик по модулю (i + 2), элемент задержки, причем первый вход первого элемента И каждого разряда соединен с тактовым входом устройства, а выход подключен к тактовому входу регистра того же разряда, информационный =вход
Ф которого соединен с первым входом второго элемента И того же разряда и с выходом элемента ИЛИ следующего разряда, выход регистра каждого разряда соединен с первым входом третьего. элемента И того же разряда, выход которого соединен с первым входом элемента ИЛИ того же разряда, второй вход которого подключен к выходу второго элемента И того же разряда, тактовый вход вспомогательного регистра является тактовым входом устройства, информационный вход которого подключен к выходу элемента ИЛИ первого,разряда, а выход дополнительного регистра соединен с первым входом второго элемента И последнего разряда, первый и второй инверсный входы четвертого элемента И соединены с выходами счетчика соответственно последующего и предыдущего разрядов, третий выход четвертого элемента И каждого Разряд через соответствующий элемент задержки подключен к тактовому входу устройства, выход счетчика каждого разряда соединен с вторым инверсными входом первого и третьего элементов И и с вторьм входом второго элемента И того же разряда, причем выходы счетчиков первого и последнего разрядов и
995093 разрядные выходы регистров являются выходами устройства (2) .
Недостатком известного устройства является низкое быстродействие (перебор всех и! перестановок из и кодов
5 осуществляется за I 1.! тактов) .
i=1
Цель изобретения — повышение быстродействия устройства.
Поставленная цель достигается тем, 1О
4то устройство для перебора перестановок,содержащее (п-))счетчиков с коэффи-, циентами пересчета 2, 3 .. °, и соответст- . венно,регистр(п-2) групп элементов И и
ИЛИ, причем выход первого счетчика подключен к первому входу первого элемента И первой группы, выход p-ro счетчика (p = 2,3,..., n-2) подключен к первому входу первого элемента
И р-й группы, выход которого подключен к счетному входу (р+1) -го счетчика, выход первого элемента И первой группы подключен к счетному входу второго счетчика, введены (n-1) групп элементов И-ИЛИ и дешифраторы, причем каждая h-я группа элементов
И-ИЛИ (h = 1,2,..., n-1) содержит h элементов 2 Й-ЙЛи -и один элемент (h+1) И-ИЛИ, первый вход устройства соединен с первыми входами первых элементов И первой группы элемента ЗО
2 И"ИЛИ, i-й вход устройства (i =
2,3...,, n) соединен с первым входом
i-го элемента И элемента i И-ИЛИ (i-1)-й группы и с первыми входами вторых элементов И элементов 2 И-ИЛИ 3$ (1+1)-й группы, выходы элементов 2ИИЛИ первой группы соединены с первыми входами первых элементов И второй группы элементов 2И»ИЛИ соответственно и с первьми входами элементов И ф) элемента ЗИ-ИЛИ второй группы соответственно„выходы j -й группы элементов 2И-ИЛИ и элемента (j +1) И-ИЛИ (1 * 1,2,..., n-2) соединены с первыми входами первых элентов И (+1)- 45 группы элементов 2И-ИЛИ соответственно и с первьми входами элементов И элемента (j +2) И-ИЛИ (j +1)-й группы соответственно, выходы (и-1)-й группы элементов 2И-ИЛИ и элемента пИ-ИЛИ о соединены с выходами устройства соответственно, первый выход первого дешифратора соединен с вторым входом второго элемента И второго элемента
2И-ИЛИ первой группы, второй выход первого дешифратора соединен с вторым входом первого элемента И второго элемента 2И-ИЛИ первой группы и с вторыми входами элементов И первого элемента 2И-ИЛИ первой группы, первый вы-. ход Х-ro дешифратора (2 = 2,3,...> . 60
g ;. 1) соединен с вторым входом (3+1)ro элемента И элемента (2+1) И-ИЛИ
Ю-й группы, к-й выход 2-го дешифратора (к - 2,3,..., 1+1) соединен с вторьм входом (Р - к + 2)-ro элемента И 65 элемента (2+1) И-ИЛИ 2-й группы и с вторыми входами элементов И (2-к+2)-ro элемейта 2И-ИЛИ Й-й группы, входы де- . шифраторов соединены с выходами счетчиков соответственно, вход тактовых импульсов устройства соединен со счетным входом первого счетчика, выход которого подключен к первому входу второго элемента И первой группы, выход которого подключен к первому входу элемента ИЛИ, вторые входы элементов И первой группы подключены к первому выходу и-ro дешифратора, выход
Ы-го счетчика (Р ф и-1) подключен к первому входу второго элемента И р-й
Группы, выход которого подключен к р-му входу элемента ИЛИ, вторые входы элементов И р-й группы подключены к р-му выходу и-го дешифратора, выход (n-l) -ro счетчика подключен к (и-1) -му входу элемента ИЛИ, выход которого подключен к шине конца работы устройства, выходы регистра подключены к входам n-ro дешифратора соответственно.
На чертеже представлена блок-схема предлагаемого устройства.
Устройство содержит счетчики 1 -1„ 1 с коэффициентами пересчета 2, 3, 4, и, дешифраторы 2„-2„ „, 3, ре- гистр 4, элементы 2И-ИЛИ 5"-5" " ЗИи-+
ИЛИ 6, 4И-ИЛИ 7,..., пИ-ИЛИ 8, элементы И 9 -9п 2, l0<-10д 2, элемент ИЛИ
ll, входы 12 -12„, 13, выходы 14 .14>, выходную шину 15 конца работы.
Первый вход 12 „ соединен с первы ми входами первых элементов И первой группы элементов 2И-ИЛИ 5„ -5>, i-й вход 12; (i = 2,3,..., n) соединен с первым входом i-ro элемента И элемента iH-ИЛИ и с первыми входами вторых элементов И (i-l)-й группы элементов
:2И-ИЛИ 5„""-5 ;, и-й вход 12п соеди:нен с первым входом n-ro элемента И элемента пИ-ИЛИ 8 и с первьми входами вторых элементов И (и-й) -й группы элементов 2И-ИЛИ 5 — 5" + выходы перИ- 1 1 вой группы элементов 2И-ИЛИ 5 „- 5 д соединены с первыми входами элементов
И второй группы соответствующих элементов 2И-ИЛИ 5 „ - 5 > и с первьми входами соответствующих элементов И элемента ЗИ-ИЛИ б, выходы,j-й группы элементов 2И-ИЛИ 5> - 5< и элемента (j +1) И-ИЛИ (j= l, 2,...,n-2)
1 соединены с первыки входами первых элементов И соответствукщих элементов
2И-ИЛИ 5)+ -5 +" и с первыми входами соответствующйх элементов И элемента (j +2) И-ИЛИ, выходы (и-1)-й группы элЕментов 2И-ИЛИ 5 1 "- 5"„ „и элемента пИ-ИЛИ 8 соединены с соответствующими выходами 14 - 14„, первый выход первого дешифратора 2„ соединен с вторым входом второго элемента И элемента 2И-ИЛИ 5 1, второй выход первого дешифратора соединен с вторьм входом первого элемента И эл мента
995093
Состояние счетчика
1 " 1
Результат
ТИ, Р
1 2 3 4
2 1 3 4
1 3 2 4
2 3 1 4
3 2 1 4
3 1 2 4
l 243
О О
2И-ИЛИ 5" и с вторым входом второго
Ф элемента И и вторьи инверсньм входомпервого элемента И элемента 2И-ИЛИ 5„, первый выход Р-го дешифратора (2.=2, 3,..., n.-l) соединен с вторим входом (У+1) элемента И элемента (Р+1)И-ИЛИ, к-й выход Ю-го дешкфратора (к 2, Зр ... 2+1) соедин<:н с вторым входом (3 - к+2) элемента И элемента (2+1.)ИИЛИ, прямым входом второго элемента
И и инверсным входом первого элемента И элемента 2И-ИЛИ 5,,. входы дешифраторов 2 — 2 соединены с выл- ходами соответствующих счетчиков 1 l„ вход 13 тактовых импульсов соединен с входом счетчика 1„, выход ко- 15 торого соединен с входами элементов
И 9„, И 10 -, выход элемента И 9> соеинеи с входом счетчика l, выходы . лементов И 10< — И 10 „ соединены с входами элемента ИЛИ ll, выход р-го 2О счетчика соединен с входами элементов И 9.и И 10, выход элемента И 9 соединен с входом (р+1) счетчика,-вы-. ход (n-1) счетчика 1„ соединен с входом элемента ИЛИ 11, выход регистра 25
4 соединен с входами дешнфратора 3, выходы дешифраторы 3 соединены соответственно с инверсными входами элементов И 9 и с входами элементов И 10, выход элемента ИЛИ ll соединен с вы- 3() ходной шиной 15 конца работы.
Устройство работает следукщим образом.
В.регистр 4 записывается число m значение которого равно числу. пере, станавливаемых чисел (m = 2,3,..., n»1). Если m = n, то в регистр 4 число не записывается.
Для примера рассмотрим работу устройства для перестановки четырех чи- 4О сел. В регистр 4 записывается число
4. На третьем выходе дешифратора 3 высокий потенциал и элемент И 9> закрыт, элемент И 10> открыт, а остальные элементы И 9 открыты, элементы
И 10 закрыты, выход счетчика 1 через 45 открытый элемент И 10 к элемент ИЛИ
11 соединен с выходной шиной 15 конца работы.
Счетчики 1„ - l находятся в нулевом состоянии, на йервых выходах дешифраторов 2,, - 2„ — высокие потен- циалы, которые поступают на l-е элементы И элементов 1К-ИЛИ, в элементах 2И-ИЛИ открыты первые элементы
И, так как на инверсные входы не подано высоких потенциалов. Следовательно, первый вход соединен с первьэа выходом, второй — с вторьм, третий — с третьим и т.,д.
В зависимости от состояний счетчиков 1., — 1, входы 12 - 12п будут подключаться через элементы И-ИЛИ к различным выходам 14 - 14„. Так, в зависймости от состояния счетчика 1., второй вход 122 может быть подключен к второму выходу 142 (состояние счетчика 1 - О) и к первому выходу 14, а первый вход 12., — к второму:выходу
14 2 (состояние счетчика 1„ - 1). В зависимости от состояния второго счетчика 12 третий вход 12 подключей к третьей выходной шине 143 (состояние
О), третий вход 12 подключен к второй, а второй вход 12 — к третьему выходу (состояние 1), третий вход подключен к первому, а первый вход — . к третьему выходу (состояние 2),. В зависимости от состояния р-ro счетчика 1 (р+1.) вход подключен к (р+1)-му вьжоду (сЬстояние О), (р+1) вход подключен к р-му выходу, а р-й вход — к (р+1) выходу (состояйке l) к т.д., (p+l) вход подключен к первому выходу, а первый вход — K (р+1-) выходу (состояние р).
Если на входы подать числа, то на выходах в зависимости от состояний счетчиков получат все возможные перестановки этих чисел. Возможные перестановки для четырех чисел представлейы в таблице.
995093
Продолжение таблицы
1И, Р
Состояние счетчика 2
Результат
1 0
0 1
0 2
0 О
1 0
0 1
13
0 2
1б
18
Q О
1 2
При поступлении 24 тактового импульса счетчики 1 — 1 устанавливают-.л5
1 Э ся в нулевое состояние, а импульс с выхода счетчика 1> поступает через элемент И 10З, элемент ИЛИ 11 на выходную шину 15 конца работы.
За 24 такта работы обеспечивается перебор всех перестановок иэ четырех чисел. Если требуется обеспечить перебор перестановок 5 чисел, то в ре.гистр 4 записывается число 5, элемент
И. 104 открыт, а элемент И 94 закрыт и выход четвертого счетчика 1@ соеди- 5 нен с выходной шиной 15 через элементы И 10 и ИЛИ 11. После поступления
