Устройство для контроля 3-кода фибоначчи
Изобретение относится к вычислительной технике и может быть использовано для контроля информации в системах, использующих 3 - коды Фибоначчи. Целью изобретения является повышение достоверности контроля. Устройство содержит девять триггеров первого регистра, шесть блоков декодирования, второй регистр, десять элементов ИЛИ, элемент ЗАПРЕТ, девять информационных входов устройства, два управляющих входа устройства, вход установки устройства, управляющий вход блока декодирования, четыре входа блока декодирования, девять прямых выходов соответствующих триггеров первого регистра, шесть инверсных выходов соответствующих шести триггеров первого регистра, шесть выходов разрядов, начиная с младшего второго регистра, девять выходов соответствующих девяти элементов ИЛИ группы. Блок декодирования содержит семь элементов И, четыре элемента ИЛИ, элемент НЕ. 1 з.п. ф-лы, 2 ил.
СО?03 СОВЕ ТС? ?ИХ
СОЯ.!АЛИСТИЧЕСНИХ
РЕСПУБЛИН I) q G 06 F I I /00
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К ABT0PCHOMV СВИДЕТЕЛЬСТВУ
ГОСУДАРСТБЕНН?э)Й НОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯ)1
ПРИ ГКНТ СССР (21) 4196046/24-24 (22) 12,02,87 (46) О7,05.89,Бюл, М 17 (71) Винницкий .политехнический институт (72) А,П.Стахов, В,А,Лужецкий, П.В.Козлюк и В.Г,Баховский (53) 681 .3 (088.8) (56) Авторское свидетельство СССР
?? 817718, кл, С 06 F I 1/00, 198-1, l (54) УСТРОЙСТВО ДЛЯ КО?1ТРОЛЯ 3-КОДА
ФИБОНАЧЧИ (57) Изобретение относится к вычислительной техн)псе и может быть использовано для контроля информации в системах, исполь зуюших 3-коды Фибоначчи, Целью изобретения является повьппение достоверности контроля, Устройство
Изобретение. относится к вычислительной технике и может быть использовано для контроля информации в системах, используюгпих 3-коды Фибоначчи.
Целью изобретения является повышение достоверности контроля.
На фиг.l представлена структурная схема устройства дг я n = 9; »а фиг,2 — функцио»аль»ая схема блока декодирования, Устройство содержит триггеры 1,1—
1.9 первого рег истра, блоки 2.1-2.6 декодирования, второй регистр 3, группу элементов ИЛ11 4,1 4.9, эле мент ИЛИ 5, элеме»т 3AIIPFT 6, и»формационные входы 7 устройства, первый 8
„„80„„1478217 А 1 содержит девять триггеров первого регистра, п)есть блоков декодирования, второй регистр, десять элементов ИЛИ, элемент ЗАПРГТ, девять информационных входов устройства, дна управляющих входа устройства, нход установки. устройства, урравляющий вход блока декодиронания, четыре входа блока декодирования, девять прямых выходов соответствующих девяти триггеров,первого регистра, шесть вьгходов соотнетствующих шести триггеров первого регистра, шесть разрядов, начиная с младшеro второго регистра, девять выходов соответствующих девяти элементов ИЛИ группы, Блок декодирования содержит семь элементов И, четыре ф элемента ИЛИ, элемент НЕ. I s.ï.ô-пм, (О
2 ил., 3 табл.
2 и второй 9 управляющие входы устройства, вход 10 установки устройства, управляющий вход 11 блока декодированигг, четыре входа 1 2-1 5 блока декодирования, прямые выходы 16-24 соответствующих триггеров 1.1-1.9 первого регистра и»верс»ые выходы 25-30 со-. ответствующих тригr еров 1.3-1.7 пер- вого регистра, выходы 31-36 разрядов, начиная с младшего, второго регистра 3, выходы 37-45 соответствующих элементов ИЛИ группы. 4,1-.4,9, В состав блока декодирования входят первый 46, второй 47, третий 48, четвертый 49, пятый 50, шестой 51 и седьмой 52 элементы И, первый 53, 14787!7 второй 54, третий 55 и четвертый 56 элементы ИЛИ и элемент lll . 57. устройство работает следующим обра soM °
В Фибоначчиевой р-системе счисления значение весов разрядов g<(i) определяется иэ рекуррентного выражения
1, i a p+ I; (1) fp (i) . Pp(i-1) &p(i-I-p),i p+I. или
1, 1.с,4, (2)
}1 „(i -2) + }И, (1-4) + М(4), 30 М(4) +М (5) 1= 2 ° М(5) + М(6) 1 =3, (3) N(i) + N(i+2) + N(i+3),i r 3, 1 (i) = где N(i.) — i- é ряэряд кода М-формы. При этом каждая единица кода 35 М-формы в кодс }IP-формы представляется последовательностью 1011, т.е. код ЧР-формы получается путем умножения кода М-формы на порождакщий noX +X+ I . 40 В качестве примера в табл.1 приведены коды М-формы и ЧР-формы чисел 8 и 9. Два дополнительных младших разряда кода ЧР-формы имеют нулевой вес, 45 а два còàðøèõ разряда всегда равны нулю. Поэтому если не использовать два старших разряда, то разрядность кода ЧР-формы будет такая же, как и кода М-формы. Код 11 ôîðìû любой раэ- 50 рядности имеет минимальное кодовое расстояние, равное трем, что позволяет исправлять одиночные ошибки. Иэ вь}ряжения (3) можно определить значения разрядов кода М-формы при 55 декодировании ЧР-формы N(3+1) = T(i+3) T(i+2) T(i+I ) Т() ), 1, ?,,п-3. (4) Так как для р=3 выражение принима.ет вид I, «С4, I5 Ч 3 (i) У (1-I)+ Ч (i-4), i 4 Табл.2 декодирования приведена с уче;гом (4) и наличия одиночных оши бок в коде ЧР-Формы (звездочками от мечены, неисправные разряды). Процедура декодирования заключается в анализе всех групп из четырех соседних разрядов кода ЧР-формы и преобразовании их в соответствующие разряды кода М-формы согласно таблице декодирования без учета ошибочных разрядов. При этом все последовательности (тетрады) в коде ЧР-формы 1011 дают единицу в соответствующий разряд кода М-формы и затем обнуляются, т,е. происходит параллельное деление на порождающий полином Х +Х+1 . Если ошибки отсутствуют, то в регистре ко-, да ЧР-формы устанавливаются нулевые значения всех разрядов . Ошибочные комбинации дают нулевой остаток. Если имеет место одиночная ошибка„ то она исправляется согласно таблице декодирования. Кроме того, исправляются все одиночные ошибки, возникающие в группах раэряцов ЧР-формы, начинающихся номерами i i+8 i+16,..., i+>.8 (k = 1,2,...) . .Корректирующая; функция F,: для i-й. тетрады (11п-3) определяется выражением Fj TjT 1 t4 (Tj g Т j+3 ) Т j g Ть}х х (Т, + Т ) ° Таким образом, процедура исправления одиночных ошибок в коде ЧР-формы состоит из двух тактов: на первом такте декодируются группы разрядов, не содержащие ошибок, и анализируется остаток; на втором такте при наличии ошибок происходит их исправление согласно таблице декодирования. Триггеры 1.1-1.9 входного регистра предназначены для записи исходного кода с информационных входов 8 устройства. Шесть блоков 2 декодирования предназначены для деления на порождающий полином Х +Х+1 (элементы И 48, 49 и ИЛИ 5) и выделения комбинаций, содержащих одиночную ошибку в группе, дающей единицу в соответствующий разряд кода М-формы согласно выраже. ния (5) . Управляющий вход 8 устройства устанавливает нулевым сигналом режим контроля (открыт элемент И 52) и единичным сигналом режим коррекции оди" ночных ошибок (открыт элемент. И 47), ! 478717 Регистр 3 минимальной формы предттазна тетт для, запистт р»зультатов деления на порождающий ттолином Х. +X+ I Э и испранленных 1тазpядoн 11-формы, т.е. 6 н нег о записывается выходной код М-формы. Элементы ИЛИ 4, I 4. 9 группы образуют кодирующее устройство получения ЧР-формы и предназначетть для установ- IO ки в нуль единичными значениями разрядов кода М-формы соответствующих ра зрядон к ода Ч Р-формы, находящихся н триггерах 1.1 1.9 входного регистра, и получения выходного кода ЧР- тг, формы. Элемент Ш!И 5 предназначен для выделения ненулевого остатка после деI в ления на порождающий полином Х +X+I в триггерах 1.1 — 1,9 входного регистра. Единичный сигнал на его выходе после деления означает наличие ошибки в контролируемом коде, Элемент ЗАПРЕТ 6 отключает сигнал контроля при коррекции одиночных оши- 25 бок. С входа 9 поступают тактовые импульсы записи в регистр 3 минимальной формы. Устаноночнь1й вход 10 устройства необходим для установки триггеров 1.1-1.9 входного регистра и ре- З0 гистра 3 минимальной формы в нуленое состояние. В исходном состоянии после подачи на вход 10 начальной установки единичного сигнала триггеры 1.1-1.9 и регистр 3 переходят н нулевое состояние. Сигнал на управляющем входе 8 имеет также нулевое значение (открыт элемент И 52). Предположим в триггеры 1,1-1.9 подан код .ЧР-формы числа 9,, не содержащий ошибок 011011101, При этом на выходах блоков 2.! 2,6 декодирования устанавливается код М-формы числа .9 (начиная с четвертого разряда) 010001, который при по- 4> даче тактового импульса с входа 9 устройства заносится н регистр.З. С помощью группы элементов ИЛИ 4.1-4.9 происходит обратное преобразование, т.е. на ее выходах устанавливается код ЧР-формы, соответствующий коду М-формы в регистре 3,011011101. При этом единичные сигналы на выходам 45, 41-43-39,38 l эпемеHTQB ИЛИ 4,9, 4,5-4.7-4,3, 4.2 группы сбрасывают в нулевое состояние соотттетствующие триггеры 1.9, 1.5-1.7-1.3 и 1,2 входного регистра, В результате этого все триггеры 1.!†I.9 ттрииимают нулевое зна тени», Ko lopo» переца» гт-я через элемент IIJIII 5 и эттетт»ит .1А!тГЕ 6 на контроль иый выход ус тройс тт а и снидетельстгует об отсvTcòíèè ошибки н принятом коде. Если в исходном коде имеются неиспранные разряды, они обнаруживаются при нулевом остатке v тp»rrepax I 1! .9.после делсния на порождаюттгттт1 полипом Х +Х+1 (т.е. обнуления триггер ров 1.1 — I..9 вх.од.ног.о .рег.истра, образующих тетрацы 1101) . He обнаруживаются только те ошибки, которые приводят к переходу н разрешенную комбинацию, При этом к ратность таких ошибок не меньше трех (например, кратна трем при появлении или исчезновении тетрад 1101), а всс одно- и двухкратные ошибки обнаруживаются. Ненулевой остаток в триггерах 1 ° ll .9 устанавливает в единицу элемент ИЛИ 5, которая передается на выход открытого элемента ЗАПРЕТ 6 и сигнализирует о наличии ошибки в принятом коде ° ь Устройство в режиме коррекции одиночных ошибок работает следующим образом. После завершения режима контроля при наличии единичного сигнала на выходе элемента ЗА1!РЕТ 6 н наиболее вероятной одиночной ошибки н контролируемом коде на управляющий вход 8 устройства подается единичный сигнал. При этом закрывается элемент ЗАПРЕТ 6 ° В блоках 2 декодирования закрывается элемент И 52 и открывается элемент И 47, пропускающий на выход элемента ИЛИ 56 сигнал с комбинационной схемы, анализирующей тетрады в триггерах 1,1-1.9 с учетом одиночных ошибок согласно выражению (5) . При обнаружении одной из ошибочных тетрад 010!» 1001, 1111 IIOO на выходе соответствующего блока 2 декодирования устанавливается единичный сигнал. При подаче тактового сигнала записи с входа 9 устройства эти единичные сигналы записываются в соответствующие раэ" ряды регистра 3 минимальной формы, на выходе элемента ИЛИ 4.1-4.9 группы устанавливается выходной код ЧР-формы с исправленными одиночными ошибками. В табл.3 приведены значения выходов блоков 2.1-2.6 декодирования в зависимости от значения остатка в триггерах 1 . 1-1, 9 получившегося-, в l 47Ц21 7 результате одиночной ошибки и коде ЧР-формы числа 9 (звездочкой отмечен ошибочный разряд) . Кроме того, могут исправляться двукратные ошибки, имеющие место в триггере 1.1 и любом из триггеров. группы 1.6-1.9. Таким образом, устройство позволяет исправлять все одиночные ошибки в тетрадах, отстоящих одна от другой на четыре разряда и обнаруживать все одиночные и двойные ошибки, а также большой процент ошибок высшей кратности. 15 Формула и зоб ре тения. 1. Устройство для контроля 3-кода Фибоначчи, содержащее первый регистр 2О иэ и триггеров (и-разрядность кода), прямые выходы триггеров регистра являются соответствующими выходами устройства, прямой выход i-ro триггера (i 4,...,п) соединен с первым вхо- 25 дом (i-3)-го блока декодирования, управляющие входы блоков декодирования объединены и являются управляющим входом устройства, группу элементов ИЛИ и элемент ИЛИ, о т л и ч а ю щ е- 30 е с я тем, что, с целью повышения достоверности контроля, в него введены второй регистр разрядностью (n-3) дополнительный элемент ИЛИ в группу и элемент ЗАПРЕТ, входы элемента ИЛИ подключены к прямым выходам соответствующих триггеров первого регистра, а выход подключен к прямому входу элемента ЗАПРЕТ,.инверсный вход которого подключен к управляющему входу 4О устройства, выход элемента ЗАПРЕТ является контрольным выходом устройства, инверсный выход i-ro (1=3,..., и-1) триггера первого регистра соединен с вторым входом (i-2)-го блока 45 декодирования, прямой выход i-го (i"2,...,n-2) триггера первого регистра соединен с третьим входом (i-1)-ro блока декодирования, прямой выход i-го (i l,...,è"3) триггера первого регистра соединен с четвертым входом 1-ro блока декодирования, выходы блоков декодирования подключены к информационным входам соответствующих разрядов второго регистра, вход записи которого является н тормм управляющим входом устройства, а ус таиовочъп N вход объединен с первыми входами эле- ментов ИЛИ группы и является установочным входом устройства, выход 1-го разряда второго регистра соединен с вторым входом i-ro, третьим входом (i+1)-го и четвертым входом (i+3)-го элементов ИЛИ группы, выходом элементов ИЛИ группы соединены с нулевыми входами соответствующих триггеров первого регистра, единичные входы которого являются соответствующими информационными входами устройства. 2. Устройство по п.l, о т л и ч а ю щ е е с я тем, что блок декодирования содержит элементы ИЛИ, эле" менты И и элемент НЕ, первые входы первого элемента И и первого элемента ИЛИ объединены и являются первым входом блока декодирования, вторые входы первого элемента И и первого элемента ИЛИ объединены и являются вторым входом блока декодирования, первые входы второго элемента И и второго элемента ИЛИ объединены и являются. третьим входом блока декодирования, первый вход третьего элемента И объединен с входом элемента НЕ и является управляющим входом блока декодирования, вторые входы второго элемента И и второго элемента ИЛИ объединены и являются четвертым входом блока декодирования, выход первого элемента И соединен с первыми входами четвертого и пятого элементов И, выход второго элемента ИЛИ соединен с вторым входом пятого элемента И, выход первого элемента КПИ соединен с первым входом шестого элемента И, выход второго элемента И соединен с вторыми входами четвертого и шестого элементов И, выход четвертого элемента И и выход элемента НЕ соединены с соответствующими входами седьмого элемента И, выходы пятого и шестого элементов И соединены с соответствующими входами третьего элемента ИЛИ, выход которого соединен с вторым входом третьего элемента И, выходы третьего и седьмого элементов И соединены с соответствующими входами четвертого элемента ИЛИ, выход которого является выходом блока декодирования. i О )478?) 7 1 а б л и tr а ! Ii -форма Номер рааряда 98 7 6 54 3? 1 II 10 98 7 6 54 3?! Вес раарйда 7 4 3 2 1 I I ) 7 5 4 3 2 1 ) 1 1 О 0 8 I 0 О О О 1 О О О О О 1 О l 1 0 E 0 I 9 1 О О О 1 0 0 0 О О О I О 1 I 1 О l 1 О Таблипа 2 Форма кода Кодовые слова )1-форма M(i+3(ЧР-форма TÄE Т„,z Т;„Т; О 0 О О О 0 О 1 0 О 1 0 0 1 О 0 1 0 О. О Таблица 3 Код остатка 1,9 1.8 1,7 1,6 ), - .4 I 3 1.2 ),1 Выходы блоков декодирований 2.2 2,1 2.6 2, 5 2.4 2.3 О О 0 О О О О О 0 О О О О О О О О О О О О О О 0 1 О О 0 1 О О 1 1 1 1:. 1 О О О О 1 О 1 О О 0 О О О О, О О О О О 0 О О, ) I 0 О д" 1 О 1 О О ! 1 О l 1 0 О О О 0 О О О О О Т;„Т; Т„„Т„ О i ! О ) О 1 О О 1 ) 1 1 0 О I 1 1 О О О О О О О О О 0. О 1 О I О I О 1 О О 0 О О О О О 0 О О О О О О 0 0 О 0 О О 1 О О О 1 О 1 0 l 0 1 0 О 0 0 0 О 00 0 1478 7 У Ф Фиг,f шаг Составитель О.Неплохов Техред Л. Сердюкова КорректорО.Кравцова Редактор И,Шулла Заказ 2365/49 Тираж 669 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина,101
