Устройство для упорядочения данных

(72) Авторы изобретения Институт электродинамики АН Украинскойи Опытно-конструкторское технологическобюро Института металлофизики АН Украинс) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ ДАН леНедостатк является нев при выполнен чисел врастанияпоступледовательбольшим я их ием ом к исло тем,чения мульт Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных устройствах обработки информации, в которых требуется быстрое уорядочение массива информации содержащего только четыре числа, поступающих параллельным кодом одно эа другим.Известно устройство для классификации двоичных чисел, выполненное на основе двух регистров и схемы сравнения. В нем одновременно произ. водится сравнение только двух чисел 11 . известного устройства окое быстродействие и классификации четырех е убывания (или возода, что обусловлено исел массива в последе и сравнительно м операций сравнения. Наиболее близкое к предлагаемомуустоойство для классификации двоич"ных чисел, содержащее сдвигающийприемный регистр, два буферных за"поминающих блока, управляемый эмент задержки, двоичный счетчик,пять элементов И, два триггера,элемент задержки и формирователь импульсов. В основе классификации чисел лежит анализ каждого из и разрядов чисел массива на наличие единицы или нуля, Числа массива посту"пают одно за другим в последовательном коде 2.Недостатком известного устройстваявляется его низкое быстродействие,которое зависит от разрядности обрабатываемых чисел,Цель изобретения - повышение быстродействия устройства.Поставленная цель достигаетсячто в устройстве для упорядо"данных, содержащем регистры,иплексоры, схемы сравнения,911506 3элемент ИЛИ, группу элементов И,триггер, постоянное запоминающееустройство, блок памяти, причем выходы блока памяти соединены с входами первого и второго мультиплексоров, выходы которых подключены. к информационным входам первого и второго регистров соответственно, информационные выходы первого .и второгорегистров соединены с входами пер. вой схемы сравнения, выход первойсхемы сравнения соединен с входомустановки в единичное состояние триггера и с первым входом элемента ИЛИ,выход которого подключен к управляющему входу первого регистра, адресныевыходы которого соединены с управляющими входами первой группы постоянного запоминающего устройства, первая и вторая .группы выходов которого З,подключены к входам первой и второйгрупп соответственно третьего иче-вертого мультиплексоров и к информационным входам элементов И первойи второй групп соответственно, выходы элементов И первой и второй группподключены к управляющим входам первого и второго мультиплексоров соответственно, входная информационнаяшина устройства соединена с входомблока памяти, с информационными входами второго мультиплексора и третьего регистра, выходы которого подключены к входам первой группы второйсхемы сравнения и к входам четвертогорегистра, информационные выходы ко Иторого соединены с входами второйгруппы второй схемы сравнения, выходкоторой подключен к первому управляющему входу четвертого регистра,адресные выходы которого соединеныс управляющими входами второй группыпостоянного запоминающего устройства,первая управляющая шина запиЖ устройства подключена к управляющемувходу. блока памяти, вторая управляю 43щая шина записи устройства соединенас управляющими входами первого, вто"рого и третьего регистров, третьяуправляющая шина записи устройстваподключена к второму входу элемента ИЛИ и к второму управляющему входучетвертого регистра, управляющая шиназапуска устройства соединена суправляющими входами элементов И первой и второй групп и с счетным вхо- ффдом триггера.,На чертеже приведена блок-схемапредлагаемого устройства. 4Устройство содержит постоянное запоминающее устройство 1, мультиплексоры 2 и 3, группу элементов И 4, триггер 5, схему 6 сравнения, элемент ИЛИ 7, схему 8 сравнения, регистры 9-12, мультиплексоры 13 и 14, блок 15 памяти, группу элементов И 16, управляющие шины 17-19 записи, управляющую шину 20 запуска и выходные шины 21-24, входную информационную шину 25.Устройство работает следующим образом.Перед началом работы устанавливаюся в нулевое состояние все регистры устройства и триггер 5, на управляющую шину 20 запуска поступает потенциал логического нуля, формируя тем самым на выходах групп элементов И 4 и 16 нулевой код.Блок 15 памяти состоит из четырех регистров, которые хранят четыре числа массива в соответствии с порядком их поступления. Каждый из регистров блока 15 памяти имеет информационную зону, в которую заносится число входного массива, и адресную зону, в которой хранится адрес (номер) этого регистра. 8 адресной зоне первого регистра блока 15 хранится код 01. в адресной зоне второго - 10 и т,д, Регистры 9-12 также имеют информаци-, онную и адресную зоны, причем в регистре 11 каждой из зон соответствует отдельный регистр. Каждое из четырех чисел обрабатываемого массива имеет информационную часть и адресную часть (три младших разряда),которая содержит номер данного числа, соответствующий порядку его поступления. Число, поступившее первым, имеет в адресной части код 001, второе число - код 010 и т,д. Работа устройства начинается с поступлением по входной информационной шине 25 первого числа в параллельном коде, информационная часть которого записывается в первый регистр блока 15 памяти с поступлением импульса по управляющей шине 17 записи, а все число записывается в регистры 10 и 12 с поступлением импульса по управляющей шине 18 записи, Нулевой код на управляющем входе мультиплексора 13 обеспечивает подключение входа регистра 11 к выходу регистра 12, а нулевой код на управляющем выходе второго муль9типлексора 14 - подключение входной информационной шины 25 к регист.ру 12. Далее поступает импульс поуправляющей шине 19 запис на второй управляющий вход регистра 9,цтоприводит к записи в него содержимого регистра 10, и через элементИЛИ 7 на управляющий вход регистра11, что приводит к записи в него содержимого регистра 12. В начале,второго такта работы по информационнойшине 25 поступает второе число, информационная часть которого с поступлением импульса по управляющей шине17 записи записывается в информационную зону второго регистра блока15 памяти, .само число записываетсяв регистры 10 и 12 с одновременнымпоступлением импульса по управляющей шине. 18 записи, После этого схемы 6 и 8 сравнения выполняют операции сравнения. Схема 6 сравнения,сравнивая содержимое информационныхзон регистров 9 и 10, выдает на выходе импульс только в случае, еслисодержимое информационной зоны регистра 10 больше содержимого такойже зоны регистра 9. Появившийся навыходе первой схемы 6 сравнения импульс, поступая на первый управляющий вход регистра 9, приводит кзаписи содержимого всего регистра 10в регистр 9. Таким образом, в результате операцйи сравнения двух чи-.сел в информационной зоне регистра 9содержится больше из двух чисел, ав. адресной зоне - номер этого числа. Схема 8 сравнения совместно срегистрами 11 и 12 работает совершенно аналогично, однако она выдает импульс на выходе только в томслучае, если содержимое информационной .зоны регистра 12 меньше содержимого информационной зоны регистра 11.Аналогичные процессы происходятв третьем и четвертом тактах, В конце четвертого такта в информацион-,ной зоне регистра, 9 находится максимальное из четырех поступившихчисел, а в адресной зоне этого регистра - номер максимального числа.В информационной зоне регистра 11находится минимальное из четырехчисел, а в адресной зоне - номер минимального,числа,Номера максимального и минимального чисел поступают. на адресныевходы постоянного запоминающего 11506 6устройства 1, на выходе которогопоявляются номера двух других чиселобрабатываемого массива.В начале пятого такта на управляющей шине 20 запуска появляетсялогическая единица, что приводит кпрохождение .ерез группы элементов И 4 и 16 на управляющие входымультиплексоров 13 и 14 кодов с со.1 о ответственно первого и второго выходов постоянного запоминающегоустройства 1, а также блокирует за-.пись информации в адресную зону регистра 11.15 ОдновремеНно трехраэрядные кодыс выходов постоянного запоминающегоустройства 1 поступают на мультиплексоры 2 и 3. При наличии логическогонуля на управляющих входах мультиго плексоров 2 и 3 на выходе мультиплексора 2 присутствует код с первоговыхода постоянного запоминающего устройства 1, на выходе мультиплексора 3 - код со второго выхода по стоянного запоминающего устройства 1.Наличие логической единицы на. управляющих входах мультиплексоров 2 и 3соответствует обратному расположе нию трехразрядных кодов на выходах зо этих мультиплексоров. Таким образом.на выходе мультиплексора 2 находится трехразрядный номер большего издвух оставшихся чисел массива, навыходе мультиплексора 3 - трехраз Рядный номер меньшего. После появления логической единицы на управляющей шине 20 запуска поступают импульсы на управляющие шины 19 и 18записи что приводит к записи в ре 4 о гистры 11 и 12 двоичных чисел изинформационных эон тех регистровблока 15 памяти, номера которыхпоступили на управляющие входы соответственно мультиплексоров 13 и 14.45 Далее схема 8 сравнения выполняетоперацию сравнения. Наличие или от сутствие импульса на выходе схемы 8сравнения определяется соотношениемвелицин сравниваемых чисел.50Появившись на управляющей шине 20запуска, единичный сигнал в началепятого такта сбрасывает в нулевоесостояние триггер 5. Поэтому, если на .выходе схемы 8 сравнения в пятом 55такте появляется имульс, то он,. поступая на счетный вход триггера 5,устанавливает его в единичное состояние.9115Таким образом, к концу пятоготакта на выходных шинах 21-24 при,сутствуют трехразрядные номера четырех регистров блока 15, которые хранят числа массива соответственно 5уменьшению их абсолютных величин,т.е. процесс упорядочения массиваиз четырех чисел закончен.Быстродействие предлагаемого устройства определяется временем выполнения четырех операций сравнениянезависимо от разрядности чисел массива. Выигрыш по быстродействию отего применения по сравнению с уст 1ройством-аналогом составляет 1,5 раэа. При равенстве разрядности чиселв предлагаемом устройстве и устройстве-прототипе выигрыш по быстродействию возрастает с ростом разрядности. Так, при использовании предлагаемого устройства упорядоченияданных в видеопроцессоре имитаторавизуальной обстановки (ИВО) с раз 1рядностью двоичных чисел, равной. и = 10, выигрыш по быстродействию4/3.10 2составляет И2 в раза9что позволяет отображать на экране;ИВО 6 существенно более сложную,более реальную картину внешней обстановки, Следует также отметить,что его применение дает возможностьэффективно совместить по времениработу других блоков видеопроцессора с работой устройства упорядоцения данных, Так, в указанном случае этап непосредственного упорядочения данных включает четвертыйи пятый такты, т.е. упорядоченныймассив данных появляется спустя два 40такта четвертый и пятый) после окончания работы блока видеопроцессора,формирующего входной массив данныхдля предлагаемого устройства,Формула изобретения 45Устройство для упорядоцения данных, содержащее регистры, мультиплексоры, схемы сравнения, элемент ИЛИ,группу элементов И, триггер, постоянное запоминающее устройство, блок 50памяти, причем выходы блока памятисоединены с входами первого и второго мультиплексороЬ, выходы которыхподключены к информационным входампервого и второго регистров соответственно, информационные выходыпервого и второго регистров соединены с входами первой схемы сравнения,Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР й 466508, кл, С 06 Р 7/04, 1973 2. Авторское свидетельство СССР й 545982, кл, С Об Р 7/06, 1975 прототип).933506 г Составитель В. БелкинТехред Т,Иаточка 1(орректор Ю. Макарен Лежни едакт Заказ 130 филиал ППП "Патент", г. Ужгород, ул. Проектн Тираж 732ИПИ Государственного кпо делам изобретений