Устройство для контроля 3-кода Фибоначчи Советский патент 1988 года по МПК G06F11/08 

с соответствующими связями, ф-лы, 4 ил., 1 табл.

1 3 .п.

(Л

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

16 Q

Неисправима ouLufm

00 Х) СП

со о:

Ри,г.1

2

1439596

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

разряд Т.. которого определяется выражением

10

t- М

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

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

На фиг, 1 представлена схема устройства для контроля 3-кода Фибоначчи; на фиг 2 схема сравнения с константой; на фиг, 3 - схема блока коррекции; на фиг. 4 - временная диаграмма работы устройства для конт- 15 где 1 Ь i-й разряд п-разрядного

кода М-формы,

При этом каждый единичный разряд кода М-форгФ в коде ЧР-формы представляется кодовой тетрадой 1011.

1+--г

+ М .

Si- 9

i 1,2,

роля З -кода Ф ибонач га,

Ус 1 ройство (фиг, 1) содер лсит с - первого по третр й регистры 1-3 сдвига, блок 4 коррекции, схему 5 сравнения

с константой, первый и второй элемен-20 т ..е.. код ЧР формы.получается путем

умножения кода М-формы на порождаю-

ть И 6 И 7 5 с первого по третий элементы HJIl-i S-IOj выход 11 результата устройства, информационный вход 12 устройства, первый тактовЕЖ вход 13 устройства, вход 14 начальной уста- 25 новки з- стройства, второй тактовый вход

15устройства, третий тактовьй вход

16устройства,; выход 17 ошибки уст™ .ройстпа., Бьшод 18 -неисправимой ошибки стройс;тва.

щий полином X + X + 1 с помощью развертки единичных разрядов кода М-формы,

Два дополнительных младших разряд кода ЧР-формы имеют нулевой вес, а два старших разряда всегда равны нулю. Поэтому, если не .использовать два старших разряда, то разрядность

30 кода ЧР-ФОР1--1Ы будет такая же, как и кода М--формь1, Так как в коде ЧР-форм содержится целое число тетрад 1011, соответствующих коду порождающего полинома, то минимальное кодовое

Схема 5 сравнения с константой (фиг. 2) содергкит элемент ИЛИ 19, элемент ьИ 20 и 21, причем входы разрядов cxes-a 5 сравнения соединены соответственно с входа1-ги: элемента ИЛИ 19 и пе.рвого элемента И 20, выходы которых соединены соответственно с входами второго элемента И 21, выход которого является }зыходом схемы 5 40 более трех подряд идуш;их единиц, сравнения с константой,т.е. обладает свойством самосинхроБлок 4 коррекции (фиг« 3) содержит первьй и второй элементы ИЛИ 22 и 23, первьш и второй элементы И 24 и 25

На входы 13, 15 и 16 устройства поступают соответственно синхросерия (фиго 4)5 проинвертированная синхросерия и синхросерия,, задержанная на сумму времени установки разрядов регистра 1 и задержки элемента И 6„

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

% ) 55

C(i-2)p5(i-4)-Cf5(i-5) ,

Для минимальной формы: (М-формы) 3-кода Фибоначчи (в которой после

низации.

Процедура декодирования заключается в вьоделении тетрад 1101 в

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

50 М-формы определяется логическим выражением

М Т М-1-З + i

. т -Т

14-2. I -(-I 1

i 15 2, ,.., п-3,

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

2

разряд Т.. которого определяется выражением

М

разряд п-разр

1+--г

+ М .

Si- 9

i-й раз

i 1,2,

умножения кода М-формы на порождаю-

5

щий полином X + X + 1 с помощью развертки единичных разрядов кода М-формы,

Два дополнительных младших разряда кода ЧР-формы имеют нулевой вес, а два старших разряда всегда равны нулю. Поэтому, если не .использовать два старших разряда, то разрядность

0 кода ЧР-ФОР1--1Ы будет такая же, как и кода М--формь1, Так как в коде ЧР-формы содержится целое число тетрад 1011, соответствующих коду порождающего полинома, то минимальное кодовое

2 расстояние равно трем, независимо от разрядности кода. Это позволяет исправлять одиночные ошибки в коде ЧР-формы любой длины.

Кроме того в коде ЧР-формы нет

низации.

Процедура декодирования заключается в вьоделении тетрад 1101 в

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

50 М-формы определяется логическим выражением

+ i

. т -Т

14-2. I -(-I 1

i 15 2, ,.., п-3,

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

31439596

содержащие одиночные ошибки

че ЧР за на

(звездочками отмечены неисправные разряды).

Форма кода

1

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

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

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

Т

1 + 3

1

а корректирующая функция для i-й ошибочной тетрады при этом равна

F. Т,

1 -fj

(Т; + Т,-, ) + Т; -Т;

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

ч-г

+3

(Т; + Т;, ). (4)

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

-

)

.

10

15

20

25

Первый регистр 1 сдвига предназначен для записи тетрад входного кода ЧР-формы. Во второй регистр 2 сдвига заносятся тетрады остатка от деления на порождающий полином.

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

Схема 5 сравнения с константой реализует функцию (3).

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

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

В исходном состоянии, после подачи на вход 14 начальной установки единичного сигнала, регистры 1-3 переходят в нулевое состояние. На вход устройства подается, например, код ЧР-формь 1101110101101, соответствующий коду М-формы 0001000100001. Предположим, что первый (младший), третий и шестой разряды принимаемого кода ошибочны, т.е. входная кодовая комбинация имеет вид 0111100101101. Разряды входного кода, начиная со старшего, заносятся с информационного входа 12 устройства в регистр 1 сдвига по переднему фронту синхроимпульсов (СИ), поступающих с входа 13 устройства. После подачи четвертого син- роимпульса в регистре 1 сдвига устанавливается первая тетрада 1101 и согласно (3) на выходе элемента И 6 устанавливается единичньй уровень. По появившемуся на входе 16 устройства переднему фронту четвертого син хроимпульса единица с выхода элемента И 6 заносится в младший разряд РГЗ, регистра 3 сдвига. Одновременно единичный сигнал с выхода элемента ИЛИ 8 45 устанавливает в нулевое состояние регистр 1 сдвига. Таким образом, происходит деление на порождаклций полином и запись результата деления в регистр 3 сдвига. До прихода заднего фронта четвертого синхроимпульса процесс деления заканчивается и в регистр 2 остатка заносится нулевое значение старшего разряда РП. первого регистра 1 сдвига.

30

35

40

50

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

По приходу девятого синхроимпульса в регистре 1 устанавливается ошибочная тетрада 1001, Так как на выходе элемента И 6 единичный сигнал не устанавлипается5 то по заднему фронту девятого синхроимпульса единица с вьЕ-юда старшего разряда РГ14 регистра 1 заносится в регистр 2. Единичное значение младшего разряда РГ2, регистра 2 сигнализирует о наличии ошибки во входном коде После

появления заднего фронта двенадцатого 15 тактовым входом устройства и с выхоскихроимпульса в регистре. 2 устанавливается тетрада 1001. При этом единичное значение принимают элемек:ты ИЛИ 22„ И 25 и ИЛИ 23 блока 4 коррекции,, Единица с выхода блока 4 коррекции поступает через элемент ИЛИ 10 на выход кода M-фop iЫ5 а по приходу тринадцатого синхроимпульса подается на вход, установки в ноль регистра 2 через открывшийся элемент И 7 и элемент ИЛИ 9 Таким образом, ошибочная тетрада 1001 правильно декодируется и регистр остатка принимает нулевое значение,

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

элемент И 21, и на выходе 18 устрой- 5 выходом результата устройства, выход

ошибки которого соединен с выходом первого разряда второго регистра сдвига, выходы первого, второго и четвертого разрядов которого соедине

ства появляется сигнал. Формула изобретения

1, Устройство для контроля 3-кода Фабоначчи,, содержащее первый регистр сдвига, схему сравнения с константой два элемента И и два элемента ИЛИ, причем информационный, вход устройства соединен с информационным входом первого регистра сдвига, тактовый вход которого соединен с первым тактовым входом устройства, выход первого элемента И соединен с первым

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

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

1А395966

сдвига, выходы разрядов которых соединены с входами разрядов схемы срав

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

0

дом -второго элемента ИЛИ, первый вход которого соединен с вторым входом первого элемента ИУй1, с входом установки в О третьего регистра сдвига и с входом начальной установки устройства, третий тактовыр вход которого соединен с тактовым входом третьего регистра сдвига и с первым входом второго элемента выход которого 5 соединен с вторым входом второго

элемента UH-i, выход первого элемента И соединен с информационным входом третьего регистра сдвига, выход блока коррекции соединен с вторым входом второго элемента И и с первым входом третьего элемента ИЛИ, второй вход и выход которого соединены соответственно с выходом четвертого разряда третьего регистра сдвига и с

0

5 выходом результата устройства, выход

ошибки которого соединен с выходом первого разряда второго регистра сдвига, выходы первого, второго и четвертого разрядов которого соедине

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

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

5

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

Фи.д

вгвз / О i е О f 00 , ° f г S i S f в в (О ff fs а ft fS

/j-jiArLrmjTJiJTJTJiJTJiJ

/ /7t-TT

РГЗ РГЗ

ргг

d

I о о

Фив. 2

ГТ

Г1

ГПTL

П

П

I о о о о t о о

п