Устройство для приведения 1-кодов Фибоначчи к нормальной форме Советский патент 1983 года по МПК H03M13/23 H03M13/53 

1.1 Изобретение относится к автоматике вычислительной технике и может быть .использовано в специализированных вычислительных машинах, преимущественно повьш1ешюй надежности и живучести. Известны устройства приведения кодов Фибоначчи к нормальной форме, содержащие набор блоков свертки по числу разр5эдов нормализуемого кода, построенные на основе алгоритма нормализации, заключающегося в последователыюм при- мененш опероште свертки двоичных разрядов l и 2 . Недостатком известных устройств являются большие временные затраты на приведение кода Фибоначчи к нормальной форме, что снижает производительность вычислительных машин. Наиболее близким к предлагаемому по технической сущности является устройство, содержащее набор блоков свертки по числу разрядов нормализуемого кода, причем каждый блок свертки содержит триггер, два- входных элемента ИЛ и элемент И Sj . Этому устройству также присущ упомянутый выше недостаток, причем больш временные затраты на приведение 1-кодо Фибоначчи к нормальной форме возникают вследствие того, что длительность управ- jg

ляющего сигнала нормализации, подаваемого на вход устройства, постоянна и задается равной максимально требуемому времени для производства всех возможных сверток в h -разрядном представлеНИИ 1-кода Фибоначчи. На практике на вход устройства может поступить 1-код Фибоначчи, полученный, например, с выхода сумматора и представленный уже в нормализованной форме, В этом случае операцию нормализации вьшолнять не надо, Возможны также случаи, когда на вход устройства поступает 1-«од Фибоначчи, тре гющий меньшего количества сверток для своего нормализованного представпе1гая, чем максимально возможное количество свер ток в Г1 -разрядном представлении 1-кода Фибоначчи. В этом случае требуется меньшее, чем максимально требуемое для h -разрядного представления, время нормализации. Цель изобретения - повышение быстр действия устройства для приведения 1кодов Фибоначчи к нормальной форие. Поставленная цель достигается тем, что устройство для приведения 1-«одов Фибоначчи к нормалы1рй форме, содержащее П однотипных блоков свертки (где

рого непосредственно и через элемент НЕ соединен соответственно с единичным и нулевым входом триггера, вькод элемента НЕ и единичный выход триггера яв282л - количество разрядов в коде), причем первый выход 6 -го блока свертки (где - от 1 до h ) соединен с первым входом (Ё -1)-го и вторым входом ( 2)-го блоков свертки, второй выход Е -го блока свертки соединен с третьим входом (t +1)-го и четвертым входом (g + +2)-го блоков свертки, входы нормализуемого числа устройства соединены с ин- формационными входами соответствующих блоков свертки, введены блок стробирования и группа элементов И, причем первый и второй выходы блока стробирования соединены соответственно с управляющими входами всех блоков свертки и с первыми входами всех элементов И группы, выходы которых образуют группу выходов устройства, первый выход каждого блока свертки соединен с соответствующим входом блока стробирования и с вторым входом соответствующего элемента И группы.Кроме TorOj блок стробирования содержит (П -1) элементов И, элемент ИЛИ, элемент НЕ и триггер, причем каждый Е -и вход блока соединен с первым входом С -го элемента И и с вторьпл входом ( 8-1)-го элемента И, выходы всех элементов И соединены с соответствующими входами элемента УЛИ, выход котоляются соответственно вторым и первым ВЫХОДОМ блока стробирования. На чертеже представлена структурная схема устройства для приведения 1-кода Фибоначчи к нормальной форме для случая .5. Устройство содержит группу 1 блоков свёртки, блок 2 стробирования и группу 3 элементов И. Группа 1 блоков свертки предназначена для вьшолнении операции свертки и состоит из пяти однотипных блоков 4 свертки, каждый из которых имеет в своем составе триггер 5, элемент И 6 и элемейты ИЛИ 7 и 8. Блок 2 стробирования предназначен для уменьшения в среднем временных затрат на приведение 1-кода Фибоначчи к нормальной форме за счет того, что . длительность вырабатываемого им сигнала нормализации зависит от вида кода, поступившего на вход устройства, и равна минимально требуемому времени приведения данного 1-кода к нормальной форме. Блок 2 стробирования состоит элемента НЕ 14 и триггера 15. Группа 3 элементов И предназначена для вьщачи нормального 1-кода в различные устройства ЦЫЧ и состоит Из пяти элементов И 16, выходы которых являются выходом устройства. На чертеже обозначены также входы 17 устройства и выходы 18 и входы 19 и 20 блсясов свертки. Устройство работает следующим обра Двоичная информация поступает на входы 17 устройства и через элементы ИЛИ 8 записьгоается в триггеры 5 блоков 4 свертки, находящиеся до прихода информации на входы 17 в нулевом состоянии. Триггер 15 блока 2 также находится в нулевом состоянии. Предполо, жим, что двоичная информация, поступив ;: шая на входы 17 устройства, представ..,:-/ лена в нормальной форме (т.е. нет двух И более рядом стоящих единиц, а в млад шем разряде кода.имеется значение О В этом случае триггер 15 остается в нулевом состоянии так как на выходе лемента ИЛИ 13 присутствует нулевой сигнал. На выходе элемента НЕ 14 будет получен единичный сигнал, которыйпосту пает на управляющие входы элементов И 16 группы 3, вторые входы которых соединены с выходами триггеров 5 всех блоков 4 свёртки. Двоичная информация. представленная в нормальной форме, счи , „о .тывается из устройства. Предположим, что двоичная информация, поступившая на входы 17 устройст ва, не представлена в нормальной форме В этом случае на выходе элемента ИЛИ появляется единичный сигнал, который, поступив на едичиный вход триггера 15 переводит его в единичное состояние Сигнал с выхода триггера 15 является сигналом нормализации и поступает на один из входов элемента И 6 всех блоков 4 свертки. Элемент И 6, будучи связан с выходами триггеров 5 блоков рвертки 0 -го, ( -1)чго и ( 6 -2)-го разрядов, анализирует состояние триггеров 5 этих блоков. На всех входах элемента И 6 будет присутствовать единичный сш:нал, T.q. выполняться условие свертки, если триг гер 5 &. -го блока 4 находится в нулевом состоянии, а триггеры 5(0 -1)нго и ( и -2) НТО блоков 4 находятся в единичном состоянии и подан заправляющий сигнал нормализации. В этом случае на вырабатывается едушичный сигнал, который поступает через элемент ИЛИ 8 на триггер 5 этой ячейки и устанавливает его в единичное состояние. Одновременно этот же сигнал с выхода 18 6 -го блока 4 свертки подается на вход 19 (0 -I)го и вход 2О (С-2)-го блоков 4 и через элементы ИЛИ 7 записьтает в триггерл 5 этих блоков нулевые сигналы. Например, в устройство записано число 3, представленное в 1-коде Фибонач- чи, отличном от нормального Вес разряда53211 1-код Фибоначчи О О 1 1 О Условие свертки выполняется при подаче сигнала нор«1ализацки для блока 4 с номером 8 -4. Элемент И 6 этого бяока вырабативает сигнал, который записы , еает в триггер 5 блоков 4 с номерами о о р оп К -3 и ь -2 нулевью сигналы. В резуль- г г пn-tnr r тате число ОО11О примет вид О1ООО, что соответствует нормальной форме числа 3 в 1-коде Фибоначчи. Так как в нормальной форйме любого числа (в нашем примере числа 3) отсутствуют едшпшьт в смежных разр5здах, то с выходов элементов И 9-12 блока 2 будут сняты нулевые сигналы, а па выходе элемента НЕ 14 будет выработан единичный сигнал, который поступит на нулевой вход триггера 15 блоки 2 и установит его в нулевое состояние, т.е. сигнал нормализации. Одновременно единичный сигнал с выхода элемента НЕ 14 nocTjTiHT на управляющие входы элементов И 16 группы 3 и 1-код нормализованного числа (в нашем примере числа 3) будет считан из устройства. Максимально требуемая длительность сигнала нормализации в случае. 6 -5необходима только для случая, когда на вход устройства поступит некорлализо- ванный 1-код числа 7, т.е. О1111. В этом случае необходимо выполнить две смежные свертки (01111 - 10О11 - 10100), а длительность сигнала нормализации можно оценить следующим образом: 5,2(2,t,,,).ic. где 2 - время задержки сигнала на элементе И 6 ИЛИ задержки сигнала на элементах ИЛИ 7 и 9; Y - время перевода триггера 5 в единичное или нулевое состояние;d, - время задержки сигнала в элемент&х блока 2 стробирования. Для рассмотренного примера (нормализация числа 3) дл1 тельность сигнала нормализации равна л л лл л так как в этом случае необходимо вьшо нить только одну свертку (OQ11P -- 01000). В прототипе любой код приводится к нормальной форме за одно и то же врем , которое является постоянным и задается равным максимально требуемом времени для производства всех возможных сверток в П -разрядном представле нии 1-кода Фибоначчи. Общее время ( Т), затрачиваемое на приведение к нормальной форме ГП к дов, поступающих последовательно, в этом случае определяется выражением ., П jt т.:1нгВ предлагаемом устройстве в отличи от известного йремя приведения к нормальной форме каждого кода ( н ) зави от вида кода, поступившего на входы устройства, и лежит в пределах и- I, ц . В случае посту11ле)П1я Jia входы устройства последовательности из т кодов общее время их 11р1геедения (Т.) определяется выражением Таким образом, время приведения-к Нормальной форме последовательности из Ш кодов в предлагаемом устройстве по cpaBHeiraro с известным уменьшено в К раз, гп ГП I«-- Л .2- н; . 1 Например, для 5-разрядного представ- ления чисел (при этом число кодов в последовательности m равно 32) предлагаемое устройство позволяет, приблизительно в 2 раза уменьшить общее время приведения поступивших кодов к нормальным 1-кодам Фибоначчи. Выигрьш по времени нормализации растет.с увеличением разрядности поступающего на входы устройства кода, что позволяет существенно повысить про- иаводительность специализирх)ванных ЦВМ.

1. УСТРОЙСТВО ДЛЯ ПРИ- , ВЕДЕНИЯ 1-КОДОВ ФИБОНАЧЧИ К НОРМАЛЬНОЙ ФОРМЕ, содержащее П однотипных блоков свертки (где h - количество разрадов в коде), причем первьй выход Ё НТО блока свертки (где Б - от 1 до И ) соединен с первым вхойом ( р 1)го и вторым входом (S -2)-го блоков свертки, второй выход 2 -нгс бло- ка свертки соединен с третьим входом ( -М)-го и четвертым Е±ОДОМ ( +J2)-ro блоков свертки, входы нормализуемого числа устройства соедвшены с информационньгми входами соответствующих блоков свертки, отличающееся тем, что, с целью повышения быстродействия, в него введены блок стробиррвания и группа элементов И, причем первый и второй выходы блока стробирования соединены соответственно с. управляпощими входами всех блоков свертки и с первыми входами всех элементов И группы, выходы которых являются группой выходов устройства, первый выход каждого блока свертки соединен с соответствующим входом блока, стробировання и с вторым входом соответствующего элемента И группы. 2. Устройство по п. 1, о т л и ч a ю щ е е с я тем, что блок стробирования содержит (М-1) элементов И, элемент ИЛИ, элемент НЕ и триггер, приW чем каждзый Р -и вход блока соединен с первым входом 6 -го элемента И и с вторым входом 2-1)нч) элемента И, § выходы всех элементов И соединены с соответствующими входами элемента ИЛИ, выход которого непос.редственно к через элемент НЕ соединен соответственно с единичным и нулевым входом , выход элемента НЕ и единичный выход триггера являются соответственно вто00 рым и первым выходом-блока стробиро ч1 вания. го 00