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

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

В матричном виде можно записать:

								i
									1
									i
									2
	s				1010101		i
		1							3
		s		=		0110011			i
		2							4
		s				0001111			r
		3							1
								r
									2
									r
									3

или Vs=D∙B(7,4),

где Vs, - вектор ошибки, указывающий на её месторасположение; D -

матрица, столбцы которой двоичные записи чисел от одного до семи,

B(7,4) – матрица кода Хэмминга.

71

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

Подставляя в систему уравнении s1=s2=s3=0, получим систему из трёх уравнений

i1 i3 r1 r3=0 i2 i3 r2 r3=0 i4 r1 r2 r3=0,

Приняв в качестве неизвестных величины r1, r2 и r3 получим систему из трёх уравнений с тремя неизвестными:

	r1 r3= i1 i3,	101				r1				1010				i1
	r2 r3= i2 i3		011				r2		=		0110			i2
														i
	r1 r2 r3= i4.	111				r					0001				3
							3
														i4

C∙R=I∙K, где R и K, вектор-столбцы, координаты которых представлены соответственно контрольными и информационными разрядами; С и I - так называемые проверочная и

информационная матрицы.

72

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

Решение системы относительно r1, r2, r3 приводит к выражениям для функций :

r1= i2 i3 i4, r2= i1 i3 i4, r3= i1 i2 i4.

73

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

символы

i1

i2

i3

i4

Кодер для кода Хэмминга (7,4)

r1= i2 i3 i4

r2= i1 i3 i4

r3= i1 i2 i4

i1

i2

i3

i4

r1

r2

r3

Код

Хэмминга

74

Код

Хэмминга

Декодер для кода Хэмминга (7,4)

	i1		i1
	i2		i2
	i3		i3
	i4		i4
		s = i’1 i’3 r’1 r’3
	r1		Дешифратор
			синдрома ошибок
			S1,S2,S3
	r2		2= i’2 i’3 r’2 r’3

r3

s3= i’4 r’1 r’2 r’3

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

символы

75

Декодер для кода Хэмминга (7,4)

Таблица работы дешифратора синдрома ошибки

Синдром
(Признак	001	010	011	100	101	110	111
ошибки)
Позиция
ошибочного
разряда	1000000	0100000	0010000	0001000	0000100	0000010	0000001
(Вектор
ошибки)
Ошибка	i1	i2	i3	i4	r1	r2	r3
в символе

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

кодовой комбинации.	000 → (0)		100 → (4)
	001	→ (1)	101 → (5)
	010 → (2)		110 → (6)
	011	→ (3)	111 → (7)

76

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

В этом случае, кроме рассмотренной проверки по контрольным

позициям (r1 – r3), следует провести ещё одну проверку на чётность для всей строки в целом. Чтобы осуществить такую проверку, к каждой

строке кода добавляют контрольный символ r4:

i1, i2, i3, i4, r1, r2, r3, r4,

где r4= i1 i2 i3 i4 r1 r2 r3.

Тогда в случае одной ошибки, проверки по символам (r1 – r3)

укажут номер ошибочной позиции, а проверка на чётность (r4) – на наличие ошибки в целом. Если проверки по символам укажут на наличие ошибки, а проверка на чётность не фиксирует её, значит в кодовой комбинации две ошибки.

77

Циклические коды (CRC, Cyclic Redundancy Check)

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

Математически n-разрядную кодовую комбинацию

записывают в виде многочлена n-1 степени с переменной x.

Пусть задана кодовая комбинация 1011001. Она

может быть записана в виде многочлена:

1x6+0x5+1x4+1x3+0x2+0x+1=x6+x4+ x3+1.

78

Циклические коды

Циклический код может быть получен с помощью образующего многочлена

G(x) степени (n–k), который является сомножителем в разложении двучлена

xn+1 на неприводимые многочлены. Для кода (7, 4) образующий многочлен

степени n-k может быть, например, x3+x+1. Проверим, как делится на него

многочлен x7 +1.

7			+1
x
7			5		+x		4
x		+x
5			4		+1
x		+x
5			3	+x		2
x	+x

3	+x+1			Можно записать (x7+1)=(x3+x+1)(x4+x2+x+1)
x
4		2	+x+1	x7 x5 x4 x3 x5 x3 x2 x4 x2 x 1= x7+1
x		+x
			- знак суммы по модулю два

4		3			2	+1
x		+x		+x
4		2	+x
x	+x
				3	+x+1
		x
				3	+x+1
		x

0

Т. о. данный многочлен для кода 7,4

является образующим.

– остаток R(x) отсутствует

Образующие многочлены приведены в специальных таблицах.

79

Построение неразделимого циклического кода с

помощью образующей матрицы

Рассмотрим код (n, k) (7,4). Образующая матрица должна содержать k строк и n столбцов. Первая строка состоит из образующего многочлена, дополненного до n нулями. Остальные строки образуются циклической перестановкой последнего члена предыдущей строки на место первого. Учитывая, что приписывание нуля к многочлену эквивалентно умножению его на x, получим матрицу:

	( 3+ + 1)000		( 3+ + 1)	∙ 3		6 + 4	+ 3
=	0( 3+ + 1)00	=	( 3+ + 1)	∙ 2	=	5 + 3	+ 2
	00( 3+ + 1)0		( 3+ + 1) ∙			4 + 2 +
	000( 3+ + 1)		( 3+ + 1)			3 + + 1

80