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

1

Изобретение относится к вычислительной технике и может быть использовано для контроля информации в системах, использующих 3-коды Фибоначчи.

Целью изобретения является повышение достоверности контроля.

На фиг.1 представлена структурная схема устройства д.гя п 9; на фиг.2 - функциональная схема блока декодирования.

Устройство содержит триггеры 1,1- 1.9 первого регистра, блоки 2.1-2.6 декодирования, второй регистр 3, группу элементов ПЛИ 4.1-4.9, элемент ИЛИ 5, -элемент ЗАПРЕТ 6, информационные пходы 7 vci роист па, первый 8

и второй 9 управляющие входы устройства, вход 10 установки устройства, управляющий вход 1I блока декодирования , четыре входа 12-15 блока декодирования, прямые выходы 16-24 соответствующих триггеров 1.1-1,9 первого регистра инверсные выходы 25-30 соответствующих триггеров 1.3-1.7 первого регистра, выходы 31-36 разрядов, начиная с младшего, второго- регистра 3, выходы J7-45 соответствующих элементов ИЛИ группы 4.1-4.9.

В состав блока декодирования входят первый 46, второй 47, третий 48, четвертый 49, пятый 50, шестой 5.1 и седьмой 52 олсменты И, первый 53,

ь

sj

оо ю

пторой 54, третий 55 и четвертый 56 элементы ИЛИ и элемент П1Г 57.

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

В Фибоначчиевой р-еистеме счисления значение весов разрядов Ч,,(1) определяется из рекуррентного выражения

О, i Р+ 1;(О

J4V(i-t)-HfP(i-l-p),i7 p+i

Так как для выражение принимаMVU)

ет вид (i)

I, U4,

(i-|) + (i-4), i 4

или

(1)

1, U4,

(2)

| Vi-2) %(i-4)i 4(1-5), ..

Для кода минимальной формы (М-фор- мы) 3-кода Фибоначчи существует код частично развернутой формы (ЧР-форма), разряды T(i) которого определяются с учетом выражения (2) следующими вы- ражениями:

М(4),1-1,

М(4)+М(5),

М(5)+М(6), (3)

M(i) + M(i+2) + M(i+3),i-73,

где M(i) - i-й рязряд кода М формы.

При этом каждая единица кода

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

Р качестве примера в табл.1 приведены коды М-формы и ЧР-формы чиссп8 и 9.

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

Из выражения (3) можно определить значения р.-прядов кода М-формы при декодировании ЧР-формы

М(З-Н) l()-T(i+2)-T(i+lVT(i),

1 1.;,... ,п-з.(4)

0

5

0

5

0

35

40

45 50

55

Табл.2 декодирования приведена с учетом (4) и напнчня одиночных оши- бок в коде ЧР-формы (звездочками от- мечены неисправные разряды).

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

При этом все последовательности (тетрады) в коде ЧР-формы 1011 дают единицу в соответствующий разряд кода М-формы и затем обнуляются, т.е. происходит параллельное деление на

л

порождающий полином X +Х+1. Если ошибки отсутствуют, то в регистре кода ЧР-формы устанавливаются нулевые значения всех разрядов. Ошибочные комбинации дают нулевой остаток. Если имеет место одиночная ошибка, то она исправляется согласно таблице декодирования. Кроме того, исправляются все одиночные ошибки, возникающие в группах разрядов ЧР-формы, начинающихся номерами i, i+8, i+16,..,, i-t-k-8 (k 1,2,...). Корректирующая функция Р., для i-й; тетрады ( n-З) определяется выражением

F, - ТДтм-СГ а+Т з) + f ,,fix

x (Т, + Т„, ).

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

Триггеры 1.1-1.9 входного регистра предназначены для записи исходного кода с информационных входов 8 устройства.

Шесть блоков 2 декодирования предназначены для деления на порождающий полином Х5+Х+1 (элементы И 48, 49 и КЛИ 5) и выделения комбинаций, содержащих одиночную ошибку в группе, дающей единицу в соответствующий разряд кода М-формы согласно выражения (5) .

Управляющий вход 8 устройства устанавливает нулевым сигналом режим контропя (открыт элемент И 52) и единичным сигналам режим коррекции одиночных ошибок (открыт элемент-И 47).

результатов деле порождяющий полином X +Х+1

Регистр 3 минимальной формы предназначен для, записи ния на

и исправленных разрядов М-формы, т.е в него записывается выходной код М-формы.

Элементы ИЛИ 4.1-4.9 группы образуют кодирующее устройство получения ЧР-формы и предназначены для устаноп ки в нуль единичными значениями разрядов кода М-формы соответствующих разрядов кода ЧР-формы, находящихся в триггерах 1.1-1.9 входного регистра, и получения выходного кода ЧР- формы.

Элемент ИЛИ 5 предназначен для выделения ненулевого остатка после де-iЯ

ления на порождающий полином X +Х+1 в триггерах 1.1-1,9 входного регистра. Единичный сигнал на его выходе после деления означает наличие ошибки в контролируемом коде.

Элемент ЗАПРЕТ 6 отключает сигнал контроля при коррекции одиночных оши бок. С входа 9 поступают тактовые импульсы записи в регистр 3 минимальной формы. Установочный вход 10 устройства необходим для установки триггеров 1.1-1.9 входного регистра и регистра 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,011011101. При этом единичные сигналы на выходах 45 41-43-39,38 I элементов ИЛИ 4.9, 4,5-4.7-4.3, 4.2 группы сбрасывают в нулевое состояние соответствующие триггеры 1.9, 1.5-1.7-1.3 и 1.2 входного регистра. В результате этого все триггеры 1.1-1.9 принимают нуле

15

20

-JQ

25

яое значение, которое п репяетсч через элемент ПЛИ 5 и -элемент ИЛПРКТ 6 на контропьнын пыход устройства и свидетельствует об отсутствии ошибки в принятом коде.

Если в исходном коде имеются неисправные разряды, они обнаруживаются при нулевом остатке в триггерах 1.1-° 1.9.после деления на порождающий полином (т.е. обнуления триггеров 1.1-1.9 входного регистра, образующих тетрады 1101). Не обнаруживаются только тс ошибки, которые приводят к переходу в разрешенную комбинацию. При этом кратность таких ошибок не меньше трех (например, кратна трем при появлении или исчезновении тетрад 1101), а все одно- и двухкратные ошибки обнаруживаются.

Ненулевой остаток в триггерах 1.1- 1.9 устанавливает в единицу элемент ИЛИ 5, которая передается на выход открытого элемента ЗАПРЕТ 6 и сигнализирует о наличии ошибки в принятом коде.

Устройство в режиме коррекции одиночных ошибок работает следующим образом.

После завершения режима контроля при наличии единичного сигнала на выходе элемента ЗАПРЕТ 6 и наиболее вероятной одинолной ошибки в контролируемом коде на управляющий вход 8 35 устройства подается единичный сигнал. При этом закрывается элемент ЗАПРЕТ 6. В блоках 2 декодирования закрывается элемент И 52 и открывается элемент И 47, пропускающий на выход элемента ИЛИ 56 сигнал с комбинационной схе30

0

5

мы, анализирующей тетрады в триггерах 1.1-1.9 с учетом одиночных ошибок согласно выражению (5). При обнаружении одной из ошибочных тетрад 0101, 1001, 1111, 1 100 на выходе соответствующего блока 2 декодирования устанавливается единичный сигнал. При подаче тактового сигнала записи с входа 9 устройства эти единичные сигналы записываются в соответствующие раз- ряды регистра 3 минимальной формы, на выходе элемента ИЛИ 4.1-4.9 группы устанавливается выходной код ЧР-формы с исправленными одиночными ошибками.В табл.3 приведены значения выходов блоков 2.1-2.6 декодирования в зависимости от значения остатка в

триггерах 1.1

получившегося- в

результате одиночной ошибки п коде ЧР-формы числа 9 ( звездочкой отмечен ошибочный разряд).

Кроме того, могут исправляться двукратные ошибки, имеющие место в триггере 1.1 и любом из триггеров, группы 1.6-1.9.

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

Формула изобретения

I. Устройство для контроля 3-кода Фибоначчи, содержащее первый регистр из п триггеров (n-разрядность кода), прямые выходы триггеров регистра являются соответствующими выходами устройства, прямой выход 1-го триггера (i 4,..,,п) соединен с первым вхо- дом ()-ro блока декодирования, управляющие входы блоков декодирования объединены и являются управляющим входом устройства, группу элементов ИЛИ и элемент ИЛИ, о тличающее с я тем, что, с целью повышения достоверности контроля, в него введены второй регистр разрядностью (п-3), дополнительный элемент ИЛИ в группу и элемент ЗАПРЕТ, входы элемента ИЛИ подключены к прямым выходам соответствующих триггеров первого регистра, а выход подключен к прямому входу элемента ЗАПРЕТ, инверсный вход которого подключен к управляющему входу устройства, выход элемента ЗАПРЕТ является контрольным выходом устройства, инверсный выход 1-го (,..., п-1) триггера первого регистра соединен с вторым входом (1-2)-го блока декодирования, прямой выход 1-го (,...,п-2) триггера первого регистра соединен с третьим входом (1-1)-го блока декодирования, прямой выход 1-го (,...,п-3) триггера первого регистра соединен с четвертым входом 1-го блока декодирования, выходы блоков декодирования подключены к информационным входам соответствующих разрядов второго регистра, вход записи

которого является яторым управляющим входом устройства, я устаповочтшй вход объединен с первыми входами эле- ментов ИЛИ группы и является установочным входом устройства, выход 1-го разряда второго регистра соединен с вторым входом 1-го, третьим входом (i-H)-ro и четвертым входом (1+3)-го элементов ИЛИ группы, выходом элементов ИЛИ группы соединены с нулевыми входами соответствующих триггеров первого регистра, единичные входы которого являются соответствующими информационными входами устройства.

2. Устройство по п.1, отличающееся тем, что блок декодирования содержит элементы ИЛИ, элементы И и элемент НЕ, первые входы J первого элемента И и первого элемента ИЛИ объединены и являются первым входом блока декодирования, вторые входы первого элемента И и первого элемента ИЛИ объединены и являются вторым входом блока декодирования, первые входы второго элемента И и второго элемента ИЛИ объединены и являются третьим входом блока декодирования, первый вход третьего элемента И объединен с входом элемента НЕ и является управляющим входом блока декодирования, вторые входы второго элемента И и второго элемента ИЛИ объединены и являются четвертым входом блока декодирования, выход первого элемента И соединен с первыми входами четвертого и пятого элементов И, выход второго элемента ИЛИ соединен с вторым входом пятого элемента И, выход первого элемента ЯЛИ соединен с первым входом шестого элемента И, выход второго элемента И соединен с вторыми входами четвертого и шестого элементов И, выход четвертого элемента И и выход элемента НЕ соединены с соответствующими входами седьмого элемента И, выходы пятого и шестого элементов И соединены с соответствующими входами третьего элемента ИЛИ, выход которого соединен с вторым входом третьего элемента И, выходы третьего и седьмого элементов И соединены с соответствующими входами четвертого элемента ИЛИ, выход которого является выходом блока декодирования.

Изобретение относится к вычислительной технике и может быть использовано для контроля информации в системах, использующих 3 - коды Фибоначчи. Целью изобретения является повышение достоверности контроля. Устройство содержит девять триггеров первого регистра, шесть блоков декодирования, второй регистр, десять элементов ИЛИ, элемент ЗАПРЕТ, девять информационных входов устройства, два управляющих входа устройства, вход установки устройства, управляющий вход блока декодирования, четыре входа блока декодирования, девять прямых выходов соответствующих триггеров первого регистра, шесть инверсных выходов соответствующих шести триггеров первого регистра, шесть выходов разрядов, начиная с младшего второго регистра, девять выходов соответствующих девяти элементов ИЛИ группы. Блок декодирования содержит семь элементов И, четыре элемента ИЛИ, элемент НЕ. 1 з.п. ф-лы, 2 ил.