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

 

,.,>>l ee."», дс о f. f, А

Соеэ Соаетскнк

Сощналнстнческнк

Рес ублнк

<>662930

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. саид-ву (22) Заявлено 0?0876(21) 2386002/18-24 (51)М. Кл.

G 06 F 5/00 с присоединением заявки №Государственный комитет

СССР но делам нэобретеннй н открытий (23) Приоритет -. (53) УДК 681 327 (088.8) Опубликовано 15,0579 Бюллетень Мо18

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

A Ï.Ñòàõîâ и Л.В.Фомичев с (71) Заявитель таганрогский радиотехнический институт им. В.Д.Калмыкова (54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ р-КОДОВ

ФИБОНАЧЧИ К МИНИМАЛЬНОЙ ФОРМЕ l0

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

Под р-кодами Фибоначчи понимается представление любого натурального числа N s виде суммы

" f0añq „ e где р - заданное натуральное число,, определянщее номер р-кода Фибоначчиу и =разность р-кода Фибоначчиу 15 ат- двоичная цифра (О или 1) в т, -ом разряде р-кода Фибоначчи; р(с) - вес 2-ro разряда р-кода

Фибоначчи (р-число Фибоначчи), зада-. ваемый следующим рекуррентным соотношениемм:

Одри 1 0

Lp (6) i opH 3 ° 0 ср 6-1)e(e (6-р-11нри 0 0.

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

2 р нулевых разрядов. При выполнении преобразованйй информации в цйфровой ,вычислительйой машине . (ЦВМ)» аналогоцифровых (РЦП) и цйфроаналоговых (ц П) преобразователях над мнимальными формами р-кодов Фибоначчи все информацйонные операции приобретают свойство естественного самоконтроля, что ведет к повышению информационной надежности ЦВЙ, ЛЦП и ЦАП.

Новой операцией над кодами в ЦВМ, АЦП и ЦАП, работаюШих в р-кодах Фибоначчи являетси операция приведения р-кодов Фибоначчи к минимальной форме.

Устройства для приведения р-кодов

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

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

Кроме того блок свертки содержит триггер, элемент И, первый и второй элемент ИЛИ, причем выход элемента И соединен с первым входом первого элемента ИЛИ и является первым выходом блока, единичный выход триггера явля-10 ется вторым выходом блока, первый и второй входы блока соединены соответственно с первым и вторым входами второго элемента ИЛИ, выход которого соединен с нулевым входом тригге- 15 ра, нулевой выход триггера соединен с первым входом элемента И, второй, третий и четвертый входы которого являются соответственно третьим, чет-вертым и пятым входами блока, второй 20 вход первого элемента ИЛИ является шестым входом блока, выход первого элемейта ИЛИ соединен с единичным входом триггера. На фиг.l изображено устройство 25 для приведения l-кодов Фибоначчи к минимальной форме °

Устройство содержит п однотипиых блоков 1 свертки, где п=5 и означает разрядность р-кода Фибоначчи. Первый выход 2 2-го блока 1 соединен с пер вым входом 3 (К-1) и вторым входом 4 (E-l-1) блока 1. Вторбй выход 5 P-ro блока 1 (2-3) является Р-ым информационным выход6м устройства и соедийен.3g с третьим входом б (.Х+1) и четвертым входом 7 (Р+1+1) блоков 1. Пятые входы 8 каждого блока l объединены и являются управляющим входом 9 устрой-" ства. Шестые входы 10 каждого блоха 1 являются информационными входами устройства.

Блок 1. содержит триггер 11, эле- .мейг 12 И, первый элемент 13 ЙЛИ и второй элемент 14 ИЛИ. Выход элемен- та 12 И соединен с первым входом эле- 45 мента 13 ИЛИ и является первым выходом 2 блока 1. Единичный выход триг- . гера 11 является вторым выходом 5 блока 1. Первый вход 3 и второй вход

4 блока 1 соединены соответственно 80 с первым и вторым входами элемента 14

ИЛИ, выход кдторого соединен с нулев1ым входом триггера 11. Нулевой выход триггера 11 соединен с первым входом

=-лемента 12 И, второй, третий и чет- 55 вертый входы которого являются соответственно входом 7, входом б и входом 8 устройства. Второй вход элемен.та 13 ИЛИ является входом 10 блока 1, а выход элемента 13 ИЛИ соединен с единичным. входом триггера 11.

662930

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

Устройство содержит п блоков 1 свертки (n=5) . Здесь каждый блок 1

- имеет также четвертый нулевой информационный вы::од 15, седьмой вход 16, пятый выход 17, (2-1) восьмых входов

181 — 18, девятый вход 19,(2+1) десятых входов 201 - 20 +< (2+1)

6динадцатых входов 211 — 21 +, шестой выход 22. Девятые выходы 19 каждого блока 1 объединены и являются вторым управляющим входом 23 устройства. Пятый выход 17 Р-ro блока 1 соединен со входом 21> (0-2-j+1} блока 1. Шестой выход 22 Р-го блока 1 соединен со входом 18; (Р-i) блока 1.

Четвертый выход 15 блока 1 соединен с седьмым входом 16 (,0-1) блока 1 и со входом 20э (3+2+э-1) блока 1, причем j=s=l 2p 2+1 1= 1, 2,. ° ., 2+1. Блок 1 в этом случае содержит также второй элемент 24 И и элемент

25 НЕ, вход которого соединен с выходом элвмента 12 И, а выход является выходом 22 блока 1 свертки. Нулевой

° выход триггера.ll является четвертым входом 15 блока 1; (р-1) входов элемента 12 И, начиная с пятого, являются восьмыми входами 181-18 +1 блока 1. Первый вход второго элемента

24 И соединен с единичным выходом триггера ll. Второй и третий входы элемента 24 И являются входом 19 и входом 16 соответственно блока 1, а оставшиеся (2+1) входов второго элемента 24 И являются десятыми входами 201 -20 +, блока l. Выход второго элемента 24 И соединен с третьим входом второго элемента 14 ИЛИ и является пятым выходом 17 блока 1.

Устройство для приведения р-кодов

Фибоначчи к минимальной форме ра. ботает следующим образом.

На фиг.l представлена схема устройства для p l и n=5. Двоичная информация поступает на входы 10 устройства и через элементы 13 ИЛИ записывается в триггеры 11 блоков 1 свертки, находящиеся, до прихода информации на входы 10, в нулевом состоянии. При подаче единичного сИгнала на управляющий вхбд 9 устройства, этот сигнал поступает на один из входов элемента 12 И всех блоков 1. Элемент 12 И, будучи связанным с триггерами 11 блоков 1 P-ro, (М-1) и (2-1-1) так,как описано выше, анализирует состояние триггеров 11 этих блоков. На всех входах элемента 12 И будет присутствовать единичный сигнал, т.е. выполнится условие свертки, если триггер 11 Ф-ro блока

1 находится в нулевом состоянии, а

g) триггера 11 (Rl) и (Я-1-1) блоков 1 находятся в единичном состоянии и на управляющий вход 9 поступает единичный сигнал. В этом случае на выходе элемента 12 И 0-го блока 1 вырабатывается единичный сигнал, который поФормула изобретения

1. Устройство для приведения р-кодов Фибоначчи к минимальной форме, о т л и ч а io щ е. е с я тем, что оно содержит и однотипных блоков свертки, причем первый выход 2-го блока свертки соединен с первым входом (Ы-1) и . вторым входом (К-р-1) блоков свертки, второй выход 2-ro блока свертки является 2-ым информационйым выходом устройства и соединен с третьим входом (g+1) и четвартым входом {й+р+1) 5 662 ступает через элемент 13 ИЛИ на триггер 11 этой ячейки и устанавливает его в единичное состояние. Одновременно этот же сигнал с выхода 2 7-ro блока 1 свертки подается на вход

3 (2-1) и вход 4 (I?-1-1) блоков 1 и через элементы 14 ИЛИ записывает в триггеры ll этих блоков нулевые сигналы. Например в устройство записано число 5, представленное в 1-коде Фибоначчи, отличном от нормального ÂBåeñ cðàâÛÿ а -.: 0 3 2 1 1 . 10

1-код Фибоначчи 0 1 0 1 1

Условие свертки выполняется при подаче единичного сигнала, на управляющий вход 9 устройства для блока 1 с номером Р=З. Элемент 12 И этого блока вырабатывает единичный сигнал, который записывает в триггер 11 блока 1 с номером 1 3 едйничный сигнал, а в триггеры 11 блоков 1 с номерами .8=2 и 0 1 — нулевые сигналы. В результате число 0 1 0 1 1 принимает внд

1 1 0 О, вследствие чего выполняется условие свертки для блока 1 с номером 25 ° После проведения второй свертки число 01011 принимает вйд

10000, что соответствует минимальной форме числа 5, в 1-коде Фибоначчи.

Длительность управляющего сигнала, подаваемого на вход 9 устройства, должна быть заведомо больше времени, Необходимого для проведения всех воэ- 30 можных сверток. По окончании управляющего сигнала свертки информация:считывается с информационных выходов 5 устройства параллельно.

Операция свертки для чисел в 2-ко- 35 де. Фибоначчи осуществляется вышеописанным способом в устройстве, изображенном на фиг.2.

На фиг.2 изображено устройство для

-приведения 2-кода Фибоначчи к мини- мальной форме, реализующее также операцию развертки в тех случаях, когда проведение всех возможных сверток не обеспечивает получения минимальной формы 2-кода Фибоначчи. В этом случае 45 устройство, изображенное на фиг,2, реализует поочередно операции сверток и разверток. Элемент 24.И блока 1 анализирует состояние триггеров 11 (2+1), E и от (Ы-2) до (Р-2-2) блоков 1.

При наличии в триггерах 11 2+1 и от (Р-2) до (0-2-2) блоков 1 нулевых сигналов, а в триггере 11 2-го блока .1 единичного сигнала, условие свертки выполнено и при подаче на второй управляющий вход 23 единичного сигнала 55 на выходе элемента 24 И вырабатывается сигнал совпадения ° Этот сигнал пе реводит триггеры 11 Р и от (Р-2) до (Е-2-2) блоков 1 в инверсное состоянйе. После проведения всех возможных 60 разверток проводятся все возможные свертки. Во время проведения сверток элемент 25 И каждой ячейки вырабатывает сигнал запрета свертки, который устраняет неоднозначность приведения

930 6 числа к минимальной форме. Например, в устройство записано число 3, пред- ставленное в 2-коде.фибоначчи, отлич-ном от нормального.

Вес аз я а 3 2 1 1 1

2-код Фибоначчи 0 1 1 0 0

При подаче единйчного" управляющего сигнала на вход 9 устройства условие свертки не выполняется ни для одного блока 1, хотя код представлен в форме, отличной от минимальной. Подается единичный сигнал на вход 23. Условие: развертки выполняется для блока 1 свертки с номером К=З, Элемент 24 И этого блока вырабатывает единичный сигнал, который записывает в триггер

11 блока 1 с номером f 3 нулевой сигнал, а в триггеры с номерами от (8-2) до (М-2-2) — единичные сигналы. .В данном случае единичный сигнал запишется только в триггеры 11 блока 1 с номерами f=l и 8=2, так как остальные отсутствуют. В результате проведения развертки код 0110Д принимает вид 00111.

Дальнейшие развертки невозможны.

Подается опять единичный сигнал на вход 9 устройства. Условие свертки выполняется для блока 1 свертки с номером Й= 3. Код 00111 принимает вид 01010. Теперь условие свертки выполняется для блоков 1 с номерами

F=5 и Я=З. Но блок свертки вырабатывает сигнал запрета свертки, который подается на вход 18j блока 1 свертки с номером Ю=З и свертка в него эапрецена. Код 01010 принимает вид 10000, что соотве Свует минимальной форме . числа в 2-коде Фибоначчи.

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

Фибоначчи к минимальной форме используется при проведении операции суммирования для приведения к минимальной фор%е промежуточной суммы, Устройство можно использовать как многбвходовой счетчик импульсов в ркодах Фибоначчи, при этом входная информация подается на р младших разрядов °

6629 30 8 блоков свертки, управляющий вход йервый и второй входы блока соединены устройства соединен с пятыми входами соответственно с первым и вторым вховсех блоков свертки, шестые входы каж- дами второго элемента ИЛИ, выход кодого блока свертки являются информа- торого соединен с нулевым входом. ционными входами устройства. " триггера, нулевой выход триггера сое2, Устройство по п.l, о- т л и ч а- динен с первым входом элемента И, ю щ е е с я тем, что блок свертки 5 второй, третий и четвертый входы косодержит триггер, элемент И, первый и торого являются соответственно тревторой элемент ИЛИ, причем выход эле- тьим, четвертым и пятым входами блока, мента И соединен с первым входом пер- второй вход первого элемента ИЛИ яввого элемента ИЛИ и является первым ляется шестым входом блока, выход первыходом блока, единичный выход триг- р вого элемента ИЛИ соединен с единичным гера является вторым выходом блока,, входом триггера.

Составитель И,Сигалов

Редактор H.Каменская Техред О.андрейко Корректор H.Стец Заказ 2701/50 Тираж 779 Подписное

ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5

Филиал ППП Патент ., г.ужгород, ул.Проектная,4