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

 

СОЮЗ СОВЕТСКИХ соцИАЛистических

РЕСПУБЛИК

09) (11) (594 С 06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ госудм ственный комитет сссР пО делАм изОБРетений и ОткРытий (21) 37? 1 7 1 8/24-24 (22) 13.07.84 (46) 07. 12.85 Бюл.й - 45 (72) А. Н.Мурашко, (53) 681.325.66(088.8) (56) Авторское свидетельство СССР

У 570050, кл. G 06 F 7/00, 1976.

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

Р 1073770, кл. G 06 F 7/06, 1982. (54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ИНФОРМАЦИИ, содержащее генератор тактовых импульсов, счетчик, блок памяти, элемент НЕ и группу элементов.

И, причем информационные входы устройства соединены с информационными входами счетчика, вход установки в нулевое состояние которого является входом начальной установки устройства, а выходы разрядов соединены с соответствующими адресными входами блока памяти и первыми входами соответствующих элементов И группы, выходы которых подключены к соответствующим информационным входам блока памяти, выходы которого являются выходами устройства, вход разрешения записи устройства соединен с синхровходом счетчика, о т л и ч а ю" щ е е с я тем, что, е целью расширения области применения устройства за счет возможности сортировки равных чисел, в него введены счетчик равных чисел, вспомогательнын блок . памяти, элемент ИЛИ и блок синхронизации, включающий формирователь импульсов, элементы И, ИЛИ и запрета и триггер, причем вход разрешения записи устройства соединен с первым входом запуска генератора импульсов, первый выход которого. соединен в блоке синхронизации с первыми входами первого, второго и третьего элементов И, второй выход генератора импульсов соединен с первыми входами четвертого и пятого элементов И, третий выход генератора тактовых импульсов подключен к первым входам шестого, седьмого, восьмого и девятого элементов И, вход режима чтения устройства соединен в блоке синхронизации с вторыми входами первого и четвертого элементов И, выход первого элемента И соединен с первым входом первого элемента ИЛИ и синхровходом триггера, информационный вход которого подключен к входу логической 3 единицы устройства, а инверсный и пря- уу . мой выходы — соответственно к третье- %УФ му входу первого элемента И и вторым С входам восьмого и девятого элементов

Ф

И, вход режима записи устройства под- Я ключен к вторым входам второго, пятого и седьмого элементов И, .вход режима очистки устройства подключен к вторым входам третьего и шестого элементов И, выход третьего элемента И подключен к первым входам второго и третьего элементов ИЛИ, выход второго элемента И подключен к вто рым входам первого и второго элементов ИЛИ, выход .девятого элемента И соединен с первым входом повторного запуска генератора тактовых импульсов и информационным входом элемента Д, Ь запрета, выход которого через формирователь импульса подключен к входу установки. в нулевое -состояние триггера и первому входу четвертого элемента ИЛИ, второй вход которого соединен с выходом шестого элемента И и вторым входом повторного запуска

1196849 генератора тактовых импульсов, выход первого элемента ИЛИ блока синхронизации соединен с синхровходом счетчика равных- чисел, выходы разрядов

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

Цель изобретения — расширение области применения за счет обеспечения сортировки равных чисел.

На фиг.1 приведена функциональная схема устройства; на фиг .2 — функцио" 10 нальная схема блока синхронизации; на фиг.3 — временная диаграмма работы блока синхронизации в режиме "очи-стка"; на фиг.4 — временная диаграмма работы блока синхронизации в ре- 1S жиме "запись"; на фиг.5 — временная диаграмма работы блока синхронизации в режиме "чтение".

Устройство содержит счетчик 1, блок 2 памяти, элемент НЕ 3, группу рр элементов И 4, блок 5 синхронизации, вспомогательный блок 6 памяти, счетчик 7 равных чисел, элемент ИЛИ 8, информационные входы 9 устройства, вход 10 разрешения записи устройства, выход 11 синхронизации устройства, вход 12 режима "очистка", вход 13 режима "запись", вход 14 режима "чтение", выход 15 запроса числа, выход

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

Блок 5 синхронизации содержит генератор 17 тактовых импульсов, формироваетль 18 импульсов, элементы И 1926, триггер 27, элементы ИЛИ 28-30, элемент И 31, элемент ИЛИ 32, элемент запрета 33.

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

Режим очистки, В исходном состоянии счетчики 1 и 7 и триггер 27 обнулены (цепи нулевых установок на чертежах не показаны). По входу 12 режима очистки поступает единичный потенциал (фиг.За), а по всем разрядам информационного входа 9 поступают нулевые потенциалы. Кроме того, сигналом нулевого потенциала с выхода элемента НЕ 3 блокируется поступление информации"с выхода счетчика 1 на информационные входы блока 2 памяти и на выходах элементов И 4 группы установятся потенциалы логического нуля. По входу 10 устройства поступает сигнал запуска (фиг.3б), который поступает на первый вход блока 5 и запускает своим задним фронтом генератор 17 тактовых импульсов. На выходах генератора 17 формируются последовательно непересекающиеся во времени импульсы ТИ1 на первом выходе

1196849 (фиг.Зв), ТИ2 на втором выходе (фиг.Зг) и ТИЗ на третьем выходе (фиг.Зд) . В такте ТИ1 срабатывает элемент И 19, сигнал с выхода которого поступает на первые входы элементов

ИЛИ 29 и 30. Сигнал с выхода элемента ИЛИ 29 поступает и далее на управляющий вход блока 2 памяти (фиг.Зж), . по которому происходит запись нулевого кода с выхода элементов И 4 по нулевому адресу ячейки, алрес которой определяется содержимым счетчика

1. Кроме того, в первом такте ТИ1 срабатывает элемент ИЛИ 30, с выхода которого сигнал поступает на вход управления вспомогательного блока

6 памяти, По этому сигналу происходит запись нулевого кода с выхода счетчика 7 (счетчик 7 обнулен) по нулевому адресу, задаваемому счетчиком 1 (фиг.3e). В третьем такте

ТИЗ срабатывает элемент И 26, сигнал с выхода которого поступает на второй вход четвертого элемента ИЛИ 32 и на второй вход генератора 17. Сиг- . нал с выхода элемента ИЛИ 32 поступает на счетный вход счетчика 1, содержимое которого увеличивается на

"1". По заднему фронту сигнала с выхода элемента И 26 снова запускается генератор 17, на выходах которого формируются такты .ТИ1, ТИ2 и ТИЗ.

Аналогично предыдущему происходит в такте ТИ1 запись нулевого кода в следующую ячейку блоков 2 и 6 памяти по первому адресу. В такте ТИЗ происходит наращивание адреса на "+1" в счетчике 1. Таким образом, далее происходит обнуление последующих ячеек блоков 2 и 6 памяти. После полного просчета счетчика 1 во всех ячейках блоков 2 и 6 памяти будет записан нулевой код. В конце режима

"очистка" на выходе переполнения счетчика 1 появится сигнал, который поступает. на выход 16 конца цикла (фиг.Зи). Внешнее устройство снимает сигнал режима "очистка" с входа

12 устройства.

Режим записи, В исходном состоянии счетчики 1 и 7 и триггер 27 обнулены. По входу 13 режима записи поступает единичный потенциал (фиг.4а). С выхода элемента HE 3 на входы элементов поступает единичный потенциал, разрешающий поступление информации с выхода счетчика 1 на информационные входы блока 2 памяти.

На информационный вход 9 устройства поступает сортируемое число, далее на вход 10 устройства поступает сигнал записи кода сортируемого числа в счетчик 1 (фиг.4б), а по заднему фронту этого сигнала запускается генератор 17 (фиг.4в,г,д). В первом такте ТИ1 срабартывает четвертый элемент И 22, сигнал с которого поступает на вторые входы элементов ИЛИ

28 и 29. Срабатывает первый элемент

ИЛИ 28. Срабатывает также второй элемент ИЛИ 29. По этим сигналам происходит запись в счетчик 7 содержимого ячейки вспомогательного блока 6 по адресу, который равен величи не сортируемого числа, а поскольку все ячейки содержат нулевой код после режима очистки, то счетчик 7 не изменит своего нулевого состояния происходит перезапись содержимого счетчика 1 (кода сортируемого числа) по, такому же адресу в блок 2 памяти.

В такте ТИ2 срабатывает элемент И

23, сигнал с выхода которого поступает на счетный вход счетчика 7, содержимым которого становится код

"1" ° В такте ТИЗ срабатывает элемент

И 24, сигнал с выхода. которого поступает на второй вход элемента ИЛИ

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

4О чисел с определенным кодом. По концу сигнала с выхода 15 происходит запрос следующего числа на сортировку. По готовности внешнее устройство выставляет код следующего числа на информа45 ционном входе 9 устройства. Далее на вход 10 устройства поступает сигнал (фиг.4б) записи сортируемого числа в счетчик 1, а цо заднему фронту сигнала запускается генератор 17

50 (фиг.4в,г,д). В первом такте ТИ1 аналогично предыдущему по сигналу с четвертого выхода 34 блока 5 происходит запись во счетчик 7 содержимого ячей,ки вспомогательного блока 6 памяти

55 по адресу, равному коду сортируемого числа. Далее возможны две ситуации: код следующего сортируемого числа равен коду предыдущего числа и вторая

1196

S ситуация, когда коды их различны.

В первом случае в счетчик 7 будет занесено число "1", поскольку при сортировке предыдущего числа по этому же адресу была занесена "1". Кроме того, сигналом в такте ТИ1 происходит перезапись содержимого основного счетчика 1 по адресу кода счетчика 1.

В такте ТИ2 сигнал поступает на счет-: ный вход счетчика 7, содержимым кото- 1р рого становится двоичный код числа ."2", т.е.число. поступивших равных чисел соответствующего кода. В такте

ТИЗ сигнал поступает на вход управления записью во вспомогательный блок 1

6 памяти кода числа "2" с выхода счетчика 7. В ячейке блока 6 памяти, Э номер которой определяется кодом сортируемого числа с выхода счетчика 1, запишется код числа "2", соответствую- р щего в нашем случае количеству равных. чисел, поступивших на вход 9 устрой- ства. В случае неравенства сортируемых чисел в счетчик 7 в.такте ТИ1 бу" дет занесен нулевой код с выхода 25 вспомогательного блока 6 памяти, а также код сортируемого числа — в блок 2 памяти по номеру ячейки, равный самому числу. В такте ТИ2 содержимое счетчика.7 увеличивается íà gp

"+1". В такте ТИЗ происходит запись кода "1" с выхода счетчика 7 во вспомогательный блок 6 памяти по адресу, код которого равен самому числу. Таким образом, в режиме запи35 си (сортировки) происходит за цикл выборка из вспомогательного блока 6 памяти кода количества ранее отсортированных равных чисел соответствующего кода и запись кода количества этих чисел в счетчик 7, увеличение его содержимого на "+1" и запись полученного кода в эту же ячейку блока 6 памяти по адресу кода самого числа. Кроме. того, сортируемое чис- 4 ло записывается в блок 2 памяти по адресу кода самого числа. По окончании сортировки каждого из числа по концу сигнала запроса с выхода

15 устройства на вход 9 устройства может поступать следующее сортируемое число. По окончании сортировки последнего числа с входа 13 режима записи снимается единичный потенци-, BJI °

Режим чтения. В исходном состоянии счетчики 1 и 7 и триггер 27 обнулены, По входу 14 устройства

849 6 поступает единичный потенциал (фиг.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 не происходит.

7 11

В такте ТИ2 на выходе элемента И 21 .появится сигнал, который поступит на пятый выход блока 5 и на выход

11 устройства (фиг.5 ж). В такте

ТИЗ срабатываеют элементы И 25 и 31.

Сигнал с выхода элемента И 25 поступает на вычитающий вход счетчика

7, который изменит свое состояние на "-1" и выставит на входах элемента

ИЛИ 8 нулевой код, который и поступит на первый вход формирователя 18..Поскольку в такте ТИЗ сработал и элемент

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

:элемент И 20.

Кроме того, сигнал с формироЬате-. ля 18 поступает на первый вход элемента ИЛИ 32, сигнал с которого поступает на счетный вход счетчика 1, который увеличивает свое содержимое на +1 . По заднему фронту (1 -"0 ) сигнала. с выхода элемента И 31 запускается, снова генератор 17. Таким образом, к началу следующего такта

ТИ1 на выходе счетчика 1 выставится . следующий адрес (код "1") на выходе блока 2 памяти - код ранее сортированного числа по этому адресу, а на выходе счетчика 7 - код количества отсортированных равных чисел, например и = 1. Аналогично предыдущему в такте ТИ1 произойдет запись содержимого следующей по адресу (код "1") ячейки вспомогательного блока 6 памяти в счетчик 7 и устанавливается триггер 27 в "1". В такте ТИ2 по синхросигналу на выходе 11 устрой"

96849, 8 ства код числа поступает с выхода основного блока 2 памяти на внешнее устройство. В такте ТИЗ содержимое счетчика 7 уменьшается на "-1" по

5 сигналу с выхода элемента И 25. Счетчик 7 обнуляется, элемент ИЛИ 8 выставляет нулевой потенциал, по которому и запускается формирователь 18, сигнал с которого поступает на счет10:ный вход счетчика 1, а также триггер

; 27 возвращается в исходное нулевое ! состояние. На выходе счетчика 7 выс.тавится код следующего адреса сортируемых чисел. Если же содержимое

15 ячейки по этому адресу вспомогательного блока 6 памяти имело нулевой код, то в такте ТИ2 устройство не выдает синхросигнала, поскольку на .третий вход третьего элемента И 21

20,поступает нулевой потенциал (в такте ТИ1 в счетчик 7. занесен нулевой код). Таким образом, устройство не выдает синхросигнала перезаписи кода с выхода блока 2 памяти. В такте ТИЗ произойдет наращивание кода в счетчике 1 и возврат триггера 27 в исходное состояние. В итоге устройство обеспечивает упорядочение всего массива чисел с выдачей соот30 ветствующего количества импульсов синхронизации внешнему устройству, которое соответствует количеству равных чисел, поступивших на вход устройства в режиме записи, причем

35 числа в режиме чтения поступают в порядке возрастания их величины.

Для формирования убывающей последовательности массива чисел необходимо вначале режима чтения по входу 9 подать "1" во все разряды счетчика 1 и переключить счетчик 1 на вычитание.

1196849

1196849 а

&од g

У дюж Ю8

1-юй Й. Юд CCA ри 17 . c

7-й ЫИ мю-,а n

Ф J-й Даф с

Р-й 8ainaP

БУХ

ыь г

ЮУХ э

Яйца

ЖХ и дачи/ Ю

Рсжим жлиси

1196849

Режим vme uc а ЬоУ 14

3 Woo 10

8 1-й8ыю вел-ра 1 з Р-ййип .в -ра 1

Ю -u 8bixo ев-ра е 4-йХы

EM .. ж Х-й Рыло

ЮХ з 7-ййаю

ЫХ и ITp. Йж трие гера

Z7 к ЬааУ ро нир. Ф Р-и ЮМа

РУХ

Составитель Е.Иванова

Редактор С.Патрушева ТехредЛ.Мартяшова Корректор С.Черни

Заказ 7564/47 . Тираж 709 Подписное

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

113035, Москва, Ж-35, Рауяская наб., д. 4/5

Филиал ППП "Патент", г.ужгород, ул.Проектная, 4