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

Изобретение относится к ттпслительной технике и может быть использовано в системах и устройствах обработки изображений, 5Цель изобретения - повьппение быст.родействия.На чертеже приведена схема устройств.Устройство содержит блоки 1 и 2 10и дмятн, генератор 3 импульсов, счетчики 4-6, блок памяти 7 маски, блок8 памяти признака, сумматор 8, пре 1 бразователь 10 кода, накапливаюпийсумматор 11, триггергп 12 и 13, эле" 15менты И 14 и 15,элемент 16 сравнения,информационный вход 17, информационный выход 18, входы задания ранга 19и маски 20, входы начальной 21-23установки, входы разрешения записи 0данных 24, маски 25 и ранга 26, выходы 27 и 28 состояния и вход 29 запуска,Преобразователь 10 кода передаеткод со своей группы входов 01 на 25группу выходов ПО беэ изменения, еслина его входе Е нулевой уровень,если на входе М . нулевой уровень,то входной код уменьшается на единицуа прн единичном уровне увеличивается на единицу.Устройство работает следующим образом.Перед началом работы сигналами,подаваемыми на входы 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 записано ш значений маски, то первый элемент набора данных записывается в блок 2 памяти по адресу ш, второй элемент - го адре. су в+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 па40 45 50 55 мяти, а в блок 8 памяти признака записывается число, равное числу на выходе блока 7 памяти маски, Если это число равно единице, то это означает, что соответствующий элемент набора участвовал в обработке, а если число равно нулю, то элемент в обработке не участвовал. Кроме того, по заднему фронту этого импульса происходит уменьшение содержимого счетчика 5 на единицу. Таким образом, каждый следующий адрес на адресном входе блока памяти 2 меньше предыдущего на единицу, что обеспечивает просмотр всех ;элементов набора данных, начиная с последнего из записанных в него и далее по убывании адресов. При обнулении счетчика 5 на его выходе заема формируется импульс, который обнуляет счетчик 4 и триггеры 12 и 13, сигнал с выхода триггера 12 переводит счетчик 4 в режим счета и закрывает элемент И 14, а сигнал с выхода триггера 13 открывает элемент И 15. По импульсу, поступающему от генератора 3 через элемент И 15, происходит суммирование числа, выбранного из блока памяти 1 по адресу, формируемому счетчиком 4, с числом, хранящимся в накапливающем сумматоре 11. Процесс суммирования в накапливающем сумматоре 11 продолжается до тех пор, пока на выходе переноса накапливающего сумматора 11 не появляется сигнал кото.Э рый устанавливает триггер 13 в единичное состояние, при этом элемент И 15 закрывается и импульсы с его выхода перестают поступать на тактовый вход накапливающего сумматора 11, а на выходах устройства 27 и 28 появляется код окончания поиска, При этом значение на выходе счетчика 4 равно значению числа с искомым рангом, это значение поступает на выход 18 устройства.При сортировке наборов, частично перекрывающихся между собой, устройство работает следующим образом.Значения маски и ранга устанавливаются так же, как в предыдущем режиме. Далее с входа 17 по сигналам, подаваемым на вход 24, производится запись в блок 2 памяти только тех элементов нового набора данных, которые различны с предыдущим. Таким образом, если количество значений мас, ки ш, а количество элементов набора и, то после окончания предыдущего 5 10 15 20 25 30 35 этапа поиска числа с заданным рангомна выходе сумматора 9 присутствуетзначение адреса, равное в+и-ш = п.5После записи новых значений маски вблок 7 памяти маски запись новых значений обрабатываемого набора в блок 2памяти набора начинается с адресаш+п, т.е. подряд за ранее записанныминеизмененными элементами набора данных.Работа устройства в дальнейшем аналогична описанному, за исключением работы преобразователя 10 кода. Так какв данном случае содермимое блока 1памяти и блока 8 памяти признака неравны нулю, причем единичное значениев блоке 8 памяти признака означает,что число, хранящееся в блоке 2 потому же адресу, уже было использованов формировании гистограммы на предьщушем этапе поиска числа с заданнымрангом, то в работе преобразователякода возможны следующие варианты:при совпадении данных на выходахблоков 7 и 8 памяти данные передаются с выхода блока памяти 1 на еговход без изменения; при их несовпадении и нулевом значении маски данныеуменьшаются на единицу; при значениимаски, равном единице, увеличиваютсяна единицу. Таким образом обеспечивается модификация гистограммы, хранящейся в блоке 1 памяти вместо формирования ее заново. Дальнейшая работа устройства аналогична. Формула изобретения Устройство для поиска чисел с заданным рангом, содержащее генератор импульсов, первый блок памяти, первый и второй счетчики и два элемента И, причем выходы разрядов первого счетчика соединены с соответствующими адресными входами первого блока памяти, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены второй блок памяти, блоки памяти признака и маски, третий счетчик, сумматор, накапливающий сумматор, преобразователь кода, два триггера и элемент сравнения, причем информационные входы устройства соединены с информационными входами второго блока памяти, выходы которого соединены с информационными входами первого счетчика, вхор установки в нулевое состояние которого объединен с входами установки в нулевое1617433 Составитель В. Горохов Техред Л.Олийнык, Редактор Л. Пчолинская Корректор С.Шевкун Заказ 4119 Тираж 565 ПодписноеВНИИПИ Государственного комитета цо изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д. 4/5 ПрОИэводственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 101 состояние обоих триггеров и подключенк выходу заема второго счетчика, вылходы разрядов которого соединены свходами первой группы сумматора и адресными входами блока памяти маски,выход которого соединен с информационным входом блока памяти признака ипервыми входами преобразователя кодаи элемента сравнения, выход которого"оединен с вторым входом преобразователя кода, выходы которого соединены с информационными входами первогоблока памяти, выходы которого соединены с информационными входами преобразователя кода и накапливающегосумматора, выход переноса которогосоединен с входом установки в единичное состояние первого триггера, инверсный выход которого является первым выходом состояния устройстваи соединен с первым входом первогоэлемента И, выход которого соединенс тактовым входом накапливающего сумматора и суммирующим входом первогосчетчика, вход запуска устройствасоединен с входом установки в единич"ное состояние втброго триггера, выход которого является вторым выходомсостояния устройства и соединен свходом разрешения записи первогосчетчика и первым входом второгоэлемента И, выход которого соединенс входами записи первого блока памяти и блока памяти признака и вычитающим входом второго счетчика,суммирующий вход которого являетсявходом разрешения записи маски устройства и подключен к входу записиблока памяти маски, информационныйвход которого является входом маскиустройства, вход разрешения записиданных устройства соединен с входомзаписи второго блока памяти и сум",мирующим входом третьего счетчика,выходы разрядов которого соединеныс входами второй группы сумматора,выходы которого соединены с адресными входами второго блока памяти иблока памяти признака, выход которого соединен с вторым входом эле"мента сравнения, входы задания ранга устройства соединены с установочными входами накапливающего сум матора, вход разрешения записи рангаустройства соединен с входом записинакапливающего сумматора, первый входначальной установки устройства сое динен с входами очистки первого и 25 второго блоков памяти и входом очистки блока памяти признака, второй итретий входы начальной установки устройства соединены с входами установкив нулевое состояние соответственно 30 второго и третьего счетчиков, выходгенератора импульсов соединен с вторыми входами первого и второго элементов И, выходы разрядов первогосчетчика являются информационными .выходами устройства.л