Преобразователь кода фибоначчи в двоичный код
Изобретение относится к вычислительной технике и технике передачи информации и может быть использовано при преобразовании кода Фибоначчи с иррациональным отрицательньм основаг нием в двоичный код с контролем в процессе преобразования. Целью изобретения является повьшение достоверности преобразования. Преобразователь содержит сдвиговый регистр 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