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

ЕТСНИХЕСНИ 5000 б Р 74 е к я у ТЕН ОПИ АВ ГОСУДАРСТВЕНйзй КОМИТЕТ ССС ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ АНИЕ ИЗОБР омм свидительст(56) 1, Стахов А.П. Введение в алго ритмическую теорию измерения. И "Советское радио"., 1977, с. 147-150.2, Авторское свидетельство сссР по заявке У 3323602/18-24 кл. 6 06 У 7/49, 1981 (прототип). (54)(57) НОРИАЛИЗАТОР КОДОВ ФИБОНАЧЧИ, содержащий:п блоков свертки, причем первый вход 1-го блока свертки (,2 = О и) соединен с выходом. невыполнения свертки (2+1)-го блока свертки,а его второй вход соединен с выходом невыполнения свертки ( 2+2)-го блока свертки, третий вход 2-го блока свертки. соединен с выходом разрешения свертки .3-1)-го блока свертки, а четвертый вход 2-го блока свертки подключен к выходу разрешения свертки ( 2-2)-.го блока свертки, пятые входы блоков свертки обра зуют первую информационную шину яормализатора, каждый блок свертки содержит четыре элемента И, три элемента ИЛИ, причем первый и второй входы первого элемента И подключены соответственно к четвертому и третьему входам блока свертки, выход первого элемента И подключен к первому входу первого элемента ИЛИ, о т л ич а ю щ и й с я тем, что, с целью повышения быстродействия йормализато. ра, четвертый вход первого блока свертки подключен к выходу разрешения свертки первого блока свертки, выход выполнения свертки М-го блока свертки подключен к шестому входу (2-2)-го блока свертки, седьмые входы блоков свертки образуют вторую информационную шину нормализатора, выходы цифры блоков свертки образуют шину результата нормализатора, при этом каждый блок свертки содержит элемент ИЛИ-НЕ, третий вход первого элемента И блока свертки подключен к седьмому входу блока свертки, выход первого. элемента И подключен к первым входам элемента ИЛИ-НЕ и второго элемента ИЛИ, второй вход первого элемента ИЛИ соединен с пятым входом блока свертки, а выход первого элемента ИЛИ является выходом разрешения свертки блока свертки, первый, второй, третий и четвертый входы второго элемента И подключены фЯ соответственно к четвертому, третьему,фф пятому и шестому еходем блока сверт- С ки, выход второго элемента И соединен с вторыми входами второго элемента ИЛИ и элемента ИЛИ-НЕ, а также с первым входом третьего элемента ИЛИ, выходы элемента ИЛИ-НЕ и второго элемента ИЛИ являются соответственно выходами невыполнения и выполнения свертки блока свертки, первый, второй и третий входы третьего элемента И подключенысоответственно к пятому, первому и второму входам блока сверткй, первый, второй, третий и четвертый входы четвертого элемента И подключены соответственно к четвертому, третьему, седьмому.и второму входам блока свертки, выходы третьего и четвертого элементов И соединены соответственно с вторым и третьим входами третьего элемента ИЛИ, выход которого является выходом цифры блока сверткиИзобретение относится к автоматикеи вычислительной технике и можетбыть использовано в специализированных вычислительных машинах.Ийеестно устройство для приведе-ния кодов Фибоначчи к нормальной форме, содержащее набор блоков сверткипо числу разрядов нормализуемого кода, построенного на основе алгоритманормализации, заключающегося в последовательном применении операциисвертки двоичных разрядов 1 .Недостатком данного нормализатораявляется низкое быстродействие,обусловленное тем, что блоки свертки неявляются комбинационными схемами,Наиболее близким к предлагаемомуявляется устройство для приведения3-кодов Фибоначчи к минимальной форме, содержащее а блоков свертки, причем первый выход 3-го блока свертки(Х)-го блоков свертки,.второй выход У-го блока свертки является информационным выходом устройства исоединен с третьим входом ( 2+1)-гои четверым входом (2+2)-го блоковсвертки, управляющий вход устройства соединен с пятыми входами 2-кблоков свертки, шестые входы которых соединены с информационными вхо" 30дами устройства, третий выход 2-гоблока свертки соединен с седьмымвходом (2+1)-го и восьмым. входом(.В+2)-го блоков свертки, а девятыйи десятый входы Х-го блока свертки .З 5соединены с четвертым входом (2+2) гои вторым выходом (2+1)-го блоковсвертки соответственно,Кроме того, в устройстве-прототипе блок свертки содержит элементы 4 ОИ, ИЛИ, НЕ н триггер, причем первыйи второй входы блока подключены кпервому и второму входам первогоэлемента ИЛИ, выход которого подключен к нулевому входу триггера, нулевой выход которого подключен к первому входу первого элемента И, второйтретий, и четвертый входы которогоподключены к третьему, четвертому ипятому входам блока соответственно,выход первого элемента И подключенк первому выходу блока и к первомувходу второго элемента ИЛИ, единичный выход триггера подключен к второму выходу блока,.третий выход которого подключен к выходу второго элемента И, первый вход которого подключен к выходу второго элемента ИЛИ,и к первому входу третьего элементаИ, второй вход которогоподключен квыходу элемента НЕвход которого Щподключен к второму входу второго эле-,мента И и к выходу четвертого элемента И, нулЕвой выХод триГгера подключен к четвертому выходу блока,выход третьего элемента И подключен к первому входу третьего элемента ИЛИ, второй вход которого подключен к шестому входу блока, а выход подключен к единичному входу триггера, сеДьмой вход блока подключен к третьему входу первого элемента ИЛИ, восьмой вход блока подключен к второму входу второго элемента ИЛИ, девятый и десятый входы блока подключены к входам четвертого элемента И 23.Недостаткбм данного устройства является невысокое быстродействие из-заналичия в составе блока свертки триггера;Цель изобретения - повышение быстродействия устройства для норма-, лизации кодов Фибоначчи.Поставленная цель достигается тем, что в нормализаторе кодов Фибоначчи, содержащем и блоков свертки, причем первый вход 2-го блока свертки (:3=0п) соединен с выходом невцполйения свертки (3+1)-го блока свертки, а его второй вход соединен с выходом невыполнения свертки (.2+2)-го блока свертки, третий вход М-го блока свертки соединен с выходом разрешения свертки ( Ю)-го блока свертки, а четвертый вход 1-гоблока свертки подключен к выходу разрешения свертки ( -2)-го блока свертки, пятые входы блоков свертки образуют первую информационную шину нормализатора, каждый. блок свертки содержит четыре элемента И, три элемента ИЛИ, причем первый и второй входы первого элемента И подключены соответственно к четвертому и третьему входам блока свертки, выход пеового элемента И подключен к первому входу первого элемента ИЛИ, четвертый входпервого блока свертки подключен к вц-,ходу разрешения свертки первого блока свертки, выход выполнения свертки 2-.го блока свертки подключен к шестому входу (2-2)-го блока свертки,седьмые входы блоков свертки образуют вторую информационную шину нормализатора, выходы цифры блоков свертки образуют шину результата нормалнзатора, при этом каждый блок свертки содержит элемент ИЛИ-НЕ, третий входпервого элемента И блока свертки подключен к седьмому входу блока свертки, выход первого. элемента И .подключен к первым входам элемента ИЛИ-НЕ и второго элемента ИЛИ, второй вход первого элемента ИЛИ соединен с пятым входом блока свертки, а выход первого элемента ЗЛИ является выхо-. дом разрешения свертки блока свертки, первый, второй, третий и четвертый входы второго элемента И подключены соответственно к четвертому, третьему,.пятому и шестому входам блока свертки, выход второго элемента И соединен с вторыми входами второгоэлемента ИЛИ и элемента ИЛИ-НЕ, атакже с первым входом третьего элемента ИЛИ, выходы элемента ИЛИ-НЕи второго элемента ИЛИ являются соответственно выходам невыполнения ивыполнения свертки блока свертки,первый, второй и третий входы третьего элемента И подключены соответбтвенно к пятому, первому и второмувходам блока свертки, первый, второй,третий и четвертый входы четвертого 10элемента И подключенысоответственнок четвертому, третьему, седьмомуи второму входам блока свертки, выходы третьего и четвертого элементовИ соединены соответственно с вторым 35и третьим входами третьего элементаИЛИ, выход которого является выходом цифры. блока свертки. В основе построения предлагаемо О го устройства лежит реализация алгоритма нормализации посредством блоков свертки комбинационного типа,Для этого в блок свертки Р-го разряда (Р = 1, 2п) обеспече 5 но поступление информации о цифре. в Х-м разряде нормализуемого кода, о проведении оПерации свертки в (Р+1)-й или (.3+2)-й разряды и о состоянии (.Р)-го и (Р)-го разрядов норма" лизуемого кода Эта информация поступает в Р-й блок свертки посредством следующих сигналов.:БР -сигнал, соответствующий циф 35 ре в Р-м разряде нормализуемого коЪ 1 су+2- сигналы, Формирующиеся при вййолнении операции свертки в (Р+1)-й или.(Р+2)-й разряды соответственно;Р ,РР - сигналы, формирующиеся в 4 О случае., если соответственно из (.1-1)-го или (Р)-го разрядов нормализуемого кода можно проводить операцию свертки.На основе данных сигналов Р-й щ блок свертки Формирует сигнал цифры Р-го разряда нормализованного кода Я сигналы выполнения или невыполе.нения операции свертки в 2-м разряде соответственно СВ или сг и сигнал о 50 возможности. проведения операции свертки из Р-го разряда РР.В соответствии с.определением операции свертки 1 ) эти сигналы формируются по следующим правиламСигнал 8 формируется в случаях:9а) если в Р-и разряде нормализуе мого кода находится единица (8 =1) и из Р-го разряда при нормализации не проведено ни одной свертки (СР+ =сР+ = 1); 60б) если в Р-м разряде нормализуемого кода находится единица (ЯР =1) и были проведены операции свертки из Р-го разряда в ( 3+2)-й и в .Р-й разряды; 65 в) если в Р-м разряде нормализуе. мого кода находится нуль (ЯР = 1) и была проведена операция свертки в Р-й разряд, а из Р-разряда сверт- ки не производилась.Сигнал С формируется в случаях: а) если в Р-м разряде нормализуе 9 мого кода находится нуль (ВР =1) и в .него произведена свертка;б) если в,Р-м разряде нормализуемого кода находится единица (БР = 1) и были проведены операции свертки из Р-го разряда в (.Р+2)-й и в Р-й разряды.Сигнал СР Формируется в противном случаеСигнал Р формируется, если в Р-м разряде нормалируемого кода находится единица (БР 1) или если в данном разряде нуль, но в -й разряд была произведена свертка.В соответствии с приведенными правилами Формирования выходных сигналов Р-й блок свертки реализует следующие логические Функции: БР = 8 д СЬСР+27 8 Р СР+2 Р-,Р 278 Р Р Р (+Р( 1 )СР =ЯРР ДЯР СРР 2 РР РР 2 (2)СЕ=БЕРЕ РЕ 2 УБДСЫРР РР 2 (3)РЕ =Б Е УЯРРЕ-РЕИзложенный метод нормализации позволяет построить нормализатор кодовФибоначчи комбинационного типа.На Фиг, 1 приведена структурная .схема нормализатора кодов Фибоначчи;на фиг, 2 - функциональная схема блока свертки." Нормализатор кодов Фибоначчисодержит и блоков 1 свертки (п - число разрядов нормализуемого кода).На структурной схеме показаны блоки свертки нулевого, первого, второгоР-го, (Р)-го и ( Р)-го разрядовсоответственно, поскольку соединениеостальных блоков свертки аналогично.Блок 1 свертки служит для реализации операции свертки и формирова"ния сигнала цифры в соответствующемразряде нормализованного кода. Неиспользуемые выходы и входы блоков,свертки нулевого и первого разрядовне показаны.Блок 1" свертки содержит элементы И 2, 3, элемент ИЛИ 4, элемеитИЛИ-НЕ и элемент ИЛИ б, предназначенные для реализации логическихфункций (1) - (4),Устройство работает следующим об-.разом.На информационные шины нормализатора поступает нормализуемый кодв парафазном представлении А8,8 п,8 РБ, 26 Я Р ЯР БР81 И Яо Ба Блоки сверткивыполняют все возможные в данномкоде операции свертки и Формируют на1027717, шине резулвтата нормализатора кодФибораччи в минимальной форме Ан щ" 8 н Е.2 8 Е 8.г81 8 оПрии н н н .н нэтом на все незадействованные Входы6 блоков свертки подается единичныйсйгнал, В частности, при иб единичный сигнал подается на третийвход блока свертки пятого разряда(С 1 а .1) н иа второй и третий входы соответственно блоков свертки пятогои четвертого разрядов (С 6 = 1).Пусть на вход шестираэрядногЬ нормалиаатора поступает код 011111, т.е. А . 011010101010. Блоки свертки нулевого, первого, второго, третьего н четвертого разрядов формируют сиг- валы Р=Р Р = РЭ=Р 1. НаО 1 2основании сигналов 8 = Р+ Р = С.1 блок свертки пятого разряда выполняет операцию свертки в пятый разряд, в результате чего формируются сигналы 8С З1, Появление сигнала С= 1 приводит к формированию блоком свертки четвертого разряда сигнала 8" = О и проведениюоперации свертки блоком сверткитРетьего РазРЯДа, посколькУ 8 э, =.С 8 = Р 2 = Р1. Блок сверткитретьего разряда формирует сигналы8 З Сэ " 1Сиг"ал Сз = 1 при дит к формированию блоком сверткивторогоразряда сигнала 8 э = О ин проведению сдвига блоком свертки первого разряда единицы из нулевого. разряда, поскольку 8= С = Р = 1. При этом формируются сигналы 8 ф = Х н С 1О, что приводит к формирова-,В нию сигнала 8 фр а О, В результатена шине результата нормалиэатораформируется код Ь" = 101010.,Норма"лнэация данного кода проведена вследующей последовательности:50 1 1 1 1 1Ф -1 0 0 1 1 110 1 О 0 1ф 1 О 1 О- оТаким образом, в предлагаемомнормализаторе кодов фибоначчи блокисвертки представляют собой двухън 15 русные комбинационные схемы, чтопозволяет выполнять операцию сверткив каждый разряд эа время Т. .= 2 ь,где Г время задержки логическогоэлемента..В прототипе операция свертки вкакой-либо разряд выполняется эавремя Т = 2 + ь. , где Т - времязадержки В 8-триггера,Учитывая, что на практике Г2"С,25 нэ выражений для Т и Т можносделать вывод, что предлагаемый нормалиэатор позволяет реализовать операциюсвертки в два раза быстрее, чем прототип. Таким образом, быстродействиепредлагаемого нормалиэатора практичеЗО ски в два раза выше, чем у прототипа.Сокращение времени выполнения нормализации позволяет уменьшить время выполнения арифметических операций, чтов конечном счете увеличивает произво 35 дительность Фибоначчиевой ЦВИ,Тираж 706 Государственного коеламизобретений и оМосква, Ж, Раушск Подпнснтета СССР рытий наб., д