Устройство для определения экстремумов Советский патент 1988 года по МПК G06F7/04 

(Л

с

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

СА 00 О5

:о

00

оо

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

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

Устройство содержит регистры 1-4 с динамическим управлением, регистры 5 и 6, 7 и 8 сравнения, счетчик 9, D-триг- гфы 10-12, элементы И 13 и 14, элементы 15-19 задержки, информационные входы 2D, вход 21 синхронизации устройства, вход 22 выбора режима, выходы 23 локальных экстремумов выход 24 стробирования локальных экстремумов, выходы 25 абсолютных экстремумов, выходы 26 адреса абсолют- нЬго экстремума и выходы 27 адреса ло- кЬльного экстремума.

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

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

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

При наличии логического «О на управляющих выходах схем 7 и 8 сравнения формируются единичные сигналы, если число соответственно на первом и втором входах больше числа соответственно на втором и пер вом входах.

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

По первому синхроимпульсу (фиг. 2а), период следования которых At tcpH-tT2+ - -tH-t-tp2, где tcp - время сравнения чисел схемой сравнения; tra - время срабатывания триггера, in - время задержки элемента И; tp2 - время срабатывания регистра, поступающему по входу синхронизации устройства 21, первое число, поступающее по входу 20, заносится в регистр 1.

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

0

5

0

5

y

З

0

5

0

5

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

В следующем такте по первому синхроимпульсу, задержанному элементом 17 задержки (фиг. 2г) время задержки которого ti7 ti6-14, результат сравнения первого и второго чисел переписывается из триггера 10 в триггер П. Этот же синхроимпульс проходит через элемент И 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 задержки, время задержки которого (фиг. 2з), записывается в триггер 12.

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

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

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

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

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

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

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

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

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

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

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

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

5 элемента задержки, выход которого соединен с входом синхронизации второго регистра с динамическим управлением и с входом второго элемента задержки, выход которого соединен с входами синхронизации первого D-триггера, третьего регистра с ди0 намическим управлением и пятого регистра, со счетным входом счетчика и с входами третьего и четвертого э. 1ементов задержки, выход третьего элемента задержки соединен с входом синхронизации второго D- триггера, с первь г1 входом второго элемен5 та И и с входом пятого элемента задержки, выход которого соединен с входом синхронизации третьего D-триггера, D-вход которого соединен с выходом второй схемы сравнения, вторая группа информацион„ ных входов которой соединена с выходами разрядов третьего регистра .с динамическим управлением, выход первой схемы сравнения соединен с D-входом первого D- триггера, прямой выход которого соединен с первым входом первого элемента И и

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

5

Фи.г