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

Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах, функционирующих в системе остаточных классов (СОК).

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

На чертеже приведена функциональная схема устройства.

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

Пусть задана СОК с основаниями Pi,

п

Р2Рп и диапазоном Р Р|,ортогональi - 1

ными базисами Bi, 62Вп, коэффициентами ядра Г1 , Г2,..., Гп.Тогда ядро числа N - (ом , оаOn) вычисляется по формуле

п

RN RrOimodRD ,(1)

I 1

где RD (ядро диапазона Р) равно

RD iri|- ,(2)

i 1 п

a RI ядра ортогональных базисов системы равны

где X - целая часть X.

Пусть числа из диапазона О, Р/2 положительные, а из диапазона Р/2. Р - 1 - отрицательные. Причем

N, для N О N

N- Р для N О

Для того, чтобы сравнить два числа А и В из диапазона Р, необходимо определить знак разности этих чисел, Если (А - В) больше нуля, то А больше В и наоборот.

Известно также, что ядро суммы Ni + N2 двух чисел равно п

RNI +N2 RNI +R№ +2,т Ј (4)

i 1

где d 0 при оц1 +о PI ; Ј| 1 при

а1 + о PI Из (4) следует, что если при сложении чисел Ni и NZ произошел выход за диапазон, то на основании (Ni + №) (Ni + N2) mod Р + Р получаем

ист

(5)

RNI + N2 RNI + N2 + RD.

ист

где RNI -I- N2 истинное значение ядра суммы Ni + N2, лежащей внутри диапазона Р.

Тогда, обозначив через М Р/2 с ядром и через С А - В с ядром Rc, получаем

правило определения знака числа С. Если ROM меньше RD, то число С положительное. Если ROM больше или равно RD. то число С отрицательное.

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

Остатки сравниваемых чисел по входным шинам 1 и 2 подаются на входы входного регистра 3, первой 13 и четвертой 16

групп элементов И и входного регистра 4 и второй 14 и третьей 15 групп элементов соответственно. С выходов входных регистров 3 и 4 остатки сравниваемых чисел подаются на входы сумматора 5 группы, которые являются модульными и работают по основаниям СОК. В сумматорах 5 группы производится вычитание сравниваемых чисел. С выходов сумматоров 5 остатки числа, равного разности сравниваемых чисел, подаются на входы

первой группы 7 блоков хранения констант и на первые входы сумматоров 6 группы. иторые входы сумматоров 6

группы соединены с первой шиной 22 константы устройства, по которой подаются остатки числа М, равного середине диапазона Р. Сумматоры 6 группы являются модульными, а выходы их являются выходами переноса результата суммирования и подключены к входам второй группы 8 блоков хранения констант. В блоках 7 хранения констант первой группы записаны значения произведений ядер ортогональных базисов RI на значения остатков (%, а в блоках 8 хранения констант записаны значения коэффициентов т. Таким образом, с выходов блоков 7 хранения констант произведения ядер ортогональных базисов на остатки поступают на входы первого сумматора 9, работающего по модулю RD. Т. е. в сумматоре 9 вычисляется значение ядра числа С, равного разности сравниваемых чисел, а во втором сумматоре вычисляется значение величины

п

firi . С выходов первого 9 и второго 10

i 1

сумматоров значения этих величин поступают на первые входы третьего сумматора 11, на второй вход 23 которого подается значение ядра RO числа М. На выходах третьего сумматора 11 таким образом появится значение ядра суммы числа М и числа С, равного разности входных чисел, которое подается на первый вход схемы 12 сравнения. Второй вход схемы 12 сравнения соединен с третьим входом 24 константы устройства, по которому подается значения RO ядра диапазона. Схема 12 сравнения производит сравнение величины, поступаемой с третьего сумматора 11 с ядром диапазона. Если величина на выходе третьего сумматора 11 меньше ядра диапазона RD, то число равное разности сравниваемых чисел больше нуля и, следовательно, число, поступающее по входной шине 1, больше числа, поступающего по шине 2. В этом случае нулевой сигнал со схемы 12 сравнения поступит на вторые входы первой 13 и второй 14 групп элементов И через элемент НЕ 17 и разрешит поступление большего числа через группу элементов ИЛИ 18 на первый выходной регистр 20 и выходную шину 25, а меньшего через группу элементов ИЛИ 19 на второй выходной регистр 21 и выход 26. Третья 15 и четвертая 16 группы элементов И заперты нулевым сигналом со схемы 12 сравнения.

Если значение, поступающее с сумматора 11 больше или равно величине ядра диапазона, то число, равное разности сравниваемых чисел, отрицательное, а значит число, подаваемое на шину 1, меньше числа, подаваемого на шину 2. В этом случае на выходе схемы 12 сравнения присутствует

единичный сигнал, который открывает третью 15 и четвертую 16 группы элементов

50 И и через элемент НЕ 17 закрывает первую 13 и вторую 14 группы элементов И. Большее число с выходов третьей группы 15 элементов И через первую группу 18 элементов ИЛИ поступит на первый выходной регистр

5 20 и на выход большего числа 25. Меньшее число с выходов четвертой группы 16 элементов И поступит на входы второй группы 19 элементов ИЛИ и далее на второй выходной регистр 21 и выход 26.

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

Пусть задана СОК с основаниями Pi 9, Р2 10, Рз 11 и диапазоном Р pix p2X рз

0 990, ортогональный базисами Bi 550, 82

-891, Вз 540. Тогда М 495 (причем

четность одного из оснований СОК не обязательна. В этом случае М (Р - 1)/2). Вы- 5 брав ri -4, Г2 0, гз 5. имеем на основании (2) и (3) RI 6, R2 9, R3 - 5 и RD Ю. А ядро RO числа М (0, 5, 0) равно пяти (Ro 5).

Пример 1. Сравним число А 200 0 (2,0, 2)иВ 100(1,0, 1)С А-В(2, 0. 2)- -(1,0, 1} (1.0, 1).

Re (Ri«i + R2«2 + Ra«3 ) mod RD - (6x1+9xO+5x 1)mod 10 1),

5 Rc+M Rc+Ro+2)afl- 1 +5 + 0 6.

i 1

так как Re + м 6 меньше Кд - 10, то С больше нуля, а значит А больше В.

Пример 2. Сравним А 100 (1,0, 1) n и В 200 (2, 0, 2) С В А - В - (1, 0. 1) - (2, О, 2) (8, 0, 10).

Re (6x8+0x9+5x10)(nod10 8,

ROM 8+5+0 13. Так как ROM больше RD, то число С отрицательное, следователь- с но, А меньше В.

Пример 3. А - 890 (8, 0, 10), В - 100 (1, 0. 1), С - А - В (7. О, 9). RC (7x6+ 0x9+ + 5x9)mod10 7. Re-ни 7+5+0 12 больше RD, значит А меньше В.

0 Пример 4. А 100 (1,0, 1). В 890 (8, 0, 10), С - А - В (2, 2. 2). Re (2x6 + 0x9 + +2x5)mod10 2. ROM 2 + 5 + 0 7 меньше RO. А больше В.

Пример 5. А 890-(8,0, 10), В-790 5 - (7, 0, 9), С - (1. О, 1). Rc (6x1 + 9x0 + +5x1)mod10 1. ROM 1 + 5 + 0-6 меньше RO. А больше В.

Пример 6. А 666 - (0, 6, 6). В - 790 (7, 0. 9), С (2. 6. 8). Re (2x6 - 6x9 + 8x5)mod10 6. ROM 6 + 5 + 1x0 11 больше RD, следовательно, А меньше В.

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

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

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

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

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

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

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

Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах, функционирующих в системе остаточных классов (СОК). Цель изобретения - расширение области применения за счет возможности сравнения чисел в положительном и отрицательном диапазонах без потери непозиционности. Устройство содержит входные регистры 3, 4, состоящие из N подрегистров (N - количество оснований СОК), сумматоры 9, 10, 11, группы сумматоров 5 и 6 по N сумматоров в каждой, группы блоков 7, 8, хранения констант схему сравнения 12, группы элементов И 13 - 16, группы элементов ИЛИ 18, 19, выходные регистры 20, 21. Группы сумматоров 5, 6, группы блоков 7, 8 хранения констант, и сумматоры 9, 10, 11 формируют код ядра разности (А - В) сравниваемых чисел, который суммируется с ядром числа, разделяющего положительные и отрицательные числа, с учетом переполнений. Полученное число сравнивается с ядром диапазона. Если оно меньше ядра диапазона, следовательно, разность сравниваемых чисел положительна, а значит, А больше В и наоборот. 1 ил.