Устройство для нормализации кодов фибоначчи

 

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

Сецнапнстнчвсиня

Ресттублин

О Il И С А Н И Е ()95129)

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свнд-ву (5I )M. KJI.

G06F 500 (22) Заявлено 11.11.80 (21) 3002942/18 — 24 с присоединением заявки М

3Ъсударстккааык камктвт

СССР ао делам «зааратеккй к открмткй (23) Приоритет (53) УДК б813 (088.8) Опубликовано 15 08.82. Бюллетень М 30

Дата опубликования описания 15.08.82 (72) Авторы изобретения

Г. В. Кремез, И. А. Баранов, В. В. Роэдобара, l

И. И. Захарчук и В. П. Лачугин

1 (7l ) Заявитель (54) УСТРОЙСТВО ДЛЯ НОРМАЛИЗАЦИИ КОДОВ

ФИБОНАЧЧИ

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

Известны устройства для приведения кодов

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

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

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

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

Работу устройства в режиме нормализации рассмотрим на примере приведения к нормальной форме фибоначчиевого восьмиразрядного . кода 11101000. Предварительно все триггеры и счетчик устанавливаются в нулевое состояние, и на сдвиговый регистр заносится код

011101000 (полагаем, что регистр девятиразрядный) . На шине 25 устанавливается единичный сигнал, который соответствует режиму нормализации и посредством элемента запрета 18 блокирует установку триггера 22 в единичное состояние. По шине 26 передается сигнал начала преобразования, который устанавливает в .единичное состояние триггер 8, в результате чего импульсы от генератора поступают на вход счетчика и сдвигают содержимое регистра 2, В результате после первого тактового импульса в регистре находится код 001! 10100, после второго — 000111010, после третьего

000011101, после четвертого тактового импульса единица из старшего разряда регистра через элементы И 16 и ИЛИ 20 по цепи циклического переноса запишется в нулевой разряд регистра 2, так как триггер 21 находится в нулевом состоянии, а следовательно, на оба входа элемента ИЛИ 19 поступают нули, на его инверсном выходе устанавливается единица и в результате открывается элемент И 16. В сдвнговом регистре формируется кол !0000! I0.

3 95129 счетчик импульсов в кодах Фибоначчи. Однако

t недостатком его являются значительные аппаратурные затраты при построении многоразрядных нормализаторов кодов Фибоначчи.

Белью изобретения является снижение аппаратурных затрат.

Поставленная цель достигается тем, что в устройстве, содержащее блок свертки, дополнительно вводятся и-разрядный сдвиговый регистр, два триггера, три элемента И, генератор импуль-<р сов, счетчик, элемент задержки, причем первый вход первого элемента И соединен с входом заI дания режима работы устройства и первым входом блока свертки, второй вход — с выходом нулевого разряда сдвигового регистра, третий вход с выходом первого разряда сдвигового регистра; а выход с единичным входом первого триггера, нулевой вход которого соединен с выходом элеме па задержки, а нулевой выход подключен к первому входу второго элемента

И, второй. вход которого соединен с выходом переполнения счетчика и входом элемента задержки, а выход подключен к нулевому входу второго триггера, единичный вход которого соединен с входом начала работы устройства, а выход подключен к первому входу третьего элемента И, второй вход которого соединен с выходом генератора импульсов, а выход подключен к входу счетчика и тактовому входу сдвигового регистра, входы разрядов,с первого по (n-1)-ый которого являются информационными входами устройства, вход нулевого разряда соединен с первым выходом блока . свертки, нулевой вход (и-2)-ого разряда и единичный вход (n-1)-oro разряда соединены с вторым выходом блока свертки, а выходы (n-2)-ого, (n-1)-ого разрядов и выход переноса сдвигового регистра соединены с вторым, третьим и четвертым входами. блока свертки соответственно, разрядный выход счетчика под. ключен к пятому входу блока свертки, выхо40 ды разрядов с первого no (n-1)-ый являются . информационными, а третий выход блока свер. тки контрольным выходом устройства.

Кроме того, блок свертки содержит первый триггер, первый элемент И, два элемента ИЛИ, два элемента запрета, второй элемент И, wt:мент задержки, дешифратор, второй триггер, причем первый вход первого элемента И соединен с инверсным выходом первого элемента ИЛИ и с первым входом второго элемента

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

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

На чертеже приведена функциональная схема устройства, Устройство содержит блок свертки 1, сдвиговый регистр 2, контрольный выход 3, элементы И 4 — 6, триггеры 7 и 8, элемент задержки 9, счетчик 10, разрядные выходы счетчика

11, шину переполнения счетчика 1,, генератор импульсов 13, выход 14 генератора импульсов, элементы И 15 и 16, элементы запрета 17 и

18, элементы ИЛИ 19 и 20, триггеры 21 и 22. элемент задержки 23, дешифратор 24, шину задания режима работы 25, шину начала работы

26.

951291 Ь о тить анпаратурные затраты для кодов, соот11. ветствующих диапазонам чисел реальных специализированных ЦВМ более, чем в 10 раз.

По пятому тактовому импульсу первоначальн в сдвиговом регистре образуется код 0100001

Однако, так как в двух старших разрядах регистра находятся единицы, то посредством элементов И 15 и ИЛИ 20 в нулевой разряд регистра заносится единица и в результате формируется

Формула изобрeòеxèÿ код 110000111. Параллельно с этим посредством триггера 21 элемента задержки 23, элемента

ИЛИ 19 блокируются циклический перенос и занесение единицы в младший разряд регистра

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

011000011, содержимое счетчика равно шести, что соответствует нахождению первого и второго разрядов нормализуемого кода соответственно в двух старших разрядах регистра, в результате возбуждается выход дешифратора. По седьмому 0 тактовому импульсу на регистре формируется код 001100001, по восьмому импульсу—

100110000, т. е. возникает единица циклического переноса, по девятому тактовому импульсу—

010011000 и на счетчике возникает сигнал переполнения, однако, так как триггер 7 находится в единичном состоянии, этот сигнал не вызывает обнуления триггера 8, в результате на управляющий вход сдвигового регистра поступает новая серия на девяти тактовых им- 30 пульсов. Через время элемента. задержки 9 триггер 7 обнуляется. По шестому тактовому импульсу срабатывает дешифратор, на выходе элемента 17 устанавливается единица и в результате осуществляется сдвиг единицы в двух 35 старших разрядах регистра 2. В течение этой серии таКтовых импульсов триггер 7 не устанавливается в единичное состояние, в .результате чего сигнал переполнения счетчика устанавливает в нуль триггер 8, что блокирует прохождение 40 импульсов от генератора 13 на .управляющий

/ вход регистра. На этом нормализация заканчивается и со сдвигового регистра. 2 считывается нормализованный код — 01000100.

После этого снимается сигнал с шины 25.

В режиме контроля в отличие от режима. нормализации на шине 25 устанавливается нулевой сигнал. В результате после установки триггера 8 в единичное состояние на сдвиго50 вый регистр от генератора поступает только одна серия тактовых импульсов.. При этом, если в каких-либо соседних разрядах кода окажу ся две единицы, триггер 22 устанавливается в единичное состояние, и на конт55 рольном выходе 3 устройства появляется сигнал ошибки. По сравнению с прототипом (3) в данном устройстве используется только один блок свертки вместо и, что позволяет сокра1. Устройство для нормализации кодов

Фибоначчи, содержащее блок свертки, о т л ич а юще ес я тем, что, с целью снижения алпаратурных.затрат, устройство содержит празрядный сдвиговый регистр, два триггера, три элемента И, генератор импульсов, счетчик, элемент задЕржки, причем первый вход первого элемента И соединен со входом задания режима работы устройства н первым входом блока свертки, второй вход — с выходом нулевого разряда сдвигового регистра, третий вход— с выходом первого разряда сдвигового регистра, а выход — с единичным входом первого триггера, нулевой вход которого соединен с выходом элемента задержки,.а нулевой выход подключен к первому входу второго элемента И, второй вход которого соединен с выходом переполнения счетчика и входом элемента задержки, а выход подключен к нулевому входу второго триггера, едини пый вход которого соединен с входом начала работы устройства, а выход подключен к первому входу третьего элемента И, второй вход которого соединен с выходом генератора импульсов, а выход подключен к входу счетчика и тактовому входу сдвигового регистра, входы разрядов с первого по (n — 1)-й которого являются информационными входами устройства, вход нулевого разряда регистра соединен с первым выходом блока свертки, нулевой вход (n-2)-ro разряда и единичный вход (n — 1)-го разряда соединены со вторым выходом блока свертки, а выходы (n — 2)-го и (n — 1)-го разрядов и выход переноса сдвигового регистра соединены со вторым, третьим и четвертым входами блока свертки соответственно, разрядный выход счетчика подключен к пятому входу блока свертки, выходы разрядов счетчика, с первого по (n-1)- й, являются информационными, а третий выход блока свертки — контрольным выходом устройства.

2. Устройство по п.1, о т л и ч а ю щ е ее я тем, что блок свертки содержит первый триггер, первый элемент И, два элемента ИЛИ, два элемента запрета, второй элемент И, элемент И, элемент задержки, дешифратор, второй триггер, причем первый вход первого элемента

И соединен с инверсным выходом первого элемента ИЛИ и с первым входом второго элемента И, второй вход первого элемента И соединен с первым информационным входом первого элемента запрета и вторым входом блока свертННИИПИ Заказ 5948/55 Тираж 731 Подписное

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

7 95129 ки, третий вход соединен с управляющим входом первого элемента запрета и третьим входом блока свертки, а выход — подключен к единичному входу первого тригтера, первому входу второго элемента ИЛИ и информационному входу второго элемента запрета, управляющий вход которого соединен с первм входом блока свертки, а выход соединен с единичным входом второго триггера, выход которого соединен с. третьим выходом блока свертки, нулевой вход 1в первого триггера соединен с выходом элемента задержки и первым входом первого элемента

ИЛИ, а выход —. соединен со входом элемента задержки и вторым входом первого элемента

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

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

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

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

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

У 2888652/18 — 24, кл. G 11 С 19/00, 1979.

3. Авторское свидетельство СССР И 662930, кл. G 06 F 5/00, 1979 (прототип).