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

Изобретение относится к вычислительной технике и может быть использовано для контроля и исправления ошибок 2-кода Фибоначчи.

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

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

Устройство (фиг.1) содержит группу триггеров 1.1-1.7, первую группу элементов И 2.1-2.5, вторую группу элементов И 3,1- 3.6, третью группу элементов И 4.1-4.4, четвертую группу элементов И 5.1 и 5.2, первый 6.1 и второй 6.2 блоки свертки по модулю два, дешифратор 7, блок 8 коррекции ошибок, группу элементов ИЛИ 9.1-9.6. входы

10.1-10.7 информационных разрядов устройства, входы нечетного 10.8 и четного 10.9 контрольных разрядов устройства, вход 11 сброса устройства, тактовый вход 12 устройства, элемент ИЛИ 13, входы 14.1-14.4 разрядов первого информационного входа блока 8 коррекции ошибок, входы 15.1-15.6 разрядов второго информационного входа блока 8 коррекции ошибок, входы 16.1-16.3 разрядов управляющих входа блока 8 коррекции ошибок.

Блок 8 коррекции ошибок (фиг.2) содержит первую группу элементов И 17.1-17.6, вторую группу элементов И 18.1-18.10, группу элементов ИЛИ 19 1-19.4.

Любое натуральное число N в п-разряд- ном 2-коде Фибоначчи представляется в виде

о о ю о

О О

N

Z ai № (0.

I 1

гдеа| Ј{0,1};

0 при П 0; 1 при (1)

902(1 - 1) + рг( - 3) при п 0.

Минимальная форма (М-норма) представления числа в 2-коде Фибоначчи имеет не менее двух О между единичными разрядами, т.е. для каждой 1 М-формы можно выделить группу 100, Если сложить исходный и сдвинутый вправо на один разряд коды М-формы (что соответствует умножению на полином 1 + х ), получают следующее преобразование выделенных групп: 100-НЮ. В полученном коде каждая 1 исходного кода М-формы представлена двумя 1, поэтому его можно назвать 2- кодом Фибоначчи с дублированием 1 (2 - ФОБ). Код 2 - ФОЕ можно записать в виде полинома, полученного в результате умножения полинома М (х) М-формы на образующий полином 1 + х :

Т(х) 21(ai + ai+i)x j BiX1.

I 0

i o

Ki + 5 ail-1;

i i

Ki + 2, 32i

i 1

Sri.

(2)

а Bi -Вы; i 2,n: ai Bi.

(3)

Каждому виду синдрома соответствует свой тип ошибки, которые сведены в таблицуИсходя из таблицы, определяют корректирующую функцию для каждого разряда при четном и нечетном i (i 1n-1): I четное:

Ci(Bi+2 §i+i Bi + Bi+2 61+1 Bi) -SiS2 + + (BiBi-iJ3i-2+ B| Bi-i 81-2) -SiS2 + + Bi+i Bi Bi-i -SiS2 +

+ Bi-2 BM bi bi+i Bi+2;(4)

i нечетное:

25

Cj ( Bi + Bi+i bi)jSi 82 + +{bi bi-1 bi-2 Bj-2) -SiS2 + +81+1 bi bi+1 Si 82 + Ьь-2 bi bi+i bi+2, ( 5)

Изобретение относится к вычислительной технике и может быть использовано в специализированных ЭВМ для контроля и исправления ошибок в системах передачи данных, использующих коды Фибоначчи. Цель изобретения - расширение области применения за счет возможности исправления одиночных ошибок в 2-коде Фибоначчи с дублированием единиц. Устройство содержит группу триггеров 1, первую группу элементов И 2, вторую группу элементов И 3, третью группу элементов И 4 и четвертую группу элементов И 5, два блока 6.1 и 6.2 свертки по модулю два, дешифратор 7, блок 8 коррекции ошибок, группу элементов ИЛИ 9, элемент ИЛИ 13 с соответствующими связями. Обнаруживаются все одиночные и двойные ошибки и исправляются все одиночные ошибки. 1 з.п. ф-лы, 2 ил.

где Bi ai + ai+i.

При единичной ошибке в коде 2 - ФОЕ могут возникнуть следующие ситуации: 010 - пропадание или появление 1, 111 - появление 1 и ситуация 11111 - появление 1 в среднем разряде, которую можно сразу исправить, преинвестировав средний единичный разряд. Умножение на полином 1 + позволяет обнаружить и локализовать ошибку до группы из трех разрядов. Чтобы локализовать ошибку в группе, необходимо дополнительно выполнить контроль по четности, выделяя два контрольных разряда Ki и Кг. Они несут информацию о четности, выделяя два контрольных разряда, соответственно в нечетных и четных разрядах первоначального кодового слова минимальной формы.

-S.

321- 1:

i 1

К2 Ј a2i; .

i 1

При возникновении ошибки один из этих разрядов нарушен, что приведет к ненулевому синдрому. Синдром определяется по формуле

0

Если одна из корректирующих функций С| имеет единичное значение, что свиде- п тельствует о наличии ошибки, то сложение его с соответствующим значением разряда Bi по модулю два позволяет исправить эту ошибку. В этом заключается суть процедуры исправления ошибок.

с Триггеры 1.1-1.7 предназначены для записи исходного кода.

Элементы И 2.1-2.5 предназначены для получения минимальной формы.

Шесть элементов И группы 3.1-3.6 позволяет выделить из кодового слова группы типа 010, свидетельствующих о наличии ошибки.

Элементы И 4.1-4.4 группы предназначены для выделения трехразрядной кодовой ц группы 111, а элементы 5.1 и 5.2 позволяют выделить пятиразрядную группу 11111.

Блоки 6.1 и 6.2 свертки по модулю два позволяют определить значение синдрома Si 82 согласно (2).

Блок 8 коррекции ошибок и группа элементов ИЛИ 9.1-9.6 предназначены для получения контрольных значений каждого информационного разряда согласно формулам (4) и (5).

Элемент ИЛИ-13 предназначен для вы0

5

деления ненулевого значения одного из контрольных разрядов. Единичный сигнал на его выходе означает наличие ошибки в контролируемом коде.

На входы 10,8 и 10.9 подаются значения контрольных разрядов Ki и «2.

Вход 11 сброса необходим для установки в нулевое состояние триггеров 1.1-1.7.

Устройство (фиг.1) работает следующим образом.

Пусть на информационный вход устройства поступает комбинация 1100110 (соответствующая коду 1001000 М-формы) с ошибкой в четвертом разряде. На входы 10.8 и 10.9 поступают единичные контрольные разряды Ki и Ка. Тогда на выходах элементов И 2.1-2,5 получают комбинацию 10000 (два младших охранных нулевых разряда М-формы не формируются).

Значение синдрома на выходах блоков 6.1 и 6.2 свертки будет 01. Выходы всех элементов И 4.1-4.4, 5.1-5.2, 3.1-3.6, кроме 3.3, будут нулевые. На выходе дешифратора 7 присутствует код 010. На выходы 15.3 и 16.2 блока 8 коррекции ошибок поступают единичные сигналы. Сигнал 1 будет на выходе элементов ИЛИ 19.1, И 18.3, на третьем выходе блока 8 коррекции ошибок и на выходе элемента ИЛИ 9.3. Этот единичный сигнал, поступая на счетный вход триггера 1.4, устанавливает его в единичное состояние, тем самым исправляя ошибку.

При поступлении на информационный вход устройства кодовой комбинации 11 Г 100, соответствующей коду 1001000 М-формы, с ошибкой в пятом разряде, на выходах элементов И 2.1-2.5 устанавливается комбинация 11110.

Выходы элементов И 4.1-4.4 группы будут единичные, кроме первого. Сигнал 1 устанавливается на выходе элемента И 5.2 группы и на выходе элемента ИЛИ 9.4 группы. Этот единичный сигнал с выхода элемента ИЛИ 9.4 группы, поступая на счетный вход триггера 1,5, устанавливает его в правильное нулевое состояние.

Пусть на информационный вход устройства поступает кодовая комбинация 1101110 с ошибкой во втором разряде(соот- ветствующая правильному коду М-формы будет 1001000), поэтому контрольные разряды Ki и Ка, поступающие на входы ТО.8 и 10.9 являются единичными. На выходах элементов И 2.1-2.5 присутствует комбинация 10011. При этом значение синдрома на выходах блоков 6.1 и 6.2 свертки по модулю два будет 10. Все выходы элементов И-3.1-3.6, 4.1-4.4, 5.1, 5.2, кроме 4.1, нулевые. На выходе дешифратора 7 имеется код 100. На входы 14.1 и 16.3 блока 8 коррекции ошибок поступают единичные сигналы. Сигнал 1. устанавливается на выходах элементов ИЛИ 19.1 и И 18.2 (на восьмом выходе блока 8 коррекции ошибок) и на выходе элемента ИЛИ 9.1. Этот единичный сигнал поступает на счетный вход триггера 1.2 и устанавливает его в нулевое

5 состояние.

Возникновение ошибки в одном из контрольных разрядов не сказывается на изменении информационных разрядов, поскольку все входы, кроме 16.1. 16.2 или

0 16.3, и все выходы блока 8 коррекции ошибок и элементов И 5.1 и 5.2 группы будут нулевыми. А следовательно, выходы элементов ИЛИ 9.1-9.6 тоже устанавливаются нулевыми, что не меняет состояния тригге5 ров 1.2-1.7.

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

0 (при этом четвертая группа элементов И вырабатывает сигналы обнаружения многократных неисправимых ошибок и в коррекции не участвует).

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

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

5 с выходом элемента ИЛИ, прямой выход (i+2)-ro (i 1-n-2, n - разрядность кода) триггера группы соединен с первым входом 1-го элемента И первой группы, вход сброса устройства соединен с входами установки в

0 О триггеров регистра, отличающее- с я тем, что, с целью расширения области применения за счет возможности исправления одиночных ошибок в 2-коде Фибоначчи с дублированием единиц, оно

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

5 К-го (К 1-п-1) элемента И второй группы соединены соответственно с инверсным выходом К-го, с прямым выходом (К+1)-го и с инверсным выходом (Кь2)-го триггеров группы, первый и второй входы М-го (М 1-п-3)элемента И третьей группы соедийены соответственно с выходами М-ro и (М+1}-го элементов И первой группы, первый и второй входы 1-го (I 1 -п-5) элемента И четвертой группы соединены соответственно с выходами 1-го, (1+2)-го элементов И третьей группы, выходы нечетных и четных элементов И первой группы соединены соответственно с младшими входами первого и второго блоков свертки по модулю два, старшие входы которых соединены соответственно с входами нечетного и четного контрольных разрядов устройства, выходы первого и второго блоков свертки по модулю два соединены соответственно с входами дешифратора, выходы которого соединены с входами соответствующих разрядов управляющего входа блока коррекции ошибок, входы разрядов первого и второго информационных входов которого соединены соответственно с выходами элементов И третьей и второй групп, К-й выход блока коррекции ошибок соединен с первым входом К-го элемента ИЛИ группы, второй вход i-ro элемента ИЛИ группы соединен с (п-1+21)-м выходом блока коррекции ошибок, (Зп-б)-й выход которого соединен с вторым входом (п-1)-го элемента ИЛИ группы, третий вход 1-го, кроме первого, элемента ИЛИ группы, соединен с (п+2) ()-2)-м выходом блока коррекции ошибок, выход 1-го элемента И четвертой группы соединен с четвертым входом (1+2)-го элемента ИЛИ группы, прямой выход первого триггера группы и выходы элементов ИЛИ группы соединены соответственно со счетными входами триггеров группы, выходы

элементов ИЛИ соединены с соответствующими входами элемента ИЛИ.

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

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

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

ошибок соединен с первыми входами (2Р- 1)-го и 2Р-го (Р-нечетное) элементов И второй группы, выход М-го элемента ИЛИ группы соединен с вторыми входами 2М-го и (2М + 1)-го элементов И второй группы,

первые входы первого и (п-1)-го элементов И первой группы соединены соответственно с вторыми входами первого и (2п-4)-го элементов И второй группы, второй вход М-го элемента ИЛИ группы соединен с первым входом (М41)-го элемента И первой группы.