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

(19) 111): Ц 51) 0 06 Г 7/ОО ОПИСАНИЕ ИЗОБРЕТЕНИЯ Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(71) Минский фияиал Всесоюзного научно-исследовательского и проектно- конструкторского института по автоматизации предприятий промышленности строительных материалов(56) 1. Авторское свидетельство .СССР Р 622121, кл. 0 06 Г 7/00, 1973.2. Авторское свидетельство СССР Р 860057, кл. 0 06 Е 7/00, 1980 (прототип),(54)(57) УСТРОЙСТВО ДЛЯ ПЕРЕБОРАРАЗМЕЩЕНИЙ, содержащее генераторимпульсов, блок сравнения, счетчики и блок вывода результата, о тл и ч а ю щ е е с я тем, что, сцелью упрощения и повышения быстродействия устройства, оно дополнительно содержит сдвигающий регистр,накапливающий сумматор, блок умножения, блок деления, блоки сравнения, задатчики исходной информации, причем выход генератора импульсов подключен к входу сдвигасдвигающего регистра, информационный вход которого подключен к выходу блока умножения и к первому и нформацио н ному входу блока деления, второй информационный входкоторого подключен к выходу первого задатчика исходной информации,выход блока деления подключен кпервому входу первого блока сравнения, второй вход которого подключен к выходу первого счетчикасчетный вход которого подключенк выходу второго блока сравненияи к, входу сброса накапливающегосумматора, информационный вход которого подключен к выходу сдвигаю- .щего регистра, выход накапливающего сумматора подключен к первомувходу блока вывода результата ик первому входу второго блока сравнения, второй вход которого подключен к выходу второго задатчика исходной информации и к первому входу блока умножения, второй вход которого подключен к выходу первого блока сравнения, к второму входу блока вывода результата и ксчетному входу второго счетчика,выход которого подключен к первомувходу третьего блока сравнения,второй вход которого подключен квыходу третьего задатчика исходнойинформации, выход третьего блокасравнения подключен к входу разрешения работы генератора импульсов.50 55 60 65 Изобретение относится к вычислительной технике и может бытьиспользовано для решения комбинаторных задач, а также для генери)рования кодовых последовательностей в устройствах управления, диагностики и контроля.Известно устройство для перебора размещений с понторениями, содержащее генератор импульсов, блоксравнения и счетчик1 ,Недостаток известного устройства - ограниченные функциональныевозможности, так как оно не позволяет варьировать порядком перебораразмещений.Наиболее близким к предлагаемому по технической сущности является устройство для перебора размещений, содержащее генератор импульсон, блок сравнения, два счетчикаи блок вывода.Данное устройство обладает большими функциональными возможностями за счет получения различногопорядка перебора размещений 23,Недостатком устройства-прототипа является то, что количество основных Функциональных элементовв нем прямо пропорционально размерности генерируемого размещения,т,е. числу Ф и Р (т,е, в устройствах содержится пп -разрядных последовательно соединенных кольцевыхсчетчиков, схем ИЛИ и других элементов). Кроме того, устройство-прототип имеет низкое быстродействие,поскольку информация в кольцевыхсчетчиках продвигается последова-.тельно разряд за разрядом и прибольших значениях и и щ время рецения задачи резко унеличивается,Наличие н прототипе элемента задержки еще более ухудшает показателиего быстродействия.цель изобретения - упрощениеустройства и повышение его быстродействия,Поставленная цель достигаетсятем, что устройство для перебораразмещений, содержащее генератор импульсов, блок сравнения, счетчикии блок вывода результата, дополнительно содеркит сдвигающий регистр,накапливающий сумматор, блок умножения, блок деления, блоки сравн 6 ния, задатчики исходной информации,причем выход генератора импульсовподключен к входу сдвига сдвигающего регистра, информационный входкоторого подключен к выходу блокаумножения и к первому информационному входу блока деления, второйинформационный вход которого подключен к выходу первого задатчика исходной информации, выход блока деления подключен к первому входу первого блока сравнения, второй нход 10 15 20 25 30 35 40 45 которого подключен к выходу первого счетчика, счетный вход которогоподключен к выходу второго блокасравнения и к входу сброса накапливающего сумматора, информационныйвход которого подключен к выходусднигающего регистра, выход накапливающего сумматора подключен кпервому входу блока вывода результата и к первому входу нторого блока сравнения," второй вход, которогоподключен к выходу второго задатчика исходной информации и к первомувходу блока умножения, второй входкоторого подключен к выходу первогоблока сравнения, к второму входублока вывода результата и к счетному входу второго счетчика, выходкоторого подключен к первому входутретьего блока сравнения, второйвход которого подключен к выходутретьего задатчика исходной информации, выход третьего блока срав-нения подключен к входу разрешенияработы генератора импульсов.На чертеже приведена блок-схема устройства для перебора размещений,Устройство содержит генератор1 импульсов,. сдвигающий регистр 2,накапливающий сумматор 3, блок 4сравнения, блоки 5 и б сравнения,счетчики 7 и 8, блок 9 умножения,блок 10 деления, задатчики 11-13исходной информации и блок 14 вывода результата.. Б качестве блоков 9 и 10 умножения и деления используются блоки целочисленного умножения и деления, а в качестве блока 14 выводарезультата может быть примененоустройство циФровой индикации илипечатающее устройство.Задатчиками 11-13 исходной информации являются цифровые задатчики с кодовым выходом.Генератор 1 импульсов своим управляющим входом связан с выходом первого дополнительного блока б сравнения, а выходом - с входом сдвигающего регистра 2, выход которого соединен с входом накапливающе го сумматора 3. Информационный выход блока 9 умножения подключен к входу сдвигающего регистра 2 й одному из входов блока 10 деления, второй вход которого подключен к выходу задатчика 11 исходной информации.Один из входов блока 4 сравнения подключен к выходу задатчика 12 исходной информации, другой его вход соединен с выходом накапливающего сумматора 3, а выход - с входом первого счетчика 7 и управляющим входом сумматора 3.Выход счетчика 7 соединен с нходом блока 5 сравнения, другой вхо-,1078425 5 10 15 20 25 45 50 55, 60 65 которого подключен к выходу блока10 деления, а информационный входпоследнего соединен с выходом за -датчика 11 исходной информации,Управляющий вход блока 9 умножения подключен к выходу блока 5сравнения, а его информационныйвход соединен с выходом задатчика 12.Входы блока 6 сравнения подключены к выходам задатчика 13 и счетчика 8, вход которого подключен квыходу блока 5 сравнения,Один из входов блока 14 выводарезультата соединен с выходом накапливающего сумматора 3, а другойего вход - с выходом блока 5 сравнения.Устройство работает следующимобразом.Перед началом работы в зависимости от размерности генерируемогоразмещения А задатчиком 11 задаПется число и", задатчиком 12 число равное , а задатчиком 13 число равное щ , где и, в - числавсевозможных размещений из и элементов по гпКроме того, в блок 9 умноженияи в сдвигающий регистр 2 заноситсяединица.Включение устройства осуществляется запуском генератора 1 импульсов.Первым импульсом с выхода генератора 1 импульсов осуществляетсясдвиг единицы в сдвигающем регистре 2 и по сигналу равенства нулюсодержимого последнего заноситсяединица в накапливающий сумматор 3,откуда содержимое последнего (т.е.единица) поступает на вход устройства 14 вывода результата и регистрируется.Кроме того, содержимое накапливающего сумматора 3 поступает наодин из входов блока 4 сравнения,где происходит сравнение этого значения с числом равным п, поступающим на другой вход блока 4 сравнения с выхода задатчика 12. Если сравниваемые значения не равны, то по аналогии с первым тактом работы генератора 1 импульсов на вход накапливающего сумматора 3 поступает вторая единица, которая прибавляется к предыдущей, и в блоке 4 сравнения происходит сравнение числа два с числом Ь, заданным задатчиком 12.Эта операция повторяется до момента сравнения значений чисел на обоих входах блока 4 сравнения, При этом на устройство 14 вывода результата поступают последовательно увеличивающиеся на единицу числа. В момент равенства сравниваемых на входах блока 4 сравнения чисел (через П тактов) на выходе последнего вырабатывается сигнал сравнения, который поступает на вход накапливающего сумматора 3, устанавливая его в нулевое состояние.Этим же сигналом заносится единица в счетчик 7, после чего описанный цикл работы, состоящий из п тактов, повторяетсяКоличество таких циклов (онределяющих число элементов первого столбца значений, регистрируемых устройством вывода) равно числу и", заданному задатчиком 11 исходной информации, и отсчитывается устройством следующим образом.Сигналы сравнения с выхода блока 4 сравнения поступают на вход счетчика 7, где суммируются, и с каждым тактом подаются на один из входов блока 5 сравнения, на другой вход которого с задатчика 11 подается число П , которое перед этим виблоке 10 деления, делится на число, поступающее с выхода блока 9 умножения. Поскольку до описываемого " периода в блоке 9 умножения находилась записанная в него единица, то число и", разделенное в блоке 10 З 0 деления на единицу, остается безизменений.Когда число циклов, суммируюцихся в счетчике 7, сравняется с числом и", на выходе блока 5 срав нения появится сигнал сравнения,который служит сигналом конца столбца для устройства вывода и переключения последнего для печати второго столбца, Кроме того, этим сиг налом разрешается считывание блоком9 умножения числа и , заданного задатчиком 12 исходной информации,а также заносится единица в счет" чик 8.Работа устройства при выводе второго столбца на устройство 14 вывода результата аналогична предыдущему.Однако поскольку к этому моменту на управляющий вход блока 9 умножения с выхода блока 5 сравнения подан разрешающий сигнал, то содержимое блока 9 умножения (т.е. единица) умножается на число и , поступающее с задатчика 12, и полученное произведение (в данном случае число п ) заносится в сдвигающий регистр 2.На выходе сдвигающего регистра 2 сигнал появляется после выполнения и тактов сдвига. Поэтому в течение первых тактов с выхода сдвигающего регистра 2 на вход накапливаюцего сумматора 3 сигналы не будут подаваться, в результате чего в каждом из и тактов на вход уст1078425 111 3212 1312 2 3 1,2 1 322 331 1 1 2 1 37 38 2 3 2 3 ройства 14 вывода результата будетпоступать и регистрироваться единица, содержащаяся в сумматоре 3,По окончании П тактов с выхсдасдвигающего регистра 2 на вход накапливающего сумматора 3 подаетсяединица, которая прибавляется кединице, уже хранящейся в накапливающем сумматоре 3, В течение следующих и тактов на вход устройства14 вывода результата подается чис-ло, равное двум. Затем аналогичнов течение следующих и тактов выводится на устройство 14 вывода результата число равное трем и такдо числа и включительно, т.е, до 15момента сравнения сигналов на обоих входах блока 4 сравнения и уста-.новки накапливающего сумматора 3в нулевое состояние.Следующий цикл работы устройст Ова по выводу остальных элементоввторого столбца аналогичен предыдущему.Число циклов при выводе элементов второго столбца равно числу 25ии отсчитывается устройством следующим образом.Сигналы сравнения с выхода счетчика 7, поступающие на вход блока ЗО5 сравнения, будут сравниваться ссигналами с выхода блока 10 деления, и так как к данному моменту навход блока 10 деления с выхода блока 9 умножения подано число т, тов результате выполнения операцииделения с выхода блока 9 умножения на вход блока 5 сравнения будетиподано числов ,ОКогда число циклов, регистрируе" 40мых счетчиком 7, достигнет числаиравного -- , на выходе блока 5 срав-нения появится сигнал который занесет вторую единицу в счетчик 8, 45переключит устройство 14 вывода ре"зулктата на следующий (третий) столбец и разрешит занесение единицы в блок 9 умножения.В блоке 9 умножения происходит умножение занесенного в него числа в с таким же числом, поданным на его вход перед началом вывода второго столбца.Таким образом, в блоке 9 умножения будет храниться числои и = иПри выводе третьего столбца по аналогии с описанным число цикловправно числу 2 , а при выводе послединего столбца число циклов будет равяно числу -т = 1.Работа устройства автоматически прекращается, когда в счетчике 8 будет число равиое,а , т.е. число, соответствующее заданному числу в размещении А.При этом содержимое счетчика 8 поступает на один иэ входов блока 6 сравнения, на другой вход которого подается код числа, заданного задатчиком 13.При равенстве значений этих кодов на выходе блока 6 сравнения вырабатывается сигнал, который поступает на управляющий вход генератора 1 импульсов и отключает последний.Таким образом, блоком 14 результата будет зафиксирована последовательность элементов, представляющих собой всевозможные размещения с повторениями из и элементов по е, те. Ав Каждое отдельное размещение с повторением представляет собой строку из,т элементов, а общее число строк равно йРабота устройства в режиме генерации размещений с повторениями А и при и = 3, п = 4 иллюстрируется таблицей.В таблице представлены всевозмож-; ные размещения с повторениями Аф" = А 4 , число которых равно п= 81.е3 1 2 2 39 73 2 311 2 2 2 2 1 3 3 41 з з 1121 2121 31 ЗЗ 1233 233 3233 42 з 10 76 1 3 2 2 2 3 2 2 3 3 2 2 44 77 3121 12 45 1221 2 2 2 1 3 2 2 1 13 79 1 ЗЗЗ 46 1 3 2 14 80 2 3 3 3 зззз 2 1 3 2 81 3132 12 32 16 1 З 21 2232 2 321 3321 11 З 1 17 Число 3 2 1 0циклов 3 3 3 3 50 51 3232 1332 2 3 3 2 3332 1113 2113 3113 1213 22 13 31 3 1313 2313 3313 1123 52 2131 20 53 3131 21 12 31 22 2 2 3 1 32 31 1 3 3 1 2331 зззг 1112 2112 3112 1212 23 56 58 26 59 27 60 28 61 62 29 63 30 31 64 В таблице размещению (беэ повторений) Аэ соответствуют размещенияпод порядковыми номерами 2, 3, 4, 6,7, 8 (элементы подчеркнуты),Для размещения (без повторений)АЗ по аналогии будут соЬтветствовать размещения в строках под номерами 12, 16, 20, 22, 33, 35,При этом не имеет значения номер, с которого начинается выборсоответствующего размещения по упо Число циклов по столбцам соответственно равно 27; 9, 3, 1. По ходу генерации размещений с повторениями устройством выдаются также размещения без.повторений.Например, размещением (без повто рений) А являются последователь 3но взятые шесть строк, состоящие из двух первых (слева) элемеитов, в которых нет одинаковых элементов (повторений), 651078425 ИПИ Заказ 964/42 Филиал ППП фПатен Ужго ул. Проект мянутому правилу. Необходимо лишь выбрать соответствующие элементы последовательно.В данном устройстве обеспечивается воэможность варьирования порядковым размещением как для размещений, так и для размещений с повторениями.В первом случае для этого достаточно изменить порядок вывода столбцов (с помощью задатчика 11, изме няющего число циклов по столбцам), а во втором случае достаточно изменить начальный элемент в последовательном чтении размещений без повторений) по описанному правилу. 15Таким образом, в данном устройстве для получения размещений с повторениями (и размещений без повторений) любой размерности достаточно с помощью задатчика 12 исходной информации ввести число п , с помощью задатчика 13 исходной информации - число о и задатчиком 11 исходной информации - число П" .В отличие от данного устройства 2 д в устройстве-прототипе максимально возможный порядок генерируемых размещений определен числом и ь -разрядных кольцевых счетчиков, элементов ИЛИ и других элементов, что делает его неприемлемым для решения комбинаторных задач большой размерности.Йроме того, быстродействие устройства-прототипа значительно (как минимум на порядок) ниже быстродействия предлагаемого устройства. Причем с увеличением размерности генерируемых размещений быстродействие резко снижается. Это объясняется наличием в устройстве-прототипе П пересчетных е -разрядных схем (кольцевых счетчиков), где информация продвигается последовательно разряд за разрядом,В данном устройстве информация передается в основном параллельным кодом между ограниченным числом элементов, что обеспечивает значительно более высокое быстродействие.Снижение быстродействия прототипа, кроме того, дополнительно обусловлено наличием в нем элемента задержкиДанное устройство, имеющее законченную структуру для размещенийлюбых размерностей, может быть выполнено по интегральной технологии в виде БИС и использоваться как функциональный элемент в различных вычислительных машинах, системах контроля и управления. Тираж 699 Подписное