Преобразователь кода фибоначчи в двоичный код

 

Изобретение относится к вычислительной технике и технике передачи информации и может быть использовано при преобразовании кода Фибоначчи с иррациональным отрицательньм основаг нием в двоичный код с контролем в процессе преобразования. Целью изобретения является повьшение достоверности преобразования. Преобразователь содержит сдвиговый регистр 1, блок 2 постоянной памяти, накапливающий сум матор 3, элемент 4 ИЛИ, дешифратор 5 запрещенных комбинаций, счетчик 6, информационные, разрешающий, установочный и тактовый входы 7-10, информационные и контрольный выходы 11, 12, 2 ил., 2 табл.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51) 4 Н 03 М 13/12

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

@ ., --... 1С

ОПИСАНИЕ ИЗОБРЕТЕНИЯ3 13

И АВТОРСКОМУ СВИДЕТЕЛЬСТВУ !

Риг. 1 (21) 4095623/24-24 (22) 27.06.86 (46) 23.10.88. Бюл. У 39 (72) А.П.Стахов, И.А.Соляниченко, В.В.Замчевский, О.Н.Тарасова и Т.И.Звенигородская (53) 681.327(088.8) (56) Авторское свидетельство СССР

У. 662933, кл ; Н 03 M 13/12, 1979.

Авторское свидетельство СССР

У 798800, кл. G 06 Г 5/02, 1979. (54) ПРЕОБРАЗОВАТЕЛЬ КОДА ФИБОНАЧЧИ

В ДВОИЧИЫЙ КОД (57) Изобретение относится к вычисли; тельной технике и технике передачи

„„SU „„1432789 А 1 информации и может быть использовано при преобразовании кода Фибоначчи с иррациональным отрицательным основа". нием в двоичный код с контролем в процессе преобразования. Целью изобретения является повышение достоверности преобразования. Преобразователь содержит сдвиговый регистр 1, блок 2 постоянной памяти, накапливающий сумматор 3, элемент 4 ИЛИ, дешифратор 5 запрещенных комбинаций, счетчик 6, информационные, разрешаюшнй, установочный и тактовый входы 7-10 информационные и контрольный выходы 11, 12, 2 ил., 2 табл.

1432789

Таблица 1

Эквивалентное значе" ние

О О

О . О

О 1

О 1

30 О

1 0

q (1) 1 1

0 0

0 0

0 ge Me е

0 СР

О 1

I 0

1 О

РР-4

0 e- Ч e- w

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

5 с иррациональным отрицательным основанием в двоичный код с контролем в процессе преобразования.

Цель изобретения — повышение дос" товерности преобразования. 10

На фиг.l представлена блок-схема ! преобразователя; на фиг.2 - схема сдвигового регистра.

Преобразователь содержит сдвиговый регистр 1, блок 2 постоянной памяти, 15 накапливающий сумматор 3, элемент ИЛИ

4, дешифратор 5 запрещенных комбинаций, счетчик б, информационные, раз- решающий, установочнь и и тактовый входы 7-10., информационные и конт- 20 рольный выходы ll и 12, Сдниговый регистр l содержит регистры 13-16.

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

P""÷èñëà Фибоначчи с иррациональны- 25 ми отрицательными основаниями (ИОО) задаются следующим рекуррентным соотношением:

О, при 1(0

1, при 1 = 0

-1, при 1 = 1, (1) Це(1-р-1)- ч" (1-1), при

1 >1, р = 0,1,3,5... 35

При р = 1 веса P-чисел Фибоначчи порождают следующий ряд:

13 -8 5 -3 2 -1 1 0

При выполнении операции свертки для I-чисел Фибоначчи с ИОО происходит процесс замены двух единиц (1+p+1)-го и (1+1)-го разрядов на единицу B 1 M разрядеу R развертка 45 в обратном порядке.

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

Для р=! из (1) следует с, (1) - (р, (1-2) — cp,(1"! ), (2)

На основании (2) реализован алгоритм функционирования предлагаемого устройства, позволяющего преобразовывать одновременно по четыре разряда входного Х-кода Фибоначчи с ИОО.

Для I-кода Фибоначчи с ИОО иэ четырех раэрядон могут возникнуть комбинации, представленные в табл.!.

Че .

Из выражения (2) и табл. l следует, что двум соседним единицам в соотвествие ставится одно значение веса Х-кода Фибоначчи с ИОО. °

Для обеспечения необходимых параметров информационного потока в сис1432789

% Wn.. Ч

0 0 О О

1 1 1 1

1 О 0 Π— на любом интервале кодо1 1 1 0 вой посылки 25

О О . Х Х вЂ” в начале кодовой посылки

1 — в конце кодо- 30 вой посылки

Х Х 1

Преобразование кода осуществляется следующим образом.

По сигналу установки, поступающему на вход 9, происходит установка в ну- 35 левое состояние накапливающего сум матора 3, в счетчик 6 записывается число n/4, где n — разрядность входного I-кода Фиб оначч и с ИОО, и по входной шине 7 исходный п-разрядный 40

I-код Фибоначчи записывается в сдвиговый регистр 1. Причем на входы n/4" разрядного сдвигового регистра 13 по.даются 1,5,9,...,(n-3) разряды входного I-кода Фибоначчи, на входы п/4- 45 разрядного сдвигового регистра 14 подаются 2,6,10,...,(п-2) разряды входного I-кода Фибоначчи, на входы n/4разрядного сдвигового регистра 15 подаются 3,7,11,...,(n-l) разряды вход-50 ного I-кода Фибоначчи, на входы

n/4-разрядного сдвигового регистра 16 подаются (4,8,12,...,n) разряды входного I-кода Фибоначчи.

На выходах регистра 1 появляются соответственно значения и, (п-l), (п-2) и (n-3)-го разрядов входного кода, которые поступающие на входы темах передачи информации на кодовые посылки, представленные в равновесной ,форме, требуется наложение следующих ограничений: длина серий подряд сле" дующих одноименных символов не более трех нулей и не более трех единиц подряд; после комбинации 10 не может возникнуть комбинация 00; после комбинации ll не может возникнуть комби- lp нация 10; кодовая посылка не может начаться с комбинациями 00 и окончиться комбинацией 11.

Исходя из данных ограничений, возникают следующие запрещенные комбина" 15 ции (ХХ вЂ” разряды с любым значением (О или 1)) . блока 8 постоянной памяти, которые являются младшими разрядами кода ад, реса и поступают также на первую груп" . пу входов дешифратора 5 запрещенных комбинаций, на вторую группу входов которого поступает код содержимого счетчика 6, Этот же код поступает на вторую группу входов (старшие разряды) блока 2 постоянной памяти.

Дешифратор 5 анализирует четыре разряда входной кодовой посылки на запрещенные комбинации, приведенные ранее.

Если появляется хотя бы одна иэ запрещенных комбинаций, на выходе дешифратора 5 появляется сигнал, свидетельствующий о нарушении формы представления входной кодовой посылки, и этот сигнал поступает на контрольный выход 12 преобразователя, а также на вход элемента ИЛИ 4, по которому происходит обнуление накапливающего сумматора 3, запись числа п/4. в счетчик б и повторная запись и-разрядной посылки I-кода Фибоначчи в регистр 1 °

При правильной входной кодовой посылке в зависимости от установившегося кода на выходе блока 2 постоянной памяти появляется двоичный эквива.— лент веса четырех разрядов I-кода Фибоначчи с ИОО, который поступает на вход накапливающего сумматора 3.

Передним фронтом тактирующего импульса происходит запись сформированного двоичного эквивалента в накапливающий сумматор 3, а также уменьшается значение счетчика 6 на единицу, происходит сдвиг на четыре разряда содержимого регистра 1. Следующие четыре разряда входного кода и новое значение счетчика 6 поступают на вход дешифратора 5 для проверки на запре- щенные комбинации и на вход блока 2 постоянной памяти, где формируется новый двоичный эквивалент поступив- ° ших четырех разрядов входного I-кода

Фибоначчи с ИОО.

Передним фронтом следующего тактирующего импульса сформированный дво" ичный эквивалент на предыдущем такте

l добавляется в накапливающий сумматор 3.

Таким образом, в накапливающем сумматоре 3 происходит накопление двоичных эквивалентов разрядов Е-ко- ды Фибоначчи с ИОО.

3а n/4 тактов в двоичном накапли-: вающем сумматоре 3 произойдет накоп1432789!

,16 15 14 13 12 ll 10 9 8 7 6 5 4 3 2 1 !

l6I0 -377 233 -144 89 -55 34 -21 13 -8 5 -3 2 -1 1 0

Преобразование 16-разрядного входНого I-кода Фибоначчи осуществляп Втся. За — 4 + I ) ° тактов т е. в данном случае за пять тактов. Таблица 2

Адрес АЗУ

Такт преобразования

Результат преобразования

RGB< с „ ) Значение счетчика

0 0

0 1 ПЗУ;

0 0 0 О О 0 0 0 0

0 О 0 0 1 О 1 l 0

0 О О О 1 0 I l О

О 0 0 0 1 1 0 0 1

О 0- О 1 О 1 1 l 1

1 1 1 1 1 1 1 0 I

1 l 0 1

100

0 1

1 0 ПЗУ, l О 1 I

Ol 1

l 1

0 1 ПЗУ;

О 1 0 1

010 ление двоичных эквивалентов (- — !) п

4. групп (по четыре разряда в каждой группе) вхоДного I-кода .Фибоначчи, а также будет сформирован двоичный эквивалент последней группы разрядов входного I-кода Фибоначчи, запись которого в накапливающий сумматор 3 осуществится передним фронтом последнего тактового импульса, с приходом которого содержимое регистра l u счетчика 6 станет равным нулю. В этот

;момент дешифратор 5 не должен вырабо" тать сигнал ошибки, хотя и появятся .четыре нуля на п (n-1), (n-2), (n-3) выходах регистра l так как все информационные группы входного кода уже ! проанализированы и сформированы их ,двоичные эквиваленты»

Таким образом, результат преобра-!, эования будет записан и храниться в накапливающем сумматоре 3 до оконча,ния тактирующего импульса. !

По окончании тактирующего импуль,са на выходе счетчика 6 возникает г сигнал переполнения, по которому происходит обнуление накапливающего сумматора 3, в счетчик 6 записы5 вается число и/4, в регистр 1 записывается новое значение I-кода Фибоначчи с ИОО. Начинается преобразование очередной входной кодовой посылки.

10 Разрешающий сигнал на входе 8 устанавливается в единичное состояние, если мы работаем с равновесной формой кода ИОО, и устанавливается в нулевое состояние, если работаем с лю15 бой другой формой I-кода Фиббоначи с

ИОО, где не требуется проверка на граничные условия (шесть запрещенных комбинаций) и на выходе дешифратора

5 всегда будет нс ль.

20 Пример. Преобразование 16разрядного Х-кода Фибоначчи с НС0, представленного в равновесной форме, в двоичный код.

25 16-разрядный ?-код- Фибоначчи с ИОО имеет следующие веса:

Пусть входной 16-разрядный код Фибоначчи имеет следующий вид: 1 1.

350 1 1 0 l О 1 О 1 0 1

О 0 °

Последовательность преобразования приведена в табл.2.

1432789

Продолжение табл.2

Адрес ПЗУ .

Результат преобразования

Такт преобразования

Значение ЙС(ф, е... в f8- Д счетчика

010000010110100Е, 1 1 1 1 1 1 1 1 1 1 1 П3 У;

001

0 0 0 0 О 0 0 1 0 1 1 0 0 1 l

0 0 0 0 -0 0 0 0 0 0 0 ПЗУ1

000

В результате преобразования полу- входного I-кода Фибоначчи с ИОО: чают следующий двоичный эквивалент

О 0 1 0 1 1 0 О 1 l (+ 179) 1

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

Преобразователь кода Фибоначчи в двоичный код, содержащий регистр, информационные входы которого являются информационными входами преобразователя, выходы соединены с одноименными первыми входами блока постоянной памяти, выходы которого соединены с ин- формационными входами накапливающего сумматора, выходы которого являются информационными выходами преобразователя, счетчик, тактовый вход которого является тактовым входом преобразователя, информационные выходы счетчика соединены с соответствующими вторыми входами блока постоянной памяти, о тл и ч а ю шийся тем, что, с целью повышения достоверности преобразования, в преобразователь введены дешифратор запрещенных комбинаций и элемент ИЛИ, а регистр выполнен сдвиговым, первые входы дешифратора запре- щенных комбинаций подключены к соот3g ветствующим выходам регистра, вторые входы дешифратора запрещенных комбинаций подключены к соответствующим выходам счетчика, стробирующий вход дешифратора запрещенных комбинаций является разрешающим входом преобра35 эователя, а выход соединен с первым входом элемента ИЛИ и является контрольным выходом преобразователя, выход переполнения счетчика соединен с

40 вторым входом элемента ИЛИ, третий вход которого является установочным входом преобразователя, а выход сое- динен с установочными входами регистра, счетчика и накапливающего сумма45 тора тактовые входы накапливающего сумматора и сдвигового регистра обьединены и подключены к тактовомувходу преобразователя. з!

432789

7

7

Составитель Б.Неплохов

Редактор Л.Зайцева Техред И.Верес Корректор Н.Король

Заказ 5464/55

Тираж 929 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4