Устройство для упорядочения данных Советский патент 1982 года по МПК G06F7/00 

(5) УСТРОЙСТВО для УПОРЯДОЧЕНИЯ ДАННЫХ

I

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

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

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

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

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

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

20

Поставленная цель достигается тем, что в устройстве для упорядочения данных, содержащем регистры, мультиплексоры, схемы сравнения. элемент ИЛИ, группу элементов И, триггер, постоянное запоминающее устройство, блок памяти, причем выходы блока памяти соединены с входами первого и второго мультиплексоров, выходы которых подключены к информационным входам первого и второго регистров соответственно, информационные выходы первого и второго регистров соединены с входами первой схемы сравнения, выход первой схемы сравнения соединен с входом установки в единичное состояние триг гера и с первым входом элемента ИЛИ, выход которого подключен к управляющему входу первого регистра, адресны вЬ(ходы которого соединены с управляю щими входами первой группы постоянного запоминающего устройства, первая и вторая группы выходов которог подключены к входам первой и второй групп соответственно третьего и че вертого мультиплексоров и к инфор мационным входам элементов И первой и второй групп соответственно, выходы элементов И первой и второй групп подключены к управляющим входам первого и второго мультиплексоров соот ветственно входная информационная шина устройства соединена с входом блока памяти, с информационными входами второго мультиплексора и третьего регистра, выходы которого подклю чены к входам первой группы второй схемы сравнения и к входам четвертог регистра, информационные выходы которого соединены с входами второй группы второй схемы сравнения, выход которой подключен к первому управляющему входу четвертого регистра,адрес «ые выходы которого соединены с управлякяцими входами второй группы постоянного запоминающего устройства первая управляющая шина запи(5й устройства подключена к управляющему входу блока памяти, вторая управляющая шина записи устройства соединена с управляющими входами первого, второго и третьего регистров, третья управляющая шина записи устройства подключена к втсфому входу элемента ИЛИ и к BTOpOKiy управляющему вход четвертого регистра, управляющая шина запуска устройства соединена с управляющими входами элементов И пер вой и второй групп и с счетным входом триггера.. На чертеже приведена блок-схема предлагаемого устройства. 9 4 Устройство содержит постоянное запоминающее устройство 1, мультиплексоры 2 и 3, группу элементов И k, триггер 5. схему 6 сравнения, элемент ИЛИ 7, схему 8 сравнения, регистры 9-12, мультиплексоры 13 и 1, блок 15 памяти, группу элементов И 1б, управляющие шины 17-19 записи, управляющую шину 20 запуска и выходные шины 21-2, входную информационную шину 25. Устройство работает следующим образом. Перед началом работы устанавливаюся в нулевое состояние все регистры устройства и триггер 5, на управляющую шину 20 запуска поступает потенциал логического нуля, формируя тем самым на выходах групп элементов И Ц и 16 нулевой код. Блок 15 памяти состоит из четырех регистров, которые хранят четыре числа массива в соответствии с порядком их поступления. Каждый из регистров блока 15 памяти имеет информационную зону, в которую заносится число входного массива, и адресную зону, в которой хранится адрес (номер) этого регистра. В адресной зоне первого регистра блока 15 хранится код 01, в адресной зоне второго - 10 и т.д. Регистры 9-12 также имеют информаци-; онную и адресную зоны, причем в регистре 11 каждой из зон соответствует отдельный регистр. Каждое из четырех чисел обрабатываемого массива имеет информационную часть и адресную часть (три младших разряда),которая содержит номер данного числа, соответствующий порядку его прступления. Число, поступившее первым, имеет в адресной части код 001, второе число - код 010 и т.д. Работа устройства начинается Q поступлением по входной информационной шине 25 первого числа в параллельном коде, информационная часть которого записывается в первый регистр блока 15 памяти с поступлением импульса по управляющей шине 17 записи, а все число записывается в регистры 10 и 12 с поступлением импульса по управляющей шине 18 записи. Нулевой код на управляющем входе мультиплексора 13 обеспечивает подключение входа регистра 11 к выходу регистра 12, а нулевой код на управляющем выходе второго мультиплексора 1 - подключение входной информационной шины 25 к регис ру 12, Далее поступает импульс по управляющей шине 19 записг на второй управляющий вход регистра 9,чт приводит к записи в него содержимого регистра 10, и через элемент ИЛИ 7 на управляющий вход регистра 11, ЧТОприводит к записи в него с держимого регистра 12. В начале,вт рого TaKta работы по информационно шине 25 поступает второе число, ин формационная часть которого с посту лением импульса по управляющей шине 17 записи записывается в информационную зону второго регистра блока 15 памяти, .само число записывается в регистры 10 и 12 с одновременным поступлением импульса по управляющей шине 18 записи. После этого схе мы 6 и 8 сравнения выполняют операции сравнения. Схема 6 сравнения, сравнивая содержимое информационных зон регистров 9 и 10, выдает на выходе импульс только в случае, если содержимое информационной зоны регистра 10 больше содержимого такой же зоны регистра 9. Появившийся на выходе первой схемы 6 сравнения импульс, поступая на первый управляющий вход регистра 9. приводит к записи содержимого всего регистра 1 в регистр 9- Таким образом, в результате операции сравнения Двух чи сел в информационной зоне регистра содержится больше из двух чисел, а в. адресной зоне - номер этого числа. Схема 8 сравнения совместно с регистрами 11 и 12 работает совершенно аналогично, однако она выдаёт импульс на выходе только в том случае, если содержимое информацион ной зоны регистра 12 меньше содержи мого информационной зоны регистра 1 1 . Аналогичные процессы происходят в третьем четвертом тактах.. В кон це четвертого такта в информаг ион-г ной зоне регистра, 9 находится максимальное из четырех поступивших чисел, а в адресной зоне этого регистра - номер максимального числа. В информационной зоне регистра 11 находится минимальное из четырех чисел, а в адресной зоне -.номер ми нимального .числа. Номера максимального и минимального чисел поступают- на адресные входы постоянного запоминающего 66 устройства 1, на выходе которого появляются номера двух других чисел обрабатываемого массива. В начале пятого такта на управляющей шине 20 запуска появляется логическая единица, что приводит к прохождению через группы элементов И Л и 16 на управляющие входы мультиплексоров 13 и }k кодов с соответственно первого и второго выходов постоянного запоминающего устройства 1, а также блокирует запись информации в адресную зону регистра 11. Одновременно трехразрядные коды с выходов постоянного запоминающего устройства 1 поступают на мультиплексоры 2 и 3. При наличии логического нуля на управляющих входах мультиплексоров 2 и 3 на выходе мультиплексора 2 присутствует код с первого выхода постоянного запоминающего устройства 1, на выходе мультиплексора 3 - код со второго выхода постоянного запоминающего устройства 1. Наличие логической единицы на. управляющих входах мультиплексоров 2 и 3 соответствует обратному расположению трехразрядных кодов на выходах этих мультиплексоров. Таким образом, на выходе мультиплексора 2 находится трехразрядный номер большего из двух оставшихся чисел массива, на выходе мультиплексора 3 трехразрядный номер меньшего. После появ- / ления логической единицы на управляющей шине 20 запуска поступают импульсы на управляющие шины 19 и 18 записи что приводит к записи в регистры 11 и 12 двоичных чисел из информационных зон тех регистров блока 15 памяти, номера которых поступили на управляющие входы соответственно мультиплексоров 13 и 14. Далее схема 8 сравнения выполняет операцию сравнения. Наличие или отутствие импульса на выходе схемы 8 равнения определяется соотношением еличин сравниваемых чисел. Появившись на управляющей шине 20 апуска, единичный сигнал в начале ятого такта сбрасывает в нулевое остоя1 1ие триггер 5- Поэтому, если на ыходе схемы 8 сравнения в пятом акте появляется имульс, то он, потупая на счетный вход триггера 5. станавливает его в единичное сосояние. 7 Таким образом, к концу пятого такта на выходных шинах 21-2 при.сутствуют трехразрядные номера четы рех регистров блока 15 которые хра нят числа массива соответственно уменьшению их абсолютных величин, т.е. процесс упорядочения массива из четырех чисел закончен. Быстродействие предлагаемого уст ройства определяется временем выпоя нения четырех операций сравнения независимо от разрядности чисел мас сива. Выигрыш по быстродействию отего применения по сравнению с устройством-аналогом составляет 1,5 р за. При равенстве разрядности чисел в предлагаемом устройстве и устройстве-прототипе выигрыш по быстро действию возрастает с ростом разряд ности. Так, при использовании предлагаемого устройства упорядочения данных в видеопроцессоре имитатора визуальной обстановки (ИБО) с разрядностью двоичных чисел, равной п 10, выигрыш по быстродействию V3,4 составляет М что позволяет отображать на экране ;ИВО 6 существенно более сложную, более реальную картину внешней обстановки. Следует также отметить, что его применение дает возможность эффективно совместить по времени работу других блоков видеопроцессора с работой устройства упорядочения данных. Так, в указанном случае этап непосредственного упорядочения данных включает четвертый и пятый такты, т.е. упорядоченный массив данных появляется спустя два такта (четвертый и пятый) после око чания работы блока видеопроцессора формирующего входной массив данных для предлагаемого устройства. Формула изобретения Устройство для упорядочения данных, содержащее регистры, мультипле соры, схемы сравнения, элемент ИЛИ группу элементов И, триггер, постоянное запоминающее устройство,бл памяти, причем выходы блока памяти соединены с входами первого и второ го мультиплексороё, выходы которых подключены к информационным входам первого и второго регистров соответственно, информационные выходы первого и второго регистров соедине ны с входами первой схемы сравнения отличающееся тем, что, с целью повышения быстродействия устройства, в нем выход первой схемы сравнения соединен с входом установки в единичное состояние триггера и с первым входом элемента ИЛИ, выход которого подключен к управляющему входу первого регистра, адресные выходы которого соединены с управляющими входами первой группы постоянного запоминающего устройства,первая и вторая группы выходов которого подключены к входам первой и второй групп соответственно третьего и четвертого мультиплексоров и к информационным входам элементов И первой и второй групп соответственно, выходы элементов И первой и второй групп лодключены к управляющим входам первого и второго мультиплексоров соответственно, входная информационная шина устройства соединена с входом блока памяти, с информационными входами второго мультиплексора и регистра, выходы которого подключены к входам первой группы второй схемы сравнения и к входам четвертого регистра, информационные выходы которого соединены с входами второй группы второй схемы сравнения, выход которой подключен к первому управляющему входу четвертого регистра, адресные выходы которого соединены с управ- . ляющими входами второй группы постоянного запоминающего устройства, первая управляющая шина записи устройства подключена к управляющему входу блока памяти, вторая управляющая шина записи устройства соединена с управляющими входами первого, второго и третьего ре|гистров, третья управляющая шина записи- устройства подключена к второму входу элемента ИЛИ и к втррому управляющему входу четвертого регистра, управляющая шина запуска устройства соединена с управляющими входами элементов И первой и второй групп и с счетным входом триггера. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № ii66508, кл. G 06 F 7/Q., 1973. 2.Авторское свидетельство СССР № , кл. G 06 F 7/06, 1975 (прототип).