Устройство для определения экстремумов

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах обработки информации , предназначенных для поиска локальных и абсолютного экстремумов функции. представленной массивом. Целью изобретения является повышение быстродействия устройства за счет последовательного конвейерного сравнения. Устройство содержит синхрон-регистры 1-6, из них четыре (1-4) с динамическим управлением, две схемы 7 и 8 сравнения, счетчик 9, три D-триггера 10-12, два элемента И 13 и 14, пять элементов 15-19 задержки. Устройство позволяет при последовательном прохождении чисел массива, представляющих какую-то функцию, через устройство осуществлять поиск абсолютного максимума либо минимума с его адресом, а также определять соответствующие локальные экстремумы с их адресами, выдача которых синхронизируется в зависимости от заданного режима 2 ил. с

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

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

РЕСПУБЛИК

m 4 G 06 F 7 04

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Мф (ру),, ОПИСАНИЕ ИЗОБРЕТЕНИЯ ц

Н АBTOPCHOMY СВИДЕТЕЛЬСТВУ ggg JJs (21) 4091068/24-24 (22) 14.07.86 (46) 07.04.88. Бюл. № 13 (72) А. В. Василькевич, А. Г. Дмитриев и Ю. А. Кипецкий (53) 681.325.5 (088.8) (56) Авторское свидетельство СССР № 746504, кл. G 06 F 7/04, 1978.

Авторское свидетельство СССР № 991412, кл. G 06 F 7/04, !981. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ЭКСТРЕМУМОВ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах обработки информации, предназначенных для поиска локальных и абсолютного экстремумов функции, „„SU„,, 13869 8 A 1 представленной массивом. Целью изобретения является повышение быстродействия устройства за счет последовательного конвейерного сравнения. Устройство содержит синхрон-регистры 1 — 6, из них четыре (1 — 4) с динамическим управлением, две схемы

7 и 8 сравнения, счетчик 9, три D-триггера 10 — 12, два элемента И 13 и 14, пять элементов 15 — 19 задержки. Устройство позволяет при последовательном прохождении чисел массива, представляющих какую-то функцию, через устройство осуществлять поиск абсолютного максимума либо минимума с его адресом, а также определять соответствующие локальные экстремумы с их адресами, выдача которых синхронизируется в зависимости от заданного режима 2 ил.

1386988

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

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

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

Устройство содержит регистры 1 — 4 с динамическим управлением, регистры 5 и 6, с1семы ? и 8 сравнения, счетчик 9„D-тригг ры 10 — 12, элементы И 13 и 14, элементы

1 — 19 задержки, информационные входы

2, вход 21 синхронизации устройства, в од 22 выбора режима, выходы 23 локальн х экстремумов, выход 24 стробирования лок льных экстремумов, выходы 25 абсолютных э стремумов, выходы 26 адреса абсолютного экстремума и выходы 27 адреса локального экстремума.

1

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

Перед началом работы регистры 1 — 6, счетчик 9 и триггеры 10 — 12 устанавливак)тся в нулевое состояние. На вход выбора режима подаетсся сигнал «Лог. 1» при поиске максимума либо сигнал «Лог.0» при поиске минимума.

Причем при наличии логической «1» на управляющих выходах схем 7 и 8 сравнения формируются единичные сигналы, если число соответственно на первом и втором входах (выходы регистров 1 и 3) меньше числа соответственно на втором и первом входах (выходы регистров 2 и 4).

При наличии логического «О» на управляющих выходах схем 7 и 8 cðàâíåíèÿ формируются единичные сигналы, если число соответственно на первом и втором входах больше числа соответственно на втором и первом входах.

Рассмотрим работу устройства на примере поиска абсолютного максимума.

Г!о первому синхроимпульсу (фиг. 2а), период следования которых At) 1;Р+Ь2+

+tH+tpz, где tcp — время сравнения чисел схемой сравнения; Ь2 — время срабатывания триггера, 1н — время задержки элемента И; tpq — время срабатывания регистра, поступающему по входу синхронизации устройства 21, первое число, поступаюгцее по входу 20, заносится в регистр 1.

В следующем такте по первому синхроимпульсу, задержанному на элементе 15 задержки на такт (фиг. 2 б), время задержки которого tis

10 1 5

2О

5 »

58

55 мы сравнения формируется единичный сигнал. если число в регистре 1 меньше числа в регистре 2. Результат сравнения заносится в следующем такте в триггер 10 по первому синхроимпульсу, задержанному элементом 16 задержки на такт (фиг. 2в), время задержки которого (16(1д. Результат сравнения показан на фиг. 2д. Все сигналы, значения которых зависят от соотношения сравниваемых чисел, показаны штриховыми линиями. По этому же синхроимпульсу (фиг. 2в), первое число заносится в регистр 3 прибавляется единица к содержимому счетчика 9 и переписывается нулевое значение счетчика 9 в регистр 5. Если второе число меньше первого, то первое число является локальным максимумом.

В этом случае импульс, задержанный 19 элементом задержки на время, необходимое для записи в триггер 10 и регистр 3, проходит через элемент И 13, на других входах которого находятся сигналы логической «1» с прямого выхода триггера 10 и инверсного выхода триггера 11, на выход

24 синхронизации локальных экстремумов.

По этому сигналу (фиг. 2ж) из регистра 3 по выходу 23 считывается значение foêàëüного . максимума, а по выходу 27 из регистра 5 — адрес локального максимума.

В следующем такте по первому синхроимпульсу, задержанному элементом 17 задержки (фиг. 2г) время задержки которого tip(ti — t4, результат сравнения первого и второго чисел переписывается из триг::ра 10 в триггер 11. Этот же синхроимпульс проходит через элемент И 14, на второй вход которого поступаст разрешение с инверсного выхода триггера 12, и производит перезапись первого числа из регистра 3 в регистр 4 и его адреса из регистра 5 в регистр 6.

В этом же такте по второму синхроимпульсу (фиг. 2в) в триггер 10 записывается результат сравнения второго и третьего чисел, в регистр 3 заносится второе чис..о, в регистр 5 — содержимое счет.ика 9, к содержимому счетчика 9 прибавляется единица.

Если второе число больше первого и третьего чисел, оно является локальным максимумом, и на входах триггеров 10 и

11 будут логические «1», которые разрешают прохождение импульса с выхода элемента 19 задержки, через элемент И 13 на выход 24 стробирования локальных экстремумов (фиг. 2ж). По этому сигналу из регистра 3 считываются второе число по выходу

23 и его адрес по выходу 27.

Второе число в регистре 3 сравнивается с первым числом в регистре 4 с помощью схемы 8 сравнения, и результат сравнения чисел (фиг. 2и) по синхроимпульсу, задержанному элементом 18 задержки, время задержки которого tie(tiz — t.2 (фиг. 2з), записывается в триггер 12.

1386988

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

Если число в регистре 3 больше или равно числу в регистре 4, то на выходе схемы 8 сравнения будет логический «О», который записывается в триггер 12. Логическая «1» с инверсного выхода триггера 12 разрешает прохождение синхроимпульса с выхода элемента 17 задержки через элемент И 14 на синхровходы регистров 4 и 6, и число из регистра 3 переписывается в регистр 4, а его адрес — из регистра 5 в регистр 6.

Дальнейшая работа устройства происходит аналогично.

По последнему (n-му) синхроимпульсу (фиг. 2а) последнее число записывается в регистр 1 и сравнивается с помощью схемы

7 сравнения с (и-1)-м числом, записанным в регистр 2 по (п — 1)-му импульсу (фиг. 2б).

В следующем такте результат сравнения по (n — 1)-му импульсу (фиг. 2в) заносится в триггер !О, а значение (и — 1)-го числа— в регистр 3, результат сравнения (п — 1) -го и (п — 2)-ro чисел переписывается из триггера 10 в триггер 11. Если (n — 1) -е число больше п-го и (п — 2)-го чисел, оно является локальным максимумом, и сигналы с выходов триггеров 10 и 11 разрешают прохождение (n — 1)-го импульса с выхода элемента 19 задержки через элемент И

13 на выход 24 синхронизации локальных экстремумов (фиг 2ж) .

В следующем такте значение (и — 1) -го числа, записанного в регистр 3, сравнивается с помощью схемы 8 сравнения с содержимым регистра 4, в котором хранится текущий обсолютный максимум. Если (и — 1)-е число больше или равно числу в регистре 4, то на выходе схемы 8 сравнения будет логический «О», который записывается в триггер 12 по сигналу с выхода элемента 18 задержки (фиг. 2з), и логическая «1» с выхода триггера 12 разрешает прохождение импульса с выхода элемента

17 задержки (фиг. 2г) через элемент И

14 на входы записи регистров 4 и 6 (фиг. 2к).

Из регистра 3 (п — 1)-е число переписывается в регистр 4, а его адрес — из регистра 5 в регистр 6. В последнем такте аналогично сравнивается и-е число, и в результате обработки в регистр 4 выбирается абсолютный максимум, а в регистр 6— его адрес.

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

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

В-входом второго D-триггера, инверсный выход которого соединен с вторым входом первого элемента И, третий вход которого соединен с выходом четвертого элемента задержки, инверсный выход третьего D-триггера соединен с вторым входом второго элемента И, выход которого соединен с входами синхронизации четвертого регистра с динамическим управлением и шестого регистра, выходы разрядов четвертого регистра с динамическим управлением являются выходами абсолютного экстремума устройства, выходы разрядов шестого регистра являются выходами адреса абсолютного экстремума устройства.

1386988

Составитель А. Александров

Редактор А. Козориз Техред И. Верес Корректор В. Бутяга

Заказ 1222/47 Тираж 704 Подписное

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

113035, Москва, 7K — 35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4