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

 

Изобретение относится к вычислительной технике и может быть использовано в системах обработки изображений. Цель изобретения - повышение быстродействия. Устройство содержит блоки памяти (БП) 1, 2, генератор импульсов 3, счетчики 4, 5, 6, БП маски 7, БП признака 8, сумматор 9, преобразователь кода 10, накапливающий сумматор 11, триггеры 12, 13, элементы И 14, 15, элемент сравнения 16, информационные вход 17 и выход 18, входы задания ранга 19 и маски 20, входы начальной установки 21, 22, 23, входы разрешения записи данных 24, маски 25 и ранга 26, выходы состояния 27, 28, вход запуска 29. Исходный набор данных записывается в БП 2, затем в БП 1 строится гистограмма этого набора данных до тех пор, пока не будет достигнуто число заданного ранга, которое устанавливается на выходе 18. При изменении набора данных гистограмма только модифицируется, а не строится заново. Часть элементов набора данных может быть замаскирована. 1 ил.

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

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

РЕСПУБЛИК (19) (11) щ) С 06 F 7/06

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

К, А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

17

2!

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

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

ПРИ ГКНТ СССР

l(21) 4620073/24 (22) 12. 12.88 (46) 30.12.90. Бюл. Н 48 (71) Куйбьппевский авиационный институт им.акад.С.П.Королева (72) Ю.О.Забродин, А.Ю.Миллер, К.В.Овчинников и А.Г.Храмов (53) 681.325{088.8) (56) Авторское свиде гельство СССР

)) 1183956, кл. G 06 F 7/06, 1984.

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

В 1310804, кл, G 06 F 7/06, 1986. (54) УСТРОЙСТВО ДЛЯ ПОИСКА ЧИСЕЛ С

ЗАДАННЫМ РАНГОМ (57) Изобретение относится к вычислительной технике и может быть использовано в системах обработки изображений. Цель изобретения — повьппение быстродействия. Устройство содержит блоки памяти (БП) 1, 2, гене2 ратор импульсов 3, счетчики 4, 5, 6, БП маски 7, БП признака 8, сумматор 9, преобразователь кода 10, накапливающий сумматор 11, триггеры 12, 13, элементы И 14, 15, элемент сравнения 16, информационные вход 17 и выход 18, входы задания ранга 19 и маски 20, входы начальной усТановки

21, 22, 23, входы разрешения записи данных 24, маски 25 и ранга 26, выходы состояния 27, 28, вход запуска 29, Исходный набор данных записывается в БП 2, затем в БП 1 строится гистограмма этого набора данных до тех пор, пока не будет достигнуто число заданного ранга, которое устанавливается на выходе 18. При изменении набора данных гистограмма только модифицируется, а не строится заново. Часть элементов набора данных может быть замаскирована ° 1 ил.

1617433

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

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

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

Устройство содержит блоки 1 и 2 10 памяти, генератор 3 импульсов, счетчики 4-6, блок памяти 7 маски, блок

8 памяти признака, сумматор 8, пре..бразователь IO кода, накапливаюший сумматор 11, триггеры 12 и 13, эле- 15 менты И 14 и 15,элемент 16 сравнения, информационный вход 17, информацион ный выход 18, входы задания ранга 19 и маски 20, входы начальной 21-23 установки, входы разрешения записи gp данных 24, маски 25 и ранга 26, выходы 27 и 28 состояния и вход 29 запуска, Преобразователь 10 кода передает код со своей группы входов DI на 25 группу выходов ПО беэ изменения, если на его входе E нулевой уровень, если на входе М . нулевой уровень, то входной код уменьшается на единицу а прн единичном уровне увеличивает- 30 ся на единицу.

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

Перед началом работы сигналами, подаваемыми на входы 21-23, производится очистка содержимого блоков памяти 1, 2 и 8 и сброс счетчиков 5 и 6.

Затем с входа 20 по сигналам, подаваемым на вход 25, производится запись значений маски в блок 7, причеь 40 каждый импульс с входа 25 своим задним фронтом увеличивает значение адреса в счетчике 5 на единицу. Значения маски равны единице для тех элементов набора, которые подлежат об-, 45 работке, и равны нулю для остальных.

Общее количество значений маски, записанных в блок 7 равно сумме количества элементов в обрабатываемом наборе данных и максимального коли( чества элементов набора, обновляемых в нем для новой обработки после окон-, чания текущего поиска числа с заданным рангом. Затем на вход 19 подается заданный ранг в дополнительном коде, который по сигналу с входа 24 записывается н накапливающий сумматор

11. Далее с входа 17 по сигналам, подаваемым на вход 24, производится запись элементов обрабатываемого набора данных в блок 2 памяти, при этом каждый импульс, подаваемый на вход

24, своим задним фронтом увеличивает содержимое счетчика 6 на единицу.

При этом адрес, по которому производится запись значений элементов набора данных в блок 2 памяти, является суммой значений, содержащихся в счетчиках 5 и 6. Суммирование производится сумматором 9, данные с выхода которого поступают на адресный вход блока 2 памяти. Таким образом, если в блок 7 записано m значений маски, то первый элемент набора данных записывается в блок 2 памяти по адресу m, второй элемент — го адресу m+1, а и-й элемент — по,адресу

m+n-1. По окончании записи элементов набора данных на вход 29 подается сигнал "Пуск", который устанавливает триггер 12 в единичное состояние, Единичный уровень с выхода триггера

12 переводит счетчик 4 в режим предустановки и открывает первый элемент

И 14. Данные с выхода блока 2 памяти поступают через счетчик 4 на

1 адресный вход блока 1 памяти,нуле- вые значения с выхода блока памяти признака 8 поступают на вход элемента сравнения 16, а значения маски из блока 7 поступают на другой вход элемента 16 сравнения и на вход

М преобразователя 10 кода, на вход

Е которого поступает выходной сигнал элемента сравнения 16. В связи с тем, что блок 8 памяти признака обнулен,на выходе элемента сравнения

16 присутствует то же значение, что и на его входе, подключенном к выходу блока 7 памяти. Таким образом, на входах Е и М преобразователя 10 кода имеются одинаковые значения.

Если на этих входах присутствует сигнал "0", то данные на выход преобразователя 10 кода проходят с его входа данных беэ изменений. Следовательно, соответствуюшдй элемент обрабатываемого набора замаскирован и не участвует в обработке. При наличии сигнала "1 на входах Е и М преобразователя 10 кода значение, поступающее на его вход, увеличивается на единицу и поступает на ин формационный вход блока 1 памяти.

По импульсу, поступающему от генератора 3 через элемент И 14, происходит запись этого значения в блок 1 па.

1617433

55 мяти, а в блок 8 памяти признака записывается число, равное числу на выходе блока 7 памяти маски. Если это число равно единице, то это означает, что соответствующий элемент набора участвовал в обработке, а если число равно нулю, то элемент в обработке не участвовал. Кроме того, по заднему фронту этого импульса происходит уменьшение содержимого счетчика 5 на единицу. Таким образом, каждый следующий адрес на адресном входе блока памяти 2 меньше предыдущего на единицу, что обеспечивает просмотр всех

;элементов набора данных, начиная с

l последнего из записанных в него и далее по убывании адресов. При обнулении счетчика 5 на его выходе заема формируется импульс, который обнуляет счетчик 4 и триггеры 12 и 13, сигнал с выхода триггера 12 переводит счетчик 4 в режим счета и закрывает элемент И 14, а сигнал с выхода триггера

13 открывает элемент И 15. По импульсу, поступающему от генератора 3 через элемент И 15, происходит суммирование числа, выбранного из блока памяти 1 по адресу, формируемому счетчиком 4, с числом, хранящимся в накапливающем сумматоре 11. Процесс суммирования в накапливающем сумматоре

11 продолжается до тех пор, пока на выходе переноса накапливающего сумматора 11 не появляется сигнал кото

1.

Э рый устанавливает триггер 13 в единичное состояние, при этом элемент

И 15 закрывается и импульсы с его выхода перестают поступать на тактовый вход накапливающего сумматора

11, а на выходах устройства 27 и 28 появляется код окончания поиска, При этом значение на выходе счетчика 4 равно значению числа с искомым рангом, это значение поступает на выход 18 устройства.

При сортировке наборов, частично перекрывающихся между собой, устройство работает следующим образом.

Значения маски и ранга устанавливаются так же, как в предыдущем режиме. Далее с входа 17 по сигналам, подаваемым на вход 24, производится запись в блок 2 памяти только тех элементов нового набора данных, которые различны с предыдущим. Таким образом, если количество значений мас, ки m а количество элементов набора и, то после окончания предыдущего

35 этапа поиска числа с заданным рангом на выходе сумматора 9 присутствует -. значение адреса, равное m+n — m = п.

После записи новых значений маски в блок 7 памяти маски запись новых значений обрабатываемого набора в блок 2 памяти набора начинается с адреса

"„+n, т.е. подряд за ранее записанными неизмененными элементами набора данных.

Работа устройства в дальнейшем аналогична описанному, за исключением работы преобразователя 10 кода. Так как в данном случае содермимое блока 1 памяти и блока 8 памяти признака не равны нулю, причем единичное значение в блоке 8 памяти признака означает, что число, хранящееся в блоке 2 по тому же адресу, уже было использовано в формировании гистограммы на предыду щем этапе поиска числа с заданным рангом, то в работе преобразователя кода возможны следующие варианты: при совпадении данных на выходах блоков 7 и 8 памяти данные передаются с выхода блока памяти 1 на его вход без изменения, при их несовпадении и нулевом значении маски данные уменьшаются на единицу, при значении маски, равном единице, увеличиваются на единицу. Таким образом обеспечивается модификация гистограммы, хранящейся в блоке 1 памяти вместо формирования ее заново. Дальнейшая работа устройства аналогична.

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

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

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

1617433

Составитель В. Горохов åõðåä Л.Олийнык, Редактор Л. Пчолинская

Корректор С.Шевкун

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

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

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

Производственно-издательский комбинат "Патент", r.Ужгород, ул. Гагарина, 101 состояние обоих триггеров и подключен к выходу заема второго счетчика, вы ходы разрядов которого соединены с входами первой группы сумматора и ад ресными входами блока памяти маски, выход которого соединен с информационным входом блока памяти признака и первыми входами преобразователя. кода и элемента сравнения, выход которого оединен с вторым входом преобразователя кода, выходы которого соединены с информационными входами первого блока памяти, выходы которого соединены с информационными входами преобразователя кода и накапливающего сумматора, выход переноса которого соединен с входом установки в единич ное состояние первого триггера, инверсный выход которого является первым выходом состояния устройства . и соединен с первым входом первого элемента И, выход которого соединен с тактовым входом накапливающего сумматора и суммирующим входом первого счетчика, вход запуска устройства ( соединен с входом установки в единич" ное состояние второго триггера, выход которого является вторым выходом состояния устройства и соединен с входом разрешения записи первого счетчика и первым входом второго элемента И, выход которого соединен с входами записи первого блока памяти и блока памяти признака и вычитающим входом второго счетчика, суммирующий вход которого является входом разрешения записи маски устройства и подключен к входу записи блока памяти маски, информационный вход которого является входом маски устройства, вход разрешения записи данных устройства соединен с входом записи второго блока памяти и сум". мирующим входом третьего счетчика, выходы разрядов которого соединены с входами второй группы сумматора, выходы которого соединены с адресными входами второго блока памяти и блока памяти признака, выход которого соединен с вторым входом элемента сравнения, входы задания ранга устройства соединены с установочными входами накапливающего сумgp матора, вход разрешения записи ранга устройства соединен с входом записи накапливающего сумматора, первый вход начальной установки устройства сое динен с входами очистки первого и второго блоков памяти и входом очист ки блока памяти признака, второй и третий входы начальной установки уст ройства соединены с входами установки в нулевое состояние соответственно

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