Устройство для выделения среднего из нечетного количества чисел Советский патент 1991 года по МПК G06F7/06 

31647554

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

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

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

Устройство содержит блок 1 ассоциативной памяти (ВАЛ) 1, сумматоры 2 и 3, регистр 4 маски, регистр 5 суммы, регистр 6 управления, блок 7 сравнения, группу триггеров 8.1-8.П

10

мая рекурсивно п раз, приведенная процедура позволяет получить значение (bЈ. -bn за п тактов.

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

В БАП 1 записываются анализируемые числа, которые поступают по входам 16 в сопровождении адреса, поступающего по входу 17 и сигнала записи по входу 21 в регистр 6 записывается величина (т+1)/2 (т - количество анализируемых чисел), счетчик 11, регистр 5 и триггеры 8.1-S.n и 12 уста(п - количество разрядов анализируе 15 навливаются в нулевое состояние, в мых чисел), группу элементов И 9И- регистре 4 старший разряд устанавли- 9.п, дешифратор 10, счетчик 11, триг- вается в единичное, а остальные раз- гер 12 управления, элементы И 13 и 14, ряды в нулевое состояние. элемент НЕ 15, информационные 16 и , Выполнение приведенной процедуры адресные 17 входы, вход 18 начальной 20 начикается с того что П°Д Действи- установки, вход 19 задания количества чисел, входы задания режимов чтения 20 и записи 21, тактовый вход 22, информационные выходы 23, выходы 24.1-24.п разрядов среднего числа. . .25

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

ем синхроимпульса, поступающего с тактового входа 20 устройства через открытый единичным потенциалом ;с прямого выхода триггера 12 элемент И 13 на вход управления опросом БАП 1 инициируется его опрос. При этом на входы признака опроса БАП 1 поступают с выходов триггеров 8 n-разрядный нулевой код, а на

входы маскирования - код 10...О

ГА,,АЛ. . . .А.у, неупорядоченное мно-30.

. г 2- , J. . с выходов регистра 4 маски. Таким

;жество чисел аjh j 1,m, ajjeЈo,l), i-T7n, ti - разрядобразом, в первом такте БАП 1 выj . -ji-t 1/ , , тГГс(7л %1- полняет ассоциативный поиск чисел ность, и пусть, В bib...bn, b:ti.U, i V - J с нулем в старшем разряде (выделесреднее (медиана) множество Й(ВС52). Множество чисел изQ меньших Bs яв- 35 ляется объединением ин.подмно И

40

ние множества Н). Сигналы совпадения, формирующиеся при этом на шинах совпадения БАП 1, суммируются сумматором 2, код RJ с выходов кото- рого на сумматоре 3 суммируется с содержимым предварительно обнулен- . ного регистра 5 и с выходов сумматора 3 и эта величина s поступает на информационные входы регистра 5 суммы и на первые входы блока 7

жеств Н: - Ј2, определяемых следующим

1

образом: Н . и (A} | (а

@b(C)0, aTk b 1, т.е. множество Н объединяет числа AJ, совпадающие старшими (i-1) разрядами с соответствующими разрядами медианы В и имеющие в i-м разряде нуль при единичном зна- сравнения, где сравнивается с кодом чении 1-го разряда среднего В. Тогда числа (tn+1)/2, хранящегося в регист- справедливо следующее: пусть извест- ре 6. Если s| (m+1)/2, то на выходе ны 1 старших разрядов b jba. .b сред- блока 7 сравнения сформируется нуле- него В, известны также количества R., R.. ..,Rg элементов, составляющих соответственно множества Hj, H.,.,Hg И необходимо определить значение

(1+1)-го разряда В. Положим, 0 и выделим множество Hg, содержащее Rpi| элементов. Очевидно, что если

Ј±J

EL-RB m+ /2, то предположение,

50

вой сигнал, который запрещает запись в регистр 5 суммы. Если s(m+1)/2, то на выходе блока 7 сравнения сформируется единичный сигнал, который разрешает запись в регистр 5 величины s. По спаду синхроимпульса, поступающего с тактового входа 20 устройства че- 55 рез элемент И 13 на вход управления

. -- -ч -, . сдвигом регистра 4, производится что Ь, является верным, и, следо- сдвиг содержимого этого регистра в вательно, +,0, а Н( -0. Повторяв- сторону младших разрядов с заполнени

мая рекурсивно п раз, приведенная процедура позволяет получить значение (bЈ. -bn за п тактов.

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

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

ем синхроимпульса, поступающего с тактового входа 20 устройства через открытый единичным потенциалом ;с прямого выхода триггера 12 элемент И 13 на вход управления опросом БАП 1 инициируется его опрос. При этом на входы признака опроса БАП 1 поступают с выходов триггеров 8 n-разрядный нулевой код, а на

входы маскирования - код 10...О

.

ние множества Н). Сигналы совпадения, формирующиеся при этом на шинах совпадения БАП 1, суммируются сумматором 2, код RJ с выходов кото- рого на сумматоре 3 суммируется с содержимым предварительно обнулен- . ного регистра 5 и с выходов сумматора 3 и эта величина s поступает на информационные входы регистра 5 суммы и на первые входы блока 7

сравнения, где сравнивается с кодом числа (tn+1)/2, хранящегося в регист- ре 6. Если s| (m+1)/2, то на выходе блока 7 сравнения сформируется нуле-

сравнения, где сравнивается с кодом числа (tn+1)/2, хранящегося в регист- ре 6. Если s| (m+1)/2, то на выходе блока 7 сравнения сформируется нуле-

вой сигнал, который запрещает запись в регистр 5 суммы. Если s(m+1)/2, то на выходе блока 7 сравнения сформируется единичный сигнал, который разрешает запись в регистр 5 величины s. По спаду синхроимпульса, поступающего с тактового входа 20 устройства че- рез элемент И 13 на вход управления

5164

ем освободившегося старшего разряда единицей. В это же время ипвертиро- ванный синхроимпульс поступает с выхода элемента НЕ 15 на первые входы всех элементов И 9, на вторые входы которых поступает поразрядно код с выходов счетчика 11 через дешифратор Ю. Поскольку в первом такте счетчик 11 установлен в нуль, то в единицу установлен только бит на первом выходе дешифратора 10 и соответственно этот единичный сигнал будет разрешать прохождение инвертированного синхроимпульса с выхода элемента И 14 через первый элемент И 9.1 группы на стробирующий вход триггера 8. По спаду инвертированного синхроимпульса триггер 8i установится в единичное или останется в нулевом состоянии в зависимости от сигнала, поступающего на его информационный вход (т.е. в зависимости от сигнала на выходе блока 7 сравнения) и во всех последующих тактах не меняет своего состояния. Кроме того, по спаду инвертированного- синхроимпульса производится прибавление единицы к содержимому счетчика 11. Второй и последующие такты отрабатываются устройством аналогично описанному способом.

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

,111...100...О,

е п-в

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

ет в нуль триггер 12 и устройство переводит в исходное состояние.

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

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

через элемент НЕ,- с вторым входом i второго элемента И, выход которого соединен с входом синхронизации регистра суммы, первыми входами всех элементов И группы и счетным йходом счетчика, выходы разрядов которого соединены с соответствующими входами дешифратора, i-й выход которого (t 1,2,,..n, n - количество разрядов анализируемых чисел) соединен с втог- рым входом 1-го элемента И группы, выход которого соединен с входом синхронизации 1-го триггера группы, выход которого является выходом 1-го разряда среднего числа устройства и соединен с i-м входом признака опроса

блока ассоциативной памяти, входы маски которого подключены к выходам соответствующих разрядов регистра маски, входы задания режимов чтения и записи устройства подключены соответственно к входам Чтение и За-, пись блока ассоциативной памяти, информационные выходы которого являются информационными выходами устройства, выход переполнения счетчика соединен с входом установки триггера управления в нулевое состояние, вход установки которого в единичное состояние, как и вход разрешения записи регистра управления, подключен к входу начальной установки устройства.

Изобретение относится к вычисли тельной технике. Цель изобретения - повышение быстродействия. Устройство содержит блок ассоциативной памяти (БАЛ) 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 ил. (Л & СЛ &п Сь