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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для построения вычислительных устройств,предназначенных , например, для автоматизированного решения задач конструирования радиоэлектронной и вычислительной аппаратуры. Целью изобретения является формирование последовательности сочетаний с постоянным и ми нимальным кодовым расстоянием по Хеммингу. Устройство содержит триггеры, .элементы И, элементы ИЛИ, элементы задержки, регистр сдвига, ключ 36, регистры, элемент И-ИЛИ, элемент коммутации. 1 ил.

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

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

РЕСПУБЛИК

2 Al (19) (11) (1) 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

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

Н А BTOPCKOMY СВИДЕТЕЛЬСТВУ (21) 4236221/24-24 (22) 24.03.87 (46) 30.09.88. Бюл. N 36 (72) А.В.Пришибской и Н.И.Пришибская (53) 681.3(088.8) (56) Авторское свидетельство СССР

М 634285, кл. G 06 F 15/32, 1975.

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

В 1262520, кл. G 06 F 15/20, 1985. (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для построения вычислительных устройств,предназначенных, например, для автоматизированного решения задач конструирования радиоэлектронной и вычислительной аппаратуры. Целью изобретения является формирование последовательности сочетаний с постоянным и минимальным кодовым расстоянием по Хеммингу. Устройство содержит триггеры, .элементы

И, элементы ИЛИ, элементы задержки, регистр сдвига, ключ 36, регистры, элемент И-ИЛИ, элемент коммутации.

1 ил.

1427382

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

Целью изобретения является форми- ip рование последовательности сочетаний с постоянным и минимальным кодовым расстоянием по Хеммингу.

На чертеже представлена функциональная схема устройства на четыре разряда (и = 4).

Устройство содержит триггеры 1-4, элементы И 5-15, элемент ИЛИ 16, элементы И 17-20, элементы ИЛИ 21-24, элементы задержки 25-28, элементы 2р

ИЛИ 29-32, регистр 33 сдвига, элементы 34, 35 задержки, ключ 36; элемент

ИЛИ 37, регистры 38-42, элементы И

43-49, 50.1-50.5, 51.1-51 5, 52.1 52 .5, 53. 1-53 .5, 54, 1-54,4, 55, 1- 25

55.5, 56.1-56.4, 57.1-57.4, 58.158.4, 59-64, элементы ИЛИ 65, 66, 67, 68.1-68.5, элемент И-ИЛИ 69, элементы ИЛИ 70-75, элементы 76-84 задержки, тактовый вход 85, вход 86 3р единичного уровня, элемент 87 коммутации, информационные выходы 88-91, выход 92 окончания перебора.

Наименьшим изменением в последовательных сочетаниях из п элементов по является замена одного элемента дру«35 гим. В терминах двоичных наборов это означает, что необходимо породить нсе и-разрядные наборы G(n, k), содержащие точно k единиц, так что последовательные наборы различаются ровно н двух разрядах (в одном нуль заменяется единицей, в другом единица нулем). В алгоритмическую основу устройства заложена рекурсивная процедура порождения сочетаний в порядке

45 минимального изменения, выводимого из дноично-отраженного и-разрядного кода Грея типа поиска с возвращением, в которой продвижение вперед и возвращение упрощаются за счет рекурсинной структуры бинарного дерева поиска.

В процессе порождения хранится путь из корня к текущему листу в виде текущего кодового слова (8„, д ), стек узлов g, G(i — 1, t) B Которое необходимо возвратиться, счетчик числа единичных .разрядов сре(, л. ди (g;,, g., ..., 8,), (г,, г

0< 8< g7 84

1 1 О О

4 3 4 5

2 О 1 1 О 2. 4 4 5

4 3 4 5

3 3 5 5

3 1 О 1 О

4 О О 1 1

5 О 1 О 1 2 5 4 5

5 3 4 5

6 1 О О 1 г„) — стек элементов, < — указатель вершины стека, Рассмотрим картину распределения памяти в устройстве. И триггера 1-4 хранится сочетание (g< 8, °, g„) н регистрах 3841 — (c,, с, ..., „), в регистре 33 — значение t н регистре

42 — значение i. Значения (г- <, о

< „), С, -1 хранятся в унитарном коде.

Устройство функционирует в соответствии со следующим аппаратным алгоритмом. о

1 . Начало работы алгоритма. Про-, РЪ изводим присвоения: t = k << 1 +

+ 1, i = О Переход к 2 о л

2 . Производим присвоения:

Л л, ° о — <, = i + 1. Переход к 3

3 . Если g; = 1, то переход к 4 о

В противном случае переход к 6

4 . Если t ф О, то g g<. В противном случае g;, = g; 1 . Переход к 5

5 . Производим присвоение: t t + о

+ 1. Переход к 8

6 . Если t g 1, тодь, = <. В противном случае g < = g«- . Переход к 7 ь

7 . Производим присвоение! t t— о

1 ° Переход к 8 о

8 . Производим присвоение: g;

= g;. Переход к 9

9 . Если й= -1 или С О, то

t = t + 1. В противном случае переход к 10 . Переход к 12

10 . Производим присвоения: t с; < = << . Переход к 11..

11 . Еслибы =О, то<, ° =1=1. В противном случае c.< = t + 1. Переход к 12

12 . Если ф и + 1, ся (g, я,, ..., g„) и переход к 1

В противном случае переход к 13

13 . Конец работы алгоритма.

Принцип работы устройства состоит в следующем. Рассмотрим пример формирования всех сочетаний для случая п4и1с=2.

14

Перед началом работы триггера 1-4, регистры 33, 38-42 устанавливаются в нулевое состояние. Затем в триггеры 1 и 2 записываются единицы, в регистр 33 записываются в унитарном коде значение t = k = 2 (01000), а в регистры 38-41 — в унитарном коде значения с, = i + 1, 1 i i < 4, ;

= k + 1, i = 1 (00100, 00100, 00010, 00001). При замыкании элемента 87 коммутации с входа 86 единичный потенциал поступает через элемент

ИЛИ 37 на входы элементов И 17-20 и, открывая их, обеспечивает поступление исходного сочетания 1100 на информационные выходы устройства. Единичный сигнал, пройдя элемент 34 задержки, открывает ключ 36 для прохождения тактового импульса с входа

85 на вход V регистра 42, что приводит к перезаписи содержимого регистра 38 в регистр 42. Длительность задержки 34 элемента определяется вре« менем считывания информации с инфор— мационных выходов устройства. Пройдя через элемент 80 задержки, длитель,ность задержки которого определяется временем перезаписи кодового слова иэ регистра 38 в регистр 42, импульс поступает на входы элементов И 54.

Так как элемент И 54.3 открыт единичныи потенциалом с выхода третьего разряда регистра 42, то, пройдя этот элемент, импульс поступает на входы элементов И 52, обеспечивая поступление информации с выходов регистра

40 через элементы И 52 и элементы

ИЛИ 68 на входы регистра 38. С выхода элемента 80 задержки импульс поступает через элемент ИЛИ 29 и элемент

76 задержки на-вход V регистра 38, раврешая перезапись информации из регистра 40 в регистр 38. Длительность задержки элемента 76 определяется временем выбора i-ro регистра из 38-41 и прохождения информации с выходов i-ro регистра на входы регистра 38. С выхода элемента И 54.3 импульс также поступает на элемент

78 задержки и, пройдя его, поступает через элемент ИЛИ 31 на вход Ч, а через элемент ИЛИ 66 — на вход D4 регистра 40, осуществляя запись в регистр 40 кодового слова 00010. Длительность задержки элемента 78 определяется временем выбора i-ro регистра и перезаписи информации из i-го регистра в регистр 38. С выхода эле27382

4 мента И 54.3 импульс также поступает на входы элементов И 7 и И 11, и так как элемент И 11 открыт единичным

5 потенциалом с инверсного выхода триггера 3, импульс проходит через открытый элемент И 11 и через элемент

ИЛИ 71 поступает на входы элементов

И 56. Так как элемент И 56.2 открыт единичным потенциалом с выхода третье го разряда регистра 33, то, пройдя через открытый элемент И 56.2, импульс через элемент ИЛИ 21 поступает на вход Т триггера 1, осуществляя его переброску в нулевое состояние.

Импульс с выхода элемента ИЛИ 71, проходя через элемент 84 задержки и элементы ИЛИ. 75, 74, поступает на входы S С с регистра 33, осуществляя уменьшение значения t = 2 (записанное в унитарном коде в регистре 33) на 1. Длительность задержки элемента 84 определяется временем опрокидывания триггера 1-4 ° С выхода

25 элемента И 54.3 импульс также поступает через элемент 27 задержки (длительность задержки определяется временем прохождения импульса через четыре логических элемента и переброса триггера) и через элемент ИЛИ 23 на вход Т триггера 3, осуществляя его переброс в единичное состояние.

На этом оканчивается процесс формирования основной информации g, но продолжается процесс формирования дополнительной информации в регистрах

Поэтому с выхода элемента 80 задержки импульс, пройдя элемент 35 задержки (длительность задержки опре40 деляется интервалом времени от момента поступления импульса на входы элементов И 54 до момента окончания процесса формирования основной информации в триггерах), через элемент

ИЛИ 37 поступает на входы элементов

И 17-20 и, открывая их, обеспечивает поступление очередного полученного сочетания 0110 на информационные выходы устройства. Одновременно с выхода элемента 35 задержки поступает на входы элементов И 60 и 63. Так как (г. = 1) (— 1 = (t — 1) Ф О, то элемент И 63 открыт нулевым потенциалом с выхода элемента

И-ИЛИ 69. Элемент И 44 открыт единичными потенциалами, поступающими с единичного выхода триггера 2 и выхода третьего разряда регистра 42, поэтому единичный потенциал с выхо1427382 да элемента И 44 проходит через элемент ИЛИ 72 и поступает на вход элемента И 59. Поэтому импульс с выхода элемента И 63, пройдя через открытый элемент И 59, поступает через элемек5 ты ИЛИ 75, 73 на входы S„, С с регистра 33, уменьшая значение t 1 на 1. Одновременно импульс поступает на входы элементов И 50 и открывает их, разрешая поступление информации с выходов регистра 38 на входы регистров 39-41 ка входы элементов

И 47-49, осуществляя выбор (i-1)-го регистра. Так как элемент И 47 открыт единичным потенциалом с выхода третьего разряда регистра 42, то импульс, пройдя его, через элемент

ИЛИ 30 поступает на вход V регистра

39, разрешая перезапись информации из регистра 38 в регистр 39. С выхода элемента И 63 импульс также проходит через элемент 82 задержки (длительность задержки определяе гся временем перезаписи информации из регистра 38 в регистр 39) и поступает на входы элементов И 61 и 64.

Так как t = О, а следовательно, элемент И 61 открыт единичным потенциалом с выхода первого разряда регистра 33, то импульс проходит через элемент И 61 и поступает на входы элементов И 58. Одновременно импульс с выхода элемента 82 задержки проходит через элемент ИЛИ 29 и элемент

76 задержки на вход V регистра 38, разрешая перезапись сдвинутой на один разряд в сторону младшего разряда информации из регистра 42 в регистр 38, На этом процесс формирования дополнительной информации в

40 регистрах, i, t оканчивается. Ре-, гистры содержат при этом следующие кодовые слова — 01000, 00010, 00010, 00001. После формирования последнего сочетания 1001 в регистрах ь будут содержаться следующие кодовые слова — 00001, 00100, 00010, 00001, поэтому элемент И 62 будет открыт единичным потенциалом с выхода последнего разряда. регистра 38 следовательно, импульс с выхода элемента

82 задержки, пройдя через элемент 81 задержки и элемент И 62, поступит на выход 92 окончания перебора. Длительность задержки элемента 81 опре- 55 деляется временем перезаписи информаиии из регистра 42 в ре гистр 38 . Этим завершается процесс перебора вс сх с оч ета ний иэ к 4 по k = 2.

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

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

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

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

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

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

j-ro (j = t ..., n + 1) элемента И третьей группы соединен с 1-м разрядным выходом регистра сдвига, второй вход i-го элемента И четвертой группы соединен с (i + 1)-м разрядным выходом регистра сдвига, .выход (i+1)-ro элемента И третьей группы подключен к первому входу i-ro элемента ИЛИ первой группы, выход (a + 1)-го (1с1, ..., п — 1) элемента И четвертой группы подключен к второму входу

1427382

k-го элемента ИЛИ первой группы, выходы первых элементов И третьей и четвертой групп через четвертый элемент ИЛИ подключены к первым входам элементов И пятой группы, выход k-го

5 элемента И пятой группы подключен к третьему входу k-го элемента ИЛИ первой группы, единичный выход i-ro триггера подключен к первым входам д-х элементов шестой и седьмой групп выходы элементов И шестой группы через пятый элемент ИЛИ подключены к первому входу первого элемента И,выход которого подключен к первым входам шестого и седьмого элементов

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

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

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

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

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

1-му разрядному информационному входу первого регистра, j-й разрядный выход

i-ro регистра подключен к первому входу j-го элемента И (i + 8)-й груп40 пы, j;A разрядный информационный вход (k+1)-ro регистра, кроме (k + 2)-ro разряда, соединен с выходом j-ro элемента И .девятой группы,(k + 2)-й разрядный информационный вход (k + 1)-го 45 регистра соединен с выходом k-го элемента ИЛИ третьей группы, j-й разрядный выход первого регистра подключен к j-му разрядному информационному входу (n + 1)-ro регистра, i-й разрядный 50 выход которого соединен с первым входом i-ro элемента И (и + 9)-й группы, вторые входы элементов И (и + 9)-й группы подключены к выходу второго элемента задержки, выход i-ro элемен- 55 та И (n + 9)-й группы подключен к вторым входам i-х элементов И первой и второй групп и к входу i-го элемента задержки первой группы, выход

k-rn элемента задержки первой группы подключен к четвертому входу k-ro элемента KIH первой группы, выход и-го элемента задержки первой группы подключен к второму входу и-ro элемента ИЛИ первой группы, выход (k +

+ 1)-го элемента И (n + 9)-й группы подключен к вторым входам всех, кроме (n + 2)-го, элементов И (k + 9)-й группы и через k-й элемент задержки второй группы — к первым входам k-x элементов ИЛИ третьей и четвертой групп, второй вход k — го элемента ИЛИ третьей группы подключен к выходу (k + 2}-ro элемента И девятой группы, второй вход k-ro элемента ИЛИ четвертой группы подключен к выходу (n + 2)-го элемента И (k + 8)-й группы, 1-й разрядный выход регистра сдвига подключен к первому входу 1-й группы элемента И-ИЛИ, (k + 1}-й разрядный выход (n + 1)-го регистра подключен к второму входу k-ro элемента

И пятой группы и к первому входу (n+

+ 2)-ro элемента И (k + 8)-й группы, (i + 1)-й разрядный выход (n + 1)-ro. регистра подключен к второАу входу

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

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

Составитель В.Байков

Техред М.Ходанич, Редактор О.Спесивых

Корректор M.Васильева

Заказ 4854/46

Тираж 704 Подписное

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

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

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

9 1427382 10 вторым входам всех элементов И (n + задержки подключен к управляющему

+ 10)- и группы, выход пятого элемен- входу записи первого регистра, выход та И подключен к вторым входам всех ключа соединен с управляющим входом элементов И восьмой группы выход

У

5 записи (n + 1) -го регистра выход

У первого элемента И (n + 10)-й группы первого элемента ИЛИ соединен с соединен с первым входом первого эле- вторыми входами всех элементов И мента ИЛИ второй группы, j-и разряд- седьмой группы, выходы которых являный выход (k + 1)-го регистра подклю- ются информационными выходами устчен к (k + 1)-му входу j ãî элемента 10 ройства, выход шестого элемента ваИЛИ второй группы, выход (k + 1)-го держки через восьмой элемент зацержэлемента И (n + 10)-й группы подклю- ки соединен с первым входом шестого чен к (n + 1)-му входу (k + i)-го элемента И, второй вход которого подэлемента ИЛИ второй группы, выход ключен к (n + 1)-му разрядному выхоk-го элемента ИЛИ четвертой группы ду первого регистра выход

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