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

. - , - "к.1 Я,цццц МЬЬ О П И С А Н И Е р) 580553ИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Оаюз Ооеетеких Социалистических Республик(51) М,ип исоединением зая Государственный комнте Совета Министров СССР ло делам изобретенийи открытий(45) Дата опубликования описания 10.11,77 вторы обрете И, В, Коган и Я. 1) Заявител нститут математики Сибирского отделения АН ССС 54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦ Изобретение относится к области автоматики и вычислительной техники, предназначено для упорядочения информации и является усовершенствованием известного устройства, описанного в авт, св.424141, 5Известны ассоциативные устройства, в которых упорядочение информации производится путсм последовательного сравнения каждого элемента информации со всеми остальными элементами массива и подсчета соответ ствующего количества элементов меньших (или больших) данного 11.Недостатком устройства является сложность организации тестового контроля. Для таких схем длина минимального теста на оди ночные неисправности пропорциональна числу входов схемы, то есть зависит от числа ячеек матрицы.Известна также специализированная сортирующая матрица, в которой упорядочение ин формации производится путем массового сдвига всех элементов меньших (или больших) данного и записи очередного элемента в освободившуюся строку матрицы, устройство реализует алгоритм сортировки вставкой 21. Не достатком этого устройства является сложность организации тестового контроля.Основное устройство выполнено в виде однородной матрицы. Каждая ячейка этой матрицы содержит триггер и элементы И и ИЛИ, ЗО Первые входы первого и второго элементов И каждой ячейки соединены с первым логическим входом этой ячейки, выход первого элемента И соединен с первыми входами первого и второго элементов ИЛИ, вторые входы первого и второго элементов ИЛИ соединены соответственно со вторым логическим входом ячейки и выходом второго элемента И, выход второго (первого) элемента ИЛИ соединен с первым (вторым) логическим выходом ячейки, второй вход второго элемента И соединен с третьим логическим входом ячейки, а второй вход первого элемента И - с выходом триггера.Подлежащие сортировке числа хранятся в триггерах соответствующих строк однородной матрицы. При подаче определенных управляющих сигналов на входы левой и верхней границ матрицы сигнал 1 появляется на выходе правой границы только в той строке, где содержится максимальное число. Сортировка осуществляется путем последовательного выделения максимальных чисел.Недостатком основного устройства для сортировки информации является сложность организации тестового контроля. Как известно, для таких схем длина минимального теста на одиночные неисправности пропорциональна числу входов схемы, то есть зависит от числа ячеек матрицы. Этим определяется большаядлительность и сложность контроля матриц реальных размеров.Целью изобретения является повышение эффективности контроля устройства для сортировки информации.Это достигается тем, что в каждую ячейку устройства введены три дополнительных элемента И, причем выход первого элемента И соединен с одним из входов первого дополнительного элемента И, другой вход которого подключен к первой дополнительной шине, а выход соединен с одним из входов второго элемента ИЛИ, выход первого элемента ИЛИ соединен с одними из входов второго и третьего дополнительных элементов И, другие входы которых подключены ко второй и третьей дополнительным шинам, а выходы - ко второму логическому выходу ячейки и к входу второго элемента ИЛИ соответственно.Благодаря такой конструкции ячейки обеспечивается эффективный контроль устройства для сортировки информации: тест на одиночные неисправности в этом случае не зависит от размеров матрицы и состоит из 18 наборов,На фиг. 1 приведена функционально-логическая схема ячейки предлагаемого устройства; на фиг. 2 - один из вариантов проверяющего теста.Ячейка имеет входы 1, 2, 3, 4, 5, 6, 7 переменных г, х, у, г, з, 1, и соответственно и выходы 8, 9, 10, 11, 12, 13, 14 переменных г, х, у, г, з, 1, и соответственно, содержит триггер 15 с входными элементами И 16 и 17, элементы И 18, 19, 20, 21, 22 и элементы ИЛИ 23,24.Ячейка реализует функции:х= (хетаг) 1;г= (хоаг) зоаггоуг;дую=их;До= а,где а - хранимый в триггере бит информации, д и чо - сигналы установки 1 и 0,Переменные г, г, 1 служат для контроля устройства. В рабочем режиме г=1, э=О, 1= =1. При этом х=хоаг, г=г(аоу) и устройство работает так, как описано в авт. св.Мо 424141.Рассмотрим организацию тестового контроля предлагаемого устройства.Проверяющим тестом будем называть систему проверок, правильное прохождение которых говорит об отсутствии заданного перечня неисправностей (из допустимого перечня); диагностируюшим тестом - систему проверок, позволяющую определить неисправности (из допустимого перечня), присутствующие в схеме.Условия прохождения тестов: подача входных наборов (в заданном порядке) и фиксация выходных наборов сигналов (с анализом - для диагностирующего теста). Время действия набора на входах должно быть больше длительности переходных процессов в проверяемой схеме. 5 10 15 20 25 Зо 35 40 45 50 55 60 65 4В качестве допустимого перечня неисправностей примем кратные константные неисправности одновременно в одной ячейке устройства. Как известно, при этом проверяющий тест будет также практически достоверным тестом для всей структуры, поскольку условия компенсации неисправностей требуют очень сложного расположения совершенно определенных неисправностей, вероятность которого ничтожно мала.Набор в (см. фиг. 2) проверяет некоторую неисправность 1, если внесение этой неисправности изменяет значение выхода на этом наборе, т. е, (в) Ф;(в), где 1 - функция, реализуемая исправной схемой, а , - функция, реализуемая схемой при наличии в ней неисправности 1,Пара наборов Щ проверяет отсутствие обеих константных неисправностей в точке 1 ячейки, что обозначено в таблице на фиг. 2 через Р(ро) и 1,. ф). Набор а(ао) проверяет может ли сигнал в некоторой точке принять значение 1(0), т. е. отсутствие в данной точке неисправности Тождественный 0(1).Наборы 1 - 13 являются проверяющими для всех ячеек устройства. Рассмотрим, например, пару наборов 5 и 6, На этих наборах от входа г к выходу г в ячейке проходит существенный путь через точку 1 о Константная неисправность в этой точке сделает постоянным значение сигнала на обоих наборах. Это верно для цепочки ячеек любой длины, следовательно, для этих наборов длина теста не за. висит от числа ячеек в схеме.Для предотвращения состязаний при пере стройке в тест введены противогоночные на боры (3 и 9).Для неисправностей, проверяемых на набо рах 14 - 18 требуется деление схемы на зоны и построение проверяющих наборов для каждой зоны отдельно,Наборы 14 а и 15 а подаются на четные строки матрицы в то же время, когда на нечетные строки подаются наборы 14 Ь и 15 Ь.При подаче наборов 16 - 18 все столбцы матрицы делятся на три зоны: А, В, С. Если- номер столбца (=1, 2,), то в зону А попадут столбцы, для которых =2 (пюд 3), в В - =1 (гпод 3) и в С - =0 (тод 3), Наборы 16 а, Ь, с подаются одновременно в зоны А, В, С соответственно, затем подаются наборы 17 а, Ь, с и далее - 18 а, Ь, с. При этом наборы 16 проверяют столбцы зоны В, 17 - А, а 18 - С.Рассмотрим, например, наборы 16. Набор 16 а задает в своем столбце г=1, так как х=з=1; набор 16 с обрывает прохождение сигнала г (так как г=з=у=О) и открывает прохождение сигнала по х (от входов г), так как о=1=1, Если в столбце зоныВ (набор 16 Ь) в какой-либо ячейке 1 ФО, т. е. имеется единичная неисправность 1=1, то получим в этой ячейке г=1 и в столбце зоны Сх=1 вместо х=О,580553 фиг,Поскольку набор 16 проверяет только каж. дый третий столбец, для проверки всей схемы требуются еще наборы 17 и 18,Можно на основе приведенного проверяющего теста построить (с добавлением нескольких наборов) диагностирующий тест, позволяющий определить место одиночной константной неисправности в матрице, Это означает, что предлагаемое устройство обладает также и диагностирующим тестом, длина которого не зависит от размеров устройства.Кроме эффективной контролируемости, предлагаемое устройство обладает также рядом других преимуществ по сравнению с устройством по авт. св. Мо 424141. Эти преимущества появляются в результате расширения логических возможностей за счет введения дополнительных элементов.Так, например, в однородной матрице предлагаемого устройства облегчается синтез различных автоматов, так как можно дополнительно использовать для настройки схем сигналы г, з, 1, Так, подавая в некоторую строку матрицы 1=0, можно изолировать схемы по горизонтали, подавая в некоторый столбец а=1, можно осуществить поворот переменной х из столбца в строку и т, д,Формула изобретения Устройство для сортировки информации поавт, св. Мо 424141, отличающееся тем, 5 что, с целью повышения эффективности контроля, в каждую ячейку устройства введены три дополнительных элемента И, причем вь,.ход первого элемента И соединен с одним из входов первого дополнительного элемента И, 10 другой вход которого подключен к первой дополнительной шине, а выход соединен с одним из входов второго элемента ИЛИ, выход первого элемента ИЛИ соединен с одним из входов второго и третьего дополнительных 15 элементов И, другие входы которых подключены ко второй и третьей дополнительным шинам, а выходы - к второму логическому выходу ячейки и к входу второго элемента ИЛИ соответственно.20 Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР Мо 376807,кл, 6 11 с 15/00, 24,04.71. 25 2. Кацапу 1 Ч. Н. Се 11 ц 1 аг 1 орсп-тегпогу аггауз, 1 ЕЕЕ Тгапз., 1969, сМо 8, р. 719 -727,ПодписСССР Тираж 818тета Совета Министроений и открытийРаушская наб., д, 4/5 Изд.889 ударственного кок по делам изобр 3035, Москва, К/уи)Пр оти бог оночныи