Устройство для сравнения р-кодов фибоначчи

(111662934 ОП ИСАН И ЕизоьгитеНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических Республик(45) Дата опубликования описания 15.05.79(5 06 Г 7/ Государственный комите СССРелам изобретений 53) УДК 681.321.53(72) Авторы изобретени А, П. Стахов и Н, А, Соляниченко анрогский радиотехнический институт им, В. Д, Калмыко(54) УСТРОЙ СТВО ДЛЯ СРАВ Н Е Н ИфИБОНАЧЧИ Д Изобретение относится к области вычислительной техники и может быть использовано для сравнения р-кодов Фибоначчи.Известны устройства для сравнения кодов, содержащие одноразрядные ячейки 5 сравнения, производящие поразрядное, начиная со старших, сравнение двух кодов с целью выявления большего кода, меньшего кода или их равенства 1.Наиболее близким техническим реше нием к данному изобретению является устройство для сравнения кодов, содержащее первый и второй и-разрядные регистры хранения р-кодов Фибоначчи, первый и второй элементы ИЛИ - НЕ, и и-од поразрядных блоков сравнения, причем первый выход каждого одноразрядного блока сравнения соединен с соответствующим входом первого элемента ИЛИ в , второй выход каждого одноразрядного блока 20 сравнения соединен с соответствующим входом второго элемента ИЛИ - НЕ, третий выход каждого из р старших одноразрядных блоков сравнения соединен с управляющим входом последующего одноразрядного блока сравнения, информационные входы каждого одноразрядного блока сравнения соединены с единичными и нулевыми выходами одноименных разрядов первого и второго и-разрядных регистров хранения 30 р-кодов Фибоначчи, управляющий вход одноразрядного блока сравнения старших разрядов является управляющим входом устройства, выход первого элемента ИЛИ - НЕ является первым выходом устройства, выход второго элемента ИЛИ - НЕ является вторым выходом устройства, третий выход одноразрядного блока сравнения младших разрядов является третьим выходом устройства 2).Недостатком известного устройства являются значительные потери времени при сравнении равных р-кодов Фибоначчи, или которые отличаются младшими разрядами.Целью изобретения является ускорение операции сравнения р-кодов Фибоначчи.Поставленная цель достигается тем, что устройство дополнительно содержит (и - р) элементов И, по одному в каждом разряде начиная со старших, (и - р) элементов ИЛИ, по одному в каждом разряде, начиная с младших, причем выход каждого элемента И соединен с первым входом элемента ИЛИ, находящегося в разряде, отстоящем от данного на (р - 1) разрядов, второй вход которого соединен с третьим выходом соответствующего одноразрядного блока сравнения; первые и вторые входы каждого элемента И соединены с единичными выходами соответствующих разрядов10 60 первого и второго регистров хранения р-кодов Фибоначчи, третьи входы каждого элемента И соединены с выходом элемента ИЛИ предыдущего разряда.На фиг. 1 показана функциональнаясхема устройства для сравнения р-кодов Фибоначчи; на фиг. 2 - функциональная схема одноразрядного блока сравнения,Устройство содержит первый п-разрядный регистр р-кодов Фибоначчи 1, второй и-разрядный регистр р-кодов Фибоначчи 2, первый элемент ИЛИ в3, второй элемент ИЛИ - НЕ 4, одноразрядный блок сравнения 5, элемент И 6, элемент ИЛИ 7,На фиг. 2 изображен одноразрядный блок сравнения, состоящий из первого элемснта И - НЕ 8, второго элемента И - НЕ 9, элемента И 10.Устройство работает следующим образом.Числа, подлежащие сравнению, заносятся в соответствующие и-разрядные регистры хранения р-кода Фибоначчи 1 и 2. Единичные нулевые выходы каждого из регистров 1 и 2 соединены со входами соответствующих одноразрядных блоков сравнения, которые производят сравнения одноименных разрядов и-разрядных регистров хранения р-кодов Фибоначчи и выдают сигнал о равенстве или неравенстве одноименных разрядов. При поступлении по шине управления разрешающего единичного сигнала происходит сравнение одноименных старших разрядов. ЕсЛи значения не совпадают и первый код больше второго, то на выходе элемента И - НЕ 8 (см. фиг. 2) исчезнет единичный сигнал, что, в свою очередь, приведет к появлению единичного сигнала на выходе первого элемента И - НЕ 9, что свидетельствует, что первый код больше второго. При этом на выходе элемента И - НЕ 7 единичный сигнал будет отсутствовать и опрос следующей ячейки производиться не будет.Если значения одноименных разрядов не равны и первый код меньше второго, то единичный сигнал появляется на выходе второго элемента И - НЕ 8,Если значения одноименных старших разрядов совпадают и равны 0, то единичный сигнал появляется на выходе элемента И - НЕ 7, что приводит к опросу следующей одноразрядной ячейки сравнения,Если значения одноименных старших разрядов совпадают и равны 1, то единичный сигнал появится на выходе шестого элемента И - НЕ и седьмого элемента И - НЕ. При этом будет произведен опрос ячейки, отстоящей от данной, в сторону младших разрядов, на рразряд,так как в нормальном р-коде Фибоначчи, за каждой 1 в кодовом слове следует не менее р нулей, т. е., если одноименные разряды равны и равны 1, то следующие за ними р разрядов обязательно будут равны и равны 0. 15 20 25 30 35 40 45 50 55 65 Аналогичным образом функционируютостальные одноразрядные ячейки сравнения,Максимальное время получения конечнопго результата равно Т=т,р - ,Ргде п - разрядность сравниваемых кодов,т,ч, время срабатывания одной ячейки,Формула изобретенияУстройство для сравнения р-кодов Фибоначчи, содержащее первый и второй п-разрядные регистры хранения р-кодов Фибоначчи, первый и второй элементы ИЛИ - НЕ, и одноразрядных блоков сравнения, причем первый выход каждого одноразрядного блока сравнения соединен с соответствующим входом первого элемента ИЛИ - НЕ, второй выход каждого одноразрядного блока сравнения соединен с соответствующим входом второго элемента ИЛИ - НЕ, третий выход каждого из р старших одноразрядных блоков сравнения соединен с управляющим входом последующего одноразрядного блока сравнения, информационные входы каждого одноразрядного блока сравнения соединены с единичными и нулевыми выходами одноименных разрядов первого и второго п-разрядных регистров хранения р-кодов Фибоначчи, управляющий вход одноразрядного блока сравнения старших разрядов является управляющим входом устройства, выход первого элемента ИЛИ - НЕ является первым выходом устройства, выход второго элемента ИЛИ - НЕ является вторым выходом устройства, третий выход одноразрядного блока сравнения младших разрядов является третьим выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью ускорения операции сравнения р-кодов Фибоначчи, устройство дополнительно содержит (п - р) элементов И, по одному в каждом разряде, начиная со старших, (и - р) элементов ИЛИ, по одному в каждом разряде, начиная с младших, причем выход каждого элемента И соединен с первым входом элемента ИЛИ, находящегося в разряде, отстоящем от данного на (р - 1) разрядов, второй вход которого соединенс третьим выходом соответствующего одноразрядного блока сравнения, первые и вторые входы каждого элемента И соединены с единичными выходами соответствующих разрядов первого и второго регистров хранения р-кодов Фибоначчи, третьи входы каждого элемента И соединены с выходом элемента ИЛИ предыдущего разряда.Источники информации,принятые во внимание при экспертизе 1, Е. Ковальская, Ядерная электроника. Л Энергия, 1974.2. В. С. Гутников. Интегральная электроника в измерительных приборах, Атом- издат, М 1972, с. 34 - 39,662934 рг.1 Риг 2 ович аменск едакто орректо Изд.353 Тираж 779 П твенного комитета СССР по делам изобретений и откры 113035, Москва, Ж, Раушская наб., д. 4/5 исное ипография, пр. Сапунов аказ 844/1 НПО Гос оставитель Техред Н,Сигалов роганова