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

(19) (11) 51)5 Н 03 М 7/3 САНИЕ ИЗОБРЕТЕНИЯ госуда ственный номитетПО ИЭОБР 1: ТЕНИЯМ И ОТКРЫТИЯМПРИ ГННТ СССР АВТОРСКОМУ СВИДЕТЕЛЬ(71) Кубанский государственный университет(56) Авторское свидетельство СССР У 1392554, кл. Н 03 М 7/30, 1926.Авторское свидетельство СССР У 662930, кл. Н 03 М 7/30, 1976. (54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ р-КОДОВ ФИБОНАЧЧИ К МИНИМАЛЬНОЙ ФОРМЕ. (57) Изобретение относится к вычисли 2тельной технике и может быть использовано для приведения кодовых слов к минимальной форме изображений в базисе р-систем счисления Фибоначчи, а также может выполнять функции счетчика. С целью расширения функциональных возможностей за счет способности приводить к минимальной форме кодовые слова при р2 устройство содержит в каждом разряде триггер 1, элементы ИЛИ 2 и 3, с первого по р-й элементы И 4-6, элемент НЕ 7, с первого по (р)-й элементы 8, 9 запрета с соответствующими связями. 1 ил.3 15470Изобретение относится к вычислительной технике и может быть исполь- зовано для приведения кодовых слов к минимальной форме изображений в5 базисе р-систем счисления фибоначчи, а также может выполнять функции счетчика.Цель изобретения " расширение Функциональных возможностей за счет спо собности приводить к минимальной форме кодовые слова при р2.На чертеже представлена схема разряда устройства для приведения р-кодов фибоначчи к минимальной форме.Разряд устройства содержит триггер 1, первый и второй элементы ИЛИ 2 и 3 с первого по р-й элементы И 4-6, элемент НЕ 7, с первого по (р)-й элементы 8 и 9 запрета, вход 10 разряда информационного входа устройства, вход 11 сброса устройства, группу входов 12 запуска устройства, входы 13"21 и выходы 22-25 разряда устройства. 25р-Системы счисления фибоначчи задаются рекурентным выражениемО, при п(0; (п)= 1, при О п (р; (1)РЕ с(п-р), при и ) р, 30 где д(п) - имя системы счисления; и - номер текущего разряда(и Оч 1 е 2 з11) р - номер системы счисления (р = 0,1,2п, в общем 35 случае и Ф р), Операция приведения р-кодов к минимальной Форме описывается выраже нием:нЧ(п)+ фп-р+11)= ц(з.) +Е(пр -1+И-з.), (2) где Б = 1(р).В основу операции свертки положено 45равенство единице содержимого триггеров 1 (г)-го и (г-р+Щ-го разрядов: а(г)=,а(г-р+И)=1; равенство нулю содержимого триггер50 ров г-го и Х (гр+14-1)-х разряд дов: а(г)=а( Е (гр+И-.= О,1: После выполнения операции свертки а( -1) = а(г-р+и) = О; Ю55 а(г) = а(; (гр+0-11,Устройство работает следующим образом. Снятие напряжения "1" с входа 12 разрешает работу Устройства, Допустим, что на вход 21 пришли все единичные сигналы.Это свидетельствует офтом, что триггеры 1 Е (гр+И-)-х,/аразрядов находятся в нулевом состоянии. Пусть триггер 1 рассматриваемого разряда также находится в нулевом состоянии, а триггер 1 (г)-го разряда - в единичном, что приводит к появлению на всех входах элемента И 6 сигналов "1". Единичный сигнал с выхода элемента 9 запрета закрывает элемент Иб и элемент 8 запрета, а через элемент НЕ 7 - элемент И 4.Сигнал "1" с выхода элемента Иб через элемент ИЛИ 3 устанавливает триггер 1 в единичное состояние,сбрасывает через выходы 22 и 25 триггеры 1 соответственно (г-р+11)-го и (г)-го разрядов, устанавливает в единичное состояние через выходы 23итриггеры 1.Е (гр+и) -х разрядов.1-После выполнения операций свертки (приведения к форме изображений) с выхода 24 снимается результат, через вход 11 триггеры 1 обнуляются и устройство готово к приему нового операнда.В случае, если на входе 21 присутствует хотя бы один сигнал "0", на выходе элемента 9 запрета появляется нулевой сигнал, который закрывает элемент Иб, но открывает элемент 8 запрета. Если на входах 20 элемента 8 запрета присутствуют сигналы "1", то происходят аналогичные описанные выше для элемента 9 запрета переключения. Если же на входе 20 присутствует хотя бы один нулевой сигнал, то на выходе элемента 8 запрета появляется сигнал, разрешающий анализ состояния входов 14 и 15, Если же и на них нулевой сигнал, то изменений в г-м разряде не происходит, но они происходят в других разрядах аналогично описанному для г"го разряда.П р и м е р, Привести к минимальной Форме изображений (представлений) кодовое слово в 3-системе счисления фибоначчи,Операции свертки описываются соотношениями, вытекающими иэ выражения:110 55Равенство нулю веса отрицательных разрядов делает ненужным их использование, однако связи положительных При опросе разрядов, начиная со старших, условия свертки выполняются только в пятом разряде. В одиннадцатом разряде этого не происходит в силу того, что перенос в четвертый разряд запрещен наличием в нем "1". Это 20 приводит к тому, что на выходе элемента 8 запрета одиннадцатого разряда присутствует нулевой сигнал. В пятом разряде на входах элемента И 6 имеются четыре единичных сигнала; с инверсного выхода триггера 1 своего разряда, с прямых выходов триггеров 1 четвертого и третьего разрядов и с выхода элемента 9 запрета, так как в входы его подключены к триггерам 1 отрицательных разрядов, следовательно, на них имеются "1". Единичный сигнал с выхода элемента И 6 через элемент ИЛИ 3 устанавливает триггер 1 пятого разряда и сбрасывает через элементы ИЛИ 2 в "0" триггеры 1 третьего и четвертого разрядов. Следующий опрос приводит к тому, что в одиннадцатом разряде на выходе элемента И 5 появляется "1", так как на его входе имеется "1" с инверсного выхода триггера 1 одиннадцатого разряда с прямых выходов триггеров 1 десятого и восьмого разрядов и с выхода элемента 8 запрета. Это приводит к тому, что в единичное состояние устанавливают через элементы ИЛИ 3 одиннадцатого и.четвертого раз.рядов соответствующие им триггеры 1. Следующей выполняется операция свертки в шестом разряде аналогично опи 50 санному для пятого. Перенос "1" из нулевого разряда описан выше. Для седьмого разряда - аналогично одиннадцатому разряду,73 6разрядов с отрицательными надо оставить. Это означает, что на входах 14,15, 16 , 17, 20 и 2 1, "соединенных"с соответствующими. отрицательными1разрядами, присутствует постоянноенапряжение "1",выходы 22 и 23, идущие в отрицательные разряды, заземлены,Рассмотрим механизм переноса "1" из нулевого разряда в третий. Опрос входов 12, начиная со старших разрядов, приводит к тому, что в первом разряде на входах элемента 9 запрета появляются логические единичные сигналы (на его входах 2 1, идущих в отрицательные разряды, присутствует постоянный сигнал "1"). Это приводит к появлению "1" на выходе элемента И 6, так как на его входах имеется "1" с инверсногсг выхода триггера первого разряда, с прямых выходов триггеров нулевого и минус первого разрядов. Единичный сигнал через элемент ИЛИ 3 устанавливает в единичное состояние триггер 1 первого разряда и сбрасывает в нулевое состояние триггер нулевого разряда. Появление "1" в первом разряде приводит к следующим процессам во втором разряде. Элемент 8 запрета заперт сигналом с выхода элемента 9 запрета. Следовательно, единичный сигнал на выходе элемента НЕ 7 приводит к появлению "1" на выходе элемента И 4, так как на его входах присутствуют "1" с инверсного выхода второго разряда, с прямых выходов первого и минус второго разрядов с,. выхода элемента НЕ 7. Это приводит к установке в единичное состояние триггера 1 второго разряда и обнулению триггера 1 первого разряда. Появление единичного сигнала во втором разряде приводит к аналогичному процессу в третьем разряде, результатом которого является установка в единичное состояние триггера 1 третьего разряда и обнуление триггера 1,нулевого разряда. Таким образом, происходит перенос "1" из нулевого разряда в третий разряд. Появление второй "1" на входе 10 нулевого разряда приводит в четвертом разряде к процессу, схожему с процессом, описанным для второго разряда, результатом которого является установка в единичное состояние триггера 1 четвертого разряда и обнуление триггеров 1 третье-3 -2 -1 0 1 2 0 О 0 1, 1 11 0 0 0 1 0 0 0 1 0 О 0 1 0 0 0 О О 1 0 0 0 1 0 0 О 0 1 О 0 0 1 0 0 0 1 0 0 0 7 8 5 710 0 0 0 0 0 0 0 0 0 0 О 0 0 0 О 0 О 0 0 О 0 0 О 0 0 0 0 0 0 0 0 0 0 0 О 0 0 0 0 иР (и)ввод ."1" Ввод "1"Ввод "1 Ввод "1" 40 гО и нулевого разрядов. 11 редставимописанный пример схематически, из коФормула изобретения Устройство для привецения р-кодов Фибоначчи к минимальной форме,содерЩащез в каждом г-м разряде триггер,н 25 цервьй элемент И, первыи и второи элементы ИЛИ, элемент НЕ, причем к 1 ходы разрядов информационного входа устройства соединены с первыми вхоами вторых элементов ИЛИ соответтвующих разрядов устройства, выходы 30 которых соединены со счетными входаМи триггеров соответствующих разрядов3 1 стр ойства , входы установки в 0 от орых с оединены с выходами и ерых элементов ИЛИ соответствующих аз р ядов устройства, первые входы от орых объединены и соединены с входом сброса устройства , инверсные выходы триггеров разрядов устройства соединены с первыми входами первых элементов . И соответствующих разрядов устройства , выходы которых соедине ны с вторыми входами вторых элементов ИЛИ соответствующих разрядов устройства, второй и третий входы первого элемента И г-го разряда устрой ства соединены соот ветственно с прямыми выходами триггеров ( г ) -г о и ( г-р ) -го разрядов устройства , четв ер тые входы первых элементов И разрядов устройства содинены с выходами элементов НЕ соответствующих ра зрядов устройства, второй и третий входы первого элемента ИЛИ г-г о разряда устройства соединены соответственно с выходами первых элементов И .( г+ 1 ) -г о и ( г+р+ 1 ) -г о разрядов устройства, пряЮые выходы триггеров разрядов устройства являются выходами соответствуюторого также поясняется работа устройства в качестве счетчика. щих разрядов устройства, о т л и ч аю щ е е с я тем, что, с целью расши-рения функциональных возможностей засчет способности приводить к минимальной форме кодовые слова пои и Ъ 2г-й разояд устройства содержит с второго по р-й элементы И и с первогопо (р)-й элементы запрета, причемвыход второго элемента ИЛИ г-го разряда устройства соединен с четвертымвходом первого элемента ИЛИ (г)-горазряда устройства, первые входы свторого по р-й элементов И разрядовустройства соединены с инверсными выходами триггеров соответствующихразрядов устройства, вторые входы свторого по в-й элементов И г-го разряда устройства соединены с прямымвыходом триггера (г)-го разрядаустройства, третий вход (К+1)-го(К+1)-го элемента И к-го разряда уст.ройства соединен с выходом К-го элемента запрета г-го разряда устройства, выход первого элемента запретаг-го разряда устройства соединен свходом элемента НЕ г-го разряда устройства, выход К-го, кроме первого,элемента запрета г-го разряда устройства соединен с управляющим входом(К)-го элемента запрета г-го разряда устройства, входы запуска группы устройства соединены с управляющими входами (р)-х элементов запре"та соответствующих разрядов устройства, выход (К+1)-го элемента и г-го1 О 1547073 ветственно (И = 0,1,р11 =1,2рр 1 = 1,20; Фп), к входам с пятого по (р+1)-й первого Составитель А. КлюевТехред Л.Сердюкова Корректор В. Гирняк ющ Редактор А. Лежнина Заказ 85 Тираж 656 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., д. 4/5Производственно-издательский комбинат "Патент", г,ужгород, ул. Гагарина, 101 входом второго элемента ИЛИ г-го разряда устройства, выходы с второго по р-й элементов И г-го разряда устРройства подключены к с; (р 1+и)-мф входам вторых элементов ИЛИ(гр 1-. 1 -1+11-х)-х разрядов устройства соотэлемента ИЛИ г-го разряда устройства подключены выходы с второго по р-й элементов И.(г+р+1-Б)-го разрядан устройства соответственно(и+1)-еУ информационные входы с первого по (р)-й элементов запрета г-го разряда устройства соединены с инверснымии