Устройство для сортировки -разрядных чисел

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНРЕСПУБЛИН А 06 Г 70 фЖТОЗНу ОПИСАНИЕ ИЗОБРЕТЕНИЯН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) УСТРОЙСТВО ДЛЯРЯДНЫХ ЧИСЕЛ(57) Изобретениетике и вычислителизобретения - расшных возможностейвозможности сортир СОРТИРОВКИ носится к авой технике.рение функцисчет обеспе ома ель ени ассивов ов о ОСУДАРСТВЕННЫЙ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ держащих равные числа, Устройство содержит два счетчика, блок памяти, генератор импульсов, коммутатор, триггер, группу элементов И, элементыИЛИ, И, НЕ, элементы запрета и элементы задержки. При поступлении очередного числа а, 1 с=1,2 Л, К - количество сортируемых чисел, иэ срртируемого массива из блока памяти считывается число Ь , записанное в немпо адресу а, увеличивается на единицуи вновь записывается по тому же адресу.Затем из блока памяти считываютсязаписанные там числа в порядке возрастания адресов, при этом обеспечивается выдача на выходы устройства текущего адреса считываемого числа аЬак раз. 1 ил, 12987Изобретение относится к автоматикеи вычислительной технике и может бытьиспользовано в системах обработки инФормации.Цель изобретения - расширение Функциональных возможностей за .счет обеспечения возможности сортировки массивов, содержащих равные числаНа чертеже представлена схема устройства, 10Устройство содержит генератор 1импульсов, счетчик 2, блок 3 памяти,коммутатор 4, элемент НЕ.5,. группу 6элементов И, реверсивный счетчик 7,триггер 8, элементы ИЛИ 9 - 11, элемент И 12, элементы 13 - 15 запрета,элементы 16 - 19 задержки, информационные входы 20, вход 21 разрешениязайиси, вход 22 начальной установкиустройства, тактовый вход 23, вход 2024 задания режима сортировки, вход25 задания режима считывания, выходы 26,Устройство работает следующим образом.25ФВ режиме очистки памяти на вход22 начальной установки устройства подается импульс, устанавливающий счетчики 2 и 7 в нулевое состоянн; наадресных и информационных входах бло- ЗОка 3 памяти устанавливаются нулевыепотенциалы. Затем на входе 21 разрешения записи устанавливается логический нуль, чем запрещается запись всчетчик 2 по входам 20. При установке 35на входах 24 и 25 нулевых потенциаловна первом и втором управляющих входахкоммутатора 4 - нулевые потенциалы, врезультате чего к выходу коммутатора4 подключается.его информационный 40вход, соединенный с генератором 1импульсов. После этого запускаетсягенератор 1 импульсов, который послевыдачи на суммирующий вход счетчика2. пачки из 2 (ш - количество разрядов сортируемь:х чисел) импульсов переполнения со счетчика 2 остановится.Одновременно на вход управления (запись/считывание) блока 3 памятичерез коммутатор 4 и элемент НЕ 5 по= 50ступает та же инвертированная пачкаимпульсов записи. После полного просчета счетчика 2 во всех ячейках блока 3 памяти записан нулевой код. В режиме сортировки на входе 21 разрешения записи устанавливается единичный потенциал, при этом разрешается запись в счетчик 2 по информа 38 2ционным входам 20. На вход 24 заданиярежима сортировки подается единичныйпотенциал, а на входе 25 сохраняетсянулевой потенциал, что обеспечиваетподключение к выходу коммутатора 4его информационного входа, которыйсоединен с выходом элемента 18 задержки, Сортируемая последовательностьиз Иш-разрядных двоичных чисел поступает на входы 20 записывается всчетчик 2 и с его выходов поступаетна адресные входы блока 3 памяти.Синхронно с каждым числом на вход 23устройства подается тактовый импульс,который переводит триггер 8, первоначально установленный в нуль, в единичное состояние. При этом на первомуправляющем входе коммутатора, подключенном к выходу элемента 13 запрета, устанавливается нулевой потенциал, а единичный сигнал с выхода триггера через элемент ИЛИ 9 поступаетна второй управляющий вход коммутатора 4, что определяет состояние коммутатора, обеспечивающее режим считывания из блока 3 памяти,Одновременно единичный потенциалс выхода триггера 8 поступает черезэлемент ИЛИ 10 на вход разрешения записи счетчика 7. Число из блока 3 памяти, находящееся по адресу, опреде 1 ляемому содержимым счетчика 2, переписывается в счетчик 7, Тот же тактовый импульс, задержанный элементом16 задержки, :возвращает триггер 8 внулевое состояние, что приводит кустановке на первом и втором управляющих входах коммутатора 4 единичногои нулевого потенциалов соответственно. Затем тот же гактовый импульс,задержанный элементом 1 задержки,поступает на суммирующий вход счетчика 7 и увеличивает его содержимое наединицу. После этого тот же тактовыйимпульс, пройдя через элемент 8 задержки, поступает на второй информационный вход коммутатора 4, что приустановленной комбинации на управляющих .входах коммутатора 4 обеспечивает запись в блок 3 памяти содержимогосчетчика 7 по адресу, равному. величине числа, поступившего на входы 20устройства, При поступлении последующих чисел на входы 20 устройство работает аналогично. В результате обработки всей последовательности сортируемых чисел в блоке 3 памяти по адресам, равным по 3 12987 ступившим в устройство числам, будет записано количество данных чисел в сортируемом массиве. Например, если в сортируемом массиве число 5 встречается дважды, то в блоке 3 памяти по адресу, равному 5, будет записано число 2.В режиме считывания на вход 21 разрешения записи подается нулевой потенциал, на входы 24 и 25 - нулевой 10 и единичный потенциалы соответственно. При этом на выходе коммутатора 4 устанавливается нулевой потенциал, а на входе управления блока 3 памяти - потенциал логической единицы, что за дает режим считывания информации из блока памяти. На вход 22 начальной установки подается импульс, устанавливающий счетчики 2 и 7 в нулевое состояние; на адресных и информационных 20 входах блока 3 памяти устанавливаются нулевые потенциалы. Единичный потенциал с входа 25 устройства через открытый элемент 14 запрета и элемент ИЛИ 1 О разрешает запись в счетчик 7. 25 Затем запускается генератор 1 импульсов, останов которого происходит приь переполнении счетчика 2.Очередной импульс с генератора 1 через элемент 15 запрета поступает 30 на суммирующий вход счетчика 2, увеличивая его содержимое на единицу. Этот же импульс через коммутатор 4 и элемент НЕ 5 поступает на управляющий вход блока 3 памяти. При этом число, 35 хранящееся в блоке 3 памяти, по адресу, установленному в счетчике 2, считывается в счетчик 7. Если в счетчик 7 считано число О, то на выходе элемента ИЛИ 11 сохранится нулевой 40 потенциал, и элементы 14 и 15 запрета останутся открытыми, а элемент И 12 - закрытым, следовательно, на выходы 26 устройства число с выходов счетчика 2 не поступит. Если в счетчик 7 считано 45 число, отличное от нуля, то на выходе элемента ИЛИ 11 появится единичный потенциал, который откроет элемент И 12 и закроет элементы 14 и 15 запрета. При этом снимается сигнал разре щения записи со счетчика 7 и блокируется суммирующий вход счетчика 2,Этот же импульс с генератора 1,задержанный элементом 19 задержки, через элемент И 12 поступает на вто.рые входыэлементов И группы 6; при этом значение очередного отсортированного числа с выходов счетчика 2 38 4подается на выходы 26 устройства, Одновременно содержимое счетчика 7 уменьшается на единицу. Если после этого содержимое счетчика не равно нулю, то сигналы на выходах элементов 14 и 15 запрета и элемента И 12 не изменятся и следующий импульс с генератора 1 через элемент 19 задержки и элемент И 12 вычтет из содержимого счетчика 7 единицу и откроет группу 6 элементов И, что обеспечит повторную выдачу этого же числа. Этот цикл будет повторяться до обнуления счетчика 7, после чего элемент И 12 закроется, а элементы 14 и 15 запрета откроются, Следующий импульс с генератора 1 увеличит содержимое счетчика 2 на единицу, и дальнейшая работа устройства в режиме считывания будет происходить аналогично. После перебора всех возможных значений счетчика на выходы устройства будет выдана упорядоченная по возрастанию последовательность чисел.Если перед считыванием во все разряды счетчика 2 записать единичные значения и переключить счетчик 2 на вычитание, то при считывании на выходах 26 получим последовательность чисел, отсортированную в порядке убывания.Формула изобретенияУстройство для сортировки ш-разрядных чисел, содержащее генератор импульсов, коммутатор, счетчик, блок памяти, группу из ш элементов И и элемент НЕ, причем выход генератора импульсов соединен с первым информационным входом коммутатора выход которого через элемент НЕ соединен с входом запись/считывание блока памяти, вход начальной установкч устройства соединен с входом установки счетчика в нулевое состояние, вход -го разряда сортируемых чисел устройства, где =1,2. т, т - разрядность сортируемых чисел, соединен с -м информационным входом счетчика, выход 1 -го разряда которого соединен с -м адресным входом блока памяти и с первым входом -го элемента И группы, выход которого является 1-м инФормационным выходом устройства, вторые входы всех элементов И группы объединены, вход разрешения записи счетчика является входом разрешения записи устройств,12987 Составитель В.Горохедактор К.Егорова Техред М.Ходанич К ктор С.Шекмар аказ 8 О/5 1 ВНИИПИ Государс по делам изоб 113035, Москва, ираж 673го комитета СССй и открытийРаушская наб писное ен ете-3 оизводственно-полиграфическое предприятие, г. Ужгород, ул, Проектн о т л и ч а ю щ е е с я тем, что,с целью расширения функциональных возможностей за счет обеспечения возможности сортировки массивов, содержащихравные числа, в него введены реверсивный счетчик, триггер, три элемента ИЛИ, элемент И, три элемента запрета и четыре элемента задержки, причем тактовый вход устройства соединенс входом установки триггера в единичное состояние и с входом первого элемента задержки, выход которого соединен с входом установки триггера в нулевое состояние и входомвторогоэлемента задержки, выход .которого со единен с суммирующим входом реверсивного счетчика и, через третий элементзадержки, с вторым информационнымвходом коммутатора, первый управляющий вход которого подключен к выходу 20первого элемента запрета, прямой входкоторого является входом задания режима сортировки устройства, вход задания режима считывания устройствасоединен с первым входом первого элемента ИЛИ и прямым входом второгоэлемента запрета, выход которого сое-динен с первым входом второго элемента ИЛИ, выход которого соединен свходом разрешения записи реверсивного 30счетчика, выход 3-го разряда которого(где=1, 2,1 ор Ж , И - количе 38 6ство сортируемых чисел в массиве, 1 х - ближайшее целое, не меньшее х)юсоединен с 3-м входом третьего элемента ИЛИ и с 3-м информационным входом блока памяти, выход 3-го разряда которого соединен с 1-м информационным входом 3-го разряда реверсивногоасчетчика, вычитающий вход которого подключен к вторйм входам элементов И группы и к выходу элемента И, первый вход которого подключен к выходу третьего элемента ИЛИ и к инверснымвходам второго и третьего элементовзапрета, выход третьего элемента запрета соединен с суммирующим входомсчетчика, прямой выход триггера соединен с инверсным входом первого элемента запрета, вторыми входами первого и второго элементов ИЛИ, выходпервого элемента ИЛИ соединен с вторым управляющим уходом коммутатора,выход генератора импульсов соединенс прямым входом третьего элемента запрета и, через четвертый элемент задержки, с вторым входом элемента И,вход установки в нулевое состояниереверсивного счетчика подключен квходу начальной установки устройства,выход переполнения счетчика соединенс входом останова генератора импульсов.