Нормализатор кодов фибоначчи

 

НОРМАЛИЗАТОР КОДОВ ФИБОНАЧЧИ , содержащий п блоков свертки, причем первый вход -го блока свертки (л О,..., ) соединен с выходснл невьтолнения свертки (.8+1)-го блока свертки,, а его второй вход соединен с выходом невыполнения свертки

ае аи

СОЮЗ ССВЕТСНИХ м шкш

РЕСПУБЛИК

308 0 Об F 7 49 я у

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

ГОСУДМРСТНЕННЬЙ КОМИТЕТ СССР

П0 ДЕЛАМ. ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

s asmecwwr cae m.EJtWTaV (21). 3405152/18-24. (22) 02.03.82 (4б) 07.07.83. Вюл. У 25 (72) Г.В. Кремез, В.В. Роздобара, И.А. Варанов-и В.П. Лачугин (53) 681.325(088.8) (-56) 1. Стахов A.Ï. Введение в anro ритмическую теорию измерения. И., "Советское радио"., 1977, с. 147-150.

2. Авторское свидетельство сссР по заявке Jt 3323602/18-24 кл. 6 06 У 7/49, 1981 (прототип). (54 ) (57 ) НОРИАЛИЗАТОР КОДОВ ФИБОНАЧЧИ, содержащий:п блоков свертки, причем первый вход Х-го блока свертки (.2 = О,..., n=1) соединен с выходом. невыполнения свертки (2+1)-го блока свертки, aего второй вход соединен с выходом невыполнения свертки (2+2)-ro блока свертки, третий вход

2-го блока свертки. соединен с выходом разрешения свертки !3-1)-го блока свертки, а четвертый вход 2-го блока свертки подключен к выходу разрешения свертки (2-2)-.го блока свертки, пятые входы блоков свертки обра зуют первую информационную шину яормализатора, каждый блок свертки содержит четыре элемента И,-.три элемента ИЛИ, причем первый и второй входы первого элемента И подключены соответственно к четвертому и третьему входам блока свертки, выход первого элемента И подключен к первому входу первого элемента ИЛИ, о т л ич а ю шийся тем, что, с целью повышения быстродействия йормализато. ра, четвертый вход первого блока свертки подключен -к выходу разрешения свертки первого блока свертки, выход выполнения свертки М-го блока свертки подключен к шестому входу (2-2)-ro блока свертки, седьмые входы блоков свертки образуют вторую информационную шину нормализатора, выходы цифры блоков свертки образуют шину результата нормализатора, при этом каждый блок свертки содержит элемент ИЛИ-НЕ, третий вход первогоэлемента И блока свертки подключен к седьмому входу блока свертки, выход первого элемента И подключен к первым входам элемента ИЛИ-НЕ и второго элемента ИЛИ, второй вход первого элемента ИЛИ соединен с пятым входом блока свертки, а выход первого элемента ИЛИ является выходом разрешения свертки блока свертки4 первый, второй, третий и четвертый входы второго элемента И подключены g+ соответственно к четвертому,-третьему, пятому и шестому еходям блока сверт- ки, выход второго элемента И соединен с вторыми входами второго элемента ИЛИ и элемента ИЛИ-НЕ, а также с первым входом третьего элемента ИЛИ, выходы элемента ИЛИ-НЕ и второго элемента ИЛИ являются соответственно выходами невыполнения и выполнения свертки блока свертки, первый, второй и третий входы третьего элемента И подключены соответственно к пятому, первому и второму входам блока > 4, сверткИ, первый, второй, третий и четвертый входы четвертого элемента

И подключены соответственно к четвертому, третьему, седьмому.и второму входам блока свертки, выходы третьего и четвертого элементов И соединены соответственно с вторым и третьим,ф входами третьего элемента ИЛИ, выход которого является выходом цифры блока свертки.

1027717

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

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

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

3-кодов Фибаначчи к минимальной форме, содержащее и блоков свертки, причем первый выход 3-го блока свертки (I = I,2,...,n) соединен с первым входом (2-I)-ro и вторым входом (Х-2)-го блоков свертки,.второй выход 7-ro блока свертки является информационным выходом устройства и соединен с третьим входом (2+Х)-ro и четверым входом (2+2)-го блоков свертки, управляющий вход устройства соединен с пятыми входами Х-.к блоков свертки, шестые входы которых соединены с информационными вхо" 30 дами устройства, третий выход 2-го блока свертки соединен с седьмым входом (2+1)-го и восьмым входом (.В+2)-га блоков свертки, а девятый и десятый входы J.-ro блока свертки З5 соединены с четвертым входом (2+2) га и вторым выходом (2+I)-го блоков свертки соответственна.

Кроме того, в устройстве-прототипе блок свертки содержит элементы 4()

И, ИЛИ, HE и триггер, причем первый и второй входы блока подключены к первому и второму входам первого элемента ИЛИ, выход которога подключен к нулевому входу триггера, нуле- 45 вой выход которого подключен к первому входу первого элемента И, второ и третий, и четвертый входы которого подключены к третьему, четвертому и пятому входам блока соответственно, выход первого элемента И подключен .к первому выходу блока и к первому входу второго элемента ИЛИ, единичный выход триггера подключен к второму выходу блока,.третий выход которого подключен к выходу второго эле- 55 мента И, первый вход которого подключен к выходу второго элемента ИЛИ, и к первому входу третьего элемента

И, второй вход которого поцключен к выходу элемента НЕ,.вход которого Щ подключен к второму входу второго эле-, мента И и к выходу четвертого элемента И, нулевой выход триггера пад ключен к четвертому выходу блока, выход третьего злемента И подключен к первому входу третьего элемента

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

И $23.

Недостаткбм данного устройства является невысокое быстродействие из-за наличия s составе блока свертки триггера;

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

Поставленная цель достигаешься тем, что в нормализаторе кодов Фибоначчи, содержащем п блоков свертки, причем первый вход 2-ro блока свертки (:3=0,...,n-I) соединен с выходом невЫполйения свертки (K+I)-ro блока свертки, а его второй вход соединен с выходом невыполнения свертки (.2+2)-ro блока свертки, третий вход

М-го блока свертки соединен с выходом разрешения свертки (в-I)-га блока свертки, а четвертый вход 1-га блока свертки подключен к выходу разрешения свертки (Й-2)-to блока свертки, пятые входы блоков свертки образуют первую информационную шину нормализатора, каждый. блок свертки содержит четыре элемента И, три элемента

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

2=го блока свертки подключен к шестому входу (2-2)-го блока свертки,седьмые входы блоков свертки образуют вторую информационную шину нармализатора, выходы цифры блоков свертки образуют шину результата нормализатаРа, при этом каждый блок свертки содержит элемент ИЛИ-НЕ, третий вход первого элемента И блока свертки подключен к седьмому входу блока свертки, выход первого элемента И -подключен к первым входам элемента ИЛИ-НЕ и второго элемента ИЛИ, второй вход первого элемента ИЛИ соединен с пятым входом блока свертки, а выход первого элемента ИЛИ является выхо-. дом разрешения свертки блока свертки, первый, второй, третий и четвертый входы второго элемента И подключены .соответственно к четвертому, третьему,.пятому и шестому входам блока свертки, выход второго элемента И соединен с вторыми входами второго

1027717 элемента ИЛИ и элемента ИЛИ-НЕ, а в) если в у-м разряде нормализуетакже с первым входом третьего зле- . мого кода находится нуль (S = I) мента ИЛИ, выходы элемента ИЛИ-НЕ и была проведена операция свертки и второго элемента ИЛИ являются соот- в 2-й разряд, а из Й-разряда сверт- ветственно выходам невыполнения и - ки не производилась. выполнения свертки блока свертки, 5 Сигнал С формируется в случаях: первый, второй и третий входы треть- а) если в 3-м разряде нормализуе его элемента И подключены соответ- мого кода находится нуль (В = I) ственно к пятому, первому и второму и в него произведена свертка; входам блока свертки, первый, второй, б) если в .2-м разряде нормализуетретий и четвертый входы четвертого 10 мого кода- находится единица (S = элемента И подключены соответственно и были проведены операции свертки к четвертому, третьему, седьмому .из Х-го разряда в (.2+2)-й и в 2-й и второму входам блока свертки, вы- Разряды. ходы третьего и четвертого элементов Сигнал С формируется в противИ соединены соответственно с вторым 3$ ном случае.. и третьим входами третьего элемента Сигнал Р формируется, если в

ИЛИ, выход которого является выхо- 2-м-разряде нормалируемого кода надом цифры. блока свертки. ходится единица (я I) или если в данном разряде нуль, но в .и-й раэВ основе построения предлагаемо- 20 ряд была произведена свертка. го устройства лежит реализация алго- В соответствии с приведенными ритма нормализации посредством бло- правилами формирования выходных сигков свертки комбинационного типа. налов 3-й блок свертки реализует

Для этого в блок свертки У-го следующие логические функции: разряда (2 = Х, 2,...,n-I) обеспече» 25 но поступление информации о цифре Б =Б С С +27Б С,2Р,,Р 2VSg g 2+) I ) в Х-м разряде нормализуемого кода, о

С =яррvs-C p p (2) проведении операции свертки в (2+? )-й 2 Е"гЮ-2 -v &2 Я-1 я-2 или (.3+2)-й Разряды и о состоянии Сд=Б Рр 1Рр-27Б С6+2 В-1 Я-2 (.2-I)-го и { Я-2)-ro разрядов норма(4-): лизуемого кода.. Эта информация посту- 3 6 Р Р-1 Р-2 пает в 2-й блок свертки посредством Изложенный метод нормализации позследующих сигналов-: воляет построить нормализатор кодов

S - сигнал, соответствующий циф- Фибоначчи комбинационного типа.

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

C - сигналы, формирующиеся на фиг. 2 — функциональная схема бло--г+ Я+Я при выполйении операции свертки в ка свертки.

{ 2+1}-й или.(7+2}-й разряды соответ- " Нормализатор кодов Фибоначчи ственно; - содержит и блоков 1 свертки- (n - чиср .,p - сигналы, формирующиеся в 40 ло разрядов нормализуемого кода). случае., если соответственно из На структурной схеме показаны бло(7.-I)-ro или (2-2)-ro разряцов нОР- -ки свертки нулевого, первого, второго мализуемого кода можно проводить опе- .2-го, (.Р-I)-ro и (Р-2}-го разрядов рацию свертки. соответственно, поскольку соединение

На основе данных сигналов 2-й щ остальных блоков свертки аналогично, блок свертки формирует сигнал цифры . Блок 1 свертки служит для реалиР-го разряда нормализованного кода. зации операции свертки и формирова-.

S" сигналы выполнения или невыпол- ния сигнала цифры в соответствующем е. нения операции свертки в 2-м разряде . разряде нормализованного кода. Несоответственно с или cg и сигнал о используемые выходы и входы блоков возможности. проведения операции свер- . свертки нулевого и первого разрядов тки из 2-ro разряда Р . не показаны.

В соответствии с.определением Блок 1" свертки содержит элеменоперации свертки {.1 ):эти сигналы ты и 2, 3, элемент или 4, элемент. формируются по следующим правилам.. ИЛИ-НЕ и элемент ИЛИ б, предназнаСигнал S формируется в случаях: ченные для реализации логических а) если в 2-м разряде нормализуе» функций (1) — (4).

9 мого кода находится единица (S j =I ) устройство работает следующим оби из 2-ro разряда при нормализации разом. не проведено ни одной свертки {C + На информационные шины нормализа=С = I); 60 тора поступает нормализуемый код б } если в Т-м paapsrpe нормализу- в парафазном представлении А емого кода находится единица (Бр =I) = я . я „Б„2Б,2...Б s < я „я „... и были проведены операции свеРтки из ...S я, Б В . Блоки свертки о а

2-го разряда в (7+2}-и H B .R-.й Раэ" выполняют все возможные в данном ряды; . 65 коде операции свертки и формируЮт на

1027717, шине резулвтата нормализатора код

Фибщлаччи в минимальной форме А"

Бе- у-2 ° ° Бе З.е-л ° Sq Во. ° ПР" и н н н .н H этом на все незадействованные входы

6 блоков свертки подается единичный сйгнал. В частности, при и 6 единичный сигнал подается на третий вход блока свертки пятого разряда (C .I) и иа второй и третий входы соответственно блоков свертки пятого и четвертого разрядов (С6 = I)Пусть на вход шестираэрядного нормалиаатора поступает код 011111, т.е. А . 011010101010. Блоки свертки нулевого, первого, второго, третьего и четвертого разрядов формируют сигналы Р = Р Р = Р> = Р+ 1. На о 2

Основании сигналов S 5 = Р + P 3 = С,. 1 блок свертки пятого разряда выполняет операцию свертки в пятый разряд, в результате чего формируются сигналы S С З 1, Появление сигнала С g = 1 приводит к формированию блоком свертки четвертого разряда сигнала S = 0 и проведению операции свертки блоком свертки третьего разряда., поскольку яэ, =.

С = P2 = P g I ° БЛОК СВЕРтки третьего разряда формирует сигналы

Бз Сэ 1ф Сигнал Сэ = 1 приводит к формированию блоком свертки второго разряда сигнала Sz = 0 и н проведению сдвига блоком свертки первого разряда единицы из нулевогоразряда, поскольку 8 ., = С = Р = 1.

При этом формируются сигналы S = 1 . и С О, что приводит к формирова-, иию сигнала S ð О. В результате на шине результата нормалиэатора формируется код A" = 101010..Нормализация данного кода проведена в следующей последовательности:

0 1 1 1 1 1

Ф- 1 — А

1 0 0 1 1 1

1 0 1 0 D 1 Е 1 0 1 0 1 О

Таким образом, в предлагаемом иормализаторе кодов Фибоначчи блоки свертки представляют собой двухъя 5 русные комбинационные схемы, что позволяет выполнять операцию свертки в каждый разряд эа время Т = 27,, где 7» время задержки логического элемента.

В прототипе операция свертки в какой-либо. разряд выполняется эа время T < = 2 t + 7ò, где 4т - ape задержки RS-триггера. учитывая, что на практике t 2 ., . иэ выражений для Т и Т можно сдеl лать вывод, что предлагаемый нормалиэатор позволяет реализовать операцию свертки в два раза быстрее, чем прототип. Таким образом, быстродействие предлагаемого нормалиэатсра практически в два раза выше, чем у прототипа.

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

1027717

Заказ 4741/53 Тираж 706 Подписное

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

4 5

113035, Москва, Ж 35, Раушская наб., д. /

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4

Составитель Н. Захаревич

Редактор A. Ворович Техред Л.Пекарь Корректор В. Бутягин