Пристрій позиційної селекції інформації

ДЛЯ СЛУЖЕБНОГО ПОЛЬЗОВАНИЯ 02 *J 5 союз СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИХ РЕСПУБЛИК (19) S I L 1326069 А1 (51)4 G 06 F 7/06 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3936219/24-24 (22) 10.06.85 (71) Институт кибернетики им. В.М.Глушкова (72) Л.Е.Горша, В.И.Гриценко, Г.И.Корниенко и К.М.Шилов (53) 681.3(088.8) (56) Авторское свидетельство СССР * 1073770, кл, G 06 F 7/06, 1982. , Авторское свидетельство СССР № 1087986, кл. G 06 F 7/06, 1983. (54) УСТРОЙСТВО ПОЗИЦИОННОЙ СЕЛЕКЦИИ ИНФОРМАЦИИ (57) Изобретение относится к области информатики и вычислительной техники и позволяет обеспечить решение задач позиционной селекции информационных массивов и их элементов, внутреннюю сортировку массивов, скользящую медианную фильтрацию и др. Целью изобретения является повышение быстродействия. Устройство позиционной селекции информации содержит т п-разрядных п сдвиговых регистров 2, (п-1) схем сравнения 3, (п-1) элементов памяти, выполненных на сдвиговых регистрах, п шифраторов, элемент задержки 4 и коммутатор. Оно позволяет из п последовательно принятых чисел выделить число, занимающее заданное положение в отсортированной по возрастанию выборке . 3 ил. І (Л со 1326069 КИй ОТНОСИТСЯ К ьЫЧНСЛ тельной технике и позволяет обеспечить решение задач позиционной селекции информационных массивов и их зле- ь ментов» внутреннюю сортировку, внутреннюю сортировку массивов в реальном масштабе времени,, скользящую медианную фильтрацию» минимаксный поиск и ДР. 10 Цель изобретения - повышение быстродействия. На фиг.) и 2 приведена структурная схема устройства; на фиг.З покаэана последовательность чисел на 15 % входе и выходе устройства. Устройство позиционной селекции информации содержит информационный вход 1 (шина) устройства, m поразрядных сдвиговых регистров 2.1-2.т, 20 схемы сравнения З.І-З.п-l, элемент задержки 4, тактовый вход 5, элементы памяти, выполненные на сдвиговых регистрах второй группы 6,1-6,п-1, 2 5 элементы НЕ 7, шифраторы 8.1-8.П, коммутатор 9, информационный выход 10 (шина) устройства, вход 11 (шина) номера элемента выборки устройства» Устройство работает следующим образом» • 30 Устройство для выборки информации позволяет из п последовательно принятых чисел выделить число, занимающее заданное положение в отсортированной по возрастанию выборке. Например, ее- 35 ли при величине выборки 5 были приня,ты числа 4, 3, 7, 0, 9 и надо выделить ,третий элемент орсортированной выборки, устройство выделит элемент 4в 40 Числа последовательно поступают по шине 1 в устройство, причем занесение в регистры 2 производится при поступлении сигнала с тактового входа 5. 45 Последнее принятое число, код которого образуется на первой шине, сравнивается с остальными числами на схемах сравнения З.І-З.п-l. Если код на первой шине меньше либо равен сравни- _. ваемому коду на шчне с 2-й по n-ю, то на выходе схемы сравнения З.і будет сформирован единичный сигнал, а если больше - нулевой. Результаты сравнения по задержанному на элементе за55 держки И сигналу синхронизации с шины 5 записываются в сдвиговые регистры 6, объем которой выбран достаточным для решения поставленной задачи и равным бит. С выхода сдви гового регистра 6 поступает информация на управляемые шифраторы 8, с выхода которых позиционный код номера искомого элемента выборки поступает на управляющие входы коммутатора -9, с выхода которого на шину 10 поступает код найденного элемента. Элемент задержки учитывает величину задержки распространения сигналов на регистрах 2 и схемах сравнения 3. Суммарная задержка появления информации на выходной шине 10 относительно сигнала на тактовом входе 5 равна сумме задержек на элементах 4tj 6 ? 7, 8. При изменении кода выбираемого элемента по шине 1I задержка будет меньшей и равной сумме задержек на элементах 8 и 9. Рассмотрим более подробно работу элементов памяти 6 и шифраторов 8. Например, п = 5, тогда нумерация элементов будет 0, I, 2, 3, 4. Пусть требуется выделить элемент отсортированной последовательности с номером 2 (медиана). Элементы памяти 6 будут состоять из четырех сдвиговых регистров - 6,1; 6,2, 6.3 и 6.4. Шифраторов этом случае должно быть пять: 8.1, 8.2, 8.3, 8.4, 8.5, причем каждый шифратор будет иметь четыре информационных и три управляющих входа. На информационные входы шифраторов будут поступать следующие признаки: на 8.1 - 6.11, 6.21, 6.31, 6.41; на 8.2 - 6 . П , 6.12, 6.22, 6.32; на 8.3 -'6.21, 6.12, 6.13, 6.23; на 8.4 - 6.31, 6.22, 6.13, 6.14; на 8.5 - 6.41, 6.32, 6.23, 6.14. На управляющие входы всех шифраторов поступит код требуемого элемента, т.е. два. Шифратор 8 выполнен так, что при совпадении кода на управляющем входе с количеством единиц на информационном входе на его выходе будет единичный потенциал, в противном случае - • нулевой. В начальном состоянии на регистрах 2 хранятся нули, а на регистрах 6 - единицы. Суммы кодов информационных входов всех шифраторов 8: 1326069 8.1 - 0 і 0 нh 0 -Ін 0 - 0 8.2 - 1 к 0 - І- 0 • 1 = 4 На выходе шифратора 8.3 появится единица, которая, поступив на коммутатор 9, скоммутирует третью шину на выходную шину 10. 10 Пусть на вход устройства по очередному синхронизирующему импульсу поступит код 1. Тогда выборка будет иметь вид 10000, в первые разряды регистров 6 запишутся нули: 15 6.1 - 0 1 1 1 6.2 - 0 1 1 6.3 - 0 1 6.4 - 0 Состояние информационных входов шиф- 20 раторов 8: - 1 1 1 1 0 0 0 0 0 10 0 25 0 110 1 11 0 Единица появится на выходе шифратора 8.4. Далее, например, при поступлении кодов 3» 2, 1 , 5, А содержимое сдвиговых регистров и информационных 30 входов 8 будет следующим (звездочкой помечен шифратор, на выходе которого появится единица): коды 3 1 0 0 0 6.1 - 0 0 1 1 8.1 — і *1 1 1 35 6.2 - 0 0 1 8.2 - 0 1 1 1 6.3 - 0 0 8.3 - 0 0 ( 0 3 6.4 - 0 8.4 - 0 0 0 8.5 - 0 0 1*0 коды 2 3 1 0 0 40 6.1 - 1 0 0 1 8.1 - 0 1 1 6.2 - 0 0 0 8.2 - 1 1 1 6.3 - 0 0 8.3 - 0 0 1*1 6. А - 0 8.А-- 0 0 ( 0 ) 8.5 - 0 0 ( 1 45 3 коды 1 2 6.1 6.2 6.3 6.4 31 -) -1 -1 - 0 коды 5 1 2 6.1 6.2 6.3 3 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 1 6.А - 0 коды 4 5 6,1 6.2 6.3 6.А 12 -1 - 0 - 0 - 0 8.1 8.2 8.3 8.А 8.5 - 0 -1 -1 -1 - 0 0 0 1 0 0 1 1 0 1*1 0 0 8.1 8.2 8.3 8.4 8.5 1 0 1 1 1 1 0 0 1 0 1 0 0 0 0 0 1 I 1 1 0 1*2 1 0 3 0 11 0 1 8.1 - 0 1 1 1 8.2 - 1 1 1 1 0 8.3 - 0 0 0 0 8.4 - 0 0 1 0 8.5 - 0 0 1 1*3 Приведенный пример иллюстрирует процедуру медианной фильтрации на выборке длиной 5, > В качестве шифратора 8 используется постоянное запоминающее устройство, на адресные входы которого заводятся информационные и управляющие входы. Для случаев п = 5, га = А для реализации шифратора 8 достаточно емкости ПЗУ 128 бит. Устранение выбросов наглядно видно на следующем численном примере. Пусть через устройство с п = 5 прошла последовательность кодов 0,0,0,0,0,0,1,4,25,8,5,0,6,7,10,3,9, 7,6» На управляющей шине 11 установ-* лен код 2. На фиг.З представлен график поступившей последовательности (1) и последовательности после устранения выбросов (2). Сравнение кодов последовательности чисел на входе и на выходе устройства: Вход 0 0 0 0 0 1 4 25*8 5 0 6 7 10 3 9 7 6 Выход х 0 0 0 1 А 5 5 5 6 6 6 6 7 7 7 х х Из приведенных данных видно, что чем тактовый вход устройства соедивыбросы полностью устранены. 50 нен с тактовыми входами п-разрядных сдвиговых регистров группы, информаФ о р м у л а и з о б р е т е н и я ционные входы которых соединены с входами селектируемых чисел устройстУстройство позиционной селекции ва, выход старшего разряда первого информации, содержащее группу из n-разрядного сдвигового регистра групm n-разрядных сдвиговых регистров, (гапы соединен с первым входом первой разрядность чисел), (п-1) схем сравгруппы входов первой схемы сравнения, нения, (и - количество селектируемых о т л и ч а ю щ е е с я тем, что, с чисел, (п-1) элементов памяти, прицелью повышения быстродействия, эле 1326069 рядных сдвиговых регистров первой менты памяти выполнены на сдвиговых группы, где к = 2...(п-1)» соединены регистрах второй группы и в него ввес первой группой -входов к-й схемы дены (п-1) групп элементов НЕ, по сравнения, і-є выходы j-x сдвиговых (n-j) элементов НК в группе, где и регистров второй группы, где j ™ j 1..4(п-1)9 элемент задержки, п • I-(n-l), i - l-(n-l) соединены с шкфраторовв коммутаторt причем такпервой группой входов [(n-2)-i-jj -го товый вход устройства через элемент шифратора и через і-й элемент НЕ j-й задержки соединен с тактоввгми входагруппы с первой группой входов ми сдвиговых регистров второй группы, [(n-l)-ij-ro шифратора, вторая групинформационные входы которых соедипа входоп которых соединена с входанены с выходами соответствующих схем ми номера элемента выборки устройстсравнения, вторые группы входов схем ва, а выходы соединены с управляющисравнения соединены с выходами перми входами коммутатора, выходы которовых разрядов поразрядных сдвиговых го соединены с информационными выхорегистров первой группы, выходы стардами устройства, а информационные тих разрядов первой группы соединены входы - с информационными выходами с второго пога-й- входами первой с п-разрядных сдвиговых регистров пергруппы с второго по т-й первой схемы вой группы. сравнения, выходы к-х разрядов п-раз а •паї и ^ By * t • I -1) Фиг. 2 1326069 Код t 20 Ю Код • • • і • 10 О '1 2 3 4 5 6 7 8 9 W Фиг.3 Редактор А.Иванова Заказ 837/ДСП ! Составитель В.Козлов Техред М.Ходанич Корректор С.Шекмар Тираж 653 Подписное ВНЙИПИ Государственного комитета СССР по делам изобретений и открытий . 113035, Москва, Ж-35, Раушская наб # > д. 4/5 Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4