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

(54) УСТРОЙСТВО для СОРТИРОВКИ ИНФОРМАЦИИ

длительность и сложность контроля матриц реальных размеров.

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

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

Благодаря такой конструкции ячейки обеспечивается эффективный контроль устройства для сортировки информации: тест на одиночные неисправности в этом случае не зависит от размеров матрицы и состоит из 18 наборов.

На фиг. 1 приведена функционально-логическая схема ячейки предлагаемого устройства; на фиг. из вариантов проверяющего теста.

Ячейка имеет входы 1, 2, 3, 4, 5, 6, 7 переменных Z, X, у, г, S, t, и соответственно и выходы 8, 9, 10, 11, 12, 13, 14 переменных z, х , у , г , s, t, и соответственно, содержит триггер 15 с входными элементами И 16 и 17, элементы И 18, 19, 20, 21, 22 и элементы ИЛИ 23,24.

Ячейка реализует функции:

х (xvaz) t;

г (xvaz)svazrvyz;

qi ux;

,

где a - хранимый в триггере бит информации, Qi и 9о - сигналы установки «1 и «О.

Переменные г, s, t служат для контроля устройства. В рабочем режиме , s 0, t 1. При этом , (avy) и устройство работает так, как описано в авт. св. № 424141.

Рассмотрим организацию тестового контроля предлагаемого устройства.

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

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

В качестве допустимого перечня неисправностей примем кратные константные неисправности одновременно в одной ячейке устройства. Как известно, при этом проверяющий

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

ничтожно мала.

Набор е (см. фиг. 2) проверяет некоторую неисправность /, если внесение этой неисправности изменяет значение выхода на этом наборе, т. е. /(s) (e), где / - функция, реализуемая исправной схемой, а fj - функция, реализуемая схемой при наличии в ней неисправности /.

Пара наборов p°pi проверяет отсутствие обеих константных неисправностей в точке //

ячейки, что обозначено в таблице на фиг. 2 через //(р°) и //(р ). Набор а(ао) проверяет может ли сигнал в некоторой точке принять значение 1(0), т. е. отсутствие в данной точке

неисправности «Тождественный 0(1).

Наборы 1-13 являются проверяющими для всех ячеек устройства. Рассмотрим, например, пару наборов 5 и 6. На этих наборах от входа z к выходу z в ячейке проходит существенный путь через точку /°. Константная неисправность в этой точке сделает постоянным значение сигнала на обоих наборах. Это верно для цепочки ячеек любой длины, следовательно, для этих наборов длина теста не зависит от числа ячеек в схеме.

Для предотвращения состязаний при перестройке в тест введены противогоночные на боры (3 и 9). Для неисправностей, проверяемых на набоpax 14-18 требуется деление схемы на зоны и построение проверяющих наборов для каждой зоны отдельно.

Наборы 14а и 15а подаются на четные строки матрицы в то же время, когда на нечетные

строки подаются наборы 146 и 15Ь.

При подаче наборов 16-18 все столбцы матрицы делятся на три зоны: А, В, С. Если i - номер столбца (, 2,...), то в зону Л попадут столбцы, для которых (mod3), в

B - (niod3) и в С (mod3). Наборы 16 а, Ь, с подаются одновременно в зоны А, В, С соответственно, затем подаются наборы 17а, Ь, с Е далее-18а, Ь, с. При этом наборы 16 проверяют столбцы зоны В, 17-А,

а 18-С.

Рассмотрим, например, наборы 16. Набор 16 а задает в своем столбце г , так как набор 16с обрывает прохождение сигнала z (так как ) и открывает

прохождение сигнала по х (от входов z), так как . Если в столбце зоны В (набор 16 &) в какой-либо ячейке , т. е. имеется единичная неисправность / 1, то получим в этой ячейке и в столбце зоны

вместо .

Поскольку набор 16 проверяет только каждый третий столбец, для проверки всей .схемы требуются еще наборы 17 и 18.

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

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

Так, например, в однородной матрице предлагаемого устройства облегчается синтез различных автоматов, так как можно дополнительно использовать для настройки схем сигналы г, S, t. Так, подавая в некоторую строку матрицы / 0, можно изолировать схемы по горизонтали, подавая в некоторый столбец , можно осуществить поворот переменной X из столбца в строку и т. д.

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

Устройство для сортировки информации по авт. св. № 424141, отличающееся тем, что, с целью повышения эффективности контроля, в каждую ячейку устройства введены три дополнительных элемента И, причем выход первого элемента И соединен с одним из входов первого дополнительного элемента И, другой вход которого подключен к первой дополнительной шине, а выход соединен с одним из входов второго элемента ИЛИ, выход первого элемента ИЛИ соединен с одним из входов второго и третьего дополнительных элементов И, другие входы которых подключены ко второй и трегьей дополнительным шинам, а выходы-к второму логическому выходу ячейки и к входу второго элемента ИЛИ соответственно.

Источники информации, принятые во внимание при экспертизе

1Авторское свидетельство СССР №376807, кл. G 11с 15/00, 24.04.71.

2Kautz W. Н. «Cellular logic-in-memory arrays, IEEE Trans., 1969, c-18 № 8, p. 719- 727.

. -.

;

580553

Только крайнего fSsSoec cmo/tSna.