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

 

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

ССФОЗ СОВЕТСКИХ

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

РЕСПУБЛИК (sg < С 06 F 7/02

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР

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

И А 8TOPCH0MV СВИДЕТЕЛЬСТВУ

15 f6

М и 22 23

CA

ЬР

Ю

С

Ю

С5 (21) 4410452/24-24 (22) 14. 04.88 (46) 07. 11.89. Бюл. II - 41 (72) А.В. Ткаченко (53) 681.325(088.8) (56) Авторское свидетельство СССР

М 1319023, кл. G 06 F 7/49, 1985.

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

Ф 662934, кл. G 06 F 7/02, 1976. (54) УСТРОЙСТВО ДЛЯ СРАВНЕНИЯ ЧИСЕЛ (57) Изобретение относится к области вычислительной техники и может быть использовано для сравнения чисел в двоичной классической системе счисления, Р-кодах и оптимальных

„.80„„1520506 A 1

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

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

Фибоначчи. Устройство содержит в кажцом разряде одноразрядную схему

1 сравнения, элементы ИЛИ 2 и 12, элементы И 3,5,6,7,8,9, 11 и 14 и элементы НЕ 4,10 и 13 с соответствуюцнми связями. 2 ил.

1520506 ный входы 17 и 18 разряда второго числа устройства, восьмой дополнительный элемент И 19, четвертый вход

20 задания режима устройства, с первого по третий входы 21-23 задания режима устройства, сигнальные выходы

24 и 25 первой и второй групп устройства, вход 26 разрешения и выход. 27

"Равно" схемы 1 сравнения.

Одноразрядная схема 1 сравнения (фиг. 2) содержит первый и второй элементы И-HE 28 и 29 и элемент

И 30, причем вход 26 соединен с первыми входами элементов И-НЕ 28 и 29, выходы которых являются выходами

24 и 25 схемы 1 сравнения и соединены с входами элемента И 30, выход которого является выходом 27 схемы 1 сравнения, вход 26 которой соединен с третьим входом элемента И 30, входы 15 и 18 соединены соответственно с вторым и третьим входами элемента

И-ИЕ 29, входы 16 и 17 — соответственно с вторым и третьим входами элемента И-HE 28.

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

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

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

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

Разряд устройства (фиг. 1) содержит одноразрядную схему 1 срав" нения, основной элемент ИЛИ 2, основной элемент И 3,. первый элемент

НЕ 4, первый и второй дополнительные элементы И 5 и 6, четвертый дополнительный элемент И 7, третий и шестой. дополнительные элементы

И 8 и 9, второй элемент НЕ 10, пятый дополнительный элемент И 11, 1 дополнительный элемент ИЛИ 12 третий элемент НЕ 13, седьмой дополнительный элемент И 14 прямой и инверсный входы 15 и 16 разряда первого числа устройства, прямой и инверсЗО

112234579121621283749...(2) h

А =,Е а;, (i), гдеа; е (0 Ц (3)

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

Такие комбинации содержат минимальное число единиц.

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

I на (3) определяются из условия ш ш, В дноичной t -системе счисления возможно представление чисел в нескольких формах изображений.

В двоичной t -системе счисления

1 любое натуральное А можно представить в виде

0 при 0

y (i)= 1 при 0

A+1

V (i-С-j) при i. > t, где t = 0,1,2,3,... . При t= 1 получаем ряд двоичной

t 1--системы счисления: и

0 приФ (n-1)>Л-, a„v,(k) <4,(п) ч при Ф (и-1)аЛ- Х а у (k), (4) где Ф (и) =0 прип<0 -(в t-д)+1 при и б 09

Ф (n} — мощнОсть ОптимальнОгО

1 кода.

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

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

А = 110...011...0110...0110...0

1520506

Пакетный код обладает следующими свойствами: мощность M(n) = g (n+3), число нулевых символов m < = О,п;

n > 3 (j=1, k-1) . Любое число В

3 можно записать в пакетно-оптимальной форме в виде в = 11о...о1 ..01-1о...o»0...0, Я, Я

Пакетно-оптимальный код обладает следующими свойствами: мощность М(п) = Ф, (и+1), число нулей между пакетами Я„=

1 3; Я = 1 2.

Устройство позволяет сравнивать

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

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

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

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

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

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

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

1О

6

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

При сравнении Р-кодов и оптимальных P-кодов Фибоначчи, а также оптимальной формы изображений двоичной избыточной системы счисления (при условии, что сравниваемые i-e разряды равны и единичны) на выходе 27 одноразрядной схемы 1 сравнения

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

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

И 5, и если на входе 21 присутствует сигнал разрешения сравнения в рассматриваемых формах, то на выходе элемента И 5 формируется единичный сигнал, поступающий на вход элемента

HJIH 2 (i-2)-го разряда и разрешающий сравнение чисел в (i-2)-х разрядах.

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

При сравнении чисел в минимальной форме изображений устройство работает аналогично, лишь сигнал, разрешающий сравнения с выхода элемента

И 19 при равных единичных разрядах, подается на вход элемента ИЛИ 2 (i-5)-го разряда.

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

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

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

При сравнении чисел в классической двоичной системе счисления единичный сигнал подается на вход 22 или вход 23, на вторые входы элементов .И 7 и 9 подается постоянный ноль, приводящий к тому, что единичные равные старшие разряды не расцениваются в i-м разряде как старшие единичные разряды пакета, и сигнал поступает на вход последующего младmего разряда. Для удобства реализации данной операции сравнения целесообразно к выходу элемента ИХК 12 подключить первый вход еще одного элемента И, на второй вход которого подавалась бы логическая единица при сравнении в пакетной и пакетно-оптимальной формах изображений и логический ноль при сравнении в классической двоичной системе счисления, 35 а выход являлся оы с ютветствующим выходом.

В устройстве при r = О сравнение протекает в классической двоичной системе счисления через выход элемента И 5 при единичном потенциале на входе 21, Следует отметить, что выполнение сравнения в приведенных формах избыточной системы счисления проис" .ходит существенно бь трее, чем в двоичной классической системе счисления.

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

Устройство для сравнения чисел, содержащее в i-м разряде (х=п-1, n - количество разрядов числа) одноразрядную схему сравнения, в каздом разряде, кроме первого, основной элемент И и в каждом разряде, кроме

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

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

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

It tt выход Равно одноразрядной схемы сравнения соединен с третьим входом основного элемента К, выход которого соединен с входом первого элемента

1520506

1О

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

И, выход четвертого дополнительного элемента И через второй элемент НЕ с вторым входом пятого дополнительного элемента И, выход третьего дополнительного элемента И вЂ” с первыми входами шестого и седьмого дополнительных элементов И, выход шестого дополнительного элемента И через третий элемент HE - r вторым входом седьмого дополнительного эле- 20 мента И, причем в каждом х-м разряде, кроме первого и второго, устройства выходы второго и третьего дополнительных элементов И соединены соответственно с первым и вторым вхо- 25 дами дополнительного элемента ИЛИ, в каждом i-м разряде, кроме с первого по четвертый, устройства выход первого элемента HE и четвертый вход задания режима устройства соединены соответственно с первым и вторым входами восьмого дополнительного элемента И, выходы пятого и седьмого дополнительных элементов И i-го разряда устройства соединены соответственно с вторым и третьим входами основного элемента ИЛИ {i-1)-ro разряда устройства, выход первого дополнительного элемента И 1-го разряда устройства соединен с четвертым входом основного элемента ИЛИ (i-t-1)-ro (t=0,1. ° . — параметр системы счисления) разряда устройства, выход шестого дополнительного элемента И

i-ro разряда устройства — с пятым входом основного элемента ИЛИ (i2)-го разряда устройства, выход четвертого дополнительного элемента И

l ãо разряда устройства — с шестым входом основного элемента ИЛИ (i4)-го разряда устройства, выход восьмого дополнительного элемента И

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