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

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советских

Социалистических

Рес ублик

IssI 1005024 (61) Дополнительное к авт. свид-ey— (22) Заявлено 27.07.81 (21} 3323602/18-24

f$g) + Кд 3 с присоединением заявки КоG 06 F 5/00

Государственный комитет

СССР по делам изобретений и открытий (23) Приоритет—

Опубликовано 1503,83. Бюллетень ¹ 10

Ю1УДК 681.3 (088. 8) Дата опубликования описания 150383 (54) УСТРОИСТВО ДИЯ ПРИВЕДЕНИЯ I-КОДОВ

ФИБОНАЧЧИ К ИИНИМАЛЬНОЙ ФОРИЕ

5 3 2

1 0 . 1

Вес разряда

Исходный код

13 8

О. 1

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

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

Недостатком такого устройства является необходимость больших временных затрат для приведения кодов

Фибоначчи к минимальной форме, что снижает производительность вычисли-. тельных машин.

Наиболее близким к предлагаемому по технической сущности является устройство для приведения р-кодов Фибоначчи к минимальной форме. содержащее п однотипных блоков свертки, при:чем первый выход 3 -го блока .свертки соединен с первым входом Я-1) -го и вторым входом 1,Р -2)-ro блоков сверт5 ки, второй выход с-го блока свертки является т -м информационным выходом устройства и соединен с тре тьим входом (9+1) -го и четвертым входом 1е +2)-ro блоков свертки, управляющий вход устройства соединен с пятыми входами всех блоков свертки, шестые входы каждого блока свертки являются информационными входами устройства 2 .

Недостатком известного устройства

15 является необходимость больших временных затрат для приведения 1-кодов

Фибоначчи к минимальной форме, которые возникают при поступлении на вход устройства кодов, требующих

20 выполнения смежных сверток, которые выполняются строго последовательно.

Работу устройства-прототипа можно, пояснить следующим примером.

1005024

Работа устройства

1 О

О О

1 О О О 1

1 О О 1 О.

Минимизированный код

1 О

О 1

Вес разряда

21 13 8 5 3 2 1

О 1 О О 1 О 1

Исходный код

Минимизированный код

0 1 О О 0

О 1В рассмотренном примере для минимизации исходного кода необходимо выполнить три операции свертки, из которых две — смежные, так как выполняются последовательно. В общем случае время минимизации Т исходного кода можно определить следующим образом:

Tie m "ñ где rn — число смежных сверток; время выполнения одной операции свертки. 2О

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

Поставленная цель достигается тем, 25 что в устройство для приведения 1-кодов Фибоначчи к минимальной форме, содержащее и блоков свертки, причем первый выход 0 -го блока свертки (Р = 1,2,..., и) соединен с первым входом (0 -1)-го и вторым входом (0-2)-ro блоков свертки, второй выход Р-ro блока свертки является 9 -м информационным выходом устройства и соединен с третьим выходом Я+1) -ro и четвертым входом (3 +2) -го блоков свертки, управляющий вход устройства соединен с пятыми входами 0 -х блоков свертки,. шестые входы которых соединены с информационными входами устройства 4О соответственно, третий выход. 0 -ro блока свертки соединен с седьмым входом (+1)-ro и восьмым входом (0+2 )-ro блоков свертки, а девятый и десятый входы 0-го блока свертки соединены с четвертым выходом (+2)-го и вторым выходом В+1)-го блоков свертки соответственно.

Кроме того, блок свертки содержит элементы И, ИЛИ, НЕ и, триггер, при- щ чем первый и второй входы блока подключены к первому и второму входам первого элемента ИЛИ соответственно, выход которого подключен к нулевому входу триггера, нулевой выход кото, рого подключен к первому входу первого элемента И, второй, третий и чет.вертый входы которого подключены к третьему, четвертому и пятому входам ,блока соответственно, выход первого элемента И подключен к первому выходу блока и к первому входу второго элемента ИЛИ, единичный выход триггера подключен к второму выходу блока, третий выход которого подключен к выходу второго элемента И, первый вход которого подключен к выходу второго элемента ИЛИ и к первому входу третьего элемента И, второй вхоц которого подключен к выходу элемента HE. вход которого подключен к второму входу второго элемента И и к выходу четвертого элемента И, нулевой выход триггера к четвертому выходу блока, выход третьего элемента H подключен к первому входу третьего элемента ИЛИ. второй вход которого подключен к шестому входу блока, а выход подключен к единичному входу триггера, седьмой вход блока подключен к третьему вхо-.. ду первого элемента ИЛИ, восьмой вход блока подключен к второму входу второго элемента ИЛИ, девятый и десятый входы блока подключены к входам четвертого элемента И соответственно, Введение дополнительных входов и выходов в каждом блоке свертки позволяет сократить время минимизации таких исходных кодов, которые требуют выполнения смежных сверток. При этом используется следующий метод минимизациии.

Если в 0 -м блоке выполняется усло-вие свертки (Ф-й разряд кода равен

"О", а (3 -1) -й и Я-2)- и разряды равны "1" ), ®-1 )-й и (8-2) -й разряды кода обнуляются, однако запись еди- ницы в 3 -й разряд минимизируемого кода происходит только в том случае, если после этого не выполняется условие свертки для (0+2) -го разряда.

Если условие свертки для Я+2)-го разряда выполняется, происходит обнуление ®+1) -го разряда, после чего определяется возможность записи единицы уже в (0+2)-й разряд и т.д.

Рассматриваемый метод минимизации кодов можно пояснить следующим примером.

1005024

Формула изобретения

В этом примере условие свертки выполняется для третьего разряда (т.е. 8 =3). При этом необходимо произвести обнуление второго и первого разрядов, однако запись единицы в третий разряд производить не нужно. так как после этого выполняется условие свертки для пятого разряда.

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

В устройстве-прототипе для минимизации данного входного кода необ- 15 ходимо выполнить две смежные операции свертки(01001 Я1 — 010Д100- 01010000 ) ..

Метод, используемый в данном устройстве, позволяет выполнить толь-2р ко одну операцию свертки (010()1011 — 01010000 ), что и сокращает вр мя минимизации кода.

Структурная схема устройства для приведения I-кодов Фибоначчи к мини- 25 мальной форме представлена на чертеже.

Устройство содержит блок 1 свертки элементы И 2, ИЛИ 3, И 4, НЕ 5, И 6, ИЛИ 7 и 8, триггер 9 и элементы И 10, входы 11- 14 свертки, выход

15 свертки, входы 16-19 свертки, выход 20 свертки, входы 21-24.свертки, выход 25 свертки.

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

Двоичная информация поступает на входы 11 устройства и через элементы ИЛИ 7 записывается в триггеры 9 блоков 1 свертки, находящиеся до прихода информации на входы 11 40 в нулевом состоянии. При подаче единичного сигнала на управляющий вход 23 устройства этот сигнал поступает на один из входов элемента И 10 всех блоков 1. Элемент И 10 анализи- 45 рует состояние триггеров 9 ф -1) -го и (-2)-ro блоков 1. На всех входах элемента И 10 присутствует единичный сигнал, т.е. выполняться,условие свертки, если триггеры 9 (6 -1) -ro5p и Я-2)-го блоков 1 находятся в единичном состоянии, а триггер 9 3 -го блока 1 — в нулевом и на управляющий вход.23 поступает единичный сигнал. В эхом случае на выходе злемен- 55 та И 10 3 -го блока 1 вырабатывается единичный сигнал, который с выхоооа 20 3 -го блока 1 свертки подается на вход 13 (Я -1) -го и вход 14 ф -2) -го блоков 1 и через элементы ИЛИ 8 записывает в триггеры 9 этих блоков нулевые сигналы.

Если триггер 9 ф +2) -го блока 1 установлен в нулевое состояние, а триггер 9 (Р +1) -ro блока 1 — в единичное, на выходе 25 (Ц +2) -го бло- 65 ка 1 и выходе 20Я + 1)-го блока 1 присутствуют единичные сигналы, которые поступают на входы 18 и 19 9 -го блока 1. В результате на выходе элемента И 4 $ -го блока 1 устанавливается единичный сигнал, подготавливающий к открытию элемент И 2. В этом случае управляющий сигнал с выхода элемента И 10 («-го блока 1 через элемент ИЛИ 3 и элемент .И 2 поступает на вход 16(6+1)-го блока 1 и через элемент ИЛИ 8 устанавливает триггер 9 этого блока в нулевое состояние. Одновременно этот же сигнал поступает на вход 17(5+2)-го блока 1.

Если при этом триггер 9(R +4) -го блока 1 находится в нулевом. а триггер 9(9+3)-го блока 1 - в единичном состоянии..то все перечисленные действия повторяются.

Если триггер 9 (6+2)-го и(9+1) -го, блоков 1 установлены в состояния, отличные от упомянутых. на выходе элемента И 4 присутствует нулевой сигнал, который через элемент НЕ готовит к открытию элемент И 6. Управляющий сигнал с выхода элемента И 10

Р -го блока 1 в этом случае через элементы ИЛИ 3. И 6 и ИЛИ 7 устанавливает триггер 9 3 -го блока 1 в единичное состояние.

По окончании управляющего сигнала свертки информация считывается с информационных выходов 20 устройства параллельно.

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

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

1. Устройство для приведения Х-кодов Фибоначчи к минимальной форме, содержащее q блоков свертки, причем первый выход Р -го блока свертки (0-1,2..., n ).. соединен с первым входом (Р-1)-ro и вторым входом (В -2)-го блоков свертки, второй выход 3 --го ,блока свертки является 2 -м информационным выходом устройства.и соединен с третьим входом (+1) -ro и четвертым входам. (9+2)-го блоков свертки, управляющий вход устройства соединен с пятыми входами В -х блоков свертки, шестые входы которых соединены с информационными входами устройства соответственно, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, третий выход P --го блока свертки соединен с седьмым входом Я +1) -ro и вось1005024 мым входом (9+2)-го блоков свертки, а девятый и десятый входы 6-ro блока свертки соединены с четвертым выходом (0 +2)-ro и вторым выходом

И +2 )-го блоков свертки соответственно.

2. Устройство по п.1, о т л ич а ю щ е е с я тем, что блок сверт ки содержит элементы И, ИЛИ, HE u триггер, причем первый и второй входы блока подключены к первому и второму входам первого элемента ИЛИ соответственно, выход которого подключен к нулевому входу триггера, нулевой выход которого подключен к первому входу первого .элемента И, второй, третий и четвертый входы которого подключены к третьему, чет вертому и пятому входам блока сООт» ветственно, выход первого элемента И подключен к первому выходу блока и к первому входу второго элемента ИЛИ, единичный выход триггера подключен к второму выходу блока, .третий выход которого подключен к выходу второго элемента И, первый вход которого подключен к выходу второго элемента

ИЛИ и к первому входу третьего элемента И, второй вход которого подключен к выходу элемента НЕ, вход которого подключен к второму входу второго элемента И и .к выходу четвертого элемента И, нулевой выход триггера подключен к четвертому выходу блока, выход третьего элемента И подключен к первому входу третьего элемента ИЛИ, второй вход которого

10 подключен к шестому входу блока, а выход подключен к единичному входу триггера, седьмой вход блока подключен к третьему входу первого элемента ИЛИ, восьмой вход блока подключен

i5 к второму входу второго элемента ИЛИ, девятый и десятый входы блока подклю-. чены к входам четвертого элемента И .соответственно.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР .,Р 732864„ кл. G 06 F 7/38, 1980.

2. Авторское свидетельство СССР

9 662930, кл. G 06 F 5/00, 1976 (прототип) °

1005024

ВНИИПИ Заказ 1899/62 Тираж 704 Подписное

Филиал ППП "Патент",г.Ужгород,ул.Проектная,4