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

11

Изобретение относится к вычислительной технике и может быть использовано в системах передачи информации, устройствах обработки, использующих модулярную арифметику, а также в составе многопроцессорных магист- рально-модульньк информационно-управ ЛЯЮ1ЦИХ систем.

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

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

Устройство содержит входные ре- гис1 ры 1.1-1.2, блок 2 хранения констант, два блока умножения по модулю 3.1 и 3.2, два сумма.тора по модулю 4.1 и 4.2, два блока ния 5.1 и 5.2, коммутатор 6, узел 7 управления и выходные шины 8.1- 8.3 устройства, выходные управляющие шины 9.1-9.3.

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

Входные регистры 1.1 и 1.2, известные функциональные элементы, выполняемые сдвиговыми, имеют параллельно-последовательную структуру, т.е. параллельные коды вычетов Записываются последовательно, начиная с младшего вычета, с помощью шины начальной установки. Сумматоры по модулю 4.1 и 4.2 накапливающего тип Блоки 5.1 и 5.2 сравнения известные функциональные элементы, обеспечи- вакнцие запоминание,результата сравнения и имеющие управляющие входы, по которым поступает импульс, разрешающий сравнения. Блоки сравнения имеют три выхода, соответственно первый выход - выход равенства, второй - выход больше, третий - выход меньше. Входы первого блока 5.1 сравнения соединены с выходами сумматоров По модулю 4.1 и 4.2. Выходы входных регистров 1.1 и 1.2 поключены к первым входам блоков умно жения по модулю 3.1 и 3.2, которые выполняются комбинационным.способом а также к первому и второму входам второго блока сравнения 5.2 соответ

0

5

0

25

50 55

30

35

ственно. Блок 2 хранения констант, известный функциональный элемент, может выполняться на ПЗУ, в котором хранятся коды ядер К„/ для выбранной системы оснований, выход необходимого ядра определяется кодом, поступающим на адресньй вход блока 2 хранения констант. Таблица истинное-, ти блока хранения констант для рассмотренного примера приведена.

Выход блока 2 хранения констант подключен к вторым входам блоков 3.1 и 3.2 умножения по модулю, выходы которых подключены к информационным входам сумматоров по модулю 4.Г и 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 хранения.констант.

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

I

Выход

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

Любое целое число NI, представленное

в модулярном коде как N (2, , 2,..., 2), может быть выражено в позиционной системе как

N, -Pi RN, - . 1

аналогично

N, P,R,,(2)

где Я-- основание системы вычетов;

i Т;п; п - число оснований.

N.. -„. р (3J - целая часть, ко J торая представля ет собой ядро числа N , К 1,2.

Из (1) и (2) следует, что для сравнения N и N иногда достаточно сравнить R N, и N Если же R , то необходимо сравнивать оС и -, что позволяет сравнить числа N, и Nj.

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

N , - rP, (4) где - - ортонормированные

векторы системы вычетов;г - ранг числа;

i-1

ния чисел.

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

R

Нк

П PJ - диапазон представле-25 в модулярном ;коде работает следующим

образом.

В исходном состоянии во входные регистры 1.1 и 1.2 записаны коды XCN вычетов о. и р, -г-р , начиная 30 с младших вычетов оС и я , которые поступают с выходов входных регистров 1.1 и 1.2 на входы блоков умножения по модулю 3.1 и 3.2, на другие входы которых с выхода блока 2 хра- «, нения констант подается код ядра R „ , так как счетчик 11 по модулю (п-1)

HctfP, -гР„

, -1

F,

так как р. является делителем чисел

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

R.

. 5.-.;.

+ м ,р 1

+... 4s

6/, 0,1. -

r. ....-rP.

|ZI RB/-/ 1 n .в . 1

где R,. ; R --.-I

(6)

- f. . Stt.

Bipj %ipj

иначе говоря, (6) будет им°ть вид

, . RB

X (mod ).(7)

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

I - Г R 1 Т1-/

4- 1-1 I , 1 ( /РНППример. Пусть имеем систему оснований f, 2; 3; Яз 5/ Р 7; тогда Р„ П,Р 210 ортонормированные вект6р ь1 системы будут равны В, 105; В 70; В 126; h 120обнулен. По окончании переходных процессов на выходах блоков 3.1 и ,3.2 умножения по модулю появятся

40

коды величин /Ro ot./r

Р Т П П

, Р,/РГ,Н

45

50

лН

i 1

Rg.x BI

55

соответственно.

На входе блока 5.2 сравнения будут находиться коды вычетов ci, и Р:,, но поскольку на управляющем входе данного блока присутствует потенциал логического О, то сравнение производиться не будет.

С приходом запускающего импульса на шине 16 Пуск устройства триггер 11 устанавливается в единичное состояние и разрешает прохождение так- товьм импульсам через элемент И 10.

Первый тактовый импульс ТИ за- коды ,/P hb и /Э,Кз, в сумматорах по модулю 4.1 и 4.2 соответственно и сдвинет содержимое регистров 1.1 и 1.2, на выходе которых появятся коды вычетов о(,, и /3 . Кроме того, первый ТИ увеличивает содержимое счетчика по модулю (п-1)

5

2560134

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

- ° - ш.

8,- - - 105

120-1

6

- - 15- R

- -у- - 15, Rj,

R

В,

R.

- - 1Я. R

--7 - Вц

2l 30.

17;

Отсюда

RW 7 //1. + /1 Sot, 30 + 17o(j/30/30

Пусть необходимо сравнить числа N, (1, 2, 2, 3) и NJ (1, 1, 4, 5), тогда f- .

//15.1/30 +10.2/30+/18.2/30 + /I7l3/30/30 62 30 2.

RN, //15.1/30 + /10.1/30 + + /18.4/30 + /17.5/30/30 /62/30 2, . т.е. получаем, что R

слеN. N.J.

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

так как

3 р4 следовательно, ot - Р , т.е. N N. Устройство для сравнения чисел

обнулен. По окончании переходных процессов на выходах блоков 3.1 и ,3.2 умножения по модулю появятся

0

коды величин /Ro ot./r

Р Т П П

, Р,/РГ,Н

5

0

5

соответственно.

На входе блока 5.2 сравнения будут находиться коды вычетов ci, и Р:,, но поскольку на управляющем входе данного блока присутствует потенциал логического О, то сравнение производиться не будет.

С приходом запускающего импульса на шине 16 Пуск устройства триггер 11 устанавливается в единичное состояние и разрешает прохождение так- товьм импульсам через элемент И 10.

Первый тактовый импульс ТИ за- коды ,/P hb и /Э,Кз, в сумматорах по модулю 4.1 и 4.2 соответственно и сдвинет содержимое регистров 1.1 и 1.2, на выходе которых появятся коды вычетов о(,, и /3 . Кроме того, первый ТИ увеличивает содержимое счетчика по модулю (п-1)

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

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

Далее работа устройства аналогич- 10 путем обеспечения сравнения любых на описа нной. На (п-1) такте в сум- двух чисел из диапазона представления чисел, в устройство введены первый

--,-,-- .,.-,, Р|. „ и второй блоки умножения по модулю и

и /fir i соответственно, а на коммутатор, а в узел управления вве- информационные входы сумматоров по 15 дены счетчик по модулю (и-1), где

3.2 появят ся коды величин /R о( / и /Rg,j соответственно. Второй ТИ увеличивает содержимое сумматоров по модулю 4.1 и 4.2 на вели

3/

чины ,,

и /РВ../Р.П

маторах по модулю 4.1 и 4.2 будут находиться величин /.й1 Rg,j/Р

/ .Г - Л Т . 1, .

модулю 4.1 и 4.2 с выходов блоков умножения по модулю 3.1 и 3.2 поступают коды ,/ и , Импульс переполнения с выхода переполнения счетчика 12 по модулю (п- -1) устанавливает триггер 11 в нулевое состояние, тем самым запрещает прохождение ТИ через элемент И 10, и через время, определяемое элементом 13 задержки, зафиксирует в сумматораз 4.1 и 4.2 числа /R и /R p,/P,J , таким образом, в сумматорах по модулю 4.1 и 4.2 будут находиться значения ядер

RM, ,VPnn - ,Re,/P.,,

которые поступают на входы блока 5.1 сравнения.

На входы блока 5.2 сравнения с

выхода регистров 1.1 и 1.2 поступают 35 рого элемента задержки узла управлеоцы старших вычетов ot,и р . Им-- пульс переполнения, задержанный элементом 14, разрешает сравнение в блоках 5.1 и 5.2 сравнения. Результаты сравнения появятся на одном из 40 трех выходов блоков 5.3 и 5.2 сравнения. Коммутатор 6 в зависимости- от потенциала на входе управления, т.е. выходе равенство блока 5.1 сравнения, подключает На выход первую груп-45 пу входов или вторую. Если R, 5 R, то на выходе коммутатора 6 резуль- тат сравнения определяет значение на выходе блока 5.1 сравнения. Если RJ, R , то на выходе коммутатора 50 6 результатом сравнения будет значение на выходе блока 5.2 сравнения.

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

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

55

- - число оснований, и два элемента задержки, причем вход пуска устройства подключен к входу установки в единичное состояние триггера узла управления, прямой выход которого соединен с первым входом элемента И, второй вход которого соединен с тактовым входом устройства, а выход подключен к первому входу элемента PfflH и счетному входу счетчика по модулю (h-1), выход переполнения которого соединен с входом установки в нулевое состояние триггера и через первый элемент задержки - с входом второго элемента задержки и вторым входом элемента ИЛИ, выход которого подключен к входам управления сдви- ; гом входных регистров и входам управления записью сумматоров,выход вто

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

iZ

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

Фиг. г

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

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

Заказ 4824/48Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

Фиг. I

.J

/J

r

/«

ff.2

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