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

выход является выходом разрешения вы- вход разрешения записи которого поддачи и подключен к управляющим входам ключен к выходу первого элемента И и выходных элементов И группы и вычита- синхронизирующему входу второго тригющим входам счетчика равных чисел, гера.

1179317

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее входные счетчики, выходной счетчик, группу элементов ИЛИ, группу формирователей импульсов, группу выходных элементов И, группу запрещающих элементов И, элемент ИЛИ, входной элемент И, первый вход которого подключен к. входу тактовых импульсов устройства, а выход со.единен с суммирующим входом выходного счетчика и первыми входами запрещающих элементов И группы, выходы которых соединены с вычитающими входами соответствующих входных счетчиков, выходы которых поразрядно подключены к входам соответствующих элементов ИЛИ группы, выходы KOTopbtx соединены с входами соответствующих формирователей импульсов группы, вторыми входами соответствующих запрещающих элементов И группы и с соответствующими входами элемента ИЛИ., выходы выходного счетчика поразрядно соединены с информационными входами выходных элементов И группы, выходы которых являются информационными выходами устройства, отличающееся тем, что, с целью повышения достоверности при сортировке равных чисел, в него введены первьш и второй триггеры, регистр, преобразователь числа единиц в двоичный код, счетчик равных чисел, первьй и второй элементы ШЖ-НЕ, первый и второй элементы И, формирователь импульса сброса, элемент задержки,причем выходы формирователей импульсов группы соединены с соответствующими разрядными входами регистра, выходы разрядов которого соединены с входами первого элемента ИЛИ-НЕ и с соответствующими входами преобразователя числа единиц в двоичный код, выхос S ды которого соединены с соответствующими информационными входами счетчика равных чисел, выходы которого С соединены с входами второго элемента ИЛИ-НЕ, выход которого соединен через формирователь импульса сброса с синхронизирующим входом первого триггера и входами зстановок в нулевое состояние регистра и второго триггера, информационный вход которого соединен с входом логической . единицы устройства, инверсный выход второго триггера соединен с первым входом первого элемента И, второй вход которого соединен с выходом первого элемента ИЛИ-НЕ и через элемент задержки - с вторым входом входного элемента И, третий вход которого сое-, динен с прямым выходом, первого триггера, информационный вход которого соединен с выходом элемента ИЛИ, вход тактовых импульсов устройства подключен к третьему входу первого элемента И и первому входу второго элемента И, второй вход которого соединен с прямым выходом второго триггера, а

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

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

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

Таблица состояния выходов преобразователя числа единиц в двоичный код в зависимости от состояния его входов (на примере пяти входов) приведена в табл.1.

Устройство содержит входные счетчики 1,...,1jj,, выходной счетчик 2, группу элементов ИЛИ 3j, , 3j, элемент ИЛИ 4, триггер 5, группу запрещающих элементов И 6, ..., 6, входной элемент И 7, группу выходных элементов И 8 , ..., 8, группу формирователей 9j, ..., 9m импульсов, регистр 10, элемент ШШ-НЕ 11, элемент 12 задержки, элемент И 13, триггер 14, преобразователь 15 числа единиц в двоичный код, счетчик 16 равных чисел, элемент ИЛИ-НЕ 17, элемент И 18, формирователь 19 импульса сброса тактовьй вход 20 устройства, информационные выходы 21 устройства, выход 22 разрешения вьщачи.

Назначение элементов устройства следующее. Счетчики Ij , ..«, 1 служат для временного запоминания исходных сортируемых чисел. Элементы ИЛИ 3(, ..., 3 служат для фиксирования нулевого состояния соответствующего счетчика 1 ,.. ., , причем-при нулевом содержимом счетчика 1, ..,,1 на выходе соответствующего элемента ИЛИ -3 , . .., 3 - нулевой потенциал. Выходной счетчик 2 служит для формирования кода на выходах 21 устройства при сортировке чисел. Элемент ШШ 4 и триггер 5 служат для

фиксирования нулевого состояния всех счетчиков 1,, ..., IP, в конце сортировки и выработки запрещающего потенциала по второму входу элемента И 7 для дальнейшей блокировки тактовых импульсов. Формирователи 9,, ..., и регистр 10 служат для фиксирования количества счетчиков 1,, ..., Iff,, установленных в нулевое состояние в последнем цикле. Преобразователь 15 служит для преобразования числа установленных разрядов регистра 10 в единичное состояние в двоичньй код (табл.1). Счетчик 16 равных чисел служит для подсчета выдаваемых устройством синхроимпульсов. Элемент ШШ-НЕ 17 служит для фиксирования нулевого состояния счетчика 16. Элемент И 13 и элемент ИЛИ-НЕ 11 служат для выработки сигнала перезаписи информации с выходов преобразователя 15 в счетчик 16 равных чисел и установки триггера 14 в единичное состояние. По первому и второму входам элемента И 13 осуществляется инверсия поступающих сиг.налов. По синхровходу триггера 14 осуществляется инверсия входного сигнала. Элемент И 18 служит для выработки синхросигнала на втором выходе устройства и вычитающих импульсов для счетчика 16 равных чисел. Элемент задержки 12 служит для обеспечения устойчивой перезаписи информации в регистр.10 путем задержки сигнала запрета по третьему входу входного элемента И 7 после срабатьшания первого элемента ИЛИ-НЕ 11 (появление нулевого потенциала), причем величина задержки (ggAf элемента 12 выбирается, например, из соотношения ЗэаАг - 2 7 длительность тактового импульса Формирователь 19 служит для формирования сигнала установки в нулевое состояние второго триггера 14, регистра 10 и синхросигнала для первого триггера 5, причем сигнал на выходе формирователя 19 задержан относительно переднего фронта единичног сигнала с выхода элемента ИЛИ-НЕ 17 на время «заЛ2 которое определяется, например, исходя из устойчивой работы устройства из соотношения л л/ TLI л 2 aAg ЪВременные интервалы между тактовыми импульсами составляют при этом, например, /эадг Исполнение элементов устройства может быть, например, следующее. Счетчики, триггеры, регистр, эле менты И, ИЛИ, ИЛИ-НЕ, группы элемен {тов И являются типовыми, например, для цифровых интегральных схем TTL серий 133, К155, 130, К131, 530, К531, К555. Лреобразователь 15 реали зуется, например, на базе типовых ло гических элементов с учетом таблицы состояний. Формирователи 9,,,.., 9 19 могут быть реализованы, например на базе типовых формирователей К155АГЗ с учетом логики функционирования и временных параметров, приведенных в материалах заявки. Устройство работает следующим образом. Во входные счетчики 1;,, ..., 1fr) заносятся сортируемые числа. Регистры 10 и счетчик 16 обнулены, триггер 14 установлен в нулевое состояние, при этом на инверсном выходе последнего - потенциал логической единицы. Триггер 5 устанавливается в единичное состояние, при этом с его выхода на второй вход элемента И 7 поступает единичный потенциал (цепи начальной установки элементов устройства на фиг.1 не показаны). В исходном состоянии на выходах элементов ШШ-НЕ 11 и 17 - единичные потенциалы, поскольку регистр 10 и счетчик 16 обнулены, а на выходах элементов ИЛИ 3 ..., единичные потенциалы, поскольку содер1 не равжимое счетчиков 1 но О, и следовательно, на первые входы группы запрещающих элементов И 6„ .,..., 6( и на второй и третий входы элемента И 7 поступают разрешающи единичные потенциалы. На вход 20 .устройства подаются тактовые импульсы (фиг.2а), которые через элемент И 7 поступают на суммирующий вход выходного счетчика 2 и через группу элементов И 6.,...,6 на вычитанлцие входы счетчиков 1 ,..., 1 . При этом содержимое счетчиков . 1,...,1 уменьшается, а выходного счетчика 2 - увеличивается. При поступлении на вход 20 устройства количества тактовых импульсов, соответствующего минимальному числу (или нескольким числам) из сортируемых чисел в счетчиках 1.,...,1, содержимое соответствующего счетчика 1 (или нескольких счетчиков 1, i) в котором (в которых) было записано минимальное число, становится равным . На выходе соответствующих элементов ИЛИ 3 появляется нулевой потенциал (фиг.25), закрывающий соответствующие элементы И 6 группы, блокируя дальнейшее поступление вычитающих импульсов на входы тех счетчиков 1|, в которых содержимое стало равным О. На выходах форьшрователей 9 , подключенных к тем элементам ИЛИ 3 , на которых выставился нулевой потенциал, появляются импульсы записи 1 в регистр 10 (фиг.2г), причем количество записанных 1 по всем разрядам регистра 10 соответствует числу счетчиков 1, установленных в нулевое состояние. Срабатывает элемент ШШ-НЕ 11, на выходе которого выставится нулевой потенциал. Далее через срабатывает .элемент 12 задержки и на третьем, входе элемента И 7 выставляется запрещающий нулевой потенциал, по которому поступление тактовых импульсов на элемента И 7 блокируется (фиг.. По концу тактового импульса срабатьшает элемент И 13, на выходе которого появляется импульс перезаписи двоичного кода числа, например 3, установленных в нулевое состояние счетчиков 1,, в счетчик 16 равных чисел по его синхровходу (фиг.2е). По концу сигнала перезаписи (поскольку по синхровходу триггера 14 осуществляется инверсия сигнала) триггер 14 устанавливается в единичное состояние, так что с его инверсного выхода на третий вход элемента И 13 поступает запрет, а с его прямого выхода на второй вход элемента И 18 - разрешение (фиг.2). На выходе элемента ИЛИ-НЕ 17 устанавливается нулевой потенциал. Тактовый импульс с первого входа элемента И 18 поступает на его выход

(фиг.2р и далее - на вычитающий вход счетчика 16, на вторые входы группы элемен- ов И В, , 8 и на второй выход 22 устройства. При этом с выхода счетчика 2 на выход 21 устройства поступает код минимального числа (чисел). По следующему тактов.ому импульсу также поступает с выхода элемента И 18 строб-импульс о вьщаче на выход 21 устройства такого же содержимого счетчика 2 (фиг.2«). Поскольку в счетчике 16 было записано число 3, то с поступлением с выхода элемента И 18 третьего вычитающего импульса счетчик 16 устанавливается в нулевое состояние,срабатывает второй элемент Ш1И-НЕ 17 и на его выходе выставляется единичный потенциал Сфиг.2и). Таким образом, на выход 21 устройства поступает код минимальных чисел столько раз, сколько бьшо записано в счетчики 1,, ..., равных чисел.

По переднему фронту () сигнала с выхода элемента ИЛИ-НЕ 17 запускается формирователь 19 через выходе которого появляется импульс (фиг. 2 о, по которому триггер 14 сбрасывается в нУлевое состояние и триггер 5 устанавливается в то же состояние, что и на выходе второго элемента ИЛИ 4, сигнал с которого поступает на информационный D-вход триггера 5. Поскольку не все счетчики 1, ..., 1 обнулились в первом цикле работы устройства, то на некоторых входах элемена ИЛИ 4 - единичные потенциалы и на выходе последнего - также единич-. ный.потенциал. Триггер 5 поэтому не

изменяет по синхроимпульсу с выхода формирователя 19 своего состояния (единичного).

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

тв

левое состояние в последнем цикле, а затем на выход 21 поступает код этих чисел с выхода счетчика 2 столько же раз. Причем коды сопровождаются синхроимпульсами с выхода 22 устройства. Циклы сортировки повторяются до тех пор, пока все записанные числа в счетчиках 1 , ..., 1 f, не будут отсортированы, т.е. все счетчики 1 j, . .. 1 fr) обнуляются. В конце последнего

цикла элемент ИЛИ 4 выставляет на своем выходе нулевой потенциал, а по переднему- фронту сигнала с выхода формирователя 19 триггер 5 устанавливается в нулевое состояние и блокирует

дальнейшее поступление тактовых импульсов через элемент И 7. Сортировка чисел окончена.

Для проведения сортировки чисел устройством, начиная с максимального числа, достаточно записать числа во входные счетчики 1;,, т обратном коде и результат получать с нулевых выходов выходного счетчика 2.

Продолжение таблицы

21

фиг. / пппппппп

fpi/s.2 t