Устройство для перебора перестановок Советский патент 1988 года по МПК G06F15/20 

(Л

вход 17 установки исходного состояния, тактовый вход 18, информационные выходы 19, группу элементов ИЛИ 20-23, элемент ИЛИ 24, элементов ИЛИ 25-27, триггеры 28-30, группу элементов запрета 31-32, элементы запрета 33,34, элемент И 35,

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

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

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

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

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

Устройство содержит счетчики 1-4, ;1ричем счетчик 1 - по mod 2, счетчик 2 - го 3, счетчик 3 - по mod 2, счетчик 4 - по mod 3, группу элемен- тов И 5-8, элемент И 9, группу эле- И 10-12, элементы 13-15 задержки, элемент ИЛИ 16, вход 17 установки исходного состояния, тактовый вход 18, информадионные выходы 19, группу элементов RTll 20-23, элемент ИЛИ 24, группу элементов ИЛИ 25-27, триггеры 28-30, группу элементов 31 и 32 запрета, элементы 33 и 34 запрета, элемент И 35, Т-триггер 36, элемент НЕ 37, регистры 38-42, группы 43г48, 49-54, 55-60, 61-66 элементов И, груг пу элементов ИЛИ 67-78, синхронизирующие входы 79-81 разрядов регистров, входы 82-84 разрядов регистров, выход 85 разряда регистра, элементы И 86 и 87,элементы ИЛИ 88 и 89, D- триггер 90 и элемент И 91.

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

Каждая очередная перестановка получается из предыдущей путем обмена элементами (кодами) между соответствующими позициями по строго опр

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

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

25

30

35

Стрелки показывают в каких позициях происходит смена элементов. После каждой перестановки формируется зеркальное отображение первых четырех элементов. Из приведенной последовательности видно, что обмен элементов, 1СТОЯЩИХ в первой и во второй позициях, происходит через одну перестановку, а элементов, стоящих в третьей и четвертой позициях, через шесть перестановок. В первых шести перестановках обмен элементов, стоящих во второй и третьей позициях, происходит через одну перестановку, а в следующих шести перестановках обмен элементов, стоящих во второй и третьей позициях, не происходит, а происходит через одну перестановку обмен элементов, стоящих во второй и четвертой позициях. Смена элементов, стоя- п(их в двух старщих позициях, влечет за собой смену элементов между всем1ч парами всех младшкх позиций. Это хорошо видно из приведенного примера. Когда через шесть перестановок происходит обмен элементов, находящихся в третьей и четвертой позициях, то одновременно должен происходить обмен элементов, стоящих в первой и второй позициях. Когда старшими при обмене являются первая и вторая, вторая и третья, вторая и четвертая позивди то они не вызывают обмена парами младших позиций, поскольку таковых просто нет.

Приведенное правило легко применяется на большее число элементов с непременным условием, что после каждой перестановки элементов в ячейках регистров зеркальному отображению подвергаются только первые четыре младших разряда, а старшие разряды остаются нетронутыми. Так, обмен элементов, находящихся в четвертой и пятой позициях, происходит через 12 перестановок, в пятой и шестой позициях через 60 перестановок. В конечном счете такая смена элементов, стоящих

в N и N-1 позициях происходит через (N-1)1/2 перестановок. На основании сказанного можно, например, подсчитать, что после 60-й перестановки, т.е. для получения 61-й перестановки, должна происходить смена элементов в первой и второй, третьей и четвертой, пятой и шестой позициях, т.е.

6 о 61

123456 432156 431265

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

0

5

0

5

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

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

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

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

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

5 НЕ 37 присутствует логическая 1, которая разрешает прохождение информации, поступающей от регистров 38- 41, через нечетные элементы И 43-66, элементы ИЛИ 67-78 на информационные выходы 19 устройства, на которых фиксируются коды чисел 4,3,1,2,5 соответственно. Верхний уровень тактового импульса, поступающего на вход устройства 18, вызывает появление на выходе первого разряда счетчика 1 епиничного потенциала, который, пройдя через открытый элемент И 5, одновременно на первый вход которого подается задержанный первый импульс, через элемент Ш1И 20 попадает на синхронизирующие входы 79 и 82 разрядов регистра 38 и синхронизирующие входы 79 разрядов регистра 39, что приводит к обмену информацией между

g регистрами 38 и 39. Задержанный первый импульс вызьгаает появление логического О на выходе элемента НЕ 37, который запрещает прохождение информации, поступающей с выходов раз0

0

5

0

5

рядов регистров 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. О с выхода элемента 15 задержки запрещает прохождение информации через четные элементы И 43-66.На выходах 19 устройства фиксируются коды чисел 4,3,2,1,5 соот- ретствеино.

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

Нижний уровень второго тактового

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

Верхний уровень шестого тактового импульса вызывает появление на выходах счетчиков 1 и 2 единичного

0

Qj

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

Нижний уровень шестого тактового импульса вызывает появление 1 на выходе элемента НЕ 37, что приводит к коммутации выходов регистров 38- 41 и получению очередной перестановки. Верхний уровень восьмого тактового импульса вызывает появление сигнала на выходе счетчика 1, кото- 5 рый, пройдя через элемент И 35, элемент 33 запрета, элементы И 9, ИЛИ 24, вызывает обмен информацией между регистрами 39 и 41. Двенадцатый тактовый импульс вызывает обмен информацией между регистрами 39-42. После прихода 60 тактового импульса на выходе счетчика 4 появляется единичный потенциал, что свидетельствует об окончании работы устройства.

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

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

Устройство для перебора перестановок, содержащее п-1 счетчиков (п 0

5

0

45

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

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

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

соединен с соответствующим входом но второго и четвертого регистров.

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

45

50

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

5 0 5

0

5

с целью повышения быстродействия, оно содержит третий элемент задержки, Т-триггер, элемент ПК, первый и второй элементы ЗАПРЕТ, первый и второй элементы И, второй элемент ИЛИ и п-1 групп элементов И, причем выход переноса первого счетчика соединен с первыми входами первых элементов ЗАПРЕТ и И, вторые входы которых сое-, динены с выходом Т-триггера, вход ко- торого соединен с выходом переноса второго счетчика, выходы первых элементов ЗАПРЕТ и И соединены с третьим входом первого элемента ЗАПРЕТ группы и первым входом второго элемента ЗАПРЕТ, остальные входы которого соединены с соответствующими выходами переноса счетчиков, выход второго элемента ЗАПРЕТ соединен с первым входом второго элемента И, второй вход которого соединен с выходом первого элемента задержки, выход второго элемента И соединен с входом второго элемента ИЛИ, выход которого соединен с синхровходами второго и четвертого pers cipoB, выход первого элемента задержки соединен с входом третьего элемента , выход которого с входом элемента НЕ, выход которого соединен с первыми входаг-ш нечетных элементов И с третьей по (п+1)-ю групп, первые входы четных элементов И которых соеди- нень с выходом третьего элемента задержки, выход каждого ра .ряда второго и четвертого регистров соединен с одним из входов разряда соответствен Q но второго и четвертого регистров.

45

50

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

92 8f 83

Фиа.З

Фие.2.

SZ S3

г-О-О

7

9S

Фиг