Устройство для приведения р-кодовфибОНАччи K МиНиМАльНОй фОРМЕ Советский патент 1981 года по МПК G06F5/06 

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

Изобретение относится к вычислительной технике и может быть исполь зовано для получения максимальной формы р-кода Фибоначчи. Известно единственное устройство для приведения р-кодов Фибоналчи к минимальной форме,содержащее п-однотипных блоков свертки, по числу разрядов р-кода Фибоначчи. Первый выход 1-го блока свертки соединен с первым входом (t-l)-ro, и вторым входом (t-p-1)-го блоков свертки, а второй выход t-ro блока свертки является 0-м прямлм информационным выходом ус ройства и соединен с третьим входом (е+1)-го и четвертым входом (t+p+Dблоков свертки 1. Недотаток известного устройства невозможность получения максимальной формы данного р-кода Фибоначчи. Максимальная форма, как и минимальная форма, является единственной для любого натурального числа N, при этом она состоит из двух частей. Например максимальная форма некоторого натурального числа N имеет вид N 000000 . .ОО1.. . 01-1 . . .10-1...-И первая часть . - V- ---;;- .вторая часть Первая часть максимальной формы-, включает в себя все разряды с нулевыми значениями, во -второй части после .каждого разряда нулевым значениям следует не менее р нулей. Эти признаки позволяют реализовать достаточно эффективный контроль хранения, передачи и выполнения арифметических операций над максимальными формами р-кодов Фибоначчи. Цель предлагаемого изобретения - расширение функциональных возможностей, заключающихся в получении максимальной формы р-кода Фибоначчи. Поставленная цель достигается Тбм, что в устройство для приведения р-кодов Фибоначчи к минимальной форме, содержащее п блоков свертки, причем первый выход Е.-го блока свертки соединен с первым входом (C-l)-ro и вторым входом (t-p-l)-ro блоков свертки, второй выход каждого блока свертки соединен с третьим входом (fc+l)-ro блока свертки и четвертым входом (Е+р+1)-го блока свертки, пятые входы каждого блока свертки являются управляющими входами,-шестые входы каждого блока свертки являются . информационными входами, вторые входы блоков свертки образуют первую группу выходов устройства, введены п-разрядный регистр, дешифратор команд, и п однотипных блоков коммутации, причем прямые и инверсивные выходы празрядного регистра соединены соответ ственно с первым и вторым входом соответствующего блока коммутации,выход каждого блока коммутации соединен с шестым входом соответствующего блока свертки, первый, второй и третий выходы дешифратора команд соединены соответственно с третьим входом всех блоков коммутации, с четвертым входом Всех блоков коммутации, с пятым входом всех блоков свертки, третьи выходы блоков свертки образуют вторую группу выходов устройства, Функциональная схема устройства для р-1 и п-5 приведена на чертеже. Устройство содержит пять блоков 1,1-1,5 свертки, каждый из которых имеет установочные входы 2 и 3 свертки, по которым проходит сигнал свертки, информационные входы свертки 4 и 5, предназначенные для считывания информации с прямых информационных выходов блоков свертки 1.&-.Е-р-1,управляющий вход б сверт ки, на котором при появлении сигнала происходит приведение р-кода Фибонач чи к минимальной форме, информационный, вход 7, по которому заносится ис ходная информация в блок 1,1-1.5 свертки, пять блоков 8,1-8.5 коммутации предназначенных для комму тации сигналов, снимаемых с прямого или инверсного информационного выход соответствующего разряда регистра 9, который предназначен для хранения ис ходного р-кода Фибоначчи, Каждый бло 8.1-8,5 коммутации имеет управляющие входы 10 и 11, соединенные соответст венно с первыми выходами дешифратора 12 команд, третий выход которого соединен с управляющими входами 6 свертки всех блоков 1,1-1,5 свертки. Прямые информационные выходы каждого блока свертки образуют первую группу выходов устройства,инверсные информа ционные выходы каждого блока свертки образуют вторую группу выходов устройства. Устройство работает следующим образом. Предположим, что необходимо получить максимальную форму 1-кода Фибонач чи числа 5, представленного в минимальной форме 1-кода Фибоначчи еле луюи1им образом: Вес разряда 53 2 1 1 1-код Фибоначчи 1 Этот 1-код Фибоначчи параллельным образом заносится в регистр 9, Так как необходимо получить максимальную форму исходного 1-кода Фибоначчи, то дешифратор 12 команд вырабатывает управляющий сигнал, который поступает на управляющий вход 10 каждого блока коммутации 8,1-8,5. В результате этого на выходе каждого блока 8.1-8.5 коммутации появляется информация, снимаемая с инверсных информационных выходов соответствующих разрядов регистра 9,Исходная комбинация 10000 при-t мет вид 01111, Эта кодовая комбинация через информационные входы 7 поступает в соответствующие блоки 1.11.5 свертки,По приходу сигнала из дешифратора 12 команд на управляющие входы 6 каждого блока 1.1-1,5 свертки производится анализ возможности проведения сверток между разрядами 1-кода Фибоначчи. В данном случае условие свертки выполнено для блока 1,5свертки, поэтому на управляющем входе 4 блока 1.4 свертки и на управляющем входе 5 блока 1.3 свертки появляется единичный сигнал, который переводит блоки 1,3-1,4 свертки в нулевое состояние, и одновременно с этим блок 1.5 свертки переходит в единичное состояние. Получают кодовую комбинацию 10011. Теперь условие свертки выполнимо для блока 1.3 свертки. На управляющем входе 4 блока 12 свертки и управляющем входе 5 блока 1.1 свертки появляется единичный сигнал, который переводит эти блоки свертки в нулевое состояние, и одновременно с этим блок 1.3 свертки переходит в единичное состояние. Получают кодовую комбинацию 10100, что соответствует минимальной форме 1-кода Фибоначчи. На инверсных информационных выходах блоков 1,11,5 свертки при этом кодовая комбинация 01011, что и соответствует максимальной форме 1-кода Фибоначчи исходного числа 5 (кода 10000). Таким образом, для получения максимальной формы р-кода Фибоначчи инверсные значения разрядов исходного кода заносятся в блоки 1,1-1,5 свертки, затем происходит приведение полученного кода к минимальной форме, и конечный результат считывается с инверсных информационных выходов бло- . ков 1,1-1.5 свертки,Кроме того, за устройством сохраняется его основная функция - приведение р-кода Фибоначчи к минимальной форме. Предположим, что необходимо получить минимальную форму числа 4, представленно -о в 1-коде Фибоначчи следующим образом: Вес разряда 532 1 1 1-код ФибоначчиО О 1-11 Этот.1-код Фибоначчи параллельным образом заносится в регистр 9, Так как необходимо получить минимальную формулу ИС.ХОДНОГО 1-кода Фибоначчи, то дешифратор 12 команд вырабатывает управляющий сигнал, который поступает на управляющий вход 11 каждого блока 8.1-8.5 коммутации. В резуль те чего на выходе каждого блока 8. 8.5 коммутации появляется информац снимаемая с прялых информационных выходов соответствующих разрядов р гистра 9, которая заносйтся через информационные входы 7 в соответст вующие блоки 1.1-1.5 свертки. По п ходу управляющего сигнала из дешиф ратора 12 команд на управляющие вх ды 6 каждого блока 1.1-1.5 свертки происходит (описанным выше образом приведение исходного кода к гиинимальной фсфме. После окончания при ведения на прямых информационных в ходах блоков 1.1-1.5 свертки будет минимальная форма исходного 1-кода Фибоначчи (т.е. код 01010J. Таким образом/ для получения минимальной формы р-кода Фибоначчи прямые значения разрядов исходного кода заносятся в блоки 1.1-1.5 свертки , затем происходит приведение кода к минимальной форме и конечный результат считывается с прямых инфор мационных выходов блоков 1.1-1.5 свертки. Приведем пример получения макси мальной форь/ы числа б в 2-коде Фибоначчи. веса разрядов 1396432111 исходный 2-код Фибоначчи 001000000 2-код Фибоначчи, заносимый в блоки 1 свертки110111111 2-код Фибо-110111111 наччи, получаемлй в про- 111010111 цессе приведения к минимальной форме в блоках свертки111100011 111100101 111101000 Максимальная форма исходного 2-кода Фибоначчи 000010111 Прещлагаемое устройство позволяет получить как минимальную, так и максимальную форму исходного р-кода Фибоначчи, что является значительным расширением функциональных возможностей устройства для приведения р-кодов к минимальной форме . Формула изобретения Устройство для приведения р-кодоа Фибоначчи к минимальной форме, содержащее п-блоков свертки, причем первый выход Е-ГО блока свертки соединен с первым входом (t-l)-ro и вторым вхо дом (C-p-l)-ro блоков свертки, второй выход каждого блока свертки соединен с третьим входом (t+1)-го блока свертки и четвертым входом (Е + р + 1)-го блока свертки, пятые входы блоков свертки являются управляющими входами, шестые входы блоков свертки являются информационными входами, вторые выходы блоков свертки образуют первую группу выходов устройства, о т л ичающееся тем, что, с целью расширения функциональных возможностей за счет получения максимальной формы р-кЪдов Фибоначчи, в устройство введены п-разрядный регистр, дешифратор команд и п-однотипных блоков коммутации, причем прямые и инверсные выходы п-разрядного регистра соединены соответственно с первым и вторым входом соответствующего блока коммутации, выход каждого блока коммутации соединен с входом соответствующего блока свертки, первый, второй и третий выходы дешифратора команд соединены соответственно с третьими входами всех блоков коммутации, с четвертыми входами всех блоков ком1У1утации, с пятыми входами всех блоков свертки, третий выход блоков свертки образует вторую группу выходов устройства. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР о эаяв11е 238б002/18-24, сл. G 06 Н{ 5/06, 02.08.76 (прототип).