Устройство для сравнения чисел в модулярном коде

 

Изобретение относится к вычислительной технике и может быть использовано при построении систем передачи информации, устройств обработки , использующих модулярную арифметику , многопроцессорных магистрально-модульных информационно управляющих систем. Цель изобретения - расширение области применения за счет обеспечения сравнения любых двух чисел из диапазона представления чисел. Устройство содержит входные регистры, блок хранения констант , два блока умножения по модулю, два блока сравнения, коммутатор, узел управления, который включает элементы И, ИЛИ, задержки, счетчик. Устройство позволяет определить адрес :чисел А и В , которые дают возможность сравнить числа, отличающиеся между собой на величину р в первом блоке сравнения. Второй блок сравнения, сравнивающий старшие вычеты d И , обеспечивает сравнение чисел, отличающихся между собой на величину, не большую чем и - 1. Обе процедуры сравнения обеспечивают сравнение любых двух чисел в диапазоне представления чисел Ph П Р- . 2 ил. с 9 (Л ю СП Од

СОЮЗ ССВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (бд 4 G 06 F 7/04

NCFf : 8 Я

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA (21) 3855358/24-24 (22) 11.02.85 (46) О?.09.86. Бюл. У 33 (72) С.Н.Хлевной и К.M.Ñàãäååâ (53) 681.325.5(088,8) (56) Авторское свидетельство СССР

У 608155, кл. G 06 F 7/04, 1976.

Авторское, свидетельство СССР

У 873237, кл. G 06 F 7/04, 1979. с с0 (54) УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ ЧИСЕЛ

В МОДУЛЯРНОМ КОДЕ (57) Изобретение относится к вычислительной технике и может быть использовано при построении систем передачи информации, устройств обработки, использующих модулярную арифметику, многопроцессорных магистрально-модульных информационно управляющих систем. Цель изобретения - расширение области применения за

„„90„„1256013 А 1 счет обеспечения сравнения любых двух чисел из диапазона представления чисел. Устройство содержит вход" ные регистры, блок хранения констант, два блока умножения по модулю, два блока сравнения, коммутатор, узел управления, который включает элементы И, ИЛИ, задержки, счетчик.

Устройство позволяет определить ад— рес чисел A и В, которые дают возможность сравнить числа, отличающиеся между собой на величину Я„ в первом блоке сравнения. Второй блок сравнения, сравнивающий старшие вычеты о „ и Р» обеспечивает сравнение чисел, отличающихся между собой на величину, не большую чем ь — 1.

Обе процедуры сравнения обеспечивают сравнение любых двух чисел в диапазоне представления чисел 1n =

=OP; . 2 ил.

i=1

1256013 ственно. Блок 2 хранения констант, известный функциональный элемент, может выполняться на ПЗУ, в котором хранятся коды ядер R . для выбранной

8i системы оснований, выход необходимого ядра определяется кодом, поступающим на адресный вход блока 2 хранения констант. Таблица истиннос-. ти блока хранения констант для рассмотренного примера приведена, Выход блока 2 хранения констант подключен к вторым входам блоков

3.1 и 3.2 умножения по модулю, выходы которых подключены к информационным входам сумматоров по модулю 4.1 и 4.2, входы синхронизации которых объединены между собой, с тактовыми входами входных регистров 1.1 и 1.2 и соединены с первым выходом блока 7 управления, второй выход которого подключен к управляющим входам блоков 5.1 и 5.2 сравнения, выходы которых подключены к входам коммутатора

6. Коммутатор 6, известный функциональный элемент, обеспечивает коммутацию трех выходов блока 5.1 сравнения или трех выходов блока 5.2 сравнения на свои выходы, в зависимости от сигнала на его входе управления, который соединен с первым выходом блока 5.1 сравнения. Выходы коммутатора являются выходными шинами устройства 8.1-8.3, соответственно первый выход . — выход "равенства", второй — выход "больше, третий - выход

"меньше". Третий выход блока 7 управления подключен к адресному входу блока 2 хранения констант.

Адресный вход Выход

01111

10001

10

В своей работе устройство использует следующее.

Любое целое число Х„представленное в модулярном коде как Ы = (2;, 2

2„), может быть выражено в позиционной системе как

N = Р; R„+ñ „ (1) Изобретение относится к вычислительной технике и может быть исполь-, зовано в системах передачи информации, устройствах обработки, использующих модулярную арифметику, а также 5 в составе многопроцессорных магистрально-модульных информационно-управляющих систем.

Цель изобретения — расширение области применения путем обеспечения сравнения любых двух чисел из диапазона представления чисел.

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

Устройство содержит входные регистры 1.1-1.2, блок 2 хранения констант, два блока умножения по модулю 3.1 и 3.2, два сумматора по

20 модулю 4.1 и 4.2, два блока сравнения 5.1 и 5.2, коммутатор 6, узел

7 управления и выходные шины 8.18.3 устройства, выходные управляющие шины 9.1-9.3.

Блок 7 управления содержит элемент И 10, триггер 11, счетчик по модулю (и-1) 12 (и — число оснований), элементы 13 и 14 задержки, элемент ИЛИ 15, шину 16 "Пуск" устройства, тактовую шину 17 устройства.

Входные регистры 1.1 и 1.2, известные функциональные элементы, выполняемые сдвиговыми, имеют парал- 35 лельно-последовательную структуру, т.е. параллельные коды вычетов записываются последовательно, начиная с младшего вычета, с помощью шины начальной установки. Сумматоры по 40 модулю 4.1 и 4.2 накапливающего типа.

Блоки 5. 1 и 5.2 сравнения известные функциональные элементы, обеспечивающие запоминание результата сравнения и имеющие управляющие входы, 45 .по которым поступает импульс, разрешающий сравнения. Блоки сравнения имеют три выхода, соответственно первый выход — выход "равенства11, второй — выход больше", третий — 50 выход "меньше". Входы первого блока

5.1 сравнения соединены: с выходами сумматоров по модулю 4.1 и 4.2. Выходы входных регистров 1.1 и 1.2 подключены к первым входам блоков умножения по модулю 3.1 и 3.2, которые выполняются комбинационным. способом, а также к первому и второму входам второго блока сравнения 5.2 соответ1256013

10 аналогично

2 (2) где P„. — основание системы вычетов;

Т.,n;

n — - число оснований. 5 (и

R = - (3) — целая часть, кояк у; торая представля.

° ет собой ядро числа N, К

1,2.

Из (1) и (2) следует, что для сравнения N u N иногда достаточно сравнить R и R„, Если же В,.

1 1

Rpf ф то необходимо сравнивать 01. и 15

Р;, что позволяет сравнить числа

N u N

Известно, что число N может быть получено, как

Ы„= ed, р — rP„, (4) 20 где 1=1 p — ортонормированные

t векторы системы вычетов;

r — - ранг числа;

Р fII, — диапазон представле-25 ния чисел.

Подставив (4) в (3), получаем

h ;, -гР„

=1 (5)

P 3D

I 1 так как P является делителем чисел

Р„, В;, то справедливо

В . В - 1

= -

N P 1 t ) Я.

В Р

+ ... + -П, „— r-1 р или R = К g + R,(+ ... +

r4 в, в2

+ RBd + ... + Re d. rP где R = R . = - — "- P = -

7; в; Р; ai P иначе говоря, (6) будет им ть вид х (mod Р„; ). (7)

Коэффициенты R в для выбранной системы оснований являются постоянными, для того чтобы они были наименьшими, необходимо осуществлять деление на старшее основание У„, получаем

/P R

Xdl /Р„

Пример. Пусть имеем систему оснований 1",= 2; У = 3; Р = 5, P, = 7; тогда Р = П,У; = 210 орто. I-=1 нормированные векторы системы будут рав"ы В = 105; Ва = 70; Bç = 126

Р4 - 120.

Вычисляем коэффициенты

105 70

R =- — =15 R = — =10

8< 7 в 7

126 120-1

R — 18 R = — — — = 17

B 7 в4 7

R = — -=30.

Nfl 7

Отсюда

R Ä— — ; //1Ю,/ЭО, + /10Ы,/30 +

+ /18,30 + 17Ы,/30/Эб

Пусть необходимо сравнить числа

N, = (1, 2, 2, 3) и И = (1, 1, 4, К1 //15. 1/30 +10. /30+/18. 2/30

+ /17. 3/30/30 = 62 30 2.

R<,= !15.1/30 + /1Д.1/30 +, + /18.4/30 + /17.5/30/30 = /62/30

2, т. е. получаем, что R R, следовательно, необходимо сравнивать вычеты по старшему основанию < и

4 р4, так как,= 3; /34= 5; следоваУстройство для сравнения чисел в модулярном,коде работает следующим образом.

В исходном состоянии во входные регистры 1.1 и 1.2 записаны коды вычетов Ы, -;, Ы„. и р, —. p„, начиная с младших вычетов oL и р, котооые

1 1 поступают с выходов входных регистров 1.1 и 1.2 на входы блоков умножения по модулю 3.1 и 3.2, на другие входы которых с выхода блока 2 хранения констант подается код ядра R так как счетчик 11 по модулю (и-1) обнулен. По окончании переходных процессов на выходах блоков 3.1 и

3.2 умножения по модулю появятся коды величин /Rp o(/1„„и /В.,/Р„„ соответственно.

На входе блока 5 ° 2 сравнения будут находиться коды вычетов С„ и но поскольку на управляющем входе данного блока присутствует потенциал логического "О", то сравнение производиться не будет.

С приходом запускающего импульса на шине 16 "Пуск" устройства триггер

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

Первый тактовый импульс ТИ "защелкнет" коды /с(, R @,/Р„„ и /p, R» /Р в сумматорах по модулю 4. 1 и 4.2 соответственна и сдвинет содержимое регистров 1.1 и 1.2, на выходе которых появятся коды вычетов 4 и 8

Кроме того, первый ТИ увеличивает содержимое счетчика по модулю (n-1) 12560

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

Устройство для сравнения чисел в модулярном коде, содержащее два входных регистра, первый и второй

12 на единицу, что приводит к выбору в блоке 2 хранения констант второго ядра R . Таким образом, на выходе

8т блоков умножения по модулю 3.1 и

3.2 появятся коды величин /к 8 d /P

+ 8у g и /R8< p /Р„„соответственно. Второй ТЙ увеличивает содержимое сумматоров по модулю 4,1 и 4.2 на величины /К8 4

Далее работа устройства аналогич- 10 на описанной. На (п-1) такте в сумматорах по модулю 4.1 и 4.2 будут находиться коды величин / ; R ./Р„„ и / ;К,/Р„„ соответственно, а на

1=! информационные входы сумматоров по 15 модулю 4.1 и 4.2 с выходов блоков умножения по модулю 3.1 и 3.2 поступают коды /R („/Р„„и /К „p„/Р

Импульс перейолйения с выхода переполнения счетчика 12 по модулю (n- 20

-1) устанавливает триггер 11 в нулевое состояние, тем самым запрещает прохождение ТИ через элемент И

10, и через время, определяемое элементом 13 задержки, зафиксирует в сумматорах 4.1 и 4.2 числа /R с „/P и /К P„/Р „, таким образом, в сумматорах по модулю 4.1 и 4.2 будут находиться значения ядер

К . / сс К,/Р и R, Щ 1 81 п которые поступают на входы блока

5. 1 сравнения.

На входы блока 5.2 сравнения с выхода регистров 1.1 и 1.2 поступают З5 .коды старших вычетов д-„ и В„. Импульс переполнения, задержанный элементом 14, разрешает сравнение в блоках 5.1 и 5.2 сравнения. Результаты сравнения появятся на одном из 40 трех выходов блоков 5.3 и 5.2 сравнения, Коммутатор б в зависимости от потенциала на входе управления, т.е. выходе "равенство" блока 5. 1 сравнения, подключает на выход первую груп-45 пу ВХОДОВ или Вторую» Если К К то на выходе коммутатора 6 резуль2 тат сравнения определяет значение на выходе блока 5.1 сравнения. Если

R„ = К„, то на выходе коммутатора 50

"1 "2

6 результатом сравнения будет значение на выходе блока 5.2 сравнения.

13 Ь сумматоры по модулю, блок хранения констант, два блока сравнения и узел управления, содержащий элементы

И, ИЛИ и триггер, причем выходы сумматоров по модулю соединены соответственно с первой и второй группами входов первого блока сравнения, о тл и ч а ю щ е е с я тем, что, с целью расширения области применения путем обеспечения сравнения любых двух чисел из диапазона представления чисел, в устройство введены первый и второй блоки умножения по модулю и коммутатор, а в узел управления введены счетчик по модулю (n-1), где м — число оснований, и два элемента задержки, причем вход пуска устройства подключен к входу установки в единичное состояние триггера узла управления, прямой выход которого соединен с первым входом элемента И, второй вход которого соединен с тактовым входом устройства, а выход подключен к первому входу элемента ИЛИ и счетному входу счетчика по модулю (-1), выход переполнения которого соединен с входом установки в нулевое состояние триггера и через первый элемент задержки " с входом второго элемента задержки и вторым вхо" дом элемента ИЛИ, выход которого подключен к входам управления сдви-, гом входных регистров и входам управления записью сумматоров, выход второго элемента задержки узла управления подключен к управляющим входам блоков сравнения, выходы которых соединены с информационными входами соответственно первой и второй групп коммутатора, управляющий вход кото : рого подключен к выходу равенства первого блока сравнения, а выходы являются выходами устройства, выходы первого и второго входных регистров подключены соответственно к первой .и второй группам входов второго блока сравнения и первым группам входов соответственно первого и второго блоков умножения по модулю, вторые группы входов которых соединены с выходами блока хранения констант, входы:которого соединены с выходами разрядов счетчика по модулю (-1) узла управления, выходы первого и второго блоков умножения по модулю соединены с информационными входами соответственно первого и второго сумматоров по модулю.

1256013 иг.

Составитель Е.Иванова

Техред Л.Сердюкова . Корректор В.Синицкая

Редактор П.Коссей

Заказ 4824/48

Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная, 4