Устройство для классификации двоичных чисел Советский патент 1977 года по МПК G06F7/06 

Изобретение относится к области автоматики и вычислительной техники и может быть использовано при технической реализации специализированных устройств обработки данных. Известно устройство для классификации двоичных чисел fljj выполненное на основе суммирующего и вычитающего счетчикое которое может определять наибольщее или наименьщее из поступающих на его вход чисел. Поступающие на вход устройства чис ла должны быть представлены только число импульсным -кодом, что является недостатком данного устройства. Известно устройство для классификации двоичных чисел 2, выполненное на основе двух регистров и схемы сравнения. Это устройство также предназначено для опреде ления наибольшего или наименьщего из поступающих на его вход чисел. Недостатком устройств l, 2 является малая эффективность классификации слов ма сива в порядке возрастания (или убывания) их кода, поскольку требуется производить большое число операций сравнения слов, равное N(ч 1)/|3 ,где N число слов в массиве. Наибопее близким техническим решением к данному изобретению является устройство для классификации двоичных чисел, содержащее сдвиговый регистр, двоичный счетчик, управляемый элемент задержки, управляющие входы которых соединены с шиной тактовых сигналов, триггеры, элементы И, формирователь импульсов, элемент задержки и буферные запоминающие блоки З. Кроме того, в системе имеются схемы сортировки, число которых равно числу одновременно участвующих в классификации (.сортировке) двоичных слов. Классификация двоичных слов в системе производится по управляющему коду, имеющемуся в каждом слове. Набор двоичных слов циркулирует через систему до их полной рассортировки в порядке возрастания или убывания их управляющего кода. Недостатком известного устройства является то, что классификация информации производится быстрее, чем в предыдущих устройствах, поскольку одновременно сравнивается не два, а пять слов, однако это достигнуто за счет увеличения сложности оборудования. Целью изобретения является упрощение устройства. Эта цель достигается тем, что в предло женном устройстве выход последнего разряда сдвигающего регистра соединен с информационными входами первого д второго буферных запоминающих блоков, управляющие входы которых подключены к выходам первого и второго элементов И соответственно, один из входов которых соединен с шиной тактовых сигналов, а другие входы с управляющей шиной. Третьи входы первого и второго элементов И подключены к пр мому и инверсному выходам первого триггера соответственно, вход установки в нулевое состояние которого через элемент задержки соединен со входом третьего элемента И и через формирователь импульсов с выходом двоичного счетчика. Другой вход третьего элемента И подключен к прямому выходу второго триггера, вход установки в нулевое состояние которого соединен со входом установки в единичное состояние первого триггера и с выходом третьего эле мента И. Вход установки в единичное состояние второго триггера через четвертый элемент И подключен к выходу первого раз ряда сдвигающего регистра и к выходу управляемого элемента задержки, другой выход которого и выход первого разряда сдви гающего регистра через пятый элемент И соединены со второй управляющей шиной. Вход управления управляемого элемента задержки подключен к третьей управляющей шине. На чертеже приведена функциональная схема устройства. Устройство содержит шину информационных сигналов 1, сдвигающий регистр 2, буферные запоминающие блоки 3 и 4, шину тактовых сигналов 5, управляемый элемент задержки 6, двоичный счетчик 7, элементы И 8, 9, управляющую шину 1О, триггер 11 элемент задержки 12, элемент И 13, формирователь импульсов 14,триггер 15,элемен ты И 16, 17 и управляющие шины 18 - 20, Устройство работает следующим образом. Перед началом работы схема управления (на чертеже не показана) подготавливает предлагаемое устройство к работе: устанавливает в О сдвигающий регистр 2, управляемый элемент задержки б, двоичный счет чик 7, триггеры 11 и 15, подает запрещающий потенциал на управляющую шину 10 и закрывает элементы И 8 и 9, а также нас раивает управляемый элемент задержки УЭЗ 6 на анализ соответствующего пг-го разряда элемента массива (слова) подачей соответствующего сигнала на управляющую шину 19. Работа устройства начинается при поступлении по шине 1 на вход сдвигающего регистра 2 элементов массива информации (слов).Предполагается,что все слова имеют одинаковую длину - п разрядов и поступают старшими разрядами вперед. Каждый разряд поступающей информации сопровождается (тактируется) синхроимпульсом, по данным на шину тактовых сигналов 5. Спустя тп тактов от начала цикла (цикл работы устройства равен П тактам синхроимпульсов, где П - число разрядов информационного слова), т.е. когда в первый разряд S сдвигающего регистра 2 поступит т -и разряд первого информационного слова, элемент 6 вырабатывает короткий импульс, который поступает на вход элемента И 16. Если в анализируемом разряде данного информационного слова содержится 1, то в m -ом такте эта 1 находится в первом разряде 5 сдвигающего регистра 2, и тогда короткий импульс, выработанный в тп -ом такте элементом 6, поступает через элемент И 16 на единичный вход триггера 15 и устанавливают его в единичное состояние. Если в тп -ом разряде информационного слова содержится О, триггер 15 остается в нулевом состоянии. Спустя п тактов от начала Ц1жла, когда в сдвигающий регистр 2 запишется последний разряд слова, двоичный счетчик переполняется, и включенный на его выходе формирователь импульсов 14 вырабатывает короткий импульс, поступающий по управляющей шине 2О в схему управления, которая снимает запрещающий потенциал с управляющей шины 10. Одновременно короткий импульс с выхода формирователя 14 nocTjnaeT на нулевой вход триггера 11 и через элемент задержки 12 на вход элемента И 13. Если триггер 15 находится в единичном состоянии, то импульс проходит на вход элемента И 13, устанавливает триггер 11 в единичное состояние и одновременно сбрасывает триггер в нулевое состояние, подготавливая его тем самым к следующему циклу работы. Триггер 11 потенциалом своего единичного выхода открывает элемент И 8, а потенциалом нулевого плеча закрывает элемент И 9 по соответствующим вхо дам. На этом все элементы устройства заканчивают цикл работы. В следующем цикле работы записанное в предыдущем цикле в сдвигающий регистр 2 слово выталкивается и поступает на информационные входы буферных запоминающих блоков 3 и 4, однако оно записывается в блок 3, так как на его управляющий вход в течение всего второго цикла работы поступают синхроимпульсы с выхода элемен та И 8, Одновременно с этим в сдвигающий регистр 2 записывается второе слово, и цикл работы устройства происходит аналогично.

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

При разделении массива информации по значению кода в -т -ом разряде, элемент И 17 производит анализ (т-1)-го разряда каждого слова. Если в этом такте в первом разряде 5 сдвигающего регистра 2 будет 1, то на управляющую щину 18 поступает импульс. Таким образом, в процессе разделения массива информации по т-му разряду схема управления получает сведения о том, сколько слов массива содержат 1 в следующем (т-1)-ом разряде (нумерация разрядов слов начинается со старщих разрядов, так как слова поступают последовательным кодом старшими разрядами вперед). Эта информация может понадобиться при поразрядном упорядочении массива информации в порядке возрастания или убьгванкя кода его слов для вычисления начальных адресов ЗУ, по которым записываются подмассивы информации; получаемые на следующем этапе разделения (т.е. при разделении по {т-1)-му разряду).

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

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

Устройство для классификации двоичных чисел, содержащее сдвигающий регистр, двоичный счетчик, управляемый элемент задержки, управляющие входы которых соединены с щиной тактовых сигналов, триггеры, элементы И, формирователь импульсов, элемент задержки и два буферных запоминающих блока, отличающееся тем, что, с целью упрощения устройства, в нем выход последнего разряда сдвигающего регистра соединен с информационными входами первого и второго буферных запоминающих блоков, управ- ляющие входы которых подключены к выходам первого и второго элементов И соответственно, один из входов которых соединен с щиной тактовых сигналов, а другие входы - с управляющей шиной; третьи входы первого и второго элементов И подключены к прямому и инверсному выходам первого триггера соответственно, вход установки в нулевое состояние которого через эле«мент задержки соединен со входом третьего элемента И и через формирователь импульсов с выходом двоичного счетчика; другой вход третьего элемента И подключен к прямому выходу второго триггера, вход установки в нулевое состояние которого соединен со входом установки в единичное состояние первого триггера и с выходом третьего элемента И, вход установки в единичное состояние второго триггера через четвертый элемент И подключен к выходу первого разряда сдвигающего регистра и к выходу управляемого элемента задержки, другой выход которого и выход первого раз ряда сдвигающего регистра через пятый элемент И соединены со второй управляю545987 щей шиной вход управления управляемого элемента задержки подключен к третьей управляющей шине. Источники информации, принятые во вни- 5 мание при экспертизе: 1. Авторское свидетельство СССР 2 8 № 256363, кл. Q 06 Т- 7/06 от 12.08. 68 г. 2. Авторское свидетельство СССР № 466508, кп, Q 06 F 7/04 от 06.02. 73 г„ 3. Патент Франции № 2052292, кл. Q 06 F 7/04 от 14.05.1971 г.