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

 

Союз Советскик

Социалистических

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт, сеид-ву (22) Заявлено 060278 (2! ) 2578461/18-24 (51)М. Кл. с присоединением заявки №вЂ” (23) Приоритет—

G 06 F 5/06

Государственный комитет

СССP по делам изобретений и открытий

Опубликовано 3006 8 1 БкзллеTeH ¹ 24 (53)

ЙК 681. 3 (088. 8

Дата опубликования описания 3рр681 (72) Авторы изобретения

А. П.Стахов и Н.А.Соляниченко (71) Заявитель

Винницкий политехнический институт (54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ Р вЂ” КОДОВ

ФИБОНАЧЧИ K МИНИМАЛЬНОЙ ФОРМЕ.вторая часть

" 30

Изобретение относится к вычислительной технике и может быть использовано для получения максимальной формы р-кода Фибоначчи, Известно единственное устройство для приведения р-кодов Фибоначчи к минимал ьной форме, содержащее и-однотипных блоков свертки, по числу разрядов р- кода Фи бон аччи . Первый выход с-rо блока свертки соединен с первым входом (P-1) -ro, и вторым входом (т,-р-1) -го блоков свертки, а второй выход E.-го блока свертки является

E-м прямым информационным выходом устройства и соединен с третьим входом 15 (0+1)-го и четвертым входом (Е+р+1)-ro блоков свертки (1) .

Недотаток известного устройства— невозможность получения максимальной форьы данного р-кода Фибоначчи. Мак- 29 симальная форма, как и минимальная форма, является единственной для любого натурального числа N, при этом она состоит из двух частей. Например, максимальная форма некоторого нату- 25 рального числа N имеет вид

N=O 00000 ..001...011.. ° 10 1...11

0 пепаая часть

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

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

Поставленная цель достйгается тем, что в устройство для приведения р-кодов Фибоначчи к минимальной форме, содержащее и блоков свертки, причем первый выход E.-го блока свертки соединен с первым входом (Е-1) — го и Вторым входом (|,-р-1)-ro блоков свертки, второй выход каждого блока свертки соединен с третьим входом (6+1) -ro блока свертки и четвертым входом (е+р+1) -го блока свертки, пятые входы каждого блока свертки являются управляющими входами,- шестые входы каждого блока свертки являются информационными входами, вторые входы блоков свертки образуют первую груп842 78б пу выходов устройства, введены и-разрядный регистр, дешифратор команд, и и однотипных блоков коммутации, при— чем прямые и инверсивные выходы празрядного регистра соединены соответственно с первым и вторым входом ro- 5 ответствующего блока коммутации, выход каждого блока коммутации соединен с шестым входом соответствующего блока свертки, перный, второй и третий вы— ходы дешифратора команд соединены соответственно с третьим входом всех блоков коммутации, с четвертым входом всех блоков коммутации, с пятым входом всех блоков свертки, третьи выхо— ды блоков свертки образуют вторую группу выходов устройства.

Функциональная схема устройства для р-1 и и-5 приведена на чертеже.

Устройство содержит пять блоков

1, 1-1,5 свертки, каждый из которых имеет установочные входы 2 и 3 20 свертки, по которым проходит сигнал свертки, информационные входы свертки 4 и 5, предназначенные для считывани я информации с прямых информационных выходов блоков свертки 25

1.В-1. E-ð-l,управляющий вход б сверт— ки, на котором при появлении сигнала происходит приведение р-кода Фибоначчи к ми нимал ь ной форме, и н формаци он— ный вход 7, по которому заносится ис- щ ходная информация в каждый блок

1. 1-1.5 свертки, пять блоков 8, 1 — 8. 5 коммутации предназначенных для коммутации сигналов, снимаемых с прямого или инверсного информационного выхода 3 соответствующего разряда регистра 9, который предназначен для хранения исходного р-кода Фибоначчи. Каждый блок

8. 1 — 8.5 коммутации имеет управляющие входы 10 и 11, соединенные соответственно с первыми выходами дешифрато- 40 ра 12 команд, третий выход которого соединен с управляющими входами б свертки всех блоков 1. 1-1.5 свертки.

Прямые информационные выходы каждого блока свертки обр аз уют первую группу выходов устройства, инверсные информационные выходы каждого блока свертки образуют вторую группу выходов уст— ройства °

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

Предположим, что необходимо получить максимальную форму 1-кода Фибоначчи числа 5, представленного н ми— нимальной форме 1-кода Фибоначчи слелующим образом:

Вес разряда 5 3 2 1 1

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

Этот 1-код Фибоначчи параллельным образом заносится в регистр 9. Так как необходимо получить максимальную форму исходного 1-кода Фибоначчи, то 65 дешифратор 12 команд вырабатывает у пр авл яющий си гн ал, который поступает на управляющий вход 10 каждого блока коммутации 8. 1-8.5. В результате этого на выходе каждого блока 8. 1-8.5 коммутации появляется информация, снимаемая с иннерсных информационных выходов соответствующих разрядон регистра 9 ..Исходная комбинация 10000 при" мет вид 01111. Эта кодовая комбинация через информационные входы 7 поступает в соответствующие блоки 1. 11. 5 свертки. По приходу сигнала из дешифратора 12 команд на управляющие входы б каждого блока 1. 1-1.5 свертки произ водится анализ возможности проведения сверток между раз рядами

1-кода Фибоначчи. В данном случае условие свертки выполнено для блока

1.5 свертки, поэтому на управляющем входе 4 блока 1.4 câåðòêè и на управляющем нходе 5 блока 1. 3 свертки поя вл яется единичный сигнал, который переводит блоки 1. 3 — 1. 4 свертки в нулевое состояние, и одновременно с этим блок 1.5 свертки переходит в единичное состояние . Получают кодовую комбинацию 10011. Теперь условие свертки выполнимо для блока 1. 3 свертки. На управляющем входе 4 блока 12 свертки и управляющем rrxn e

5 блока 1. 1 свертки появляется еди— ничный си гнал, который переводит эти блоки свертки в нулевое состояние, и одновременно с этим блок 1. 3 свертки переходит н единичное состо яни е. Получают кодовую комбин ацию

10100, что соответствует минимальной форме 1 — кода Фибоначчи. На инверсных информационных выходах блоков 1. 11. 5 свертки при этом кодовая комбинация 01011, что и соответствует максимальной форме 1-кода Фибоначчи ис— ходного числа 5 (кода 10000) . Таким образом, для получения максимальной формы р-кода Фибоначчи инверсные з начения разрядов исходного кода заносятся в блоки 1. 1-1.5 свертки, затем происходит приведение полученного кода к минимальной форме, и конечный результат считывается с инверсных информационных выходов блоков 1.1-1.5 свертки. Кроме того, эа устройством сохраняется его основная функция — приведение р-кода Фибоначчи к минимальной форме. Предположим, что необходимо получить минимальную форму числа 4, представленно..о в

1-коде Фибоначчи следующим образом:

Вес разряда 5 3 2 1 1

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

Э тот 1- код Фибон аччи пар аллел ьным образом заносится в регистр 9. Так как необходимо получить минимальную формулу исходного 1-кода Фибоначчи, то дешифратор 12 команд вырабатывает управляющий сигнал, который поступает на управляющий вход 11 каждого

842786

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

20 веса РазРЯдов 13 9 б 4 3 2 1 1 1 1

30 исходный 2-код

Фибоначчи

О 0 1 О 0 О О О О

2-код Фибоначчи, эаноси— мый в блоки

1 свертки

1 1 О 1 1 1 1 1 1

1 1 1

1 1 1

1 1 1

О 1 О

ООО1

11110 а1О 1

1 1 1 1 О 1 О О О

Источники информации, принятые во внимание при экспертизе

$0

1. Авторское свидетельство СССР по эаявке 9 ?386002/18-24, кл. G 06 Ц 5/06, 02. 08. 76 (прототип), Максимал ьн а я форма исходного 2-кода

Фибоначчи

О О О О 1 О 1 1 1 блока 8.1-8.5 коммутации. В результате чего на выходе каждого блока 8.18. 5 коммутации появляется информация снимаемая с пряьжх информационных выходов соответствующих разрядов регистра 9, которая заносится через информационные входы 7 в соответствующие блоки 1.1-1.5 свертки. По приходу управляющего сигнала из дешифратора 12 команд на управляющие входы б каждого блока 1. 1-1.5 свертки происходит (описанным выше образом) приведение исходного кода к минимальной форме. После окончания приведения на прямых информационных выходах блоков 1.1 — 1 5 свертки будет минимальная форма исходного 1-кода

Фибоначчи (т.е. код 01010) . Таким образом, для получения минимальной форьи р-кода Фибоначчи прямые значения разрядов исходного кода заносятся в блоки 1.1-1.5 свертки затем происходит приведение кода к минимальной форме и конечный результат считывается с прямых информационных выходов блоков 1.1-1.5 свертки.

Приведем пример получения максимальной формы числа б в 2-коде

Фибоначчи.

2-код Фибо — 1 1 О наччи, получаемый в про- 1 1 1 цессе приведения к минимальной форме в блоках свертки 1 1 1

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

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

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

Фи бои аччи к минимальной форме, содержащее п-блоков свертки, причем первый выход P-го блока свертки соединен с первым входом (f-1) -го и вторым входом (p-p-1) -ro блоков свертки, второй выход каждого блока свертки соединен с третьим входом (5+1) -го блока свертки и четвертым входом (Е + p + 1) -го блока свертки, пятые входы блоков свертки являются управляющими входами, шестые входы блоков свертки являются информационными входами, вторые выходы блоков свертки образуют первую группу выходов устройства, о т л и,ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей з а счет получения максимальной формы р-кодов Фибоначчи, в устройство введены и-разрядный регистр, дешифратор команд и п-однотипных блоков коммутации, причем прямые и инверсные выходы п-разрядного регистра соединены соответственно с первым и вторым входом соответствующего блока коммутации, выход каждого блока коммутации соединен с входом соответствующего блока свертки, первый, второй и третий выходы дешифратора команд соединены соответственно с третьими входами всех блоков коммутации, с четвертыми входами всех блоков коммутации, с пятыми входами всех блоков свертки, третий выход блоков свертки образует вторую группу выходов устройства.

842 786

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

Редактор И. Ковальчук Техред H.Майорош Корректор С.Щомак

Заказ 5101/59 Тираж 745 Подписное

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

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

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