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

If IS

/7.

го ii f а

l

(Л

с

ел ьэ

о

ел

о

Од

tf

Фиг.

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

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

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

Разряд устройства (фиг. t) содержит одноразрядную схему 1 сравнения основной элемент ИЛИ 2, dc- новной элемент ИЗ, первый элемент НЕ 4, первый и второй дополнительные элементы И 5 и 6, четвертый допооганительньй элемент И 7, третий и шестой, дополнительные элементы Н 8 и 9, второй элемент. НЕ 10, пя- тый допопннтельный элемент И t1, дополнительный элемент ИЛИ 12, третий элемент НЕ 13, седьмой дополня- тельйый элемент И tA,, прямой и инверсный входы 15 и 16 разряда перво

го числа устройства;, прямой и инверсны й входы 17 и 18 разряда второго числа устройства, восьмой дополнительный элемент И 19, четвертый вход 20 задания режима устройства, с первого по третий входы 21-23 задания режима устройства, сигнальные выходы 24 и 25 первой и второй групп устрой- ства вход 26 разрешения и выход 27 Равно схемы 1 сравнения.

Одноразрядная схема 1 сравнения (фиг. 2) содержит первый и второй элементы И-НЕ 28 и 29 и элемент И 30, причем вход 26 соединен с первыми входами элементов И-НЕ 28 и 29, выходы которых являются выходами 24 и 25 схемы 1 сравнения и соединены с входами элемента И 30, выход которого является выходом 27 схемы 1 сравнения вход 26 которой соединен с третьим входом элемента И 30, входы 15 н 18 соединены соответственно с вторым и третьим входами элемента Й-ИЕ 29, входы 16 и 17 - соответ- ственно с вторым и третьим входами элемента И-НЕ 28,

Известна двоичная t-система счис- лейИя-р задаваемая выражением

V.(i)0при i О

1при о i - t

(О

i-n

% Vt(i-t-j) при i- 7 t, где t 0,1,2,3.,,,.

При получаем ряд двоичной ti системы счисления;

Изобретение относится к области вычислительной техники и может быть использовано для сравнения чисел в двоичной классической системе счисления, P-кодах и оптимальных P-кодах Фибоначчи, минимальной, оптимальной, пакетной, пакетно-оптимальной формах изображений в двоичной избыточной системе счисления. Изобретение позволяет расширить функциональные возможности за счет способности сравнивать числа в различных формах изображений двоичной избыточной системы счисления и P-кодах Фибоначчи. Устройство содержит в каждом разряде одноразрядную схему 1 сравнения, элементы ИЛИ 2 и 12, элементы И 3,5,6,7,8,9,11 и 14 и элементы НЕ 4,10 и 13 с соответствующими связями. 2 ил.

1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 ,., (2)

В двоичной t -системе счисления возможно.представление чисел в нескольких формах изображений.

|В двоичной t -системе счисления любое натуральное А можно представить в биде

Л i: а; ч , (i), где а, ,(3)

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

Мощность минимального кода состаляет величину ц/(п+1). В оптимальной форме коэффициенты а. многочлена (3) определяются из условия

п

0приФ(п-1)А- Х,,(п)

1приФЛп-1)4А- 1 (k) , (4)

где , (п) О при п 0

|(n-t-j)-f1 при п О, j,(n) - мощность оптимального

кода,

Характерной особенностью оптимальных изображений является то, что мехсду двумя соседними единицами не менее t и не более 2t нулей.

Любое число в пакетной форме изображений можно представить в виде

А 110.,.011,,.0110,..0110.,.0

т.

m

k-1

nik

Пакетный код обладает следующими свойствами:

мощность М(п)

число нулевых символов п. П: / 3 (j 1, k-1). Любое число

V, (п+3), m

O.nj В

можно записать в пакетно-оптимальной

форме в виде

J

.0110,...11Ch..0 Я, ЛС

л,

Пакетно-оптимальный код обладает следующими свойствами:

мощность М(п) (f, (п+1), число нулей между пакетами

lT3i г Ь2.

Устройство позволяет сравнивать Фибоначчиевый код и оптимальный код для любого натурального числа t р, а минимальный, пакетный, пакетно- оптимальнь й коды только для .

Анализ свойств минимальной, оптимальной, пакетной, пакетно-оптимальной форм изображений в двоичной t -системе счисления позволяет сделать вывод, что если числа, подлежащие сравнению в i-м разряде, равны и имеют единичное состояние, то для iинимaльнoй формы изображений следующий сравниваемый разряд (х-5)-й (это объясняется тем, что в минимальной форме количество нулей между единицами 4), для оптимальной фор1Ф1 ; изображений двоичной t-системы счисления, оптимального Фибоначчи (i-t-1)-й, (t р) разряд, для пакетной фор№1, если старший разряд паке- та, то (1-1)-й, если младший, то (х-4)-й разряд, для пакетно-оптимальной, если старший разряд пакета (1-1)-й разряд, если младший (1-2)-й разряд подвергается операции сравнения .

Вход 20 служит для организации

операций сравнения в минимальной форме изображения чисел.

Вход 21 служит для организации сравнения чисел в Р-коде Фибоначчи, в оптимальном Р-коде Фибоначчи, оптимальной форме изображений чисел в , ; двоичной t-системе счисления.

Вход 22 служит для организации сравнения пакетной формы изображений числаJ для сравнения чисел в двоичной классической системе счисления.

Вход 23 слулит для организации сравнения в пакетно-оптимальной форме изображений в двоичной избыточной системе счисленин.

10

;

15

20

25

30

35

40

45

50

55

6

Устройство (фиг. 1) работает следующим образом.

При сравнении Р-кодов и оптимальных Р-кодов Фибоначчи, а также оптимальной формы изображений двоичной избыточной системы счисления (при условии, что сравниваемые i-e разряды равны и единичны) на выходе 27 одноразрядной схемы 1 сравнения i-x разрядов появляется единичный сигнал, поступаклций на вход элемента И 3, так как числа в рассматриваемом разряде равны и единичны, на входе 16 присутствует нулевой потенциал, который закрывает элемент И 3 и приводит к появлению на выходе элемента НЕ 4 единичного сигнала, последний поступает на вход элемента И 5, и если на входе 21 присутствует сигнал разрешения сравнения в рассматриваемых формах, то на выходе элемента И 5 формируется единичный сигнал, поступаюпщй на вход элемента ШВ1 2 (i-2)-ro разряда и разрешающий сравнение чисел в (i-2)-x разрядах.

Если же i-e разряды равны и имеют нулевое значение, на выходе 27 формируется также единичный сигнал, который при наличии сигнала с выхода ИЛИ 2 и единичного сигнала с инверсного выхода 16 формирует единичный выходной сигнал, запирающий через элемент НЕ 4 элементы И 19, 5, 6,8 и разрешающий опрос следующего младшего (i-l)-ro разряда устройства.

При сравнении чисел в минимальной форме изображений устройство работает аналогично, лишь сигнал, разрешающий сравнения с выхода элемента И 19 при равных единичных разрядах, подается на вход элемента ИЛИ 2 (i-5)-ro разряда.

При сравнении чисел в пакетной форме изображений управляющий сигнал подается на вход 22. При нулевых равных числах i-ro разряда процесс сравнения протекает аналогично. При равных единичных разрядах единичный - сигнал формируется на выходе элемента И 6 , и если на втором входе эле- . мента И 7 присутствует логическая единица, свидетельствующая о том, что предьздущий (1+1)-й разряд содержит единичные значения первого и вто рого чисел, то на выходе элемента И 7 формируется сигнал, поступающий на вход элемента ИЛИ 2 (i-4)-ro разряда, если же на втором входе элемента И 7 логический ноль, тогда единичный сигнал вьфабатьшается на выходе элемента И 11, поступая на вход элемента ИЛИ 2 (i-l)-ro разряда.

При сравнении чисел в пакетно- рптимальной форме изображений сигнал управления подается на вход 23 и про цесс сравнения протекает аналогично процессу сравнения в пакетной форме изображений, только при наличии единичного сигнала на втором входе элемента И 9 сигнал с выхода элемента |И 9 поступает на вход элемента ;ИЛИ 2 (i-2)-ro разряда. При сравнении чисел в классичес кой двоичной системе счисления единичный сигнал подается на вход 22 или вход 23, на вторые входы элементов И 7 и 9 подается постоянный ноль приводящий к тому, что единичные равные старшие разряды не расцениваются в i-M разряде как старшие единичные разряды пакета, и сигнал поступает на вход последующего младшего разряда. Для удобства реализации данной операции сравнения целесообразно к выходу элемента ИЛИ t2 подключить первый вкод еще одного элемента И, на второй вход которого подавалась бы логическая единица при сравнении в пакетной и пакетно-оп- тимальной формах изображений и логический ноль при сравнении в классической двоичной системе счисления а выход являлся бы соответствующим выходом.

в устройстве при t О сравнение протекает в классической двоичной системе счисления через выход элемента И 5 при единичном потенхщале на входе 21.

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

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

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

10

15

20

25

-, ,

5205068

одноразрядной схемы сравнения i-ro разряда устройства соединены соответственно с прямым и инверсным входами i-ro разряда первого числа устройства, третий и четвертый информационные входы одноразрядной схемы сравнения i-ro разряда устройства соединены соответственно с прямым и инверсным входами i-ro разряда второго числа устройства, инверсные выходы Меньше и Больше одноразрядной схемы сравнения i-ro разряда устройства являются i-ми сигнальными выходами соответственно первой и второй групп устройства, вход запуска которого соединен с входом разрешения одноразрядной схемы сравнения пто разряда устройства, прямой выход Равно одноразрядной схемы сравнения первого разряда устройства является выходом Равно устройства, рысход основного элемента И i-ro разряда устройства соединен с первсм входом основного элемента ИЛИ (i- -t)-ro разряда устройства в каждом i-M разряде, кроме п-го, устройства выход основного элемента ИЛИ . соединен с входом разрешения одноразрядной схемы сравнения, в калщом i-M разряде устройства, кроме первого, вход разрешения и второй информационный вход одноразрядной схемы сравнения соединены соответствен- но с первым и вторым входами основ- JHoro элемента И, отличаю30

35

0

0

5

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

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

соответственно с первым и вторым вхо- 25 5)-го разряда устройства, выход додаш1 дополнительного элемента ИЛИ, в каждом i-M разряде, кроме с первого по четвертый, устройства выход первого элемента НЕ и четвертый вход задания режима устройства соединены соответственно с первым и вторым

10

2050610

входами восьмого дополнительного элемента И, выходы пятого и седьмого дополнительных элементов И i-ro разряда устройства соединены соответственно с вторым и третьим входами основного элемента ИЛИ (i-l)-ro разряда устройства, выход первого дополнительного элемента И i-ro разряда устройства соединен с четвертым входом основного элемента ИЛИ (i-t-l)-ro (,1... - параметр системы счисления) разряда устройства, выход шестого дополнительного элемента И i-ro разряда устройства - с пятым входом основного элемента ИЛИ (i- 2)-го разряда устройства, выход четвертого дополнительного элемента И i-ro разряда устройства - с шестым входом основного элемента ШШ (i- 4)-го разряда устройства, выход восьмого дополнительного элемента И i-ro разряда устройства - с седьмым входом основного элемента ИЛИ (i15

20

полнительного элемента ИЛИ i-ro разряда устройства - с объединенными вторыми входами четвертого .и шестого дополнительных элементов И ( разряда устройства.