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

 

рц 580553

ОПИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Оаюз Ооветеких

Социалистических

Республик (61) Дополнительное к авт. свид-ву 424141 (22) Заявлено 18.07.75;(21) 2158428/24 с присоединением заявки № (23) Приоритет (43) Опубликовано 15.11.77. Бюллетень № 42 (45) Дата опубликования описания 10.11,77 (51) М. Кл. С 06F 7/02

Государственный комитет

Совета Министров СССР по делам изобретений и открытий (53) УДК 681.325.5 (088.8) (72) Авторы изобретения

И. В. Коган и Я. И. Фет

Институт математики Сибирского отделения АН СССР (71) Заявитель (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦИИ

Д

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

Недостатком устройства является сложность организации тестового контроля. Для таких схем длина минимального теста на одиночные неисправности пропорциональна числу входов схемы, то есть зависит от числа ячеек матрицы.

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

Основное устройство выполнено в виде однородной матрицы. Каждая ячейка этой матрицы содержит триггер и элементы И и ИЛИ.

Первые входы первого и второго элементов И каждой ячейки соединены с первым логическим входом этой ячейки, выход первого элемента И соединен с первыми входами первого и второго элементов ИЛИ, вторые входы первого и второго элементов ИЛИ соединены соответственно со вторым логическим входом ячейки и выходом второго элемента И, выход второго (первого) элемента ИЛИ соединен с

10 первым (вторым) логическим выходом ячейки, второй вход второго элемента И соединен с третьим логическим входом ячейки, а второй вход первого элемента И вЂ” с выходом триггера.

Подлежащие сортировке числа хранятся в триггерах соответствующих строк однородной матрицы. При подаче определенных управляющих сигналов на входы левой и верхней границ матрицы сигнал «1» появляется на выходе правой границы только в той строке, где содержится максимальное число. Сортировка осуществляется путем последовательного выделения максимальных чисел.

Недостатком основного устройства для сор25 тировки информации является сложность организации тестового контроля. Как известно, для таких схем длина минимального теста на одиночные неисправности пропорциональна числу входов схемы, то есть зависит от числа

30 ячеек матрицы. Этим определяется большая

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

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

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

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

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

Ячейка имеет входы 1, 2, 3, 4, 5, 6, 7 переменных z, х, у, r, s, t, и соответственно и выходы 8, 9, 10, 11, 12, 13, 14 переменных z, х, у, r, s, t, и соответственно, содержит триггер

15 с входными элементами И 16 и 17, элементы И 18, 19, 20, 21, 22 и элементы ИЛИ 23,24.

Ячейка реализует функции: х = (xvaz) t;

z = (xvaz) svazrvyz;

q =ux;

gp= Qy, где а — хранимый в триггере бит информации, д и чо — сигналы установки «1» и «О».

Переменные r, s, t служат для контроля устройства. В рабочем режиме r= 1, s=0, t=

=1. При этом х =xvaz, z =z(avy) и устройство работает так, как описано в авт. св.

Хо 424141.

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

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

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

Зо

4

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

Набор в (см. фиг. 2) проверяет некоторую неисправность 1, если внесение этой неисправности изменяет значение выхода на этом наборе, т. е, /(в) (;(в), где f — функция, реализуемая исправной схемой, а /, — функция, реализуемая схемой при наличии в ней неисправности j.

Пара наборов Щ проверяет отсутствие обеих константных неисправностей в точке Ii, ячейки, что обозначено в таблице на фиг. 2 через Р(р ) и jl. (6 ). Набор а (ap) проверяет может ли сигнал в некоторой точке принять значение 1(0), т. е. отсутствие в данной точке неисправности «Тождественный 0(1)».

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

Для предотвращения состязаний при пере стройке в тест введены противогоночные на боры (3 и 9).

Для неисправностей, проверяемых на набо. рах 14 — 18 требуется деление схемы на зоны и построение проверяющих наборов для каждой зоны отдельно, Наборы 14а и 15а подаются на четные строки матрицы в то же время, когда на нечетные строки подаются наборы 14b и 15b.

При подаче наборов 16 — 18 все столбцы матрицы делятся на три зоны: А, В, С. Если

i — номер столбца (i=1, 2,...), то в зону А попадут столбцы, для которых i=2 (mod 3), в

 — i=1 (mod3) и в С вЂ” i=0 (mod3). Наборы 16 а, о, с подаются одновременно в зоны

А, В, С соответственно, затем подаются наборы 17а, b, с и далее — 18а, b, с. При этом наборы 16 проверяют столбцы зоны В, 17 — А, а 18 — С.

Рассмотрим, например, наборы 16. Набор

16а задает в своем столбце z =1, так как

x=s= l; набор 16 с обрывает прохождение сигнала z (так как r=s=y=0) и открывает прохождение сигнала по х (от входов z), так как v=t= l. Если в столбце зоны В (набор

16 b) в какой-либо ячейке 1„ ФО, т. е. имеется единичная неисправность I„ = 1, то получим в этой ячейке z = 1 и в столбце зоны С х = 1 вместо х =О, 580553

Фиг. 1

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

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

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

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

s=1, можно осуществить поворот переменной х из столбца в строку и т. д, Формула изобретения

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

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

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

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

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

25 2. Qautz 1Ч. Н. «Cellular logic-in-memory

arrays», IEEE Trans., 1969, с-18 № 8, р. 719—

727.

Праберяемые точки и mun наоора

8ZOOh/

У njn

Выхааы

orna o&a Y 6 1

/у (()

Пр оти бог оночныи

/ (o)

/; /a (,/з ./

/,/,„ );ycmaao1&a v д б

/õ (ойдо)

Пращибо ганачныи

/й()

/х ) /< (/3 /; /» (0 )1 v((x )

/,,/(/з ); /,,/„ (с )-нечегпн, 1

3 ф

6

9

12

14о

196

15а

15h

16а

166

/ ó / / /а ) mog д=2

/2 // /1 (о1 о) О аа д

16 С

17а

17h

17С

16а

16Ь

16 С

/ / /1(w ) moor Л=б

* i аАько для кра /чего,.ооогс -mod0ga.

Составитель В. Белкин

Техред И. Рыбкина

Корректор О. Тюрина

Редактор Н. Хлудова

Подписное

Типография, пр. Сапунова, 2

Заказ 2794/8 Изд. № 889 Тираж 818

НПО Государственного комитета Совета Министров СССР по делам изобретений и открытий

113035, Москва, К-35, Раушская наб., д. 4/5