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

Сфиаз Советск ихСецмапнстмчвсинаРесттублмн О П И С А Н И Е ои 951291ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(088,8) Опубликовано 15.08,82. Бюллетень М 30 Дата опубликования описания 15.08.82 Г. В. Кремез, И. А, Баранов, В, В, Роэдобара,И. И. Захарчук и В. П. Лачугин 72) Авторы изобретения(7) Заявите УСТРОЙСТВО ДЛЯ НОРМАЛИЗАЦИИ КОДО ФИБОНАЧЧИ1Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах.Известны устройства для приведения кодов Фибоначчи к нормальной форме, содержагцие блоки свертки по числу разрядов нормалнзуемого кода, построенные на основе алгоритма нормализации, заключающегося в последователь. ном применении операции свертки двоичных разрядов 1 .и 2.Недостатком известных устройств является значительное количество оборудования при разрядности реальных специализированных вычислительных машин.Наиболее близким к предлагаемому по технической сущности является устройство для приведения р-кодов Фибоначчи к минимальной форме, содержащее и однотипных блоков свер тки, причем первый выход 1.ого блока свертки соединен с первым входом ( - 1) -ого и вторым входом (1 - р - 1)-ого блоков свертки, второй выход 1-ого блока свертки является 1-ым информационным выходом устройства и соединен с третьим входом (1+1).ого и четвертым входом (1+р+1).ого блоков свертки, управляющий вход устройства соединен с пятымвходами всех блоков свертки, шестые входы каждого блока свертки являются информацнон.ными входами устройства. Кроме того, блоксвертки содержит триггер, элемент И, первыйи второй элементы ИЛИ, причем выход элемента И соединен с первым входом первого элемента ИЛИ и является первым выходом блока,единичный выход триггера является вторымвыходом блока, первый и второй входы блокасоединены соответственно с первым и вторымвходами второго элемента ИЛИ, выход которо.го соединен с нулевым входом триггера, нулевой выход триггера соединен с первым входомэлемента И, второй, третий и четвертый входыкоторого являются соответственно третьим,четвертым и пятым входами блока, второйвход первого элемента ИЛИ является шестым р 0 входом блока, выход первого элемента ИЛИсоединен с единичным входом триггера 3,Это устройство позволяет производитьоперацию нормализации кодов Фибоначчи, атакже может использоваться как многовхоиовойРаботу устройства в режиме нормализации рассмотрим на примере приведения к нормальной форме фибоначчиевого восьмиразрядного . кода 11101000. Предварительно все триггеры и счетчик устанавливаются в нулевое состояние, и на сдвиговый регистр заносится код011101000 (полагаем, что регистр девятиразряд. ный), На шине 25 устанавливается единичный сигнал, который соответствует режиму нормализации и посредством элемента запрета 18 блокирует установку триггера 22 в единичное состояние. По шине 26 передается сигнал начала преобразования, который устанавливает в .единичное состояние триггер 8, в результате чего импульсы от генератора поступают на вход счетчика и сдвигают содержимое регистра 2, В результате после первого такто. вого импульса в регистре находится код 001 10100, после второго - 000111010, после третьего 000011101, после четвертого тактового импульса единица из старшего разряда регистра через элементы И 16 и ИЛИ 20 по цепи циклического переноса запишется в нулевой разряд ре. гистра 2, так как триггер 21 находится в нулевом состоянии, а следовательно, на оба входа элемента ИЛИ 19 поступают нули, на его инверсном выходе устанавливается единица и в результате открывается элемент И 16. В сдвн. говом регистре формируется кол 0000О. 3 95129 счетчик импульсов в кодах Фибоначчи, Однако недостатком его являются значительные аппаратурные затраты при построении многоразрядных нормализаторов кодов Фибоначчи.Целью изобретения является снижение аппаратурных затрат.Поставленная цель достигается тем, что в устройстве, содержащее блок свертки, дополнительно вводятся и-разрядный сдвиговый регистр, два триггера, три элемента И, генератор импульсов, счетчик, элемент задержки, причем первый вход первого элемента И соединен с входом задания режима работы устройства и первым вхо. дом блока свертки, второй вход - с выходом нулевого разряда сдвигового регистра, третий вход с выходом первого разряда сдвигового регистра; а выход с единичным входом первого триггера, нулевой вход которого соединен с выходом элемепа задержки, а нулевой выход подключен к первому входу второго элемента И, второй. вход которого соединен с выходом переполнения счетчика и входом элемента за. держки, а выход подключен к нулевому входу второго триггера, единичный вход которого соединен с входом начала работы устройства, а выход подключен к первому входу третьего элемента И, второй вход которого соединен с выходом генератора импульсов, а выход подключен к входу счетчика и тактовому входу сдвигового регистра, входы разрядов,с пер вого по (п.1)-ый которого являются информационными входами устройства, вход нулевого разряда соединен с первым выходом блока .свертки, нулевой вход (п.2)-ого разряда и единичный вход (н) -ого разряда соединены с вторым выходом блока свертки, а выходы (п)-ого, (и 1).ого разрядов и выход переноса сдвигового регистра соединены с вторым, третьим и четвертым входами. блока свертки соответственно, разрядный выход счетчика под. ключен к пятому входу блока свертки, выхо 40 ды разрядов с первого по (и)-ый являются информационными, а третий выход блока свер тки контрольным выходом устройства.Кроме того, блок свертки содержит первый триггер, первый элемент И, два элемента ИЛИ, два элемента запрета, второй элемент И, эле. мент задержки, дешифратор, второй триггер, причем первый вход первого элемента И соединен с инверсным выходом первого элемента ИЛИ и с первым входом второго элемента И, второй вход - с первым информацйонным входом первого элемента запрета и вторым входом блока свертки, третий вход - соединен с управляющим входом первого элемента за 55 прета и третьим входом блока свертки, а. выход подключен к единичному входу первого триггера, первому входу второго элемента ИЛИ, информационному входу второго элемен 1 4та запрета, управляющий вход которого соединен с первым входом блока свертки, а выходсоединен с единичным входом второго триггера,выход которого соединен с третьим выходомблока свертки, нулевой вход первого триггерасоединен с выходом элемента задержки и первым входом первого элемента ИЛИ, а выходсоединен с входом элемента задержки и вторым входом первого элемента ИЛИ, крометого выход первого элемента запрета соединенс втооым выходом блока свертки, а его второйинформационный вход соединен с выходом дешифратора, вход которого соединен с пятымвходом блока свертки, второй вход второгоэлемента И соединен с четвертым входом блокасвертки, а выход подключен к второму входувторого элемента ИЛИ, выход которого соеди- .нен с первым выходом блока свертки.На чертеже приведена функциональная схема устройства,Устройство содержит блок свертки 1, сдви.говый регистр 2, контрольный выход 3, элементы И 4 - 6, триггеры 7 и 8, элемент задержки 9, счетчик 10, разрядные выходы счетчика11, шину переполнения счетчика 12, генераторимпульсов 13, выход 14 генератора импульсов,элементы И 15 и 16, элементы запрета 17 и18, элементы ИЛИ 19 и 20, трггеры 21 и 22,элемент задержки 23, дешифратор 24, шинузадания режима работы 25, шину начала работы26.951191 Ьо тить анпаратурные затраты для кодов, соот 11. ветствующих диапазонам чисел реальныхспециализированных ЦВМ более, чем в 10 раз. 5По пятому тактовому импульсу первоначальн 0 сдвиговом регистре образуется код 0100001 Однако, так как в двух старших разрядах регистра находятся единицы, то посредством эле. ментов И 15 и ИЛИ 20 в нулевой разряд регистра заносится единица и в результате формируется Формула изобретениякод 110000111. Параллельно с этим посредством триггера 21 элемента задержки 23, элемента ИЛИ 19 блокируются циклический перенос и занесение единицы в младший разряд регистра 0 2 на время двух последующих тактовых импуль. сов. В двух младших разрядах регистра находятся единицы, в результате триггер 7 устано. вится в единичное состояние, По шестому так. товому импульсу в регистре 2 формируется код15 011000011, содержимое счетчика равно шести, что соответствует нахождению первого и второго разрядов нормализуемого кода соответственно в двух старших разрядах регистра, в результате возбуждается выход дешифратора. По седьмому 0 тактовому импульсу на регистре формируется код 001100001, по восьмому импульсу - 100110000, т. е, возникает единица циклического переноса, по девятому тактовому импульсу - 010011000 и на счетчике возникает сигнал переполнения, однако, так как триггер 7 находится в единичном состоянии, этот сигнал не вызывает обнуления триггера 8, в результате на управляющий вход сдвигового регистра поступает новая серия на девяти тактовых им- З 0 пульсов. Через время элемента. задержки 9 триггер 7 обнуляется, По шестому тактовому импульсу срабатывает дешифратор, на выходе элемента 17 устанавливается единица и в результате осуществляется сдвиг единицы в двух З 5 старших разрядах регистра 2. В течение этой серии таКтовых импульсов триггер 7 не устанавливается в единичное состояние, в результате чего сигнал переполнения счетчика устанавливает в нуль триггер 8, что блокирует прохождение 40 импульсов от генератора 13 на .управляющийГ вход регистра. На этом нормализация заканчивается и со сдвигового регистра. 2 считывается нормализованный код - 01000100, После этого снимается сигнал с шины 25. 45 1В режиме контроля в отличие от режима. нормализации на шине 25 устанавливается нулевой сигнал. В результате после установки триггера 8 в единичное состояние на сдвиго.50 вый регистр от генератора поступает только одна серия тактовых импульсов . При этом, если в каких-либо соседних разрядах кода окажутся две единицы, триггер 22 устанавливается в единичное состояние, и на конт 55 рольном выходе 3 устройства появляется сигнал ошибки. По сравнению с прототипом 31 в данном устройстве используется только один блок свертки вместо и, что позволяет сокра 1, Устройство для нормализации кодовФибоначчи, содержащее блок свертки, о т л ичающееся тем, что, с целью сниженияалпаратурных.затрат, устройство содержит празрядный сдвиговый регистр, два триггера,три элемента И, генератор импульсов, счетчик,элемент задЕржки, причем первый вход первогоэлемента И соединен со входом задания режимаработы устройства н первым входом блокасвертки, второй вход - с выходом нулевогоразряда сдвигового регистра, третий вход -с выходом первого разряда сдвигового регистра,а выход - с единичным входом первого триг.гера, нулевой вход которого соединен с выхо.дом элемента задержки,.а нулевой выход подключен к первому входу второго элемента И,второй вход которого соединен с выходомпереполнения счетчика и входом элементазадержки, а выход подключен к нулевому входувторого триггера, единипый вход которогосоединен с входом начала работы устройства,а выход подключен к первому входу третьегоэлемента И, второй вход которого соединенс выходом генератора импульсов, а выход под.ключен к входу счетчика и тактовому входусдвигового регистра, входы разрядов с первогопо (и - 1)-й которого являются информационными входами устройства, вход нулевого разря.да регистра соединен с первым выходом блокасвертки, нулевой вход (и)-то разряда и единичный вход (и - 1)-го разряда соединены совторым выходом блока свертки, а выходы(и - 2).го и (и - 1)-го разрядов н выход перено.са сдвигового регистра соединены со вторым,третьим и четвертым входами блока сверткисоответственно, разрядный выход счетчикаподключен к пятому входу блока свертки, выходы разрядов счетчика, с первого по (п)- й,являются информационными, а третий выходблока свертки - контрольным выходом устрой.ства,2. Устройство по п.1, о т л и ч а ю щ е ее я тем, что блок свертки содержит первый триггер, первый элемент И, два элемента ИЛИ, два элемента запрета, второй элемент И, элемент И, элемент задержки, дешифратор, второй триггер, причем первый вход первого элемента И соединен с инверсным выходом первого элемента ИЛИ и с первым входом второго элемента И, второй вход первого элемента И соединен с первым информационным входом первого элемента запрета и вторым вхолом блока сверт.ННИИПИ Заказ 5948/55 Тираж 731 Подписное лиал ППП "Чагенг", г. Ужгород, ул. Проекгнэя,4 7 95129ки, третий вход соединен с управляющим вхо"дом первого элемента запрета и третьим входомблока свертки, а выход - подключен к еди.ничному входу первого тригтера, первому входувторого элемента ИЛИ и информационномувходу второго элемента запрета, управляющийвход которого соединен с первм входом блокасвертки, а выход соединен с единичным входомвторого триггера, выход которого соединен с.третьим выходом блока свертки, нулевой вход 1 впервого триггера соединен с выходом элементазадержки и первым входом первого элементаИЛИ, а выход - соединен со входом элементазадержки и вторым входом первого элементаИЛИ; кроме того, выход первого элемента за. 1прета соединен со вторым выходом блока 1 8свертки, а его второй информационный входсоединен с выходом дешифратора, вход которого соединен с пятым входом блока свертки,второй вход второго элемента И соединен счетвертым входом блока свертки, а выходподключен ко второму входу второго элементаИЛИ, выход которого соединен с первым выхо.дом блока свертки.Источники йнформации,принятые во внимание при экспертизе1, Авторское свидетельство СССР Р 7328 б 4,кл, 6 06 Е 7/38, 1980,2. Авторское свидетельство СССР по заявкеИф 2888 б 52/18 - 24, кл. 6 11 С 19/00, 1979,3, Авторское свидетельство СССР И бб 2930,кл. 6 06 Е 5/00, 1979 (прототип).