Устройство для экстремальной фильтрации

 

Изобретение относится к вычислительной технике. Цель изобретения - повышение быстродействия. Операция экстремальной фильтрации определяется как нахождение вектора B такого, что B<SB POS="POST">I</SB>=MAX{A<SB POS="POST">I</SB>,A<SB POS="POST">I+1</SB>,...,A<SB POS="POST">I+N-1</SB>}, где I=1,2,...,M-N+1, A=(A<SB POS="POST">1</SB>,A<SB POS="POST">2</SB>,...,A<SB POS="POST">M</SB>)-исходный вектор длиной M, N -длина апертуры. Устройство содержит счетчики 1-4, блок 5 памяти, регистры 6-9, элемент 10 сравнения, RS-триггер 11, D-триггер 12, регистр 13 сдвига, элементы И 14-18, элементы ИЛИ 19-21, одновибраторы 22-25, элементы НЕ 26,27, генератор 28 импульсов, делитель 29 частоты, вход 30 выбора типа фильтрации, вход 31 начальной установки, группы 32 и 33 входов задания длины массива и длины апертуры, вход 34 запуска, группу 35 информационных выходов, выход 36 окончания работы, выход 37 синхронизации. В блоке 5 памяти хранится исходный массив. С помощью элемента 10 сравнения определяется максимальное из N первых чисел массива. Затем начальный адрес массива, хранящийся в счетчике 1, увеличивается на единицу, и производится поиск максимального из N чисел, начиная с второго ит.д. 1 ил.

СОЮЗ С08ЕТСНИХ

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

РЕСПУБЛИН (5D 4 С 06 F 7/04

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

ГОСУДАРСТ8ЕННЫЙ KOMHTET

flQ ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ- СССР

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4405322/24-24 (22) 06.04.88 (46) 07.! 1.89, Бюл. К- 41 (71) Львовский политехнический институт им.Ленинского комсомола (72) Л.В.Василькевич, В.2!.Крищипп1н, В.С.11итьков и Н.В.Черкасский (53) 681.325.5(088 ° 8) (56) Авторское свидетельство СССР

t> 77 1665, кл. С Об F 7/04, 1978.

Авторское свидетельство СССР !! 1339547, кл. G Об F 7/04, 1986. (54) УСТРОЙСТВО ДЛЯ ЭКСТРЕИАЛЬНОЙ

ФИЛЬТРАЦИИ (57) Изобретение относится к вычислительной технике. Цель изобретения — повышение быстродействия. Операция экстремальной фильтрации определяется как нахождение вектора В такого, что Ь;= иа1сс 1а.;,а;„ (а,,а,...,а„). — исходный вектор

„„80„„1520507 А 1

2 . длиной n n — длина апертуры. Устройство содержит счетчики 1-4, блок 5 памяти, регистры 6-9, элемент 10 сравнения, RS-триггер 11, 9-триггер 12, регистр 13 сдвига, элементы И 14-18, элементы ИЛИ 19-21, одновибраторы

22-25, элементы НЕ 26,27, генератор

28 импульсов, делитель 29 частоты, вход 30 выбора типа фильтрации, вход

31 начальной установки, группы 32 и 33 входов задания длины массива и длины апертуры, вход 34 запуска, группу 35 информационных выходов, выход 36 окончания работы, выход 37 синхронизации. В блоке 5 памяти хранится исходный массив. С помощью элемента 1О сравнения определяется максимальное из и первых чисел массива.

Затем начальный адрес массива, хранящийся в счетчике 1, увеличивается на единицу, и производится поиск максимального из и чисел, начиная с второго и т.д. 1 ил.

1520507

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

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

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

19

Устройство содержит счетчики 1-4 (счетчики 3 и 4 — вычитающие), блок 5 памяти, регистры 6-9, элемент 10 сравнения, RS-триггер 11, D-триггер 12, регистр 13 сдвига, элементы !

И 14-18 элементы ИЛИ 19-21 одновибФ Я раторы 22-25, элементы НЕ 26 и 27, генератор 28 импульсов, делитель 29 частоты, вход 30 выбора типа фильтрации, вход 31 начальной установки, ! группы входов задания длины массива 32 и длины апертуры 33, вход 34 запуска, группу информационных выходов 35, выход 36 окончания работы и выход 37 синхронизации. 25

Операция экстремальной фильтраций (для определенности - максимальной) определяется следующим образом.

Пусть дан вектор А = (а,,а а ) из m ч иHcсеeл, причем а,= а =

= а „, < = а„, а „„,= а„„ „,,, = О, где n - длина аперВ туры. Тогда результирующий вектор В определяется, как В,= ма1сс1а,,а;„ ...,а;. „ 1, где 1 = 1 2,..., 1

3э (m-в+1)

Операция экстремальной фильтрации выполняется следующим образом.

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

Производится сдвиг апертуры на один элемент и определяется следующее экстремальное значение и т.д.

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

Фильтрации.

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

При наличии на входе 30 выбора типа фильтрации логической единицы устройство выполняет максимальную фильтрацию, Сигнал с входа 30 поступает на управляющий вход элемента 10 сравнения и на его выходе устанавливается единичный сигнал, если число на первой группе входов (выходы регистра 9) больше числа на второй группе входов (выходы регистра 7).

При логическом нуле на входе 30 выполняется минимальная фильтрация и йа выходе элемента 10 сравнения устанавливается единичный сигнал,если число на первой группе входов не

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

Сигнал начальной установки, поступающий по входу 31 в режиме максимальной фильтрации через элементы ИЛИ 19 и И 14, устанавливает в регистре 7 минимальное число, счетчики 1 и 2 и триггеры 11 и 12 установятся в нулевое состояние в счетчик 3 с входа 32 запишется длина обрабатываемого массива, а в регистр 6 с входа 33— длина апертуры. Сигнал "Пуск ", поступающий с входа 34,через элемент ИЛИ

21 поступает на вход разрешения записи счетчика 4, в который запишется длина апертуры из регистра 6, Тем ze сигналом триггер 11 будет установлен в единичное состояние.

Генератор 28 импульсов формирует импульсы синхронизации, частота которых уменьшается в два раза делителем 29 частоты и по переднему фронту импульса триггер 12 устанавливается в единичное состояние. Единичное состояние триггера 12 разрешает прохож-дение импульсов с делителя 29 частоты через элемент И 16 и устанавливает первый разряд регистра 13 в единичное состояние, По иснульсам синхронизации, поступающим с генератора 20 импульсов, на выходах второго и четвертого разрядов регистра 13 формируются сдвинутые относительно друг друга последовательности импульсов.

По испульсам первой последовательности производится прибавление единицы в счетчике 2 текущего адреса, вычитание единицы в счетчике 4 длины апертуры и запись предыдущего значения счетчика 2 в регистр 8., По адресу, поступающему на адресные вхо1520507 ды блока 5 памяти, производится считывание информации из блока памяти и запись ее в регистр 9 по испульсам второй последовательности. Число счиУ 5 танное в регистр 9, сравнивается с помощью элемента 10 сравнения с числом, хранящимся в регистре 7, и большее из этих чисел записывается в регистр 7. 10

По и-му тактовому импульсу первой последовательности обнуляется счетчик 4 и на его выходе формируется сигнал, по которому запускается одновибратор 23 и сбрасываются триггеры !5

11 и 12. По импульсу с выхода одновибратора 23 производится прибавление единицы в счетчике 1 начального адреса и запускается одновибратор 24.По импульсу с выхода одновибратора 24 20 производится запись модифицированного начального адреса в счетчик 2 текущего адреса и запускается одновибратор 25. Сигнал с одновибратора 25 поступает на выход 37 синхронизации 25 . устройства, сообщая, что на выходах; 35 установлено экстремальное число в окрестности, а также по этому сигналу вычитается единица в счетчике 3 длины массива и запускается 30 одновибратор 22, по импульсу с выхода которого через элемент ИЛИ 19 производится начальная установка регистра 7, а через элементы И 17 и ИЛИ 21 производится запись длины апертуры из регистра 6 в счетчик 4 и установка в единицу триггера 11. Таким образом, происходит запуск следующего цикла поиска наибольшего числа,аналогичного первому циклу. 40

В каждом последующем цикле определяется следующее наибольшее число среди элементов массива, количество которых задается длиной апертуры,а начальный адрес в блоке 5 памяти оп45 ределяется в счетчике 1. 3a m циклов (где ш — количество чисел в массиве, записанное в счетчике 3 в начале работы} счетчик 3 обнуляется и сигнал с его выхода заема после инвертирования элементом НЕ 27 поступает на вход элемента И 17 и запрещает перезапуск устройства на следующий цикл. Сигнал с выхода заема счетчика 3 поступает также на выход 36 окон5 чания работы устройства.

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

Устройство для экстремальной фильтрации, содержащее четыре счетчика,первыл» и второй регистры, блок памяти, элемент сравнения, Rs-триггер, D-триггер, пять элементов И, три элемента ИЛИ, два элемента НЕ, первый одновибратор и генератор импульсов, причем вход выбора типа фильтрации устройства соединен с управляющим входом элемента сравнения, первым входом первого элемента И и. через первый элемент НŠ— с первым входом второго элемента И, вход начальной установки устройства соединен с входами установки в нулевое состояние первого и второго счетчиков, входами разрешения записи третьего счетчика и первого регистра и первыми входами первого и второго элементов ИЛИ, входы задания длины массива и длины апертуры устройства соединены с информационными входами соответственно третьего ,счетчика и первого регистра, вход запуска устройства соединен с нервьм входом третьего элемента ИЛИ, выход которого соединен с S-входом КЯ-триггера и входом разрешения записи четвертого счетчика, выход заема которого соединен с вторым входом третьего элемента ИЛИ, выход которого соединен c R-входами RS- u D-триггеров, прямой выход RS-триггера соединен с

0-входом Р-триггера, прямой выход которого соединен с первым входом третьего элемента И, выход которого соединен с суммирующим входом второго и вычитаюцим входом четвертого счетчиков,инЬормационнь»е входы которых подключены к выходам разрядов соответственно первого счетчика и первого регистра, выход заема третьего счетчика является выходом окончания работы устройства и через второй элемент НЕ соединен с первым входом четвертого элемента И, выход которого соединен с вторьел входом третьего элемента ИЛИ, выход первого одновибратора соединен с вторыми входами четвертого элемента И и первого элемента ИЛИ, выход которого соединен с вторыми входами первого и второго элементов И, выходы которых соедине- ны соответственнно с входами установки в нулевое и единичное состояние второго регистра, выходы разрядов которого являются информационными выходами устройства и соединены с первой группой информационных входов элемента сравнения, выход которого соединен с первым входом пятого эле1520507

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

Техред А.Кравчук

Редактор В.Данко

Корректор Л.Бескид

Заказ 6758/49 Тираж 668 Подписное

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

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

Производственно-издательский комбинат "Патент", r.Óæãîðîä, ул. Гагарина, 101 мента И, выход которого соединен с входом разрешения записи второго регистра, информационные входы которого соответственно объединены с информационными входами второй группы элемента сравнения, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, в него введены третий и четвертый регистры, регистр сдвига, второй, третий и четвертый одновибраторы и делитель частоты,причем выходы разрядов второго счетчика соединены с информационными входами третьего регистра, выходы разрядов которого соединены с адресными входами блока амяти, информационные выходы которого соединены с информационными входами четвертого регистра, выходы разрядов которого соединены с информационными входами второго регистра, выход заема четвертого счетчика соединен с входом второго одновибратора, выход которого соедииен с суммирующим входом первого счетчика и входом третьего одновибратора, выход которого соединен с входом разре,шения записи второго счетчика и входом четвертого одновибратора, выход

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

И, выход которого соединен с входом .разрешения записи третьего регистра, 1 входом установки в единичное состояние первого и входами установки в нулевое состояние остальных разрядов регистра сдвига, выходы первого и третьего разрядов которого соединены соответственно с вторым входом пятого элемента И и входом разрешения записи четвертого регистра.