Устройство для сортировки двоичных чисел Советский патент 1987 года по МПК G06F7/06 

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

Цель изобретения - упрощение устройства.

На чертеже приведена функциональная схема устройства.

Устройство содержит счетчики h -1„ (п - число сортируемых двоичных чисел), выходной счетчик 2, группу триггеров , группу элементов И 4i-4„, выходные регистры 5i-5h, элемент ИЛИ 6, генератор 7 тактовых импульсов, триггер 8 управления, первый 9 и второй 10 элементы И, элемент НЕ 11, сдвиговый регистр 12, группу элементов 13i - 13n-i задержки, группу элементов ИЛИ 14i -14„, входы 15: -15„ сортируемых чисел, вход 16 запуска, выход 17 конца работы, вход 18 начальной установки.

Счетчики 11 - In служат для ввода и хранения сортируемых чисел. Выходной счетчик 2 осуществляет обратный счет от нулевого значения и служит для формирования текущего значения числа перед записью его в выходные регистры 5i-5„. Триггеры 3i-3„ служат для фиксации факта переполнения счетчиков li -1„ в цикле сортировки. Элемент ИЛИ 6 служит для выработки признака переполнения любого из счетчиков 1, - 1„. Триггер 8 обеспечивает запуск генератора 7 и его останов в конце цикла сортировки. Элементы И 9 и К) и элемент НЕ 11 позволяют выбрать направление передачи тактовых импульсов: при отсутствии признака переполнения счетчиков - на их суммирующие входы и вычитающий вход выходного счетчика; при наличии признака переполнения - на вход сдвигового регистра. Сдвиговый регистр 12 обеспечивает формирование сигналов разрешения записи в соответствующие выходные регистры 5i-5„. Группы элементов И 4i-4„, задержки 13i- 13„, ИЛИ 14| -14„ служат для последователь ного перевода в нулевое состояние триггеров 3|-3„ и соответствующих им счетчиков 1| -1„ после записи информации в очередной выходной регистр.

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

В исходном состоянии по сигналу начальной установки (вход 18) выходной счетчик 2, триггеры 3i-3„ устанавливаются в нулевое, а первый разряд сдвигового регистра 12 - в единичное состояние. В счетчики 1., -1„ в произвольном порядке заносятся сортируемые числа. Задача состоит в том, чтобы записанные во входных счетчиках 1| -1,1 числа в конце цикла сортировки перенести в выходные регистры 5i-5„ в порядке убывания их величин, начиная с регистра 5.

0

На вход 16 поступает сигнал пуска устройства, который устанавливает триггер 8 в единичное состояние. Сигнал высокого уровня с выхода триггера 8 поступает на вход

управления генератора 7 тактовых импульсов и запускает его. Поскольку все триггеры 3i-3л группы в нулевом состоянии, на выходе элемента ИЛИ 6 сигнал низкого уровня, который поступает на первый вход второго элемент И 10 и запрещает прохождение через него тактовых импульсов, а проходя через элемент НЕ 11 и поступая с его выхода на первый вход первого элемента И 9, разрещает прохождение через него тактовых импульсов. Тактовые импульсы с вы5 хода генератора 7 тактовых импульсов через .первый элемент И 9 поступают на суммирующие входы счетчиков - In и вычитающий вход выходного счетчика 2.

С приходом каждого тактового импульса содержимое счетчиков 1| -1„ увеличива ется, а содержимое выходного счетчика 2 уменьшается на единицу. Поскольку первый разряд сдвигового регистра 12 в единичном состоянии, сигнал высокого уровня с его выхода поступает на вход разрешения за5 писи выходного регистра 5i и разрешает прием инфор.мации в регистр с выхода выходного счетчика 2.

После поступления определенного числа тактовых импульсов на выходах переполнения счетчика 1 -1„ возникают сигналы

0 высокого уровня, которые поступают на единичные входы соответствующих триггеров 3i-3л группы и устанавливают их в единичное состояние. Как только хотя бы один из триггеров 3|-3„ группы преходит в единичное состояние, сигнал высокого уровня с

5 его единичного выхода поступает на вход элемента ИЛИ 6, а с его выхода через элемент НЕ 11 на первый вход первого элемента И 9, где запрещает прохождение тактовых импульсов на суммирующие входы счетчиков 1| -1„ и вычитающий вход выходного счетчика 2. На выходе выходного счетчика 2 при этом устанавливается код числа, соответствующий коду чисел, записанных в те счетчики Ь -1„, где произощло переполнение, поскольку происходил обратный счет

5 от нулевого значения в выходном счетчике 2 кольцевого типа. Этот же код фиксируется в выходном регистре 5|.

Сигнал высокого уровня с выхода элемента ИЛИ 6 поступает на первый вход второго элемента И 10, где разрешает про0 хождение тактовых импульсов. Очередной тактовый импульс с выхода генератора 7 тактовых импульсов через второй элемент И 10 поступает на вход сдвигового регистра 12 и осуществляет сдвиг единицы в нем на один разряд. Второй разряд сдвигово5 го регистра 12 переходит в единичное состояние, и сигнал высокого уровня с его выхода поступает на вход разрешения записи выходного регистра 62 и разрешает прие.м

информации в регистр с выхода выходного счетчика 2.

Очередной тактовый импульс с выхода второго элемента И 10 поступает также на вторые входы элементов И 4|-4п группы для перевода соответствующего триггера из группы 3i-3„ в нулевое состояние. По очередному тактовому импульсу переводится в нулевое состояние только один триггер, а именно триггер с наименьшим порядковым номером из числа находящихся в единичном состоянии. Обеспечивается это следующим образом. Разрешение на перевод в нулевое состояние i-ro триггера подтверждается его собственным единичным состоянием (сигнал высокого уровня с единичного выхода i-ro триггера поступает на первый вход i-ro элемента И и нулевым состоянием всех предшествующих триггеров (если хотя бы один из предшествующих триггеров находится в единичном состоянии, то сигнал низкого уровня с его нулевого выхода по- ступает на соответствующие входы всех последующих элементов И и запрещает прохождение сигнала). Элементы 13i-13,, задержки предназначены для исключения возможной неоднозначности состояний при пе- реходе триггеров 3|-3« из единичного состояния в нулевое. Таким образом, сигнал высокого уровня с выхода соответствующего элемента И 4i-4„ группы через соответствующий элемент ИЛИ 14, -14.„ группы поступает на нулевой вход соответствующего триггера 3, -Зи группы и вход установки в «О соответствующего счетчика 1, -1, и переводит их в нулевое состояние.

Если в исходном состоянии в нескольких из счетчиков 1, -1„ находились одинаковые числа, то сигналы высокого уровня появля- ются на выходах переполнения нескольких счетчиков и несколько триггеров 3:-3л находятся в единичном состоянии. При переводе одного из них в нулевое состояние, сигнал высокого уровня признака переполнения на выходе элемента ИЛИ 6 продолжает деист- вовать, запрещая прохождение тактовых импульсов через первый элемент И 9 и разрешая прохождение тактовых импульсов через второй элемент И 10. Повторяется описанный выше процесс.

С приходом следующего тактового импульса происходит сдвиг единицы в третий разряд сдвигового регистра 12, в выходном регистре 52 фиксируется код числа, соответствующий содержимому выходного счетчика 2, сигнал с выхода сдвигового регистра 12 поступает на вход разрешения записи выходного регистра 5з, происходит перевод в нулевое состояние соответствующего триггера 3i-3„ и соответствующего счетчика li -1,2 и т.д. Таким образом, в несколько выходных регистрах подряд зафиксированы равные числа, соответствующие равным числам, принятым в исходном состоянии в какие-то из счетчиков 11 - In. Переполнение происходит первоначально в счетчиках li-1„, содержащих большие числа.

Как только после перевода очередного триггера 3, -Зц в нулевое состояние, оказывается, что больше нет триггеров 3i-3,; в единичном состоянии, на выходе элемента ИЛИ 6 формируется сигнал низкого уровня, который, поступая на первый вход второго элемента И 10, запрещает прохождение тактовых импульсов на вход сдвигового регистра 12 и для перевода в нулевое состояние триггеров 3|-3„, а проходя через элемент НЕ 11 на первый вход первого элемента И 9, разрещает прохождение тактовых импульсов на суммирующие вход111 счетчиков -1„ и вычитающий вход выходного счетчика 2. Код следующего по величине числа формируется в выходном счетчике 2 и поступает в очередной выходной регистр. Процесс сортировки чисел продолжается.

В тот момент, когда происходит переполнение последнего (содержащего в исходном состоянии наименьшее по величине число) из счетчиков - п сигнал высокого уровня признака переполнения с выхода элемента ИЛИ 6, проходя через элемент НЕ 11 на первый вход первого элемента И 9, запрещает прохождение тактовых импульсов на входы счетчиков, а поступая на первый вход второго элемента И 10 разрещает прохождение через него тактовых импульсов. В выходном регистре 5 фиксируется код наименьшего числа. Очередной тактовый импульс с выхода .генератора 7 тактовых импульсов через второй элемент И 10, через соответствующий элемент И ,, обеспечивает перевод в нулевое состояние соответствующего триггера 3i-3„ и счетчика li - „, содержащего в исходном состоянии наименьшее число.

Поступая на вход сдвигового регистра 12, очередной тактовый импульс вызывает его переполнение. Сигнал переполнения с выхода сдвигового регистра поступает на нулевой вход триггера 8 и на выход 17 сигнала конца работы устройства. Триггер 8 переходит в нулевое состояние, сигнал низкого уровня с его выхода поступает на управляющий вход генератора 7 и блокирует его работу. На этом заканчивается цикл сортировки группы двоичных чисел.

Формула изобретения

Устройство для сортировки двоичных чисел, содержащее генератор тактовых импульсов, счетчики, группу триггеров, группу элементов И, выходные регистры, элемепт ИЛИ, выходной счетчик, триггер управлепия, первый и второй элементы И, элемент НИ, причем вход запуска устройства подключен к входу установки в «1 триггера управления, прямой выход которого соединен с управляющим входом генератора тактовых импульсов, выход которого соединен с первым входом первого элемента И, выход которого соединен с вычитающим входом выходного счетчика и суммирующими входами счетчиков, информационные входы которых являются входами сортируемых чисел устройства, выход переполнения i-ro счетчика, где 1 l,2,...,rt, п - количество сортируемых чисел, соединен с входом установки в «1 г -го триггера группы, прямой выход которого соединен с первым входом i-ro элемента И группы, выход элемента ИЛИ подключен к первому входу второго элемента И через элемент НЕ к второму входу первого элемента И, информационные выходы выходного счетчика соединены с соответствующими информационными входами выходных устройств, отличающееся тем, что, с целью упрощения устройства, оно содержит сдвиговый регистр, группу элементов ИЛИ и группу элементов задержки, причем второй вход второго элемента И подключен к выходу генератора тактовых импульсов, а выход соединен с вторыми входами всех элементов И группы и входом управления сдвигом сдвигового регистра, выход г -го разряда которого соединен с входом управления записью г -го выходного регистра, а вход младшего разряда подключен к входу начальной установки устройства, входу установки в «О выходного счетчика и первым входам всех элементов ИЛИ группы, выход j-ro элемента И группы соединен с вторым входом i-ro элемента ИЛИ группы, выход которого подключен к входам установки в «О i-ro триггера группы и i-ro счетчика, прямые выходы всех триггеров группы подключены к входам элемента ИЛИ, инверсный выход i-ro триггера группы, где / 1,2,..., (п-1) через /-Й элемент задержки соединен с (/+2)-ми входами элементов И группы с ( 1)-го по «-Й, выход старшего разряда сдвигового регистра подключен к входу установки в «О триггера управления и является выходом конца работы устройства.

Изобретение относится к вычислительной технике и может быть использовано при выполнении операций сравнения по величине кодовых комбинаций. Цель изобретения - упрощение устройства. Устройство содержит счетчики 1, выходной счетчик 2, группу триггеров 3, группу элементов И 4, выходные регистры 5, элементов ИЛИ 6, генератор 7 тактовых импульсов, триггер 8 управления, элементы И 9, 10, элемент НЕ 11, сдвиговый регистр 12, группу элементов задержки 13, группу элементов ИЛИ 14. Счетчики служат для ввода сортируемых чисел. Выходной счетчик осуществляет обратный счет и служит для формирования текущего значения числа для записи его р выходные регистры. Сдвиговый регистр обеспечивает формирование сигналов разрешения записи в соответствующие выходные регистры. Группы элементов И, ИЛИ и задержки служат для последовательного перевода в нулевое состояние соответствующих счетчиков после записи информации в очередной выходной регистр. 1 ил. S сл оо ISD ел 4 О5 Ю ю /г