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

 

Оn КCАИМ;.

Соаз Советских

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

Республик (11) 545®® (61) Дополнительное к авт. свид-ву (22) Заявлено 20.06.75 (21) 2146958/24 с присоединением заявки № (23) Приоритет (43) Опубликовано 05.02.77.Бюллетень ¹ 5 (45) Дата опубликования описания 01.04.77 (51) И. Кл.

G 06 F 7/06

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

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

В. С. Погорелов и А.!». Романкевич

Киевский opjleHa Ленина HGJIHT HHH HHÉ:. нстт;. -т им,50-ле1ия

Великой Октябрьской социалистической оеволюции (71) Заявитель (54) УСТРОЙСТВО ДЛЯ К.ЛАССИФИКАЦИИ ДВОИЧНЫХ ЧИСЕЛ

Изобретение относится к области автоматики и вычислительной техники и может быть использовано при технической реализации специализированных устройств обработки данных. 5

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

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

Недостатком устройств (1, 21 является малая эффективность классификации слов массива в порядке возрастания (или убывания) их кода, поскольку требуется производить 25 большое число Операций сравнения слов, равное N(t 1)/2,где N - число слов в массиве.

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

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

545982 достигнуто за счет увеличения сложности оборудования.

Целью изобретения является упрощение устройства.

Эта цель достигается тем, что в предло- женном устройстве выход последнего разряда сдвигающего регистра соединен с информационными входами первого и второго буферных запоминающих блоков, управляющие входы которых подключены к выходам пер- )ф вого и второго элементов И соответственно, один из входов которых соединен с шиной тактовых сигналов, а другие входы— с управляющей шиной. Третьи входы первого и второго элементов И подключены к пря-)5 мому и инверсному выходам первого триггера соответственно, вход установки в нулевое состояние которого через элемент задержки соединен со входом третьего элемента И и через формирователь импульсов 20 с выходом двоичного счетчика. Другой вход третьего элемента И подключен к прямому выходу второго триггера, вход установки в нулевое состояние которого соединен со входом установки в единичное состояние первого триггера и с выходом третьего элемента И. Вход установки в единичное состояние второго триггера через четвертый элемент И подключен к выходу первого разряда сдвигающего регистра и к выходу уп— равляемого элемента задержки, другой выход которого и выход первого разряда сдвигающего регистра через пятый элемент И соединены со второй управляющей шиной.

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

Устройство содержит шину информационных сигналов 1, сдвигающий регистр 2, буферные запоминающие блоки 3 и 4, шину тактовых сигналов 5, управляемый элемент задержки 6, двоичный счетчик 7, элементы

И 8, 9, управляющую шину 10, триггер 11, элемент задержки 12, элемент И 13, формирователь импульсов 14,триггер 1 5,элементы И 16, 17 и управляющие шины 18 — 20.

Устройство работает следующим образом. 50

Перед началом работы схема управления (на чертеже не показана) подготавливает предлагаемое устройство к работе: устанавливает в "0" сдвигающий регистр 2, управляемый элемент задержки 6, двоичный счет- бб чик 7, триггеры 11 и 15, подает запрещающий потенциал на управляющую шину 10 и закрывает элементы И 8 и 9, а также настраивает управляемый элемент задержки

УЭЗ 6 на анализ соответствующего а-го б9 разряда элемента массива (слова) подачей соответствующего сигнала на управляющую шину 19.

Работа устройства начинается при поступлении по шине 1 на вход сдвигающего регистра 2 элементов массива информации (слов). Предполагается, что все слова имеют одинаковую длину — и разрядов и поступают старшими разрядами вперед. Каждый разряд поступающей информации сопровождается (тактируется) синхроимпульсом, поданным на шину тактовых сигналов 5. Спустя m тактов от начала цикла (цикл работы устройства равен П Tàêòàì синхроимпульсов

Ф где — число разрядов информационного слова), т.е. когда в первый разряд S сдви» гающего регистра 2 поступит tn -й разряд первого информационного слова, элемент 6 вырабатывает короткий импульс, который поступает на вход элемента И 16 . Если в анализируемом разряде данного информационного слова содержится "1", то в m -ом такте эта "1" находится в первом разряде

5» сдвигающего регистра 2, и тогда короткий импульс, выработанный в 7п-ом такте элементом 6, поступает через элемент И

16 на единичный вход триггера 15 и устанавливают его в единичное состояние. Если в m-ом разряде информационного слова содержится "0", триггер 15 остается в нулевом состоянии. Спустя п тактов от начала цикла, когда в сдвигающий регистр 2 запишется последний разряд слова, двоичный счетчик переполняется, и включенный на его выходе формирователь импульсов 14 вырабатывает короткий импульс, поступающий по управляющей шине 20 в схему управления, которая снимает запрещающий потенциал с управляющей шины 10. Одновременно короткий импульс с выхода формирователя 14 поступает на нулевой вход триггера 11 и через элемент задержки 12 на вход элеменга И 13. Если триггер 15 находится в единичнсм состоянии, то импульс проходит на вход элемента И 13, устанавливает триггер

11 в единичное состояние и одновременно сбрасывает триггер в нулевое состояние, подготавливая его тем самым к следующему циклу работы. Триггер 11 потенциалом своего единичного выхода открывает элемент

И 8, а потенциалом нулевого плеча закрывает элемент И 9 по соответствующим входам. На этом все элементы устройства заканчивают цикл работы.

В следующем цикле работы записанное в предыдущем цикле в сдвигающий регистр

2 слово "выталкивается" и поступает на информационные входы буферных запоминающих блоков 3 и 4, однако оно записывает545982 ся в блок 3, так как на его управляющий вход в течение всего второго цикла работы поступают синхроимпульсы с выхода элемен та И 8. Одновременно с этим в сдвигающий регистр 2 записывается второе слово, и цикл работы устройства происходит аналогично.

Если в анализируемом разряде второго слова содержится "0", то в гп -ом такте второго цикла триггер 1 5 остается в нуле- р вом состоянии. В -ом такте второго цикла работы короткий импульс с выхода формирователя импульсов 14 устанавливает в нулевое состояние триггер 1 1, который остается в этом состоянии в течение д следующего цикла. Триггер 11 закрывает элемент И 8 и открывает элемент И 9, Вследствие этого в следующем цикле работы второе слово, "выталкиваемое" иэ сдвигающего регистра 2, записывается в буфер- 20 ный запоминающий блок 4, на управляюший вход которого в течение всего цикла поступают синхронизирующие импульсы с выхода элемента И 9. Устройство работает таким образом до тех пор, пока не будет просмотрен весьма массив информации. В процессе просмотра массива информации в буферном запоминающем блоке 3 накапливаются слова, содержашие "1" в анализируемом разряде, а в блоке 4 — слова, содержащие "0" в том 30 же разряде. Если емкость блоков 3 и 4 недостаточна, то по мере их заполнения информация с них может быть переписана по соответствуюшим адресам в ЗУ большего объема, в котором таким образом полу— чают два подмассива информации, слова одного из которых содержат "1", а другого—

"0" в необходимом р азряде.

При разделении массива информации по значению кода в m -ом разряде, элемент 40

И 17 производит анализ (tn-1)-го разряда каждого слова. Если в этом такте в первом разряде S< сдвигающего регистра 2 будет "1", то на управляющую шину 18 поступает импульс. Таким образом, в про- 45 цессе разделения массива информации по

m-му разряду схема управления получает сведения о том, сколько слов массива содержат "1" в следующем (гп-1)-оМ разряде (нумерация разрядов слов начинается со 50 старших разрядов, так как слова поступают последовательным кодом старшими разрядами вперед). Эта информация может понадобиться при поразрядном упорядочении массива информации в порядке возрастания или ® убывания кода его слов для вычисления начальных адресов ЗУ, по которым записываются подмассивы информации, получаемые на следующем этапе разделения (т.е. при разделении по (m -1)-му разряду). 69

Устройство содержит малое количество оборудования и может быть легко состыковано с ЗУ, информация в которых эаписы вается и считывается последовательным кодом. Устройство может найти применение в системах обработки данных для классификации элементов массивов по определенному признаку, для ассоциативного поиска записей, а также для упорядочения массивов информации в порядке возрастания или убывания кода признака его элементов. В случае упорядочения по коду самих двоичных т)— разрядных слов требуется и прогонов мас сива через устройство. Таким образом, если массив содержит hJ д -разрядных двоичных слов, то полное упорядочение его с помощью предложенного устройства может быть произведено примерно за Ь и тактов.

2.

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

Устройство для классификации двоичных чисел, содержащее сдвигающий регистр, двоичный счетчик, управляемый элемент задержки, управляюшие входы которых соединены с шиной тактовых сигналов, триггеры, элементы И, формирователь импульсов, элемент задержки и два буферных запоминающих блока,отличаюшееся тем,что,с целью упрощения устройства, в нем выход последнего разряда сдвигающего регистра соединен с информационными входами первого и второго буферных запоминающих блоков, управ ляющие входы которых подключены К выходам первого и второго элементов И соот ветственно, один из входов которых соедиHEH с шиной тактовых сигналов, а другие входы — с управляющей шиной; третьи входы первого и второго элементов И подключены к прямому и инверсному выходам первого триггера соответственно, вход установки в нулевое состояние которого через эле мент задержки соединен со входом третьего элемента И и через формирователь импульсов с выходом двоичного счетчика; другой вход третьего элемента И подключен к прямому выходу второго триггера, вход установки в нулевое состояние которого соединен со входом установки в единичное состояние первого триггера и с выходом третьего элемента И, вход установки в единичное состояние второго триггера через четвертый элемент И подключен к выходу первого разряда сдвигающего регистра и к выходу управляемого элемента задержки, другой выход которого и выход первого раз ряда сдвигающего регистра через пятый элемент И соединены со второй управляю545982

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

Редактор Л. Утехина Техред O. Луговая Корректор В. Салка

Заказ 236/2 Тираж 899 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 щей шиной; вход управления управляемого элемента задержки подключен к третьей управляющей шине.

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

1. Авторское свидетельство СССР

¹ 256363,кл. Cj 06 7 7/06 от 12,08.

68 r.

2, Авторское свидетельство СССР № 466508, кл. G 06 T 7/04 от 06.02.

5 73г, 3. Патент Франции № 2052292, кл.

G 06 Р 7/04 от 14.05.1971 г.