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

(51)4 С 0 ОПИСАНИЕ ИЗОБРЕТЕН а й А) УСТРОЙСТВО РЕБОРА СОЧ 7) Изо тике и ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ ВТОРСКОМУ С 8 ИДЕТЕЛЬСТВ(56) Авторское свидетельство СССРВ 634285, кл. С 06 Р 15/32, 1975.Авторское свидетельство СССРВ 1262520, кл. С 06 Р 15/20, 1985 етение относится к автомислительной технике и м жет быть использовано для построениявычислительных устройств,предназначенных, например, для автоматизированного решения задач конструирования радиоэлектронной и вычислительноаппаратуры. Целью изобретения является формирование последовательностисочетаний с постоянным и минимальнымкодовым расстоянием по Хеммингу. Устройство содержит триггеры, .элементыИ, элементы ИЛИ, элементы задержки,регистр сдвига, ключ 36, регистры,элемент И-ИЛИ, элемент коммутации.1 ил.Изобретение относится к областиавтоматики и вычислительной техникии может быть использовано для построе.ния вычислительных устройств, предназначенных, например, для антоматизированного решения задач конструирования радиоэлектронной и вычислительной аппаратуры,Целью изобретения является форми Орование последовательности сочетанийс постоянным и минимальным кодовымрасстоянием по Хеммингу,На чертеже представлена функциональная схема устройства на четыре 15разряда (и = 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.152 .5, 53. 1-53 .5, 54 . 1-54 .4, 55. 1- 2555.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 ЗОединичного уровня, элемент 87 коммутации, информационные выходы 88-91,выход 92 окончания перебора,Наименьшим изменением н последовательных сочетаниях из п элементов по1 с является замена одного элемента дру 35гим. В терминах двоичных наборов этоозначает, что необходимо породить нсеи-разрядные наборы С(п, К) содержащие точно к единиц, так что последовательные наборы различаются ровнон двух разрядах (в одном нуль заменяется единицей, в другом единица нулем). В алгоритмическую основу устройства заложена рекурсивная процедура порождения сочетаний в порядке45минимального изменения, выводимогоиз дноично-отраженного и-разрядногокода Грея типа поиска с возвращением,в которой продвижение вперед и возвращение упрощаются за счет рекурсиннойструктуры бинарного дерева поиска.В процессе порождения хранится путьиз корня к текущему листу в виде текущего кодового слова (8 К0 К 87 84 1 1 0 О 4 3 4 5 2 0 1 1 0 2 4 4 5 4 3 4 5 3 3 5 5 3 1 0 1 0 4 0 0 1 1 5 0 1 0 1 2 5 4 5 5 3 4 5 6 1 0 0 1 лг) - стек элементов, : - указатель вершины стека, Рассмотрим картину распределения памяти в устройстве. И триггера 1-4 хранится сочетание (8 8 , ) н регистрах 38-41 - (, гг ) в регистре 33 - значениен регистре 42 - значение . Значения (, ), й - хранятся в унитарном коде.Устройство функционирует в соответствии со следующим аппаратным алгоритмом.о1, Начало работы алгоритма. Про-,фи изводим присвоения: С = 1 г1 + + 1, 3. = О. Переход к 2ол2 . Производим присвоения; 1 гЛ л,о., ,; = 1+ 1. Переход к 33, Если 8; = 1, то переход к 4о В противном случае переход к 64 , Если СО, то 8ЦВ противном случае 8;= 8;, . Переход к 55 . Производим присвоение: й С +о+ 1. Переход к 86 . Если С 1 1, то ць- = 3В противном случае 8, = я- . Переход к 7ь7 . Производим присвоениеф Сй -о1Переход к 8о8 . Производим присвоение; = я 1. Переход к 99. Если й =- 1 или С ф О, то= С + 1. В противном случае переход к 10. Переход к 1210 . Производим присвоения й щс;= А . Переход к 1111 . Еслибы =О, то = 1= 1. В противном случае 1 =+ 1. Переход к 1212 . Если 1 Ф и + 1, то ВыВодится (8 К , 8) и переход к 1 В противном случае переход к 1313 . Конец работы алгоритма.Принцип работы устройства состоит в следующем. Рассмотрим пример формирования всех сочетаний для случая и 4 И 1 с=2.314Перед началом работы триггера 1-4, регистры 33, 38-42 устанавливаются в нулевое состояние, Затем в триггеры 1 и 2 записываются единицы, в регистр 33 записываются в унитарном коде. значение с = 1 с = 2 (01000), а в регистры 38-41 - в унитарном коде значения с, = 1 + 1, 1 с 1 с 4, с; = 1 с + 1, 1 = 1 (00100, 00100, 00010, 00001). При замыкании элемента 87 коммутации с входа 86 единичный потенциал поступает через элемент ИЛИ 37 на входы элементов И 17-20 и, открывая их, обеспечивает поступление исходного сочетания 1100 на информационные выходы устройства. Единичный сигнал, пройдя элемент 34 задержки, открывает ключ 36 для прохождения тактового импульса с входа 85 на вход Ч регистра 42, что приводит к перезаписи содержимого регистра 38 в регистр 42, Длительность задержки 34 элемента определяется временем считывания информации с инфор - мационных выходов устройства. Пройдя через элемент 80 задержки, длитель,ность задержки которого определяется временем перезаписи кодового слова иэ регистра 38 в регистр 42, импульс поступает на входы элементов И 54. Так как элемент И 54.3 открыт единичныи потенциалом с выхода третьего разряда регистра 42, то, пройдя этот элемент, импульс поступает на входы элементов И 52, обеспечивая поступление информации с выходов регистра 40 через элементы И 52 и элементы ИЛИ 68 на входы регистра 38. С выхода элемента 80 задержки импульс поступает через элемент ИЛИ 29 и элемент 76 задержки на вход Ч регистра 38, раврешая перезапись информации из регистра 40 в регистр 38. Длительность задержки элемента 76 определяется временем выбора -го регистра из 38-41 и прохождения информации с выходов 1-го регистра на входы регистра 38, С выхода элемента И 54.3 импульс также поступает на элемент 78 задержки и, пройдя его, поступает через элемент ИЛИ 31 на вход Ч, а через элемент ИЛИ 66 - на вход Р 4 регистра 40, осуществляя запись в регистр 40 кодового слова 00010. Длительность задержки элемента 78 определяется временем выбора -го регистра и перезаписи информации из. 1-го регистра в регистр 38, С выхода эле 273824мента И 54,3 импульс также поступаетна входы элементов И 7 и И 11, и таккак элемент И 11 открыт единичным 5потенциалом с инверсного выхода триггера 3, импульс проходит через откры"тый элемент И 11 и через элементИЛИ 71 поступает на входы элементовИ 56. Так как элемент И 56.2 открытединичным потенциалом с выхода третьего разряда регистра 33, то, пройдячерез открытый элемент И 56.2, импульс через элемент ИЛИ 21 поступает на вход Т триггера 1, осуществляяего переброску в нулевое состояние.Импульс с выхода элемента ИЛИ 71,проходя через элемент 84 задержки иэлементы ИЛИ. 75, 74, поступает навходы Б С с регистра 33, осуществляя уменьшение значения Т = 2 (записанное в унитарном коде в регистре 33) на 1. Длительность задержкиэлемента 84 определяется временемопрокидывания триггера 1-4С выхода 25 элемента И 54.3 импульс также поступает через элемент 27 задержки (длительность задержки определяется временем прохождения импульса черезчетыре логических элементаи переброса триггера) и через элемент ИЛИ 23на вход Т триггера 3, осуществляяего переброс в единичное состояние,На этом оканчивается процесс формирования основной информации 8, но продолжается процесс формирования дополнительной информации в регистрах1, С. Поэтому с выхода элемента 80задержки импульс, пройдя элемент 35задержки (длительность задержки определяется интервалом времени от момента поступления импульса на входы элементов И 54 до момента окончания процесса формирования основной информации в триггерах), через элементИЛИ 37 поступает на входы элементовИ 17-20 и, открывая их, обеспечиваетпоступление очередного полученногосочетания 0110 на информационные выходы устройства. Одновременно с выхода элемента 35 задержки поступаетна входы элементов И 60 и 63, Таккак (г.=1)(-1=2) и (с- 1) Ф О, то элемент И 63 открыт нулевым потенциалом с выхода элементаИ-ИЛИ 69. Элемент И 44 открыт единичными потенциалами, поступающимис единичного выхода триггера 2 и выхода третьего разряда регистра 42,поэтому единичный потенциал с выхо 1427382да элемента И 44 проходит через элемент ИЛИ 72 и поступает на вход элемента И 59. Поэтому импульс с выхода элемента И 63, пройдя через открытый элемент И 59, поступает через элемек 5 ты ИЛИ 75, 73 на входы Б, С с регистра 33, уменьшая значение1 на 1. Одновременно импульс поступает на входы элементов И 50 и открывает их, разрешая поступление информации с выходов регистра 38 на входы регистров 39-41 ка входы элементов И 47-49, осуществляя выбор (-1)-го регистра, Так как элемент И 47 открыт единичным потенциалом с выхода третьего разряда регистра 42, то импульс, пройдя его, через элемент ИЛИ 30 поступает на вход Ч регистра 39, разрешая перезапись информации из регистра 38 в регистр 39, С выхода элемента И 63 импульс также проходит через элемент 82 задержки (длительность задержки определяегся временем перезаписи информации из регистра 38 в регистр 39) и поступает на входы элементов И 61 и 64Так как С = О, а следовательно, элемент И 61 открыт единичным потенциалом с выхода первого разряда регистра 33, то импульс проходит через элемент И 61 и поступает на входы элементов И 58. Одновременно импульс с выхода элемента 82 задержки проходит через элемент ИЛИ 29 и элемент 76 задержки на вход Ч регистра 38, разрешая перезапись сдвинутой на один разряд в сторону младшего разряда информации из регистра 42 в регистр 38, На этом процесс Формирования дополнительной информации в40 регистрах 2 , ,оканчивается. Ре-, гистрысодержат при этом следующие кодовые слова - 01000, 00010, 00010, 00001, После формирования последнего сочетания 1001 в регистрах с будут содержаться следующие кодовые слова - 00001, 00100, 00010, 00001, поэтому элемент И 62 будет открыт единичным потенциалом с выхода последнего разряда. регистра 38, следовательно, импульс с выхода элемента 82 задержки, пройдя через элемент 81 задержки и элемент И 62, поступит на выход 92 окончания перебора. Длительность задержки элемента 81 опре деляется временем перезаписи информашки из регистра 42 в ре гистр 38 . Этим завершается процесс перебора всех соч етаний иэ к4 по= 2.Формула изобретенияУстройство для перебора сочетаний, содержащее и триггеров (и - число перебираемых элементов); первый элемент ИЛИ, первую группу элементов ИЛИ, первую, вторую, третью и четвертую группы элементов И, регистр сдвига, первый и второй элементы задержки, первую группу элементов задержки, ключ и элемент коммутации, причем выход -го (1 1, , и) элемента ИЛИ первой группы подключен к счетному входу х-го триггера, единичный и нулевой выходы -го триггера подключены к первым входам х-х элементов И первой и второй групп соответственно, первый вход первого элемента ИЛИ и вход первого элемента задержки через элемент коммутации соединены с входом единичного уровня устройства, выход первого элемента задержки подключен к управляющему входу ключа, информационный вход ключа является тактовым входом устройства, выход ключа соединен с вхо:м второго элемента задержки, о т л и ч а ю щ е е с я тем, что, с целью Формирования последовательности сочетаний с постоянным и минималь-. ным кодовым расстоянием по Хэммингу, оно содержит элементы ИЛИ с второго по девятый, шесть элементов И, вторую, третью и четвертую группы элементов ИЛИ, группы с пятой по (10 + и)-ю элементов И, и + 1 регистров, элементы задержки с третьего по восьмой, вторую группу элементов задержки, элемент И-ИЛИ, причем выходы элементов И первой и второй групп подключены соответственно к входам второго и третьего элементов ИЛИ, выходы второго и третьего элементов ИЛИ подключены к первым входам элементов И третьей и четвертой групп соответственно, второй вход .1 го Ц = 1, , и + 1) элемента И третьей группы соединен с 1-м разрядным выхЬдом регистра сдвига, второй вход -го элемента И четвертой группы соединен с ( + 1)-м разрядным выходом регистра сдвига, выход (+1)-го элемента И третьей группы подключен кпервому входу -го элемента ИЛИ первой группы, выход Ь + 1)-го Ь1, , и - 1) элемента И четвертой группы подключен к второму входу1 с-го элемента ИЛИ первой группы, выходы первых элементов И третьей и четвертой групп через четвертый элемент ИЛИ подключены к первым входам элементов И пятой группы, выход 1 с-го5 элемента И пятой группы подключен к третьему входу 1 с-го элемента ИЛИ первой группы, единичный выход -го триггера подключен к первым входам д-х элементов шестой и седьмой групп выходы элементов И шестой группы через пятый элемент ИЛИ подключены к первому входу первого элемента И,выход которого подключен к первым входам шестого и седьмого элементов ИЛИ, выход второго элемента ИЛИ через третий элемент задержки подклю" чен к второму входу шестого элемента ИЛИ и к первому входу восьмого элемента ИЛИ, выход третьего элемента ИЛИ через четвертый элемент задержки подключен к третьему входу шестого элемента ИЛИ и к второму входу седьмого элемента ИЛИ,. выход шестого25 элемента ИЛИ подключен к синхронизирующему входу регистра сдвига, выходы седьмого и восьмого элементов ИЛИ подключены к управляющим входам переноса в старший и младший разряды соответственно регистра сдвига, (+1)-й разрядный выход регистра сдвига подключен к первому входу -го элемента И восьмой группы, выход которого соединен с первым входом (д+1)-го элемен. та ИЛИ второй группы, выход -го эле- З 5 мента ИЛИ второй группы подключен к 3-му разрядному информационному входу первого регистра, 1-й разрядный выход д-го регистра подключен к первому входу 1-го элемента И (д + 8)-й груп 40 пы, З;й разрядный информационный вход (1 с+1)-го регистра, кроме Ос + 2)-го разряда, соединен с выходом 1-го элемента И девятой группы,Ь + 2)-й разрядный информационный вход (1 с + 1)-го 45 регистра соединен с выходом 1 с-го элемента ИЛИ третьей группы, 3-й разрядный выход первого регистра подключен к З-му разрядному информационному входу (и + 1)-го регистра, д-й разрядный 50 выход которого соединен с первым входом -го элемента И (и + 9)-й группы, вторые входы элементов И (и + 9)-й группы подключены к выходу второго элемента задержки, выход -го элемен та И (и + 9)-й группы подключен к вторым входам -х элементов И первой и второй групп и к входу -го элемента задержки первой группы, выход 1 с-го элемента задержки первой группы подключен к четвертому входу 1 с-го элемента ИЛИ первой группы, выход и-го элемента задержки первой группы подключен к второму входу и-го элемента ИЛИ первой группы, выход (1 с +1)-го элемента И (и + 9)-й группы подключен к вторым входам всех, кроме (и + 2)-го, элементов И (1 с + 9)-й группы и через 1 с-й элемент задержки второй группы - к первым входам 1 с-х элементов ИЛИ третьей и четвертой групп, второй вход 1 с-го элемента ИЛИ третьей группы подключен к выходу (1 с + 2)-го элемента И девятой группы, второй вход 1 с-го элемента ИЛИ четвертой группы подключен к выходу (и + 2)-го элемента И+ 8)-й группы, -й разрядный выход регистра сдвига подключен к первому входу 1-й группы элемента И-ИЛИ, (1 с + 1)-й разрядный выход (и + 1)-го регистра подключен к второму входу 1 с-го элемента И пятой группы и к первому входу (и+ + 2)-го элемента И (1 с + 8)-й группы, (1 + 1)-й разрядный выход (и + 1)-го регистра подключен к второАу входу -го элемента.И шестой группы, к первому входу д-го элемента И (и + 10)-й группы и к второму входу ( + 1)-й группы элемента И-ИЛИ, выход второго элемента задержки подключен к первому входу девятого элемента ИЛИ и через пятый элемент задержки - к второму входу первого элемента ИЛИ, к первому входу второго элемента И и к прямому входу третьего элемента И, второй вход второго элемента И и инверсный вход третьего элемента И подключены к выходу элемента И-ИЛИ, выход второго элемента И подключен к четвертому входу шестого элемента ИЛИ и к второму входу восьмого элемента ИЛИ, выход третьего элемента И подключен к второму входу первого элемента И, к вторым входам всех элементов И девятой группы, к вторым входам (и + 2)-х элементов И групп с десятой по (и + 7)-ю, к входу шестого элемента задержки, выход которого подключен к первому входу четвертоГо элемента И и к прямому входу пятого элемента И, второй вход четвертого элемента И и инверсный вход пятого элемента И подключены к первому разрядному выходу регистра сдвига, выход четвертого элемента И подключен кСоставитель В,Байковактор О.Спесивых Техред М. Ходанич,орректор М. Василье 4854/46 ВНИИПИ Гос по делам 113035, Москвираж 7 За одписн дарственного комитета СССизобретений и открытийЖ, Раушская наб д,Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная, 4 9 1427382 10 вторым входам всех элементов И (и + задержки подключен к управляющему + 10)- й группы, выход пятого элемен- входу записи первого регистра, выход та И подключен к вторым входам всех ключа соединен с управляющим входом элементов И восьмой группы выходУ5записи (и + 1)-го регистра выходУ первого элемента И (и + 10)-й группы первого элемента ИЛИ соединен с соединен с первым входом первого эле- вторыми входами всех элементов И мента ИЛИ второй группы, -и разряд- седьмой группы, выходы которых являный выход (Е + 1)-го регистра подклю- ются информационными выходами устчен к Ь + 1)-му входу 1-го элемента 10 ройства, выход шестого элемента ва- ИЛИ второй группы, выход (к + 1)-го держки через восьмой элемент зацержэлемента И (и + 10)-й группы подклю- ки соединен с первым входом шестого чен к (и + 1)-му входу Ь + 1)-го элемента И, второй вход которого подэлемента ИЛИ второй группы, выход ключен к (и + 1)-му разрядному выхо- К-го элемента ИЛИ четвертой группы ду первого регистра выход15У подключен к управляющему входу запи- шестого элемента И является си Ь + 1)-го регистра, выход девято- выходом окончания перебора устго элемента ИЛИ через седьмой элемент ройства.