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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения комбинаторных задач автоматизации конструирования . Цель изобретения - повышение быстродействия. Устройство содержит группу счетчиков 1-4, группу элементов И 5-8, элемент И 9, группу элементов И 10-12, элементы задержки 13-15, элемент ИЛИ 16,

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

И9! (! I I

Ã5II 4 О всюсонм %

1П ",13

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ать !0 -I«

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4142134/24-24 (22) 04. 11.86 (46) 23. 05.88. Бюл, % 19 (72) Таганрогский радиотехнический институт им, В.Л.Калмыкова (72) В,M. Глушань, И .Г.Ефремов, М.И.Пупков и Л.И.ll1epáaxov (53) 681 ° 325.5(088.8) (56) Авторское свидетельство СССР

И 748416, кл. О 06 F 15/20, 1978.

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

В 1190388, кл . G ОЬ F 15/20, 198 (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения коибинаторных задач автоиатизации конструирования. !!ель изобретения - повышение быстродействия. Устройство содержит группу счетчиков 1-4, группу элементов И 5-8, элемент И 9, группу элементов И 10-12, элементы задержки 13-15, элемент ИЛИ 16, вход 17 установки исходного состояния, тактовый вход 18, информационные вьгходы 19, группу элементов ИЛИ

20-23, элемент ИЛИ 24, группу элементов ИЛИ 25-27, триггеры 28-30, группу элементов запрета 31-32, элементы запрета 33,34, элемент И 35, 1397933

Т-триггер 36, элемент HF. 37, регистры 38-42, группу элементов И 43-66, группу элементов ИЛИ 67-78, Устройство позволяет генерировать п! перестановок из п переставляемых элемени! тов за --- тактов. 4 ил.

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

Целью изобретения является повышение быстродействия устройства.

На фиг. 1 приведена структурная схема устройства для и-5 переставляе»»»»х элементов, на фиг. 2 - струкгурная схема взаимосвязи всех регстрон. на фиг. 3 и 4 — схемы разрядов регистров.

Устройство содержит счетчики 1-4, .»»ч»чс м счетчик 1 — по mod 2, счетчик

2 — .-n»»od 3, счетчик 3 — по mod 2, счетчик 4 — по mod 3, группу элементов И 5-8, элемент И 9, группу эле20 ментов И 10-12, элементы t 3-15 задержки, элемент ИЛИ 16, вход 17 установки исходного состояния, тактовый вход

18, информационные выходы 19, группу элементов ИЛИ 20-23, элемент ИЛИ 24, группу элементов ИЛИ 25-27, триггеры 28-30, группу элементов 3 1 и 32 запрета, элементы 33 и 34 запрета, элемент И 35, Т-триггер 36, элемент

НЕ 37, регистры 38-42, группы 43=48, 49-54, 55-60, 61-66 элементов И, груп пу элементов ИЛИ 67-78, синхронизирующие входы 79-81 разрядов регистров, входы 82-84 разрядов регистров, выход 85 разряда регистра, элементы 35

И 86 и 87,элементы ИЛИ 88 и 89, Dтриггер 90 и элемент И 91 °

Принцип работы устройства состоит в следующем.

Каждая очередная перестановка по- 40 лучается из предыдущей путем обмена элементами (кодами) между соответствующими позициями по строго определенной закономерности. Алгоритм перестановок предусматривает отображение первых ч тырех элементов после каждого такта обмена информацией между ячейками независимо от общего количества элементов, участвующих в перестановках. Зеркальное отображение подразумевает перестановку элемента, занимающего первую позицию, в четвертую позицию, а элемента, занимающего четвертую позицию, — в первую, и, соответственно, элемента, занимающего вторую позицию, — в третью, а элемента, занимающего третью позицию, — во вторую.

Рассмотрим алгоритм работы устройства на примере перестановки четырех элементов. Нумеруют позиции, занимаемые элементами, слева направо и в позиции 1,2,3,4 записывают соот— ветственно элементы 1 2 3 4. Получают 12 основных и 12 зеркальных перестановок.

Стрелки показывают в каких позициях происходит смена элементов. После каждой перестановки формируется зеркальное отображение первых четырех элементов, Из приведенной послелова1 234

1. 1 2 34

2.2134

3.2314

4,3214

5.3124

6. 1 3 2 4 — Ф вЂ”

7.3142 8. t 3 4

9.1243

10. 2 1 4 3

11. 2 3 4 1

12. 3 2 4 1

1 234

1 . 4 3 2 1

2.4312

3.4132

4 . 4 1 2 3

4213

6 ° 4 2 3 1

2 4 1 3

8 .2431

9 . 34 21

10, 3 4 1 2

1t,1432

12.1423

123456

60. 123456

61. 213456!

23456

60 . 432156

61, 431265

55 з 13979 тельности видно, что обмен элементов, стоящих в первой и во второй позициях, происходит через одну перестановку, а элементов, стоящих в третьей

5 и четвертои позициях, через шесть перестановок. В перных шести перестановках обмен элементов, стоящих во второй и третьей позициях, происходит через одну перестановку, а в следую- 1р щих шести перестановках обмен элементов, стоящих во второй и третьей позициях, не происходит, а происходит через одну перестановку обмен элементов, стоящих во второй и четвер- 15 той позициях. Смена элементов, стоящих в двух старщих позициях, влечет за собой смену элементов между всеми парами всех младших позиций. Это хорошо видно из приведенного примера. 2р

Когда через шесть перестановок происходит обмен элементов, находящихся н третьей и четвертой позициях, то одновременно должен происходить обмен элементов, стоящих в первой и второй 25 позициях. Когда старшими при обмене являются первая и вторая, вторая и третья, вторая и четвертая позиции

) то они не вызывают обмена парами младших позиций, поскольку таковых прос- gp то нет.

Приведенное правило легко применяется на большее число элементов с не. пременным условием, что после каждой перестановки элементов в ячейках ре35 гистров зеркальному отображению подвергаются только первые четыре младших разряда, а старшие разряды остаются нетронутыми. Так, обмен элементов, находящихся в четвертой и пя- 4р той позициях, происходит через 12 перестановок, в пятой и шестой позициях через 60 перестановок. В конечном счете такая смена элементов, стоящих .в N u N-1 позициях происходит через (N-1)1. /2 перестановок. На основании сказанного можно, например, подсчитать, что после 60-й перестановки, т.е. для получения 61-й перестановки

) должна происходить смена элементов в 50 первой и второй, третьей и четвертой, пятой и шестой !позициях, т.е.

Перестановки 60 .и 6 1 являются зеркальньии для перестановок 60 и

33

61 соответственно. Аналогично лля получения 721-й перестановки должен происходить обмен элементов, стоящих во второй и третьей, четвертой и пятой, шестой и седьмой позициях.

1234567 1234567

720. 1234567 720 . 4321567

721. 13254 76 721, 52314 76

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

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

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

По сигналу, поступающему на вход

17 установки исходного состояния, сбрасываются триггеры 28-30, счетчики 1-4 и Т-триггер 36, в регистры

38-42 записываются двоичные коды чисел 2,1,3,4,5 соответственно. При отсутствии тактовых импульсов на входе 18 устройства на выходе элемента

HE 37 присутствует логическая "1", которая разрешает прохождение информации, поступающей от регистров 384 1, через нечетные элементы И 43-66, элементы ИЛИ 67-78 на информационные выходы 19 устройства, на которых фиксируются коды чисел 4,3, 1,2,5 соответственно. Верхний уровень тактового импульса, поступающего на вход устройства 18, вызывает появление на выходе первого разряда счетчика

1 единичного потенциала, который, пройдя через открытый элемент И 5, одновременно на первый вход которого подается задержанный первый импульс, через элемент ИЛИ 20 попадает на синхронизирующие входы 79 и 82 разрядов регистра 38 и синхронизирующие входы 79 разрядов регистра 39, что приводит к обмену информацией между регистрами 38 и 39. Задержанный первый импульс вызывает появление логического "0" на выходе элемента

НЕ 37, который запрещает прохождение информации, поступающей с выходов раз1397933 рядов регистров 38-41 через нечетные элементы И 43-66, а логическая "1" на выходе элемента 15 задержки разрешает прохождение информации, поступающей от регистров, через четные элементы И 43-66 и соответствующие элементы И 43-66 и ИЛИ 67 — 78. На выходах 19 устройства фиксируются коды чисел 1,2,3 4,5 соответственно. .Нижний уровень тактового импульса, пройдя через элемент 15 задержки, вызывает появление "1" на выходе элемента НЕ 37, которая разрешает прохождение информации через нечетные элементы И 43-66 и соответствующие элементы ИЛИ 67-78, "0" с выхода элемен та 15 задержки запрещает прохождение информации через четные элементы И

43-66.На выходах 19 устройства фик- 2п сируются коды чисел 4,3,2,1,5 соответственно.

Верхний уровень тактового импульса вызывает появление на выходе счетчика 1 единичного потенциала, 25 который поступает на первые входы элемента 34 запрета и элемента И 35, на вторые входы которых поступает

"0" со сброшенного триггера 36, который запрещает прохождение сигнала через элемент И 35 и разрешает через элемент 34 запрета, далее сигнал проходит через открытый элемент

31 запрета, на вторые входы которого поступают "0" со сброшенных счет35 чиков 2 и 3, проходит открытый элемент И 6, элемент ИЛИ 21 и поступает на синхронизирующие входы разрядов регистров 39 и 40, что приводит к обмену информацией между ними, 0 40 на выходе элемента НЕ 37 запрещает прохождение информации через нечетные элементы И 43-66, а "1" на выходе элемента 15 задержки разрешает прохождение информации через чет- 4 ные элементы И 43-66 и соответствующие элементы ИЛИ 67-78. На выходах

19 устройства фиксируются коды чисел

1,3,2,4,5 соответственно.

Нижний уровень второго тактового импульса, пройдя через элемент 15 задержки, вызывает появление "1" на выходе элемента НЕ 37, в результате чего на выходах 19 устройства появляются коды чисел 4,2,3, 1,5 соответственно.

Верхний уровень шестого тактового импульса вызывает появление на выходах счетчиков 1 и 2 единичного потенциала. Сигнал с выхода счетчика 2 является старшим, он запирает элементы 31 и 33 запрета, проходит через элементы 32 запрета, открытый элемент И 8, элементы ИЛИ 22 и 20 и попадает на синхронизирующие входы разрядов регистров 38-4 1, что вызывает обмен информацией между ними. Единичный потенциал на выходе счетчика

2 одновременно вызывает опрокидывание Т-триггера 36, " 1" на выходе которого запрещает в дальнейшем прохождение сигнала через элемент 34 запрета и разрешает через элемент

И 35.

Нижний уровень шестого тактового импульса вызывает появление "1" на выходе элемента НЕ 37, что приводит к коммутации выходов регистров 3841 и получению очередной перестановки. Верхний уровень восьмого тактового импульса вызывает появление сигнала на выходе счетчика 1, который, пройдя через элемент И 35, элемент 33 запрета, элементы И 9, ИЛИ

24, вызывает обмен информацией между регистрами 39 и 4 1. Двенадцатый тактовый импульс вызывает обмен информацией между регистрами 39-42. После прихода 60 тактового импульса на выходе счетчика 4 появляется единичный потенциал, что свидетельствует об окончании работы устройства.

Если возникает необходимость увеличить число элементов в перестановках, то необходимо добавить соответствующее число разрядов, Каждый разряд, начиная с четвертого, содержит счетчик по модулю (P-1), где P— номер разряда, элемент И в первой и второй группах, элемент ИЛИ в первой и второй группах, элемент запрета, триггер, регистр. ф о р м у л а и з о б р е т е н и я

Устройство для перебора перестановок, содержащее п-1 счетчиков (n— число переставляемых элементов), группу триггеров, две группы элементов

И, три группы элементов ИЛИ, группу элементов ЗАПРЕТ, два элемента задержки, первый элемент ИЛИ и и регистров, причем выход первого элемента задержки соединен с первыми входами элементов И первой и второй групп и входом второго элемента задержки, выход которого соединен с первым входом пер1397933 ваго элемента ИЛИ, выход которогo соединен с нулевыми входами триггеров группы, выходы которых соединены с вторыми нходами элементов И пернай

5 группы, выходы которых соединены с первыми входами элементов ИЛИ первой группы, ныход i-ro элемента ИЛИ группы (i = 1,п-2) соединен с установочными входами i-го счетчика, установочные входы (п-1)-га счетчика соединен с вторым входом первого элемента ИЛИ, вторыми входами элементов

ИЛИ первой группы и входом установки исходного состояния устройства, выход признака окончания работы которого саединен.с выходом (и-1) -го счетчика, счетный вход j-ro счетчика (j =- 2,п-1) соединен с нчхацом переноса (j-1)-го счетчика. единичными входами триггеров группы и с входами соответствующих элементов ЗАПРЕТ группы, выход первого разряда первого счетчика соединен с вторым входом первого элемента И второй группы, второй вход

k-го элемента И которой (k = 2,п-2) соединен с выходом соответствующего элемента ЗАПРЕТ группы, втарой вход

<и-1)-ro элемента И второй группы соединен с выходом (n-2)-га счетчи30 ка, выходы элементов И второй группы соединены с первыми входами соответствующих элементов ИЛИ нтарай груп.пы, выход каждого нечетного элемента И второй группы соединен с соответствующими входами предыдущих не35 четных элементов ИЛИ второй группы, выход каждого четного элемента И второй группы, начиная с четвертого, соединен с соответствующим входом пре-40 дыдущих четных элементов ИЛИ второй группы, выходы элементов ИЛИ второй группы, выход каждого m-го (m = 1,п) элемента ИПИ которой соединен с син.хронходам m го и (m+1) Га регистран 45 вьгсоды разрядов каждого регистра соединены с входами одноименных разрядов предыдущего и последующего регистров, выходы элементов ИЛИ третьей группы и n-ro регистра являются информационными выходами устройства, 50 а т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит третий элемент задержки, Т-триггер, элемент НГ, первый и второй элементы ЗАПРЕТ, первый и второй элементы И, второй элемент ИПИ и n"1 групп элементов И, причем выход переноса первого счетчика соединен с первыми входами первых элементов

ЗАПРЕТ и И, вторые входы которых соединены с выходом Т-триггера, вход которого соединен с выходом переноса второго счетчика, выходы первых элементов ЗАПРЕТ и И соединены с третьим входом первого элемента ЗАПРЕТ груп" пы и первым нходом второго элемента

ЗАПРЕТ, остальные вхацы которого соединены с соответствующими выходами переноса счетчиков, выход второго элемента ЗАПРЕТ соединен с первым входом второго элемента И, второй нхад которого соединен с выходам первого элемента задержки, выход нтарого элемента И соединен с входом нторого элемента ИЛИ, выход которого соединен с синхровхадами нтарага и четвертага реггczpnн, наход первого элемента задержки соединен с входом третьего элемента задержки, выход которого сае, анен с входом элемента ПЕ, выход каторага соединен с первыми входаии нечетных элементов И с третьей па (и+1)-ю групп, первые входы четных элементов И которых соединены с ныходом третьего элемента задержки, выход каждого ра;ряда второго и четвертого регистров соединен с одним из входов разряда соответственна второго и четвертого регистров, выходы каждого разряда 1 † регистра (1 = in-1) соединены с вторыми входами четных элементов И 1-й группы и вторыми входами нечетных элементов

И (1+2) -й и (1-2) -й групп, выходы элементов И с третьей по (п+1)-ю групп соединены попарно с входами элементов ИЛИ третьей группы, счетный вход первого счетчика соединен с входом первого элемента задержки и тактовым входом устройства.

1397933

Составитель О. Береэикова

Редактор И.Николайчук Техред M.Õîäàíè÷ Корр е ктор А. Обр учар

Заказ 2272/48 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4