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

 

(11! 662934

ОПИСАНИЕ

ИЗОЬГЕт ЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

" @й v !,;1" 1Я (61) Доп ол интел ь но е к авт. с вид- ву— (22) Заявлено 02.08.76 (21) 2386002/18-24 с присоединением заявки ЛЪ (23) Приоритет (43) Опубликовано 15.05.79. Бюллетень Ке 18 (45) Дата опубликования описания 15.05.79 (51) М. Кл.

G 06 Г 7/02

Государственный комитет (53) УДК 681.321.53 (088.8) ло делам изобретений и открытий (72) Авторы изобретения

А. П. Стахов и H. А. Соляниченко (71) Заявитель Таганрогский радиотехнический институт им. В. Д. Калмыкова (54) YCTPOACTBO ДЛЯ СРАВНКНИЯ р-КОДОВ

ФИБОНАЧЧИ

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

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

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

НЕ является первым выходом устройства, выход второго элемента ИЛИ вЂ” HE является вторым выходом устройства, третий выход одноразрядного блока сравнения младших разрядов является третьим выходом устройства (2).

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

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

Поставленная цель достигается тем, что устройство дополнительно содержит (n — р) элементов И, по одному в каждом разряде

20 начиная со старших, (n — р) элементов

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

662934

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

ИЛИ предыдущего разряда.

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

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

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

9, элемента И 10.

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

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

9, что свидетельствует, что первый код больше второго. При этом на выходе элемента И вЂ” НЕ 7 единичный сигнал будет отсутствовать и опрос следующей ячейки производиться не будет.

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

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

Если значения одноименных старших разрядов совпадают и равны «1», то единичный сигнал появится на выходе шестого элемента И вЂ” НЕ и седьмого элемента И—

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

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

Максимальное время получения конечнои

ro результата равно Т=т,р —, P где n — разрядность сравниваемых кодов, т,„время срабатывания одной ячейки, Формула изобретения

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

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

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

ИЛИ вЂ” НЕ является первым выходом устройства, выход второго элемента ИЛИ—

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

Источники информации, принятые во внимание при экспертизе

1. Е. Ковальская. «Ядерная электроника».

Л., «Энергия», 1974.

2. В. С. Гутников. «Интегральная электроника в измерительных приборах», Атомиздат, М., 1972, с. 34 — 39, 662934

Фиг.1

Риг 2

Составитель И. Сигалов

Техред Н. Строганова

Редактор Н. Каменская

Корректор Р. Беркович

Типография, пр. Сапунова, 2

Заказ 844/1 Изд. № 353 Тираж 779 Подписное

НПО Государственного комитета СССР по делам изобретений и открытий

113035, Москва, 5К-35, Раушская наб., д. 4/5