Устройство для сортировки информации Советский патент 1985 года по МПК G06F7/06 

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

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

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

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

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

Устройство содержит счетчик 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 устройства поступает сигнал запуска (фиг.36), который

поступает на первый вход блока 5 и запускает своим задним фронтом генератор 17 тактовых импульсов. На выходах генератора 17 формируются последовательно непересекающиеся во времени импульсы ТИ1 на первом выходе

3

(фиг.Зв), ТИ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 конца цикла (фиг.Зи). Внешнее уст1эойство снимает сигнал режима очистка с входа 12 устройства.

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

6849 , 4

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

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

20 происходит перезапись содержимого счетчика 1 (кода сортируемого числа) по. такому же адресу в блок 2 памяти. В такте ТИ2 срабатывает элемент И 23, сигнал с выхода которого поступает на счетный вход счетчика , содержимым которого становится код 1. В такте ТИЗ срабатывает элемент И 24, сигнал с выхода, которого пос тупает на второй вход элемента ИЛИ

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

, памяти, номер которой задается кодом (самого сортируемого числа с выхода счетчика 1, записывается число.1, соответствующее количеству поступивших на вход устройства сортируемьгх

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

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

5 по адресу, равному коду сортируемого числа. Далее возможны две ситуации: код следующего сортируемого числа . равен коду предыдущего числа и вторая ситуация, когда коды их различны. В первом случае в счетчик 7 будет занесено число 1, поскольку при сортировке предыдущего числа по этому же адресу была занесена 1. Кроме того, сигналом в такте ТИ1 происходит перезапись содержимого основного счетчика 1 по адресу кода счетчика 1. В такте ТИ2 сигнал поступает на счет- ный вход счетчика 7, содержимым кото- ю рого становится двоичный код числа 2 , т.е.число поступивших равных чисел соответствующего кода. В такте ТИЗ сигнал поступает на вход управления записью во вспомогательный блок J5 6 памяти кода числа 2 с выхода счетчика 7. В ячейке блока 6 памяти, номер которой определяется кодом сор тируемого числа с выхода счетчика 1, запишется код числа 2, соответству щего в нашем случае количеству равны чисел, поступивших на вход 9 устройства. В случае неравенства сортируемых чисел в счетчик 7 в такте ТИ1 бу дет занесен нулевой код с выхода вспомогательного блока 6 памяти, а также код сортируемого числа - в блок 2 памяти по номеру ячейки, равный самому числу. В такте ТИ2 содержимое счетчика.7 увеличивается на 4-1. В такте ТИЗ происходит запись кода 1 с выхода счетчика 7 во вспомогательный блок 6 памяти по адресу, код которого равен самому числу. Таким образом, в режиме записи (сортировки) происходит за цикл выборка из вспомогательного блока 6 памяти кода количества ранее отсортированных равных чисел соответствующего кода и запись кода количества этих чисел в счетчик 7, увеличение его содержимого на +1 и запись полученного кода в эту же ячейку блока 6 памяти по адресу кода самого числа. Кроме того, сортируемое число записывается в блок 2 памяти по адресу кода самого числа. По окончании сортиррвки каждого из числа по концу сигнала запроса с выхода 15 устройства на вход 9 устройства может поступать следующее сортируемое число. По окончании сортировки последнего числа с входа 13 режима записи снимается единичный потенци-, ал. Режим чтения. В исходном состоянии счетчики 1 и 7 и триггер 27 обнулены. По входу 14 устройства 1196 496 поступает единичный потенциал (фиг.5а), а на входах 12 и 13 - нулевые потенциалы. На информационный вход 9 устройства поступает нулевой код. На вход 10 поступает сигнал запуска (фиг.56), по заднему фронту, которого и запускается генератор 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 не происходит. В такте ТИ2 на выходе элемента И 21 появится сигнал, который поступит на пятый выход блока 5 и на выход 11 устройства (фиг.5 ж). В такте ТИЗ срабатываеют элементы И 25 и 31. Сигнал с выхода элемента И 25 поступает на вычитающий вход счетчика 7, который изменит свое состояние на -1 и выставит на входах элемента ИЛИ 8 нулевой код, который и поступит на первый вход формирователя 18. Поскольку в такте ТИЗ сработал и элемен И 31, то по совпадению нулевого потенциала на первом входе формирователя 18 и единичного на выходе элемента И 31 через элемент запретаjc соответствующей задержкой запускается формирователь 18 (фиг. 5 к). Сигналом с выхода формирователя 18 триг гер 27 обнуляется,и разблокируется .элемент И 20. Кроме того, сигнал с формироёателя 18 поступает на первый вход элемента ИЛИ 32, сигнал с которого поступает на счетный вход счетчика 1, который увеличивает свое содержимое на +1. По заднему фронту () сигнала с выхода элемента И 31 запус кается .снова генератор 17. Таким образом, к началу следующего такта ТИ1 на выходе счетчика 1 выставится следующий адрес (код 1) на выходе блока 2 памяти - код ранее сортированного числа по зтому адресу, а на выходе счетчика 7 - код количеств

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

Для формирования убывающей последовательности массива чисел необходимо вначале режима чтения по входу 9 подать 1 во все разряды счетчика 1 и переключить счетчик 1 на вычитание. ства код числа поступает с выхода основного блока 2 памяти на внешнее устройство. Б такте ТИЗ содержимое счетчика 7 уменьшается на -1 по сигналу с выхода элемента И 25. Счетчик 7 обнуляется, элемент ИЛИ 8 выставляет нулевой потенциал, по которому и запускается формирователь 18, сигнал с которого поступает на счет-ный вход счетчика 1, а также триггер J27 возвращается в исходное нулевое ;состояние. На выходе счетчика 7 выс:тавится код следующего адреса сортируемых чисел. Бели же содержимое ячейки по этому адресу вспомогательного блока 6 памяти имело нулевой код, то в такте ТИ2 устройство не вьщает синхросигнала, поскольку на третий вход третьего элемента И 21 поступает нулевой потенциал (в такте ТИ в счетчик 7 занесен нулевой код). Таким образом, устройство не выдает синхросигнала перезаписи кода с выхода блока 2 памяти. В такте ТИЗ произойдет наращивание кода в счетчике 1 и возврат триггера 27 в исходное состояние. В итоге устройство обеспечивает упорядочение всего массива чисел с выдачей соответствующего количества импульсов синхронизации внешнему устройству, которое соответствует количеству равных чисел, поступивших на вход устройства в режиме записи, причем числа в режиме чтения поступают

1U

21

//

Jf/J

J

L4:

Q

10

/1 I

15

f.Z

Режим yanvcu