Теория передачи сигналов (2 часть)

Классификация помехоустойчивых корректирующих кодов

Разделимые коды состоят из двух частей: ин-

формационной и проверочной. Их символы всегда занимают одни и те же позиции. Разделимые коды получили условное обозначение - (n,k) коды.

В

неразделимых

кодах

деление

на

информационные и проверочные символы отсутствует. К

таким кодам относятся, в частности, коды с постоянным

весом, так называемые равновесные коды.

61

Классификация помехоустойчивых корректирующих кодов

Коды называются систематическими, если про-

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

информационными. Кроме того, любая разрешённая

кодовая комбинация может быть получена в результате

линейной операции над набором кодовых комбинаций.

62

Классификация помехоустойчивых корректирующих кодов

Коды называются несистематическими, если про-

верочные символы не образуются с помощью линейных

операций над информационными.

Информационные символы				Проверочные
				символы		Пример
0	0	0	0		0	несистематического кода
						Бергера
0	0	1	0		1
0	1	1	1		0
1	1	1	1		1

Проверочные символы содержат число единиц в информационной части кода

63

Код с проверкой на чётность

В таком коде к кодовым комбинациям безызбыточного первичного двоичного k-разрядного кода

добавляется один дополнительный разряд (символ проверки на чётность, называемый проверочным, или контрольным). Если число символов 1 исходной кодовой комбинации чётное, то в дополнительном разряде

формируют контрольный символ 0, а если число символов

1 нечётное, то в дополнительном разряде формируют

символ 1. В результате общее число символов 1 в любой

передаваемой кодовой комбинации всегда будет чётным.

64

Код с проверкой на чётность

Структурная схема кодирующего устройства

Информационные

символы

i1

i2

i3

i4

i1
i2
i3	Код
	с проверкой
	на чётность
i4
r1

r1= i1 i2 i3 i4

Минимальное кодовое расстояние равно двум (dmin = 2), и, следовательно, ошибки не

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

только для обнаружения ошибок.

65

Код с проверкой на чётность

Структурная схема декодирующего устройства

Код с проверкой на чётность

i1 i2 i3 i4 r1

	&			i1
	&			i2		Информационные
						символы
	&			i3
	&			i4
		S= i1	i2	i3	i4	r1
		S=0 – ошибки нет
	Формирователь
	запроса на	S=1 – присутствует ошибка
Обратный канал	повторную
	передачу

Критерием правильности принятой комбинации является равенство нулю результата S

суммирования по mod 2 всех n символов кода, включая проверочный символ r1.	66

Корректирующие коды Хэмминга

Проверочные разряды в кодах Хэмминга формируются с помощью

линейных операций над информационными разрядами. Увеличивая число

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

свойства кода так, чтобы он позволял не только обнаруживать, но и исправлять

ошибки.

Для каждого числа проверочных символов r = 3, 4, 5… существует

классический код Хэмминга с маркировкой:

(n, k)=(2r-1, 2r-1-r),

т. е. (7,4), (15,11), (31,26) …

67

Код Хэмминга (7, 4)

Информационные символы (i1, i2, i3, i4) дополним тремя проверочными символами.

Значения проверочных символов r необходимо увязать со значениями информационных символов i тремя функциями :

r1=f (i1, i2, i3, i4) r2=f (i1, i2, i3, i4) r3=f (i1, i2, i3, i4),

чтобы в последующем с помощью трёх других функций

s1=f (i1, i2, i3, i4, r1, r2, r3) s2=f (i1, i2, i3, i4, r1, r2, r3) s3=f (i1, i2, i3, i4, r1, r2, r3)

определить значения s1, s2, s3 содержащие информацию о том, произошла ли ошибка вообще и если да, то, в каком именно из семи символов. В случае же, когда ошибка не имела места, набор s1s2s3 должен указать на нулевую позицию, т.е. на несуществующий символ i0.

68

Код Хэмминга (7, 4)

Трёхсимвольная последовательность (s1,s2,s3) называется синдромом. Синдром S=(s1,s2,s3) представляет собой сочетание результатов проверки на чётность соответствующих символов кодовой группы и характеризует определённую конфигурацию ошибок (вектор ошибки).

Число возможных синдромов определяется выражением

S = 2r.

При числе проверочных символов r = 3 имеется восемь возможных синдромов (23 = 8). Нулевой синдром (000) указывает на то, что ошибки при приёме отсутствуют или не обнаружены.

69

Код Хэмминга (7, 4)

Из двоичной записи позиций

	s3s2s1			s3s2s1
	000 → (0)		i4	100	→ (4)
i1	001 → (1)		r1	101 → (5)
i2	010	→ (2)	r2	110	→ (6)
i3	011	→ (3)	r3	111 → (7)

видно, что значение s1 "несёт ответственность" за позиции i1, i3, r1 и r3 и поэтому в качестве s1 берётся зависимость

s1 = i1 i3 r1 r3.

Аналогично, значения s2 и s3 отвечают соответственно за i2, i3, r2, r3

и i4, r1, r2, r3, получим

s2= i2 i3 r2 r3, s3= i4 r1 r2 r3.

70