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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано для приведения P-кодов Фибоначчи к минимальной форме. Цель изобретения - повышение быстродействия. Устройство для приведения P-кодов Фибоначчи к минимальной форме содержит группу информационных входов, тактовый вход, группу информационных выходов, выход признака конца формирования кода, блокисвертки,каждый из которых содержит элементы ИЛИ, элементы И и триггер. Введение дополнительных связей и изменение функциональной схемы блока свертки обусловило изменение алгоритма работы устройства таким образом, что длительность формирования минимального кода стала зависеть от числа фактически выполняемых сверток, т.е. увеличилось среднее быстродействие устройства. 1 с.п.ф, 1 з.п.ф. 3 ил.

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

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

РЕСПУБЛИК (19) (11) А1 (51)5 Н 03 И 7/30

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

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

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

ПО ИЗОБРЕТЕНИЯМ И OTHPbfTHRM

ПРИ ВАНТ СССР (21) 4445768/24-24 (22) 21.06.88 (46) 28.02.90. Бнш. И - 8 (71) Пермский политехнический институт (72) Л.Ф. Викентьев, А.А. Клюкин, С.Ю. Погодина, О.Л. Лепихина и И.О. Синегубов (53) 681.3(088.8) (56) Авторское свидетельство СССР.

9 1392554, кл. Н 03 M 7/30, 1986. . Авторское свидетельство СССР

Ф 842782, кл. Н 03 И 7/30, 1979.

2 (54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ р-КО-

ДОВ ФИБОНАЧЧИ К ИИНИИАЛЬНОИ ФОРИЕ (57) Изобретение относится к вычислительной технике и может быть использовано для приведения р-кодов

Фибоначчи к минимальной форме. Цель изобретения — повьппение быстродейст.— вия. Устройство для приведения р-кодов Фибоначчи к минимальной форме содержит группу информационных входов, тактовый вход, группу информационных выходов и выход признака кон1547074 а формирования кода, блоки свертки, Каждый иэ которых содержит элементы

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

Целью изобретения является павы! щенке быстродействия.

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

Устройство (фиг. 1) содержит груп 1у информационных входов 1 устройстФа тактовый вход 2 устройства, и блоков 3 свертки, каждый из которых имеет шестой 4, пятый 5, третий 6, четвертый 7, седьмой 8, первый 9 и торой 10 входы, второй 11, третий

12 и первый 13 выходы, группу ин- 30 формационных выходов 14 устройства

1 выход 15 признака конца формирования кода устройства.

Блок 3 свертки (фиг. 2) содержит йервый и второй элементы ИЛИ 16 и

17, второй и первый элементы И 18 и

19:и. триггер 20.

Устройство (фиг. 1) работает слеДуюшим образом.

Перед началом работы все триггеры 40 .20 блоков 3 свертки устанавливаются

s нулевое состояние подачей сигнала по входу объединяющему все входы установки в нули (не показаны).Сиг-. налы, поступающие по;информационным 45 входам 1 устройства, устанавливают. триггеры 20 в состояния, соответствующие поданным разрядам исходного кода. !

Рассмотрим случай, когда минимизируется 1-код Фибоначчи для п==б:

Иомер блока 3 свертки 654321 .Вес разряда 853211

1-Код Фибоначчи 010101

Временные диаграммы работы устройства для этого случая приведены на фиг ° 3.

При подаче кода на установочные входы триггеров 20 триггеры Т1, Т3 ты устройства таким образом, что длительность формирования минимального кода стала зависеть от числа фактически выполняемых сверток, т. ° е. увеличилось среднее быстродействие устройства. 1 з.п. ф-лы, 3 ил. и Т5 устанавливаются в состояние "1", а триггеры Т2, Т4 и Тб — в состояние

"0". Элемент И19 каждого блока 3 свертки анализирует состояние трех триггеров, хранящих значения 1-ro, (1"1)-ro и (1-2)-ro разрядов, и фор" мирует на выходе признак свертки Х =

0 e 0 е- i Ч е-гЕсли Х = 1, то над соответствующими разрядами кода Фибоначчи должна быть выполнена операция свертки.Для рассматриваемого случая признак сверт.— ки, равный 1, будет вырабатываться на выходе элемента И19 второго блока 3 свертки.

С выхода элемента И19 признак . свертки через элемент ИЛИ16 подается на первый вход элемента ИЛИ 17, который предназначен для выработки признака конца формирования разряда Zg.

Для 1-ro блока 3 свертки признак конца Z < формируется как объединение сигнала признака конца, поступившего с (1+1)-ro блока 3 свертки, и признаков свертки 1-го (1+1)-го и (1+2)-го блоков 3:

Одновременно с формированием приз нака конца сигнал свертки Х постуГ пает.на первый вход элемента И 18.

Элемент И18 каждого блока 3 свертки используется для синхронной;подачи сигнала U на счетные входы триггеров 20, что устраняет эффект гонок.

Выработка сигнала U< на выходе элемента И 18 осуцествляется в момент подачи на второй вход этого элемента управляющего сигнала У по входу 2:

U = х(х vх „чх, ).

В рассматриваемом примере единичный сигнал свертки Х подается на входы элементов ИЛИ16 первого и второго блоков 3 свертки. Элементы

ИЛИ 16 пропускают эти единичные сигналы на первые входы элементов И 18 и

47074

10

20 четвертыми входами k = Х (k < р+2) блоков свертки.

2. Устройство по п.1 о т л и

° ° 1 ч а ю щ е е с я тем, что блок свертки содержит первый и второй элементы

40

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

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

Ф содержащее и блоков свертки, причем первый выход 1-го блока свертки соединен с первым входом (1-1)го и вторым входом (1-р-1)-ro блоков свертки, второй выход 1-го блока свертки сое50

5 и элементов ИЛИ 17, на выходе 15 устройства появляется сигнал признака конца формирования кода, равный единице. По входу 2 устройства подается управляющий сигнал У, при этом на выходах элементов И 18 первого и второго блоков 3 свертки появляются единичные сигналы U u U

2 подаваемые на счетные входы триггеров 71 и Т2, Триггеры 71 и Т2, срабатывая по заднему фронту входного сигнала, изменяют состояние на противоположное; триггер Т1 переключается из единичного состояния в нулевое, а триггер Т2 — из нулевого в единичное.

Устройство из исходного состояния

010101 переходит в состояние 010110.

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

2 серии управляющих сигналов Y прекращается. На информационных выходах устройства получается результирующий минимальный код Фибоначчи 100000.

Таким образом, длительность подачи серии сигналов Y меняется в зависимости от количества сверток, фактически выполняемых при формировании устройством минимального кода Фибоначчи. Самой длительной по времени является серия сигналов Y для приведения "тяжелого" кода Фибоначчи типа

1010101010101 0101011. Для приведения

"легкого" кода Фибоначчи типа

01001001001001001001 длительность серии сигналов Y равна нулю. Кроме того,в устройстве каждый из блоков свертки содержит меньшее количество логических Элементов при сохранении функциональных воэможностей прототипа. динен с 1-ым информационным выходом группы устройства, третьим входом (1+1)-го и четвертым входом (1+р+1)ro блоков свертки, тактовый вход устройства соединен с пятыми входами всех блоков свертки, информационные входы группы устройства соединены с шестыми входами соответствующих блоков свертки, о т л и ч а ю щ е е с я тем, что, с целью повьпления быстродействия, третий выход 1-го блока свертки (при 1 > 1) соединен с седьмым входом (1-1)-ro блока свертки, третий выход первого блока свертки является выходом признака конца формирования кода устройства, вторые входы i=X (i v и-р-1) и первый и седьмой входы и-ro блоков свертки соединены с входом логического нуля устройства, вход логической единицы которого соединен с третьим входом первого и

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

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

"1." триггера, прямой выход которого соединен с вторым выходом блока свеитки, а инв ер с ный выход — с первым входом первого элемента И, второй и третий входы которого соединены с третьим и четвертым входами блока свертки соответственно, второй вход второго элемента ИЛИ соединен с седьмым входом блока свертки, выход второго элемента ИЛИ соединен с третьим выходом блока свертки.

1547074

gg

Оу

9q

Ду

g)

gg

2р

6g Х

,9 д g

jY

Zlj ,((Хз

Ую

Уу

zg

Ур

М

2f /, ФизЗ

Составитель А. Клюев

Редактор А. Лежнина Техред Jl.Сердюкова Корректор В. Гирняк

Заказ 85 - Тираж 659 Подписное

ВНИИПИ Государственного комитета по изобретениям и открьггиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", r, Ужгород, ул. Гагарина, 101