5.2.1 Обнаружение однократной ошибки

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

Код однократной ошибки представляет полином вида, где. Код ошибки суммируется по модулю два с одним из символовn-разрядной кодовой комбинации:

. (5.17)

Среди всех неприводимых полиномов полином видаобладает наименьшей степенью. Двоичный код, соответствующий этому полиному, записывается как 11. При делении любого полинома степенина полиномимеется единственный остаток, равный «0» или «1». Остаток, равный «1» - это признак ошибки в кодовой комбинации, и это свойство легло в основу создания и обнаружения однократной ошибки.

Образование кода. Положим- код, проверочный символ которогонеизвестен. Разделим кодовую комбинациюна код 11 неприводимого полинома. В результате деления получится остаток. Проверочный символзаменяется остатком.

	1	0	0	0		1		1
	1	1				1		1
	0	1	0
		1	1
		0	1	0
			1	1
Оста- ток			0	1
Рис. 5.7 Процедура обнаружения однократной ошибки

	1	0	1		1	1
	1	1			1	1
	0	1	1
		1	1
		00
Рис. 5.6 Процедура определение значения символа .

Например, пусть кодовая комбинация 101 представляет информационные символы. На рисунке 5.6 представлена процедура определения значения символа. Последняя строка на этом рисунке – остаток, равный нулю, поэтому символ=0.

На рисунке 5.7 представлена процедура обнаружения однократной ошибки. Ошибка в коде обозначена жирным шрифтом. В результате деления кода с ошибкой на неприводимый полином образовался остаток, равный «1» - признак ошибки.

5.2.2 Исправление однократной ошибки

Исправление одиночной ошибки связано с определением разряда, в котором произошла ошибка. Это производится на основании анализа остатков от деления многочленов ошибок на неприводимый полином. Каждому остатку соответствует один из разрядов кодовой комбинации, в которой произошла ошибка. Чем больше остатков, тем больше ошибок можно исправить. Наибольшее число остатков дает неприводимый полином, так как он не содержит ни одного сомножителя кроме самого себя.

Боузом и Чоудхури доказано[20], что существует циклический код разрядности

, (5.18)

где m= 1, 2, 3, …,

с кодовым расстоянием

. (5.19)

При этом число проверочных символов удовлетворяет соотношению

. (5.20)

Питерсеном [Коды, исправляющие ошибки] доказано, что полином вида

(5.21)

может быть представлен в виде произведения неприводимых многочленов, степени которых являются делителями числа mот 1 доmвключительно [Березюк].

Соотношение между числом исправляемых ошибок s, числом информационных символов и числом проверочных символов регулируется формулой (5.6).

В таблице 5.4 приведены значения числа символов nв кодовой последовательности в зависимости от величиныm,обеспечивающие кодовое расстояниеd=3

Таблица 5.4
m	2	3	4		5	…
n	3	7	15		31	…
r	2	3	4		5	…
k	1	4	11		26	…

при исправлении одиночной ошибки. Для значенийn= 3, 7, 15 по формуле (5.21) получены множества неприводимых многочленов

,

,

.

Не каждый многочлен даёт необходимое число остатков. Например, при исправлении однократной ошибки в 15-разрядном коде необходимо 15 остатков , полученных от деления кода ошибки на неприводимый полином. Однако, если выбран полином будет всего шесть остатков. В то же время полиномдаёт 15 остатков. Двоичное значение полинома11001.

Образование циклического кода.n-разрядная кодовая комбинация имеет вид,. Положим, определеныk,rиn. Тогда известны неприводимый многочлени многочлен, соответствующийk-разрядной комбинации информационных символов. Необходимо определить проверочные символы. Один из методов образования кода заключается в следующем.

Многочлен умножается на. Это соответствует приписываниюrнулей справа в кодовой последовательности. Произведениеделится на неприводимый полиноми получается- разрядный остаток. Все символыв кодовой последовательностизамещаются символами остатка. В результате имеем многочлен

.

Полученный многочлен делится без остатка на неприводимый многочлен. Действительно,

,

где частное от деления, остаток отсутствует.

Если в одном из разрядов символ изменил своё значение, остаток от деления не равен нулю. Каждому ошибочному символу в кодовой комбинациисоответствует свой остаток (синдром).

Пусть n= 7,k= 4,r= 3. Выберем полином1011, который дает 7 остатков. Положим,. Неизвестными являются проверочные символы.

Определим полиномы и соответствующие им коды 1110000,1011. Остаток от деления полиномана полиномравен100.

Заменим нули проверочной части кода 1110000 кодом остатка и получим закодированную кодовую комбинацию 1110100, которому соответствует полином вида . Разделив полиномна полином, получим полином000.

Исправление однократной ошибки. Для исправления однократных ошибок определим коды ошибок, соответствующие каждому разряду кодовой комбинации. Заменяя исправный символ в коде 1110100 ошибочным и деля полученный код на код неприводимого многочлена, получим код ошибки (синдром) для соответствующего разряда. В результате получится таблица 5.5. Если искажён символ, скажем, то после деления кода с искажённым символом на код неприводимого многочлена получим синдром 011, что позволит инвертировать символ.

Таблица 5.5
Код сообщения
Синдром S	101	111	110	011	100	010	001

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

Считается, множество кодов, составляющие разрешённые комбинации , образовано с помощью выбранного неприводимого полинома и он остается неизменным во время исправления однократной ошибки. В зафиксированной кодовой комбинации содержится однократная ошибка.При делении зафиксированной кодовой комбинации на код образующего полинома получается остаток. Если все разряды кода не искажены, остаток равен нулю. Искажение одного из символов приводит к остатку, отличного от нуля. Анализ остатка позволяет определить искажённый символ. Ввиду того, что ошибка однократная и надо найти разряд, в котором произошла ошибка, то вес остаткадолжен быть равен единице. Чтобы проверить каждый разряд кода на наличие ошибки производится поэтапно циклический сдвиг влево на один разряд кодовой комбинации. На каждом этапе осуществляется деление сдвинутого кода на неприводимый полином и определяется вес остатка. Процедура циклических сдвигов останавливается, если вес остатка=1. Этот остаток служит индикатором того, что последний разряд в сдвинутом коде ошибочный и его надо инвертировать. Инвертирование достигается суммированием по модулю 2 сдвинутого кода с кодом остатка.

Чтобы восстановить неискажённую кодовую комбинацию производятся циклические сдвиги вправо столько раз, сколько производились циклические сдвиги влево.

Пример 5.6 Пустьn= 7,k= 4,r= 3. Выберем полином

1011, который дает 7 остатков. Выберем из множества разрешённых кодовых комбинаций код 1110100 и внесём ошибку в 4-ый разряд 1111100. На рисунке 5.8 показана процедура определения искажённого символа. Разделив кодовую комбинацию с ошибкой на неприводимый полином, убедимся, что вес остаткаw

Сдвига нет
	1111100	1011
	1011	1101
	1001
	1011
	1000
	1011
	11
	w> 1	а
1-ый сдвиг влево
	1111001	1011
	1011	1101
	1000
	1011
	1101
	1011
	110
	w> 1	б

а б в

3-ий сдвиг влево
	1100111	1011
	1011	111
	1111
	1011
	1001
	1011
	101
	w> 1

2-ой сдвиг влево
	1110011		1011
	1011		110
	1010
	1011
	111
	w> 1		в
4-ый сдвиг влево
	1001111	1011
	1011	101
	1011
	1011
	1
	w= 1	д

г д е

Рис. 5.8 Процедура определения искажённого символа

Исправление ошибки
	1001111
	1
	1001110

больше 1, рисунок 5.8 а. На рисунках 5.8 б, 5.8 в, 5.8 г показаны процедуры циклического сдвига и получения остатков, больших единицы. На рисунке 5.8.д демонстрируется, после очередного циклического сдвига и деления полученного кода на неприводимый полином остаток равен единице, следовательно вес остатка w=1. Это значит последний сдвинутый символ ошибочный. Чтобы исправить ошибочный символ, последнюю кодовую комбинацию сложим по модулю 2 с остатком, рисунок 5.8.е. Произведя последовательно 4 раза циклический перенос вправо кодовой комбинации с исправленным символом, получим безошибочную кодовую комбинацию:

1001110  0100111, 1010011, 1101001,1110100.

Оглавление