ВЫЧИСЛИТЕЛЬ РАНГОВ Российский патент 1997 года по МПК G06F7/06 

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

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

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

Известное устройство для ранжирования чисел [2] выбранное в качестве прототипа, содержит регистр сдвига с N ячейками и отводом от каждой ячейки, где N число сортируемых чисел (размер окна), 2(N-1) компараторов, один (N-1)-входовый сумматор, (N-1) элементов НЕ, N m-разрядных элементов задержки, где m количество разрядов числа N, и (N-1) трехвходовых сумматоров.

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

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

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

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

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

На чертеже изображена блок-схема вычислителя рангов.

Устройство содержит регистр сдвига 1 с отводами от каждой ячейки, группу компараторов 2, 3, 4 и 5, сумматор 6, элементы НЕ 7, 8, 9 и 10, группы одноразрядных элементов задержки 11; 12, 13; 14, 15, 16; 17, 18, 19, 20; группу трехразрядных (в данном примере для хранения числа 4 максимального ранга требуется три разряда) элементов задержки 21, 22, 23 и 24, трехвходовые сумматоры 25, 26, 27 и 28, шину тактового питания устройства 29, вход устройства 30 и выходы 31, 32, 33, 34, и 35, причем информационный вход регистра сдвига является информационным входом устройства.

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

Выход первого разряда сдвигового регистра 1 соединен с первыми входами компараторов 2 5, второй вход i-го компаратора, где i=1.(N-1), N - количество сортируемых чисел, подключен к выходу (i+1)-го разряда сдвигового регистра, выходы компараторов 2 5 подключены к соответствующим входам сумматора 6 и через элементы НЕ 7 10 соединены с первыми входами соответствующих трехвходовых сумматоров 25 28 и входами соответствующих групп последовательно соединенных одноразрядных элементов задержки 11; 12, 13; 14, 15, 16; 17, 18, 19, 20. Выходы групп одноразрядных элементов задержки подключены к третьим входам соответствующих трехвходовых сумматоров 25 28. Выходы сумматора 6 и трехвходовых сумматоров 25, 26 и 27 через соответствующие трехразрядные элементы задержки 21 24 подключены ко вторым входам соответствующих трехвходовых сумматоров 25 28. Вход 29 тактовых импульсов устройства соединен с тактовыми входами сдвигового регистра 1, трехразрядных элементов задержки 21 24, одноразрядных элементов задержки 11; 12, 13; 14, 15, 16; 17, 18, 19, 20. Выходы сумматора 6 и трехвходовых сумматоров 25 28 образуют выходы устройства 31 35.

После окончания предыдущего цикла вычисления ранги чисел, остающихся в сдвиговом регистре 1, передаются в следующий сумматор (из 6 в 25, из 25 в 26 и т.д.). Новое число, поступившее в регистр сдвига 1, сравнивается компараторами 2 5 с числами, уже находящимися в этом регистре; многовходовый сумматор 6 подсчитывает ранг этого нового числа, а элементы НЕ 7 10 и группы одноразрядных элементов задержки 11; 12, 13; 14, 15, 16; 17, 18, 19, 20 формируют сигналы для модификации рангов старых чисел с помощью трехвходовых сумматоров 25 28.

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

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

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных. Вычислитель рангов содержит регистр 1 сдвига, группу компараторов 2-5, группу многоразрядных элементов 11-24 задержки, сумматор 6, группу трехвходовых сумматоров 25-28, группу элементов 7-10 НЕ. Введение (N-1) групп одноразрядных элементов задержки обеспечивает существенное упрощение устройства. 1 ил.

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