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

СО

с

Изобретение относится к автоматике и вычислительной технике и может быть использовано для сортировки чисел путем сравнения с нечетким числом. Цель изобретения - расширение функциональных возможностей. Устройство содержит элемент И 1, счетчики 2, 17,18.8, блок хранения векторов 3, блок 14 памяти, коммутатор 19, блоки алгебраического суммирования 4 и 10, блок сравнения с допуском 7 и блок сравнения векторов 16, элемент ИЛИ 19, элементы задержки 20 и 16, регистры 5, 6, 11, 12 и блок сравнения 9. 3 ил.

00

о ю

со о

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

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

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

Устройство для сравнения и сортировки исел (фиг. 1) содержит элемент И 1, первый четчик 2, блок 3 хранения векторов, первый блок А алгебраического суммирования, первый 5 и второй 6 регистры 7, блок сравнения допуском, четвертый счетчик 8, блок 9 равнения, второй блок 10 алгебраического суммирования, третий 11 и четвертый 12 регистры, коммутатор 13, блок 14 памяти, второй элемент задержки 15, блок 16 сравнения векторов, третий 17 и второй 18 счетчики, элемент ИЛИ 19, первый элемент задержки 20.

1 Блок 16 сравнения векторов (фиг.2) содержит элементы возведения разности в квадрат 21 и 22, схему 23 сравнения, элементы И 24, 25.

Блок 7 сравнения с допуском содержит элементы возведения разности в квадрат 26, 27, схемы 28. 29 сравнения, первый 30, второй 31 и третий 32 элементы И.

Работает устройство для сравнения и сортировки чисел следующим образом.

Перед началом работы устройства в блок 3 хранения векторов по адресам i 0,...,N-1 записываются вектора xfi, а в блоки 2, 5, 6, 11, 12, 17, 18 подаются сигналы начальной установки (НУ). По сигналу НУ первый 2 и четвертый 8 счетчики переходят в состояние, в котором на их выходах устанавливается число О, а на выходах третьего 17 и четвертого 18 счетчиков устанавливается число 1. В первый 5, второй 6, третий 11 и четвертый 12 регистры по сигналу НУ должны быть записаны векторы хо и хТ соответственно, которые записаны в блоке 3 по адресам i 0 и I 1.

После прохождения импульсов НУ на выходе н блока 9 сравнения устанавливается уровень логической единицы. Этот сигнал поступает на вход первого элемента И 1 и открывает его для прохождения тактовых импульсов со входа С устройства,

Рассмотрим работу устройства при прохождении тактового импульса.

Тактовый импульс со входа С устройства поступает на счетный вход первого счетчика 2, который реализован как счетчик

по модулю N. Адрес I с выхода первого счетчика 2 поступает на адресные входы А блоков 3 и 14, с выхода D блока 3 вектор Xi поступает на входы первого 4 и второго 10

блоков и на вход А2 блока 16. На другие входы блока 4 поступает число К1 с выхода , второго счетчика 18 и вектор Ti с выхода первого регистра 5. На вход блока 10 поступает число К2 с выхода третьего счетчика 17

и вектор V2 с выхода третьего регистра 11, На входы А1 и A3 логического преобразователя 16 поступают векторы Vt и /2 соответственно.

Первый блок 4 реализует функцию

- -.

Vi Vi +(xi-Vi) 1/K1,

а второй блок 10 функцию V2 /2 + (х - /2) 1/К2.

Новые центры двух классов - векторы Vi и N/21 с выходов первого 4 и второго 10 блоков поступают на входы первого 5 и

третьего 11 регистров соответственно. Запись информации в них происходит по единичному импульсу, поступающему на входы W с выходов S1 и S2 блока 16. С выхода S1 блока 16 сигнал поступает на счетный вход

второго счетчика 18, а с выхода S2 - на счетный вход третьего счетчика 17. Единичный импульс, поступивший на входы третьего 17 и второго 18 счетчиков увеличивает на единицу значение числа К1 или К2 соответственно.

Схема блока 16 приведена на фиг.2. Работает блок 16 следующим образом. Элемент 21 реализует функцию

. |2

/31 Ixi-Vi

а элемент 22 - функцию

/ЭгИх|- /2 I2,

0)

(2)

) - §ектор, поступающий на вход А2, . a Vi и V2 поступают на входы А и A3 блока 16.

Если число pi меньше числа pi , то на

выходе схемы 23 появляется уровень логической единицы. При условии р рг уровень логической единицы появляется на выходе схемы 23. Сигналы с выходов схемы 23 поступают на элементы И

24 и 25. На другие входы элементов И подается тактовый импульс. Таким образом, если выполнено условие (1), то единичный импульс появляется на выходе S1, а при выполнении условия (2) - на выходе S2.

Вектор Vi с выхода первого регистра 5 поступает на вход второго регистра б и на вход А2 блока 7. Вектор 2 поступает с выхода третьего регистра 11 на вход четвертого регистра 12 и на вход A3 блока 7, на входы А1 и А2 блока 7 поступают векторы Й1 и Wz с выходов второго 6 и четвертого 12 регистров соответственно.

Схема блока 7, приведенного на фиг.З, работает следующим образом.

Элемент 26 реализует функцию

Li- |Wi-Vil , .(3). а элемент 27 - функцию

т-л«.

Ц |W2-V2I ,(4)

На выходе схемы 28 сравнения появляется уровень логической единицы, если 20 выполнено условие

L e

(5)

На выходе элемента 29 сравнения 25 появляется уровень логической единицы, при выполнении условия

L Ј.(6)

Сигналы с выходов элементов 28 и 29 30 поступают на вход первого элемента И 30, при одновременном выполнении условий (5) и (6) уровень логической единицы с выхода первого элемента И 30 поступает на вход второго элемента И 31. Если не выполнено 35 хотя бы одно из условий (5), (6), то уровень логической единицы поступает с инверсного выхода первого элемента И 30 на третий элемент И 32. На другие входы второго 31 и третьего 32 элементов И подается тактовый 40 импульс. Таким образом при одновременном выполнении условий (5), (6) единичный импульс появляется на выходе ST блока 7, в противном случае - на выходе S2.

Сигналы с выходов S1 и S2 блока 7 по- 45 ступают на входы счет и сброс четверто- го счетчика 8. При поступлении единичного импульса на вход счет содержимое четвертого счетчика увеличивается на единицу. А при подаче такого импульса на вход 5,0 сброс на выходе четвертого счетчика 8 устанавливается число О.

Сигнал с выхода S2 блока 7 поступает на входы W разрешения записи второго 6 и четвертого 12 регистров. При поступлении 55 единичного импульса на их входы W в них записывается информация.

Число S с выхода четвертого счетчика 8 поступает на вход блока 9 сравнения. На

0

5

0

5

0 5 0

5 0

5

другой вход блока 9 подается число N-1. На выходе блока 9 сравнения устанавливается уровень логической единицы если число S меньше N-1,

Сигнал с выхода элемента И 1 поступает на вход С блока 16 и на вход второго элемента задержки 20. С выхода второго элемента задержки 20 импульс поступает на вход С блока 7, Длительность задержки во втором элементе 20 выбирается таким образом, чтобы к моменту появления единичных импульсов на выходах блока 7 на входах второго 6 и четвертого 12 регистров уже установились значения векторов Vi и V2.

Данные о принадлежности векторов xi, I 0,...,N-1,K одному из двух классов записываются в блок 14. На адресный вход блока 14 поступает число i с выхода первого счетчика 2, а на вход данных - числа О или 1 с выхода коммутатора 19. Управление коммутатором 19 осуществляется сигналом с выхода S2 блока 16. Запись информации происходит при поступлении единичного импульса на вход W разрешения записи блока 14. Для формирования сигнала управления записью служит цепочка из элемента ИЛИ 19 и второго элемента задержки 20. Длительность задержки второго элемента задержки 20 подбирается таким образом, чтобы за это время успело установиться определенное значение на выходе коммутатора 19.

Устройство автоматически прекращает работу, если число S на выходе четвертого счетчика 8 равно числу N-1 (обработаны все векторы из заданного множества). При этом на выходе 5 блока 9 устанавливается уровень логической единицы - сигнал стоп устройства, а уровень логического нуля с выхода блока 9 закрывает элемент И 1 для прохождения тактовых импульсов.

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

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

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

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

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

А2

A3

-зУ-

27

А4:

#

О

Фае. 2

J/

30

Ф$

29

..J