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

 

Н.Н. Дученко, В.ф. Евдокимов, П.А. Тарч

Н.П..Тимошенко и И.Е. Цыгановский (72) Авторы изобретения

Институт электродинамики АН Украинской и Опытно- конструкторское технологическо бюро Института металлофизики AH Украинс (7! ) Заявители (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ ДАННЫХ сел 11).

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

Известно устройство для классификации двоичных чисел, выполненное на основе двух регистров и схемы сравнения. 8 нем одновременно произ. водится сравнение только двух чиНедостатком известного устройства является невысокое быстродействие при выполнении классификации четырех чисел в порядке убывания (или возрастания) их кода, что обусловлено поступлением чисел массива s последовательном коде и сравнительно большим числом операций сравнения.

Наиболее близкое к предлагаемому устоойство для классификации двоич" ных чисел, содержащее сдвигающий приемный регистр, два буферных за" поминающих блока, управляемый элемент задержки, двоичный счетчик, пять элементов И, два триггера,элемент задержки и формирователь импульсов. В основе классификации чисел лежит анализ каждого из Il раэ1в рядов чисел массива на наличие единицы или нуля. Числа массива поступают одно за другим в последовательном коде P2).

Недостатком известного устройства

)5 является его низкое быстрореиствие, которое зависит от разрядности обрабатываемых чисел.

Цель изобретения — повышение бы20 стродействия устройства.

Поставленная цель достигается тем, что в устройстве для упорядочения данных, содержащем регистры, мультиплексоры, схемы сравнения, 911506

3 элемент ИЛИ, группу элементов И, триггер, постоянное запоминающее устройство, блок памяти, причем выходы блока памяти соединены с входами первого и второго мультиплексоров, выходы которых подключены. к информационным входам первого и второго регистров соответственно, информационные выходы первого .и второго регистров соединены с входами пер- 1о . вой схемы сравнения, выход первой схемы сравнения соединен с входом установки в единичное состояние триггера и с первым входом элемента ИЛИ, выход которого подключен к управляющему входу первого регистра, адресные выходы которого соединены с управляющими входами первой группы постоянного запоминающего устройства, первая и вторая .группы выходов которого З1 подключены к входам первой и второй групп соответственно третьего и че-вертого мультиплексоров и к информационным входам элементов И первой и второй групп соответственно, выходы элементов И первой и второй групп подключены к управляющим входам первого и второго мультиплексоров соответственно, входная информационная шина устройства соединена с входом блока памяти, с информационными входами второго мультиплексора и третьего регистра, выходы которого подключены к входам первой группы второй схемы сравнения и к входам четвертого регистра, информационные выходы ко И торого соединены с входами второй группы второй схемы сравнения, выход которой подключен к первому управляющему входу четвертого регистра,адресные выходы которого соединены с управляющими входами второй группы постоянного запоминающего устройства, первая управляющая шина запи& устройства подключена к управляющему входу. блока памяти, вторая управляю45 щая шина записи устройства соединена с управляющими входами первого, второго и третьего регистров, третья управляющая шина записи устройства подключена к второму входу элемента ИЛИ и к второму управляющему входу четвертого регистра, управляющая шина запуска устройства соединена с управляющими входами элементов И первой и второй групп и с счетным входом триггера., На чертеже приведена блок-схема предлагаемого устройства.

Устройство содержит постоянное запоминающее устройство 1, мультиплексоры 2 и 3, группу элементов И 4, триггер 5, схему 6 сравнения, элемент ИЛИ 7, схему 8 сравнения, регистры 9-12, мультиплексоры 13 и

14, блок 15 памяти, группу элементов И 16, управляющие шины 17-19 записи, управляющую шину 20 запуска и выходные шины 21"24, входную информационную шину 25.

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

Перед началом работы устанавливаюся в нулевое состояние все регистры устройства и триггер 5, на управляющую шину 20 запуска поступает потенциал логического нуля, формируя тем самым на выходах rpynn элементов И 4 и 16 нулевой код.

Блок 15 памяти состоит из четырех регистров, которые хранят четыре числа массива в соответствии с порядком их поступления. Каждый из регистров блока 15 памяти имеет информационную зону, в которую заносится число входного массива, и адресную зону, в которой хранится адрес (номер) этого регистра. 8 адресной зоне первого регистра блока 15 хранится код 01. в адресной зоне второго - 10 и т.д.

Регистры 9-12 также имеют информаци-, онную и адресную зоны, причем в регистре 11 каждой из зон соответствует отдельный регистр. Каждое из четырех чисел обрабатываемого массива имеет информационную часть и адресную часть (три младших разряда),которая содержит номер данного числа, соответствующий порядку его поступления. Число, поступившее первым, имеет в адресной части код 001, второе число - код 010 и т.д.

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

17 записи, а все число записывается в регистры 10 и 12 с поступлением импульса по управляющей шине 18 записи. Нулевой код на управляющем входе мультиплексора 13 обеспечивает подключение входа регистра 11 к выходу регистра 12, а нулевой код на управляющем выходе второго муль5 9«506 6 запуска, единичный сигнал в начале гистра - номер максимального числа.

В информационной зоне регистра 11 пятого такта сбрасывает в нулевое состояние триггер 5. Поэтому, если на . выходе схемы 8 сравнения в пятом такте появляется имульс, то он, понаходится минимальное из четырех чисел, а в адресной зоне - номер ми55 нималь ного, числа. ступая на счетный вход триггера 5, Номера максимального и минимального чисел поступают на адресные устанавливает его в единичное сосвходы постоянного запоминающего тояние. типлексора 14 — подключение вход- устройства 1, на выходе которого ной информационной шины 25 к регист- появляются номера двух других чисел ру 12. Далее поступает импульс по обрабатываемого массива. управляющей шине 19 запис на вто- В начале пятого такта на управрой управляющий вход регистра 9,что 5 ляющей шине 20 запуска появляется приводит к записи в него содержи- логическая единица, что приводит к мого регистра 10, и через элемент прохождению - ерез группы элеменИЛИ 7 на управляющий вход регистра тов И 4 и 16 на управляющие входы

11, что приводит к записи в него со- мультиплексоров 13 и 14 кодов c содержимого регистра 12. В начале,BTQ to ответственно первого и второго вырого такта работы по информационной ходов постоянного запоминающего шине 25 поступает второе число, ин- устройства 1, а также блокирует за-. формационная часть которого с поступ- пись информации в адресную зону релением импульса по управляющей шине гистра ll.

17 записи записывается в информа- . 15 Одновременно трехраэрядные коды ционную зону второго регистра блока с выходов постоянного запоминающего

15 памяти, .само число записывается устройства l поступают на мультиплекв регистры 10 и 12 с одновременным соры 2 и 3. При наличии логического поступлением импульса по управляю- нуля на управляющих входах мультищей шине. 18 записи. После этого схе- щ плексоров 2 и 3 на выходе мультимы 6 и 8 сравнения выполняют опера- плексора 2 присутствует код с первого ции сравнения. Схема 6 сравнения, выхода постоянного запоминающего устсравнивая содержимое информационных ройства 1, на выходе мультиплексозон регистров 9 и 10, выдает на вы- ра 3 — код со второго выхода походе импульс только в случае, если г5 стоянного запоминающего устройства 1 ° содержимое информационной зоны ре- Наличие логической единицы на. управгистра 10 больше содержимого такой ляющих входах мультиплексоров 2 и 3 же зоны регистра 9. Появившийся на соответствует обратному расположевыходе первой схемы 6 сравнения. им- нию трехразрядных кодов на выходах пульс, поступая на первый управляю- зр этих мультиплексоров. Таким образом, щий вход регистра 9, приводит к на выходе мультиплексора 2 находитзаписи содержимого всего регистра 10 ся трехразрядный номер большего из в регистр 9. Таким образом, в ре- двух оставшихся чисел массива, на зультате операцйи сравнения двух чи-- выходе мультиплексора 3 - трехразсел в информационной зоне регистра 9 35 рядный номер меньшего. После появсодержится больше из двух чисел, а ° ления логической единицы íà управв. адресной зоне — номер этого чис- ляющей шине 20 запуска поступают им" ла. Схема 8 сравнения совместно с пульсы на управляющие шины 19 и 18 регистрами 11 и 12 работает совер- записи что приводит к записи в решенно аналогично, однако она вы- 4О гистры 11 и 12 двоичных чисел из дает импульс на выходе только в том информационных эон тех регистров случае, если содержимое информацион- блока 15 памяти, номера которых ной зоны регистра 12 меньше содержи- поступили на управляющие входы соотмого информационной зоны регист- ветственно мультиплексоров 13 и l4. ра 11. 45 Далее схема 8 сравнения выполняет

Аналогичные процессы происходят операцию сравнения. Наличие или отв третьем .и четвертом тактах., В KQH сутствие импульса на выходе схемы 8 це четвертого такта в информацион-. сравнения определяется соотношением ной зоне регистра, 9 находится мак- величин сравниваемых чисел. симальное из четырех поступивших

50 чисел, а в адресной зоне этого ре- Появившись на управляющей шине 20

Таким образом, к концу пятого такта на выходных шинах 21-24 при.сутствуют трехразрядные номера четырех регистров блока 15, которые хранят числа массива соответственно 5 уменьшению их абсолютных величин, т.е. процесс упорядочения массива из четырех чисел закончен. быстродействие предлагаемого устройства определяется временем выполнения четырех операций сравнения независимо от разрядности чисел массива. Выигрыш по быстродействию от его применения по сравнению c YcT

1 ройством-аналогом составляет 1,5 раза. При равенстве разрядности чисел в предлагаемом устройстве и устройстве-прототипе выигрыш по быстродействию возрастает с ростом разрядности. Так, при использовании пред- 20 лагаемого устройства упорядочения данных в видеопроцессоре имитатора визуальной обстановки (ИВО} с раз1 рядностью двоичных чисел, равной . и = 10, выигрыш по быстродействию 4/3 .10 2 составляет И 2 в раза

9 что позволяет отображать на экране

;ИВО 6 существенно более сложную, более реальную картину внешней об- Зо становки. Следует также отметить, что его применение дает возможность эффективно совместить по времени работу других блоков видеопроцессора с работой устройства упорядочения данных. Так, в указанном случае этап непосредственного упорядочения данных включает четвертый и пятый такты, т.е. упорядоченный массив данных появляется спустя два 4в такта {четвертый и пятый) после окончания работы блока видеопроцессора, формирующего входной массив данных для предлагаемого устройства.

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

Устройство для упорядочения данных, содержащее регистры, мультиплексоры, схемы сравнения, элемент ИЛИ, группу элементов И, триггер, постоянное запоминающее устройство, блок 5в памяти, причем выходы блока памяти соединены с входами первого и второго мультиплексороЬ, выходы которых подключены к информационным входам первого и второго регистров соответственно, информационные выходы первого и второго регистров соединены с входами первой схемы сравнения, 06 8 о т л и ч а ю щ е е с я тем что

В 1 с целью повышения быстродействия устройства, в нем выход первой схемы сравнения соединен с входом установки в единичное состояние триггера и с первым входом элемента ИЛИ, выход которого подключен к управляющему входу первого регистра, адресные выходы которого соединены с управляющими входами первой группы постоянного запоминающего устройства,первая и вторая группы выходов которого подключены к входам первой и второй групп соответственно третьего и четвертого мультиплексоров и к информационным входам элементов И первой и второй групп соответственно, выходы элементов И первой и второй групп;подключены к управляющим входам первого и второго мультиплексоров соответственно, входная информационная шина устройства соединена с входом блока памяти, с информационными входами второго мультиплексора и третьего регистра, выходы которого подключены к входам первой группы второй схемы сравнения и к входам четвертого регистра, информационные выходы которого соединены с вхсдами второй группы второй схемы сравнения, выход которой подключен к первому управляющему входу четвертого регистра, адресные выходы которого соединены с управляющими входами второй группы постоянного запоминающего устройства, первая управляющая шина записи устройства подключена к управляющему входу блока памяти, вторая управляющая шина записи устройства соединена с управляющими входами первого, второго и третьего ре гистров, третья управляющая шина записи устройства подключена к второму входу элемента ИЛИ и к второму управляющему входу четвертого регистра, управляющая шина запуска устройства соединена с управляющими входами элементов И первой и второй rpynn и с счетным входом триггера.

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

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

М 466508, кл. G 06 F 7/04., 1973.

2. Авторское свидетельство СССР и 545982, кл. G 06 F 7/06, 1975 (прототип).

911506

21

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

Редактор А. Лежнина Техред Т,Матоsкa Корректор Ю. Макаренко

»4(Заказ 1129/40 ираж 732 Подписное

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

113035, Москва, Ж-35, Рауаская наб., д. 4/5 филиал ППП "Патент", г. Ужгород, ул. Проектная,4