Синдром и обнаружение ошибок

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

Пусть U = (U₀ , U₁ ,… U_n ) является кодовым словом, переданным по каналу с помехами, а r = (r₀ , r₁ ,... r_n ) - принятой последовательностью, возможно, отличающейся от переданного кодового слова U. Отличие r от U состоит в том, что некоторые символы r_i принятой последовательности могут отличаться от соответствующих символов U_i переданного кодового слова. Например, U = (0 0 0 1 0 0 0), а r = (0 0 0 0 0 0 0), то есть произошла ошибка в четвертом символе кодового слова, 1 перешла в 0. Или другой пример: передано кодовое слово U = (0 0 1 1 1 1), а принятая последовательность имеет вид r = (1 0 1 1 1 1 1), то есть ошибка возникла в первом бите кодового слова, при этом 0 перешел в единицу.

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

Так, вектор ошибки e = (0 0 0 1 0 0 0) означает однократную ошибку в четвертой позиции (четвертом бите), вектор ошибки e = (1 1 0 0 0 0 0) - двойную ошибку в первом и втором битах и т.д.

Тогда при передаче кодового слова U по каналу с ошибками принятая последовательность r будет иметь вид

r = U + e, (3.21)

например: U = (0 0 0 1 0 0 0),

e = (0 0 0 1 0 0 0), (3.22)

r = (0 0 0 0 0 0 0).

Приняв вектор r, декодер сначала должен определить, имеются ли в принятой последовательности ошибки. Если ошибки есть, то он должен выполнить действия по их исправлению.

Чтобы проверить, является ли принятый вектор кодовым словом, декодер вычисляет (n-k)-последовательность, определяемую следующим образом:

S = (S₀ , S₁ , …, S_n-k-1) = r × H ^T. (3.23)

При этом r является кодовым словом тогда, и только тогда, когда S=(00..0), и не является кодовым словом данного кода, если S ¹ 0. Следовательно, S используется для обнаружения ошибок, ненулевое значение S служит признаком наличия ошибок в принятой последовательности. Поэтому вектор S называется синдромом принятого вектора r.

Некоторые сочетания ошибок, используя синдром, обнаружить невозможно. Например, если переданное кодовое слово U под влиянием помех превратилось в другое действительное кодовое слово V этого же кода, то синдром S = V * H ^T = 0. В этом случае декодер ошибки не обнаружит и, естественно, не попытается ее исправить.

Сочетания ошибок такого типа называются необнаруживаемыми. При построении кодов необходимо стремиться к тому, чтобы они обнаруживали наиболее вероятные сочетания ошибок.

Для рассматриваемого в качестве примера линейного блочного систематического (7,4)-кода Хемминга синдром определяется следующим образом:

пусть принят вектор r = (r₀ , r₁ , r₂ , r₃ , r₄ , r₅ , r₆), тогда

	1 0 1 1 1 0 0	^T
S= r* H (7,4)^T = (r0, r1, r2, r3, r4, r5, r6) *	1 1 1 0 0 1 0	=
	0 1 1 1 0 0 1

= (r₀ + r₂ + r₃ + r₄ ), (r₀ + r₁ + r₂ + r₅), (r₁ + r₂ + r₂ + r₆ ), (3.23)

или

S₀ = r₀ + r₂ + r₃ + r₄ ,
S₁ = r₀ + r₁ + r₂ + r₅ , (3.24)
S₂ = r₁ + r₂ + r₂ + r₆ .

Основываясь на полученных соотношениях, можно легко организовать схему для вычисления синдрома. Для (7,4)-кода Хемминга она приведена на рис. 3.5.

Рис. 3.5

Дата добавления: 2014-01-07