Нормализатор кодов Фибоначчи Советский патент 1983 года по МПК G06F7/49 

Изобретение относится к автомати и вычислительной технике и может бытьиспользовано в специализирован ных вычислительных машинах. известно устройство для приведения кодов Фибоначчи к нормальной фор ме, содержащее набор блоков свертки по числу разрядов нормализуемого ко да, построенного на основе алгоритм нормализации, заключающегося в посл довательном применении операции свертки двоичных разрядов t lНедостатком данного нормализатор является низкое быстродействие,обус ловленное тем, что блоки свертки не являются комбинационными схемами, Наиболее близким к предлагаемому является устройство для приведения г-кодов Фибоначчи к минимальной фор ме, содержащее п блоков свертки, при чем первый выход -го блока свертки (1 I,L,...,n) соединен с первым входом (J2-1) -го и вторым входом (;t- 2 ) -го блоков свертки, второй выход .2-го блока свертки является информационным выходом устройства и соединен с третьим входом (2+1)-го и четверым входом (2+2-)-го блоков свертки, управлянидий вход устройства соединен с пятыми входами I-x блоков свертки, шестые входы которых соединены с информационными вхо дами устройства, третий выход .-го блока свертки соединён с седьмым входом (l+l)-ro и восьмым входом (,В+2)-го блоков свертки, а девятый и десятый входы i-ro блока рвертки соединены с четвертым входом (1+2)и вторым выходом (S+l)-го блоков свертки соответственно . Кроме того, в устройстве-прототипе блок свертки содержит элементы И, ИЛИ, НЕ и триггер, причем первый и второй входы блока подключены к первому и второму входам первого элемента ИЛИ, выход которого подключен к нулевому входу триггера, нулеВОЙ выход которого подключен к первому входу первого элемента И, второ третий, и четвертый входы которого подключены к третьему, четвертому и пятому входам блока соответственно, выход первого элемента И подключен к первому выходу блока и к первому входу второго элемента ИЛИ, единичный выход триггера подключен к второ му выходу блока, третий выход которого подключен к выходу второго злемента И, первый вход которого подключен к выходу второго элемента ИЛИ и к первому входу третьего элемента. И, второй вхрД которо,го.:прдключен к выходу элемента НЕ,. вход которого . подключен К второму входу второго эл мента Ник выходу четвертого элемента И, нулевой выход триггера подключей к четвертому выходу блока, выход третьего элемента И подключен к первому входу третьего элемента ИЛИ, второй вход которого подключен к шестому входу блока, а выход подKJao4eH к единичному входу триггера, седьмой вход блока подключен к третьему входу первого элемента ИЛИ, восьмой вход блока подключен к второму входу второго элемента ИЛИ, девятый и десятый входы блока подключены к входам четвертого элемента И I2i. Недостатком данного устройства является невысокое быстродействие из-за наличия в составе блока свертки триггера; . Цель изобретения - повышение быстродействия устройства для норма-, лизации кодов Фибоначчи. Поставленная цель достигаемся тем, что в нормализаторе кодов Фибоначчи, содержащем п -блоков свертки, причем первый вход Е-го блока свертки (,...,n-l) соединен с выходом невыполнения свертки (s+i)-ro блока свертки, а его второй вход соединен с аыходс м невыполнения свертки (:е+2)-го блока свертки, третий вход 3-гО блока свертки соединен с выходом разрешения свертки (E-l)-rO блока свертки, а четвертый вход 1-го блока свертки подключен к выходу разрешения свертки {Е-2)-го блока свертки, пятые входы блоков свертки образуют первую информационную шину нормализатора, каждый блок свертки содержит четыре элемента И, три элемента ИЛИ, причем первый и второй входы первого: элемента И подключены соответственно к четвертому и третьему входам блока свертки, выход паевого элемента И подключен к первому входу nejJBoro элемента ИЛИ, четвертый вход первого блока свертки подключен к выг ходу разрешения свертки первого блока свертки, выход выполнения свертки .Бтго блока свертки подключен к шестому входу (7-2)-го блока свертки,седьмые входы блоков свертки -образуют вторую информационную шину нормализатора, выходы цифры блоков свертки образуют шину результата нормализатора, при этом каждый блок свертки содержит элемент ИЛИ-НЕ, третий вход первого элемента И блока свертки подключен к седьмому входу блока сверт ки, выход первого элемента И подключен к первым входам элемента ИЛИ-НЕ и второго элемента ИЛИ, второй вход первого элемента ИЛИ соединен с пятым входом блока свертки, а выход первого элемента ИЛИ является выходом разрешения свертки блока свертки, первый, второй, третий и четвертый входы второго элемента И подключены соответственно к четвертому,третьему, пятому и Шестому входам блока свертки, выход второго элемента И соединен с вторыми входгини второго элемента ИЛИ и элемента ИЛИ-НЕ, а тактхе с первым входом третьего элемента ИЛИ, выходы элемента и второго элемента ИЛИ являются соо ветственно выходам невыполнения и выполнения свертки блока свертки, первый, второй и третий входы треть его элемента И подключены соответственно к пятому, первому и второму входам блока свертки, первый, второй третий и четвертый входы четвертого элемента И подключены соответственно к четвертому, третьему, седьмому и второму входам блока свертки, выходы третьего и четвертого элементов И соединены соответственно с вторым и третьим входами третьего элемента ИЛИ, выход которого является выходом цифры, блока свертки. В основе построения предлагаемого устройства лежит реализация алгоритма нормализации посредством блоков свертки комбинационного типа.. Для этого в блок свертки 5-го разряда а I, 2,...,п-1) обеспечено поступление информации о цифре, в :г-м раэряде нормализуемого кода, о проведении операции свертки в (е+1)или (..е+2)-й разряды и о состоянии (:Е-1 )-го и (JE-2 )-го разрядов нормализуемого кода.. Эта информация посту пает в 2-й блок свертки посредством следующих сигналов-: . Sg - сигнал, соответствующий цифре в 1-м разряде нормализуег зго коДа;- - . . - ,Ce+2 сигналы, формирующиеся При выполнении-операции свертки в (Е+1)-й или. (И-2)-й разряйы соответствен йо; Pg, сигналы, формирующиеся в случае, если соответственно из (J-D-PO или (5-2)-го разрядов нормализуемого кода можно проводить опе рацию свертки. На основе данных сигналов 2-й блок свертки формирует сигнал цифр1л 1-го разряда нормализованного кода сигнёшы-выполнения или невыполнения оп;ерации свертки в 2-м разряд соответственно С- или Cg и сигнал о возможности проведения операции све тки из 2-го разряда Pg. В соответствии с определением операции свертки (1 эти сигналы формируются по следующим правилам. Сигнал Sg формируется в случаях а)если в 2-м разряде нормализуе мого кода находится единица (Sg 1) и из 1-го разряда при нормализации не проведено ни одной Свертки (Cj C.2 I); б)если в 1-м разряде нормализуемого кода находится единица {Sg 1 и были проведены операции свертки и 2-го разряда в (12+2)-ft и в ;г-й разряды;-в) если в S-tA разряде нормализуемого кода находится нуль (Sj 1) и была проведена операция свертки в 1-й разряд, а из Е-разряда сверт- ки не производилась. Сигнал Cg формируется в случаях: а)если в jE-м разряде нормализует мого кода находится нуль (Sg 1) и в .него произведена свертка; б)если в .Е-м разряде нормализуемого кода находится единица (Sg 1) и были проведены операции свертки из 1-го разряда в (.г+2)-й и в г-й разряды. .- Сигнал Cg формируется в противном случае.. Сигнал Pg формируется, если в . В-м-разряде нормалируемого кода находится единица (Sg l) или если в данном разряде нуль, но в -й разР5 д была произведена свертка. В соответствии с приведенными правилами формирования выходных сигналов Е-й блок свертки реализует следующие логические функции: s SgCe -Ce+2VSeGg 2Pe-/Pe2 Se% e-2 .,pg.2 . Х ,Pg.2VSgCg 2PE- e-Z. (3) Изложенный метод нормализации позволяет построить нормализатор кодов Фибоначчи комбинационного типа. На фиг. 1 приведена структурная схема нормализатора кодов Фибоначчи; на фиг. 2 - функциональная схема блока свертки. Норадализатор кодов Фибоначчи содержит п блоков 1 свертки (п - число разрядов нормализуемого кода). На структурной схеме показаны блоки свертки нулевого, первого, второго 2-го, {.2-1)-го и (е-2)-го разрядов соответственно, поскольку соединение остальных блоков свертки аналогично. Блок 1 свертки служит для реализации операции свертки и формирова-; ния сигнала цифры в соответствующем разряде нормализованного кода. Неиспользуе№4е выходы и входы блоков. свертки нулевого и первого разрядов не показаны. . Блок . свертки содержит элементы И 2, 3, элемент ИЛИ 4, элемент ИЛИ-НЕ и элемент ИЛИ 6, предназначенные для реализации логических функций (1)-{4). Устройство работает следующим образом. На информационные шины нормализатора поступает нормализуемый код в парафазном представлении А . - гм31..-2 - е е ...3 -1 0 0 свертки выполняют все возможные в данном коде операции свертки и формируют шине результата нормгшизатора код в минимальной форме А - s. s;:- о Р этом на все незадёйствованные бхощы 5в блоков свертки подается единичны ригнал, В частности, при п б едияичный сигнал подается на третий вход блока свертки пятого разряда (С-,« I) и на вторрй и третий входы соответственно блоков свертки пятог и четвертого разрядов (С в I). Пусть на вход шестиразрядногб нсчрмалиаатора поступает код 011111, т.е. А « 011010101010. БЛОКИ свертк нулевого, первого, второго, третьег и четвертого разрядов формируют сиг налы РО PI РЗ э л основании сигналов 85 Р, - г « 1 блок свертки пятого разряда выполняет операцию свертки в пятый разряд, в результате чего формируют ся сигналы Sj Cg 1. Появление сигнёша С 5 1 приводит к формирова нию блоком свертки четвертого разряда сигнала О и проведению Операции свертки блоком свертки третьего разряда, поскольку S. г 5 Pj Р1 I. БЛОК свертки третьего разряда формирует сигналы s5 3 Сигнал Сз i приводит к формированию блоком свертки второго разряда сигнала S О и проведению сдвига блоком свертки первого разряда единицы из нулевого разряда, поскольку S С р„ 1 При этом формируются сигналы s 1 нию сигнала 8 в 0. В результате на шине результата нормализатора формируется код А 101010..Нормалиэа1и1я данного кода проведена в следующей последовательности: Таким Образом, в предлагаемом но ; 4ализаторе кодов Фибоначчи блоки свертки представляют собой двухъярусные комбинационные схемы, что позволяет выполнять операцию свертки в каждый разряд за время т 2t, где Т- время задержки логического элемента. В прототипе операция свертки в какой-либо разряд выполняется за время Т 2 t + 1Г , где /jr - время задержки RS-триггёра. Учитывая, что на практике ТГ 9i 2-Г, из вщ ажений для Т и Т можно сделать вывод, что предлагаемый нормализатор позволяет реализовать операцию свертки в два раза быстрее, чем прототип. Таким образом, быстродействие предлагаемого нормализатора практически в два раза выше, чем у прототипа. Сокращение времени выполнения нормализации позволяет уменьшить время выполнения арифметических операций, что в конечном счете увеличивает произвот-г

& г

ffj-f

SI

sT

ffi

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

&

S:

ct

ff .

cf

4

Cl

Фаг. /