Устройство для сортировки информации

союз советскихсоцИАлистическихРЕСПУБЛИК 09) (11) о 4 Со госудАРственный комитет сссР по делАм изОБРетений и ОтнРыти АНИЕ И ЗОБРЕТЕНИЯ О У СВИД ВТОР льство СССР /00, 1976. ство СССР 7/06, 1982.(54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦИИ, содержащее генератор тактовых импульсов, счетчик, блок памяти, элемент НЕ и группу элементов. И, причем информационные входы устройства соединены с информационными входами счетчика, вход установки в нулевое состояние которого является входом начальной установки устройства, а выходы разрядов соединены с соответствующими адресными входами блока памяти и первыми входами соответствующих элементов И группы, выходы которых подключены к соответствующим информационным входам блока памяти, выходы которого являются выходами устройства, вход разрешения записи устройства соединен с синхровходом счетчика, о т л и ч а ю" щ е е с я тем, что, е целью расширения области применения устройства за счет возможности сортировки равных чисел, в него введены счетчик равных чисел, вспомогательный блок . памяти, элемент ИЛИ и блок синхронизации, включающий формирователь импульсов, элементы И, ИЛИ и запрета и триггер, причем вход разрешения записи устройства соединен с первым входом запуска генератора импульсов, первый выход которого соединен в б ло(21) 37 1718/24-24(56) Авторское свидетеУ 570050, кл, С 06 Г 7Авторское свидетельУ 1073770, кл, С 06 Р ке синхронизации с первыми входамипервого, второго и третьего элементов И, второй выход генератора импульсов соединен с первыми входами четвертого и пятого элементов И, третий выход генератора тактовых импульсов подключен к первым входам шестого, седьмого, восьмого и девятогоэлементов И, вход режима чтения устройства соединен в блоке синхронизации с вторыми входами первого и четвертого элементов И, выход первогоэлемента И соединен с первым входомпервого элемента ИЛИ и синхровходом триггера, информационныи вход которого подключен к входу логическойединицы устройства, а инверсный и прямой выходы - соответственно к третьему входу первого элемента И и вторымвходам восьмого и девятого элементовИ, вход режима записи устройства подключен к вторым входам второго, пятого и седьмого элементов И, входрежима очистки устройства подключенк вторым входам третьего и шестогоэлементов И, выход третьего элемента И подключен к первым входам второго и третьего элементов ИЛИ, выходвторого элемента И подключен к вторым входам первого и второго элементов ИЛИ, выход .девятого элемента Исоединен с первым входом повторногозапуска генератора тактовых импульсов и информационным входом элементазапрета, выход которого через форми"рователь импульса подключен к входуустановки в нулевое состояние триггера и первому входу четвертого элемента ИЛИ, второй вход которого соединен с выходом шестого элемента И ивторым входом повторного запуска1196849 генератора тактовых импульсов, выходпервого элемента ИЛИ блока синхронизации соединен с синхровходом счетчика равных чисел, выходы разрядовкоторого: соединены с информационнымивходами вспомогательного блока памяти и входами элемента ИЛИ, выход которого соединен с управляющим входом элемента запрета в блоке синхронизации и третьими входами четвертогои восьмого элементов И, выход четвертого элемента И является выходомсинхронизации устройства, выход второго элемента ИЛИ блока синхронизации соединен с входом записи-считывания блока памяти, выход пятого элемента И блока. синхронизации подключен к входу сложения счетчика равных чисел, вход установки в нулевоесостояние которого подключен к входу начальной установки устройства,Изобретение относится к вычислительной технике и может быть использовано в системах обработки информацииеЦель изобретения - расширение области применения за счет обеспечения сортировки равных чисел. На фиг.1 приведена функциональная схема устройства; на фиг.2 - функцио" 1 Ональная схема блока синхронизации;на фиг.З - временная диаграмма работы блока синхронизации в режиме "очистка"; на фиг.4 - временная диаграмма работы блока синхронизации в режиме "запись"; на фиг.5 - временнаядиаграмма работы блока синхронизациив режиме "чтение".Устройство содержит счетчик 1,блок 2 памяти, элемент НЕ 3, группу 2 рэлементов И 4, блок 5 синхронизации,вспомогательный блок 6 памяти, счетчик 7 равных чисел, элемент ИЛИ 8,информационные входы 9 устройства,вход 10 разрешения записи устройства, 25 выход 11 синхронизации устройства,вход 12 режима "очистка", вход 13режима "запись", вход 14 режима "чтение", выход 15 запроса числа, выход16 конца цикла. вход вычитания соединен с выходомвосьмого элемента И блока синхронизации; а информационные входы счетчика равных чисел соединены с соответствующими выходами вспомогательного блока памяти, адресные входыкоторого подключены к выходам соответствующих разрядов счетчика, счетный вход которого соединен с выходомчетвертого элемента ИЛИ блока синхронизации, второй вход которогосоединен в блоке синхронизации с выходом седьмого элемента И и является выходом запроса числа устройства,выход третьего элемента И блока синхронизации соединен с входом записи-считывания вспомогательного блокапамяти, вторые входы элементов Игруппы подключены через элемент НЕк входу режима очистки устройстваБлок 5 синхронизации содержит гене. ратор 17 тактовых импульсов, формироваетль 18 импульсов, элементы И 19- 26, триггер 27, элементы ИЛИ 28-30, элемент И 31, элемент ИЛИ 32, элемент запрета 33.Устройство работает следующим образом.Режим очистки, В исходном состоянии счетчики 1 и 7 и триггер 27 обнулены (цепи нулевых установок на чертежах не показаны). По входу 12 режима очистки поступает единичный потенциал (фиг.За), а по всем разрядам информационного входа 9 поступают нулевые потенциалы. Кроме того, сигналом нулевого потенциалас выхода элемента НЕ 3 блокируется поступление информации"с выхода счетчика 1 на информационные входы блока 2 памяти и на выходах элементов И 4 группы установятся потенциалы логического нуля. По входу 10 устройства поступает сигнал запуска (фиг.Зб), который поступает на первый вход блока 5 и запускает своим задним фронтом генератор 17 тактовых импульсов, На выходах генератора 17 формируются последовательно непересекающиеся во времени импульсы ТИ 1 на первом выходе(фиг.Зв), ТИ 2 на втором выходе (фиг.Зг) и ТИЗ на третьем выходе (фиг.Зд), В такте ТИ 1 срабатывает элемент И 19, сигнал с выхода которого поступает на первые входы элементов ИЛИ 29 и 30. Сигнал с выхода элемента ИЛИ 29 поступает и далее на управляющий вход блока 2 памяти (фиг.Зж), . по которому происходит запись нулевого кода с выхода элементов И 4 по нулевому адресу ячейки, алрес которой определяется содержимым счетчика 1. Кроме того, в первом такте ТИ 1 срабатывает элемент ИЛИ 30, с выхода которого сигнал поступает на вход управления вспомогательного блока 6 памяти, По этому сигналу происходит запись нулевого кода с выхода счетчика 7 (счетчик 7 обнулен) по нулевому адресу, задаваемому счетчиком 1 (фиг.Зе). В третьем такте ТИЗ срабатывает элемент И 26, сигнал с выхода которого поступает на второй вход четвертого элемента ИЛИ 32 и на второй вход генератора 17. Сиг-. нал с выхода элемента ИЛИ 32 поступает на счетный вход счетчика 1, содержимое которого увеличивается на "1". По заднему фронту сигнала с выхода элемента И 26 снова запускается генератор 17, на выходах которого формируются такты .ТИ 1, ТИ 2 и ТИЗ. Аналогично предыдущему происходит в такте ТИ 1 запись нулевого кода в следующую ячейку блоков 2 и 6 памяти по первому адресу, В такте ТИЗ происходит наращивание адреса на "+1" в счетчике 1. Таким образом, далее происходит обнуление последующих ячеек блоков 2 и 6 памяти. После полного просчета счетчика 1 во всех ячейках блоков 2 и 6 памяти будет записан нулевой код. В конце режима "очистка" на выходе переполнения счетчика 1 появится сигнал, который поступает. на выход 16 конца цикла (фиг.Зи). Внешнее устройство снимает сигнал режима "очистка 11 с входа 12 устройства.Режим записи, В исходном состоянии счетчики 1 и 7 и триггер 27 обнулены. По входу 13 режима записи поступает единичный потенциал (фиг,4 а). С выхода элемента НЕ 3 на входы элементов поступает единичный потенциал, разрешающий поступление информации с выхода счетчика 1 на информационные входы блока 2 памяти, На информационный вход 9 устройства поступает сортируемое число, далеена вход 10 устройства поступает сигнал записи кода сортируемого числав счетчик 1 (фиг,4 б), а по заднемуфронту этого сигнала запускаетсягенератор 17 (фиг.4 в,г,д). В первомтакте ТИ 1 срабартывает четвертый элемент И 22, сигнал с которого поступает на вторые входы элементов ИЛИ28 и 29. Срабатывает первый элементИЛИ 28, Срабатывает также второйэлемент ИЛИ 29. По этим сигналампроисходит запись в счетчик 7 содержимого ячейки вспомогательного бло ка 6 по адресу, который равен величине сортируемого числа, а посколькувсе ячейки содержат нулевой кодпосле режима очистки, то счетчикне изменит своего нулевого состояния 2 О происходит перезапись содержимогосчетчика 1 (кода сортируемого числа)по, такому же адресу в блок 2 памяти,В такте ТИ 2 срабатывает элемент И23, сигнал с выхода которого поступает на счетный вход счетчика 7, содержимым которого становится код"1"В такте ТИЗ срабатывает элементИ 24, сигнал с выхода. которого поступает на второй вход элемента ИЛИ30. Срабатывает элемент ИЛИ 30, сигнал с выхода которого поступает навход управления записью во вспомогательный блок 6 памяти информации свыхода счетчика 7. В ячейке блока 6памяти, номер которой задается кодомсамого сортируемого числа с выходасчетчика 1, записывается число " 1",соответствующее количеству поступивших на вход устройства сортируемых 40 чисел с определенным кодом. По концусигнала с выхода 15 происходит запросследующего числа на сортировку. Поготовности внешнее устройство выставляет код следующего числа на информа ционном входе 9 устройства. Далеена вход 10 устройства поступает сигнал (фиг.4 б) записи сортируемого числа в счетчик 1, а по заднему фронтусигнала запускается генератор 17 50 (фиг.4 в,г,д). В первом такте ТИ 1 аналогично предыдущему по сигналу с четвертого выхода 34 блока 5 происходитзапись во счетчик 7 содержимого ячейки вспомогательного блока 6 памяти 5555 по адресу, равному коду сортируемогочисла. Далее возможны две ситуации:код следующего сортируемого числаравен коду предыдущего числа и вторая11963ситуация, когда коды их различны.В первом случае в счетчик 7 будет занесено число "1", поскольку при сортировке предыдущего числа по это" му же адресу была занесена 1. Кроме того, сигналом в такте ТИ 1 происходит перезапись содержимого основного счетчика 1 по адресу кода счетчика 1. В. такте ТИ 2 сигнал поступает на счет-: ный вход счетчика 7, содержимым кото рого становится двоичный код числа ."2", т.е.число. поступивших равных чисел соответствующего кода. В такте ТИЗ сигнал поступает на вход управления записью во вспомогательный блок 1 6 памяти кода числа "2" с выхода счетчика 7. В ячейке блока 6 памяти,Эномер которой определяется кодом сортируемого числа с выхода счетчика 1, запишется код числа "2, соответствующего в нашем случае количеству равных чисел, поступивших на вход 9 устрой- ства. В случае неравенства сортируемых чисел в счетчик 7 в.такте ТИ 1 бу" дет занесен нулевой код с выхода 25 вспомогательного блока 6 памяти, а также код сортируемого числа - в блок 2 памяти по номеру ячейки, равный самому числу. В такте ТИ 2 содержимое счетчика.7 увеличивается наз 0 "+1". В такте ТИЗ происходит запись кода "1" с выхода счетчика 7 вовспомогательный блок 6 памяти по адресу, код которого равен самому числу. Таким образом, в режиме запи 35 си (сортировки) происходит за цикл выборка из вспомогательного блока 6 памяти кода количества ранее отсор" тированных равных чисел соответствующего кода и запись кода количества этих чисел в счетчик 7, увеличение его содержимого на "+1" и запись полученного кода в эту же ячейку блока 6 памяти по адресу кода самого числа, Кроме.того 1 сортируемое чис ло записывается в блок 2 памяти по адресу кода самого числа. По окончании сортировки каждого из числа по концу сигнала запроса с выхода 15 устройства на вход 9 устройства может поступать следующее сортируемое число. По окончании сортировки последнего числа с входа 13 режима записи снимается единичный потенци-, але55Режим чтения. В исходном состоянии счетчики 1 и 7 и триггер 27 обнулены, По входу 14 устройства 849 Ьпоступает единичный потенциал(фиг.5 а), а на входах 12 и 13 - нулевые потенциалы. На информационныйвход 9 устройства поступает нулевойкод. На вход 10 поступает сигналзапуска (фиг.5 б), по заднему фронту.которого и запускается генератор17 (фиг.5 в, г, д). В такте ТИ 1 срабатывает элемент И 20 и сигнал сего выхода поступает на первый входэлемента ИЛИ 28 и на вход синхронизации триггера 27. Срабатывает элемент ИЛИ 28, и сигнал. с его выходапоступает на вход синхронизации счет"чика 7, По переднему фронту сигналапроисходит перезапись содержимогоячейки счетчика 7 по нулевому адресузадаваемому счетчиком 1. Если ранеев режиме записи количество сортируемых чисел с нулевым кодом отличноот нуля, то в счетчике 7 будет занесен код количества этих равных чиселнулевого кода. По заднему фронту сигнала с выхода элемента И 20 триггер27 установится в единичное состояниепричем сигналом с инверсного выходатриггера блокируется по третьемувходу элемент И 20 а с прямого выхода триггера 27 единичный потенци"ал поступает на первые входы элементов И 25 и 31(фиг.5 и). При ненулевокоде в счетчике 7 на выходе элементаИЛИ 8 единичный потенциал. Во второмтакте ТИ 2 срабатывает элемент И 21и сигнал с его выхода поступаетдалее на выход синхронизации устройства. По этому сигналу внешнее устройство производит съем информациис выхода блока 2 памяти. В тактеТИЗ срабатывают элементы И 25 и 31.Сигнал с выхода седьмого элементаИ 25 поступает на вычитающий входсчетчика 7, который изменяет запи"санный ранее код с ячейки вспомогательного блока 6 памяти на "-1".Если в счетчике 7 записано числои2, то после одного вычитающегоимпульса содержимое счетчика 7 будетотличным от нуля и на выходе элемента ИЛИ 8 останется единичный потенциал. По концу, сигнала в такте ТИЗ с выхода элемента И 31 снова запуска" ется генератор 17 по третьему входу. Поскольку второй элемент И 20 заблокирован сигналом с выхода триггера 27, то в первом такте ТИ 1 выработки сигналов в блоке 5 не происходит.96849 , 8ства код числа поступает с выходаосновного блока 2 памяти на внешнееустройство. В такте ТИЗ содержимоесчетчика 7 уменьшается на "-1" по 5 сигналу с выхода элемента И 25. Счетчик 7 обнуляется, элемент ИЛИ 8 выставляет нулевой потенциал, по которому и запускается формирователь 18,сигнал с которого поступает на счет О:ный вход счетчика 1, а также триггер;состояние. На выходе счетчика 7 выс.тавится код следующего адреса сортируемых чисел. Если же содержимое 15 ячейки по этому адресу вспомогательного блока б памяти имело нулевойкод, то в такте ТИ 2 устройство невыдает синхросигнала, поскольку на.третий вход третьего элемента И 21 20 ,поступает нулевой потенциал (в такте ТИ 1 в счетчик 7. занесен нулевойкод). Таким образом, устройство невыдает синхросигнала перезаписикода с выхода блока 2 памяти. В так:те ТИЗ произойдет наращивание кодав счетчике 1 и возврат триггера 27в исходное состояние. В итоге устройство обеспечивает упорядочениевсего массива чисел с выдачей соот ветствующего количества импульсовсинхронизации внешнему устройству,которое соответствует количествуравных чисел, поступивших на входустройства в режиме записи, причемчисла в режиме чтения поступаютв порядке возрастания их величины.Для формирования убывающей последовательности массива чисел необходимо вначале режима чтения по входу 9 подать "1" во все разряды счетчика 1 и переключить счетчик 1 на вычитание.196849адюУ 1 РЬй АРЛЮ ИЮ ра 17й Аад бУ;Фс дмюР Ю