Устройство для контроля 3-кода фибоначчи

СО 03 СОВЕ ТО ИХСОЯАЛИСТИЧЕСНИХРЕСПУБЛИН 801478217 А 1 0 06 Р/0 ИСАНИЕ ИЗОБРЕТЕ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ический и н, В,А,Лужецкий,,8)свидетельство СССРС 06 Г 11/00) 1981,т- ев сис наччи ппение и второй 9 строййстна, дирова- декоди- оответы управляюпид 10 установй вход 11 бле входа 12 рямые выход ства, в хоуправлян 1 пи тел де о эовано дсистемах,. ока24 я, четыр вания, и в ующих т 16- -1,9 ходь в 1 нач первого 25-30 со- -1 7 периггеров 1 . версцые вь их тригеро выш вля брет иост ью и егист трол ве ие д труктурна ца на блокаотв етс тв чо представлен иг,1стро 31-36 разряд орого регист тветствующих,1-.4,9. ов,о регистра, выходь иная с младшего, в3, выходы 37-45 со ментов ИЛИ группы ства дтя и циоцальцая схе ц фиг,2 декод нация эл ггеры 1и 2,1-2стр 3,,9, эле6, ицфва, пер ержит трц тра, блок орой реги ИЛ 11 4 1 4цт ЗАПРГТ с тройст тво со о реги Уст 1,9 пе декоди группу мент ИЛВ состав первый 4 ования вхотретий 48, ес той 51 первый 53,К еа в т од я,ов тов элем И 5,четвертыи 49, пятыц седьмой 52 элемсц 1 элемоды ационные ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЬПИЯПРИ ГКНТ СССР(56) Авторское1) 817718, кл,(54) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ 3-КОДАФИБОНАЧЧИ(57) Изобретение относится к вычислтельной технпе и может быть использовано для контроля информациитемах, используюших 3-коды ФибоЦелью изобретения является повьдостоверности контроля, Устройство обретение. относится к вычислиой технике и может быть исполля контроля информации виспольэукнцих 3-коды Фибосодержит девять триггеров первого регистра, песть блоков декодирования, второй регистр, десять элементов ИЛ) элемент ЗАПРГТ, девять информационных входов устройства, дна управляющих входа устройства, нход установки, устройства, урравляющий вход блока декодиронания, четьре входа блока декодирования, девять прямых выходов соответствующих девяти триггеров,первого регистра, шесть выходов соотне ствующих шести триггеров первого р гистра, шесть разрядов, начиная с младшего второго регистра, девять выходов соответствующих девяти элементов ИЛИ группы, Блок декодирования с. содержит семь элементов И, четыреф элемента ИЛИ, элемент НЕ, 1 э.п.е 1"пм, (О 2 ил., 3 табл.второй 54, третий 55 и четвертый 56 элементы ИЛИ и элемент 11 Е 57,устройство работает следующим образом вВ Фибоцаччиевой р"системе счисления значение весов разрядов Ч(1) определяется иэ рекуррентного выра" жеция р +( ) 1 ОМр (Д)Мр (з.-1) +%(д-р) з.р+1,или 1, з.с,4, (2)20Чь ( з.-2) + Р,(з.-4) + Ч( -5),з 4,Г, (з)" Для кода минимальной формы (М-формы) 3-кода фибоцаччи существует код частично развернутой Формы (ЧР-Форма), разряды Т(з.) которого определяются с учетом выражения (2) следующими вы ражениями: М(4), 1 ф 30М(4) +М (5) з.=2,М(5) + М(6) з =3, (3)М(з) + М(з.+2) + М(з+3),з T 3,Т(з) = где М(з.) - з.-й ряэряд кода М-формы.Прц этом каждая единица кода 35 М-Формы в кодс Р-формы представляется последовательностью 1011, т,е. код Ч 1-Формы получается путем умножения кода М-формы ца порождающий полином Х+Х+1, 40В качестве примера в табл.1 принелены коды М-Формы и ЧР-Формы чисел 8 и 9.Два дополнительных младших разряда кода ЧР-Формы имеют нулевой вес, 45 а два старших разряда всегда равны нулю. Поэтому если не использовать два старших разряда, то разрядность кода ЧР"формы будет такая же, как и кода М-формы. Код 1-Формы любой раэ рядности имеет минимальное кодовое расстояние, равное трем, что позволяет испранлять одиночные ошибки.Иэ выражения (3) можно определить значения разрядов кода М-Формы при 55 декодировании ЧР-формыМ(3+1) = Т(з+3)Т(з+2) Т(31) Т(1),1 12 е.уп 3 (4) Так как для р=3 выражение принима,ет вид1, з 44)15ЧзРь(з.- )+ Ч (з.-4), з.: 4 Табл,2 декодирования приведена с уче;гом (4) ц цапцчця одиночных ошибок и коде ЧР-формы (звездочками от . мечены,неисправные разряды).Процедура декодирования заключается в анализе всех групп из четырех соседних разрядов кода ЧР-формы и преобразовании их в соответствующие разряды кода М-Формы согласцо таблице декодирования без учета ошибочных разрядов.При этом нсе последовательности (тетрады) в коде ЧР-формы 1011 дают единицу н соответстнующий разряд кода М-формы и затем обнуляются, т,е. происходит параллельное деление на порождающий полином Х +Х+1 . Если ошибки отсутствуют, то в регистре ко-, да ЧР-Формы устанавливаются нулевые эцачецця нсех разрядов, Ошибочные комбинации дают цуленой остаток, Если имеет место одиночная ошибка то она исправляется согласно таблице декодирования Кроме того, исправляются нсе одиночные ошибки, возникающие н группах раэряцов ЧР-Формы, начинающихся номерами з., з.+8, з.+16 з+Ь 8 (1 с = 1,2,), Корректирующая, функция Р,: для з.-й, тетрады (1 1- и) определяется выражением Е - Т 1 4(Тз+я Т 13 ) Т дТьх х (Т, + Т , )Таким образом, процедура исправления одиночных ошибок в коде ЧР-формы состоит из двух тактов: на первом такте декодируются группы разрядов, це содержащие ошибок, и анализируется остаток; на втором такте при наличии ошибок происходит их исправление согласно таблице декодирования,Триггеры 1,1-1,9 входного регистра предназначены для записи исходного кода с информационных нходов 8 устройства.Шесть блоков 2 декодирования предназначены для деления на порождающий полином Хз+Х+ (элементы И 48, 49 и ИЛИ 5) и выделения комбинаций, содержащих одиночную ошибку в группе, дающей единицу в соответствующий разряд кода М-формы согласно выраже. ния (5) .Управляющий вход 8 устройства устананлцвает нулевым сигналом режим контроля (открыт элемент И 52) и единичным сигналом режим коррекции оди" ночных ошибок (открыт элемент И 47),478717Регистр 3 минимальной Формы предназначен для, записи результатов деления ца порождающий попиггом Х. +Х+1Эи исправленных разрядон М-Формы, т,е.н цег о записывается выходной кодМ-формы.Элементы ИЛИ 4,1-4.9 группы образуют кодирующее устройство полученияЧР-формы и прелназцачеггы для устацонки в нуль единичными значениями разрядовв кода М-Формы соответствующихразрядов кода ЧР-Формы, находящихсян триггерах 1.1-1,9 входного регистра, и получения выходного кода ЧР г,формы.Элемент Ш 1 И 5 предназначен длявыделения ненулевого остатка после де 4 вления на порождающий полицом Х +Х+1в триггерах 1.1-1,9 входного регистра. Единичный сигнал на его выходепосле деления означает наличие ошиб"ки в контролируемом коде,Элемент ЗАПРЕТ 6 отключает сигналконтроля при коррекции одиночных ошибок. С входа 9 поступают тактовыеимпульсы записи в регистр 3 минимальной Формы. Установочный вход 10 уст"ройства необходим для установки триггеров 1.1-1,9 входного регистра и ре- З 0гистра 3 минимальной формы в нуленоесостояние,В исходном состоянии после подачина вход 10 начальной установки единичного сигнала триггеры 1,1-1.9 ирегистр 3 переходят н нулевое состояние. Сигнал на управляющем входе 8имеет также нулевое значение (открытэлемент И 52). Предположим в триггеры 1,1-1.9 подан код ,ЧР-формы числа 9 не содержащий ошибок 011011101,При этом на выходах блоков 2,1-2,6декодирования устанавливается кодМ-формы числа 9 (начиная с четвертого разряда) 010001, который при подаче тактового импульса с входа 9устройства заносится н регистр 3, Спомощью группы элементов ИЛИ 4,1-4,9происходит обратное преобразование,т.е. на ее выходах устанавливаетсякод ЧР-формы, соответствующий кодуМ-формы в регистре 3,0110)1101, Приэтом единичные сигналы ца выходам 45,41-43-39,38элементов ИЛИ 4,9,4,5-4,7-4,3, 4.2 группы сбрасываютв нулевое состояние соответствующиетриггеры 1,9, 1,5-1.7-.3 и 1,2 входного регистра, В результате этоговсе триггеры 1,1-1,9 принимают нулевое зца ение, ко горов передастся через элемент 1 ШИ 5 и элемент ЗЮПГЕТ 6 ца контрольный выход устройстга ц снцдетельстгует об отсчтствци ошибкин принятом коде.Если в исходном коде имеются цеиспранные разряды, оцц обнаруживаютсяпри нулевом остатке в триггерах 1,11,9.после делсния ца порождаюгггий полипом Х +Х+1 (т.е. обнуления триггерров.1 - 1.9 входного регистра, образующих тетрацы 1101). Ие обнаруживаются только те ошибки, которые приводят к переходу н разрешенную комбинацию, При этом кратность таких ошибок не меньше трех (например, кратнатрем при появлении цпи исчезновениитетрад 101), а всс одно- и двухкратные ошибки обнаруживаются.Ненулевой остаток н триггерах 1.11.9 устанавливает в единицу элементИЛИ 5, которая передается на выходоткрытого элемента ЗАПРЕТ 6 и сигнализирует о наличии ошибки в принятомкодеьУстройство в режиме коррекции одиночных ошибок работает следующим образом,После завершения режима контроляпри наличии единичного сигнала на выходе элемента ЗАПРЕТ 6 н наиболеевероятной одиночной ошибки н контролируемом коде на управляющий вход 8устройства подается единичный сигнал,При этом закрывается элемент ЗАПРЕТ 6В блоках 2 декодирования закрываетсяэлемент И 52 и открывается элементИ 47, пропускающий на выход элементаИЛИ 56 сигнал с комбинационной схемы, анализирующей тетрады в триггерах 1,1-1,9 с учетом одиночных ошибоксогласно выражению (5). При обнаруже"нии одной из ошибочных тетрад 01011001, 1111, 1100 на выходе соответствующего блока 2 декодирования устанавливается единичный сигнал. При подаче тактового сигнала записи с входа 9 устройства эти единичные сигналызаписываются в соответствующие раз"ряды регистра 3 минимальной формы, навыходе элемента ИЛИ 4,1-4.9 группыустанавливается выходной код ЧР-формы с исправленными одиночными ошибками.В табл.3 приведены значения выходов блоков 2,1-2,6 декодирования взависимости от значения остатка втриггерах 1,1 - 1,9, цопучггвшегося-.врезультате одиночной ошибки н коде 1 Р-формы числа 9 ( звездочкой отмечен ошибочный разряд) .Кроме того, могут исправляться двукратные ошибки, имеющие место в триггере 1,1 и любом из триггеров, группы 1.6-1.9.Таким образом, устройство позволяет исправлять все одиночные ошибки в тетрадах, отстоящих одна от другой на четыре разряда и обнаруживать все одиночные и двойные ошибки, а также большой процент ошибок высшей кратности. 15Формула изобретения1. Устройство для контроля 3-кода Фибоначчи, содержащее первый регистр 20 иэ и триггеров (и-разрядность кода), прямые выходы триггеров регистра являются соответствующими выходами устройства, прямой выход -го триггера (х 4 п) соединен с первым вхо дом (ь.-3)-го блока декодирования, управляющие входы блоков декодирования объединены и являются управляющимвходом устройства, группу элементов ИЛИ и элемент ИЛИ, о т л и ч а ю щ е- ЗО е с я тем, что, с целью повышения достоверности контроля, в него введены второй регистр разрядностью (п), дополнительный элемент ИЛИ в группу и элемент ЗАПРЕТ, входы элемента ИЛИ подключены к прямым выходам соответствующих триггеров первого регистра, а выход подключен к прямому входу элемента ЗАПРЕТинверсный вход которого подключен к управляющему входу 40 устройства выход элемента ЗАПРЕТ является контрольным выходом устройства, инверсный выход -го (=3 и) триггера первого регистра соединен с вторым входом (1-2)"го блока декодирования, прямой выход ъ-го ( 2п) триггера первого регистра соединен с третьим входом (д)-го блока декодирования, прямой выход д-го (1 1п"3) триггера первого регистра соединен с четвертым входом д-го блока декодирования, выходы блоков декодирования подключены к информационным входам соответствующих разрядов второго регистра, вход записи которого является вторым управляющим входом устройства, а установочный вход объединен с первыми входами эле- ментов ИЛИ группы и является установочным входом устройства, выход 1.-го разряда второго регистра соединен с вторым входом 1.-го, третьим входом (з.+1)-го и четвертым входом (д+3)-го элементов ИЛИ группы, выходом элементов ИЛИ группы соединены снулевыми входами соответствующих триггеров первого регистра, единичные входы которого являются соответствующими информационными входами устройства.2. Устройство по п,1, о т л ич а ю щ е е с я тем, что блок декодирования содержит элементы ИЛИ, эле" менты И и элемент НЕ, первые входыпервого элемента И и первого элемента ИЛИ объединены и являются первым входом блока декодирования, вторые входы первого элемента И и первого элемента ИЛИ объединены и являются вторым входом блока декодирования, первые входы второго элемента И и второго элемента ИЛИ объединены и являются. третьим входом блока декодирования, первый вход третьего элемен" та И объединен с входом элемента НЕ и является управляющим входом блока декодирования, вторые входы второго элемента И и второго элемента ИЛИ объединены и являются четвертым входом блока декодирования, выход первого элемента И соединен с первыми входами четвертого и пятого элементов И, выход второго элемента ИЛИ соединен с вторым входом пятого элемента И, выход первого элемента КПИ соединен с первым входом шестого элемента И, выход второго элемента И соединен с вторыми входами четвертого и шестого элементов И, выход четвертого элемента И и выход элемента НЕ соединены с соответствующими входами седьмого элемента И, выходы пятого и шестого элементов И соединены с соответствующими входами третьего элемента ИЛИ, выход которого соединен с вторым входом третьего элемента И, выходы третьего и седьмого элементов И соединены с соответствующими входами четвертого элемента ИЛИ, выход которого является выходом блока декодирования.0 Габлииа 11-фо рм а Номер рааряда 9 8 7 6 5 ч 31 1 1 О 9 8 7 6 5 Ь Э 2 1 Вес рааряда 7 5 4 3 2 1 1 1 1 7 5 4 3 2 1 1 1 1 0 О8 100001 000 00 1 О 3 3 01 01 1 9 100010000 00 101110110 Таблица 2 форма кода Кодовые слова М-формаМ(1+3 ЧР-Форма Т Т Т;Т;0 0 0 0 0 0 0 3 0 0 1 0 0 1 0 0 1 0 О. 0 Таблица Э Код остатка1,9 1,8 1,7 1,6 1,.ч 1,3 1,2 1,1 Выходы блоков декодирования2,2 2,1 2,6 2,5 2,4 2.3 0 0 О 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 О 0 0 0 1 0 0 0 1 0 0 1 1 1 1 . 10 1 0 0 0 0 1 0 1 0333 0 0 0 0 0 О, 0 0 0 0 0 0 О О. 1 ф 3 0 0 д" 1 О 1 0 0 1 1 0 1 10 0 0 0 0 0 0 0 0 0 т;т, тт 01 1 0 1 0 1 0 0 1 13 1 1 0 0 1 11418 17 Составитель О.Неплохерактор И,йулла Техред Л. Сердюкова ректор О. Кран нова ГКНТ СС ский комбинат "Патент", г. Уагор Гагарина,10 Проиэводственно"и ак НК 65/49 осуда Тираж ббвенного комитет113035, Москва Подписноео иэобретениям и открытия35, Раушская наб., д. 4/5