Устройство сортировки информации Советский патент 1993 года по МПК G06F7/10 

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

Целью изобретения является расширение области применения устройства за счет возможности адаптации его к различным типам входных данных.

Пусть в качестве сортируемой информации служит массив 1-разрядных кодовых

СЛОВ (21,22,...,Z|,,...Z|).

На выход устройства пропускаются только те слова, которые соответствуют им- пликантам булевой функции вида:

Л

(1)

F(Z1,Z2,...,Z|,...,Z|)A V($Z ) ,

- . .... .. 1 1

где ty ( Јi(zi ) - логическая функция двух переменных, принимающая значения у (0,0) 1; t/(0,1) 0; (1,0) 1; (1,1) 1;

Јг логическая переменная, определяемая следующим образом;

со

х О

00

00

I

Јi хн zi (Л, xij I zj) (Vxij

1

ll):

Н

xij zj -штрих Шеффера; xij; Jj; i,j 1,1- логические переменные, составляющие входные данные и предназначенные для задания режима работы устройства, т.е. совокупности выделяемых из исследуемого массива кодовых слов.

В качестве иллюстрации рассмотрим вариант применения описываемого устройства для исследования ремонтопригодности некоторой технической системы (фиг.1), состоящей из I 18 С4.

При этом в качестве входных данных должна использоваться следующая информация:

xij; i,j 1,1 - переменные, характеризующие структуру исследуемой системы (xji 1, если i-ая составная часть (СЧ) включает в свой состав j-ю СЧ; xij 0 - в противном случае);

Jj; j 1,1 - переменная, характеризующая техническое состояние (ТО) системы (Jj 1, если имеет место отказ j-й СЧ; Jj 0 - в противном случае).

В рассматриваемом случае любой имп- ликант функции (1), т.е. выделяемое кодовое слово, характеризует возможный вариант восстановления (ВВ) исследуемой системы. Данный вариант предусматривает замену только отказавших СЧ или СЧ содержащих отказавшие и исключает кратные замены, т.е. одновременные замены некоторых СЧ и СЧ их содержащих.

Значения xij и Jj сведены в таблицу (фиг.2). Определим совокупность выделенных кодовых слов применительно к приве денным исходным данным, для чего определим §1, Ј2,...-, §18.

§1 Z1 -Z3 24 25 28 Z9 210 tZ11 212 Z13 214; §2 Z2-Z6 Z7 Z15 Z16 Z17 Z18;

§3 0; §4 0 ; §5 Z5-Z12-Z13-Z14:

§6 ze zis zie; §7 0; §8 0; §9 0; Ј10 0; §11 0; §12 0; §13 zn; §14 0; §15 0; §ie zie: §17 0; §18 0. С учетом этого запишем:

F(Z1 ,Z2 , . . . Zl8)V(Јl ,Z1 ) V ( §2 . 22 } 23 Z4 ф ( §5 . Z5 )

ip (§6 . ze ) z 2a zg zio 211

Z12 V(§13Z13 ) Z14 Z15 1/(§16Z , 16 ) 217 Z18 .

Импликантами данной функции и соответствующими им кодовыми словами являются:

18 Zl Д zj ------ 100000000000000000

i--L18

zrz2-A-Z| ----- v 010000000000000000

J

18

Z1Z2Z3Z4Z5 Az| ---.-н. 000010000000000000

Наличие а 1-й и т.д. позиции кодового слова I свидетельствует о необходимости замены 1-й СЧ согласно характеризуемому данным кодовым словом ВВ, 0 Рассмотренная и проиллюстрированная задача решается с помощью устройства сортировки информации (УСИ) благодаря тому, что оно содержит (фиг.З):

1 - входной регистр; 5. 2 - регистр хранения;

3 - схема сравнения I;

4 - схема сравнения II;

5 - блок информации; 6- блок синхронизации,

0 Информация о значениях Jj(tC) поступает на входной per истр 1. С выхода этого блока информация поступает через наборное поле (НП), входящее в состав информа- ционного блока 5 и определяющее

5 посредством соответствующей коммутации значения xij, на регистр хранения 2.

Кодовое слово (zi,Z2,....,zi,,..,zi) (ВВ) поступает на схемы сравнения I и II и далее в зависимости от результатов его сравнения с

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

Указанное выше НП состоит из ячеек, состав и соединение которых представлены на фиг.5. Каждая из ячеек состоит из двух диодов и переключения. На фиг.4 представ0 лена схема коммутации НП применительно к рассмотренному иллюстративному примеру.

Заштрихованы те ячейки НП, в которых необходимо замкнуть контакты выключате5 лей для отображения НП приведенной для примера системы. На фиг.5 обозначены входы и выходы первой и второй групп ячеек. Если контакты выключателей некоторой ячейки разомкнуты, то независимо от вход0 ных сигналов этой ячейки ее выходные уровни обеих групп при условии, что они подаются на логические элементы (ЛЭ) серий ТТЛ, будут восприниматься этими ЛЭ как уровень логической единицы. Если кон5 такты замкнуты, то выходные сигналы обеих групп полностью соответствуют входным. Поэтому в УСН применяются ЛЭ серий ТТЛ и информационным уровнем в НП является уровень логического нуля.

На фиг.6 изображена функциональная электрическая схема УСН для анализа 30-ти позиционных кодовых слов. Рассмотрим как анализируется информация. Этот анализ начинается с подачей сигнала Прием ТС. При появлении этого сигнала (информационный уровень - единица) входной регистр единицей на входе РЕ открывается по входу и сигналы в ШДтс (информационный уровень - ноль) фиксируется в регистре, Значит информация о ТС должна быть в ШДтс до поступления сигнала ПРИЕМ ТС и находиться там во время действия сигнала ПРИЕМ ТС. Сигнал ПРИЕМ ТС подается на инвертор в блоке синхронизации. С выхода этого инвертора ноль поступает на вход ВО входного регистра и открывает его по выходу, то есть на выходе регистра сигналы те же, что и на входе. Единица сигнала ПРИЕМ ТС подается на первые входы ЛЭ 2ИЛИ-НЕ блока синхронизации и на выходах этих ЛЭ независимо от ВВ, подаваемого на вторые входы ЛЭ 2ИЛИ-НЕ, будет ноль, который инвертируется и в старших разрядах подается на входы разрешения буферных ЛЭ с разрешением, устанавливая на их выходах Z-состояние, а выходы этих элементов подключены к выходам входного регистра. Сигналы с выхода входного регистра в старших разрядах подаются на входы I группы НП. Эти сигналы отображаются на выходах I группы в соответствующих разрядах. Сигналы с выходов I группы НП подаются на ЛЭ ЗИ-НЕ блока информации (на вторые входы ЛЭ). На первые входы этих ЛЭ подаются сигналы с выхода входного регистра в младших разрядах. А на третьи выходы подаются единицы с блока синхронизации, то есть эти сигналы не влияют на ЛЭ ЗИ-НЕ. На выходе ЛЭ ЗИ-НЕ появится единица в том разряде, в котором хоть на одном входе будет ноль. Эта единица инвертируется и ноль подаётся на входы 2 группы НП и на входы младших разрядов регистра хранения. Входы этого регистра открыты сигналам ПРИЕМ ТС, а выходы открыты все время подключением ВО к корпусу. На выходе схемы ввода в НП будут нули в тех разрядах, которые могут предлагаться в В§ по младшим разрядам. На выходах 2 группы НП будут нули в тех разрядах, которые могут предлагаться в ВВ по старшим разрядам. При пропадании сигнала ПРИЁМ ТС входной регистр запирается по входу и выходу (в нем фиксируется информация о ТС), регистр хранения - по входу, а блок синхронизации практически исключается (ноль на входе Л Э 2ИЛИ-НЕ превращает его в инвертор). Таким образом, в регистре хранения фиксируется информация о тех позициях, которые могут предлагаться в ВВ.

Рассмотрим работу схемы сравнения I, которая заключается в сравнении предлага- 5 емых позиций в ВВ с теми позициями, которые могут предлагаться в ВВ. На входы буферных элементов с разрешением схемы анализа подается информация с регистра хранения, а на входы разрешения - предла0 гаемый ВВ (информационный уровень ноль). На выходе буферного элемента будет ноль только тогда, когда на его входе единица, а на входе разрешения ноль, то есть, когда данная позиция не должна принимать

5 участие в В В, а она предлагается. Если хоть в одном разряде на выходе буферного элемента будет ноль, то на выходе ЛЭ 12И-НЕ схемы сравнения I появится единица - сигнал запрета,

0 Рассмотрим работу схемы сравнения II. Суть работы схемы состоит в следующем. Сначала, когда сдвиговый регистр в данном блоке обнулен, на выходах буферных элементов будет единица или z-состояние (в

5 зависимости от ВВ) и его выходы будут зависеть только от предполагаемого 88 в младших разрядах. Выходы блока синхронизации отображаются на выходах 2 группы НП, которые соединены со входами ЛЭ

0 ЗИЛИ-НЕ, на эти же ЛЭ подаются старшие разряды ВВ, Если хоть в каком-то разряде на выходе ЛЭ ЗИЛИ-НЕ будут три нуля, на выходе ЛЭ 12И-НЕ появится единица - сигнал запрещения ВВ. Так проверяется соот5 ношение младших и старших разрядов ВВ. Если сигнал запрещения не появился, начинается последовательное заполнениехдви- гового регистра единицами. Единица в первом разряде сдвигового регистра подаст

0 на вход I группы НП ноль в первом разряде, если этот разряд предлагается в ВВ, и единицу (точнее z-состояние), если не предлагается. И эта же единица блокирует первый разряд в схеме анализа, то есть этот разряд

5 уже не может быть причиной появления сигнала запрета. Так проверяется соотношение первого разряда с остальными старшими. Если сигнал запрета не появился, то далее проверяется второй разряд, за0 тем третий и т.д. до тех пор, пока не появится сигнал запрета или пока не поя- . вится единица в последнем разряде сдвигового регистра, которая разрешает выдачу ВВ.

5 Проверка очередного ВВ начинается с появлением сигнала ЗАПУСК (информаци- . онный уровень - единица). Очередной ВВ должен быть в ЩДвх до момента прихода перепада с нуля в единицу сигнала ЗАПУСК. Сигнал ЗАПУСК, инвертируясь в блоке синхронизации, подается на вход ЛЭ 2ИЛИ- НЕ, куда подается и сигнал ПРИЕМ ТС. Это необходимо с целью исключения влияния сигнала ЗАПУСК во время действия сигнала ПРИЕМ ТС. При отсутствии сигнала ПРИЕМ ТС единица сигнала ЗАПУСК поступает на формирователь импульса на элементах С1, R1. Сигнал с резистора R1 открывает регистр в блоке синхронизации по входу и в него записывается предлагаемый ВВ. Этот же сигнал обнуляет сдвиговый регистр и опрокидывает триггер, собранный на двух ЛЭ 2ИЛИ-НЕ. Для рассмотрения динамики работы УСИ удобно воспользоваться временными диаграммами, изображенными на фиг.7. На нем обозначено: 1 - сигнал на верхнем по схеме входе триггера блока синхронизации; 2 - сигнал на выходе триггера; 3 - сигнал на входе ЛЭ 2ИЛИ-НЕ, к которому подключен выход триггера; 4 - сигнал на выходе автоколебательного мультивибратора (АМВ), собранного на двух ЛЭ 2ИЛИ-НЕ и элементах R2, R3, С2, СЗ. В начале предположим в результате проверки предыдущего ВВ принято решение о его запрещении, о чем свидетельствует единица на выходе триггера (это есть сигнал ЗАПРЕТ) и на верхнем входе триггера, а она там может появиться только, если на выходе сдвигового регистра в 12 разряде ноль, а на входе ЛЭ 12И-НЕ схемы анализа второго - единица. Единица на выходе этого ЛЭ может появиться либо в результате действия на его входе нуля (анализ второй), либо в результате действия единицы на входе разрешения ВО (анализ первый). Очередной В В должен быть установлен до появления сигнала ЗАПУСК. При появлении сигнала ЗАПУСК на выходе триггера устанавливается ноль, который через ЛЭ 2ИЛИ-НЕ и инвертор разрешает генерацию АМВ (до этого она была запрещена). Через некоторое время с момента появления сигнала ЗАПУСК на верхнем входе триггера появляется ноль. Тактовые импульсы с АМВ подаются на син- хровход сдвигового регистра. Предположим, схема сравнения I не выдала сигнала запрета, не выдала его и схема сравнения II, тогда анализ И продолжается дальше - происходит заполнение единицами сдвигового регистра. Если на выходе этого регистра в последнем разряде появится единица, то значит анализ дал положительный результат. По фронту некоторого тактового импульса (на временных диаграммах после многоточия) на 12-м выходе сдвигового регистра появляется единица (это есть сигнал ВЫДАЧА). Эта единица, проходя через ЛЭ 2ИЛИ-НЕ и инвертор, запрещает генерацию АМВ, проходя через инвертор, открывает регистр в блоке синхронизации и разрешает выдачу текущего В В, а поступая на вход ЛЭ 2ИЛЙ-НЕ, куда подается и проин- вертированный сигнал запрета, не допускает действия сигнала запрета (и его выдачу) в случае, если следующий В В вызовет появление этого сигнала в схеме сравнения Гили в схеме сравнения II. Допустим, такая ситуация возникла, тогда при подаче сигнала ЗА- ПУСК обнуляется сдвиговый регистр и сигнала ВЫДАЧА пропадает, практически одновременно с этим на верхнем входе триггера устанавливается единица, но на входе триггера пока ноль, так как на нижнем

его входе действует единица. Через некоторое время потенциал на резисторе R1 становится ниже порога срабатывания ЛЭ 2ИЛ.И-НЕ и на выходе триггера устанавливается единица, генерация АМВ запрещается, Предположим, на входе УСИ подали новый ВВ, который вызывает сигнал запрета сразу же, но в виду того, что новый ВВ устанавливается не сразу, сигнал запрета сначала пропадает, а затем снова появляется (это показано на временной диаграмме). При подаче сигнала ЗАПУСК генерация АМВ разрешается только на время полутакта при равенстве номиналов резисторов и конденсаторов и снова запрещается, Таким

образом, в УСИ у ЩДвх, ШДтс, ЩДвых информированный уровень ноль, а у сигналов ПРИЕМ ТС, ЗАПУСК, ВЫДАЧА, ЗАПРЕТ - единица.

Важное место занимает вопрос выбора

частоты генерации АМВ, то есть быстродействие УСИ. Максимально возможная частота следования тактовых импульсов будет определяться следующим образом, последовательной работой блока синхронизации,

блока информации и сравнения:

Fmax ТС.Р. + Т Б.С. + ТЗИ-НЕ + ЗГНЕ +

45

+ ТЗ ИЛИ-НЕ + 5 ИЛИ-НЕ + fl2 И-НЕ +

+ 4Г2ИЛИ-НЕ 1

где Тс.з. - время прохождения сигала в сдвиговом регистре по синхровходу;

ТБ.С.- время прохождения сигнала в бу- ферном элементе с разрешением блока синхронизации;

7з И-НЕ - время прохождения сигнала в ЛЭ ЗИ-НЕ блока информации;

THE - время прохождения сигнала в инверторе блока синхронизации;

7з ИЛИ-НЕ - время прохождения сигнала в ЛЭ ЗИЛ И-НЕ схемы сравнения первого; ТВИЛИ-НЕ время прохождения сигнала вЛЭБИЛИ-НЕ;

П. и иг- премя прохождения сигнала в ЛЭ 12И HF::

г или-НЕ время прохождения сигнала п ЛЭ 2ИЛИ -НЕ в блоке синхронизации.

Частоту следует выбирать меньше максимальной с учетом различного рода неста- бильностей. Частота генерации АМВ устанавливается резисторами R2, R3 и конденсаторами С2, СЗ. Необходимо выдерживать: R1 R2 R3, С1 С2 СЗ. При указанных на схеме номиналах частота равна примерно 2 МГц. Увеличение произведения R2.C3 вызывает пропорциональное ему уменьшение частоты. Желательно номиналы резисторов не уменьшать.

Перечисленные выше конструктивные элементы выполнены следующим образом: входной регистр на основе К531ИР22, регистр хранения и регистр синхронизации - К555ИР22, сдвиговый регистр КМ55ИР8, ЛЭ ЧИ-К555ЛИ6, ЛЭ ЗИ-НЕ-К555ЛАЧ, ЛЭ 12И-НЕ-К531ЛА19, ЛЭ 2ИЛИ-НЕ- К555ЛВ1, ЛЭ ЗИЛИ-НЕ-К555ЛВЧ, ЛЭ 5ИЛИ-НЕ-К531ЛВ7, буферные инвертирующие ЛЭ, выходы которых подключены к НП-К531ЛН1, остальные буферные инвертирующие ЛЭ-К555ЛН1, инвертирующие ЛЭ с разрешением - К155ЛП8.

Предлагаемое устройство обладает значительно более широкими возможностями, чем его прототип. Путем задания необходимых исходных данных (xij, Jj, I.,I) устройство может быть переведено в желаемый режим работы, когда оно будет выделять только соответствующие данному режиму кодовые слова.

Формула изобретения Устройство сортировки информации, содержащее входной регистр, регистр хранения, первую и вторую схемы сравнения, 5 причем первый информационный вход устройства соединен с информационным входом входного регистра,вход синхронизации устройства - с входами синхронизации входного регистра и регистра

0 хранения, выход которого соединен с первым информационным входом первой схемы сравнения, второй информационный вход устройства - с вторым входом первой схемы сравнения и с первым входом второй

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

5 регистра хранения, второй информационный вход устройства соединен с информационным входом блока синхронизации, выход которого соединен с информационным выходом устройства, выходы равенства

0 первой и второй схем сравнения соединены соответственно с первым и вторым строби- рующими входами блока синхронизации, выходы сопровождения информации которого подключены соответственно к выходам

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

Изобретение относится к вычислительной технике. Цель изобретения состоит в расширении области применения устройства за счет возможности адаптации его к различным типам входных данных. На вход данного устройства подается массив кодовых слов. Некоторая совокупность слов из данного массива передается на выход устройства. Вид этой совокупности определяется режимом работы устройства, который, в свою очередь, зависит от входных данных. Поставленная цель достигается тем, что в состав устройства анализа информации введены дополнительно блок информации и блок синхронизации. В состав блока информации входит наборное поле, коммутация которого в сочетании с входными данными позволяет изменять режим работы устройства. Блок синхронизации осуществляет синхронизацию работы составных частей устройства. Предлагаемое устройство позволяет решать различные задачи, связанные с сортировкой исходной информации по различным группам. 7 ил. (Л

&г/

Фиг2

ШДтс

I

прием

ШДтс

запуск)i II in ни i in MIТ

a 9 ю и я я /4 /5 V V /6

+ шдвш.

запрет Sttfava

Фиг.З

3

ч ;5

7

Шлге

Фиг. $

/гя/А

и/г

Фиг. 6а

2пф

4 ffWidzx xtyrt/ I

bVWftAx

I

eeomi

Vt.

ф

&Л

N.

аА«.

Рш.6;