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

 

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - упрощение устройства. Устройство содержит г log2n ступеней 1 ячеек анализа (ЯА) 2, где х - ближайшее целое, не меньшее х, каждая ячейка анализа содержит коммутатор 3, элемент ИЛИ 4, триггеры 5, 8, 9, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 6,7,10, кроме того, устройство содержит элемент НЕ 11, входы чисел 12, тактовый вход 13, управляющие входы 14, входы синхросигнала передачи знаков чисел 15, вход выбора режима 16, выход 17. ЯА 2 соединены в виде бинарного дерева, на входы каждого ЯА подаются два числа прямым последовательным кодом , начиная со старшего разряда, старший разряд - знаковый, из которых ЯА передает на свой выход максимальное или минимальное (в зависимости от режима). В следующем (1+1)-м такте ЯА первой ступени анализируют (1+1)-й разряд всех чисел, а ЯА второй ступени - i-й разряд чисел, выбранных на предыдущем такте ЯА, первой ступени и т. д. 2 ил, 1 табл. сл С

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

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

РЕСПУБЛИК (51)5 G 06 F 7/02

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ЬЭ (л) О .фь. (21) 4817372/24 (22) 28.02.90 (46) 15.04.92. Бюл. N 34 (71) Житомирский филиал Киевского политехнического института (72) Л.Е.Горкуша и Т.Н.Черная (56) Авторское свидетельство СССР

N 526888, кл. G 06 F 7/06. 1978.

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

¹-966690, кл. G 06 F 7/02, 1982.

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

N 1520509, кл. G 06 F 7/06, 1988. (54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ЭКСТРЕМАЛЬНОГО ЧИСЛА (57) Изобретение относится к автоматике и вычислительной технике, Цель изобретения — упрощение устройства. Устройство содержит r=)logzn(ступеней 1 ячеек анализа(ЯА)

2, где )х(— ближайшее целое. не меньшее х, Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных вычислительных устройств, предназначенных для сортировки массивов данных в реальном масштабе времени.

Известно устройство для выделения экстремельного из Й п1-разрядных двоичных чисел, содержащее матрицу ячеек, каждая из которых содержит элементы И, ИЛИ, элементы запрета (1).

Недостатком данного устройства является его сложность.

Другое устройство для выделения экстремального из N m-разрядных двоичных чисел содержит N m-разрядных регистров, групп элементов И, m-входовых элементов

„„5U„„1762304 А1 каждая ячейка анализа содержит коммутатор 3, элемент ИЛИ 4, триггеры 5, 8, 9, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 6,7, 10, кроме того, устройство содержит элемент НЕ 11, входы чисел 12, тактовый вход 13, управляющие входы 14, входы синхросигнала передачи знаков чисел 15, вход выбора режима

16, выход 17. ЯА 2 соединены в виде бинарного дерева, на входы каждого ЯА подаются два числа прямым последовательным кодом, начиная со старшего разряда, старший разряд — знаковый, из которых ЯА передает на свой выход максимальное или минимаRьное (в зависимости от режима), В следующем (!+1)-м такте ЯА первой ступени анализируют(!+1)-й разряд всех чисел. а ЯА второй ступени — -й разряд чисел, выбранных на предыдущем такте ЯА, первой ступени и т. д, 2 ил, 1 табл, ИЛИ, элементов ИСКЛЮЧАЮЩЕЕ ИЛИ. триггеров, N-входовый элемент ИЛИ, шины управления поразрядным сравнением (2).

Недостатком устройства является его

СложнОСть.

Наиболее близким является устройство для сортировки чисел, содержащее ) —. (ячеN

2 ек анализа i-го типа (N — количество сортируемых чисел, i = 1, 2...„)togzN(, )Х(— ближайшее целое, не меньшее Х), счетчик, )logzN(— 1 формирователей импульсов, вход начальной установки, тактовый вход, информационные входы, выходы отсортированных чисел, выход окончания работы, ячейка анализа i-го типа содержит две группы регистров, элементы сравнения, комму1762304 таторы, входы управления записью, информационные входы и выходы (3).

Недостатком этого устройства является его сложность.

Целью изобретения является упроще- 5 ние устройства.

Поставленная цель достигается тем, что устройство, содержащее г=)! одгй(ступеней ячеек анализа (N — количество сравниваемых чисел, )Х(— ближайшее целое, не мень- 10 шее X), i-ая группа ячеек анализа (i = 1, 2, ..., N

r) содержит ) —.(ячеек анализа, вход j-го

2 числа устройства (j =1, 2, „„N) соединен с (2 — mod2j)-ым информационным входомД(-ой ячейки анализа первой ступени, выход 1-ой ячейки анализа k-ой ступени (I = 1, 2, ..., N

) — (, k = 1, 2...„r — 1) соединен с (2 — modal)-ым

20 информационным входом ) — (-ой ячейки анализа (k+1)-ой ступени, входы начальной установки ячеек анализа первой ступени соединены с первым управляющим входом устройства, тактовый вход устройства

25 соединен с тактовыми входами всех ячеек анализа нечетных ступеней, выход r-ой ступени ячеек анализа является выходом устройства, каждая ячейка анализа содержит два триггера и коммутатор, о т л и ч а ю щ е30 е с я тем, что, с целью упрощения устройства, оно содержит элемент НЕ, а каждая ячейка анализа — третий триггер, элемент

ИЛИ и три элемента ИСКЛЮЧАЮЩЕЕ

ИЛИ, причем,k+1)-ый управляющий вход

35 устройства соединен со входами начальной установки всех ячеек анализа (k+1)-ой ступени, тактовый вход устройства через элемент НЕ соединен с тактовыми входами всех ячеек анализа четных ступеней, i-ый

40 вход синхросигнала передачи знаков чисел соединен со входами синхронизации первых триггеров всех ячеек анализа i-ой ступени, вход выбора режима устройства соединен с первыми входами первых эле45 ментов ИСКЛЮЧАЮЩЕЕ ИЛИ всех ячеек анализа, в каждой ячейке анализа ее вход начальной установки соединен со входом установки в единичное состояние первого триггера и со входом установки в нулевое

50 состояние второго триггера, выход которого соединен со входом синхронизации третьего триггера, выход которого соединен со вторым входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен с

55 управляющим входом коммутатора, выход которого является выходом ячейки анализа, первый и второй информационные входы ячейки анализа соединены соответственно с первым и вторым информационными входами коммутатора, первым и вторым входами элемента ИЛИ и второго элемента

ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен со входом установки в единичное состояние второго триггера, информационный вход третьего триггера соединен с выходом третьего элемента ИСКЛЮЧАЮЩЕЕ

ИЛИ, первый и второй входы которого соединены соответственно с первым информационным входом ячейки анализа и инверсным выходом первого триггера, информационный вход которого соединен с выходом элемента ИЛИ.

На фиг.1 представлена функциональная схема устройства; на фиг.2 — временные диаграммы его работы.

Устройство для выделения экстремального числа содержит r = )!оцгй(ступеней 1 ячеек анализа (N — количество сравниваемых чисел, )Х(— ближайшее целое, не меньшее X), i-ая группа ячеек анализа (i = 1, 2, ..., N г) содержит ) —.(ячеек анализа 2, каждая

2 ячейка анализа 2 содержит коммутатор 3, элемент ИЛИ 4, первый триггер 5, третий элемент ИСКЛ ЮЧАЮ ЩЕ Е ИЛИ 6, второй элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 7, второй триггер 8, третий триггер 9, первый элемент

ИСКЛЮЧАЮЩЕЕ ИЛИ 10, кроме того, устройство содержит элемент НЕ 11, N входов чисел 12, тактовый вход 13, управляющие входы 14, входы синхросигнала передачи знаков чисел 15, вход выбора режима 16, выход 17 устройства.

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

На входы чисел 12 устройства сравниваемые m-разрядные числа поступают прямым последовательным кодом, начиная со старших разрядов, старший разряд — знаковый.

Каждая ячейка анализа 2 производит выделение экстремального из пары чисел а и b в соответствии с табл.

Рассмотрим работу ячейки анализа 2 для режима выделения максимального числа (на вход выбора режима 16 устройства подается "0").

Перед началом сравнения пары m-разрядных чисел импульсом единичного уровня, поступающим с соответствующего управляющего входа 14, устройства, триггер

5 устанавливается в "0"), триггер 8 устанавливается в "0". В это время на первом и втором информационных входах 12 и 12 ячейки анализа 2 соответственно присутствует единичный уровень и на тактовом входе 13 устройства также единичный уровень.

1762304

50

Триггер 9 сохраняет предыдущее состояние. Сигнал с выхода триггера 9 через элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 10 без изменения поступает на управляющий вход коммутатора 3. На выход коммутатора 3 будет передаваться "1" либо с первого, либо со второго информационного входа коммутатора 3 (в зависимости от предыдущего состояния триггера 9) по отрицательному перепаду сигнала, поступающего с тактового входа 13 устройства. При появлении сравниваемых чисел а и Ь на первом и втором информационных входах 12! и 122 соответственно (при этом на тактовом входе 13 устройства- — единичный уровень) производится, начиная со старшего разряда, последовательный поразрядный анализ исследуемых чисел. Пусть в старшем разряде чисел имеется неравенство, При этом на выходе элемента ИЛИ 4 устанавливается

"1", которая поступает на информационный вход триггера 5. Во время анализа старших (знаковых) разрядов сравниваемых чисел а и Ь на вход синхронизации триггера 5 поступает импульс единичного уровня с соответствующего входа синхросигнала передачи знаков чисел 15< устройства. По положительному перепаду синхросигнала передачи знаков чисел, поступающего на вход синхронизации триггера 5 со входа 15! устройства, триггер 5 на инверсном выходе сохраняет "0", который поступает на элемент

ИСКЛЮЧАЮЩЕЕ ИЛИ 6, При этом на выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 6 передается число а с первого информационного входа 12,. На выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 7 устанавливается "1", которая поступает на вход установки в единичное состояние триггера 8, на выходе которого появляется "1". По этому положительному перепаду в триггер 9 производится запись знакового разряда числа а, Сигнал с выхода триггера 9 через элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 10 без изменения поступает на управляющий вход коммутатора 3. Если значение знакового разряда числа а равно О, триггер 9 устанавливается в "О" и на выход коммутатора 3 по отрицательным перепадам сигнала, поступающего с тактового входа 13 устройства на тактовый вход коммутатора 3, передается число а; если в старшем разряде числа 1— то число b, В случае, если значения знаковых разрядов чисел а и Ь равны 1, на инверсном выходе триггера 5 также сохраняется "О", при этом выход элемента ИСКЛЮЧАЮЩЕЕ

ИЛИ 6 повторяет число а. При равенстве значений разрядов чисел а и b триггер 9 сохраняет предыдущее сос.ояние. На вы5

25 ход коммутатора 3 будет передаваться либо число а, либо число Ь (a зависимости от предыдущего состяония триггера 9). В момент несовпадения разрядов чисел а и b триггер 8 переключается в "1 по сигналу с элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 7. При переключении триггера 8 из "О" в "1" производится запись значения разряда числа а в триггер 9. Если значение этого разряда числа а равно О, на выход коммутатора 3 передается число а в соответствии с сигналами на управляющем и тактовом входах коммутатора 3; если значение разряда числа а равно 1 — число Ь.

В случае, если значения знаковых разрядов чисел а и Ь равны О, на выходе элемента ИЛИ 4 устанавливается "О", который поступает на информационный вход триггера 5. По положительному перепаду сигнала, поступающего на вход синхронизации триггера 5 со входа 151 устройства, на инверсном выходе триггера 5 устанавливается "1" и на выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ

6 передается инверсное значение числа а.

При равенстве значений разрядов чисел а и

b триггер 9 сохраняет предыдущее состояние. При этом на выход коммутатора 3 будет передаваться либо число а, либо число Ь (в зависимости от предыдущего состояния триггера 9). В момент несовпадения разрядов чисел а и Ь триггер 8 переключается в

"1" посигналусэлемента ИСКЛЮЧАЮЩЕЕ

ИЛИ 7. При переключении триггера 8 из "О" в "1" производится запись инверсного значения числа а в триггер 9. Если сигнал на управляющем входе коммутатора 3 — О, на

его выход передается число а, если 1 — число

Если сравниваемые числа а и Ь равны, то триггер 9 будет сохранять предыдущее состояние на протяжении всего времени анализа чисел и на выход коммутатора 3 будет передаваться либо число а, либо число

Ь.

Если требуется выделить минимальное из исследуемых чисел, то на первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 10 со входа выбора режима 16 устройства поступает

"1"; последовательный поразряднь.й анализ сравниваемых чисел производится аналогично. Тогда на управляющий вход коммутатора 3 поступает инверсное значение выхода триггера 9, что соответствует передаче на выход коммутатора 3 минимального числа.

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

Устройство для выделения экстремального числа, содержащее r = )log, и(ступеней ячеек анализа, где n — количество сравниваемых чисел, )х(— ближайшее целое, не мень1762304

Выбор ма ксимал ьно го ч исла

Выбор минимального числа и м е ч а н и е: x — на выходе ячейки анализа 2 может быть как число а, так и число Ь. шее x, i-я группа ячеек анализа (где i = 1, 2, ..., г) содержит )и/2 (ячеек анализа, вход j-го числа устройства (где j = 1, 2, ..., n) соединен с (2 — тоб2))-м информационным входом

1i/2(-й ячейки анализа первой ступени, вы- 5 ход I-й ячейки анализа К-й ступени (где! = 1, 2, ..., )n/2 (, k = 1, 2, ..., r-1) соединен с (2 — madge)-м информационным входом )1/2(-й ячейки анализа (К+1)-й ступени, входы начальной установки ячеек анализа первой 10 ступени соединены с первым управляющим входом устройства, тактовый вход устройства соединен с тактовыми входами всех ячеек анализа нечетных ступеней, выход ячейки анализа r-й ступени является выхо- 15 дом устройства, каждая ячейка анализа содержит два триггера и коммутатор, о т л и ча ю щ е е с я тем, что, с целью упрощения устройства, оно содержит элемент НЕ, а каждая ячейка анализа — третий триггер, 20 элемент ИЛИ и три элемента ИСКЛЮЧАЮЩ Е Е ИЛИ, причем(К+1)-й управляющий вход устройства соединен с входами начальной установки ячеек анализа (К+1)-й ступени, тактовый вход устройства через элемент НЕ 25 соединен с тактовыми входами всех ячеек анализа четных ступеней, i-й вход синхросигнала передачи знаков чисел соединен с входами синхронизации первых триггеров всех ячеек анализа i-й ступени, вход выбора 30 режима устройства соединен с первыми входами первых элементов ИСКЛЮЧАЮЩЕЕ

ИЛИ всех ячеек анализа, в каждой ячейке анализа ее вход начальной установки соединен с входом установки в единичное состояние первого триггера и с входом установки в нулевое состояние второго триггера, выход которого соединен с входом синхронизации третьего триггера, выход которого соединен с вторым входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен с управляющим входом коммутатора, выход которого является выходом ячейки анализа, первый и второй информационные входы ячейки анализа соединены соответственно с первым и вторым информационными входами коммутатора, первым и вторым входами элемента ИЛИ и второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен с входом установки второго триггера в единичное состояние, информационный вход третьего триггера соединен с выходом третьего элемента

ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второй входы которого соединены соответственно с первым информационным входом ячейки анализа и инверсным выходом первого триггера, информационный вход которого соединен с выходом элемента

ИЛ И.

1762304

f4)

I5r

E я ллр

f2 р 4р

Р5р Ц, 570dbj а 21

i2

Фиг. 2

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

Техред М.Моргентал Корректор О. Густи

Редактор А,Бер

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101

Заказ 3260 Тираж Подписное

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

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