Устройство для нормализации кодов Фибоначчи Советский патент 1982 года по МПК H03M13/23 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах. Известны устройства для приведения кодов Фибоначчн к нормальной форме, содержащие блоки свертки по чнслу разрядов нормализуемого кода, построенные на основе алгоритма нормализации, заключающегося в последователь ном применении операции свертки двоичных разрядов (1) и 2. F eдocтaткoм нзвестных устройств является значительное количество оборудования при разрядности реальных специализированных вычислительных машин. Наиболее близким к предлагаемому по технической сущности является устройство для приведения р-кодов Фибоначчи к минимальной форме, содержащее п однотипных блоков свертки, причем первый выход 1-ого блока свертки соединен с первым входом (1-1) -ого и вторым входом (l-p-l)-oro блоков свертки, второй выход 1-ого блока свертки является 1-ым информационным выходом устройства и соединен с третьим входом (1+1)-ого и четвертым входом (1+р+1)-ого блоков свертки, управляющий вход устройства соединен с пятыми входами всех блоков свертки, шестые входы каждого блока свертки являются информационными входами устройства. Кроме того, блок свертки содержит триггер, злемент И, первый и второй злементы ИЛИ, причем выход злемента И соединен с первым входом первого злемента ИЛИ и является первым выходом блока, единичный выход триггера является вторым выходом блока, первый и второй входы блока соединены соответственно с первым и вторым входами второго злемента ИЛИ, выход которого соединен с нулевым входом триггера, нулевой выход триггера соединен с первым входом элемента И, второй, третий и четвертый входы, которого являются соответственно третьим, четЬерТ1 1м и пятым входами блока, второй вход первого элемента ИЛИ является шестым входом блока, выход первого злемента ИЛИ соединен с единичным входом триггера 3. Это устройство позволяет производить операцию нормализации кодов Фибоначчи, а также может использоваться как многовходовой счетчик илтульсов в кодах Фибоначчи. Oiwako недостатком его являются значительные аппаратурные затраты при построении многоразрядных нормализаторов кодов Фибоначчи. Целью изобретения является снижение аппаратурных затрат. Поставленная цель достигается тем, что в устройстве, содержащее блок свертки, дополни тельно вводятся п-разрядный сдвиговый perHCT два триггера, три элемента И, генератор импул сов, счетчик, элемент задержки, причем первый |ВХод первого элемента И соединен с входом з дания режима работы устройства и первым вхо дом блока свертки, второй вход - с выходом нулевого разряда сдвигового регистра, третий вход с выходом первого разряда сдвигового регистра, а выход с единичным входом первого триггера, нулевой вход которого соединен с выходом элемечта задержки, а нулевой выход подключен к первому входу второго элемента И, второй, вход которого соединен с выходом переполнения счетчика и входом элемента задержки, а выход подключен к нулевому входу второго триггера, единичный вход которого соединен с входом начала работы устройства , а выход подключен к первому входу третьего элемента И, второй вход которого соединен с выходом генератора импульсов, а выход подключен к входу счетчика и тактовому входу сдвигового регистра, входы разрядов, с первого по (п-О-ый которого являются информационными входами устройства, вход нулевого разряда соединен с первым выходом блока .свертки, нулевой вход (п-2)-ого разряда и единичный вход (n-l)-oro разряда соединены с вторым выходом блока свертки, а выходы {п-2)-ого, (n-l)-oro разрядов и выход переноса сдвигового регистра соединены с вторым, третьим и четвертым входами блока свертки соответственно, разрядный выход счетчика подключен к пятому входу блока свертки, выходы разрядов с первого по (п-1)-ый являются информационными, а третий выход блока свертки контрольным выходом устройства. I Кроме того, блок свертки содержит первый триггер, первый элемент И, два элемента ИЛИ, два элемента запрета, второй элемент И, элемент задержки, дешифратор, второй триггер, причем первый вход первого элемента И соединен с инверсным выходом первого элемента ИЛИ и с первым входом второго элемента И, второй вход - с первым информационным входом первого элемента запрета и вторым входом блока свертки, третий вход - соединен с прйвляющим входом первого элемента запрета и третьим входом блока свертки, а . выход подключен к единичному входу первого триггера, первому входу второго элемента ИЛИ, информациотюму входу второго элемента запрета, управляющий вход которого соединен с первым входом блока свертки, а выход соединен с eди fflчным входом второго триггера, выход которого соединен с третьим выходом блока свертки, нулевой вход первого триггера Соединен с выходом элемента задержки и первым входом первого элемента ИЛИ, а выход соединен с входом элемента задержки и вторым входом первого элемента ИЛИ, кроме того выход первого, элемента запрета соединен с вторым выходом блока свертки, а его второй информационный вход соединен с выходом дешифратора, вход которого соединен с пятым входом блока свертки, второй вход второго элемента И соединен с четвертым входом блока свертки, а выход подключен к второму входу второго элемента ИЛИ, выход которого соединен с первым выходом блока свертки. Начертеже приведена функциональная схема устройства. Устройство содержит блок свергки 1, сдвиговый регистр 2, контрольный выход 3, элементы И 4-6, триггеры 7 и 8, элемент задержки 9, счетчик 10, разрядные выходы счетчика 11, шину переполнения счетчика 12, генератор импульсов 13, выход И генератора импульсов, 1элемен1Ъ1 И 15 и 16, элементы запрета 17 и 18, элементы ИЛИ 19 и 20, триггеры 21 и 22, элемент задержки 23, дешифратор 24, шину задания режима работы 25, шину начала работы 26. Работу устройства в режиме нормализации рассмотрим на примере приведе шя к нормальной форме фибоначчиевого восьмиразрядного . кода 11101000. Предварительно все триггеры и счетчик устанавливаются в нулевое состояние, и на сдвиговый регистр заносится код 011101000 (полагаем, что регистрдевятиразрядный) . На шине 25 устанавливается единичный сигнал, который соответствует режиму нормализации и посредством элемента запрета 18 блокирует установку триггера 22 в единичное состояние. По шине 26 передается сигнал начала преобразованиЯд который устанавливает в единичное состояние триггер 8, в результате чего импульсы от генератора поступают на вход счетчика и сдвигают содержимое регистра 2. В реэультате после первого тактового импульса в регистре находится код 001110100, после второго - 00011.1010, после третьего - 000011101, после четвертого тактового импульса единица из старшего разряда регистра через элементы И 16 и ИЛИ 20 по цепи циклического переноса запишется в нулевой разряд регистра 2, так как триггер 21 находится в нулевом состоянии, а следовательно, на оба входа элемента ИЛИ 19 поступают нули, на его инверсном выходе устанавливается еди1™ца и в результате открывается элемент И 16. В сдвиговом регистре формируется кол 100001110. 5 flo пятому тактовому импульсу первоначально В. сдвиговом регистре образуется код 0100001 Однако, так как в двух старших разрядах регистра находятся единицы, то посредством эле ментов И 15 и ИЛИ 20 в нулевой разряд регистра заносится единица и в результате формируется код 110000111. Параллельно с этим посредств триггера 21 элемента задержки 23, элемента ИЛИ 19 блокируются циклический перенос и занесение единицы в младший разряд регистра 2 на время двух последующих тактовых импу сов. В двух младших разрядах регистра находятся единицы, в результате триггер 7, установится в единичное состояние. По шестому тактовому импульсу в регистре 2 формируется ко 011000011, содержимое счетчика равно шести, что соответствует нахождению первого и второго разрядов нормализуемого кода соответственно в двух старших разрядах регистра, в результат возбуждается выход дешифратора. По седьмом тактовому импульсу на регистре формируется код 001100001, по восьмому импульсу 100110000, т. с. возникает единица циклическо го переноса, по девятому тактовому импульсу 010011000 и на счетчике возникает сигнал переполнения, однако, так как триггер 7 находится в единичном состоянии, этот сигнал не вызывает обнуления триггера 8, в результат на управляющий вход сдвигового регистра поступает новая серия на девяти тактовых импульсов. Через время элемента, задержки 9 триггер 7 обнуляется. По шестому тактовому импульсу срабатывает дешифратор, на выходе элемента 17 устанавливается единица и в результате осуществляется сдвет единицы в двух старших разрядах регистра 2. В течение этой серии TakTOBbix импульсов триггер 7 не устанавливается в единичное состояние, в результате чего сигнал переполнения счетчика устанавливает в нуль триггер 8, что блокирует прохождение импульсов от генератора 13 на .управляющий вход регистра. На этом нормализация заканчивается и со сдвигового регистра: 2 считывается нормализованный код - 01000100. После этого снимается сигнал с шины 25. В режиме контроля в отличие от режима, нормализации на шине 25 устанавливается нулевой сигнал. В результате после установки триггера 8 в единичное состояние на сдвиго; вый регистр от генератора поступает только одна серия тактовых импульсов.. При этом, если в каких-либо соседних разрядах кода окажутся две единицы, триггер 22 устанавливается в единичное состояние, и на контрольном выходе 3 устройства появляется сигнал оижбки. По сравнению с прототипом 3 в данном устройстве используется только один блок свертки нместо п, что позволяет сокра16тить аппаратурные затраты для кодой, ссютветствующих диапазонам чисел реальных специализированных ЦВМ более, чем в 10 раз. Формула изобретения 1. Устройство для нормализации кодов . Фибоначчи, содержащее блок свертки, отличающееся тем, что, с целью снижения аппаратурных затрат, устройство содержит празрядный сдвиговый регистр, два т тиггера, три элемента И, генератор импульсов, счетчик, элемент задержки, причем первый вход первого элемента И соединен со входом задания режима работы устройства и первым входом блока свертки, второй вход - с выходом нулевого разряда сдвигового регистра, третий вход с выходом первого разряда сдвигового регистра, а выход - с единичным входом первого триггера, нулевой вход которого соединен с выходом элемента задержки, .а нулевой выход подключен к первому входу второго элемента И, второй вход которого соединен с выходом переполнения счетчика и входом .элемента задержки, а выход подключен к нулевому входу второго триггера, единишаш вход которого соединен с -входом начала работы устройства, а выход подключен к первому входу третьего элемента И, второй вход которого соединен с выходом генератора импульсов, а выход подключен к входу счетчика и тактовому входу сдвигового регистра, входы разрядов с первого по (п-1)-й которого являются информационными входами устройства, вход нулевого разряда регистра соединен с первым выходом блока свертки, нулевой вход (п-2)-го разряда и единичный вход (п-1)-го разряда соединены со вторым выходом блока свертки, а выходы (п-2)-го и (n-l)-ro разрядов и выход переноса сдвигового регистра соединены со вторым, третьим и четвертым входами блока свертки соответственно, разрядный выход счетчика подключен к пятому входу блока свертки, выходы разрядов счетчика, с первого по (п-1)- и, являются информационными, а третий выход блока свертки - контрольным выходом устройства. 2. Устройство по п. 1, отличающее - с я тем, что блок свертки содержит первый триггер, первый элемент И, два элемента ИЛИ, два элемента запрета, второй элемент И, элемент И, элемент задержки, дешифратор, второй триггер, причем первый вход первого элемента И соединен с инверсным выходом первого элеента ИЛИ и с первым входом второго элемента И, второй вход первого элемента И соединен первым информационным входом первого элемента запрета и вторым входом блока свергки, третий вход соединен с управляющим входом первого элемента запрета и третьим входом блока свертки, а выход - подключен к единичному входу первого триггера, первому входу второго элемента ИЛИ и информационному входу второго элемента запрета, управляющий вход которого соединен с первм входом блока свертки, а выход соединен с единичным входом второго триггера, выход которого соединен с. третьим выходом блока (жертки, нулевой вход первого триггера соединен с выходом элемента задержки и первьгм входом первого элемента ИЛИ, а выход - соединен со входом элемента задержки и вторым входом первого элемента ИЛИ, кроме того, выход первого элемента за прета соединен со вторым выходом блока свертки, а его второй информационный вход соединен с выходом дешифратора, вход которого соединен с пятым входом блока свертки, второй вход второго элемента И соединен с четвертым входом блока свертки, а выход подключен ко второму входу второго элемента ИЛИ, выход которого соединен с первым выходом блока свертки. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 732864, кл. G 06 F 7/38, 1980. 2.Авторское свидетельство СССР по заявке N 2888652/18-24, кл. G 11 С 19/00, 1979. 3.Авторское свидетельство СССР № 662930, кл. G 06 F 5/00, 1979 (прототип).

L

to