Устройство для классификации двоичных чисел

ОЛ ИСАИ ИСоаз Советскии Социапистицеских Респубпин(23) Приоритет осударственныи номитеСовета Министров СССпо делам изобретенийи атнрытий 2,77,Бюллетень3) Опубликован К 681. 32088,8) 53) ата опубликования описания 01.04.77(72) Авторы изобретения редов и А, М, Романкевич Ленина попигехнический институт им,50-дег 1тябрьской социалистической революции вский орде Великой(54) УСТРОЙСТВО ДЛЯ КЛАССИФИКАЦИИ ДВОИЧНЫХ ЧИСЕ 2 И обретение относится к и и вычиспитедьной г обпасти автохники и может ческой реапитройсгв обрамати быть опьзовано при гехни специализированныхданных. заци ботк Известно устройство дд двоичных чисел 11, выпоп ве суммирующего и вычита которое может определять наименьшее из поступающи чисел. Поступающие на вх па допжны быть представп импульсным кодом, что яв ком данного устройства. кпа икации а осно ненное юшего счетчи наибольшее и х на его входод устройства ены только чи тся недостат 15 Извесоич ных устройст пения на тупаюшихНедос малая эфф сиваих ко тно устройство дпя классификации чисел 21, выполненное на оснорегистров и схемы сравнения. Это во также предназначено дпя опредеибопьшего ипи наименьшего из посна его вход чисел.татком устройств 1, 21 являетсяективность классификации слов маспорядке возрастания (ипи убывания) , поскодьку требуется производить 2 большое число операций сравнения слов, равное М(Й)2,где К - число слов в массиве.Наибодее близким техническим решением к даннол 1 у изобретению является устройство ддя кпассификацип двоичных чисед, содержащее сдвиговый регистр, двоичный счетчик, управляемый эдеменг задержки, управляю - щие входы которых соединены с шиной тактовых сигнапов, триггеры, эпелленты И,формироватепь импульсов, эпеменг задержки и буферные запоминающие блоки 81. Кроме того, в системе имеются схемы сортировки, число которых равно чиспу одновременно участвующих в классификации сортировке) двоичных слов, Классификация двоичных спов в системе производится по управ - пяющему коду, имеющемуся в каждом слове. Набор двоичных слов циркулирует через систему до их полной рассортировки в порядке возрастания ипи убывания их управпяюшего кода, Недостатком известного устройства является то, что классификация информации производится быстрее, чем в предыдущих устройствах, поскольку одновременно сравнивается не два, а пять спов, однако этодостигнуто за счет увеличения сложностиоборудования.Целью изобретения является упрощениеустройства,Эта цель достигается тем, что в предло-женном устройстве выход последнего разряда сдвигающего регистра соединен с информационными входами первого и второго буферных запоминающих блоков, управляющиевходы которых подключены к выходам первого и второго элементов И соответственно, один из входов которых соединен с шиной тактовых сигналов, а другие входы -с управляющей шиной. Третьи входы первого и второго элементов И подключены к пря мому и инверсному выходам первого триггера соответственно, вход установки в нулевое состояние которого через элементзадержки соединен со входом третьего элемента И и через формирователь импульсов 20с выходом двоичного счетчика. Другой входтретьего элемента И подключен к прямомувыходу второго триггера, вход установки внулевое состояние которого соединен совходом установки в единичное состояние 2 Ьпервого триггера и с выходом третьего элемента И. Вход установки в единичное состояние второго триггера через четвертыйэлемент И подключен к выходу первого разряда сдвигающего регистра и к выходу уп - Зйравляемого элемента задержки, другой выход которого и выход первого разряда сдвигающего регистра через пятый элемент Исоединены со второй управляющей шиной.Вход управления управляемого элемента задержки подключен к третьей управляющейшине,На чертеже приведена функциональнаясхема устройства,Устройство содержит шину информационных сигналов 1, сдвигающий регистр 2, буферные запоминающие блоки 3 и 4, шинутактовых сигналов 5, управляемый элементзадержки 6, двоичный счетчик 7, элементыИ 8, 9, управляющую шину 10, триггер 11, фэлемент задержки 12, элемент И 13, формирователь импульсов 14,триггер 15,элементы И 16, 17 и управляющие шины 18 - 20.Устройство работает следующим образом. 30 Перед началом работы схема управления (на чертеже не показана) подготавливает предлагаемое устройство к работе: устанавливает в "Оф сдвигающий регистр 2, управляемый элемент задержки 6, двоичный счет- Я чик 7, триггеры 11 и 15, подает запрещающий потенциал на управляющую шину 10 и закрывает элементы И 8 и 9, а также настраивает управляемый элемент задержки УЭЗ 6 на анализ соответствующего ти-го бО разряда элемента массива (слова) подачей соответствующего сигнала на управляющую шину 19.Работа устройства начинается при поступлении по шине 1 на вход сдвигающего регистра 2 элементов массива информации (слов). Предполагается, что все слова имеют одинаковую длину - и разрядов и поступают старшими разрядами вперед. Каждый разряд поступающей информации сопровождается (тактируется) синхроимпульсом, поданным на шину тактовых сигналов 5. Спустя тп тактов от начала цикла (цикл работы устройства равен П тактам синхроимпульсов, где и - число разрядов информационного слова), т.е. когда в первый разряд 5 сдвигающего регистра 2 поступит п -й разряд первого информационного слова, элемент 6 вырабатывает короткий импульс, который поступает на вход элемента И 16 . Если в анализируемом разряде данного информационного слова содержится "1", то в тп -ом такте эта ф 1" находится в первом разряде 5 сдвигающего регистра 2, и тогда короткий импульс, выработанный в 7 п -ом такте элементом 6, поступает через элемент И 16 на единичный вход триггера 15 и устанавливают его в единичное состояние. Если в тп -ом разряде информационного слова содержится "0", триггер 15 остается в нулевом состоянии, Спустя п тактов от начала цикла, когда в сдвигающий регистр 2 запишется последний разряд слова, двоичный счетчик переполняется, и включенный на его выходе формирователь импульсов 14 вырабатывает короткий импульс, поступающий по управляющей шине 20 в схему управления, которая снимает запрещающий потенциал с управляющей шины 10. Одновременно короткий импульс с выхода формирователя 14 поступает на нулевой вход триггера 11 и через элемент задержки 12 на вход элемента И 13. Если триггер 15 находится в единичнсм состоянии, то импульс проходит на вход элемента И 13, устанавливает триггер 11 в единичное состояние и одновременно сбрасывает триггер в нулевое состояние, подготавливая его тем самым к следующему циклу работы. Триггер 11 потенциалом своего единичного выхода открывает элемент И 8, а потенциалом нулевого плеча закрывает элемент И 9 по соответствующим вхо- дам. На этом все элементы устройства заканчивают цикл работы.В следующем цикле работы записанное в предыдущем цикле в сдвигающий регистр 2 слово "выталкивается" и поступает на информационные входы буферных запоминающих блоков3 и 4, однако оно записывает 545982ся в блок 3, так как на его управляющийвход в течение всего второго цикла работыпоступают синхроимпульсы с выхода элемента И 8. Одновременно с этим в сдвигающий регистр 2 записывается второе слово,и цикл работы устройства происходит аналогично.Если в анализируемом разряде второгослова содержится фО", то в гп -ом тактевторого цикла триггер 1 5 остается в нуле- рвом состоянии. В й -ом такте второгоцикла работы короткий импульс с выходаформирователя импульсов 14 устанавливает в нулевое состояние триггер 1 1, который остается в этом состоянии в течение 1 бследующего цикла, Триггер 11 закрываетэлемент И 8 и открывает элемент И 9,Вследствие этого в следующем цикле работы второе слово, фвыталкиваемоеф иэ сдвигающего регистра 2, записывается в буферный запоминающий блок 4, на управпяюшийвход которого в течение всего цикла поступают синхронизируюшие импульсы с выхода элемента И 9. Устройство работает таким образом до тех пор, пока не будет просмотрен весьмамассив информации. В процессе просмотрамассива информации в буферном запоминающем блоке 3 накапливаются слова, содержашие "1" в анализируемом разряде, а вблоке 4 - слова, содержащие "О" в том З 0же разряде. Если емкость блоков 3 и 4недостаточна, то по мере их заполненияинформация с них может быть переписанапо соответствуюшим адресам в ЗУ большего объема, в котором таким образом полу -чают два подмассива информации, слова одного из которых содержат "1", а другого -"О" в необходимом разряде,При разделении массива информации позначению кода в 1 т 1 -ом разряде, элемент 40И 17 производит анализ (ти)-го разряда каждого слова. Если в этом такте в первом разряде Ь сдвигаюшего регистра 2будет "1 ф, то на управляющую шину 18поступает импульс, Таким образом, в про бцессе разделения массива информации пот-му разряду схема управления получаетсведения о том, сколько слов массива содержат "1 ф в следующем (тп)-ом разряде (нумерация разрядов слов начинается со бОстарших разрядов, так как слова поступаютпоследовательным кодом старшими разрядами вперед), Эта информация может понадобиться при поразрядном упорядочении массива информации в порядке возрастания или ббубывания кода его слов дпя вычисления начальных адресов ЗУ, по которым записываются подмассивы информации, получаемыена следующем этапе разделения (т.е. приразделении по (пт -1)-му разряду). 69 Устройство содержит малое количество оборудования и может быть легко состыковано с ЗУ, информация в которых эаписы вается и считывается последовательным кодом. Устройство может найти применение в системах обработки данных для классификации элементов массивов по определенному признаку, для ассоциативного поиска записей, а также для упорядочения массивов информации в порядке возрастания или убывания кода признака его элементов. В случае упорядочения по коду самих двоичных т) - разрядных слов требуется и прогонов мас сива через устройство. Таким образом, если массив содержит Й И -разрядных двоичных слов, то полное упорядочение его с помощью предложенного устройства может быть произведено примерно за Ь и тактов.йФормула изобретенияУстройство для классификации двоичных чисел, содержащее сдвигающий регистр, двоичный счетчик, управляемый элемент задержки, управляюшие входы которых соединены с шиной тактовых сигналов, триггеры, элементы И, формирователь импульсов, элемент задержки и два буферных запоминающих блока,отпичаюшееся тем,что,с целью упрощения устройства, в нем выход последнего разряда сдвигаюшего регистра соединен с информационными входами первого и второго буферных запоминающих блоков, управ ляюшие входы которых подключены К выходам первого и второго элементов И соот ветственно, один из входов которых соединен с шиной тактовых сигналов, а другие входы - с управляющей шиной; третьи входы первого и второго элементов И подключены к прямому и инверсному выходам первого триггера соответственно, вход установки в нулевое состояние которого через эле мент задержки соединен со входом третьего элемента И и через формирователь импульсов с выходом двоичного счетчика;другой вход третьего элемента И подключен к прямому выходу второго триггера, вход установки в нулевое состояние которого соединен со входом установки в единичное состояние первого триггера и с выходом третьего элемента И, вход установки в единичное состояние второго триггера через четвертый элемент И подключен к выходу первого разряда сдвигаюшего регистра и к выходу управляемого элемента задержки, другой выход которого и выход первого раз ряда сдвигаюшего регистра через пятый элемент И соединены со второй управляю545982 Составитель В. БелкинРедактор Л. Утехина Техред О. Луговая Корректор В. Салка Заказ 236/2 Тираж 899 ПодписноеЦНИИПИ Государственного комитета Совета Министров СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д, 4/5 Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 щей шиной; вход управления управляемогоэлемента задержки подключен к третьейуправляющей шине,Источники информации, принятые во внимание при экспертизе:1, Авторское свидетельство СССР256363,кл, 5 06 7 7/06 от 12,08,68 г.2, Авторское свидетельство СССР466508, кл. 6 06 Р 7/04 от 06,02,б 73 г,3, Патент Франции2052292, кл.Ь 06 Г 7/04 от 14,05.1971 г.