Документ взят из кэша поисковой машины. Адрес оригинального документа : http://halgebra.math.msu.su/wiki/lib/exe/fetch.php/staff:markov:codes-2-art.pdf Дата изменения: Wed Feb 13 11:26:38 2013 Дата индексирования: Sun Apr 10 00:13:10 2016 Кодировка: Windows-1251

ЭЛЕМЕНТЫ АЛГЕБРАИЧЕСКОЙ ТЕОРИИ КОДОВ
Коды и их основные параметры.
Пусть ство



конечное множество (алфавит), длины

q = || > 1,

n

множе-

слов Кодом

длины

C кодовыми словами кода C . Размерностью кода C называется (действительное) число logq |C |. Расстоянием Хэмминга между словами a = (a1 , . . . , an ) и b = (b1 , . . . , bn ) называется число d(a, b) = |{i 1, n : ai = bi }|. Расстоянием кода C называется число d(C ) = min{d(a, b) : a, b C и a = b}. Код длины n над алфавитом из q элементов, имеющий размерность k и расстояние d, называется [n, k , d]q -кодом .
множество

над алфавитом называется любое непустое подn множества строк . Элементы множества C называются

n. n

Свойства расстояния Хэмминга.
Для любых слов 1) 2) 3)

a, b, c

n

справедливы следующие утверждения:

d(a, b) = d(b, a); d(a, b) = 0
тогда и только тогда, когда

a=b

.

(Неравенство треугольника) d(a, c) d(a, b) + d(b, c).

Исправление ошибок.
d расстояние Хэмминга n для любого слова a существует не более которого выполнено неравенство d(a, c) r .
Пусть

Теорема 1.

кода

C

одного

2r < d. Тогда слова c C , для
и . Тогда

2 Действительно, пусть c1 , c2 C , d(a, c1 ) r и d(a, c2 ) r d(c1 , c2 ) d(c1 , a) + d(a, c2 ) 2r < d, откуда c1 = c2 . 2

Принцип максимального правдоподобия. Если известно, что переданное слово a принадлежит коду C , а полученное слово b ему не принадлежит, то слово b заменяется на такое слово c C , что d(b, c) минимально. Если при передаче искажено менее чем d/2 знаков, то c = a.
1


Граница Синглтона. Теорема 2. Если C
d + k n + 1. 2
Пусть

код длины

n

размерности

k

с расстоянием

d

, то

m = |C | = q

k

. Выпишем все слова кода

C

в виде матрицы и

разделим ее столбцы

(a

1,1

(a (a (a

i,1

j,1

m,1

. . . a1,d-1 a1,d ... . . . ai,d-1 ai,d ... . . . aj,d-1 aj,d ... . . . am,d-1 am,d
d-1

. . . a1,n ) ... . . . ai,n ) ... . . . aj,n ) ... . . . am,n )
n-(d-1)

(a

i,d

. . . ai,n ) = (a i=j

j,d

. . . aj,n )

n-(d-1)

Следовательно,

m = qk q

k n - d + 1. 2

МДР-коды. Определение 1.
ется если

Код

C

длины

n

размерности

МДР-кодом

(или, полностью,

k с расстоянием d называкодом с максимальным достижимым расстоянием

),

d + k = n + 1. [n,
Простейшие примеры: 1) Код констант C 1, n]q -код. 2) Код n [n, n, 1]q -код. 3) Код

состоящий из слов рых

(a1 , . . . , an )

над алфавитом

= {(c, c, . . . , c) : c } проверки на ч?тность , {0, 1, . . . , q - 1}, для кото

a1 + . . . + an 0 (mod q ) [n, n - 1, 2]q
-код.

Параметры МДР-кодов. Нерешенная задача.
Для заданных значений

q

и

k

найти максимальную возможную длину

n(k , q )
1)

МДР-кода размерности

k

над алфавитом из

q

элементов.

Простые оценки n(k , q ).
n(1, q ) = (код констант имеет любую заданную длину). 2) n(k , q ) k + 1 (код проверки на ч?тность). 3) Если q k , то n(k , q ) = k + 1. 4) Если k < q , то n(k , q ) q + k - 1. 5) Если q = q1 q2 , то n(k , q ) min{n(k , q1 ), n(k , q2 )}.
2


Пример доказательства оценки.
Докажем утверждение 4. Пусть

C

МДР-код длины

n

и размерности

k

над

. = {0, 1, ..., q - 1}
и каждое кодовое слово представим его графиком, т.е. линией, соединяющей точки

Будем считать, что

(a1 , . . . , an ) (i, ai ).

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

(k - 1)
O

общих точек.

Рассмотрим все слова, имеющие общее начало

(a1 , . . . , a

k-1 ).



q-1 ћћћ 1 0

ћћћ - ћћћ ћћћ ћћћ

ћ ћћћ ћ ћ

ћ ћћћ ћ ћ ћ ћ ћ ћћћ

ћ ћ ћћћ ћ ћ
/

1..k-2

k-1

k

ћћћ

n

i

Рассмотрим кодовое слово, которое имеет начало где

(a1 , . . . , a

k-2

, ak-1 ),

ak-1 = ak-1 . Его график имеет не более одной точки пересечения с продолжениями рассмотренных слов.


O

q-1 ћћћ 1 0

ћћћ - ћћћ ћћћ ћћћ

ћ ћћћ ћ ћ

ћ ћћћ ћ ћ ћ ћ ћ ћћћ

ћ ћ ћћћ ћ ћ
/

1..k-2

k-1

k

ћћћ

n

i

3


Из рисунка видно, что

n - (k - 1) q

, что и требовалось.

Линейные коды.
Пусть теперь число. Код

= F конечное поле
линейным

,

q = |F | = p C

r

,

p

простое

C

над

F

называется

, если

подпространство ли-

нейного пространства строк над полем

F

.

Примеры кодов, приведенные ранее, линейные коды.

Замечание 1. Если C линейный код, то d(a, b) = d(a - b, 0) для люa, b C , поэтому d(C ) = min{d(c, 0) : 0 = c C }. Число d(c, 0) называется весом слова c.
бых

Определение 2.

n k различных элементов 1 , . . . , n поля F и n обратимых элементов u1 , . . . , un поля F . Множество слов {(u1 f (1 ), . . . , un f (n )) : f (x) F [x] и deg f (x) < k } называется обобщ?нным кодом РидаСоломона GRS (k , n).
Пусть Выберем

k q - 1.

Обобщ?нный код РидаСоломона МДР-код. Теорема 3.
2
Пусть Код

GRS (k , n)

имеет размерность

k

и расстояние

n - k + 1,

т.е. является МДР-кодом.

0 = f (x) F [x] и deg f (x) < k . Тогда число корней многочлена f (x) в F не превосходит deg f (x), т.е. меньше k . Значит, вес слова {(u1 f (1 ), . . . , un f (n )) больше n - k , значит d(GRS (k , n)) n - k + 1.
Привед?нное рассуждение также показывает, что число слов в коде

GRS (k , n) равно k т.е. q , т.е. k d(C ) n + 1 - k

числу многочленов размерность кода . Следовательно,

f (x) F [x], таких, GRS (k , n). Граница d(C ) = n + 1 - k . 2

что

deg f (x) < k

,

Синглтона дает

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

Теорема 4.
F

Если

C

линейный код длины

, то существует матрица

H

размера

n m Ч n,

и размерности такая, что

k

над полем

C = {a F n : H aT = 0}.
При этом

rank(H ) = n - k . Матрица H называется проверочной матрицей
4

кода

C

.


Декодирование по таблице синдромов
F, имеющий расстояние d. H его проверочная матрица размера (n - k ) Ч k . Синдромом вектора a F n называется вектор aH T = (H aT )T . Синдром это вектор длины n - k .
Пусть линейный код длины и размерности над полем

C

n

k

b

сопоставляется вектор Пусть послано слово

Один раз можно составить таблицу: каждому возможному синдрому e(b), являющийся решением системы H xT = bT

и имеющий наименьший вес среди всех таких решений.

aC

, получено слово

a

. Если синдром

0,

то, предполагая, что число ошибок при передаче меньше, чем

a HT = d, полу-

a = a (обнаружение < d ошибок) . T Если же b = c H = 0, то находим по таблице e(b). Тогда (c - T e(b))H = b - b = 0 c = c - e(b) C . Предполагая, что число ошибок при передаче меньше, чем d/2, получаем c = a.
чаем

Список литературы
[1] Ф. Дж. МакВильямс, Н. Дж. А. Слоэн, Теория кодов, исправляющих ошибки. Москва, Связь, 1979. [2] Э. Р. Берлекамп, Алгебраическая теория кодирования, Москва, Мир, 1971.

5