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

:: --...,. ... ИЭЬбретейие.ОТНОСИТСЯ к области вычислительнойf аналого-цифровой и цифроаналоговой техники и может быть использовано дЛя приведения р-кодов к минимальной форме., / Под р-кодалш Фибоначчи понимаетс представление любого натурального чи ла N в виде суммы «-1 ;i где р - заданное натуральное число, ,определшощее номер р-кода Фибоначчи п -разность р-кода Фибоначчи; aj- двоичная цифра (О или 1) в t -рм разряде р-кода Фибоначчи; фр(С) - вес J-ro разряда р-кода Фибоначчи (р-число Фибоначчи), задаваемый следующим рекуррентным соотношением:ГОпри ц)р1е).| i при . ц)р (6-1)+(|jp(e-p-i) приело. Под лшнимальной формой р-кода Фибоначчи понимается такой р-код Фибоначчи, в котором после каждого единичного разряда следует не менее ..-/. ;::-- ./г . ;. , , г, р нулевых разрядов. При выполнении преобразований информации в цифровой .вычислит ьной машине (ЦВМ) аналогоцифровых (ЙЦП) и цйфроаналоговых (ЦйП) преобразователях над мнимальньоли формами р-кодов Фибоначчи все информационные операции приобретают свойство естественного самоконтроля, что ведёт кпЬвьйёйию информационной надежности ЦВМ, ДЩТ и . HoBoiJ операцией над кодами в ЦВМ, йЦП и ЦЙП, работающих в р-кодах Фибоначчи является операцйя приведения р-кодов Фибоначчи к минимальной форме. , , /: ;,,.. v.,.;, , ,, Устройства Для приведения р-кодов Фибоначчи к минимальной форме неизвестны. Целыо изобретения является создание устройства для приведения р-кодов Фибоначчи к минимальной форме. Это достигается тем, что устройство содержит п однотипных блоков свертки, причем первый вход С-го блока свертки соединен с первым входом (,-1) и вторым входом (-р-1) блоков свертки, второй выход t-ro блока свертйи является Е-ым информационны выходом устройства и соединен с третьим входом (Р+1) и четвертым вхоом (t+p+1) блоков свертки, управлящий вход устройства соединен с пяыми входами всех блоков свертки, естые входы каждого блока свертки являются информационными входами стройства .

Кроме того блок свертки содержит 5 риггер, элемент И, первый и второй элемент ИЛИр причем, выход элемента И зоединен с первым входом первого элемента ИЛИ и является первым выходом блока, единичный выход триггера явля-10 ется вторым выходом блока, первый и второй ВХОДЫ блока соединены соответственно с первым и вторым входами второго элемента ИЛИ, выход которого соединён с нулевым входом тригге- 15 ра, нулевой выход триггера соединен с первым входом элемента И, второй, третий и четвертый входы которого являются соответственно третьим, четвёртьам и пятым входами блока, второй 20 вход первого элемента ИЛИ является шестымвходом блока, выход первого элемента ИЛИ соединен с единичным входом триггера. ,- . - . :. .

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

Устройство содержит п однотипных блоков 1 свертки, где и означает разрядность Фибоначчи. Первый jO выход 2 .f-ro блока 1 соединен с пер вым входом 3 (J-1) и вторым входом 4 . (-1-1) блока 1, Второй выход 5 .f-гб блока 1 (S-3) язвляется ,t-bwi информ - i Цйонным выходом устройства и соединен igg с третьим входом 6 (t+l) и четвертым входом 7 (:jKfl+l) блоков 1, Пятые входы 8 каждого блока 1 объеданёны и яйляются управляювдм входом 9 устрой- ства. Шестые входа 10 каждого блока 1 ., являются информационными входами устройства. -..:.. ,; ; .-.-.. :

Блок 1 содержит триггер 11, эле- . Meffr 12 И, первый элемент 13 ИЛИ и : второй элемент 14 ИЛИ. ВыхОД элемен- . та 12 И соединен с первым входом эле- мента 13 ИЛИ и явлЯеТся первьвл выходом 2 блока 1. Единичный вьйсод трнг . гера 11 является вторшл выходом 5 блсжа 1 а Первый вхОд 3 и второй иход . 4 блока 1 соединены соответственно 50 с первым и вторым входами элемента 14 ИЛИ, выход которого соединен с нулев{лм входом триггера 11, Нулевой выход триггера 11 соединен с первым входом эт емента 12 И, второй, третий и чет- 55 вертый входы которого являются соответственно входом 7, входом б и входом 8 устройства. Второй вход элемента 1.3 ИЛ1 является входом 10 блока 1, а выход элемента 13 ИЛИ соеда1нен с gg единичным входом триггера 11.

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

Устройство содержит п блоков 1 свертки (). Здесь каждый блок 1 имеет также четвертый нулевой информационный выход 15, седьмой вход 16, пятый выход 17, (2-1) восьмых входов 18| - I8j. , девятый вход 19,(2+1) десятых входов 20 - , (2+1) одинадцатых входов 21 - 2154-1 , шестой выход 22. Девятые выходы 19 каждого блока 1 объединены и являются вторым управляющим входом 23 устройства. Пятый выход 17 Z-ro блока 1 соединен со входом 21j (6-2-j+l) блока 1. Шестой выход 22 Е-го блока соединен со входом 18 (P-i) блока 1 Четвертый выход 15,блока 1 соединен с седьмым входом 16 (.-1) блока 1 и со входом 203 (.E+2+S-1) блока 1, причем , 2,...,2+1, 1 1, 2,..., 2+1. Блок 1 в этом случае содержит также второй элемент 24 И и элемент 25 НЕ, вход которого соединен с выходом элемента 12.И, а выход является выходом 22 блока 1 свертки. Нулевой выход триггера 11 является четвертым входом 15 блока 1; Лр-1) вхОдОв элемента 12 И, начиная с пятого, являются восьмыми входами 18j -lS-j+i блока 1. Первый вход второго элемента 24 И соединен с единичным выходом триггера 11. Второй и третий входы элемента 24 И являются входом 19 и входом 16 соответственно блока 1, а оставшиеся (2+1) входов второго элемента 24 И являются десятыми входами , блока 1. Выход второго элемента 24 И соединен с третьим входом второго элемента 14 ийи и является пятым выходом. 17 блока 1.

Устройство для приведения р-кодов Фибоначчи к минимальной форме работает следующим обраэом. .

На фиг.1 представлена схема устройства для и . Двоичная информация .поступает на входы 10 устройства и через элементы 13 ИЛИ записывается в триггеры 11 блоков 1 свертки, находящиеся, до прихода информации на входы 10, в нулевом состоянии. При подаче единичного сигнала на управляющий вхОд 9 устройства, этот сигнал поступает на Один из входов элемента 12 И всех блоков 1. Элемент 12 И, будучи связанным с триггерами 11 блоков 1 -го (2-1) и (Е-1-1) так,как описано выше анализирует состояние триггеров 11 этих блоков. На всех входах элемента 12 И будет присутствовать единичный сигнал, т.е. выполнится условие свертки, если триггер 11 -го блока 1 находится в нулевом состоянии, а триггера 11 (6-г1) и (-1-1) блоков 1 находятся в единичном состоянии и на управляющий вход 9 поступает единичный сигнал. В этом случае на выходе эрлемента 12 И Р-го. блока 1 вырабатывается единичный сигнал, который поступает через элемент 13 ИЛИ йа триг гер 11 этой ячейки и устанавливает его в единичное состояние. Одновремейно этот же сигнал с выхода 2 f-ro блока 1 свертки подается, на вход 3 (2-1) и вход 4 (е-1-1) блоков 1 и через элементы 14 ИЛИ записывает в триггеры 11 этих блоков нулевые сигналы. Например в устройство записано число 5, представленное в 1-коде Фибоначчи, отличном от нормального Вес разряда -: 53 2 11 1-код Фибоначчи 01011 Условие Свертки выполняется при подаче единичного сигнала.на управляющий вход 9 устройства для блока 1 с номером . Элемент 12 И этого блока вырабатывает единичный сигнал, который записывает в триггер 11 блока 1 с номером единичный сигнал, а в триггеры 11 блоков 1 с номерами -2 и - нулевые сигналы. В резул тате число О 1 01 1 принимает вид Q 1 I 00, вследствие чего выпрлняет ся условие свертки для блока 1 с номером . После проведения вторсэй свертки число 01011 принимает вид 10000, что соответствует минимальной форме числа 5, в 1-коде Фибоначчи. Длительность управляющего сигнала, подаваемого на вход 9 устройства, должна быть заведомо больше времени, йеобходимого для проведения всех воз можных сверток. По окончании управля ющего сигнала свертки информация счи тывается с информационных выходов 5 устройства параллельно. Операция свертки для чисел в 2-коде. Фибоначчи осуществляется вышеописанным способом в устройстве, изображенном на фиг.2.; На фиг.2 изображено устройство для приведения 2-кода Фибоначчи к мини- г мальной форме, реализующее также операцию развертки в тех случаях, когда проведение всех возможных сверток не обеспечивает получения минимальной формы 2-кода Фибоначчи. В этом случае устройство, изображенное на ф.иг,2, реа;лизует поочередно операции сверток и разверток. Элемент 24.И блока 1 ана лизирует состояние триггеров 11 (+1) Е и от (2-2) до (г-2-2) блоков 1. При наличии в триггерах 11 +1 и о (В-2) до (8-2-2) блоков 1 нулевых сиг налов, а в триггере 11 й-гс бдока 1 единичного сигнала, условие свертки, выполнено и при подаче на второй управляющий вход 23 единичного сигнала на выходе элемента 24 И вырабатывается сигнал совпадения. Этот сигнал переводит триггеры 11 В и от (-2) до (-2-2) блоков 1 в инверсное состояние. После проведения всех возможных разверток проводятся все возможные свертки. Во время проведения сверток элемент 25 И саждой ячейки вырабатывает сигнал запрета свертки, который устраняет неоднозначность приведения числа к минимальной форме. Например, в устройство записано число 3, представленное в 2-кодё. Фибоначчи , отличном от нормального. Вес разряда 3 1 1 2-код Фибоначчи 01100 При подаче единичногог управляющего сигнала на вход 9 устройства условие свертки не выполняется ни для одного блока 1, хотя код представлен в форме, отличной от минимальной. Подается единичный сигнал на вход 23. Условие; развертки.выполняется для блока 1 свертки с номером 3, Элемент 24 И этого блока вырабатывает единичный сигнал, который записывает в триггер 11 блока 1 с номером нулевой сигнал, а в триггеры с номерами от (Е-2) до (-2-2) - единичные сигналы. .В данном случае единичный сигнал запишется только в триггеры 11 блока 1 с номерами 0-1 и t-2, так как остальные отсутствуют, в результате проведения развёрткикод 01100 принимает вид 00111.- Дальнейшие развёртки невозможны. Подается опять единичный сигнал на вход 9 устройства. Условие свертки выполняется для блока 1 свертки с номером . Код OOIJJ принимает вид 01010. Теперь условие свертки выполняется для блоков 1 с номерами и 3. Но блок свертки вырабатывает сигнал запрета свертки, который подается на вход iSj блока 1 свертки с номером и свертка в него за|фещена. Код 01010 принимает вид 10000, что соответствует минимальной форме числа в 2-коде Фибоначчи. Использование р-кодов Фибоначчи в цифровой вычислительной технике позволяет создавать самоконтролирующиеся узлы вычислительных машин. Устройство для приведения р-кодов Фибоначчи к минимальной форме используется при проведении операции суммирования для приведения к минимальной промежуточной суммы. Устройстйо:можн6 использовать как многовходовой счетчик импульсов в ркЬдах Фибоначчи, при этом входная ин-. формация подается на р младших разрядов . Формула изобретения 1. Устройство для приведения р-коов Фибоначчи к минимальной форме, тличающеес я тем, что оно одержит п однотипных блоков свертки, ричем первый выход -го блока сверти соединен с первым входом (-) и . торым входом (Ef-p-1) блоков свертки, торой выход -го блока свёртки явяется -ым информационным выходом стройства и соединен с третьим вхоом (2+1) и четвертьим входом (f+p+1) блоков свертки, управляющий вход устройства соединен Ь пятыми входами всех ёлбкШ (5вёртки, шестые входы каж дого блока свертки являются информационными входами устройства . 2, Устройство по П.1, о т л и ч аю щ е е с я тем, что блок свертки содержит триггер, элемент И, первый и второй элемент ИЛИ, причем выход элемента И соединен с первым входом первого элемента ИЛИ и являет;ся первым выходом блока, единичный выход триггера является вторым выходом блока, . 6 08 первый и второй входы блока соединены соответственно с первым и вторым входами второго элемента ИЛИ, выход которого соединен с нулевым входомтриггера, нулевой выход триггера соединен с первым входом элемента И, второй, третий и четвертый входы которого являются соответственно третьим, четвертым и пятым взводами блока, второй вход первого элемента ИЛИ является шестым входом блока,выход первого элемента ИЛИ соединен с единичным входом триггера.

9 гз.

Фиг. г