Устройство для выделения среднего из нечетного количества чисел

Изобретение относится к вычислительной технике н может быть исполь" зонано в составе специализированных ЭВМ и устройствах обработки данных.5Пель изобтетения - повьпиение быстродействия.На чертеже представлена схема устройства.Устройство содержит блок 1 ассоциативной памяти (БАЛ) 1, сумматоры 2 и 3, регистр 4 маски, регистр 5 суммы, регистр б управления блок сравнения, группу триггеров 8.1-8.п (и - количество разрядов анализируемых чисел), группу элементов И 9 1- 9.п, дешифратор 10, счетчик 11, триггер 12 управления, элементы И 13 и 14, элемент НЕ 15, информационные 16 и адресные 17 входы, вход 18 начальной установки, вход 19 задания количества чисел, входы задания режимов чтения 20 и записи 21, тактовый вход 22, инозормационные выходы 23, выходы 24.1-24.п разрядов среднего числа. 25Сущность процедуры нахождения сред/ него из нечетного количества чисел, реализуемой в предлагаемом устройст. -ве, состоит в следующем. Пусть Й= еА,АА,Ам- неупорнноченное мне ;жество чисел А=а ау0 а 1 Пр,щ а(О 1 х - 1 пр и разряд ность, н пусть, Н= ЬЬеЬе, Ь;АГ 0,1- среднее (медиана) множество Й (ВЕЯ). Множество чисел избменьших В, яв ляется объединением БНзподмно(жеств Н Я, определяемых следующим1- Образом: Н =фЬ =0 н Н,=0(А ) / (а йЗ401 к ЭЬк)=Ор а 0 Ь,=1, т.е. множество Н объединяет числя А, совпадающие старшими (-1) разрядами с соответствующими разрядами медианы В и имеющие в 1-м разряде куль нри единичном зна 45 чении х-го разряда среднего В, Тогда справедливо следующее: пусть известны 1 старших разрядов ЬАЬ.,ЬЕ среднего В, известны также количества К , К,КЕ элементов, составляющих соответственно множества Н 1, Н,Н50 и необходимо определить значение(1+1)-го разряда В. Положим, ЬР=О и выделим множество Нсодержащее К элементов. Очевидно, что если+1 55К(щ+1)/2, то предположение,Р 1что Ь 0 является верным, и, следо+вательно, Ьр+1=0, а Н+, -. Повторяемая рекурсивно и раз, приведенная процедура позволяет получить значение В=ЬЬЬд за и тактов.Устройство работает следующим образом.В БАП 1 записываются анализируемые числа, которые поступают по входам 16 в сопровождении адреса, поступающего по входу 17 и сигнала записи по входу 21 в регистр 6 записывается величина (щ+1) /2 (щ - количество анализируемых чисел), счетчик 11, регистр 5 и триггеры 8.1-8.п и 12 устанавливаются в нулевое состояние, в регистре 4 старший разряд устанавливается в единичное, а остальные разряды - в нулевое состояние.Выполнение приведенной процедуры начинается с того, что под действием синхроимпульса, поступающего с тактового входа 20 устройства через открытый единичным. потенциалом ;с прямого выхода триггера 12 элемент И 13 на вход управления опро,сом БАП 1 инициируется его опрос. При этом на входы признака опроса БАП 1 поступают с выходов триггеров 8 и-разрядный нулевой код, а на входы маскирования - код 100 с выходов регистра 4 маски. Такимобразом, в первом такте БАП 1 выполняет ассоциативный поиск чисел с нулем в старшем разряде (выделение множества Н). Сигналы совпадения, Формирующиеся при этом на ши-. нах совпадения БАП 1, суммируются сумматором 2, код В.1 с выходов которого на сумматоре 3 суммир"ется с содержимым предварительно обнулен- . ного регистра 5 и с выходов сумматора 3 и эта величина з поступает на информационные входы регистра 5 суммы и на первые входы блока сравнения, где сравнивается с кодом числа (щ+1) /2, хранящегося в регистре 6. Если з (щ+1)/2, то на выходе блока 7 сравнения сформируется нулевой сигнал, который запрещает запись в регистр 5 суммы. Если з(щ+1) /2, то на выходе блока 7 сравнения сформируется единичный сигнал, который разрешает запись в регистр 5 величины з. По спаду синхроимпульса, поступающего с тактового входа 20 устройства через элемент И 13 на вход управления сдвигом регистра 4, производится сдвиг содержимого этого регистра в сторону младших разрядов с заполнени164 7554 10 15 20 25 ем освобоциншегося старшего разряд единицей. В эта же время инвертированный синхроимпульс поступает с выхода элемента НГ 15 на первые входы всех элементов И 9, на вторые входы которых поступает поразрядно код с выходов счетчика 11 через дешиФратор 10. Поскольку в первом такте счетчик 11 установлен в нуль, то в единицу установлен только бит на первом выходе дешиФратора 10 и соответственно этот единичный сигнал будет разрешать прохождение инвертированного синхроимпульса с выхода элемента И 14 через первый элемент И 9, 1 группы на стробирующий вход триггера 81 . По спаду инвертированного синхроимпульса триггер 81 установится в единичное или останется в нулевом состоянии в зависимости от сигнала, поступающего на его инФормационный вход (т.е. в зависимости от сигнала на выходе блока 7 сравнения) и во всех последующих тактах не меняет своего состояния. Кроме того, по спаду инвертированного- синхроимпульса производится прибавление единицы к содержимому счетчика 11, Второй и последующие такты отрабатываются усФройством аналогично описанному способом.Всего будет выполнено и тактов, причем каждый 1-й такт (1-"2,п) отличается от первого тем, что маска на входах маскирования БАП 1 Формируется следующим образом:1111000,-0 а на входы признака опроса БАП 1 с выходов триггеров 8 группы поступает код, старшие (1-1) разрядов которого совпадают со старшими (1-1) циФрами среднего, определенными в предыдущих тактах и заФиксированных на первых (1-1) триггерах 8 группы, а остальные разряды которого равны нулю. В счетчике 11 будет заФиксироваио число (1-1), а соответственно и синхроимпульс с выхода элемента И 14 будет подаваться через элемент И 9 на стробирующий вход триггера 8 В, а в.регистре 5 к началу такта будет заФиксировано суммарное количество чисел на хранящихся БАП 1, которые меньше, чем среднее и исключены из поиска.После окончания и-го такта иа выходе переполнения счетчика 11 появится единичный сигнал, который устанавливает в нуль триг 1 ер 12 и устройствопере."одпт н исходное состояние. Формула изобретения Устройство для выделения среднего из нечетного количества чисел, содержащее группу триггеров, счетчик и группу элементов И, причем вход начальной установки устройства соединен с входом установки в нулевое состояние триггеров группы, о т л и ч а ющ е е с я тем, что, с целью повьпйения быстродействия, в него введены блок ассоциативной памяти, блок сравнения, два сумматора, регистр маски, регистр суммы, регистр управления, дешиФратор, триггер управления, два элемента И и элемент НЕ, причем адресные и инФормационные входы устройства соединены соответственно с адресными и инФормационными входами блока ассоциативной памяти, выходы признака совпадения которого соединены с входами первого сумматора, выходы которого соединены с соответствующими входами первой группы второгосумматора, выходы которого соединены 30 с соответствующими входами первойгруппы блока сравнения и с соответствующими инФормационными входами регистра суммы, выходы разрядов которого соединены с соответствующими входами втоРой гРуппы второго сумматора,входы задания количества чисел устройства соединены с соответствующимиинФормационными входами регистра управления, выходы разрядов которого 4 О соединены с соответствующими входамивторой группы блока сравнения, выходкоторого соединен с инФормационнымивходами всех триггеров группы и с входом разрешения записи регистра суммы, 45. вход установки в нулевое состояниекоторого объединен с входом установкив нулевое состояние счетчика и всехразрядов регистра маски, кроме старшего, и входом установки в единичное 5 О состояние старшего разряда регистра .маски и подключен к инверсному выходу триггера управления, прямой выходкоторого соединен с первыми входамипервого и второго элементов И, тактовый вход устройства соединен с вторымвходомпервого элемента И, выход которого соединен с входом управленияопросом блока ассоциативной памяти,сдвиговым входом регистра маски и1647554 Составитель В,ГороховТехред И.ДидыкКорректор Н.Король Редактор Я,Бугренкова Заказ 1400 Тирак 404 Подписное. ВНЮЙИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Иосква, Ж, Раушская наб., д, 4/5 Производственно-издательский комбинат "Патент", г.ужгород, ул, Гагарина,101 через элемент НЕ., - с вторым входомвторого элемента И, выход которого соединен с входом синхронизации регистра суммы, первыми входами всех элементов И группы и счетным входом счетчика, выходы разрядов которого соединены с соответствующими входами дешнйратора, -й выход которого ( 1,2п, и - количество разрядов 10 анализируемых чисел) соединен с вто; рым входом -го элемента И группы, выход которого соединен с входом син" хронизации 1-го триггера группы, выход которого является выходом -го разряда среднего числа устройства и соединен с 1-м входом признака опроса блока ассоциативной памяти, входымаски которого подключены к выходамсоответствующих разрядов регистрамаски, входы задания режимов. чтенияи записи устройства подключены соответственно к входам "Чтение" и "За-пись" блока ассоциативной памяти,информационные выходы которого являются информационными выходами устройства, выход переполнения счетчикасоединен с входом установки триггерауправления в нулевое состояние, входустановки которого в единичное состояние, как и вход разрешения записирегистра управления, подключен к входу начальной установки устройства.