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

 

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

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

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

РЕСПУБЛИК (505 G 06 F 7/10

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ по различным группам. 7 ил. (21) 4767957/24 (22) 08.12.89 (46) 23.05.93. Бюл. М 19 (72) И.И,Западаев, Н,А.Глущенко и В.В.Заруба (56) Шевкопляс Б.В, Микропроцессорныеструктуры. — М: Радио и связь. 1986, с.249, рис,11.16. (54) УСТРОЙСТВО СОРТИРОВКИ ИНФОРМАЦИИ (57) Изобретение относится к вычислительной технике. Цель изобретения состоиг в расширении области применения устройства за счет возможности адаптации его к различным типам входных данных, На вход данного устройства подается массив кодовых слов. Некоторая совокупность слов из

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

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

СЛОВ (21 22 .21 ".2!)

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

5U „, 1817088 À1 данного массива передается на выход устройства. Вид этой совокупности определяется режимом работы устройства, который, в свою очередь, зависит от входных данных.

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

F(z1,z2,...ä,...,zl) =Л ф (ф zi ) (1) (=1 где tP (g,2() — логическая функция двух пе-. ременных, принимающая значения ф(0,0) =

=1; 1/) (0,1) = 0; ф(1,0) = 1; 1/) (1,1) = 1; ф- логическая переменная, определяемая следующим образом:

l ф =xil zl (А xl) I т ) (vxij- li);

i=1 =1

)Ф! хц zj — штрих Шеффера; х((,,3, Ц = 1,! — логические переменные, составляющие входные данные и предназначенные для задания режима работы уст1817088 ройства, т.е, совокупности выделяемых из исследуемого массива кодовых слов.

В качестве иллюстрации рассмотрим вариэнт применения описываемого устройства для исследования ремонтопригодности некоторой технической системы (фиг.1), состоящей из I = 18 С4, При этом в качестве входных данных должна использоваться следующая информация: х11, 1,1 = 1,1 — переменные, характеризующие структуру исследуемой системы (xi = 1, если i-эя состэвнэя часть (СЧ) включэет в свой состав j-ю СЧ; х11 = Π— e противном случае); .1;; J = 1,1 — переменная, характеризующая техническое состояние (ТО) системы (Jl=

= 1. если имеет место отказ J-й СЧ; JI = О - в противном случае).

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

Данный вариант предусматривает замену только отказавших СЧ или СЧ содержащих отказавшие и исключает. кратные замены, т.е. одновременные замены некоторых СЧ и

СЧ их содержащих.

Знэчения х11 и JI сведены в таблицу

{фиг.2), Определим совокупность выделенных кодовых слов применительно к приведенным исходным данным, для чего определим (1, (z,..., (18. 1= Z1 23 Z4 Z5 Z8 Z9 Z10 .Z11 212 213 214

Q= 22 26 27 215 216 217 Z18

13=- О, (4= 0; (5= 25 212 Z13 214: (6= 26 215 216;

Е7= О; (8= О; (9= О, 510= О; Ь1= О; 12= О, (13= Z13; 1 14=- О; (15= О; 16= 216: (17= 0; 418= О

С учетом этого запишем:

Г (21, 22.... 218) =ф((1,21) ф(52,22) 23 24 ф((5.25) ф ((б, 26 ) 27 28 29 Z10 211 Z12 ф(13 213 ) 214 Z15

1 ((162, 16) Z17 Z18.

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

18

z1 Л zi ----- 100000000000000000

1=-2

z1.zz A zl ---------- 010000000000000000

1=3

И

Z1zzz3z4z5 Л21 --- — -- 000010000000000000

1=6

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

1 — входной регистр;

2 — региртр хранения;

3 — схема сравнения 1;

4 — схема сравнения И;

5 — блок информации;

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

25 посредством соответствующей коммутации значения х11, на регистр хранения 2, Кодовое слово {21,22„...,21,...ä) (ВВ) поступает на схемы сравнения 1 и ll и далее в зависимости от результатов его сравнения с кодовыми словами допустимой совокупности выдается или не выдается нэ выход устройства через блок синхронизации 6, который осуществляет синхронизацию работы всех составных частей данного устройЗ5 ства.

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

Заштрихованы те ячейки НП, в которых необходимо замкнуть контакты выключате45 лей для отображения НП приведенной для примера системы. На фиг.5 обозначены входы и выходы первой и второй групп ячеек.

Если контакты выключателей некоторой ячейки разомкнуты, то независимо от входных сигналов этой ячейки ее выходные уровни обеих групп при условии, что они подаются на логические элементы (ЛЭ) серий ТТЛ, будут восприниматься этими ЛЭ как уровень логической единицы. Если кон55 такты замкнуты, то выходные сигналы обеих групп полностью соответствуют входным.

Поэтому в УСН применяются ЛЭ серий ТТЛ и информационным уровнем в НП является уровень логического нуля.

1817088

На фиг.б изображена функциональная формация о тех позициях, которые могут электрическая схема УСН для анализа 30-ти предлагаться в ВВ. позиционных кодовых слов. Рассмотрим Рассмотрим работу схемы сравнения I, как анализируется информация. Этот ана- которая заключается в сравнении предлагализ начинается с подачей сигнала Прием 5 емых позиций в ВВ с теми позициями, котоTC. При появлении этогосигнала(информа- рые могут предлагаться в ВВ, На входы ционный уровень — единица) входной ре- буферных элементов с разрешением схемы гистр единицей на входе PE открывается по анализа подается информация с регистра входу и сигналы в ШДтс (информационный хранения, а на входы разрешения — предла уровень — ноль) фиксируется в регистре, 10 гаемый ВВ (информационный уровень

Значит информация о ТС должна быть в ноль), На выходе буферногоэлемента будет

ШДтс до поступления сигнала ПРИЕМ ТС и ноль только тогда, когда на его входе едининаходиться там во время действия сигнала ца, а на входе разрешения ноль, то есть, ПРИЕМ ТС, Сигнал ПРИЕМ ТС подается на когда данная позиция не должна принимать инвертор в блоке синхронизации, С выхода 15 участие в ВВ, а она предлагается. Если хоть этого инвертора ноль поступает на вход BO в одном разряде на выходе буферного элевходного регистра и открывает его по выхо- мента будет ноль, то на выходе ЛЭ 12И-НЕ ду, то есть на выходе регистра сигналы те схемы сравнения I появится единица — сигже, что и на входе. Единица сигнала ПРИЕМ нал запрета.

TC подается на первые входы ЛЭ 2ИЛИ вЂ” НЕ 20 Рассмотрим работу схемы сравнения II. блока синхронизации и на выходах этих ЛЭ Суть работы схемы состоит в следующем. независимо от ВВ, подаваемого на вторые Сначала, когда сдвиговый регистр в данном входы ЛЭ 2ИЛИ вЂ” НЕ, будет ноль, который блоке обнулен, на выходах буферных элеинвертируется и в старших разрядах пода- ментов будет единица или г-состояние (в ется на входы разрешения буферных ЛЭ с 25 зависимости от BB) и его выходы будут заразрешением, устанавливая на их выходах висеть только от предполагаемого ВВ в

Z-состояние, а выходы этих элементов под- младших разрядах. Выходы блока синхроключены к выходам входного регистра, Сиг- низации отображаются на выходах 2 группы налы с выхода входного регистра в старших: НП, которые соединены со входами ЛЭ разрядах подаются на входы I группы НП. 30 ЗИЛИ вЂ” НЕ, на эти же ЛЭ подаются старшие

Эти сигналы отображаются на выходах I разряды ВВ, Если хоть в каком-то разряде группы в соответствующих разрядах. Сигна- на выходе ЛЭ 3ИЛИ вЂ” НЕ будут три нуля. на лы с выходов I группы НП подаются на ЛЭ выходе ЛЭ 12И вЂ” НЕ появится единица — сигЗИ вЂ” НЕ блока информации(на вторые входы нал запрещения ВВ. Так проверяется соотЛЭ). На первые входы этих ЛЭ подаются 35 ношение младших и старших разрядов ВВ. сигналы с выхода входного регистра в млад- Если сигнал запрещения не появился, начиших разрядах. А на третьи выходы подаются нается последовательное заполнение.сдвиединицысблокасинхронизации,тоестьэти гового регистра единицами, Единица в сигналы не влияют на ЛЭ ЗИ вЂ” НЕ. На выходе первом разряде сдвигового регистра подаст

ЛЭ ЗИ вЂ” НЕ появится единица в том разряде, 40 на вход I группы НП ноль в первом разряде, в.котором хоть на одном входе будет ноль, . если этот разряд предлагается в ВВ, и едиЭта единица инвертируется и ноль подается ницу(точнее z-состояние), если не предлагана входы 2 группы НП и на входы младших ется. И эта же единица блокирует первый разрядов регистра хранения. Входы этого разряд в схеме анализа, то есть этот разряд регистра открыты сигналам ПРИЕМ ТС, а 45 уже не можетбыть причиной появления сиг. выходы открыты все время подключением нала запрета. Так проверяется соотношеBO к корпусу. На выходе схемы ввода в НП ние первого разряда с остальными будут нули в тех разрядах, которые могут старшими. Если сигнал запрета не появилпредлагаться в BB по младшим разрядам. ся, то далее проверяется второй разряд, заНа выходах 2 группы НП будут нули в тех 50 тем третий и т.д. до тех пор, пока не разрядах, которые могут предлагаться в BB появится сигнал запрета или пока не поя- . по старшим разрядам, При пропадании сиг- вится единица в последнем разряде сдвигонала ПРИЕМ ТС входной регистр запирает- вого регистра, которая разрешает выдачу ся по входу и выходу (в нем фиксируется ВВ. информация о ТС), регистр хранения — по 55 Проверка очередного ВВ начинается с входу, а блок синхронизации практически появлением сигнала ЗАПУСК (информациисключается (ноль на входе ЛЭ 2ИЛИ-НЕ онный уровень — единица). Очередной ВВ превращает его в инвертор), Таким обра- должен быть в ЩДвх до момента прихода зом, в регистре хранения фиксируется ин- перепада с нуля вединицусигнала ЗАПУСК.

Сигнал ЗАПУСК, инвертируясь в блоке син1817088

10

ЗО

40

55 хронизации, подается на вход ЛЭ 2ИЛИНЕ, куда подается и сигнал ПРИЕМ ТС. Это необходимо с целью исключения влияния сигнала ЗАПУСК во время действия сигнала

ПРИЕМ ТС. При отсутствии сигнала ПРИЕМ

ТС единица сигнала ЗАПУСК поступает на формирователь импульса на элементах С1, й1. Сигнал с резистора R1 открывает регистр в блоке синхронизации по входу и в него записывается предлагаемый ВВ, Этот же сигнал обнуляет сдвиговый регистр и опрокидывает триггер, собранный на двух

ЛЭ 2ИЛИ-НЕ. Для рассмотрения динамики работы УСИ удобно воспользоваться временными диаграммами, изображенными на фиг.7. На нем обозначено: 1 — сигнал на верхнем по схеме входе триггера блока синхронизации; 2 - сигнал на выходе триггера, 3 — сигнал на входе ЛЭ 2ИЛИ вЂ” ME, к которому подключен выход триггера; 4 — сигнал на выходе автоколебательного мультивибратора (AMB), собранного на двух ЛЭ 2ИЛИ вЂ” НЕ и элементах R2, R3, С2, С3, В начале предположим в результате проверки предыдущего ВВ принято решение î его запрещении, о чем свидетельствует единица на выходе триггера (это есть сигнал 3АПРЕТ) и на верхнем входе триггера, а она там может появиться только, если на выходе сдвигового регистра в 12 разряде ноль, а на входе ЛЭ 12И-НЕ схемы анализа второго— единица, Единица на выходе этого ЛЭ может появиться либо в результате действия на его входе нуля (анализ второй), либо в результате действия единицы на входе разрешения ВО (анализ первый). Очередной

ВВ должен быть установлен до появления сигнала ЗАПУСК. При появлении сигнала

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

Тактовые импульсы с АМВ подаются на синхровход сдвигового регистра. Предположим, схема сравнения не выдала сигнала запрета, не выдала его и схема сравнения!!, тогда анализ lt продолжается дальше — происходит заполнение единицами сдвигового регистра, Если на выходе этого регистра в последнем разряде появится единица, то значит анализ дал положительный результат, По фронту некоторого тактового импульса (на временных диаграммах после многоточия) на 12-м выходе сдвигового регистра появляется единица (это есть сигнал

ВЫДАЧА). Эта единица, проходя через ЛЭ

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

2ИЛИ вЂ” НЕ и на выходе триггера устанавливается единица, генерация AMB запрещается, Предположим, на входе УСИ подали новый ВВ, который вызывает сигнал запрета сразу же, но в виду того, что новый ВВ устанавливается не сразу, сигнал запрета сначала пропадает, а затем снова появляется (это показано на временной диаграмме).

При подаче сигнала ЗАПУСК генерация

АМВ разрешается только на время полутакта при равенстве номиналов резисторов и конденсаторов и снова запрещается, Таким образом, в УСИ у ЩДвх, ШДтс, ЩДвых информированный уровень ноль, а у сигналов

ПРИЕМ ТС, ЗАПУСК, ВЫДАЧА, ЗАПРЕТ— единица.

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

I max = (тс.p. + w Б.с. + тзи-не + Зтне +

+ тЗ ИЛИ-HE + а ИЛИ-НЕ + Г12 И-HE+

+ 4 х2 или-не) где tc.3. — время прохождения сигала в сдвиговом регистре по синхровходу; тБ.с.— время прохождения сигнала в буферном элементе с разрешением блока синхронизации; тз и-не — время прохождения сигнала в

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

e ËÝ ЗИЛИ-НЕ схемы сравнения первого;. т5или-не — время прохождения сигнала в ЛЭ 5ИЛИ вЂ” НЕ;

1817088 га и г.- время прохождения сигнала в

ЦЭ 12Ð Нг" гг или-)и=- время прохождения сигнала в ЛЭ 2ИЛИ -HE в блоке синхронизации, Чэсготу следует выбирать меньше максимальной с учетом различного рода нестабильностей, Частота генерации AMB устанавливается резисторами R2, RÇ и конденсаторами С2, CÇ. Необходимо выдерживать: R1 = R2 = RÇ, C1 = С2 = C3. При указанных на схеме номиналах частота равна примерно 2 МГц, Увеличение произведения R2.CÇ вызывает пропорциональное ему уменьшение частоты. Желательно номиналы резисторов не уменьшать.

Перечисленные выше конструктивные элементы выполнены следующим образом: входной регистр на основе К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, Предлагаемое устройство обладает значительно более широкими возможностями, чем его прототип. Путем задания необходимых исходных данных (х 1,,3, Ц=1,1) устрой ство может быть переведено в желаемый режим работы, когда оно будет выделять только соответствующие данному режиму кодовые слова.

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

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

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

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

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

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

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

1817088

1817088! х.2гр, Фиг ба

18 1 7088

/ e А..

Я.з ,Вв

Фл. бЕ

Жг. 6d

1817088

Фиг. 6е

1817088

1817088

° 1.ег у 3 3 @

° ° °

Составитель И.Западаев

Техред М.Моргентал Корректор Л.Ливринц

Редактор Т.Иванова г

Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101

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

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

113035, Москва, Ж-35, Раушская на6„4/5