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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК. (19) (И) д(51) 6 06 Г 5/00 06 Р 3.1/00

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3350183/18-24 (22) 29. 10.8 1 (46) 30.03.83. Бюл. ¹ 12 (72} В. П. Лачугин, И. А. Баранов, Г.. B. Кремез, В. В. Роздобара и И. И. Захарчук. (53) 681. 3(088.8) (56) 1. Смахов A. П. Введение в алго ритмическую теорию измерения. М., "Советское радио -, 1977,: с. 126-129, 146-150.

2. Авторское свидетельство СССР № 732864, кл. (j 06 F 7/385, 1980.

3. Авторское свидетельство СССР № 662930, кл.Cj 06 F 5/00, 1979

: (прототип). (54) (57) 1. УС ГРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ 1-KOQOB ФИБОНАЧЧИ К

НОРМАЛЬНОЙ ФОРМЕ, содержащее Ь однотипных блоков свертки (где И вЂ” количество разрядов в коде), причем первый ,выход L . -го блока свертки (где (— от

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

2. Устройство по п. 1, о т л и ч аю щ е е с я тем, что блок стробирова-. ния содержит (((-1) элементов И; элемент ИЛИ, элемент НЕ и триггер, причем каждый (-й вход блока соединен с первым входом f -го элемента И и с С вторым входвм (g -1)-го элемейта И, выходы всех элементов И соединены с соответствующими входами элемента ИЛИ, . выход которого непосредственно и через элемент НЕ соединен соответственно с единичным и нулевым входом триго ера, Мм выход элемента НЕ и единичный выход триггера являются соответственно вто- 4 рым и первым выходом- блока стробиро- 00 вани я. .«3

1 100.8

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

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

Недостатком известных устройств яв- ляю гся большие временные затраты íà 15 приведение кода Фибоначчи к нормальной форме, что снижает производительность вычислительных машин.

Наиболее близким к предлагаемому по технической сущности является уст- 2О ройство, содержащее набор блоков свертки по числу разрядов нормализуемого кода, причем каждый блок свертки содержит триггер, даа входных элемента ИЛИ и элемент И )3)

Этому устройству также присущ упомянутый выше недостаток, причем большие временные затраты на приведение 1-кодов

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

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

50 для tl -разрядного представления, время нормализации.

Бель изобретения - повышение быстродействия устройства для приведения 1— кодов Фибоначчи к нормальной форме.

Поставленная цель достигается тем, 55 что устройство для приведения 1-кодов

Фибоначчи к нормальной форме, содержащее A однотипных блоков свертки (где, 728 2 р — количество разрядов в коде), причем первый выход 3 -го блока свертки (где.У вЂ” от 1 до il ) соединен с первым входом (g -1)-ro и вторым входом ((в

2)-го блоков свертки, второй выход f -го блока свертки соединен с третьим входом (1+1)-го и четвертым входом (It, +

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

Кроме того, блок стробирования содержит (tl -1) элементов И, элемент ИЛИ, элемент HE и триггер, причем каждый

1 -й вход блока соединен с первым входом 3 -го элемента И и с вторым входом (1-1)-го элемента И, выходы всех элементов И соединены с соответствующими входами элемента ЦЛИ, выход которого непосредственно и через элемент HE соединен соответственно с единичным и нулевым входом триггера, выход элемента HE и единичный выход триггера являются соответственно вторым и первым выходом блока стробирования.

На чертеже представлена структурная схема устройства для приведения l-кода Фибсначчи к нормальной форме для случая 8.=5.

Устройство содержит группу 1 блоков свертки, блок 2 стробирования и группу 3 элементов И.

Группа 1 блоков свертки предназначена для выполнении операции свертки и состоит из пяти однотипных блоков 4 свертки, каждый из которых имеет в своем составе триггер 5, элемент И 6 и элементы

ИЛИ 7 и 8.

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

ООЙ728 4

3. выходе элемента И.6 0 -ro блока 4 вырабатывается единичный сигнал, который поступает через элемент ИЛИ 8 на триггер 5 этой ячейки и устанавливает его в единичное состояние. Одновременно этот же сигнал с выхода 18 8 -го блока 4 свертки подается на вход 19 (0 -1)го и вход 20 (g -2)--:го бпоков 4 и через элементы ИЛИ 7 записывает в триггеры 5 этйх блоков нулевые сигналы.

Например, в устройство записано число 3, представленное в 1-коде Фибоначчи, отличном от нормального

Вес разряда 5 3 2 1 1

i5

1-код Фибоначчи 9 0 1 1 0

Условие свертки выполняежя при подаче сигнала нормализации для блока 4 с номером 8 -4. Элемент И 6 этого блока вырабатывает сигнал, который записывает в триггер 5 блоков 4 с номерами

Д -3 и 5 -2 нулевые сигналы. В результате число 00110 примет вид 01000, что соответствует нормальной форме числа 3 в 1-коде Фибоначчи.

Так как в нормальной форме любого числа (в нашем примере числа 3) отсутствуют единицы в смежных разрядах, то с выходов элементов И 9-12 блока 2

Ю будут сняты нулевые сигналы, а па выходе элемента HE 14 будет выработан едшшчный сигнал, который поступит на нулевой вход триггера 15 блока 2 и установит его в нулевое состояние, т.е. будет CH5iT CHrHBB HopMG1IHGGItHE Oggio временно единичный сигнал с выхода элемента HE 14 поступит на управляющие входы элементов И 16 группы 3 и 1-код нормализованного числа (в нашем примере числа 3) будет считан из устройства.

Максимально требуемая длительностьсигнала нормализации в.случае. 6 -5 необходима только для случая, когда на вход устройства поступит ненормализо ванный 1-код числа 7, т.е. 01111. В этом случае необходимо выполнить две смежные свертки (01111 10011

-"10100), а длительность сигнала нормализации можно оценить следующим образом:

lr r +л

-"и= ("и "или "т1 "с. где 1Ни иЛИ и т

3 1 из элементов И 9 — 12, элемента ИЛИ l элемента HE 14 и триггера 15.

Группа 3 элементов И предназначена для выдачи нормального 1-кода в раз- личные устройства L18M и состоит из пяти элементов И 16, выходы которых являются выходом устройства.

На чертеже обозначены также входы

17 устройства и выходы 18 и входы 19 и 20 6поков свертки.

Устройство работает следующим образом.

Двоичная информация поступает на входы 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 свертки g -го, (f -1)-го и (К -2)-го разрядов, анализирует состояние триггеров 5 этих блоков.

На всех входах элемента И 6 будет присутствовать единичный сигнал, т.е. выполняться условие свертки, если триггер 5 E -ro блока 4 находится в нулевом состоянии, а триггеры 5 (-1)-го и (g --2)-ч о блоков 4 находятся в единичном состоянии и подан управляющий сигнал нормализации. В этом случае на время задержки сигнала на элементе И 6 время задержки сигнала на элементах ИЛИ 7 и Э; время перевода триггера 5 в единичное или нулевое состояние;

1008728 6

В случае поступле)пы на входы усто- ройства последовательности из щ кодов общее время их приведения (T) определяется выражением

YYl

T=-Е ".í. 1 1 1

5 — время задержки сигнала в элементах блока 2 стробир вани я.

Для рассмотренного примера (норма лизация числа 3) длительность сигнала нормализации равна

Л h Л

4H=- LM "HAM AT+ "C

I так как в этом случае необходимо выполнить только одну свертку (00110 — ъ01000).

В прототипе любой код приводится к нормальной форме за одно и то же время 4ф, которое является постоянным и ,задается равным максимально требуемому 15 времени для производства всех возможных сверток в р -разрядном представлении 1-кода Фибоначчи.

Общее время (P ), затрачиваемое на приведение к нормальной форме pl ко- О дов, поступающих последовательно, в этом случае определяется выражением

+ яч А%

Yl

" =X. "H "н

«=1

В предлагаемом устройстве в отличие от известного время приведения к нормальной форме каждого кода (ЬH ) зависит от вида кода, поступившего на входы устройства, и лежит в пределах 30 л+

0-ьн- н.

Таким образом, время приведения к нормальной форме последовательности из

Щ кодов в предлагаемом устройстве по сравнению с известным уменьшено в К раз

T "П "н к= — = — „

7,— л

Например, для 5-разрядного представления чисел (при этом число кодов в последовательности й) равно 32) предлагаемое устройство позволяет. приблизи- тельно в 2 раза уменьшить общее время приведения поступивших кодов к норма п ным 1-кодам Фибоначчи.

Выигрыш но времени нормализации растет с увеличением разрядности поступающего на входы устройства кода, что позволяет существенно повысить производительность специализированных.

UBM.

f008728

ВНИИПИ Заказ 2339/59 . Тираж 704 подписное филиал flOfl "Патент", г Ужгород, ул. Проектная, 4