Вычислитель рангов Советский патент 1993 года по МПК G06F7/06 

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

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

Недостатки такого устройства заключаются в том, что оно не обеспечивает высокой скорости вычисления ранга данных внутри окна при скольжении этого окна едоль числовой последовательности, так как при каждом смещении окна ранги вычисляются заново без учета предыдущих сравнений; устройство имеет большие габариты, так как каждый его элемент выполняется в виде отдельного узла,

Известное устройство для ранжирования чисел, выбранное в качестве прототипа, содержит регистр сдвига с (2N+1J ячейками и отводом от каждой ячейки, где (2N+1) - количество сортируемых чисел (размер окна), 6N компараторов, один 2N - входовой сумматор, (2N+1) элементов задержки и 2N трехвходовых сумматоров. Данное устройство работает следующим образом. При поступлении нового числа в сдвиговый регистр с отводами это число сравнивается первыми 2N компараторами с остальными числами, хранящимися в регистре, и 2N - входрвый сумматор вычисляет рант нового числа. Ранги чисел, уже находящихся в регистре сдвига, модифицируются трехвходо- выми сумматорами при помощи вторых и третьих 4N компараторов, сравнивающих ранги этих чисел с рангами вновь появившегося в регистре и вышедшего из регистра чисел.

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

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

Поставленная цель достигается тем, что в вычислитель рангов, содержащий регистр сдвига, две группы компараторов, группу элементов задержки, сумматор, группу трехвходовых сумматоров, причем информационный вход регистра сдвига является .информационным входом устройства, выход первого разряда сдвигового регистра соединен с первыми входами компараторов первой группы, второй вход 1-го компаратрра группы, где ...(N-1), N - количество сортируемых чисел, подключен к выходу (i+1)-ro разряда сдвигового регистра, выходы компараторов первой группы подключены к соответствующим входам сумматора, выход первого элемента задержки соединен с первым входом первого компаратора второй группы, выход i-ro трехвходового сумматора группы через (1+1)-ый элемент за0 держки подключен к первому входу (i+1)-ro компаратора второй группы, вторые входы всех компараторов второй группы подключены к выходу N-го элемента задержки, выход 1-го компаратора второй группы

5 соединен с первым входом i-ro трехвходового сумматора группы, второй вход которого соединен с выходом i-ro элемента задержки, вход тактовых импульсов устройства соединен с тактовыми входами сдвигового

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

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

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

Устройство содержит регистр сдвига 1 С отводами от каждой ячейки, первую группу компараторов 2,3,4 и 5, сумматор 6, элементы НЕ 7, 8, 9, 10, группу элементов задер0 жки 11, 12, 13, 14 и 15, вторую группу компараторов 16, 17, 18 и 19, трехвходовые сумматоры 20, 21, 22, 23, причем информационный вход регистра сдвига является информационным входом устройства.

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

Выход первого разряда сдвигового регистра Т соединен с первыми входами компараторов 2, 3, 4 и 5 первой группы, второй

0 вход i-ro компаратора группы, где ...(N- 1), N - количество сортируемых чисел, подключен к выходу (1+1)-го разряда сдвигового регистра, выходы компараторов 2, 3, 4 и 5 первой группы подключены к соответствую5 щим входам сумматора б и через элементы НЕ 7, 8, 9, 10 группы соединены с третьими входами соответствующих трехвходовых сумматоров 20, 21, 22, 23 группы. Выход первого элемента задержки 11 соединен с первым входом первого компаратора 16

второй группы. Выход i-ro трехвходового сумматора группы через (1+1)-ый элемент задержки подключен к первому входу (i-H)-ro компаратора второй группы. Вторые входы всех компараторов второй группы 16, 17,18 и 19 подключены к выходу N-ro элемента задержки, выход 1-го компаратора второй группы 16, 17, 18, 19 соединен с первым входом i-ro трехвходового сумматора группы (20, 21, 22, 23), второй вход которого соединен с выходом i-ro элемента задержки. Вход 24 тактовых импульсов устройства соединен с тактовыми входами сдвигового регистра 1 и элементов задержки 11, 12, 13, 14, 15 группы. Выходы сумматора 6 и трех- входовых сумматоров 20, 21, 22, 23 группы образуют выход устройства.

После окончания предыдущего цикла вычисления ранги чисел, остающихся в сдвиговом регистре 1, сравниваются с рангом, находящимся в сумматоре 23, и передаются в следующий сумматор ( из 22 в 23, из 21 в 22 и т.д.). Новое число, поступившее в регистр сдвига 1, сравнивается компараторами 2-5 с числами, уже находящимися в этом регистре; многовходовый сумматор 6

подсчитывает ранг этого нового числа, а элементы НЕ 7-10 формируют сигналы для модификации рангов старых чисел с помощью сумматоров 20-23, Группы компараторов 2-5 и 16-19 работают независимо друг от друга, поэтому они могут работать одновременно, то есть вычислять ранг всех чисел в течение одного такта.

Сдвиговый регистр с отводами, блок

сумматоров и элементов задержки легко реализуются в микроэлектронном выполнении на приборах с зарядовой связью, а компараторы - на МОП-транзисторах, при этом блок сумматоров и элементов задержки представляет из себя сдвиговый регистр с дополнительными электродами для сложения и вычитания содержимого ячеек регистра с единичным зарядовым пакетом.

По сравнению с прототипом предложенный вычислитель рангов, в который введена группа элементов НЕ, является более простым устройством, так как в нем простые электронные узлы, осуществляющие функцию НЕ (замену 0 на 1 и наоборот), заменяют имеющиеся в прототипе такие сравнительно сложные электронные узлы, как компараторы.

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

Формула изобретения Вычислитель рангов, содержащий регистр сдвига, две группы компараторов, группу элементов задержки, сумматор, группу трехвходовых сумматоров, причем информационный вход регистра сдвига является информационным входом вычислителя, выход первого разряда сдвигового регистра соединен с первыми входами компараторов первой группы, второй вход 1-го компаратора группы, где ,...,N-1; N - количество сортируемых чисел, подключен к выходу (i+1)-ro разряда сдвигового регистра, выходы компараторов первой группы подключены к соответствующим входам сумматора, выход первого элемента задержки соединен с первым входом первого компаратора второй группы, выход i-ro трехвходового сумматора группы через (1+1)-й элемент задержки подключен к первому входу (1+1)-го компаратора второй группы, вторые входы всех компараторов второй группы подключены к выходу N-ro

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

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

сумматоров группы.