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

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

сообщение

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

 

канал

 

связи

„ "шум" „

помехи

а

 

 

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

9

полученное сообщение

 

а

 

с + е

Мы будем считать, что символы, входящие в запись сообщений и кодов, являются элементами поля СР(д) = -Рг Кодирование - это отображение / : У]1} —>• У,". где п > к. Т.е. каждое сообщение а\а2 ... щ. (а; Є У,,) заменяется кодовым словом с\... сп. Аналогично, декодирование - это отбражение д :

Пусть ж, у Є У,". Расстоянием Хэмминга (1(х. у) между векторами ж, у называется число координат, которыми векторы х и у отличаются друг от друга, а весом Хэмминга гп(х) называется число ненулевых координат этого вектора. Ясно, что о!(х, у) = гп(х — у), и если х - передаваемое слово, а у -полученное слово, то о!(х, у) - число ошибок, сделанных при передаче. Лег­ко видеть, что функция о1(х,у) удовлетворяет следующим трем свойствам метрики в пространстве У]" (Ух. у.,;. Є У]") :

1) о1(х: у) = 0 -Ф4> х = у;

2) й(х,у) = <%ж);

3) о1(х: г) < о1(х: у) + о1(у: г).

Пусть V С У'(1    некоторое множество кодовых слов и і ~ натуральное число. Скажем, что код V исправляет не более Ї ошибок, если для любого Ь Є У'ч' существует не более одного вектора а £ V такого, что о!(Ь, а) < т.е. в окрестности Ві(Ь) = {:/; Є У]": о!(Ь, х) < ї] существует не более одного вектора из V.

Число о1(У) = тіп{оІ(аіі а2); а\:а2 Є V. а\ ф а2} называется кодовым (минимальным) расстоянием кода V.

Предложение 1. Пусть о1(у) > 2£+1. Тогда кодУ исправляет не более Ї ошибок.

ДОКАЗАТЕЛЬСТВО. Пусть Ъ Є У,';. Если шар (окрестность) В,{Ь) со­держит два вектора а\. а-> Є I . то <1(а\. а2) < <1(а\. 1))+<1(а2. Ь) < 21 С другой стороны, оІ(аі,а2) > 2£ + 1. Противоречие доказывает предложение.

Т.е. если при передаче слова а произошло не более Ї ошибок, то для принятого слова Ь имеем неравенство о!(Ь, а) < Ї и для любого другого кодового слова с Є V о!(Ь, с) > ї + 1.

Определение [13]. Пусть Н - матрица над полем Уч порядка (п — к) х п и ранга (п — к). Линейным (п, к) - кодом над полем     называется множество

С решений сбсистемы линейных однородных уравнений

Я • ст = 0.

Ясно, что оНтрдС = к. Число к называется размерностью кода, а число п - его длиной. Матрица Я называется проверочной матрицей кода С, а элементы С называются кодовыми словами, или кодовыми векторами. Если (1 = 2. то код называется бинарным. Если Я = (Л/„_*.). где А - ма­трица порядка (п — к,к), а 1п^к - единичная матрица порядка (п — к), то код С называется систематическим. Если в систематическом коде С пер­вые к символов в каждом кодовом слове являются информационными (т.е. совпадают с к символами исходного сообщения), а остальные (п — к) симво­лов являются проверочными, то система уравнений Я • сТ = 0 называется системой уравнений проверки на четность. Пример 3 в 3.2 соответствует си­стематическому бинарному коду с матрицей Я = (11. ..11). Пример 1 из §2

соответствует линейному (п, 1)-коду с проверочной матрицей Я = (—1/п_1 т.е.

/ -1 1 0   0   ...0 \

Я =

10 10 ...0

п—1)хп-

\ -1 0 0 ...     0    1 /

Пусть Я = (А1п^) - проверочная матрица линейного (п, к) - кода. Тогда матрица О = (//,• ^ Ат) порядка к х п называется порождающей (кодирую­щей) матрицей кода С. Эта матрица возникает в связи с равенством

ст =[_А) °т = («№ " АТ))Т>

где а = <7 | ... а/, передаваемое сообщение, с = с\... сп - соответствующее кодовое слово и Нст = 0 - проверочное уравнение.

Так как Нст = 0 и с = аЄ, то НЄТ = 0 (или Є • Нт = 0). Из этого равен­ства следует, что код С порождается строками С В случае произвольноголинейного кода С его порождающей матрицей называется любая [к х п) матрица, строки которой порождают пространство С.

Определение. Пусть с - кодовое слово и у - слово, полученное после передачи сообщения по каналу (с помехами). Разность е = у — с = е\... еп называется вектором ошибок, или шумовым вектором.

Для линейного кода С минимальное расстояние Хэмминга о1с = т/п{<1(и. г): и. г £ С и ф г} совпадает с минимальным весом Хэм­минга тгп{ги(с)] с £ С, с ф 0}. Докажем следующий критерий для нижней границы минимального расстояния линейного кода С с проверочной ма­трицей Н.

Предложение 2. о1с > в + 1 тогда и только тогда, когда любые в столбцов Н линейно независимы.

ДОКАЗАТЕЛЬСТВО. Если в Н найдутся в столбцов //.;,..... которые линейно зависимы Хф^ + • • • + Х8Н{8 =0, то вектор

с=(0,0,...,0,Ль0,...,0,Л«,0,...,0)еС

и имеет вес в, т.е. о1с < е. Обратно, пусть любые в столбцов Н являются линейно независимыми и о1с < в. Пусть а £ Н,гп(а) = о!с,а ф 0. Тогда из равенства Н • аТ = 0 следует, что некоторые о1с < в столбцов Н линейно зависимы.

Пусть далее С - линейный (п, к)-код над полем Разложим простран­ство .Р^ на смежные классы по С:

у^1 = (0 + С) и (6^ + с) и • • • и (6<в> + С),

где в = д"^1'' — 1. В каждом классе Ь1,) + С(Ь11]) = 0) существует элемент минимального веса. Выберем его и назовем лидером этого смежного клас­са. Если передавалось кодовое слово с £ С, а было принято слово у, то вектор ошибок е = у — с принадлежит тому же смежному классу, что и у. Если а{,) - лидер класса у + С, то декодируем у как х = у — а{,) £ С. Этот способ декодирования называется алгоритмом декодирования по ли­деру смежного класса. Детализируем этот алгоритм. Пусть а11)...., -лидеры смежных классов У1'...., и С = {г( 1' = 0, с{2)...., с'-'1''} - все элементы кода С Пусть у - принятый вектор. Вектор Нут длины (п — к) называется синдромом у. Ясно, что синдром векторов у, г £ ^ совпада­ет тогда и только тогда, когда их смежные классы равны. Считаем далее

синдром Б (у) = Я ■ у1. Зная синдром лидеров 5( а

(і)

5(а

мы определим смежный класс, в котором содержится у. Например, у £ Ф\ Тогда декодируем у как х = (у — а''1).

Пример. Рассмотрим бинарный (5,2) - код С с проверочной матрицей / 1 1 1 1 0 \

Я

V 0 0 10 1 10 10 0 /

Пусть у = Б{у) = Н-ут

1,1,0,1,1

о

Vі/

полученное слово с синдромом

Приведем все смежные классы, выделив в начале

их лидеров:

(0, 0, 0, 0, 0), (0, 1, 0, 1, 1 0, 0, 0,0)

(2 (о

(о (о

о

о

о

о

о

о

о

о

о

0, 0)

0, 0)

1, 0)

0, 1

1, 0)

0, 0)

1, 1, 0, 1, 1

(0, 0, 0, 1, 1 (0, 1, 1, 1, 1 (0, 1, 0, 0, 1 (0, 1, 0, 1, 0) 1, 1,0, 0, 1 1,0, 0, 1, 1

1, 0, 1, 0, 1), (1, 1, 1, 1, 0) (0, 0, 1, 0, 1), (0, 1, 1, 1, 0) 1, 0, 1, 1, 0) 1, 1, 0, 1, 0) 1, 1, 1, 0, 0)

1, 1, 1, 0, 1 1, 0, 0, 0, 1

1,0, 1, 1, 1 1, 0, 1, 0, 0) (0, 0, 1, 1, 1 (0, 1, 1, 0, 1

1, 1, 1, 1, 1

(О, 1, 1, 0, 0) (О, 0, 1, 1, 0)

Так как 5(у) = 5(а^)) = 5 •

 

0

 

0

0

0

 

 

V0 У

 

то искомое кодовое слово равно х = у —      = (0,1,0,1,1).

Предложение 3. Пусть С - бинарный (п,к)-код с проверочной ма­трицей Н. Тогда синдром получаемого вектора у равен сумме столбцов Я, номера которых совпадают с номерами ошибочных координат у.

ДОКАЗАТЕЛЬСТВО. Действительно, пусть передавалось слово х £ С. Тогда

у = х+е я Б (у) = НеТ = Н^+Н^Л-----гдее = (0,..., 0,1, 0,... ,0,1,0,...,

причем единицы стоят на местах г\ иг$.

Если все столбцы Н различны и существует только одна ошибка в г-ж координате, то 5(у) = Н{, т.е. удачный выбор матрицы позволяет обнару­живать и исправлять одну ошибку.

Определение. Бинарный код Стп длины 2т — 1 = п(т > 2) с про­верочной матрицей Н порядка т х (2т — 1) называется кодом Хэммин-га, если столбцы Н представляют собой запись в двоичной системе чисел

Предложение 4. Бинарный код Ст имеет размерность (2т — т — 1) и исправляет одну ошибку.

ДОКАЗАТЕЛЬСТВО. Ранг матрицы Сгп равен т и, следовательно,

о1гтр2Ст = 2т — 1 — т. Так как любые два столбца Ст линейно незави­симые и Сгп содержит их сумму, то о1Ст = 2 + 1 = 3 (см. предложение 2). По предложению 1 код Ст является кодом, исправляющим одну ошибку.

Пример. Пусть Сз - бинарный (7, 4) - код Хэмминга. Его проверочная матрица равна

1,2,...

1.

/ 0 0 0 1 1 1 1 \

я

0 110 0 11

V

10 10 10 1

1 2 3 4 5 6 7

Пусть у = (0,0,1,0,1,0,1) - полученное слово. Его синдром равен о

V1/

Это первый столбец Н. Следовательно, ошибка допущена в первой коорди-

нате, и искомое кодовое слово равно (1, 0, 1, 0, 1, 0, 1)

В заключении параграфа докажем некоторые оценки относительно основ­ных параметров, характеризующих код.

Предложение 5 (граница Хэмминга). Пусть С - код над полем Ич. содержащий М кодовых слов, имеющий длину п и исправляющий t ошибок. Тогда

м.{1 + с1{ч-1) + --- + с1Хч-1У)<чп.

ДОКАЗАТЕЛЬСТВО. Действительно, шары радиуса Ї с центрами в ко­довых словах попарно не пересекаются. Каждый такой шар содержит по­мимо кодового слова ещё С*(д — 1) слов, отличающихся от него одной ко­ординатой, С2(д — I)2 слов, отличающихся двумя координатами, и т.д. Так как       = д". то неравенство доказано.

Приведем без доказательства следующее предложение [13]: Предложение 6 (граница М.Плоткина). Пусть С - линейный (п, к)-код над полем ¥,г Тогда

п ■ ак^1(а — 1)

(<?* -1)