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

1

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

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

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

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

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

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

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

первого и второго регистров хранения р-кодов Фибоначчи, третьи входы элемента И соединены с выходом элемента ИЛИ предыдущего разряда.

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

Устройство содержит первый /г-разрядный регистр р-кодов Фибоначчи 1, второй /2-разрядный регистр р-кодов Фибоначчи 2, первый элемент ИЛИ-НЕ 3, второй элемент ИЛИ-НЕ 4, одноразрядный блок сравнения 5, элемент И 6, элемент ИЛИ 7.

На фиг. 2 изображен одноразрядный блок сравнения, состоящий из первого элемента И -НЕ 8, второго элемента И-НЕ 9, элемента И 10.

Устройство работает следующим образом.

Числа, подлежащие сравнению, заносятся в соответствующие «-разрядные регистры хранения р-кода Фибоначчи 1 и 2. Единичные нулевые выходы каждого из регистров 1 и 2 соединены со входами соответствующих одноразрядных блоков сравнения, которые производят сравнения одноименных разрядов я-разрядных регистров хранения р-кодов Фибоначчи и выдают сигнал о равенстве или неравенстве одноименных разрядов. При поступлении по щине управления разрешающего единичного сигпала происходит сравнение одноименных старших разрядов. ЕсЛи значения не совпадают и первый код больше второго, то на выходе элемента И-НЕ 8 (см. фиг. 2) исчезнет единичный сигнал, что, в свою очередь, приведет к появлению единичного сигнала на выходе первого элемента И-НЕ 9, что свидетельствует, что первый код больше второго. При этом на выходе элемента И-НЕ 7 единичный сигнал будет отсутствовать и опрос следующей ячейки производиться не будет.

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

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

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

Аналогичным образом функционируют остальные одноразрядные ячейки сравнения.

Максимальное время получения конечного результата равно Г тср-- ,

где п - разрядность сравниваемых кодов.

время срабатывания одной ячейки.

Н;р

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

Устройство для сравнения р-кодов Фибоначчи, содержащее первый и второй л-разрядные регистры хранения р-кодов Фибоначчи, первый и второй элементы ИЛИ-

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

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

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

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

второго регистров хранения р-кодов Фибоначчи, третьи входы каждого элемента И соединены с выходом элемента ИЛИ предыдущего разряда.

Источники информации,

принятые во внимание при экспертизе

1.Е. Ковальская. «Ядерная электроника. Л., «Энергия, 1974.2.В. С. Гутников. «Интегральная электроника в измерительных приборах, Атомиздат, М., 1972, с. 34-39.

ff