Математика/2. Перспективы систем информатики

Старший научный сотрудник Борисов К. Ю.,

д. т. н., профессор Павлов А.А.,

младший научный сотрудник Павлов П.А.,

Заслуженный деятель науки РФ, д. т. н., профессор Царьков А.Н.,

к.т.н., старший научный сотрудник Хоруженко О.В.

Межрегиональное общественное учреждение «Институт инженерной физики», Россия

Метод коррекции байтовых ошибок с аддитивным формированием вектора ошибки

Предлагается метод построения корректирующего кода, исправляющего одиночные байты ошибок (под байтом ошибки понимаются ошибки, кратность которых не превышает число разрядов b блока информации), реализующего линейную процедуру построения кода с синдромным декодированием.

Для получения кодового расстояния, позволяющего обеспечить исправление байтовых ошибок кратности b в двоичном наборе, содержащем k=b2^b информационных символов, используем r=b+log₂(b2^b) контрольных разрядов. Обозначим вторую часть контрольных разрядов буквой q= log₂(b2^b).

Для каждого блока информации выберем свою совокупность проверок, используя 2^b матриц кодирования информации размерности b x q.

Каждой матрице присвоим свой номер, равномерно выбирая значения чисел из множества {0, 1, 2 ....... b2^b}. Номер матрицы формируется проверкой на четность строк сформированных матриц. Например, для b=3 имеем восемь матриц, для которых выбраны номера: 0, 1,2,3, 6,12, 13, 21:

№ 13 №2 № 3 №6

011 0 110 0 101 0 000 0

Х = 111 1 Z= 000 0 A= 000 0 C= 101 0

001 1 011 0 100 0 111 1

000 0 001 1 111 1 010 1

001 1 011 0 010 1 011 0

№1 №12 №0 №12

000 0 000 0 000 0 001 1

E= 110 0 F= 100 1 G= 000 0 H= 110 0

000 0 111 1 000 0 100 1

011 0 110 0 000 0 011 0

100 1 101 0 000 0 111 1

Значения контрольных разрядов формируются сложением по mod2 элементов строк матриц, имеющих единичные значения, которые затем объединяются по mod2.

Для рассматриваемого примера значения второй части контрольных разрядов формируется проверками:

r₁^g= х₂Åх₃ Å z₁Å z₂ Åa₁Åa₃Åh₃; r₂^g= х₁Åх₂Åх₃ Åc₁Åc₃ Å e₁Åe₂ Åf₁ Å h₁Å h₂;

r₃^g= х₃ Åz₂Åz₃ Åa₁ Åc₁Åc₂Åc₃ Åf₁ Åf₂Åf₃Åh₁; r₄^g= z₃ Åa₁ Åa₂Åa₃Åс₂ Åe₂Åe₃ Åf₁Åf₂Åh₂ Åh₃; r₅^g= х₃ Åz₂Åz₃ Åa₂ Åc₂ Åc₃ Åe₃ Åf₁Åf₃Åh₁Åh₂Åh₃.

В общем случае при кодировании информации предлагаемым методом формируется кодовый набор:

Y_K=х₁ х₂.... х_b, у₁ у₂…. у_b,………, z₁ z_z…. z_b х₁ х₂.... х_b1 r₁¹ r₂¹…….. r_q¹

у₁ у₂…. у_b2 r₁² r₂²…….. r_q²

Å ………………………………..

z₁ z_z…. z_bw r₁^w r₂^w…….. r_q^w

r₁^f r₂^f… r_b^f r₁^g r₂^g…….. r_q^g ,

Результат сложения по mod2 переданных значений контрольных разрядов r_i^f , r_i^g и контрольных разрядов r_i^fП , r_i^gП, сформированных относительно полученных информационных разрядов даст значение синдрома ошибки, включающего две части:

S= s₁⁰ s₂⁰… …….s_b⁰ s₁¹ s₂¹… …..s_q¹ .

S^f S^g

Первая часть синдрома ошибки-S^f определяет вектор ошибки (ошибочные разряды в блоке информации), а значение второй части синдрома ошибки S^g определяет номер ошибочного блока (байта) информации.

Стратегия декодирования заключается на следующих положениях:

1. S^f =0; S^g=0. Ошибок нет;

2. S^f =0; S^g ¹0. Произошла ошибка в контрольных разрядах или не корректируемая ошибка в двух байтах информации;

3. S^f ¹0; S^g ¹0 (S^g =0). Произошла ошибка в информационных байтах (в одном байте- корректируемая, в двух- обнаруживаемая).

В табл.1 представлены значения синдромов ошибок для рассматриваемого примера.

Таблица 1 -Значения синдромов для кода (24,8)

Значение первой части синдрома ошибок	Значения проверок второй части синдрома ошибок
	X	Z	A	C	E	F	G	H
100 010 001 110 101 011 111	01000 11000 10101 10000 11101 01101 00101	10000 10101 00111 00101 10111 00010 00010	10110 00011 10010 10101 00100 10001 00111	01100 00111 01101 01011 00001 01010 00110	01001 01110 00010 00011 01011 01000 00001	01111 00110 00101 01001 01010 00011 01100	00000 00000 00000 00000 00000 00000 00000	01101 01011 10011 00110 11110 11000 10101

Литература:

1. Щербаков Н.С. Достоверность работы цифровых устройств. М: Машиностроение, 1989.