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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик

<н842782 (61) Дополнительное к авт. сеид-ву (22) Заявлено 280279 (21) 2732032/18-24 с присоединением заявки Н9 (23) Приоритет

Опубликовано 300681,Бюллетень М24

Дата опубликования описания 300681 (51)М, К,.

G 06 F 5/00

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

СССР но делам изобретений и открытий (53) УДК 681 327 (088. 8) (72) Авторы изобретения

А.П. Стахов, Н. А. Соляниченко, A.H. Черняк и В. В.Замченский (71) Заявитель

Винницкий политехнический институт (54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ P — КОДОВ

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

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

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

К-го блока свертки соединен со вторым входом (В-,р-1)-го блока свертки, второй выход I-го блока свертки является информационным выходом устройства и соедииен с третьим входом (6+1) го блока снертки и четвертым входом (В+р+1)-го блока свертки, управляющий вход устройства соединен с пятыми входами всех блоков

Све1(тки, шестые входы каждого блока свертки являются информационными вхо- 2О дами устройства (1) .

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

Это определяется тем, что процесс приведения к минимальной форме состоит из ряда последовательно выполнаяемых операций свертки над группой из трех разрядов. Время одной сверт- 30 ки (;с в Указанном УстРойстве бУдет равно

Л П.

"СЦ = " и + "Или + тд где i iи, iи и, тр — время переключений соответственно элементов И, ИЛИ и триггера. Максимальное время приведения кода к минимальной форме равно и

tnt> 2 св

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

rl л л л, 5

Тп а = 2 ("и + "или+ "тР ) - 2 див ° и учитывая соотношения и - или — "инв q "19= - и где и„ вЂ” время переключения одного инвертора.

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

Поставленная цель достигается тем, что в устройство для приведения р-кодов Фибоначчи к минимальной форме, содержащее и однотипных блоков снертки, причем первый выход 8-го блока свертки соединен с первым входам (с-1)-го и вторым входом (0 — р-1) -го

842 782 блоков свертки, второй выход E- ro блока свертки является 1-м информационным выходом устройства и соединен с третьим входом(К+1) -го и четвертым входом (.В+р+1) -го блоков свертки, управляющий вход устройства соединен с пятым входом всех блоков свертки, шестые входы каждо ro блока св ертки являют с я информационными входами у стройства, введена дополнительная связь, первый выход P.-ro блока свертки сое(о динен с седьмлм входом (В+р+1) — го блока свертки. Кроме того, блок свертки содержит триггер, первый, второй, третий и четвертый элементы И, первый, второй и третий элементы ИЛИ, первый и второй элементы НЕ, причем выход первого элемента НЕ соединен с первым входом первого элемента И, ин— версный выход триггера соединен с пер— вым входом первого элемента ИЛИ, выход которого соединен с первым вхо- 20 дом второго элемента И, выход второго элемента ИЛИ соединен с вторым входом второго элемента И, выход ко— торого соединен с первым входом третьего элемента И, входом первого 25 элемента НЕ и первым выходом блока, первый вход блока соединен с первым входом четвертогo элемента И, выходы первого, третьего и четвертого элементов И соединены соответственно

3() с первым, вторым и третьим входами третьего элемента ИЛИ, выхсд которого соединен со счетным входом триггера, прямой выход которого является вторым выходом блока, второй вход блока сое— динен со входом второго элемента НЕ, "o вторым входом первого ="ëåìåíòà И и со вторым входом первого элемента

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

На фиг. 1 изображена функциональная схема устройства для р=1 и п=б; на фиг. 2 — функциональная схема блока свертки.

УGTpoAGTBo содержит шесть блоков

1 све!ртки. Каждый из которых имеет установочные входы 2 и 3, информационные входы 4 и 5, управляющий вход

6, кроме того, каждый блок 1 свертки имеет информационный вход 7 для зане- 60 сения исходной информации и установочный вход 8 сквозного переноса. По установочным входам 2 и 3 и по установочному входу 8 сквозного переноса в соответствующие блоки свертки поступает единичный сигнал, свидетельствующий о выполнении условия свертки.

Блок 1 свертки (фиг. 2) содержит триггер 9 со счетным входом, первый элемент И 10, второй элемент И 11, третий элемент И 12, четвертый элемент И 13, первый элемента ИЛИ 4, второй элемент ИЛИ 15, третий элемент

ИЛИ 16, первый элемент НЕ 17, второй элемент НЕ 18. Выход второго элемента И 11 является первым выходом блока 1 свертки, появление единичного сигнала на выходе которого свидетельствует о выполнении условия свертки для данного блока 1 свертки, Единичный выход триггера 9 является вторым выходом блока 1 свертки. Входы второго элемента И 11 соединены через первый элемент ИЛИ 14 с установочным входом 3 блока 1 свертки и инверсным выходом триггера 9, через второй элемент ИЛИ 15 с установочным входом 8 сквозного переноса блока 1 свертки и информационным входом 5 блока 1 свертки и непосредственно с информационным входом 4 блока 1 свертки .Кро— ме того, первый выход блока 1 свертки соединен со входом первого элемента

НЕ 17 и первым входом третьего элемента И 12. Входы первого элемента

И 10 соединены соответственно с выходом первого элемента НЕ 17,управляющим входом б блока 1 свертки и установочным входом 3 блока 1 свертки.

Входы третьего элемента И 12 соединены соответственно с выходом второго элемента HE 18,управляющим входом 6 блока 1 свертки и первым выходом блока 1 свертки . Входы четВертого элемен— та И 13 соединены соответственно с управляющим входом б блока 1 свертки и с установочным входом 2 блока 1 свертки . Выходы первого элемента И 10, третьего элемента И 12 и четвертого элемента И 13 соединены через третий элемент ИЛИ 16 со счетным входом триггера 9 . .Появление единичного сигнала на выходе третьего элемента ИЛИ

16 приводит к инвертированию состояния триггера 9, Кроме того, установочный вход 3 блока 1 свертки соединен со входом второго элемента HE 18.

Уст ановочный вход в единицу три ггера

9 соединен с информационным входом

7 блока 1 свертки .

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

Перед началом работы все триггеры находятся в нулевом состоянии. Сигналы, поступающие на установочные входы 7 блоков 1 свертки всех разрядов, устанавливают триггеры 9 в coc— тояния, соответствующие поданному коду °

Предположим, что необходимо привести к минимальной форме 1-код Фибоначчи числа 8, представляемого следующим образом:

842782

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

Номер блока свертки 1,6 1,5 1,4 1,3 1,2 1,1

1-код Фибоначчи числа -,0 1 0 1 0 1

В предлагаемом устройстве это происходит в два этапа.

На первом этапе — этапе подготовки-осуществляется формирование сигналов выделения ситуаций для выполнения операций свертки. Эти сигналы формируются по цепям сквозного переноса, но при этом свертка не производится °

На втором этапе, при поступлении единичного сигнала на управляющие входы 6 всех блоков 1 свертки, происходит формирование сигналов, поступающих на счетные входы триггеров

9 блоков 1 свертки разрядов, подлежащих свертке. C установлением триг- 20 геров 9 в соответствующие состояния на инверсном выходе триггера 9 блока 1,2,свертки возникает единичный сигнал, который через первый элемент ИЛИ 14 блока 1,2 свертки поступает на первый вход второго элемента И 11 блока 1,2 свертки, на второй вход которого поступает единичный сигнал со второго выхода блока l 1 свертки, а на третьем входе находится постоянно единичный сигнал.

На выходе второго элемента И 11 блока 1,2 свертки появляется единичный сигнал, который поступает на вход первого элемента НЕ 17, блока 1,2 свертки, на первый вход третьего элемента И 12 блока 1,2 свертки, на первый вход четвертого элемента И 13 блока 1, 1 свертки и через второй элемент ЙЛИ 15 блока 1,4 свертки на второй вход второго элемента И 11 40 блока 1, 4 свертки, на третий вход которого поступает единичный сигнал со второго выхода блока 1,3 свертки, а на первый вход поступает через элемент ИЛИ 14, блока 1,4 свертки 45 единичный сигнал с инверсного выхода триггера 9 блока 1, 4 свертки. Нулевой сигнал с выхода первого элемента

HE 17 блока 1,2 свертки поступает на первый вход пеРвого элемента И 10 блока 1, 2 свертки, запрещая появление единичного сигнала на выходе этого элемента. На выходе второго элемента

И 11 блока 1,4 свертки появляется единичный си гнал, который поступает на вход первого элемента НЕ 17 блока

1,4 свертки, на первый вход третьего элемента И 12 блока 1,4 свертки, на первый вход четвертого элемента И 13 блока 1, 3 свертки, на второй вход первого элемента И 10 блока 1,2 сверт-Ц) ки, на вход второго элемента НЕ 18 блока 1,2 свертки и через второй элемент ИЛИ 15 блока 1,6 свертки на второй вход второго элемента И 11 блока 1,6 свертки, на третий вход 65 которого поступает единичный сигнал со второго выхода блока 1,5 свертки, а на первый вход поступает через элемент ИЛИ 14 блока 1,6 свертки единичный сигнал с инверсного выхода триггера 9 блока 1,6 свертки. Нулевой сигнал с выхода первого элемента HE

17 блока 1,4 свертки поступает на первый вход первого элемента И 10 блока 1,4 свертки, запрещая появления единичного сигнала на выходе этого элемента. Нулевой сигнал с выхода второго элемента HE 18 блока 1,2 свертки поступает на третий вход третьего элемента И 12 блока 1,2 свертки, запрещая появление единичного сигнала на выходе этого элемента. На выходе второго элемента И 11 блока 1,6 свертки появляется единичный сигнал, который поступает на вход первого элемента HE 17 блока 1,6 свертки, на первый вход третьего элемента И 12 блока 1,6 свертки, на первый вход четвертого элемента И 13 блока 1,5 свертки, на третий вход первого элемента И 10 блока 1,2 свертки и на вход второго элемента НЕ 18 блока 1, 2 свертки. Нулевой сигнал с выхода первого элемента HE 17 блока 1,6 свертки поступает на первый вход первого элемента И 10 блока 1,6 свертки, запрещая появление на его выходе единичного сигнала. Нулевой си гн ал с выход а вт оро го элемент а

HE 18 блока 1,4 свертки поступает на третий вход третьего элемента И 12 блока 1, 4 свертки, запрещая появление единичного сигнала на его выходе.

Таким образ ом, единичные сигналы появляются на первых выходах блоков

1, 2; 1,4; 1,6 свертки, на третьих входах первых элементов И 10 блоков

1, 2; 1, 4 свертки, на первых входах первых элементов И 10 блоков 1, 1;

1, 3; 1, 5 свертки, на первых входах третьих элементов И 12 блоков 1, 2;

1,4; 1,6 свертки, на третьих входах третьих элементов И 12 блоков 1, 1;

1, 3; 1,5; 1,6 свертки, на первых входах четвертых. элементов И 13 блоков 1, 1; 1, 3; 1, 5 свертки. Нулевые сигналы появляются на первых выходах блоков 1, 1 ; 1, 3; 1,5; на третьих входах первых элементов И 10 блоков 1, 1;

1, 3; 1, 5 свертки, на первых входах первых элементов И 10 блоков 1, 2;

1,4; 1,6 свертки, на первых входах третьих элементов И 12 .блоков 1,1у

1, 3 свертки, на третьих входах третьих элементов И 12 блоков 1, 2; 1, 4>

1,6 свертки, на первых входах четвертых элементов И 13 блоков 1,2 и 1,4, запрещая появление единичных сигналов на выходах первого элемента И 10 третьего элемента И 12 блока 1,1 свертки; первого элемента И 10, третьего элемента И 12, четвертого элемента И 13 блока 1,2 свертки; первого элемента И 10, третьего элемен842782

0 1 1 1

1 0 1 0 1 0

1 1 0 1 0 1

Результат свертки

1 0 1 0 1 0 та И 12 блока 1, 3 свертки; первого элемента И 10, третьего элемента И 12, четвертого элемента И 13 блока 1,4 свертки; первого элемента И 10, третьего элемента И 12 блока 1,5 свертки;третьего элемента H 12,четвертого элемента И 13 блока 1,6 свертки.

При поступлении единичного сигнала на Управляющие входы 6 блоков 1, 1;

1,2; 1 3; 1 4; 1 5; 1,6 свертки возникают единичные сигналы на выходах четвертых элементов И 13 блоков 1, 1;

1,3; 1,5 свертки и на выходе третьего элемента И 12 блока 1,6 свертки, которые через третьи элементы ИЛИ 16 соответствующих блоков свертки посту". пают на счетные входы триггеров 9 блоков 1, 1; 1, 3; 1, 5; 1,6 снертки.

Устройство иэ состояния 010101 переходит н сосояние 100000.

Для пояснения работы устройства при приведении к минимальной форме 20 других кодов введены следующие обоз— начения:

С вЂ” сигнал с перного выхода блока

1 свертки Е-го разряда; сигнал с выхода третьего эле- 75 мента ИЛИ 16 блока 1 свертки й-ro разряда;

Т1 — сигнал с прямого выхода триггера 9 блока 1 свертки (r-го раз— ряда;

3()

TK — сигнал с инверсного выхода триггера 9 блока 1 свертки (r-ro разряда;

Ч вЂ” сигнал, поступающий на пятые входы всех блоков 1 свертки.

В соответствии с принятыми обоз— начениями формирование сигналов С и U происходит по следующим уравнениям:

С . = (тЕ + СЕ ) ТЕ- (ТЕ-2+ СЕ- ), (1) (C0 ° C0+g+ С3+a+ CI?+2 ° CP) Ч, (2) 40

Уравнение (1) соответствует первому этапу работы устройства, а на втором этапе происходит формирование инвертирующих сигналов в соответствии с уравнениям (2). 45

Примеры, иллюстрирующие работу устройства, приведены ниже. При необходимости к минимальной форме 1-код

Фибоначчи числа 12 значения сигналов

С и. U, вычисляемые для каждого блока св ертки в соответствии с приведенными выше уравнениями, а также окончательный результат свертки, будут следующи ми:

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

Номер блока свер ки 1 6 1 5 1 4 1 3 1,-2 1 1

1-код Фибоначчи числа

Ниже приводятся значения сигналов

С для каждого разряда, а также окончательный результат свертки при приведении к минимальной форме 1-кода Фибоначчи числа 11

Вес разряда 8 5 3

Номер бло ка свертки

1,6 1,5 1,4 1,3 1,2 1,) 1-код Фибоначчи числа 0 1 1 1 0 1

1 0 1 0 1 0

1 1 0 1 0 1

Результат свертки 1 0 1 0 0 0

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

1. Устройство для приведения р-кодов Фибоначчи к минимальной форме, содержащее п блоков свертки, причем первый выход 3-го блока свертки соединен с первым входом (3-1) -го и вторым входом (3-р-1)-го блоков свертки, второй выход В-го блока свертки являПредлагаемое устройство поз воля ет получать минимальную формулу исходно го р- кода Фибон аччи з а один такт управляющего сигнала Y . Максимальное время приведения кода к минимальной форме равно

Т,, = T l,„+ Т2 - „, где т1 „„д — максимальное время осу— ще ст влени я первого э тапа работы устройства;

Т2 осуществленияя второго этапа работы устройства;

Т1„„„зависит от количества разрядов и равно и 3 г

1ъс х 2 (Илц + - и + ц я) МнВ

Т2„, не зависит от количества раэ— рядой и равно б

+ ил = 2 "ивов

Значение максимального времени

T приведения кода к минимальной

1а форме равно

A\crv 2 AH/ rr<5

Для двадцатиразрядного 1-кода Фибонначи в известном устройстве Т „=50 Анв, тогда как при том же количестве разрядов в предлагаемом — Т„ - 323 <8.

Таким образом, предпагаемое устройство обладает более высоким быстродействием, что и определяет положительный эффект. Кроме того, устройство может осуществлять контроль за формированием сигналов С, основывающийся на том, что при правильной работе невозможно появление сигналов CB в двух соседних блоках 1 свертки, что янляется дополнительным преимуществом устройства

842782

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

2. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что блок свертки содержит триггер, первый, второй, третий и четвертый элементы И, первый,!5 второй и третий элементы ИЛИ, первый и второй элементы НЕ, причем выход первого элемента HE соединен с первым входом первого элемента И, инверсный выход триггера соединен с первым 2О входом первого элемента ИЛИ, выход которого соединен с первым входом второго элемента И, выход второго элемента ИЛИ соединен со вторым входом второго элемента И, выход которого, соединен с первым входом третьего элемента И; входом первого элеменТа

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

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

9 662926 по заявке Р 2386002/18-24, кл. G 06 F 5/00, от 01.08.76 (прототипи) °

842782

Составитель И .Сигалов

Редактор И . Ковальчук Техред 3 . Фанта . Корректор Г.Решетник

Заказ 5101/59 Тираж 745 Под пи сн ое

BHHHIIH Государственного комитета СССР по делам изобретений и открытий

1130 35, Москва, Ж-35, Раушская наб., д. 4/5

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