Устройство сортировки информации

ОЮЗ СОВЕТСКИ ОЦИАЛИСТИЧЕСКИХЕСПУБЛИК , (19) О 17088 1)5 0 ТЕНТН ОСУДАРСТВЕННОЕ ВЕДОМСТВО СССР ГОСПАТЕНТ СССР) ЗС) БР ЕТЕ Н ИЯ И ИДЕТЕЛ ЬСТВУ К АВТОРСКО. Бюл, %19адаев, Н,А.Глущенко и В.В.Заяс Б,В, МикропроцессорныеструкРадио и связь. 1986, с.249,ение относится к вы . Цель изобретения области применения возможности адапта ипам входных данны ройства подается ма екоторая совокупнос Изобретение относится к вычислительной технике и может бытьиспользовано длявыделения из массива поступающих,на его, вход кодовых слов некоторой их совокупности, определяемой режимом работы устройства,Целью изобретения является расшире-ние области применения устройства за счетвозможности адаптации его к различным ти-."пам входных данных,Пусть в качестве сортируемой информации служит массив -разрядных кодовыхСЛОВ (71,72,;,7 Ь .7).На выход устройства пропускаютсятолько те слова, которые соответствуют им- .пликантам булевой функции аида; е 7) (чх1=1(57) Изобреной техникрасширенива за счетразличнымданного уствых слов. Н СТВО СОРТИРОВКИ ИНФОРчислительсостоиг в устройстции его к х, На вход ссив кодоть слов из данного массива передается на выход устройства. Вид этой совокупности определяется режимом работы устройства, который, в свою очередь, зависит от входных данных. . Поставленная цель достигается тем, что в состав устройства анализа информации введены дополнительно блок информации и блок синхронизации. В состав блока информации входит наборное поле, коммутация которого в сочетании с.входными данными позволяет изменять режим работы устройства. Блок синхронизации осуществляет синхронизацию работы составных частей устройства; Предлагаемое устройство позволяет решать различные задачи, связанные с сортировкой исходной информации 3 по различным группам. 7 ил.Р(71,727 ьд) =Л ф(5 7 ), (1)=1где ф(ф,7 ) - логическая функция двух и ременных, принимающая значения ф(0,0) = =1;ф(0,1) =0;ф(1,0) =1; ф(1,1) =1;ф- логическая переменная, определяемая следующим образом;1817088 гу ЬЛ,Фиг 6 аказ 1723 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГК 113035, Москва, Ж, Раушская на 64/5 Производственно-издательский комбинат "Патент", г, Ужгоройства, т.е, совокупности выделяемых из исследуемого массива кодовых слов.В качестве иллюстрации рассмотрим вариэнт применения описываемого устройства для исследования ремонтопригодности некоторой технической системы (фиг.1), состоящей из= 18 С 4,При этом в качестве входных данных должна использоваться следующая информация:х 1; Ц = 1, - переменные, характеризующие структуру исследуемой системы (х = 1, если -эя состэвнэя часть (СЧ) включэет в свой состав -ю СЧ; х = 0 - в противном случае);.;= 1, - переменная, характеризующая техническое состояние (ТО) системы (11= = 1. если имеет место отказ )-й СЧ;= 0 - в противном случае).В рассматриваемом случае любой импликант функции (1), т.е. выделяемое кодовое слово, характеризует возможный вариант восстановления (ВВ) исследуемой системы. Данный вариант предусматривает замену только отказавших СЧ или СЧ содержащих отказавшие и исключает. кратные замены, т.е. одновременные замены некоторых СЧ и СЧ их содержащих.Знэчения х; исведены в таблицу (фиг.2), Определим совокупность выделенных кодовых слов применительно к приведенным исходным данным, для чегоопределим 1, 2, 1841= г гз г 4 г 5 г 8 г 9 г 10.г 11 г 12 г 13 г 14к2= г 2 гбг 7г 15 г 16 г 17 г 1843=- О, 4= 0; 5= г 5 г 12 г 13 г 14:6= гб г 15г 16;7= 0; 8= 0; 9= 0; 10= 0; Ь 1= О; 12= 0;13= г 13; ф 14=- О; ф 15= О; и= г 16: ф 17= 0; ф 18= 0С учетом этого запишем:Г(г 1, г 2, г 18) ф(11 г 1)ф(ф 2, г 2 )гЗг 4ф(ф 5, г 5 )ф ( фбгб )г 7г 8г 9г 10г 11г 12ф ( 13 г 13 )г 14г 157 ( 16 2 , 16 )г 17г 18 ,Импликантэми данной функции и соответствующими им кодовыми словами являются;18г 1Лг1000000000000000001=-2 г 1 г 2 А г- -. - 010000000000000000=3Иг 1 г 2 гзг 4 г 5 Лг " -0000100000000000005 1=бНэличие в -й и т,д, позиции кодовогословасвидетельствует о необходимостизамены -й СЧ согласно характеризуемомуданным кодовым словом ВВ,10 Рассмотренная и проиллюстрированнэя задача решается с помощью устройствасортировки информации (УСИ) благодарятому, что оно содержит (фиг.З):1 - входной регистр;2 - региртр хранения;3 - схема сравнения ;4 - схема сравнения ;5 - блок информации;6 - блок синхронизации,Информация о значениях 3(ТС) поступает на входной регистр 1. С выхода этогоблока информация поступает через наборное поле (НП), входящее в состав информационного блока 5 и определяющее25 посредством соответствующей коммутациизначения х, на регистр хранения 2,Кодовое слово (г 1,г 2, гь,.г) (ВВ) поступает на схемы сравненияии далее взависимости от результатов его сравнения скодовцми словами допустимой совокупности выдается или не выдается нэ выход устройства через блок синхронизации 6,который осуществляет синхронизацию работы всех составных частей данного устройЗ 5 ства,Указанное выше НП состоит из ячеек,состав и соединение которых представленына фиг.5. Каждая из ячеек состоит из двухдиодов и переключения, На фиг.4 представ 40 лена схема коммутации НП применительнок рассмотренному иллюстративному примеру.Заштрихованы те ячейки НП, в которыхнеобходимо замкнуть контакты выключате 45 лей для отображения НП приведенной дляпримера системы. На фиг.5 обозначены входы и выходы первой и второй групп ячеек.Если контакты выключателей некоторойячейки разомкнуты, то независимо от входных сигналов этой ячейки ее выходные уровни обеих групп при условии, что ониподаются на логические элементы (ЛЭ) серий ТТЛ, будут восприниматься этими ЛЭкак уровень логической единицы, Если кон 55 такты замкнуты, то выходные сигналы обеихгрупп полностью соответствуют входным.Поэтому в УСН применяются ЛЭ серий ТТЛи информационным уровнем в НП являетсяуровень логического нуля.На фиг.б изображена функциональная формация о тех позициях, которые могут электрическая схема УСН для анализа 30-ти предлагаться в ВВ.позиционных кодовых слов. Рассмотрим Рассмотрим работу схемы сравнения 1, как анализируется информация, Этот ана- которая заключается в сравнении предлагализ начинается с подачей сигнала Прием 5 емых позиций в ВВ с теми позициями, кото- ТС. При появлении этого сигнала(информа- рые могут предлагаться в ВВ, На входы ционный уровень - единица) входной ре- буферных элементов с разрешением схемы гистр единицей на входе РЕ открывается по анализа подается информация с регистра входу и сигналы в ШДтс (информационный хранения, а на входы разрешения - предлауровень - ноль) фиксируется в регистре, 10 гаемый ВВ (информационный уровень Значит информация о ТС должна быть в ноль), На выходебуферногоэлементабудет ШДтс до поступления сигнала ПРИЕМ ТС и ноль только тогда, когда на его входе едининаходиться там во время действия сигнала ца, а на входе разрешения ноль, то есть, ПРИЕМ ТС, Сигнал ПРИЕМ ТС подается на когда данная позиция не должна принимать инвертор в блоке синхронизации, С выхода 15 участие в ВВ, а она предлагается. Если хоть этого инвертора ноль поступает на вход ВО в одном разряде на выходе буферного элевходного регистра и открывает его по выхо- мента будет ноль, то на выходе ЛЭ 12 И-НЕ ду, то есть на выходе регистра сигналы те схемы сравнения появится единица - сигже, что и на входе. Единица сигнала ПРИЕМ нал запрета,ТС подается на первые входы ЛЭ 2 ИЛИ - НЕ 20 Рассмотрим работу схемы сравнения 1. блока синхронизации и на выходах этих ЛЭ Суть работы схемы состоит в следующем. независимо от ВВ, подаваемого на вторые Сначала, когда сдвиговый регистр в данном входы ЛЭ 2 ИЛИ - НЕ, будет ноль, который блоке обнулен, на выходах буферных элеинвертируется и в старших разрядах пода- ментов будет единица или г-состояние (в ется на входы разрешения буферных ЛЭ с 25 зависимости от ВВ) и его выходы будут заразрешением, устанавливая на их выходах висеть только от предполагаемого ВВ в Е-состояние, а выходы этих элементов под- младших разрядах. Выходы блока синхроключены к выходам входного регистра, Сиг- низации отображаются на выходах 2 группы налы с выхода входного регистра в старших: НП, которые соединены со входами ЛЭ разрядах подаются на входыгруппы НП, 30 ЗИЛИ - НЕ, на эти же ЛЭ подаются старшие Эти сигналы отображаются на выходах 1 разряды ВВ, Если хоть в каком-то разряде группы в соответствующих разрядах. Сигна- на выходе ЛЭ ЗИЛИ - НЕ будут три нуля. на лы с выходов группы НП подаются на ЛЭ выходе ЛЭ 12 И - НЕ появится единица - сиг- ЗИ - НЕ блока информации(на вторые входы нал запрещения ВВ, Так проверяется соот- ЛЭ). На первые входы этих ЛЭ подаются 35 ношение младших и старших разрядов ВВ. сигналы с выхода входного регистра в млад- Если сигнал запрещения не появился, начиших разрядах. А на третьи выходы подаются нается последовательное заполнение сдвиединицысблокасинхронизации,тоестьэти гового регистра единицами, Единица в сигналы не влияют на ЛЭ ЗИ - НЕ. На выходепервом разряде сдвигового регистра подаст ЛЭ ЗИ - НЕ появится единица в том разряде, 40 на вход группы НП ноль в первом разряде, в котором хоть на одном входе будет ноль, . если этот разряд предлагается в ВВ, и едиЭта единица инвертируется и ноль подается ницу(точнее я-состояние), если не предлагана входы 2 группы НП и на входы младших ется, И эта же единица блокирует первый разрядов регистра хранения. Входы этого разряд в схеме анализа, то есть этот разряд регистра открыты сигналам ПРИЕМ ТС, а 45 уже не можетбыть причиной появления сиг. выходы открыты все время подключением нала запрета, Так проверяется соотношеВОк корпусу, Навыходесхемы вводавНП ние первого разряда с остальными будут нули в тех разрядах, которые могут старшими. Если сигнал запрета не появилпредлагаться в ВВ по младшим разрядам. ся, то далее проверяется второй разряд, заНа выходах 2 группы НП будут нули в тех 50 тем третий и т.д, до тех пор, пока не разрядах, которые могут предлагаться в ВВ появится сигнал запрета или пока не поя- . по старшим разрядам, При пропадании сиг- вится единица в последнем разряде сдвигонала ПРИЕМ ТС входной регистр запирает- вого регистра, которая разрешает выдачу ся по входу и выходу (в нем фиксируется ВВ,информация о ТС), регистр хранения - по 55 Проверка очередного ВВ начинается с входу, а блок синхронизации практически появлением сигнала ЗАПУСК (информациисключается (ноль на входе ЛЭ 2 ИЛИ-НЕ онный уровень - единица). Очередной ВВ превращает его в инвертор), Таким обра- должен быть в ЩДвх до момента прихода зом, в регистре хранения фиксируется ин- перепада с нуля вединицусигнала ЗАПУСК.Сигнал ЗАПУСК, инвертируясь в блоке синхронизации, подается на вход ЛЭ 2 ИЛИНЕ, куда подается и сигнал ПРИЕМ ТС. Это необходимо с целью исключения влияния сигнала ЗАПУСК во время действия сигнала ПРИЕМ ТС. При отсутствии сигнала ПРИЕМ ТС единица сигнала ЗАПУСК поступает на формирователь импульса на элементах С 1, В 1. Сигнал с резистора 81 открывает регистр в блоке синхронизации по входу и в него записывается предлагаемый ВВ, Этот же сигнал обнуляет сдвиговый регистр и опрокидывает триггер, собранный на двух ЛЭ 2 ИЛИ-НЕ. Для рассмотрения динамики работы УСИ удобно воспользоваться временными диаграммами, изображенными на фиг.7. На нем обозначено: 1 - сигнал на верхнем по схеме входе триггера блока синхронизации; 2 - сигнал на выходе триггера, 3 - сигнал на входе ЛЭ 2 ИЛИ - НЕ, к которому подключен выход триггера; 4 - сигнал на выходе автоколебательного мультивибратора (АМВ), собранного на двух ЛЭ 2 ИЛИ - НЕ и элементах Р 2, КЗ, С 2, СЗ, В начале предположим в результате проверки предыдущего ВВ принято решение о его запрещении, о чем свидетельствует единица на выходе триггера (это есть сигнал ЗАПРЕТ) и на верхнем входе триггера, а она там может появиться только, если на выходе сдвигового регистра в 12 разряде ноль, а на входе ЛЭ 12 И-НЕ схемы анализа второго - единица, Единица на выходе этого ЛЭ может появиться либо в результате действия на его входе нуля (анализ второй), либо в результате действия единицы на входе разрешения ВО (анализ первый). Очередной ВВ должен быть установлен до появления сигнала ЗАПУСК. При появлении сигнала ЗАПУСК на выходе триггера устанавливается ноль, который через ЛЭ 2 ИЛИ - НЕ и инвертор разрешает генерацию АМВ (до этогоона была запрещена), Через некоторое время с момента появления сигнала ЗАПУСК на верхнем входе триггера появляется ноль. Тактовые импульсы с АМВ подаются на синхровход сдвигового регистра, Предположим, схема сравненияне выдала сигнала запрета, не выдала его и схема сравнения , тогда анализпродолжается дальше - происходит заполнение единицами сдвигового регистра, Если на выходе этого регистра в последнем разряде появится единица, то значит анализ дал положительный результат, По фронту некоторого тактового импульса (на временных диаграммах после многоточия) на 12-м выходе сдвигового регистра появляется единица (это есть сигнал ВЫДАЧА). Эта единица, проходя через ЛЭ 2 ИЛИ-НЕ и инвертор, запрещает генерацию АМВ, проходя через инвертор, откры вает регистр в блоке синхронизации и разрешает выдачу текущего ВВ, а поступая нэ вход ЛЭ 2 ИЛИ-НЕ, куда подается и проинвертированный сигнал запрета, не допускает действия сигнала запрета (и его выдачу) в случае, если следующий В В вызовет появление этого сигнала в схеме сравненияили в схеме сравнения . Допустим, такая ситуация возникла, тогда при подаче сигнала ЗАПУСК обнуляется сдвиговый регистр и сигнала ВЫДАЧА пропадает, практически одновременно с этим на верхнем входе триггера устанавливается единица, но на 5 10 входе триггера пока ноль, так как на нижнем его входе действует единица. Через некоторое время потенциал на резисторе Й 1 становится ниже порога срабатывания ЛЭ 2 ИЛИ - НЕ и на выходе триггера устанавливается единица, генерация АМВ запрещается, Предположим, на входе УСИ подали 20 новый ВВ, который вызывает сигнал запрета сразу же, но в виду того, что новый ВВ устанавливается не сразу, сигнал запрета сначала пропадает, а затем снова появляется (это показано на временной диаграмме). При подаче сигнала ЗАПУСК генерация АМВ разрешается только на время полутакта при равенстве номиналов резисторов и конденсаторов и снова запрещается, Таким образом, в УСИ у ЩДвх, ШДтс, ЩДвых информированный уровень ноль, а у сигналов ПРИЕМ ТС, ЗАПУСК, ВЫДАЧА, ЗАПРЕТ - единица.Важное место занимает вопрос выбора частоты генерации АМВ, то есть быстродействие УСИ, Максимально возможная частота следования тактовых импульсов будет определяться следующим образом, последовательной работой блока синхронизации,40 блока информации и сравнения:+ 4 х 2 или.неТгде тс,з, - время прохождения сигала в сдвиговом регистре по синхровходу;тБ,с. - время прохождения сигнала в буферном элементе с разрешением блока синхронизации;гз и-не - время прохождения сигнала в ЛЭ ЗИ - НЕ блока информации;хне - время прохождения сигнала в инверторе блока синхронизации;тз или.не - время прохождения сигнала вЛЭ ЗИЛИ-НЕ схемы сравнения первого;т 5 или-не - время прохождения сигналав ЛЭ 5 ИЛИ - НЕ; 45 50 55 25 30 35 Рвах = ( тс,Р, +Б,с. + тзи-не + Зле +гц и г время прохождения сигнала в ЛЭ 12 И Нг;гг илии: - время прохождения сигнала в ЛЭ 2 ИЛИ -НЕ в блоке синхронизации,Чэсготу следует выбирать меньше максимальной с учетом различного рода нестабильностей, Частота генерации АМВ устанавливается резисторами й 2, ВЗ и конденсаторами С 2, СЗ. Необходимо выдерживать; В 1 = Р 2 = ЯЗ, С 1 = С 2 = СЗ. При указанных на схеме номиналах частота равна примерно 2 МГц, Увеличение произведения Я 2.СЗ вызывает пропорциональное ему уменьшение частоты, Желательно номиналы резисторов не уменьшать.Перечисленные выше конструктивные элементы выполнены следующим образом: входной регистр на основе К 531 ИР 22, регистр хранения и регистр синхронизации - К 555 ИР 22, сдвиговый регистр КМ 55 ИР 8, ЛЭ ЧИ - К 555 ЛИ 6, ЛЭ ЗИ - НЕ - К 555 ЛАЧ, ЛЭ 12 И - Н Е - К 531 ЛА 19, ЛЭ 2 ИЛИ - НЕ - К 555 ЛВ 1, ЛЭ ЗИЛИ - НЕ - К 555 ЛВЧ, ЛЭ 5 ИЛИ - НЕ - К 531 ЛВ 7, буферные инвертирующие ЛЭ, выходы которых подключены к НГ 1-К 531 ЛН 1, остальные буферные инвертирующие ЛЭ-К 555 ЛН 1, инвертирующие ЛЭ с разрешением - К 155 ЛП 8,Предлагаемое устройство обладает значительно более широкими возможностями, чем его прототип. Путем задания необходимых исходных данных (х 13, Ц=1,1) устройство может быть переведено в желаемый режим работы, когда оно будет выделять только соответствующие данному режиму кодовые слова. Формула изобретения Устройство сортировки информации.содержащее входной регистр, регистр хранения. первую и вторую схемы сравнения, 5 причем первый информационный вход устройства соединен с информационным входом входного регистра, вход синхронизации устройства - с входами синхронизации входного регистра и регистра 10 хранения, выход кОторого соединен с первым информационным входом первой схемы сравнения, второй информационный вход устройства - с вторым входом первой схемы сравнения и с первым входом второй 15 схемы сравнения, о тл и ч а ю щ е е с я тем,что, с целью расширения области применения зэ счет возможности адаптации устройства к различным типам входных данных, оно дополнительно содержит блок инфор мации и блок синхронизации, причем выходвходного регистра соединен с входом блока информации, первый и второй выходы которого подключены соответственно к второму входу второй схемы сравнения и к входу 25 регистра хранения, второй информационный вход устройства соединен с информационным входом блока синхронизации, выход которого соединен с информационным выходом устройства, выходы равенства 30 первой и второй схем сравнения соединенысоответственнос первым и вторым стробирующими входами блока синхронизации, выходы сопровождения информации которого подключены соответственно к выходам 35 признаков разрешения и запрещения выдачи информации устройства, вход пуска устройства подключен к входу пуска блока синхронизации.