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

,И 9 6 Г 5/О Г 31/О Ю"Ф Й ТЕН 2 Баранбара аалго 2. У юшее ния соде мент ИЛИ чем каждпервым вторым выходы соотве лемент единичнымвыход элтриггерарым и пе ГОСУДАРСТВЕННЫЙ КОМИТЕТ ССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫ ОПИСАНИЕ ИЗ АВТОРСКОМУ СВИДЕТЕЛЬС(56) 1, Смахов А, П, Введение вритмическую теорию измерения, М.,(54) (57) 1. УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ 1-КОДОВ ФИБОНАЧЧИ КНОРМАЛЬНОЙ ФОРМЕ, содержащее Ь однотипных блоков свертки (где И - количество разрядов в коде), причем первыйвыход О -го блока свертки (где 0 - от1 до й ) .соединен с первым входом(-1)-го и вторым входом (3 -2)-гоблоков свертки, второй выход 0 -го блока свертки соединен с третьим входомИ +1)-го и четвертым жодом (3+2)-гоблоков свертки, входы нормализуемогочисла устройства соединены с информационными входами соответствующих бло 8010087 ков свертки, о т л и ч а ю щ е е с .ятем, что, с целью повьпцения быстродействия, в него введены блок стробированияи группа элементов И, причем первый ивторой выходы блока стробирования сое-динены соответственно с. управляющимивходами всех блоков свертки и с первыми входами всех элементов И группы,выходы которых являются группой выходовустройства, первый выход каждого. блока свертки соединен с соответствующимвходом блока. стробирования и с вторымвходом соответствующего элемента И тройство по п. 1, о т л и ч ас я тем, что блок стробирова-. ржит (И -1) элементов И; эле, элемент НЕ и триггер, приый Г -й вход блока соединен с входом 1 -го элемента И и свходвм ( -1)-го элемейта И,всех элементов И соединены стствующими входами элемента ИЛИ,оторого непосредственно и черезНЕ соединен соответственно с и нулевым входом триггера мента НЕ и единичный выхо являются соответственно втовым выходом. блока стробиро 1003Изобретение относится к автоматике ивычислительной технике и может быть,использовано в специализированных вычислительных машинах, преимущественноповышенной надежности и живучести. 5.Известны устройства приведения кодов Фибоначчи к нормальной форме, содержащие набор блоков свертки по числуразрядов нормализуемого кода, построенные на основе алгоритма нормализации, 10заключающегося в последовательном применении операции свертки двоичных разрядов 11 и 2Недостатком известных устройств яв-ляюгся большие временные затраты на 15приведение кода Фибоначчи к нормальнойформе, что снижает производительностьвычислительных машин.Наиболее близким к предлагаемомупо технической сущности является уст оройство, содержащее набор блоков свертки по числу разрядов нормализуемогокода, причем каждый блок свертки содержит триггер, два входных элемента ИЛИи элемент И Я25Этому устройству также присущ упомянутый выше недостаток, причем большиевременные затраты на приведение 1-кодовФибоначчи к нормальной форме возникаютвследствие того, что длительность управляющего сигнала нормализации, подаваемого на вход устройства, постоянна изадается равной максимально требуемомувремени для производства всех возможных сверток в и -разрядном представле 35нии 1-кода фибоначчи,На практике на вход устройства может поступить 1-код Фибоначчи, полученный, например. с выхода сумматорафи представленный уже в нормализованной форме. В этом случае операцию нормализации выполнять не надо, Возможнытакже случаи, когда на вход устройствапоступает 1.-код фибоначчи, требующийменьшего количества сверток для своегонормализованного представления, чеммаксимально возможное количество сверток в ц -разрядном представлении 1-кода Фибоначчи. В этом случае требуетсяменьшее, чем максимально требуемое56для 1 -разрядного представления, времянормализации.Бель изобретения - повышение быстродействия устройства для приведения 1 кодов фибоначчи к нормальной форме.Поставленная цель достигается тем,55что устройство для приведения 1-кодовфибоначчи к нормальной форме, содержащее ц однотипных блоков свертки (где,7282р - количество разрядов в коде), причем первый выход 3 -го блока свертки+2)-го блоков свертки, входы нормализуемого числа устройства соединены с информационными входами соответствующихблоков свертки, введены блок стробирования и группа элементов И, причем первыйи второй выходы блока стробирования соединены соответственно с управляющимивходами всех блоков свертки и с первымивходами всех элементов И группы, выходы которых образуют группу выходов устройства, первый выход каждого блокасвертки соединен с соответствующим входом блока стробирования и с вторым входом соответствующего элемента И группывКроме того, блок стробирования содержит (п -1) элементов И, элемент ИЛИ,элемент НЕ и триггер, причем каждый1 -й вход блока соединен с первым входом 1 -го элемента И и с вторым входом ( 1-1)-го элемента И, выходы всехэлементов И соединены с соответствующими входами элемента ЦЛИ, выход которого непосредственно и через элемент НЕсоединен соответственно с единичным инулевым входом триггера, выход элемента НЕ и единичный выход триггера являются соответственно вторым и первымвыходом блока стробирования,На чертеже представлена структурнаясхема устройства для приведения 1-кода Фибсначчи к нормальной форме дляслучая 8.=5.Устройство содержит группу 1 блоковсвертки, блок 2 стробирования и группу 3элементов И.Группа 1 блоков свертки предназначенадля выполнении операции свертки и состоит из пяти однотипных блоков 4 свертки,каждый из которых имеет в своем составе триггер 5, элемент И 6 и элементыИЛИ 7 и 8.Блок 2 стробирования предназначендля уменьшения в среднем временныхзатрат на приведение 1-кода Фибоначчик нормальной форме за счет того, что,длительность вырабатываемого им сигнала нормализации зависит от вида кода,поступившего на вход устройства, и равна минимально требуемому времени приведения данного 1-кода к нормальнойформе. Блок 2 стробирования состоит008728 43. выходе элемента И 6 1 -го блока 4вырабатывается единичный сигнал, который поступает через элемент ИЛИ 8на триггер 5 этой ячейки и устанавливаетего в единичное состояние. Одновременноэтот же сигнал с выхода 18 3 -го блока 4 свертки подается на вход 19 (8 -1)-го и вход 20 (-2).-го блоков 4 и черезэлементы ИЛИ 7 записывает в триггеры 516 этйх блоков нулевые сигналы.Например, в устройство записано число 3, представленное в 1-кодефибоначчи, отличном от нормальногоВес разряда 5 3 2 1 1 151-код Фибоначчи О О 1 3. 0Условие свертки выполняежя при подаче сигнала нормализации для блока 4с номером 3 -4, Элемент И 6 этого блока вырабатывает сигнал, который записывает в триггер 5 блоков 4 с номерами9 -3 и 1 -2 нулевые сигналы, В результате число 00110 примет ищ 01000,что соответствует нормальной форме чис ла 3 в 1-коде фибоначчи.Так как в нормальной форме любогочисла (в нашем примере числа 3) отсутствуют единицы в смежных разрядах, тос выходов элементов И 9-12 блока 2 Юбудут сняты нулевые сигналы, а па выходе элемента НЕ 3.4 будет выработанедшшчный сигнал, который поступит нанулевой вход триггера 15 блока 2 иустановит его в нулевое состояние, т.е.будет снят сигнал нормализации, Одновременно единичный сигнал с выхода элемента НЕ 14 поступит на управляющиевходы элементов И 16 группы 3 и 1-коднормализованного числа (в нашем примеречисла 3) будет считан из устройства.Максимально требуемая длительностьсигнала нормализации в.случае. 1 -5 необходима только для случая, когда навход устройства поступит ненормализованный 1-код числа 7, т.е. 01111. Вф 5 этом случае необходимо выполнить двесмежные свертки (01111 10011-ю-"10100), а длительность сигнала нормализации можно оценить следующимобразом:й, Ю л +л-"или т 1 " где 1 Н лиЛИлТ 3 3.из элементов И 9 - 12, элемента ИЛИ 1элемента НЕ 14 и триггера 15,Группа 3 элементов И предназначенадля выдачи нормального 1-кода в раз-личные устройства ЦВИ и состоит изпяти элементов И 3.6, выходы которыхявляются выходом устройства.На чертеже обозначены также входы17 устройства и выходы 18 и входы 19и 20 блоков свертки.Устройство работает следующим образом.Двоичная информация поступает навходы 17 устройства и через элементыИЛИ 8 записывается в триггеры 5 блоков 4 свертки, находящиеся до приходаинформации на входы 17 в нулевом состоянии. Триггер 15 блока 2 также находится в нулевом состоянии. Предположим, что двоичная информация, поступившая на входы 17 устройства, представлена в нормальной форме (т,е, нет двухи более рядом стоящих единиц, а в младшем разряде кода, имеется значение ф 0),В этом случае триггер 15 остается внулевом состоянии так как на выходе.-цемента ИЛИ 13 присутствует нулевойсигнал,На выходе элемента НЕ 14 будетполучен единичный сигнал, который поступает на управляющие входы элементовИ 16 группы 3, вторые входы которыхсоединены с выходами триггеров 5 всехблоков 4 свертки. Двоичная информация,представленная в ьормапьной форме, считывается из устройства.Предположим, что двоичная информация, поступившая на входы 17 устройства, не представлена в нормальной форме,В этом случае на выходе элемента ИЛИ 1появляется единичный сигнал, который,поступив на едичиный вход триггера 15,переводит его в единичное состояниеСигнал с выхода триггера 15 являетсясигналом нормализации и поступает наодин из входов элемента И 6 всех блоков 4 свертки. Элемент И 6, будучисвязан с выходами триггеров 5 блоков 4свертки 6 -го, (-1)-го и (К -2)-горазрядов, анализирует состояние триггеров 5 этих блоков.На всех входах элемента И 6 будетприсутствовать единичный сигнал, т.е.выполняться условие свертки, если триггер 5-го блока 4 находится в нулевом состоянии, а триггеры 5 (-1)-гои ( 3 -2)-ч о блоков 4 находятся в единичном состоянии и подан управляющийсигнал нормализации. В этом случае на время задержки сигнала наэлемен(ге И 6время задержки сигнала наэлементах ИЛИ 7 и Э;время перевода триггера 5в единичное или нулевое состояние;