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

1

(21)4412455/24-24

(22)18.04.88

(46) 28.02.90. Бюп. № 8

(71)Кубанский государственный университет

(72)В.В. Дудкин и Н.А. Яковенко

(53)681.3(088,8)

(56)Авторское свидетельство СССР 1392554, кл. Н 03 М 7/30, 1926.

Авторское свидетельство СССР 662930, кл. Н 03 М 7/30, 1976.

(54)УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ р-КО- ДОВ ФИБОНАЧЧИ К МИНИМАЛЬНОЙ ФОРМЕ.

(57)Изобретение относится к вычислительной технике и может быть использовано для приведения кодовых слов к минимальной форме изображений в базисе р-систем счисления Фибоначчи, а также может выполнять функции счетчика. С целью расширения функциональных возможностей за счет способности приводить к минимальной форме кодовые |слова при р 2 устройство содержит в- каждом разряде триггер 1, элементы ИЛИ 2 и 3, с первого по р-й элементы И 4-6, элемент НЕ 7, с первого по (р-1)-й элементы 8, 9 запрета с соответствующими связями. 1 ил.

Изобретение относится к вычислительной технике и может быть использовано для приведения кодовых слов к минимальной форме изображений в базисе P-систем счисления Фибоначчи, а также выполнять функции счетчика. С целью расширения функциональных возможностей за счет способности приводить к минимальной форме кодовые слова при P*982 устройство содержит в каждом разряде триггер 1, элементы ИЛИ 2 и 3, с первого по P-й элементы И 4-6, элемент НЕ 7, с первого по (P-1)-й элементы 8,9 запрета с соответствующими связями. 1 ил.

«И7 21

12

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

Цель изобретения - расширение функциональных возможностей за счет спо-jg Го разряда также находится в нулевом

собности приводить к минимальной форме кодовые слова при .

На чертеже представлена схема разряда устройства для приведения р-кодов Фибоначчи к минимальной форме. с л -3

Разряд устройства содержит триггер

1, первый и второй элементы ИЛИ 2 и 3, с первого по р-й элементы И 4-6, элемент НЕ 7, с первого по (р-1)-й элементы 8 и 9 запрета, вход 10 разряда информационного входа устройства, вход И сброса устройства, группу входов 12 запуска устройства, входы 13-21 и выходы 22-25 разряда устройства о

р-Системы счисления Фибоначчи задаются рекурентным выражением

0,при п г 0;

1,при 0 п р; (1)

20

25

Чр(и)

состоянии, а триггер 1 (г-1)-го разряда - в единичном, что приводит к появлению на всех входах элемента И 6 сигналов Единичный сигнал с выхода элемента 9 запрета закрывает элемент И6 и элемент 8 запрета, а через элемент НЕ 7 - элемент И40 Сигнал 1 с выхода элемента И6 через элемент ИЛИ 3 устанавливает триггер 1 в единичное состояние,сбрасывает через выходы 22 и 25 триггеры 1 соответственно (г-р-1+Ы)то и Јг-1)-го разрядов, устанавливает в

единичное состояние через выходы 23, н

триггеры 1 Т (г-2p-1+n-j)-x разрядов.

Ь

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

I 0 tfpCn-p-J ) , при п

где (п) системы счисления;

п

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

- номер текущего разряда

(п (),1,2,...N); р - номер системы счисления

(р 0,1,2,...,п, в общем35 ствует хотя бы один сигнал U, на случае п 4- р)выходе элемента 9 запрета появляется

Операция приведения р-кодов к ми- нулевой сигнал, который закрывает

элемент Иб, но открывает элемент 8

В случае, если на входе 21 присут

0,

нимальной форме описывается выражением:

П„9т1- 40

(n-1)(n p-1+N) (i) + Ъ-1 п-2р- -l+N-i), (2)

где N 1,...„(р-1).

В основу операции свертки положено

равенство единице содержимого триггеров 1 (г-1)-го и (r-p-1+NJ-ro разрядов: Q(r-1)Q(r-p-1+N)1;

равенство нулю содержимого триггемров r-го и 21 (r-2p-1+N-j)-x разряi N

дов: Q(r)Q( (r-2p-H-N-j)) О.

) После выполнения операции свертки

Q(r-1) Q(r-p-1+N) 0;

Q(r) Q(i: r-2p-UN-j)) 1.

Ь

Устройство работает следующим образом.

запрета. Если на входах 20 элемента 8 запрета присутствуют сигналы 1, то происходят аналогичные описанные выше для элемента 9 запрета переключения. Если же на входе 20 присутствует хотя бы один нулевой сигнал, то

дг на выходе элемента 8 запрета появляется сигнал, разрешающий анализ состояния входов 14 и 15. Если же и на них нулевой сигнал, то изменений в r-м разряде не происходит, но они

, (происходят в других раарядах аналогично описанному для r-го разряда.

55

Пример. Привести к минимальной форме изображений (представлений кодовое слово в 3-системе счисления Фибоначчи.

Операции свертки описываются соотношениями, вытекающими из выражения:

Снятие напряжения 1 с входа 12 разрешает работу устройства. Допустим, что на вход 21 пришли все единичные сигналы.Это свидетельствует о

м

том, что триггеры 1 21 (r-2p-1+N-j)-x

разрядов находятся в нулевом состоянии. Пусть триггер 1 рассматриваемо

состоянии, а триггер 1 (г-1)-го разряда - в единичном, что приводит к появлению на всех входах элемента И 6 сигналов Единичный сигнал с выхода элемента 9 запрета закрывает элемент И6 и элемент 8 запрета, а через элемент НЕ 7 - элемент И40 Сигнал 1 с выхода элемента И6 через элемент ИЛИ 3 устанавливает триггер 1 в единичное состояние,сбрасывает через выходы 22 и 25 триггеры 1 соответственно (г-р-1+Ы)то и Јг-1)-го разрядов, устанавливает в

единичное состояние через выходы 23, н

триггеры 1 Т (г-2p-1+n-j)-x разрядов.

Ь

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

ует хотя бы один сигнал U, на оде элемента 9 запрета появляется

В случае, если на входе 21 присут 0,

запрета. Если на входах 20 элемента 8 запрета присутствуют сигналы 1, то происходят аналогичные описанные выше для элемента 9 запрета переключения. Если же на входе 20 присутствует хотя бы один нулевой сигнал, то

на выходе элемента 8 запрета появляется сигнал, разрешающий анализ состояния входов 14 и 15. Если же и на них нулевой сигнал, то изменений в r-м разряде не происходит, но они

(происходят в других раарядах аналогично описанному для r-го разряда.

Пример. Привести к минимальной форме изображений (представлений) кодовое слово в 3-системе счисления Фибоначчи.

Операции свертки описываются соотношениями, вытекающими из выражения:

Л01234567

9 1

V3(n) 1 1 1 123457+0+4 Операнд 000110001 0 1

При опросе разрядов, начиная со старших, условия свертки выполняются только в пятом разряде. В одиннадцатом разряде этого не происходит в силу того, что перенос в четвертый разряд запрещен наличием в нем I Это приводит к тому, что на выходе элемента 8 запрета одиннадцатого разряда присутствует нулевой сигнал. В пятом разряде на входах элемента И 6 имеются четыре единичных сигнала: с инверсного выхода триггера 1 своего разряда, с прямых выходов триггеров 1 четвертого и третьего разрядов и с выхода элемента 9 запрета, так как в входы его подключены к триггерам 1

из нулевого разряда в третий. Опрос входов 12, начиная со старших разрядов, приводит к тому, что в первом

j 5 разряде на входах элемента 9 запрета появляются логические единичные сигналы (на его входах 21, идущих в отрицательные разряды, присутствует постоянный сигнал 1). Это приводит

20 к появлению 1 на выходе элемента Иб, так как на его входах имеется 1 с инверсного- выхода триггера первого разряда, с прямых выходов триггеров нулевого и минус первого разрядов.

25 Единичный сигнал через элемент ИЛИ 3 устанавливает в единичное состояние триггер 1 первого разряда и сбрасывает в нулевое состояние триггер нув перлевого разряда. Появление 1

30 вом разряде приводит к следующим проотрицательных разрядов, следователь- цессам во втором разряде. Элемент 8 но, на них имеются 1. Единичный сигнал с выхода элемента И 6 через элемент ИЛИ 3- устанавливает триггер 1 пятого разряда и сбрасывает через

35

запрета заперт сигналом с выхода элемента 9 запрета. Следовательно, единичный сигнал на выходе элемента НЕ 7

элементы ИЛИ 2 в О триггеры 1 третьего и четвертого разрядов. Следующий опрос приводит к тому, что в одиннадцатом разряде на выходе элемента И5 появляется 1, так как на его входе имеется 1 с инверсного выхода триггера 1 одиннадцатого разряда у с прямых выходов триггеров 1 десятого и восьмого разрядов и с выхода элемента 8 запрета. Это приводит к тому, что в единичное состояние устанавливают через элементы ИЛИ 3 одиннадцатого и четвертого разрядов соответствующие им триггеры 1.

40

элемента И4, так как на его входах присутствуют 1 с инверсного выхода второго разряда, с прямых выходов первого и минус второго разрядов с выхода элемента НЕ 7. Это приводит к установке в единичное состояние триггера 1 второго разряда и обнулению триггера 1 первого разряда. Появление единичного сигнала во втором разряде 45 приводит к аналогичному процессу в третьем разряде, результатом которого является установка в единичное состояние триггера 1 третьего разря- .да и обнуление триггера 1;нулевого

элемента И4, так как на его входа присутствуют 1 с инверсного выхо второго разряда, с прямых выходов первого и минус второго разрядов с выхода элемента НЕ 7. Это приводит установке в единичное состояние тр гера 1 второго разряда и обнулению триггера 1 первого разряда. Появле единичного сигнала во втором разря 45 приводит к аналогичному процессу в третьем разряде, результатом котор го является установка в единичное состояние триггера 1 третьего разр .да и обнуление триггера 1;нулевого

Следующей выполняется операция сверт- разряда. Таким образом, происходит ки в шестом разряде аналогично опи-- перенос 11 из нулевого разряда в третий разряд. Появление второй 1 на входе 10 нулевого разряда приводит в четвертом разряде к процессу гс схожему с процессом, описанным для второго разряда, результатом которого является установка в единичное состояние триггера 1 четвертого раз ряда и обнуление триггеров 1 третье

санному для пятого. Перенос 1 из нулевого разряда описан выше. Для седьмого разряда - аналогично одиннадцатому разряду.

I

Равенство нулю веса отрицательных разрядов делает ненужным их использование, однако связи положительных

470736

разрядов с отрицательными надо оста- вить. Это означает, что на входах 14, 15, 16, 17, 20 и 21, соединенных с соответствующими отрицательными разрядами, присутствует постоянное напряжение 1,выходы 22 и 23, идущие в отрицательные разряды, заземлены.

10 ,

Рассмотрим механизм переноса 1

из нулевого разряда в третий. Опрос входов 12, начиная со старших разрядов, приводит к тому, что в первом

j 5 разряде на входах элемента 9 запрета появляются логические единичные сигналы (на его входах 21, идущих в отрицательные разряды, присутствует постоянный сигнал 1). Это приводит

20 к появлению 1 на выходе элемента Иб, так как на его входах имеется 1 с инверсного- выхода триггера первого разряда, с прямых выходов триггеров нулевого и минус первого разрядов.

25 Единичный сигнал через элемент ИЛИ 3 устанавливает в единичное состояние триггер 1 первого разряда и сбрасывает в нулевое состояние триггер нув перлевого разряда. Появление 1

цессам во втором разряде. Элемент 8

запрета заперт сигналом с выхода элемента 9 запрета. Следовательно, единичный сигнал на выходе элемента НЕ 7

элемента И4, так как на его входах присутствуют 1 с инверсного выхода второго разряда, с прямых выходов первого и минус второго разрядов с выхода элемента НЕ 7. Это приводит к установке в единичное состояние триггера 1 второго разряда и обнулению триггера 1 первого разряда. Появление единичного сигнала во втором разряде приводит к аналогичному процессу в третьем разряде, результатом которого является установка в единичное состояние триггера 1 третьего разря- да и обнуление триггера 1;нулевого

разряда. Таким образом, происходит - разряда. Таким образом, происходит - перенос 11 из нулевого разряда в третий разряд. Появление второй 1 на входе 10 нулевого разряда приводит в четвертом разряде к процессу, с схожему с процессом, описанным для второго разряда, результатом которого является установка в единичное состояние триггера 1 четвертого разряда и обнуление триггеров 1 третьеrft и нулевого разрядов. Представим описанный пример схематически, из ко

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

Устройство для приведения р-кодов Фибоначчи к минимальной форме,содер- 1ащее в каждом r-м разряде триггер, г ервый элемент И, первьй и второй элементы ИЛИ, элемент НЕ, причем разрядов информационного входа Устройства соединены с первыми входами вторых элементов ИЛИ соответ- с твующих разрядов устройства, выходы которых соединены со счетными входами триггеров соответствующих разрядов Устройства, входы установки в О которых соединены с выходами первых элементов ИЛИ соответствующих разрядов устройства, первые входы Которых объединены и соединены с входом сброса устройства, инверсные выходы триггеров разрядов устройст- йа соединены с первыми входами первых элементов И соответствующих разрядов устройства, выходы которых соединены с вторыми входами вторых элементов ИЛИ соответствующих разрядов устройства, второй и третий входы первого элемента И r-го разряда устройства соединены соответственно с прямыми выходами триггеров (г-1)-го и (г-р-1)-го разрядов устройства,чет- вертые входы первых элементов И разрядов устройства содийены с выходами элементов НЕ соответствующих разрядов устройства, второй и третий входы . первого элемента ИЛИ r-го разряда устройства соединены соответственно с выходами первых элементов И (,г-М)-г и (г+р+1)-го разрядов устройства, прмые выходы триггеров разрядов устройства являются выходами соответствую

торого также поясняется работа устройства в качестве счетчика.

5

0

5

0

45

50

55

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

9 1547073Ю

входом второго элемента ИЛИ r-гоэлемента ИЛИ r-го разряда устройстразряда устройства, выходы с второгова подключены выходы с второго по

по р-й элементов И r-го разряда уст-Р-Й элементов И (r+p+1-N)-ro разряда

Р , , ц

ройства подключены к (Р+1+п)-м, устройства соответственно, 51 (п-М)-е

1 НI

входам вторых элементов ИЛИ 2 (г-2р-информационные входы с первого по

-1+N-i)-x разрядов устройства соот-(р-О-й элементов запрета r-го разряда устройства соединены с инверсными

ветственно (N 0,1,...,р-1; п .

12 D- т - 1 2 N- vвыходами триггеров (r-2p-1+N-i)-x

- i,c,os.,p, 1 - I,:,...,.и, ) t кUi

входам с пятого по (р+1)-й первогоразрядов устройства соответственно.