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

СОЮЗ СОНЕТСНИХСОЦИАЛИСТИЧ ЕСНИХРЕСПУБЛИН 9) (11) 06 Г 7 ЗАВИСАНИЕ ИЗОБРЕТЕН(57) И УПОР ЯДО оЕ Н 1 О ДЛ СТРОИС1 СЕЛзооретной те л. Р .А.Ст .8) чис ение зо к лител ватьс обраб ния -ляров ра при построен тки информаци распирение фу тей за счет у чисел с учето ьство СССР 7/06, 1983 тво СССР /06, 1985. ете де телОб Ртель6 Р возмасможн сиво втореиг,/ ОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Авторское сР 1073770, кл.Авторское свиР 1183956, кл. Г 1 осится к в может испо ии систем с и. Цель изо нкцио наль ны порядочения м знака и п1 3833ния равных чисел при выводе. Устройство содержит блок памяти 11, мультиппексор 10, два триггера 12, 14, реверсивный счетчик 13, группу элементов И 15-1 - 15-(1+1), формирователь импульсов 20, два элемента И 18, 19, два элемента НЕ 8, 17 и элемент ИЛИ 16, Нри упорядочении массива чисел осуществляется запись в блок памяти признаков наличия чисел по адресу, задаваемому значением числа. СчитыЗбвание информации производится счетчиком с линейным нарастанием или убыванием возможных значений числа. Блокпамяти управляет выводом чисел из счетчика и разрешает дальнейшее, линейное нарастание или убывание его кода. Дополнительный дешифратор управляет режимом ввода и записи начальных условий в счетчик и два триггера памяти начальных условий.2 з.п. ф лы 3 ил, Изобретение относится к вычислительной технике и может использоваться при построении систем сбора и обработки информации.11 елью изобретения является расширение Функциональных возможностей за счет упорядочения массивов чисел с учетом знака и повторения .равных чисел при выводе.На Фиг.1 дана Функциональная схема устройства для упорядочения массива чисел; на фиг.2 - схема блок памяти; на фиг.З - схема ячейки памяти, входящей в состав блока памяти.Устройство для упорядочения массива чисел (фиг,1) содержит управляющий вход 1 информации, вход 2 "Сброс", вход 3 задания режима сортировки чисел при выводе упорядоченного массива, входы 4-1 - 4-М модуля, вход 5 знака, вход 6 записи чисел, тактовый вход 7, элемент НЕ 8, элемент И 9, мультиплексор 10, блок 11 памяти, Э"триггер 12, Я-"разрядный счетчик 13, Р-триггер 14,группу из И+1 элементов И 15-1 - 15-Ы четвертый элемент И 15-(И+1), элемент ИЛИ 16, элемент НЕ 17, элементы НЕ 18 и 19, Формирователь 20 импульса по переднему Фронту входного сигнала, дешифратор 21 нуля, выходы 221 - 22-И, выход 23 знака упорядоченных чисел, синхронизирующий выход 24, управляющий выход 25. Блок 11 памяти содержит вход 26 выбора режима, тактовый вход 27, синхронпзирующий вход 28 конца цикла ввода, вход 29 "Сброс", адресные входы ЗР".1ЗО-И, адресный вход 31 2знака числа, формирователь 32 импуль"са, элемент НЕ 33, группу элементовИ 34-1 - 34-(М+1), группу элементов 5И 35-1 35-(М+1) ячейки 36-1 - 36(М++1) памяти, группу элементов И 37-137-(М+1), элемент ИЛИ 38, преобразователь 39 двоичного кода в позиционный, выход 40 блока памяти.10 Ячейки 36-1 - 36-(М+1) памяти содержат синхронизирующий вход 41 кон:ца цикла ввода, суммирующий 42 и вычитающий 43 входы, вход 44 "Сброс",синхронизирующий вход 45, реверсив ный счетчик 46, дешифратор 47 нуля,регистр 48, элемент И 49, информационный выход 50.Устройство работает следунццим образом.20 Для ввода чисел упорядоченногомассива необходимо подать на вход 2(фиг.1) импульс, осуществляющий установку в нулевое состояние реверсивного счетчика 46 (фиг.З), установить 25 единичный потенциал на входе 1, переключающий мультиплексор 10 (фиг.1)в режим передачи информации с входаА на выход С, разрешающий открытьсягруппе входных элементов И 34-1 30 34-(М+1) (фиг.2) для прохождения импульсов с тактового входа 27 (фиг.2)на суммирующий вход счетчика 46 изакрывающий нулевым сигналом с выхода элемента НЕ 17 прохождение такто .вых импульсов с входа 7 через элемент И 18 на вход И-разрядного счетчика 13, а также с выхода элементаНЕ 33 на элементы И 37-1 - 37(М+1).Кроме того, необходимо подать синх ронно с импульсами записи на входе 6числа упорядоченного массива на вхо 1383336ды 4-1 - 4-И модули чисел, а на вход 5 -. знаки чисел.Каждым импульсом записи на входе 6, проходящем через элемент ИЛИ 16 на вход "Запись" счетчика 13 и тактовый вход триггера 14, осуществляется запись очередного числа (модуля в счетчик и знака в триггер)аВ связи с тем, что мультиплексор 10 открыт для прохождения импульса записи с входа А на выход С с его выхода, этот импульс .поступает на тактовый вход 27 блока памяти. В это же время с выхода счетчика 13 модуль числа, а с выхода 0-триггера 14 знак числа подаются на адресные входы 30-1 - 30-М и 31 блока 11 памяти. Двоичный код модуля и знака числа преобразуется преобразователем 39 в 20 позиционный. При этом на одном из выходов преобразователя 39 устанавливается уровень логической единицы, разрешающий прохождение тактового импульса с входа 27 через соответствую щий элемент И 34-1 - 34-(М+1) на суммирующий вход относящегося в нему счетчика каждой из ячеек 36-1 - 36- (М+1). Счетчик каждой из ячеек 36-1 - 36-(М+1) осуществляет фиксацию наличия соответствующего ему числа на информационных входах устрой- . ства. В связи с тем, что при установке каждого конкретного адреса происходит нарастание кода счетчика каж дой из ячеек 36-1 - 36-(М+1) на одну единицу, разные числа в упорядоченном массиве могут следовать в произвольном порядке. Число разрядов счетчиков 46, следовательно, и регистров 40 48 должно выбираться из условия максимально возможного количества разных чисел в упорядоченном массиве. Таким образом, после подачи всех 45 чисел упорядоченного массива на входы 4-1 - 4-И и 5 устройства в счетчиках 46 каждой из ячеек 36-1 - 36- (М+1) памяти блока 11 памяти устанавливаются коды, пропорциональные количеству равных чисел в упорядоченном массиве. Эти коды задним фронтом сигнала Ввод-выводц на входе 1 устройства с помощью элемента НЕ 33 н формирователя 32 переписываются из счетчиков 46 в регистры 48 каждой из ячеек 36-1 - 36-(М+1) памяти.Для вывода упорядоченного массива необходимо подать на входы 4 1 4-И, вход 5 и вход 3 код, соответствующий требованиям начальным условиям по таблице. Необходимо также осуществить запись соответствующих кодов начальныхусловий в счетчик 13, триггеры 14 и12 путем подачи импульса записи навход 6 устройства и установить навходе 1 устройства нулевой потенциал, переключающий мультиплексор 10в режим передачи сигнала с входа Вна выход С, закрывающий группу входных элементов И 34-1 - 34-(М+1),разрешающий открываться входным элементам И 35-1 - 35-(М+1), выходным элементам И 37-1 - 37-(М+1) и элементуИ 18,Пусть, например, необходимо вывести положительные числа в порядке ихвозрастания. После подачи соответствующих указаний см. таблиду потенциалов на входы 3-5 устройства триггер 12 устанавливается в единичноесостояние, предписывающее работусчетчика 13 в режиме суммирования,сам счетчик 13 устанавливается в нулевое состояние, т.е. значение минимального числа, а триггер 14 - в единичное состояние, соответствующее положительным числам.Как только на входе 1 устройстваустанавливается нулевой потенциал,элемент И 18 открывается единичнымпотенциалом с выхода элемента НЕ 17для прохождения тактовых импульсов свхода 7 устройства на тактовый входсчетчика 13 и через мультыплексор 10на тактовый вход блока 11 памяти.Нулевой выходной код счетчика 13и единичный потенциал с выхода триггера 14 подаются на адресные выходы30-1 - ЗО-Б,31 блока 11 памяти, который осуществляет проверку присущствия в упорядоченном массиве такогокода. Информация об этом хранится вячейках 36-1 - 36-(М+1) памяти. Вслучае, если при записи упорядоченного массива этот код присутствует, посоответствующему адресу всчетчике46 устанавливается единичный код, если таких чисел несколько, код в счетчике 46 соответствует количеству нулевых чисел со .знаком плюс в упорядоченном массиве, если этого числа вмассиве нет, в счетчике нулевой код,установленный перед вводом чисел упорядоченного массива сигналом "Сброс"5 13833 на входе 2 устройства, входе 27 блока 11 памяти и входе 44 ячеек 36-136-(М+) памяти.Дешифратор 47, выход которого является выходом ячейки 36 памяти, от 5 мечает выходным сигналом наличие нулевого кода в счетчике 46 и единичным кода, отличного от нулевого.Аналогично производится проверка наличия чисел в ,порядоченном массиве, отличных от нуля.Установка на адресных входах 30-1 - 30-М и 31 блока 11 памяти некоторого кода приводит при считывании к обращению к 1-й ячейке памяти. . Это осуществляется подключением ее выхода 50, т.е. выхода дешифратора 47, через открытые единичным потенциалом с выхода элемента НЕ 33 и с 20 выхода преобразователя 39 элементы И37"1 - 37(М+1) и элемент ИЛИ 38 к выходу 40 запоминающего устройства. Следовательно, если число в счетчике 46 отлично от нуля, т.е. при запи си присутствуют числа, соответствующие адресу 1-й ячейки, на выходе блока 11 памяти устанавливается логическая единица, разрешающая прохождение при считывании выходного кода счетчи ка 13, потенциала с выхода триггера 14 и тактового импульса с выхода открытого элемента И 18 через элементы И 15-1 - 15-(И+1) и 19 на выходы 22-1 - 22-Б, 23 и 24 устройства.В связи с тем, что выход дешифратора 47 нуля соединен с одним входом элемента И 49, на второй вход которого подается тактовый сигнал, в случае, если код в счетчике отличен от нуля, тактовый импульс через открытый элемент И 49 подается на вычитающий вход счетчика 46.Таким образом, с каждым тактовым импульсом в счетчике 46 код убывает 45 на единицу дотех пор, пока дешифра тор нуля не запретит прохождение тактовых импульсов через элемент И 49 нулевым сигналом на его выходе,Одновременно дешифратор 47 при наличии равных чисел в упорядоченном массиве запрещает прохождение тактовых импульсов в счетчик 13 с помощью элемента НЕ 8 и элемента И 9 до тех пор, пока код в х-м счетчике 46 не станет нулевым. Как только это прои зойдет, нулевой выходной потенциал дешифратора 47 ячейки 36 памяти через элемент НЕ 8 разрешает прохожде 6Збние последующего тактового импульса с выхода элемента И 18 через элемент И 9 на вход счетчика 13.В соответствии с этим как только будут считаны все нулевые числа из соответствующей ячейке.36 памяти следующим за этим тактовым импульсом, счетчик 13 устанавливается в состояние 001 и начинается проверка наличия таких чисел в упорядоченном массиве, которая может быть рассмотрена аналогично.В связи с тем, что числа в счетчике 13 линейно нарастают и производится последовательная проверка наличия каждого из этих чисел, на выходах устройства 22-1 - 22-И, 23 выделяются в нарастающем порядке числа, присутствовавшие в упорядоченном массиве до тех пор, пока не установится в счетчике 13 нулевое число, что отме-" чается дешифратором 21. Если вслед за этим не вводятся новые начальные условия, счетчик 13 циклически повторяет вывод положительных чисел в порядке нарастания. Если вводятся новые начальные условия (см. таблицу), счетчик 13 и триггер 14 обеспечивают циклический вывод положительных чисел в порядке убывания (в этом случае счетчик работает на вычитание), отрицательных чисел в порядке возрастания (счетчик 13 работает на вычитание), отрицательных чисел в порядке убывания (счетчик 13 работает на суммирование). Работу устройства в этих режимах рассмотреть несложно по аналогии с описанным.При каждой установке нулевого ко-. да счетчика 13 можно осуществлять установку любых начальных условий, отмеченных в таблице, что позволяет осуществлять циклический вывод положительных и отрицательных чисел в произвольном порядке.Формула и з о б р е т е н и я1. Устройство для упорядочения массива чисел, содержащее М-разрядный счетчик (где И - разрядность сортируемых чисел), блок памяти, мультиплексор, группу из И элементов И, первый элемент НЕ, причем входы модуля числа устройства подключены к информационным входам И-разрядного счетчика, выходы разрядов которого соединены с группой адресных входов138337блока памяти с первого по М-й и с соответствующими первыми входами элементов И группы, вторые входы которых соединены с выходом блока памяти, управляющий вход устройства соединен . с управляющим входом мультиплексора, выходы элементов И группы являются выходами устройства, о т л и ч а ю - щ е е с я тем, что, с целью расширения функциональных возможностей за счет упорядочения массивов чисел с учетом знака и повторения равных чисел при выводе, в него введены два Э-триггера, четыре элемента И, второй элемент НЕ, формирователь импульсов и дешифратор нуля, причем управляющий вход устройства соединен с входом выбора режима блока памяти и через первый элемент НЕ с первым вхо О дом первого элемента И, вход сброса блока памяти соединен с входом "Сброс" устройства, вход "Знак" устройства соединен с информационным входом первого триггера, вход зада ния режима сортировки устройства соединен с информационным входом второго триггера, вход "Запись" устройства соединен с первым входом элемента ИЛИ, выход которого .подключен к тактовым входам первого и второго Р-триггеров, к входу разрешения записи счетчика и первому информационному входу мультиплексора, вход блока памяти соединен с выходом мультиплексора, тактовый вход устройства соеди.нен с вторым входом первого элемента И, выход .которого соединен с пер- . вым входом второго и третьего элементов И и с вторым информационным вхо О дом мультиплексора, выход второго элемента И соединен с тактовым входом счетчика, вход выбора режима которого соединен с прямым выходом второго триггера, прямой выход первого .45 триггера подключен к (0+1)-му адресному входу блока памяти и первому входу четвертого элемента И, второй вход которого соединен с вторыми входами элементов И группы и через второй элемент НЕ с вторым входом второ 50 го элемента И, выходы разрядов счетчика соединены с соответствующими входами дешифратора нудя, выход которого соединен с входом формирователя импульсов и является управляющим выходом устройства, выход формирователя импульсов соединен с вторым входом элемента ИЛИ и с синхронизирую 36щим входом блока памяти, выход четвертого элемента И является выходом "Знак" устройства, выход третьего элемента И является синхронизирующим выходом устройства.2. Устройство по и.1, о т л и - ч а ю щ е е с я тем, что блок памяти содержит первую, вторую и третью группы элементов И по (М+1) элементов в каждой (где М - количество элементов массива чисел), группу из (М+1) ячеек памяти, преобразователь двоичного кода в позиционный, формирователь импульсов, элемент ИЛИ и элемент НЕ, причем адресные входы блока памяти подключены к входам преобразователя двоичного кода в позиционный, вход выбора режима блока памяти соединен с первыми входами элементов И .первой группы и через элемент НЕ с первыми входами элементов И второй и третьей групп и входом формирователя импульсов, тактовый вход блока памяти соединен с вторыми входами элементов И первой и второй групп, вторые входы -го элемента И третьей группы (где д = 1 М+1) соединен с выходом -й ячейки памяти, третьи входы элементов И всех трех групп соединены с соответствующими выходами преобразователя двоичного кода в позиционный, выход -х элементов И первой и второй групп подключены соответственно к суммирующему и вычитающему входам -й ячейки памяти, вход сброса блока памяти соединен с входами сброса всех ячеек памяти, первый синхровход каждой ячейки памяти соединен с синхронизирующими входами блока памяти, второй синхровход ячеек памяти соединен с выходом формирователя сигналов, выходы элементов И третьей группы соединены с входами элемента ИЛИ, выход которого является выходом блока памяти.. 3Устройство по пп. 1 и 2, о т - л и ч а ю щ е е с я тем, что ячейка памяти содержит реверсивный счетчик, регистр, дешифратор нуля, элемент И, причем суммирующий вход ячейки памяти соединен с суммирующим входом реверсивного счетчика, вход сброса ячейки памяти соединен с входом начальной установки реверсивного счетчика, первый синхровход ячейки памяти объединен с управляющим входом регистра, второй синхровход соединен с1.383336 1 О в порядке возрастания 000 в порядке убыва, ния 111 0 в порядке возрастания 11 1 0 0 в порядке убывания 000 0 входом разрешения записи реверсивного счетчика, вычитающий вход ячейкипамяти соединен с первым входом элемента И, выход которого соединен свычитающим входом реверсивного счетчика, выходы разрядов реверсивногосчетчика соединены с информационными Режим ввода Входы 4-1 Положительные числа Отрицательные числа входами регистра и входами дешифрато"ра нуля, выход которого соединен свторым входом элемента И и являетсявыходом ячейки памяти, выходы разрядов регистра подключены к соответствующим информационным входам реверсивного счетчика.- 4-И Вход 5 Вход 3138333 б оставитель В.Журавлевехред Л Олийнык орректор Г.Решет исное го комитета СССРний и открытий ушская наб., д. 4/ оизводственно-полиграфическое пред.едактор Л.Лангазо аказ 1297/47 ВНИИ и 3035, Тираж 704 Государственн делам изобрете осква, Ж, Р тие, г. Ужгород, ул. Проектна