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

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

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

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

Устройство содержит триггеры 1-4, элементы И 5-15, элемент ИЛИ 16, элементы И 17-20, элементы ИЛИ 21-24, элементы задержки 25-28, элементы ИЛИ 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- 55.5, 56.1-56.4, 57.1-57.4, 58.1- 58.4, 59-64, элементы ИЛИ 65, 66, 67, 68.1-68.5, элемент И-ШШ 69, элементы ИЛИ 70-75, элементы 76-84 задержки, тактовый вход 85, вход 86 единичного уровня, элемент 87 коммутации, информационные выходы 88-91, выход 92 окончания перебора.

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

в которой продвижение вперед и возвра

щение упрощаются за счет рекурсивной

структуры бинарного дерева поиска. В -процессе порождения хранится путь из корня к текущему листу в виде те- куп;его кодового слова (gr,, gn-( gj), стек узлов g;G(i - 1, t), в ко- торое необходимо возвратиться, t - счетчик числа единичных .разрядов сре- ди (g;., , 8м , ..., g,), ( 6, , 2- ,

..., „ ) - стек элементов, ;., - указатель вершины стека. Рассмотрим картину распределения памяти в устройстве. В триггера 1-4 хранится сочетание (g4, В7 ёп) в регистрах 38-41 - (t,, , , ...,€„), в регистре 33 - значение t, в регистре 42 - значение i. Значения (t,, t-i , ..., ) i хранятся в унитарном коде.

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

1 . Начало работы алгоритма. Про-,

изводим присвоения: t k, + 1, i 0. Переход к 2°.

k +

Zt - t-i.

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

/.

i + 1. Переход к 3

3. Если gj 1, то переход к 4 , В противном случае переход к 6 ,

4. Если t т О, то g gf противном случае g ;- g. . Переход

к 5° .

5°. Производим присвоение: t - t + + 1. Переход к 8.

6°. Если t т 1, то gt-1 gt-1 . В

противном случае g i-i к 7.

; Переход

Производим присвоение

О

t 1. Переход к 8 У

В.;

Производим присвоение Переход к 9 .

g

9 . Если t 1 - 1 или t О, то t t + 1. В противном случае переход к 10°. Переход к 12.

Ю. Производим присвоения: t t - g ;(,, Si . Переход к 11..

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

12°. Если i / п + 1, то выводится (g,, g,,,, ..., gn) и переход к 1°. В противном случае переход к 13 .

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

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

Перед началом работы триггера 1-4 регистры 33, 38-42 устанавливаются в нулевое состояние. Затем в триггеры 1 и 2 записываются единицы, в регистр 33 записываются в унитарном коде значение t k 2 (01000), а в регистры 38-41 - в унитарном коде значения с , i+ 1, 1 164, ; k + 1, i 1 (00100, 00100, 00010, 00001), При замыкании элемента 87 коммутации с входа 86 единичный по- теш:1иап поступает через элемент ИЛИ 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 и прохождения информации с выходов -го регистра на входы регистра 38. С выхода элемента И 54.3 импульс также поступает на элемент 78 задержки и, пройдя его, поступает

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

5

0

5

0

5

0

5

0

мента И 54.3 импульс также поступает на входы элементов И 7 и И 11, и так как элемент И 11 открыт единичным потенциалом с инверсного выхода триггера 3, импульс проходит через открытый элемент И 11 и через элемент ИЛИ 71 поступает на входы элементов И 56. Так как элемент И 56.2 открыт единичным потенгщалом с выхода третье го разряда регистра 33, то, пройдя через открытый элемент И 56.2, импульс через элемент ИЛИ 21 поступает на вход Т триггера 1, осуществляя его переброску в нулевое состояние. Импульс с выхода элемента ИЛИ 71, проходя через элемент 84 задержки и элементы ИЛИ. 75, 74, поступает на входы S , С с регистра 33, осуп(еств- ляя уменьшение значения t 2 (записанное в унитарном коде в регистре 33) на 1. Дпительность задержки элемента 84 определяется временем опрокидывания триггера 1-4. С выхода элемента И 54.3 импульс также поступает через элемент 27 задержки (длительность задержки определяется временем прохождения импульса через четыре логических элемента и переброса триггера) и через элемент ИЛИ 23 на вход Т триггера 3, осуществляя его переброс в единичное состояние. На этом оканчивается процесс формирования основной информации g, но продолжается процесс формирования дополнительной информации в регистрах & , i, t. Поэтому с выхода элемента 80 задержки импульс, пройдя элемент 35 задержки (длительность задержки определяется интервалом времени от момента поступления импульса на входы элементов И 54 до момента окончания процесса формирования основной информации в триггерах), через элемент ИЛИ 37 поступает на входы элементов И 17-20 и, открывая их, обеспечивает поступление очередного полученного сочетания 0110 на информационные выходы устройства. Одновременно с выхода элемента 35 задержки поступает на входы элементов И 60 и 63. Так как (t 1) (1 - 1 2) и (t 1) / О, то элемент И 63 открыт нулевым потенциалом с выхода элемента И-ИЛИ 69. Элемент И 44 открыт единичными потенциалами, поступающими с единичного выхода триггера 2 и выхода третьего разряда регистра 42, поэтому единичный потенциал с выхода элемента И 44 проходит через элемент HJM 72 и поступает на вход элемента И 59. Поэтому импульс с выхода элемента И 63, пройдя через открытый элемент И 59, поступает череэ элементы ИЛИ 75, 73 на входы S, С с регистра 33, уменьшая значение t 1 на 1, Одновременно импульс поступает на входы элементов И 50 и открывает их, разрешая поступление информации с выходов регистра 38 на входы ре- гистров 39-41 на входы элементов И 47-49, осуществляя выбор (i-l)-ro регистра. Так как элемент И 47 открыт единичным потенциалом с выхода третьего разряда регистра 42, то импульс, пройдя его, через элемент ИЛИ 30 поступает на вход V регистра 39, разрешая перезапись информации из регистра 38 в регистр 39, С выхода элемента И 63 импульс также проходит через элемент 82 задержки (длительность задержки определяется временем перезаписи информации из регистра 38 в регистр 39) и поступает на входы элементов И 61 и 64. Так как t О, а следовательно, элемент И 61 открыт единичным потенциалом с выхода первого разряда регистра 335 то импульс проходит через элемент И 61 и поступает на входы элементов И 58. Одновременно импульс с выхода элемента 82 задержки проходит через элемент ИЛИ 29 и элемент 76 задержки на вход V регистра 38, разрешая перезапись сдвинутой на один разряд в сторону младшего разряда информации из регистра 42 в регистр 38, На этом процесс формирования дополнительной информации в регистрах , i, t оканчивается. Регистры IT содержат при этом следующие кодовые слова - 01000, 00010, 00010, 00001, После формирования последнего сочетания 1001 в регистрах будут содержаться следующие кодовы слова - 00001, 00100, 00010, 00001, поэтому элемент И 62 будет открыт единичным потенциалом с выхода последнего разряда, регистра 38, следовательно, импульс с выхода элемента 82 задержки, пройдя через элемент 81 задержки и элемент И 62, поступит на выход 92 окончания перебора. Длительность задержки элемента 81 определяется временем перезаписи информации из регистра 42 в регистр 38 . Этим завершается

процесс Г еребора всех НИИ из п 4 по 2.

соч ета

0

5

0

5

0

5

0

5

0

5

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

Устройство для перебора сочетаний, содержащее п триггеров (п - число перебираемых элементов), первый элемент ИЛИ, первую группу элементов ИЛИ, первую, вторую, третью и четвертую группы элементов И, регистр сдвига, первый и второй элементы задержки, первую группу элементов задержки,ключ и элемент коммутации, причем выход i-ro (i 1, ..., n) элемента ИЛИ первой группы подключен к счетному входу i-ro триггера, единичный и нулевой выходы i-ro триггера подключены к первым входам i-x элементов И первой и второй групп соответственно, первый вход первого элемента ИЛИ и вход первого элемента задержки через элемент коммутации соединены с входом единичного уровня устройства, выход первого элемента задержки подключен к управляющему входу ключа, информационный вход ключа является тактовым входом устройства, выход ключа соединен с вход: М второго элемента задержки, отличающееся тем, что, с целью формирования последовательности сочетаний с постоянным и минималь-. ным -кодовым расстоянием по Хэммингу, оно содержит элементы ИЛИ с второго по девятый, шесть элементов И, вторую, третью и четвертую группы элементов ИЛИ, группы с пятой по (10 + п)-ю элементов И, п + 1 регистров, элементы задержки с третьего по врсьмой, вторую группу элементов задержки, элемент И-ИЛИ, причем выходы элементов И первой и второй групп подключены соответственно к входам второго и третьего элементов ИЛИ, выходы второго и третьего элементов РШИ подключены к первым входам элементов И третьей и четвер- той групп соответственно, второй вход j-ro (, ...,n+1) элемента И третьей группы соединен с j-м разрядным выходом регистра сдвигаj второй вход i-ro элемента И четвертой группы соединен с (i + 1)-м разрядным выходом регистра сдвига, выход (1+1)-го элемента И третьей группы подключен к первому входу i-ro элемента ИЛИ первой группы, выход (k + 1)-го (k 1, ,.., п - 1) элемента И четвертой группы подключен к второму входу

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

5

0

Q 5 0 5

0

5

0

5

Га задержки первой группы, выход k-ro элемента задержки первой группы подключен к четвертому входу k-ro элемента ИЛИ первой группы, выход п-го элемента задержки первой группы подключен к второму входу п-го элемента ИЛИ первой группы, выход (k + 1)-го элемента И (п + 9)-й группы подключен к вторым входам всех, кроме (п + 2)-го, элементов И (k + 9)-й группы и через k-й элемент задержки второй группы - к первым входам k-x элемент-ов ИЛИ третьей и четвертой групп, второй вход k-ro элемента ИЛИ третьей группы подключен к выходу (k + 2)-го элемента И девятой группы, второй вход k-ro элемента ИЛИ четвертой группы подключен к вьгходу (п + 2)-го элемента И (k + 8)-й группы, j-й разрядный выход регистра сдвига подключен к первому входу j-й группы элемента И-ИЛИ, (k + 1)-й разрядный выход (п + 1)-го регистра подключен к второму входу k-ro элемента И пятой группы и к первому входу (п+ + 2)-го элемента И (k + 8)-и группы, (i + 1)-й разрядный выход (п + 1)-го- регистра подключен к второйу входу i-ro элемента.И шестой группы, к первому входу i-ro элемента И (п + 10)-и группы и к второму входу (i + 1)-й группы элемента И-ИЛИ, выход второго элемента задержки подключен к первому входу девятого элемента ШШ и через пятый элемент задержки - к второму входу первого элемента ИЛИ, к первому входу второго элемента И и к прямому входу третьего элемента И, второй вход второго элемента И и инверсный вход третьего элемента И подключены к выходу элемента И-ИЛИ, выход второго элемента И подключен к четвертому входу шестого элемента ИЛИ и к второму входу восьмого элемента ИЛИ, выход третьего элемента И подключен к второму входу первого элемента И, к вторьпч входам всех элементов И девятой группы, к вторым входам (п + 2)-х элементов И групп с десятой по (п + 7)-ю, к входу шестого элемента задержки, выход которого подключен к первому входу четвертого элемента И и к прямому входу пятого элемента И, второй вход четвертого элемента И и инверсный вход пятого элемента И подключены к первому разрядному выходу регистра сдвига, выход четвертого элемента И подключен к

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

0

5

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

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