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

(щ 590728 ОПИСАНИЕ ИЗОБРЕТЕН ИЯ Союз Советских Сорапистическик Республик(45) Дата опубликования описания 20.01.78 Государственный комитет Совета Министров СССРдо делам изобретенийи открытий 53) УДК 681.327(72) Авторы изобретения етешкин и К. С, Барашев Заявитель 4) УСТРОЙСТВО ДЛЯ СОРТИРО НФОРМА Изобретение относится к области вычислительной техники и предназначено для логической обработки информации.Известны устройства для сортировки информации. Одно из них содержит элементы памяти, схемы сравнения и мажоритарный элемент, причем сортировка осуществляется последовательным анализом одноименных разрядов сортируемых чисел. Это устройство обладает низким быстродействием 1. 1Наиболее близким к изобретению является устройство для сортировки информации, содержащее ячейки, каждая из которых содержит триггер, единичный и нулевой входы которого соединены соответственно с выходами 1 первого и второго входных элементов И; первый вход второго входного элемента И соединен с выходом элемента НЕ, вторые входы входных элементов И соединены с первым управляющим входом устройства, а выход 2 триггера подключен к первому входу первого выходного элемента И, с вторым входом которого соединен второй управляющий вход устройства 2.Недостатком такого устройства также является низкое быстродействие,Целью изобретения является повышение быстродействия. Это достигается тем, что каждая ячейка дополнительно содержит (и - 1) триггеров (и - количество разрядов З в сортируемых числах), группу из 2(и - 1) входных элементов И, группу из (и - 1) выходных элементов И, дешифратор, имеющий и входов и т выходов, (т - 2) элементов 1-1 Г, группу из т элементов И и т элементов ИЛИ. В каждой ячейке выход Уг-го триггера (1=1 - ;и) соединен с Уг-ым входом дешифратора, первый вход у-го элемента И группы (у=1 - ;т) соединен с у-ым выходом деши фратора, второй выход /-го элемента И группы соединен с третьим управляющим входом устройства, остальные (у - 1) входов у-го элемента И группы соединены соответственно с выходами первого, второго, (у - 1) -го элемен тов НЕ, выход у-го элемента И группы соединен с первым выходом у-го элемента ИЛИ, со входом (т у+1) т-го элемента ИЛИ, причем первый вход входного (2 Уг - 1)-го элемента И группы соединен со входом А-го О элемента НЕ, выходом Й-го выходного элемента И группы, с Уг-ым входом первой группы входов устройства и с уг-ым выходом первой группы выходов устройства; входы остальных элементов НЕ каждой ячейки сое,динены соответственно с (и+ 1) - : (т - 1) входами первой группы входов устройства и выходами (и+1) - : (иг - 1) первой группы выходов устройства; второй вход г-го элемента ИЛИ (У= 1 - :т - 1) каждой ячейки соединен с выходом г-го элемента ИЛИ предыду5 10 15 20 25 30 35 40 45 50 55 60 65 щей ячейки, второй вход 1-го элемента ИЛИсоединен с 1-тым входом второй группы входов устройства, выход 1-го элемента ИЛИсоединен с 1-ым выходом второй группы выходов устройства, выход п-го элемента ИЛИкаждой ячейки соединен с соответствующимвыходом группы выходов результата устройства.На фиг. 1 представлена структурная схема предложенного устройства; на фиг, 2схема одной его ячейки,Устройство содержит ячейку 1 с первойи второй группами входов, первой и второйгруппами выходов и группой выходов результата. Каждая ячейка содержит и-триггеров2, группу из 2(и - 1) входных элементов И:3,группу из (и - 1) выходных элементов И 4,дешифратор б с и входами и т выходами,(т - 2) элементов НЕ б, группу из т элементов И 7, т элементов ИЛИ 8, первый, второйи третий управляющие входы 9, 10 и 11 и выход результата 12.Устройство может работать в режимах:Сортировка, Запись, Чтение. Для работы устройства в указанных режимах выходы второй группы соединены с одноименными входами первой группы.В режиме Сортировка необходимо натретий управляющий вход 11 всех ячеек подать единичный потенциал, а на первый ивторой управляющие входы 9 и 10 - нулевой потенциал. Если среди анализируемыхпризнаков, хранящихся в ячейках 1, найдется хотя бы один признак с максимальнымзначением, равным 2", то на выходе первогоэлемента И 7 тех ячеек, где это имеет место,образуется единичный сигнал, который черезт-ый элемент ИЛИ 8 поступает на выходрезультата 12 и через первый элемент ИЛИ8 на первый выход второй труппы выходов.Так как первый выход второй группы выходов соединен с первым входом первой группы входов, то единичный сигнал поступает навход первого элемента НЕ б всех ячеек устройства. Выходной сигнал первого элементаНЕ б поступает на вход второго и всех последующих элементов И 7 в качестве запрещающего сигнала. Единичный сигнал возникает только в тех ячейках, где анализируемые признаки имеют максимальные значения, равные 2".Если среди анализируемых признаков нечайдется ни одного признака со значениемравным 2", но найдется хотя бы один признак со значением равным 2" - 1, то на выходе второго элемента И 7 тех ячеек, где этоимеет место, образуется единичный сигнал,который через т-ый элемент ИЛИ 8 поступает на выход результата 12 и через второйэлемент ИЛИ 8 на второй выход второйгруппы выходов, Так как второй выход второй группы выходов соединен с вторым входом первой группы входов, то единичный,игнал поступает на вход второго элементаНЕ б всех ячеек устройства. Выходной сигнал второго элемента НЕ б поступает на вход третьего и всех последующих элементов И 7 в качестве запрещающего сигнала. Единичный сигнал на выходе результата 12 возникает только в тех ячейках, где анализируемые признаки имеют максимальные значения, равные 2" - 1. Для выделения признака с очередным максимальным значением необходимо исключить выделенные ранее признаки. Это можно осуществить путем подачи нулевого потенциала на третий управляющий вход И тех ячеек, в которых хранятся ранее выделенные признаки.Для сортировки путем выделения минимальных значений признаков необходимо на входы дешифратора б подать инверсные выходы соответствующих триггеров 2.В режиме Запись на второй управляющий вход 10 и третий управляющий вход 11 подаетая ,нулевой потенциал. При записи и-разрядное слово подается на соответствующие входы первой группы входов. Адрес записи указывается подачей единичного потенциала на первый управляющий вход 9 той ячейки, в которую необходимо записать слово. При этом через группу входных элементов И 8 произойдет парафазная запись слова в запоминающие элементы 2 ячейки. Если требуется записать и-разрядное слово одновременно в несколько ячеек, то необходимо на первые управляющие входы 9 соответствующих ячеек подать единичный потенциал, Для стирания информации в какой-либо ячейке (или в множестве ячеек) необходимо произвести запись и-разрядного слова: А = 00 0.В режиме Чтение на первый управляющий вход 9 и третий управляющий. вход 11 всех ячеек необходимо подать нулевой потенциал, Считывание выделенного признака осуществляется путем подачи единичного потенциала на второй управляющий вход 10 соответствующей ячейки. При этом на второй управляющий вход 10 остальных ячеек подается нулевой потенциал. В этом случае на соответствующих выходах первой группы выходов будет считано и-разрядное слово. Если в массиве имеется несколько признаков с одинаковыми значениями, то их считывание производится по очереди в произвольно установленном порядке,Формула изобретенияУстройство для сортировки информации, содержащее ячейки, каждая из которых содержит триггер, единичный и нулевой входы которого соединены соответственно с выходами первого и второго входных элементов И; первый вход второго входного элемента И соединен с выходом элемента НЕ, вторые входы входных элементов И соединены с первым управляющим входом устройства, а выход триггера подключен к первому входу первого выходного элемента И, с вторым8 асрая груп- ПР 1 пи гДгллс бмбод ла УмйЬР входом которого соединен второй управляющий вход устройства, отлич ающееся тем, что, с целью повышения быстродействия устройства, каждая ячейка дополнительно содержит (и - 1) триггеров (и - количество разрядов в сортируемых числах), группу из 2(п - 1) входных элементов И, группу из (и - 1) выходных элементов И, дешифратор, имеющий п входов и т выходов, (т - 2) элементов НЕ, группу из т элементов И и т элементов ИЛИ, причем в каждой ячейке выход Й-го триггера (1=1-;п) соединен с Й-ым входом дешифратора, первый вход 1-го элемента И группы (=1 - . т) соединен с у-ым выходом дешифратора, второй вход 1-го элемента И группы соединен с третьим управляющим входом устройства, остальные ( - 1) входов -го элемента И группы соединены соответственно с выходами первого, второго, Ц - 1) элементов НЕ, выход 1-го элемента И группы соединен с первым выходом -го элемента ИЛИ, со входом (т - )+1) т-го элемента ИЛИ, причем,первый вход входного (2 й - 1) элемента И группы соединен со входом й-го элемента НЕ, выходом й-го выходного элемента И группы, с Й-тым входом первой группы входов устройства, с етым выходом первой группы выходов устройства, входы остальных элементов НЕ каждой ячей ки соединены соответственно с (и+1) - ; (т - 1)входами первой группы входов устройства и выходами (и+1) - : (т - 1) первой группы выходов устройства, второй вход 1-го элемента ИЛИ (1=1 - ;т - 1) каждой ячейки соеди нен с выходом 1-го элемента ИЛИ предыдущей ячейки, второй вход 1-го элемента ИЛИ соединен с 1-тым входом второй группы входов устройства, выход 1-го элемента ИЛИ соединен с 1-тым выходом второй группы вы ходов устройства, выход т-го элемента ИЛИкаждой ячейки соединен с соответствующим выходом группы выходов результата устройства,20 Источники информации, принятые во внимание при экспертизе:1. Авторское свидетельство СССР463968, кл. й 06 Г/08, 1973.2. Авторское свидетельство СССР 25424141, кл. б 06 Р 7/00, 1972.