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

 

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

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

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

РЕСПУБЛИК (51)4 С 06 F

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

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

f3

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4240804/24-24 (22) 07.05.87 (46) 23,11.88. Бюл. Р 43 (72) А.П.Стахов, В,А.Лужецкий, и П.В.Козлюк (53) 681.3(088 ° 8) (56) Авторское свидетельство СССР

Р 817718, кл. Г 06 F 11/00, 1979.

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

Р 1149261, кл. С 06 Г 11/00, 1983.

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

N - 951291, кл. G 06 F 11/00, 1980.

„„SU„„1439596 A 1 (54) УСТРОЙСТВО пЛЯ КОНТРОЛЯ 3-КОЛА фИБОНА 1КИ (57) Изобретение относится к вычислительной технике и может быть использовано для контроля и исправления ошибок в устройствах для передачи и магнитной записи информации, использующих коды Фибоначчи ° Цель изобретения — расширение функциональных возможностей за счет обнаружения двойных ошибок и исправления одиночных ошибок. В устройство, содержащее регистр сдвига, схемц 5 сравнения с константой, элементы И 6, 7 и элементы

ИЛИ 8, 9, введены регистры 2, 3 сдвига, блок 4 коррекции и элемент ИЛИ 10 Ж с соответствующими связями, 1 з,п. ф-лы, 4 ил., 1 табл.

1439596 зоьано для контроля и исправления ошибок 3-кода Фибоначчи.

Целью изобретения является рас-ширение функциопальных гозможностей за счет обнаружения двойных ошибок

И ИСПРЯВЛЕНИЯ ОДИНОЧНЬП< ОтШИО От<, На фнг, 1 представлеьта схема устройства для :<онтроля 3-кода Фибонач.и. на фиг: 2 — схема сравнения с константотй9 на. фиг, 3 — схемЯ блокЯ кору:-кции; на фиг. 4 - временная диаграмма работы устройства для контроля 3-кода ФибонЯччи

7C Поттстно (фттГ, 1) т Оцеужттт первого по третий гегистры 1-3 сдвига„ бл<п< 4 коррекции. схему 5 спявне птя

С КОНСТЯНТОй,. ПЕРВЫЙ::..-. т:тОРОЙ ЭЛЕМЗНты И 6 I I / ". IIeps oro rso ттретий маять. ИЛИ 8-10, выход 11 результата устуот-,cTTÇB. информяцтионныйт вход 12 ттn I -,ni- ство первый ":акт<)вый вход 3 3

Устуойстват вхоД 14 начальншй Установки ус:<ройствя, второй тактовый зхо1

1"". стpoéñòÂß третий r=ктовый Вхсд

16 устройства, выход 17 Ошибки устройства., вьГ".Од I8 неисправимой ОшиО-КИ тстттой< ТВЯ „

М 1 М +М. — 1,2, ..., n, 2Г, . хема. 5 срЯвнения т кОнстЯнтОЙ (фиг. 2) содержит элемент Р,.ЛИ 19, элемтенты.И 20 и 21,. причем входы разрядов схемы 5 сравнения =оединены соответственно с входами элемента ИЛИ

19 и первого элемента И 20. вьг<оды

КОтОрЬтХ СОЕДИНЕНЫ СООТ ЗЕтСТВЕННО С входами второго элемента И 21, выход которого является .3ь:ходом схемы 5 щ сравнения с константой, Блок 4 коррекции (фиг. 3) содержит первый и второй элементы ИЛИ 22 и 23, первый и второй элементы И 24 и 25, Ня вхоцы 13, 15 и 16 устройства я» поступают соответственно синхросерия (фиг. 4), проинвертировянная синхросерия и синхросерия,, задержанная на сумму времени установки разрядов регистра 1 и задержки элемента И 6.

Б 3-системе Фибоначчи счисления вес 1-го разряда определяется из следующего рекуррентного соотношения:

1 4 ( (1 2)+

2 ч

° °, и-- . о

Ненулевой остаток от деления на порождающий полином свидетельствует о наличии ошибки. B таблице приведены

Изобретение относится к вьгчислительной технике и может быть испольДля минимальной формы (М-формы)

З-.кода Фибоняччи (в которой после каждого единичного разряда следует

1 не менее трех нупевых разрядов) существует код частично развернутой формы (ЧР-формы), получаемый в результате развертки каждого единичного разряда М-формы согласно (1), i-й разряд Т„ которого определяется выраI жением где М„ — 1-й разряд и-разрядного кода М-формы.

При этом каждый единичный разряд кода М-формы в коде ЧР-формы представляется кодовой тетрадой 1011, т.е. код ЧГ-формы .получается путем умножения кода Yi-формы на порождающий полипом Х + Х + с помоцтью

3 развертки единичных разрядов кода

М-формы, Два дополнительных младших разряда кода ЧР-формы имеют нулевой вес, а двя старших разряда всегда равны нулю, Поэтому, если не использовать два старших разряда, то разрядность кода ЧР-формы будет такая же, как и кода М-формы. ТЯ1< как в коде ЧР-формы содержится целое число тетрад l011, соответствующих коду порождающего полинома, То минимальное кодовое расстояние равно трем, независимо от ра -p>AHo«II I

ЧР-формы любой длины.

Кроме того в коде ЧР-,формы нет более трех подряд идущих единиц, т.е. обладает свойством самосинхронизации.

Процедура декодирования заключается в выделении тетрад 1101 в коде ЧР-формы и замене (свертке) их на единичное значение соответствующего разряда в коде М-формы, что соответствует делению на порождающий полином. Значение i-го разряда кода

М-формы определяется логическим выражением т+3 — т+3, 1 +т T) з 1439596 тетрады, содержащие одиночные ошибки (звездочками отмечены неисправные ч разряды). Ч

Форма кода

Кодовые слова

M-форма

M(i+1) ЧР-форма

0000 101 1

0001

1010

00101001

01001111

1000 00 t 1 (2) 55

Исправление ошибок осуществляется путем нахождения в коде остатка тетрад, соответствующих коду порождающего полинома с учетом одиночной ошибки.

Для последовательного кода

ЧР-формы процедуру деления на порождающий полином можно совместить с исправлением ошибочных тетрад 1111, Тогда i-разряд кода М-формы будет определяется выражением а корректирующая функция для i-й ошибочной тетрады при этом равна

В процессе деления на порождающий полином определяются также неисправимые тетрады 1011 и 0111, содержащие двойную ошибку. В этом случае вырабатывается сигнал "Неисправимая ошибка" описываемый функцией

F Т, Т;, (7; + Т;„). (4) Код ЧР-формы позволяет обнаружить все одиночные и двойные ошибки, а также все ошибки высшей кратности, не приводящие в разрешенной кодовой комбинации. Кроме того исправляются все единочные ошибки в тетрадах, отстоящих друг от друга на четыре разряда.

1О

Первый регистр 1 сдвига предназнаен для записи тетрад входного кода

P-формы. Во второй регистр 2 сдвига заносятся тетрады остатка от деления на порождающий полином.

В третьем регистре 3 сдвига осуществляется задержка коДа М-формы на четыре такта для согласования с выходом блока 4 коррекции, реализующего . функцию коррекции (3), Схема 5 сравнения с константой реализует Аункцию (3).

С помощью элемента И 6 выделяется кодовая комбинация согласно (2), Устройство работает следующим образом.

В исходном состоянии, после подачи на вход 14 начальной установки единичного сигнала, регистры 1-3 переходят в нулевое состояние, На вход устройства подается, например, код

ЧР-формы 110!110101101, соответствующий коду М-формы 0001000100001. Предположим, что первый (младший), третий и шестой разряды принимаемого кода ошибочны, т.е. входная кодовая комбинация имеет вид 0 11110010110 1, Разряды входного кода, начиная со старшего, заносятся с информационного входа.12 устройства в регистр 1 сдвига по переднему фронту синхроимпульсов (СИ), поступающих с входа 13 устройства. После подачи четвертого синроимпульса в регистре 1 сдвига устанавливается первая тетрада 1101 и согласно (3) на выходе элемента И 6 уСтанавливается единичный уровень.

По появившемуся на входе 16 устройства переднему фронту четвертого син» хроимпульса единица с выхода элемента

И 6 заносится в младший разряд РГЗ, регистра 3 сдвига. Одновременно единичный сигнал с выхода элемента ИЛИ 8 устанавливает в нулевое состояние регистр 1 сдвига. Таким образом, происходит деление на порождающий полином и запись результата деления в регистр 3 сдвига. До прихода заднего фронта четвертого синхроимпульса процесс деления заканчивается и в регистр 2 остатка заносится нулевое значение старшего разряда РГ1 пер4 вого регистра 1 сдвига.

После прихода седьмого синхроимпульса единичное значение старшего разряда РГЗд регистра 3 передается на выход элемента ИЛИ 10, что со143 ответствует появлению старшего разряда выходного кода М-формы.

По приходу девятого синхроимпульса з регистре 1 устанавливается ошибочная тетрада 1001, Так как на выходе элемента И б единичный сигнал не устанавливается, то по заднему фронту девятого синхроимпульса единипа с выхода старшего разряда РГ1 регистра i заносится в регистр 2„

Единичное значение младшего разряда

1 Г2, регистра 2 сигнализирует о наличии ошибки во входном коде. После поязления заднего фронта двенадцатого синхроимпульса в регистре 2 устанавливается тетрада 1001. При этом единичное значение принимают элементы

ИЛИ 22. И 25 и ИЛИ 23 блока 4 коррекции,, Единица с выхода блока 4 коррекции поступает через элемент

ИЛИ 10 па выход кода 1" -форьы, а пс приходу тринадцатого синхроимпульса подаетс; †. на вход установки з ноль регистра 2 через открывшийся элемент

И 7 и элемент ИЛИ 9. Таким образом, ошибо шая тетрада 1001 правильно декодируется и регистр остатка принимает нулевое значение, После подачи пятнадцатого слнхроимпульса в регистре 1 устанавливается ошибочная тетрада 0111. При этом з ециничное состояние устанавливаются элементы И 20 и ИЛИ 19,. открывающие элемент И 21, и на выходе 18 устройства появляется сигнал. изобретения

Ф о р м у л а

1. Устройство для контроля 3-кода фабоначчи, содержащее первый регистр сдвига,. схему сравнения с константой, дза элемента И и два элемента ИЗП, причем информационный вход устройства соединен с информационным входом первого регистра сдвига, тактовый вход которого соединен с первым тактовым входом устройства, выход первого элемента И соединен с первым входом первого элемента HJIH, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обнаружения двойных . ошибок и исправления одиночных ошибок, оно содержит второй и третий регистры сдвига, блок коррекции и третий элемент ИЛИ, причем выход первого элемента ИЛИ соединен с входом установки в 0" первого регистра

959á 6 сдвига, выходы разрядов которых соединены с входами разрядоз схемы сразкения с константой, выход которой является выходом неисправимой ошибки

5 устроиства, выходы первого, второго и четвертого разрядов первого регистра сдвига соединены соответственно с входами первого элемента И, выход четвертого разряда первого регистра сдвига соединен с информационным входом второго регистра сдвига, тактовый вход и вход установки з "0 которого соединены соответственно с вторым тактовым входом устройства и с выходом второго элeìåíòà ИЛИ, первый вход которого соединен с вторым входом первого элемента ИЛИ, с входом установки в "Он третьего регистра сдвига и с входом начальной установки устройства, третий тактовый вход которого соединен с тактовым входом третьего регистра сдвига и с первым входом второго элемента И, выход которого

2 соединен с вторым входом второго элемента ИЛИ, выход первого элемента

И соединен с информационным входом третьего рсгистра. сдвига, выход блока коррекции соединен с вторым

30 входом второго элемента И и с первым входом третьег0 элемента ИЛИ, второй вход и выход которого соединены соответственно с выходом четвертого разряда третьего регистра сдвига и с выходом результата устройства, выход ошибки которого соедлнен с выходом первого разряда второго регистра сдвига, выходы первого, второго и четвертого разрядов которого соединено ны соответственчо с первым, вторым и третьим входами блока коррекции.

2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок коррекции содержит два элемента И и два элемента ИЛИ, причем первый и второй входы первого элемента ИЛИ являются соответственно первым и вторым входами блока коррекции, выход которого соединен с выходом второго элемента

ИЛИ, первый и второй входы которого соединены соответственно с выходами первого и второго элементов И, первый и второй входы первого элемента

И соединены соответственно с первым и вторым входами первого элемента

ИЛИ, первый и второй входы второго элемента И соединены соответственно с выходом первого элемента ИЛИ и с третьим входом блока коррекции.

1439596

urrurèîr î

rz

Я е rr а a r rS

rs

Pff

PI$

РГ3

PI 2 оа о о оо л еис тра Уимо т ми&а ц

Фиг. Ф

Составитель А. Клюев

Редактор A. Ворович Техред М.Ходанич Корректор И. Муска

Закаэ 6078/48 ТиРаж 704 Подписное

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

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

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