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

 

Изобретение относится к вычисли тельной технике. Цель изобретения - повышение быстродействия. Устройство содержит блок ассоциативной памяти (БАЛ) 1, сумматоры 2, 3, регистр 4 маски, регистр 5 суммы, регистр 6 уп 16 23 АI п равления, блок сравнения 7, группу регистров п (п - количество разрядов анализируемых чисел), группу элементов И , дешифратор 10, счетчик 11, триггер 12 управлений, элементы И 13,14, элемент НЕ 15, информационные 16 и адресные 17 входы , вход 18 начальной установки, вход 19 задания количества чисел, входы задания режимов питания 20 и записи 21, тактовый вход 22, информационные выходы 23, выходы разрядов среднего числа. На каждом j-м такте (,2,..n) БАЛ 1 производит поиск чисел, разряды которого с 1-го по j-1-й равны уже выделенному, а j-й разряд равен нулю. Если выделенное количество таких чисел в сумме с количеством ранее исключенных из рассмотрения - s(m+1)/2 (m - количество анализируемых чисел), то j-й разряд среднего числа равен нулю, в противном случае - единице. 1 ил. (Л & СЛ &п Сь

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕаЪБЛИН (19) 01) 4 А1 (51)5 С 06 Г 7/06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTGPCHGMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТ8ЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

llPM ГКНТ СССР (21) 4615572/24 (22) 02.12.88 (46) 07.05.91 ° Бюл. Р 17 (71) Киевский политехнический институт им . 50-летия Великой

Октябрьской социалистической революции (72) Барвадеш Пандиан (ТИ), В.И.Корнейчук, А.П.Марковский

:и Е.А.Иаслянчук (SU) (53) 681.325(088.8) (56) Авторское свидетельство СССР

Р 1246088, кп. G 06 F 7/06, 1986.

Авторское свидетельство СССР

У 1053100. кл. G 06 F 7/06, 1982. (54) УСТРОЙСТВО ДЛЯ ВСЕЛЕНИЯ СРЕДНЕГО ИЗ НЕЧЕТНОГО КОЛИЧЕСТВА ЧИСЕЛ (57) Изобретение относится к вычислительной технике. Цель изобретения— повышение быстродействия. Устройство содержит блок ассоциативной памяти (БАП) 1, сумматоры 2, 3, регистр 4 маски, регистр 5 суммы, регистр 6 уп2 равления, блок сравнения 7, группу регистров 8 -8 < (n — количество разрядов анализируемых чисел), группу элементов И 9<-9д, дешифратор 10, счетчик 11, триггер 12 управлени1, элементы И 13, 14, элемент НЕ 15, информационные 16 и адресные 17 входы, вход 18 начальной установки, вход 19 задания количества чисел, входы задания режимов питания 20 и записи 21, тактовый вход 22, информационные выходы 23, выходы 24 -24 разрядов среднего числа. На каждом

j-.ì такте (j=1,2...n) hAll 1 производит поиск чисел, разряды которого с

1-го по j-1-й равны уже вьщеленному, а -й разряд равен нулю. Если выде-; ленное количество таких чисел в сумме с количеством ранее исключенных из рассмотрения — s) (m+f) /2 (m — количество анализируемых чисел), то

j-й разряд среднего числа равен нулю, в противном случае — единице . f an.

1647554

Изобретение относится к вычислительной технике н может быть использовано в составе специализированных

ЭВМ и устройствах обработки данных.

Цель изобтетения — повьпиение быстродействия.

На чертеже представлена схема устройства.

Устройство содержит блок 1 ассоциативной памяти (БАЛ) 1, сумматоры 2 и 3, регистр 4 маски, регистр 5 суммы, регистр б управления„ блок 7 сравнения, группу триггеров 8.1-8.п (n — количество разрядов анализируе1 мых чисел), группу элементов И 9 19.п, дешифратор 10, счетчик 11, триггер 12 управления, элементы И 13 и 14, элемент НЕ 15, информационные 16 и адресные 17 входы, вход 18 начальной установки, вход 19 задания количества чисел, входы задания режимов чтения 20 и записи 21, тактовый вход 22, информационные выходы 23, выходы 24.1-24.п разрядов среднего числа. 25

Сущность процедуры нахождения сред/ него из нечетного количества чисел, реализуемой в предлагаемом устройст. — .. ве, состоит в следующем. Пусть Q,=

=f À <, АА..., А м 3- неуоорнночене ее мне- 30

;жество чисел А =а,, а0,...,a>»

j=1,m, а, (0,1j, i=1,n, n — разряд"

„„,, x cycle, Н= Ь,Ь,...Ь„, ЬФ0,13среднее (медиана) множество Q (ВЕ53 .

Множество чисел изб 10 меньших В, является объединением UH подмно( жеств Н + Q, определяемых следующим (р

1-!

Образом : Н, =фЬ| =0 н Н,,=0(А ) Q (а „®

"1к

®Ь, ) =О, а „ Ь, =1, т.е. множество Н, объединяет числя А,, совпадающие старшими (i-1) разрядами с соответствующими разрядами медианы В и имеющие в

i-м разряде куль нри единичном зна45 чении i-ro разряда среднего В. Тогда справедливо следующее: пусть известны 1 старших разрядов blab<...ЬЕ среднего В, известны также количества К, R<...,R< элементов, составляющих соответственно множества Н1, Н ...,Нg

50 и необходимо определить значение (1+1)-го разряда В. Положим, Ь + =О и выделим множество Н +(, содержащее

Rg (элементов. Очевидно, что если

+(55

К > (m+1)/2, то предположение, 1 что Ь 0 является верным, и, следо +! вательно, Ьр+1=0, а Н +, =p. Повторяемая рекурсивно и раз, приведенная процедура позволяет получить значение B=b(Ь ...Ьд за и тактов.

Устройство работает следующим образом.

В БАП 1 записываются анализируемые числа, которые поступают по входам 16 в сопровождении адреса, поступающего по входу 17 и сигнала записи по входу 21 в регистр 6 записывается величина (m+1) /2 (m — количество анализируемых чисел), счетчик 11, регистр 5 и триггеры 8.1-8.п и 12 устанавливаются в нулевое состояние, в регистре 4 старший разряд устанавливается в единичное, а остальные разряды — в нулевое состояние.

Выполнение приведенной процедуры начинается с того, что под действием синхроимпульса, поступающего с тактового входа 20 устройства через открытый единичным. потенциалом

;с прямого выхода триггера 12 элемент И 13 на вход управления опро,сом БАП 1 инициируется его опрос.

При этом на входы признака опроса

БАП 1 поступают с выходов триггеров 8 и-разрядный нулевой код, а на входы маскирования — код 10...0 с выходов регистра 4 маски. Таким образом, в первом такте БАП 1 выполняет ассоциативный поиск чисел с нулем в старшем разряде (выделе:ние множества Н ). Сигналы совпадения, формирующиеся при этом на ши-. нах совпадения БАП 1, суммируются сумматором 2, код В.1 с выходов кото рого на сумматоре 3 суммир"ется с содержимым предварительно обнулен- . ного регистра 5 и с выходов сумматора 3 и эта величина s поступает на информационные входы регистра 5 суммы и на первые входы блока 7 сравнения, где сравнивается с кодом числа (m+1) /2, хранящегося в регистре 6. Если s> (ш+1) /2, то на выходе блока 7 сравнения сформируется нулевой сигнал, который запрещает запись в регистр 5 суммы. Если з .(т+1) /2, то на выходе блока 7 сравнения сформируется единичный сигнал, который разрешает запись в регистр 5 величины s.

По спаду синхроимпульса, поступающего с тактового входа 20 устройства через элемент И 13 на вход управления сдвигом регистра 4, производится сдвиг содержимого этого регистра в сторону младших разрядов с заполнени (475: ем освобоциншегося старшего разряд» единицей. В эта же время инвертированный синхроимпульс поступает с выхода элемента НГ 15 на первые входы

5 всех элементов И 9, на вторые входы которых поступает поразрядно код с выходов счетчика 11 через дешифратор 10. Поскольку в первом такте счетчик 11 установлен в нуль, то в единицу установлен только бит на первом выходе дешифратора 1Р и соответственно этот единичный сигнал будет разрешать прохождение инвертированного синхроимпульса с выхода элемента

И 14 через первый элемент И 9. 1 группы на стробирующий вход триггера 8 .

По спаду инвертированного синхроимпульса триггер 81 установится в единичное или останется в нулевом состо- 20 янии в зависимости от сигнала, поступающего на его информационный вход (т.е. в зависимости от сигнала на выходе блока 7 сравнения) и во всех последующих тактах не меняет 25 своего состояния. Кроме того, по спаду инвертированного- синхроимпульса производится прибавление единицы к содержимому счетчика 11. Второй и последующие такты отрабатываются gp усФройством аналогично описанному способом.

Всего будет выполнено и тактов, причем каждый 1-й такт (1-"2,п) отличается от первого тем, что маска на входах маскирования БАП 1 формируется

35 следующим образом:

111...100...0, и-В а на входы признака опроса БАП 1 с 4р выходов триггеров 8 группы поступает код, старшие (1-1) разрядов которого совпадают со старшими (1-1) цифрами среднего, определенными в предыдущих тактах и зафиксированных на первых (1-1) триггерах 8 группы, а остальные разряды которого равны нулю. В счетчике 11 будет зафиксировано число (1-1), а соответственно и синхроимпульс с выхода элемента И 14 будет подаваться через элемент И 9 на стробирующий вход триггера 8В, а в.регистре 5 к началу такта будет зафиксировано суммарное количество чисел на хранящихся БАП 1, которые мень-55 ше, чем среднее и исключены из поиска.

После окончания и-го такта иа выходе переполнения счетчика 11 появится единичный сигнал, который устанавливает в нуль триг1ер 12 и устройство пере.:одпт н исходное состояние.

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

Устройство для выделения среднего из нечетного количества чисел, содержащее группу триггеров, счетчик и группу элементов И, причем вход начальной установки устройства соединен с входом установки в нулевое состояние триггеров группы, о т л и ч а ю— щ е е с я тем, что, с целью повьпйе— ния быстродействия, в него введены блок ассоциативной памяти, блок сравнения, два сумматора, регистр маски, регистр суммы, регистр управления, дешифратор, триггер управления, два элемента И и элемент НЕ, причем адресные и информационные входы устройства соединены соответственно с адресными и информационными входами блока ассоциативной памяти, выходы признака совпадения которого соединены с входами первого сумматора, выходы которого соединены с соответствующими входами первой группы второго сумматора, выходы которого соединены с соответствующими входами первой группы блока сравнения и с соответствующими информационными входами регистра суммы, выходы разрядов которого соединены с соответствующими входами второй группы второго сумматора, входы задания количества чисел устройства соединены с соответствующими информационными входами регистра управления, выходы разрядов которого соединены с соответствующими входами второй группы блока сравнения, выход которого соединен с информационными входами всех триггеров группы и с вхо" дом разрешения записи регистра суммы, вход установки в нулевое состояние которого объединен с входом установки в нулевое состояние счетчика и всех разрядов регистра маски, кроме старшего, и входом установки в единичное состояние старшего разряда регистра . маски и подключен к инверсному выходу триггера управления, прямой выход которого соединен с первыми входами первого и второго элементов И, тактовый вход устройства соединен с вторым входом первого элемента И, выход которого соединен с входом управления опросом блока ассоциативной памяти, сдвиговым входом регистра маски и

1647554

Составитель В.Горохов

Техред N,Äèäûê Корректор Н.Король

Редактор R.Áóãðåíêoâà

Заказ 1400 Тиржк 404 Подписное .

ВНИИЙИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Иосква, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г.ужгород, ул, Гагарина,101 через элемент НК, — с вторым входом второго элемента И, выход которого соединен с входом синхронизации регистра суммы, первыми входами всех элементов И группы и счетным входом счетчика, выходы разрядов которого соединены с соответствующими входами дешнфратора, i-й выход которого (i

1,2,..., n, n - количество разрядов 10 анализируемых чисел) соединен с вто.рым входом i-ro элемента И группы, выход которого соединен с входом синхронизации х-го триггера группы, выход которого является выходом i-го разряда среднего числа устройства и соединен с i входом признака опроса блока ассоциативной памяти, входы маски которого подключены к выходам соответствующих разрядов регистра маски, входы задания режимов чтения и записи устройства подключены соответственно к входам "Чтение" и "3a-.. пись" блока ассоциативной памяти, информационные выходы которого являются информационными выходами устройства, выход переполнения счетчика соединен с входом установки триггера управления в нулевое состояние, вход установки которого в единичное состояние, как и вход разрешения записи регистра управления, подключен к входу начальной установки устройства.