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

 

Изобретение относится к автоматике и вычислительной технике и предназначено для определения максимального и минимального чисел в последовательности чисел. Цель изобретения - повышение быстродействия. Устройство содержит регистр 1 - 7 коммутаторы 8 , 9, схемы сравнения 10 - 12, триггеры 13, 14, элементы НЕ 15, 16, элементы И 17, 18, элементы задержки 19 - 21. Введение новых элементов и связей для попарного сравнения чи- . сел во входной последовательности и обеспечение конвейерного режима работы позволяет повысить быстродействие устройства. 2 ил.

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

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

РЕСПУБЛИК

ÄÄSUÄÄ 1462291

А1 (5ц 4 G 06 F 7/00 7/04

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

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

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

ПРИ ГКНТ СССР

Н АBTQPCHQMY СВИДЕТЕЛЬСТВУ (21) 4269169/24-24 (22) 26.06.87 (46) 28.02.89. Бюл. М 8 (72) А.В.Василькевич, А.Г.Дмитриев, Ю.А.Кипецкий и И.Н.Яцимирский (53) 681.325(088.8) (56) Авторское свидетельство СССР

N - 771665, кл. G 06 F 7/04, 1978.

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

Р 849200, кл. G 06 F 7/00, 1979. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ ЗНАЧЕНИЙ ПОСЛЕДОВАТЕЛЬНОСТИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и предназначено для определения максимального и минимального чисел в последовательности чисел. Цель изобретения— повышение быстродействия. Устройство содержит регистр 1 — 7; коммутаторы 8, 9, схемы сравнения 10 — 12, триггеры 13, 14, элементы НЕ 15, 16, элементы И 17, 18, элементы задержки 19 — 21. Введение новых элементов и связей для попарного сравнения чисел во входной последовательности и обеспечение конвейерного режима работы позволяет повысить быстродействие устройства. 2 ил.!

462291

Изобретение относится к автомати" ке и вычислительной технике и предназначено для определения максимального и минимального чисел в последовательности чисел.

Цель изобретения — повышение быстродействия устройства за счет обеспечения конвейерного режима работы.

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

Устройство содержит регистры 1 — 7, коммутаторы 8 и 9, схемы сравнения

30 — 12, триггеры 13 и 14, элеменхы НЕ 15 и 16, элементы И !7 и 18, элементы задержки 19 — 21, информа" ционный вход 22, вход 23 тактовых импульсов, выход 24 минимального числа и выход 25,максимального числа устройства.

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

Перед началом работы в регистр 6 заносится минимальное возможное число, а в регистр 7 максимальное возможное число. Триггеры 13 и 14 устайовлены в нулевое состояние.

Последовательность сравниваемых чисел поступает на входную шину 22 устройства (фиг. 2 c ). Нечетные чисЛа в ряду поступающих чисел записываются в регистр 1 по передним фронтам тактовых импульсов, поступающих по входу 23 устройства на управляющий вход регистра 1 (фиг. 2 Б).

Четные числа в ряду поступающих чисел записываются в регистр 3 по тактовым импульсам, задержанным на полтакта с помощью элемента 19 задержки (фиг. 2 ь).

По этому же управляющему сигналу нечетные числа,из регистра 1 переписываются в регистр 2 (фиг. 2 r).

Таким образом, в регистры 2 и 3 записываются (2i-1)-тое и 2i-тое, числа, где i = 1, 2, 3,..., и/2. В первом такте, пара. чисел .сравнивается с помощью схемы 11 сравнения, кото.— рая формирует на своих выходах сигналы А З В и А В, по которым через коммутатор 8 проходит большее число, а через коммутатор 9 меньшее число йз пары чисел.

По передним фронтам тактовых имйульсов, задержанным на такт с помощью элемента 20 задержки (фиг.. 2 ), большее из пары чисел записывается в регистр 4, а меньшее — в регистр 5.

Во втором такте большее из пары чисел, выбранное в регистр 4, сравнивается с помощью схемы 10 сравнения с минимальным возможным числом в регистре 6. Одновременно во втором такте меньшее число, выбранное в регистр 5, сравнивается с помощью схемы 12 сравнения с максимальным возможным числом в регистре 7.

5 !

Если числа в регистре 4 больше числа в регистре 6, то,на выходе схемы 10 сравнения формируется уровень "1", в противном случае — уровень "0".

По переднему фронту тактового импульса, задержанного на такт с помощью элемента 21 задержки (фиг. 2е), !

20 сигнал с выхода схемы 10 сравнения заносится в триггер 13. Если число в регистре 4 больше числа в регистре 6, то триггер 13 устанавливается в единичное состояние и по переднему

25 фронту сигнала с выхода триггера 13 большее число переписывается из регистра 4 в регистр 6, в противном случае в регистре 6, остается предыдущее число.

Единичный сигнал с выхода триггера 13,разрешает прохождение через элемент И 17 сигнала с выхода элемента НЕ .15 и после окончания тактоВо втором такте одновременно со .сравнением большего из первой :пары чисел с числом, хранящимся в регистре 6 и меньшего из первой пары чисел с числом, хранящимся в регистре 7 производится сравнение третьего и четвертого чисел с помощью -.схемы 11 сравнения и записи большего из них. в регистр 4, а меньшего в регистр 5 по переднему фронту второго импульса последовательности (фиг. 2 9 ).

S5 ваго импульса производится сброс

35 триггера 13..

Элементы НЕ 15, И 17.и триггер 13 обеспечивают надежное формирование импульса записи в регистр 6.

Аналогично, если число в регистре 5 меньше числа в регистре 7, то на выходе схемы 12 сравнения формируется уровень "1", который поступает на D-вход триггера 14 и формируется импульс записи в регистр 7, в противном случае в регистре 7 остается предыдущее число.

146229!

В третьем такте с помощью схемы 11 сравнения сравниваются пятое и шестое числа, а с помощью схемы 10 сравнения сравнивается большее число из

5 пары — третье или четвертое и число, хранящееся в регистре, а с помощью схемы 12 сравнения сравнивается. меньшее число из этой же пары с числом, хранящимся в регистре 7. По переднему фронту второго импульса последовательности (фиг. 2 е ) в регистр 6 заносится наибольшее из четырех первых чисел, а в регистр 7 — наименьшее.

В последующих тактах устройство работает аналогично. За (n/2+1) тактов в регистр 6 выбирается наибольшее, а в регистр 7 — наименьшее числа из последовательности из и чисел.

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

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

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

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