Устройство для перебора размещений
Патент 1078425
Авторы
Классы МПК
Устройство для перебора размещений
Иллюстрации
Реферат
УСТРОЙСТВО ДЛЯ ПЕРЕБОРА РАЗМЕ1иЕНИЙ, содержащее генератор импульсов, блок сравнения, счетчики и блок вывода результата, о тличающееся тем, что, с целью упрощения и повышения быстродействия устройства, оно дополнительно содержит сдвигающий регистр, накапливающий сумматор, блок умножения , блок деления, блоки сравнения , задатчики исходной информа:ции , причем выход генератора импульсов подключен к входу сдвига сдвигающего регистра, информационный вход которого подключен к выходу блока умножения и к первому информационному входу блока деления , второй информационный вход которого подключен к выходу первого задатчика исходной информации, выход блока деления подключен к пepвo 1y входу первого блока сравнения , второй вход которого подключен к выходу первого счетчика, счетный вход которого подключен к второго блока сравнения и кГвходу сброса накапливающего сумматора, информационный вход которого подключен к выходу сдвигающего регистра, выход накапливающего сумматора подключен к первому входу блока вывода результата и I к первому входу второго блока сравнения , второй вход которого подклюСП чен к выходу второго задатчика исходной информации и к первому входу блока умножения, второй вход которого подключен к выходу первого блока сравнения, к второму входу блока вывода результата и к счетному входу второго счетчика, выход которого подключен к первому входу третьего блока сравнения, второй вход которого подключен к выходу третьего задатчика исходной информации, выход третьего блока сравнения подключен к входу разрешения работы генератора импульсов.
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИН (19) (11): (5)) 0 06 Г 7/ОО
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21 ) 3486363/18-24 (22) 24.08.82 (46) 07,03. 84. Бюл. 9 9 (72) В.Г. Левин и Г.П. Левин (71) Минский фипиал Всесоюзного научно-исследовательского и проектноконструкторского института по автоматизации предприятий промышленности строительных материалов (53) 681.3(088.8) (56) 1. Авторское свидетельство CCCP
9 622121, кл. G 06 F 7/00, 1973.
2. Авторское свидетельство СССР
9 860057, кл. 0 06 Е 7/00, 1980 (прототип). (54)(57) УСТРОЙСТВО,) ЛЯ ПЕРЕБОРА
РАЗМЕЩЕНИЙ, содержащее генератор импульсов, блок сравнения, счетчики и блок вывода результата, о тл и ч а ю щ е е с я тем, что, с целью упрощения и повышения быстродействия устройства, оно дополнительно содержит сдвигающий регистр, накапливающий сумматор, блок умножения, блок деления, блоки сравнения, задатчики исходной информации, причем выход генератора импульсов подключен к входу сдвига сдвигающего регистра, информационный вход которого подключен к выходу блока умножения и к первому информационному входу блока деления, второй информационный вход которого подключен к выходу первого задатчика исходной информации, выход блока деления подключен к первому входу первого блока сравнения, второй вход которого подключен к выходу первого счетчика„ счетный вход которого подключен к выходу второго блока сравнения и к: входу сброса накапливающего сумматора, информационный вход которого подключен к выходу сдвигаю- . щего регистра, выход накапливающего сумматора подключен к первому входу блока вывода результата и к первому входу второго блока сравнения, второй вход которого подключен к выходу второго задатчика исходной информации и к первому входу блока умножения, второй вход которого подключен к выходу первого блока сравнения, к второму входу блока вывода результата и к счетному входу второго счетчика, выход которого подключен к первому входу третьего блока сравнения, второй вход которого подключен к выходу третьего задатчика исходной информации, выход третьего блока сравнения подключен к входу разрешения работы генератора импульсов.
1078425
Изобретение относится к вычислительной технике и может быть использовано для решения комбинаторных задач, а также для генерирования кодовых последовательностей в устройствах управления, диаг ностики и контроля.
Известно устройство для перебора размещений с повторениями, содержащее генератор импульсов, блок сравнения и счетчик (1 ).
Недостаток известного устройства — ограниченные функциональные возможности, так как оно не позволяет варьировать порядком перебора размещений.
Наиболее близким к предлагаемому по технической сущности является устройство для перебора размещений, содержащее генератор импульсов, блок сравнения, два счетчика и блок вывода.
Данное устройство обладает большими функциональными возможностями за счет получения различного порядка перебора размещений (23.
Недостатком устройства-прототипа является то, что количество основных функциональных элементов в нем прямо пропорционально размерности генерируемого размещения, т.е. числу е и и (т.е. в устройствах содержится пп> -разрядных последовательно соединенных кольцевых счетчиков, схем ИЛИ и других элементов). Кроме того, устройство-прототип имеет низкое быстродействие, поскольку информация в кольцевых счетчиках продвигается последова-тельно разряд за разрядом и при больших значениях и и m время решения задачи резко увеличивается.
Наличие в прототипе элемента задержки еще более ухудшает показатели его быстродействия.
Цель изобретения — упрощение устройства и повышение его быстродействия.
Поставленная цель достигается тем, что устройство для перебора размещений, содержащее генератор импульсов, блок сравнения, счетчики и блок вывода результата, дополнительно содержит сдвигающий регистр, накапливающий сумматор, блок умножения, блок деления, блоки сравн6ния, задатчики исходной информации, причем выход генератора импульсов подключен к входу сдвига сдвигающего регистра, информационный вход которого подключен к выходу блока умножения и к первому информационному входу блока деления, второй информационный вход которого подклю. чен к выходу первого задатчика исходной информации, выход блока деления подключен к первому входу первого блока сравнения, второй вход
45 которо го подключен к выходу пер вого счетчика, счетный вход которого подключен к выходу второго блока сравнения и к входу сброса накапливающего сумматора, информационный вход которого подключен к выходу сдвигающего регистра, выход накапливающего сумматора подключен к первому входу блока вывода результата и к первому входу второго блока сравнения второй вход, которого подключен к выходу второго задатчика исходной информации и к первому входу блока умножения, второй вход которого подключен к выходу первого блока сравнения, к второму входу блока вывода результата и к счетному входу второго счетчика, выход которого подключен к первому входу третьего блока сравнения, второй вход которого подключен к выходу третьего задатчика исходной информации, выход третьего блока срав- нения подключен к входу разрешения работы генератора импульсов.
На чертеже приведена блок-схема устройства для перебора размещений.
Устройство содержит генератор
1 импульсов,. сдвигающий регистр 2, накапливающий сумматор 3, блок 4 сравнения, блоки 8 и 6 сравнения, счетчики 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
55;
65 которо го цодклк«lE ll к выходу блока
10 деления, а информационный вход последнего соединен с выходом за— датчика 11 исходной информации.
Управляющий вход блока 9 умножения подключен к выходу блока 5 сравнения, а его информационный вход соединен с выходом задатчика 12.
Входы блока 6 сравнения подключены к выходам задатчика 13 и счетчика 8, вход которого подключен к выходу блока 5 сравнения.
Один из входов блока 14 вывода результата соединен с выходом накапливающего сумматора 3, а другой его вход — с выходом блока 5 сравнения.
Устройство работает следующим образом.
Перед началом работы в зависимости от размерности генерируемого размещения А задатчиком 11 задаfTl ется число tl"",,задатчиком 12 число равное, а задатчиком 13 число равное m, где и, е — числа всевозможных размещений из и элементов по гп
Кроме того, в блок 9 умножения и в сдвигающий регистр 2 заносится единица.
Включение устройства осуществляется запуском генератора 1 импульсов.
Первым импульсом с выхода генератора 1 импульсов осуществляется сдвиг единицы в сдвигающем регистре 2 и по сигналу равенства нулю содержимого последнего заносится единица в накапливающий сумматор 3, откуда содержимое последнего (т.е. единица) поступает на вход устройства 14 вывода результата и регистрируется.
Кроме того, содержимое накапливающего сумматора 3 поступает на один иэ входов блока 4 сравнения, где происходит сравнение этого значения с числом равным п, поступающим на другой вход блока 4 сравнения с выхода задатчика 12.
Если сравниваемые значения не равны, то по аналогии с первым тактом работы генератора 1 импульсов на вход накапливающего сумматора 3 поступает вторая единица, которая прибавляется к предыдущей, и в блоке 4 сравнения происходит сравнение числа два с числом h, заданным задатчиком 12.
Эта операция повторяется до момента сравнения значений чисел на обоих входах блока 4 сравнения, При этом на устройство 14 вывода результата поступают последовательно увеличивающиеся на единицу числа.
В момент равенства сравниваемых на входах блока 4 сравнения чисел (через П тактов) на выходе последнего вырабатывается сигнал сравнения, который поступает на вход накапливающего сумматора 3, устанавливая его в нулевое состояние.
Этим же сигналом заносится единица в счетчик 7, после чего описанный цикл работы, состоящий иэ и тактов, повторяется..
Количество таких циклов (определяющих число элементов первого столбца значений, регистрируемых устройством вывода) равно числу И", заданному эадатчиком 11 исходной информации, и отсчитывается устройством следующим образом.
Сигналы сравнения с выхода блока 4 сравнения поступают на вход счетчика 7, где суммируются, и с каждым тактом подаются на один из входов блока 5 сравнения, на другой вход которого с эадатчика 11 подается число И, которое перед этим в и блоке 10 деления, делится на число, поступающее с выхода блока 9 умножения. Поскольку до описываемого " периода в блоке 9 умножения нахо-. дилась записанная в него единица, то число и разделенное в блоке 10 деления на единицу, остается без изменений.
Когда число циклов, суммирующих ся в счетчике 7, сравняется с числом п", на выходе блока 5 срав35 нения появится сигнал сравнения, который служит сигналом конца столбца для устройства вывода и переключения последнего для печати второго столбца. Кроме того, этим сиг40 налом разрешается считывание блоком
9 умножения числа п заданного задатчиком 12 исходной информации, а также заносится единица в счет".. чик 8.
Работа устройства при выводе второго столбца на устройство 14 вывода результата аналогична предыдущему.
Однако поскольку к этому моменту на управляющий вход блока 9 умножения с выхода блока 5 сравнения подан разрешающий сигнал, то содержимое блока 9 умножения (т.е. единица) умножается на число п, поступающее с задатчика 12. и полученное произведение (в данном случае число и ) заносится в сдвигающий регистр 2.
На выходе сдвигающего регистра
2 сигнал появляется после выполнения и тактов сдвига. Поэтому в течение первых тактов с выхода сдвигающего регистра 2 на вход накапливающего сумматора 3 сигналы не будут подаваться, в результате чего в каждом из и тактов на вход уст1078425
1 1 1 1
2 1 1 1
3 1 1 1
1,2 11
2 2,1 2
3 2 1 2
1312
2312
М»
2123
3 1 2 3
1 2 2 3
2223
322 3
1 3 2 3
2 3 2 3
34
68
3 312
1 1 2 2
2 1 2 2
2211
37
3211
38 ройства 14 вывода результата будет поступать и регистрироваться единица, содержащаяся в сумматоре 3.
По окончании П тактов с выхсда сдвигающего регистра 2 на вход накапливающего сумматора 3 подается единица, которая прибавляется к единице, уже хранящейся в накапливающем сумматоре 3. В течение следующих п тактов на вход устройства
14 вывода результата подается чис- ® ло, равное двум. Затем аналогично в течение следующих h тактов выводится на устройство 14 вывода результата число равное трем и так до числа и включительно, т.е. до 15 момента сравнения сигналов на обоих входах блока 4 сравнения и уста-. новки накапливающего сумматора 3 в нулевое состояние.
Следующий цикл работы устройст- gQ ва по выводу остальных элементов второго столбца аналогичен предыдущему.
Число циклов при выводе элементов второго столбца равно числу 25
П
Ill и отсчитывается устройством следующим oбразом.
Сигналы сравнения с выхода счетчика 7, поступающие на вход блока ЗО
5 сравнения, будут сравниваться с сигналами с выхода блока 10 деления, и так как к данному моменту на вход блока- 10 деления с выхода блока 9 умножения подано число т, то 35 в результате выполнения операции деления с выхода блока 9 умножения на вход блока 5 сравнения будет п
l подано число
П
Когда число циклов, регистрируе- 40 мых счетчиком 7, достигнет числа
ll равного — —, на выходе блока 5 срав- нения появится сигнал„ который занесет вторую единицу в счетчик 8, 45 переключит устройство 14 вывода результата на следующий (третий) столбец и разрешит занесение единицы в блок 9 умножения.
В блоке 9 умножения происходит умножение занесенного в него числа
rn с таким же числом, поданным на
его вход перед началом вывода второго столбца.
Таким образом, в блоке 9 умножения будет храниться число и n = п
При выводе третьего столбца по аналогии с описанным число циклов
П равно числу 2, а при выводе последи него столбца число циклов будет рав À но числу -т = 1.
Работа устройства автоматически прекращается, когда в счетчике 8 будет число равиое,а, т.е. число, соответствующее заданному числу в размещении А и .
TIpH этом содержимое счетчика 8 поступает на один иэ входов блока
6 сравнения, на другой вход которого подается код числа,. заданного задатчиком 13.
При равенстве значений этих кодов на выходе блока 6 сравнения вырабатывается сигнал, который поступает на управляющий вход генератора 1 импульсов и отключает последний.
Таким образом, блоком 14 результата будет зафиксирована последовательность элементов, представляющих собой всевозможные размещения с повторениями из П элементов по т, те. А
Каждое отдельное размещение с повторением представляет собой строку из m элементов, а общее число строк равно h
Работа устройства в режиме генерации размещений с повторениями A u при n = --3, rn - =4 иллюстрируется таблицей.
В таблице представлены всевозмож-; ные размещения с повторениями A„ =
А 4, число которых равно пи = 81.
1078425 т- т
1З11
3323 з 3
73
2 3 1 1
2 2 2
2 2 2 2
3З11
1121
2121
31З З
1 2 3 3
2 ? 3 3
3 2 3 3
42 з???
76
1 3 2 2
2 3 2 2
3 3 2 2
77
3 1 2 1
45
1 2 2 1
2 2 2 1
3 2 2 1
1з
1ЗЗЗ
1 3 2
80
2 3 3 3
ЗЗЗ3
2 1 3 2
3 1 3 2
1 2 3 2
1З21
2 2 3 2
2 3 2 1
3 3 2 1
11 З1
Число 3 2 1 0 циклов 3 3 3 3
51
52
2 1 3 1
53
3 1 3 1
1 2 3 1
23
57
26
27
28
62
63
31
2 2 3 1
3 2 3 1
1 3 3 1
2 3 3 1
ЗЗЗ1
1112
2112
3112
1212 Число циклов по столбцам соответственно равно 27; 9, 3, 1. По ходу генерации размещений с повторениями устройством выдаются также размещения без.повторений.
Например, размещением (без повто- 60 рений) А являются последователь3 но взятые шесть строк, состоящие из двух первых (слева) элемеитов, в которых нет одинаковых элементов (повторений) . 65
3 2 3 2
1 3 3 2
2 3 3 2
3 3 3 2
1 1 1 3
2 1 1 3
3 1 1 3
1 2 1 3
2 2 1 3
3 ? 1 3
1 3 1 3
2 3 1 3
3 3 1 3
1 1 2 3
В таблице размещению (беэ повторений) A соответствуют размещения под порядковыми номерами 2, 3, 4, 6, 7, 8 (элементы подчеркнуты) .
Для размещения (без повторений)
АЗ по аналогии будут соответствовать размещения в строках под номерами 12, 16, 20, 22, 33, 35.
При этом не имеет значения номер, с которого начинается выбор соответствующего размещения по упо1078425
10 щцщДЯ Заказ 964/42 Тираж 699 Подписное àï ППП "Патент", г, Ужгород, ул. Проектная,4 мянутому правилу. Необходимо лишь выбрать соответствующие элементы последовательно.
В данном устройстве обеспечивается воэможность варьирования порядковым размещением как для размещений, так и для размещений с повторениями.
В первом случае для этого достаточно изменить порядок вывода столбцов (с помощью задатчика 11, изме- 10 няющего число циклов по столбцам), а во втором случае достаточно изменить начальный элемент в последовательном чтении размещений (без повторений) по описанному правилу.
Таким образом, в данном устройстве для получения размещений с повторениями (и размещений без повторений) любой размерности достаточно с помощью задатчика 12 исходной информации ввести число и, с помощью задатчика 13 исходной информации — число ю и задатчиком 11 исходной информации — число П" .
В отличие от данного устройства 2д в устройстве-прототипе максимально возможный порядок генерируемых размещений определен числом h-m -разрядных кольцевых счетчиков, элементов ИЛИ и других элементов, что делает его неприемлемым для решения комбинаторных задач большой размерности.
tpoxe того, быстродействие устройства-прототипа значительно (как минимум на порядок) ниже быстродействия предлагаемого устройства. Причем с увеличением размерности генерируемых размещений быстродействие резко снижается. Это объясняется наличием в устройстве-прототипе rl пересчетных щ -разрядных схем (кольцевых счетчиков), где информация продвигается последовательно разряд за разрядом.
В данном устройстве информация передается в основном параллельным кодом между ограниченным числом элементов, что обеспечивает значительно более высокое быстродействие.
Снижение быстродействия прототи-. па, кроме того, дополнительно обусловлено наличием в нем элемента задержки.
Данное устройство, имеющее законченную структуру для размещений любых размерностей, может быть выполнено по интегральной технологии в виде БИС и использоваться как функциональный элемент в различных вычислительных машинах, системах контроля и управления.