линейные коды-Чуканов

ФГБОУ ВПО Челябинский государственный университет

Чуканов Н.А.

Линейные коды Методическое пособие

Челябинск

2014

1

Составитель: кандидат физико-математических наук Н.А.Чуканов

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

2

Содержание

1	Введение		4
2	Линейные коды		5
	2.1	Построение линейного кода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	5
	2.2	Декодирование линейных кодов . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	8
	2.3	Основные определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	13

2.4Строение конечных полей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.5Примеры конечных полей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Циклические коды		19
3.1	Определение и свойства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	19
3.2	Порождающий многочлен . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	20
3.3	Кодирование циклических кодов . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	21
3.4	Проверочный многочлен . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	23
3.5	Декодирование циклического кода . . . . . . . . . . . . . . . . . . . . . . . . . . . .	25

3

1Введение

Âнастоящее время большое значение приобрели проблемы передачи информации и, в частности, вопросы кодирования и декодирования в целях ее надежной передачи по "защищенным"каналам. Обычно бывает необходимо передать сообщение, состоящее из конечной последовательности символов, являющихся элементами некоторого конечного алфавита. Если, например, этот алфавит состоит из символов 0 и 1, то передаваемое сообщение можно рассматривать как некоторое двоичное число. В общем случае предполагается, что алфавит является некоторым конечным полем. Передача конечной последовательности элементов алфавита по каналу связи не обязательно осуществляется в "точном"виде в том смысле, что каждый бит информации передается по каналу не изменяясь. Ввиду того, что не существует идеального канала без "шумов" , получатель передаваемого сообщения может получить искаженную информацию и ошибочно истолковать переданные сигналы.

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

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

4

2 Линейные коды

Определение. Алгебраическая система < F; +; > называется полем, если:

1.< F; +; > является коммутативной (абелевой) группой по сложению

2.< F=f0g; > является абелевой группой по умножению

3.выполняется закон дистрибутивности: для любых a; b; c 2 F справедливо

a(b + c) = ab + ac

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

Примеры. <Q; +; >; < R; +; >; < C; +; > - бесконечные поля.

Кольцо вычетов < Z; +; > целых чисел по модулю простого числа p. Далее такое поле будем называть простым и обозначать Fp.

Определение. Характеристикой поля F называется наименьшее целое положительное число p такое, что в поле F справедливо равенство:

1 + 1 + ::: + 1					= 0
|		{z		}
	p
		ðàç

Поскольку в поле нет делителей нуля, характеристика p всегда является простым числом. Если такого числа не существует, то говорят, что поле F имеет характеристику 0. Очевидно, что любое конечное поле имеет характеристику, отличную от 0.

2.1Построение линейного кода

Простая модель системы связи следующая:

Сообщение a

# f

Закодированное сообщение c

#

5

ными) символами.

Такая схема кодирования часто представляется в следующем виде.Пусть H - матрица размером (n k) n с элементами из Fq и имеющая вид

H = (AEn k)

Канал связи		øóì

#

Полученное сообщение c + e

# g

Декодированное сообщение a

Символы, составляющие исходное закодированное сообщение, являются элементами конеч-

íîãî ïîëÿ Fq.Кодирование обозначает, что блок из k символов передаваемого сообщения a1 a2 ::: ak,ai 2

Fq i = 1; k заменяется кодовым словом c1; c2; :::; cn n > k; ci 2 Fq; i = 1; n.

Мы будем рассматривать кодовое слово как n-мерную вектор-сторону c 2 Fqn

Таким образом, функция f из Fqk â Fqn называется схемой кодирования, а g : Fqn ! Fqk называется схемой декодирования.

Простая разновидность схемы кодирования имеет вид:

a = a1 a2 ::: ak ! a1 a2 ::: ak c1 c2 ::: cn k = c

где первые k символов совпадают с k символами исходного сообщения и называются информационными символами, а дополнительные n k символы называются проверочные (контроль-

где А - матрица размера (n k) k, а En k - единичная матрица порядка n k. Тогда проверочные символы определяются из системы линейных уравнений

Hct = 0

Уравнения данной системы называются проверочными уравнениями линейного кода.

Пример 1. Пусть H3 7 матрица над полем F2 следующего вида:

H =	0 1		1	0	1	0	1	0 1
	@	1	0	1	1	1	0	0	A
		1	1	1	0	0	0	1

n = 7; k = 4

Проверочные символы можно найти из системы уравнений Hct = 0 ãäå c = (a1 a2 a3 a4 c1 c2 c3).

6

8 a1	+ a2		+ a4		+ c2		= 0
a1	+	a3	+	a4	+	c1	=	0
< a1	+	a2	+	a3	+	c3	=	0;
:

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

	8 c2	= a1	+ a2			+ a4
	c1	= a1		+ a3		+ a4
	< c3 = a1		+ a2 + a3
Èòàê,	:
	a1 a2 a3 a4 ! a1 a2 a3 a4 c1 c2 c3
		f : F24 ! F27
a1 a2 a3 a4 ! a1 a2 a3 a4 (a1 + a2 + a4) (a1 + a2 + a4) (a1 + a2 + a3)
Например 0101 ! 0101001:
Определение. Пусть H -	n			Fq			(n k) t n		n k
	матрица над полем				размером			и ранга		. Множество

С всех n-мерных векторов c 2 Fq удовлетворяющих уравнению Hc = 0 называется линейным (n; k) кодом над полем Fq. Элементы множества С называются кодовыми словами (векторами). Число n называется длиной кода, k - размерностью кода. Матрица H называется проверочной матрицей линейного кода С. Если q = 2, С называется бинарным кодом. Если матрица H имеет

âèä H = (AEn k), то код С называется систематическим кодом.

Заметим, что множество С решений системы линейных уравнений Hct = 0 является k - мер-

ным подпространством векторного пространства Fqn .Так как кодовые слова образуют группу по сложению, то С также называется групповым кодом.

Пример 2. (код с общей проверкой на четность)

Пусть дано поле F2 и передаваемое сообщение имеет вид a1 a2 ::: ak. Определим схему кодиро- вания f следующим образом:

f : a1 a2 ::: ak ! b1 b2 ::: bk+1; ãäå bi = ai; i = 1; k ; a

bk+1 =	1; åñëè kk=1	ai = 1
	0; åñëè ik=1	ai = 0

Следовательно, сумма элементов любого кодового слова равна 0. Если сумма элементов равна 1, то получатель узнает, что в процессе передачи сообщения появилась ошибка. Если положить n = k + 1, то полученный код является линейным (n; n 1) кодом с проверочной

матрицей H = (1 1 ::: 1).

Определение. Матрица G = (Ek At) размером k n называются порождающей матрицей

линейного (n + k) кода с проверочной матрицей H = (A En k).

Из уравнения H ct = 0 и c = a G следует G Ht = 0 èëè H Gt = 0. Код С совпадает с пространством строк порождающей матрицы G. В общем случае любая k n матрица G, пространство строк которой равняется С, называется порождающей матрицей кода С.

7

Пример 3. Порождающая матрица G с проверкой матрицей Н из примера 1 имеет вид:

G =	0 0 1			0	0	0	1	1 1		;
	B	1	0	0	0	1	1	1	C
		0	0	0	1	1	1	0
	B	0	0	1	0	1	0	1	C
	@								A

aG = c

(a1 a2 a3 a4)G = a1 a2 a3 a4 a1 +a3 +a4 a1 +a2 +a4 a1 +a2 +a3, т.е. получаем тот же линейный

код как в примере 1.

Легко проверить, что GHt = 0.

2.2Декодирование линейных кодов

Определение. Пусть x; y 2 Fqn, тогда:

1.Расстоянием Хэмминга d(x; y) между векторами х и у называется число координат, которыми векторы х и у отличаются друг от друга.

2.Весом Хэмминга !(x) вектора х называется число ненулевых координат этого вектора.

Таким образом, если х - передаваемое слово, то величина d(x; y) дает число ошибок, появившихся при передаче слова х. Легко видеть, что !(x) = d(x; 0); d(x; y) = !(x y).

Лемма. Расстояние Хэмминга является метрикой в пространстве Fqn, т.е. для любых x; y 2 Fqn выполняются следующие условия:

1.d(x,y)=0 тогда и только тогда, когда х=у

2.d(x; y) = d(y; x)

3.d(x; z) 6 d(x; y) + d(y; z)

Пример 4. Построить E3 - метрическое пространство над полем F2.

При декодировании полученного слова y обычно стараются найти кодовое слово с, для которого !(y c) принимает наименьшее возможное значение. Таким образом, при декодировании

мы ищем кодовое слово с, ближайшее в смысле расстояния Хэмминга к полученному слову y. Это правило называется декодированием в ближайшее кодовое слово.

Определение. Если t - некоторое натуральное число, то код C 6 Fqn называется кодом, исправляющим t ошибок, если для любого y 2 Fqn найдется не более одного слова c 2 C, такого,

÷òî d(y; c) 6 t.

Если c 2 C - передаваемое кодовое слово и при передаче появилось не более t ошибок, то d(y; c) 6 t для полученного слова y. Если код С - код исправляющий t ошибок, то для всех кодовых слов x 6= c должно выполняться соотношение d(y; x) > t. Это означает, что с является

ближайшим к y кодовым словом и декодирование в ближайшее кодовое слово дает правильный результат. Таким образом, одна из задач теории кодирования состоит в построении таких

8

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

Определение. Число

dc = min d(u; v) = min !(c)

u; v 2 C u 6= v 0 6= c 2 C

называется расстоянием линейного кода С.

Теорема. Код С с расстоянием dc может исправлять t ошибок, если dc > 2t + 1.

Пример 5. Код из примера 1 имеет dc = 3 и, следовательно, может исправлять одну ошибку.

Лемма. Для того чтобы линейный код С с проверочной матрицей Н имел расстояние dc > s + 1, необходимо и достаточно, чтобы любые s столбцов матрицы Н были линейно независимы.

Определение. Пусть С - линейный (n; k) код над полем Fq. Множество a + C = fa + c j c 2 Cg

называется смежным классом.

Таким образом, векторное пространство Fqn=C состоит из всех смежных классов по коду С.

Определение. Лидером смежного класса a + C называется вектор е, имеющий минимальный вес.

Определение. Пусть Н - проверочная матрица линейного (n; k) кода С. Тогда вектор S(y) = Hyt длины (n k) называется синдромом вектора y.

Теорема. Если y; z 2 Fqn, òî

1.S(y) = 0 () y 2 C

2.S(y) = S(z) () y + C = z + C.

Пусть C 6 Fqn - линейный (n; k) код, и пусть y - принятый вектор. Для того чтобы исправить ошибки, имеющиеся в y, вычислим S(y) и найдем такой лидер смежного класса е, синдром

которого равен S(y). Тогда декодируем y как x = y e. Здесь х - кодовое слово, находящееся на минимальном расстоянии от y.

Пример 6.

1. Построить (4; 2) код над полем F5

H =	1	2	3	0
	0	1	2	2

c2 a1 a2 c1

9

2. Систематизируем матрицу Н

	H =	1	2	2	0
		2	3	0	1

a1 a2 c1 c2

Домножим первую строку матрицы на 3

	H =	3	1	1	0
		2	3	0	1
	A =		2	3
			3	1

3. Из матрицы Н находим c1; c2

c1 = 3a1 a2 = 2a1 + 4a2 c2 = 2a1 3a1 = 3a1 + 2a2

a1a2 ! a1a2 2a1 + 4a2 3a1 + 2a2

4. Находим порождающую матрицу Gk n = (E At)

	0	1	1	3		0	1	4	2
G =	1	0	3	2	=	1	0	2	3

Найдем c1; c2 по формуле: aG = c

	( a1	a2	)	1	0	2	3	=	a1a2	2a1 + 4a2 3a1 + 2a2
				0	1	4	2

5. Проверим правильно ли мы нашли порождающую матрицу G

				0 1		3 1				GHt	= 0
1	0	2	3					=	3 + 2	2 + 3	=	0	0
0			2	B	3	1	C		1 + 4	3 + 2 0			0
	1	4			1	0
					0	1
				B			C
				@			A

10