Устройство для приведения р-кодов Фибоначчи к минимальной форме Советский патент 1990 года по МПК H03M7/30 

%

Ј

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

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

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

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

Устройство (фиг. 1) содержит груп Йу информационных входов 1 устройства, тактовый вход 2 устройства, п блоков 3 свертки, каждый из которых имеет шестой 4, пятьй 5, третий 6, четвертый 7, седьмой 8, первый 9 и торой 10 входы, второй 11, третий 2 и первый 13 выхода группу информационных выходов 14 устройства и выход 15 признака конца формирования кода устройства I Блок 3 свертки (фиго 2) содержит первый и второй элементы ИЛИ 16 и 17, второй и первый элементы И 18 и 19:и триггер 20.

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

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

Рассмотрим случай, когда минимизируется 1-код Фибоначчи для Номер блока 3 свертки 654321 Вес разряда853211

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

При подаче кода на установочные входы триггеров 20 триггеры Т1, ТЗ

0

5

0

5

0

5

0

и Т5 устанавливаются в состояние, а триггеры Т2, Т4 и Т6 - в состояние О. Элемент И19 каждого блока 3 свертки анализирует состояние трех триггеров, хранящих значения 1-го, (1-1)-го и (1-2)-го разрядов, и формирует на выходе признак свертки Xg Q г Q е- i Q е-2

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

С выхода элемента И19 признак свертки через элемент ИЛИ16 подается на первый вход элемента ИЛИ 17, который предназначен для выработки признака конца формирования разряда Zg. Для 1-го блока 3 свертки признак конца Z g формируется как объединение сигнала признака конца, поступившего с (1+1)-го блока 3 свертки, и признаков свертки 1-го (1+1)-го и (1+2)-го блоков Зг

ze z|t(v(x,v x|41vxM)

Одновременно с формированием приз нака конца сигнал свертки Хп поступает на первый вход элемента И 18. Элемент И18 каждого блока 3 свертки используется для синхронной подачи сигнала Uj на счетные входы триггеров 20, что устраняет эффект гонок. Выработка сигнала U на выходе ьле- мента И 18 осуществляется в момент подачи на второй вход этого элемента управляющего сигнала Y по входу 2:

II Y

ие х

(xgv xf41vx).

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

и элементов ИЛИ 17, на выходе 15 устройства появляется сигнал признака конца формирования кода, равный единице. По входу 2 устройства подается управляющий сигнал Y, при этом на выходах элементов И 18 первого и второго блоков 3 свертки появляются единичные сигналы Uf и U2 , подаваемые на счетные входы триггеров Т1 и Т2. Триггеры Т1 и 12, срабатывая по заднему фронту входного сигнала, изменяют состояние на противоположное; триггер Т1 переключается из единичного состояния в нулевое, а триггер Т2 - из нулевого в единичное.

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

Таким образом, длительность подачи серии сигналов Y меняется в зависимости от количества сверток, фактически выполняемых при формировании устройством минимального кода Фибоначчи. Самой длительной по времени является серия сигналов Y для приведения тяжелого кода Фибоначчи типа 10101010t01010101011. Для приведения легкого кода Фибоначчи типа 01001001001001001001 длительность серии сигналов Y равна нулю. Кроме того,в устройстве каждый из блоков свертки содержит меньшее количество логических элементов при сохранении функциональных возможностей прототипа0

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

470746

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

5

0

5

5

0

тем, что, с целью повышения быстродействия, третий выход 1-го блока свертки (при 1 1) соединен с седьмым входом (1-1)то блока свертки, третий выход первого блока свертки является выходом признака конца формирования кода устройства, вторые входы (i n-p-1) и первый и седьмой входы n-го блоков свертки соединены с входом логического нуля устройства, вход логической единицы которого соединен с третьим входом первого и четвертыми входами k X (k p+2) блоков свертки.

0

Фиг 2

Фм.З

Редактор А. Лежнина

Составитель А. Клюев Техред Л.Сердюкова

Заказ 85

Тираж 659

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

Корректор В. Гирняк

Подписное