Кодирование информации

Обнаружение и исправление ошибок в коде Хэмминга

Пример 2.2. Предположим, в канале связи под действием помех произошло искажение и вместо 0100101 было принято 0100111.

Решение: Для обнаружения ошибки производят уже знакомые нам проверки на четность.

Первая проверка: сумма П1+П3+П5+П7 = 0+0+1+1 четна. В младший разряд номера ошибочной позиции запишем 0.

Вторая проверка: сумма П2+П3+П6+П7 = 1+0+1+1 нечетна. Во второй разряд номера ошибочной позиции запишем 1.

Третья проверка: сумма П4+П5+П6+П7 = 0+1+1+1 нечетна. В третий разряд номера ошибочной позиции запишем 1. Номер ошибочной позиции 110 = 6. Следовательно, символ шестой позиции следует изменить на обратный, и получим правильную кодовую комбинацию.

Табл. 2.4 Код, исправляющий одиночную и обнаруживающий

двойную ошибки

	Десятичное
	представле-				Позиция
	ние чисел на
	позициях 3,
	5, 6 и 7
		1	2	3	4	5	6	7		8
	0	0	0	0	0	0	0	0		0
	1	1	1	0	1	0	0	1		0
	2	0	1	0	1	0	1	0		1
	3	1	0	0	0	0	1	1		1
	4	1	0	0	1	1	0	0		1
	5	0	1	0	0	1	0	1		1
	6	1	1	0	0	1	1	0		0
	7	0	0	0	1	1	1	1		0
	8	1	1	I	0	0	0	0		1
	9	0	0	1	1	0	0		1		1
	10	1	0	1	1	0	1		0		0
	11	0	1	1	0	0	1	1		0
	12	0	1	1	1	1	0	0		0
	13	1	0	1	0	1	0	1		0
	14	0	0	1	0	1	1	0		1
	15	1	1	1	1	1	1	1		1

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

18

с исправлением одиночной ошибки и обнаружением двойной. Для этого, кроме указанных выше проверок по контрольным позициям, следует провести еще одну проверку на четность для всей строки в целом. Чтобы осуществить такую проверку, следует к каждой строке кода добавить контрольные символы, записанные в дополнительной колонке (табл. 2.4 колонка 8). Тогда в случае одной ошибки проверки по позициям укажут номер ошибочной позиции, а проверка на четность – на наличие ошибки. Если проверки позиций укажут на наличие ошибки, а проверка на четность не фиксирует ее, значит в кодовой комбинации две ошибки.

2.5. Групповой код.

Принцип формирования образующей матрицы

Групповые коды удобно задавать при помощи матриц, размерность которых определяется параметрами кода nи и nк. Число строк матрицы равно nи, число столбцов n = nи + nк:

	a11	a12	K	a1nи	P11	P12	K P1nк
C =	a21	a22	K a2 nи		P21	P22	K P2 nк	(2.7)
	K	K	K	K	K	K	K K
	anи1 anи 2		K anиnи		P Pnи1		K Pnиnк
Коды, порождаемые этими				матрицами, известны			как (n, k) –	коды,

где k = nи, а соответствующие им матрицы называют производящими,

порождающими, образующими.

Производящая матрица С может быть представлена при помощи двух матриц И и П (информационной и проверочной). Число столбцов матрицы П равно nк, число столбцов матрицы И – nи.

При соблюдении всех этих условий любую производящую матрицу группового кода можно привести к следующему виду:

a1 a2 a3 … an и P1 P2 … Pnи

1	0	0	K 0	P11	P12	K P1(n−nи )
0	1	0	K 0	P21	P22	K P2(n−nи )
С = 0	0	1	K 0	P31	P32	K	P3(n −nи )	,
			K			K

0 0 0 K 1 PK1 PK2 K PK(n−nи )

называемому левой канонической, или приведенной ступенчатой формой производящей матрицы.

Для кодов с d0 = 2 производящая матрица С имеет вид

19

																		И							П
				1	0	0	K 0	1								1	0	0	K 0								1
				0	1	0	K 0	1								0	1	0	K 0								1
С =				0	0	1	K 0	1				=				0	0	1	K 0								1
				K K K K K K												K K K K K
				0	0	0	K 1	1								0	0	0	K 1								1

Во всех комбинациях кода, построенного при помощи такой матрицы, четное число единиц.

Известны формулы, по которым определяется связь между n, nи и nк. В частности, если известно количество информационных разрядов nи, то nк

вычисляется по формуле:	[log2 {(nи +1)+[log2 (nи +1)]}].
nк =		(2.8)

Квадратные скобки означают округление полученного числа до целого.

Если известно количество разрядов в коде, т. е. n, то количество корректирующих разрядов равно:

n к =[log 2 (n+1)].

(2.9)

Пример 2.3. Построить матрицу для группового кода, способного исправлять одиночную ошибку при передаче 16 символов первичного алфавита.

Решение:

1. Так как число информационных разрядов кода nи = 4 (16 = 24 = 2nи), то число строк производящей матрицы С должно быть равно 4.

2. Число столбцов матрицы С равно n; n – длина кода, которая равна nи + nк, а число корректирующих разрядов для кодов с d0 = 3,

n к = log 2 {5 + [log 2 5]}= log 2 8 = 3 .

Следовательно, число столбцов, содержащих контрольные разряды, должно быть равно 3, а общее число столбцов матрицы С равно nи + nк = 4+3 = 7.

3. Так как вес каждой строки проверочной матрицы П должен быть

WП ≥d0 − WИ ,

то в качестве строк проверочной матрицы могут быть выбраны трехзначные двоичные комбинации с числом единиц, большим или равным двум (d0 = 3, a WИ=1, потому что матрицу информационных разрядов удобно выбирать единичную): 111; 110; 101; 011.

4. Окончательный вид производящей матрицы:

	1	0	0	0	1	1	1		1	0	0	0	1	1	1
С1 =	0	1	0	0	1	1	0	или С2 =	0	1	0	0	0	1	1
	0	0	1	0	1	0	1		0	0	1	0	1	1	0
	0	0	0	1	0	1	1		0	0	0	1	1	0	1

20

или

	1	0	0	0	0	1	1
С3 =	0	1	0	0	1	0	1
	0	0	1	0	1	1	0
	0	0	0	1	1	1	1

Как видно из примера, основным требованиям могут удовлетворять несколько матриц. Выбор той или иной матрицы из числа матриц, возможных для данных nи, nк и d0, определяется по дополнительным требованиям: минимум корректирующих разрядов или максимальная простота аппаратуры.

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

Решение:

1. 2nи ≥ 2000, n И =11, согласно (2.8), при nи=11 и d0=3,

nк =[log2 {(11+1)+[log2 (11+1)]}]= 4.

2. Проверим условие оптимальности кода. Условие оптимальности принимает вид

2n−nи −1 = n; 215−11 −1 =1; 15 =15. 3. Вес каждой комбинации проверочной матрицы П

Wп >d0 −1, Wп ≥ 2.

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

W ≥ 2.

5.Окончательный вид матрицы С:

	1	0	0	0	0	0	0	0	0	0	0	0	0	1	1
	0	1	0	0	0	0	0	0	0	0	0	0	1	0	1
	0	0	1	0	0	0	0	0	0	0	0	0	1	1	0
	0	0	0	1	0	0	0	0	0	0	0	0	1	1	1
	0	0	0	0	1	0	0	0	0	0	0	0	0	0	1
С =	0 0 0 0 0 1 0 0 0 0 0 1 0 1 0
	0	0	0	0	0	0	1	0	0	0	0	1	0	1	1
	0	0	0	0	0	0	0	1	0	0	0	1	1	0	0
	0	0	0	0	0	0	0	0	1	0	0	1	1	0	1
	0	0	0	0	0	0	0	0	0	1	0	1	1	1	0
	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1

21

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

Wn ≥d0 −1.

Пример 2.5. Источник сообщений рассчитан на передачу 120 различных 11-разрядных комбинаций. Одним из главных требований технического задания (ТЗ) на разработку приемного устройства является максимальная простота дешифратора и возможность коррекции одиночных ошибок в каждой передаваемой комбинации. Построить образующую матрицу группового кода, удовлетворяющую требованиям ТЗ.

Решение:

1. Задана длина кода n=11 и максимальное расстояние между кодами d0=3. Согласно (2.9),

n к =[log(11 +1)]= 4.

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

двоичные комбинации весом Wn=2, 3, 4 и используем те комбинации, в которых содержится меньшее число единиц, т. е.(0011,0100, 0110, 1010, 1100, 0111).

3.Искомая матрица имеет вид

	1	0	0	0	0	0	0	0	0	1	1
	0	1	0	0	0	0	0	0	1	0	1
	0	0	1	0	0	0	0	0	1	1	0
С =	0 0 0 1 0 0 0 1 0 0 1
	0	0	0	0	1	0	0	1	0	1	0
	0	0	0	0	0	1	0	1	1	0	0
	0	0	0	0	0	0	1	0	1	1	1

Метод кодирования при помощи образующей матрицы

Метод кодирования при помощи образующих матриц может быть представлен следующим образом.

Строки образующей матрицы С представляют собой n комбинаций искомого кода. Остальные комбинации кода строятся при помощи образующей матрицы по следующему правилу: корректирующие символы, предназначенные для обнаружения или исправления ошибки в информационной части кода, находятся путем суммирования по модулю 2 тех строк матрицы П, номера которых совпадают с номерами разрядов, содержащих единицы в кодовом

22

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

Алгоритм образования проверочных символов по известной информационной части кода может быть записан следующим образом:

P1 = P11α1 P21α2 L Pnи 1αnи ;

P2 = P12 α1 P22 α2 L Pnи 2 αnи ;

..................................................				(2.10)
Pnk	= P1nk α1 P2 nk α2		L Pnиnk αnи
		или	nи
P =P α P α				P α
		L P α = ∑
ij	1 j 1 2 j 2		nij nи i=1	ij i

Пример 2.6. Построить групповой код по заданной производящей матрице:

	1	0	0	0	1	1	1		1	0	0	0			1	1	1
C =	0	1	0	0	1	1	0	=	0	1	0	0			1	1	0
	0	0	1	0	1	0	1		0	0	1	0			1	0	1
	0	0	0	1	0	1	1		0	0	0	1			0	1	1

И П

Решение:

1. Число строк матрицы nи=4. Следовательно, число возможных информационных комбинаций

	N = 2nи = 24 = 16.
1) 0 0 0 0	5) 0 0 1 0	9) 0 0 0 1		13) 0 0 1 1
2) 1 0 0 0	6) 1 0 1 0	10)	1 1 0 0	14) 1 0 1 1
3) 0 1 0 0	7) 0 1 1 0	11)	0 1 0 1	15) 0 1 1 1
4) 1 1 0 0	8) 1 1 1 0	12)	1 1 0 1	16) 1 1 1 1

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

23

1) 0 0 0	2) 1 1 1	3) 1 1 0

5)1 0 1

9)1 0 1

3. Окончательно комбинации корректирующего кода имеют вид:

1) 0 0 0 0 0 0 0	5) 0 0 1 0 1 0 1	9) 0 0 0 1 0 1 1	13) 0 0 1 1 1 1 0
2) 1 0 0 0 1 1 1	6) 1 0 1 0 0 1 0	10) 1 0 0 1 1 0 0	14) 1 0 1 1 0 0 1
3) 0 1 0 0 1 1 0	7) 0 1 1 0 0 1 1	11) 0 0 0 1 1 1 0	15) 0 1 1 1 0 0 0
4) 1 1 0 0 0 0 1	8) 1 1 1 0 1 0 0	12) 1 0 0 1 1 0 0	16) 1 1 1 1 1 1 1

Коррекция ошибок в групповых кодах

Коррекции ошибок в линейных кодах связаны с выполнением проверок, идея которых в общем виде может быть представлена следующим образом:

	ni	P *a		=S, j=1,2,...,n	к.	(2.11)
P ∑			i
i	i=1	ij

Для каждой конкретной матрицы существует своя, одна-единственная система проверок. Проверки производятся по следующему правилу: в первую проверку вместе с проверочным разрядом Р1 входят информационные разряды, соответствующие единицам первого столбца проверочной матрицы П, во вторую – второй проверочный разряд Р2 и информационные разряды, соответствующие единицам второго столбца проверочной матрицы, и т. д. Число проверок равно числу проверочных разрядов корректирующего кода nк.

В результате проверок образуется проверочный вектор S1, S2,..., Sn – синдром. Если число единиц проверяемых разрядов четно, то значение соответствующего разряда синдрома равно нулю.

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

24

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

Вид синдрома для каждой конкретной матрицы может быть определен при помощи контрольной матрицы Н, которая представляет собой транспонированную матрицу П, дополненную единичной матрицей I, число столбцов которой равно числу проверочных разрядов кода. Первый столбец матрицы становится первой строкой транспонированной матрицы, второй столбец – второй строкой и т. д.

H =

ПТInк

(2.12)

Столбцы такой матрицы представляют собой значение синдрома для разряда, соответствующего номеру столбца матрицы H.

Пример 2.7. Групповой код построен по матрице

	1	0	0	0	0	1	1
С =	0	1	0	0	1	0	1
	0	0	1	0	1	1	0
	0	0	0	1	1	1	1

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

Решение:

1. Производящая матрица С в виде информационной матрицы И и проверочной матрицы П может быть представлена следующим образом:

	1	0	0	0	0	1	1		1	0	0			0	1	1
С =	0	1	0	0	1	0	1	=	0	1	0	0		1	0	1
	0	0	1	0	1	1	0		0	0	1	0		1	1	0
	0	0	0	1	1	1	1		0	0	0	1		1	1	1
										И					П

Согласно принципу построения системы проверки, система проверок для кодов, построенных по матрице С, будет иметь вид

P1 a 2 a 3 a 4 =S1 P2 a1 a 3 a 4 =S1 P3 a1 a 2 a 4 =S3

2. Чтобы знать, какая комбинация значений разрядов синдрома S1, S2, S3 будет соответствовать ошибке в определенном разряде принятой комбинации, строим контрольную матрицу Н, cтроками которой являются столбцы матрицы П, дополненные единичной транспонированной матрицей In, размерность которой определяется числом избыточных разрядов кода, т. е. в нашем случае равна 3. Таким образом,

25

a1 a2 a3 a4 P1 P2 P3

H =	0	1	1	1			1	0	0
	1	0	1	1			0	1	0
	1	1	0	1			0	0	1

ПТ In

Если разряды синдрома соответствуют первому столбцу матрицы Н, т. е. Sj=0, S2=1, S3=1, то ошибки в первом разряде принятой комбинации, если синдром имеет вид 101, что соответствует второму столбцу матрицы Н, то ошибка во втором разряде, синдром 001 соответствует ошибке в третьем проверочном разряде кода и т. д.

3. Так как информационная часть кода обычно представляет собой натуральный двоичный код разрядности nи то в качестве примера проверки корректирующих свойств кода используем информационные комбинации, соответствующие цифрам 3, 4 и 5 в четырехзначном двоичном коде3: 1100, 0010 и 1010. Значение корректирующих разрядов находим путем суммирования строк матрицы П, соответствующих единицам в информационных комбинациях:

P′= 011 101 =110; P′′ =110;

P′′′= 011 110 =101.

Полные комбинации кода имеют вид соответственно: 1 1 0 0 1 1 0; 0 0 1 0 1 1 0; 1 0 1 0 1 0 1.

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

0 1 0 0 1 1 0;

0 0 1 1 1 1 0;

1 0 1 0 1 0 0.

Находим проверочные векторы согласно системе проверок. Для первой комбинации Р' =110, т. е. Р1=1; Р2=1; Р3=0:

P1 a 2 a 3 a 4 =1 1 0 0 =0; P2 a1 a 3 a 4 =1 0 0 0 =1; P3 a1 a 2 a 4 =0 0 1 0 =1.

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

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

26

Для второй комбинации

1 0 1 1 =1;

1 0 1 1 =1;

0 0 0 1 =1.

Синдром 1 1 1 – ошибка в четвертом разряде.

Для третьей комбинации

1 0 1 0 = 0;

0 1 1 0 = 0;

0 1 0 0 =1.

Синдром 001 – ошибка в седьмом разряде.

2.6. Циклические коды. Идея построения циклических кодов

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

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

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

4 Множество элементов принадлежит к одному полю, если над ними можно производить операции сложения и умножения по правилам данного поля, при этом сложение и умножение должны подчиняться дистрибутивному закону: (а + b) с = ас + bc для всех а, b и с.

27