Методическое пособие 640

откуда видно, что любые две строки матрицы содержат по две единицы и отличаются значениями символов на двух позициях, т.е. код обладает кодовым расстоянием d 2 и, значит, способен обнаруживать однократные ошибки. Проверочная матрица содержит только одну строку и представима как

H11 1 ,

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

Следует отметить, что порождающая матрица G кода с повторением (n,1) совпадает с проверочной матрицей H кода

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

Пример. Код #3, код из всех слов четного веса.

Код с k = 3, n = 4 и с проверочной матрицей

Н = [111].

Каждое кодовое слово содержит три информационных символа x1x2x3 и один проверочный символ

x4 = x1 + x2 + x3.

Кодовыми словами, число которых 23=8, являются после-

довательности 0000, 0011, 0101, 1001, 0110, 1010, 1100, 1111, т. е. все возможные векторы длины 4 с четным числом единиц.

161

7.4.3. Свойства линейного кода

1) х = х1 ... хп является кодовым словом, если и только

если

2) Проверочная матрица Н - это ((n—k)x n)- матрица

вида

3) Имеется 2k кодовых слов, которые выглядят следующим образом:

информационные проверочные символы символы

4) Порождающая матрица.

Для декодирования сообщения используется следующее сообщение

где

= [ | − ] ,

называется порождающей матрицей кода и ее легко по-

лучить из проверочной матрицы H.

5) Матрицы H и G связаны между собой соотношением

G·HT = 0 или H·GT = 0.

Учитывая сказанное выше, можно их «поменять ролями» и использовать H в качестве порождающей, а G – проверочной матрицы некоторого другого кода. Коды, связанные с таким преобразованием, называются дуальными друг другу. Таким образом, если исходный являлся (п, k) кодом, то дуальным ему будет (п, n - k) код.

6) Параметры линейного кода.

Говорят, что кодовое слово х = х1 ... хп имеет длину п. Здесь имеется в виду не длина вектора в обычном математическом смысле, а число символов в этом векторе, т. е. его раз-

162

мерность. Число n называется также блоковой длиной кода. Если Н имеет n—k линейно независимых строк, то имеется 2k кодовых слов. Число k называется размерностью кода. Мы назовем такой код (п, k) -кодом. Этот код использует п символов для передачи k символов сообщения, поэтому говорят, что код имеет скорость или эффективность

R=k/n.

7) Линейность.

Если х и у — кодовые слова данного кода, то х + у - также кодовые слова этого кода, так как Н (х + у)Т=НхТ + Нут=0. Если с — любой элемент поля, то с·х - также кодовое слово, так как Н(сх)Т = сНхТ=0. Например, в троичном коде, если х — кодовое слово, то 2х = -х также является кодовым словом. Поэтому эти коды и называются линейными кодами. Такой код является также аддитивной группой и векторным пространством над полем.

Пример. Код #1 (продолжение).

Согласно (7.6) каждое из восьми кодовых слов имеет вид: u1 · (строка 1) + u2· (строка 2) + u3· (строка 3), где u1, u2, u3 = 0 или 1.

Вновь убеждаемся, что кодовое слово, соответствующее сообщению u=011, равно

х = uG = строка 2 +строка 3= 010101+ 001110 = 011011,

где, как обычно, сложение было выполнено по mod 2. Затем, путем отброса проверочных символов, получаем исходное переданное сообщение.

163

7.4.4. Другие порождающие и проверочные матрицы

Код может иметь несколько различных порождающих матриц. Например, матрицы

и

обе являются порождающими для кода #4. В действительности любое максимальное множество линейно независимых кодовых слов, выбранных из данного кода, может быть использовано в качестве строк порождающей матрицы для этого кода.

Проверочным соотношением для кода является любой

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

7.4.5. Коды над другими полями

Вместо использования только символов 0 и 1 мы можем допустить, чтобы символы были из любого конечного поля. Например, троичный код имеет символы 0, 1 и 2 и все вычисления в проверочных соотношениях и т.п. выполняются по мо-

дулю 3 (1+2=0; -1=2; 2+2=1; 2·2=1 и т.д.). Если используются символы конечного поля из q элементов, то код по-прежнему определяется соотношениями (7.1) и (7.2) и (п, k)-код содержат qk кодовых слов.

Пример. Код #6. Троичный (4,2)-код задается проверочной матрицей

164

Тогда порождающая матрица имеет вид:

Код состоит из следующих девяти слов вида u1 · (строка

1) + u2 · (строка 2) u1 , u2 = 0, 1 или 2):

Сообщение u Кодовое слово x

101022

111110

121201

202011

212102

222220

Этот код имеет скорость R=k/n=1/2.

7.4.6. Декодирование сообщения

Предположим, что сообщение u = u1 ... uk закодировано в кодовое слово х = х1 ... хп , которое потом передается по каналу. Так как канал с шумом, то принятый вектор y = y1 ... yп может отличаться от х. Удобно ввести вектор ошибок

Тогда ei = 0 с вероятностью 1—р (в этом случае - i-й символ правильный) и 1 с вероятностью р (i-й символ неправильный). В предыдущем параграфе р было равно 1/100, но в общем случае р может быть любым числом в диапазоне 0 ≤ р ≤ 1/2. Таким образом, в канале кодовое слово х искажается, за счет прибавления к нему вектора ошибок е.

165

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

Декодер (рис. 7.4) должен на основании принятого сигнала у решить, какое сообщение или (что обычно проще) какое кодовое слово х было передано. Конечно, достаточно, если декодер найдет е, так как тогда х = у - е. Но декодер никогда не может знать наверняка, какой был вектор ошибок е. Eгo стратегия, следовательно, будет заключается в выборе наиболее вероятного для данного принятого у вектора ошибок е. При условии, что все кодовые слова равновероятны, эта стратегия оптимальна в том смысле, что она минимизирует вероятность ошибки декодера, и такая стратегия называется декодировани-

ем по максимуму правдоподобия.

Вектор ошибок

Рис. 7.4. Полная система связи

В процессе декодирования ошибки происходят с вероятностью р, например

Prob {е = 00000} = (1- р)5

Prob {е = 01000} = р·(1 - p)4

Prob {e = 10010} = p2·(1 - р)3.

В общем случае, если v — некоторый фиксированный

Следовательно, фиксированный вектор ошибок веса 1 более вероятен, чем фиксированный вектор ошибок веса 2, и т.д. Поэтому стратегия декодировании такова: у декодируется в ближайшее кодовое слово х (ближайшее в смысле расстояния Хэмминга), иначе говоря, выбирается вектор ошибок е с наименьшим весом. Это называется декодированием в бли-

жайшее кодовое слово.

Декодирование полным перебором заключается просто в сравнении у со всеми 2k кодовыми словами и в выборе ближайшего слова. Это хорошо для небольших кодов. Но если k велико, это невозможно! Одной из целей теории кодирования является отыскание кодов, которые могут быть декодированы более быстрым методом, чем этот.

7.5. Основные характеристики кода

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

Расстояние (Хэмминга) между двумя векторами х = х1 ... хп и y = y1 ... yп равно числу позиций, в которых они различаются.

Оно обозначается dist (x, у), например

dist (10111, 00101) = 2; dist (0122, 1220) = 3

(то же самое определение справедливо и для недвоичных векторов).

Вес (Хэмминга) вектора х = х1 ... хп равен числу ненулевых хi . Он обозначается wt (x).

Например,

wt (101110) = 4; wt (01212110) = 6.

Очевидно, что

167

так как обе части выражают число позиций, в которых различаются векторы х и у.

Минимальное расстояние Хемминга между его кодовыми словами (минимальное кодовое расстояние):

d = min{dist (u, v)} = min{wt (u—v)}; u ; ; u≠v. (7.10)

Число d называется минимальным расстоянием или про-

сто расстоянием кода. Любые два кодовых слова различаются по крайней мере в d позициях.

Линейный код длины n, размерности k и с минимальным расстоянием d далее будет называться (n, k, d) -кодом.

Для нахождения минимального расстояния линейного кода не обязательно сравнивать все возможные пары кодовых слов. Если u и v принадлежат линейному коду , то u—v = =w также является кодовым словом, и, как следует из (7.10),

d = min wt (w), где w ≠ 0 и w .

Другими словами, справедлива следующая теорема.

Теорема 1. Минимальное расстояние линейного кода равно минимальному весу ненулевых кодовых слов.

Пример. Минимальные расстояния кодов #1, #2, #3, #6 равны 3, 5, 2, 3 соответственно.

Второй важный вопрос, который необходимо рассмотреть: как много ошибок может исправлять код?

Теорема 2. Код с минимальным расстоянием d может исправлять (d—1)/2 ошибок. Если d четное, то код может одновременно исправлять (d—2)/2 ошибок и обнаруживать d/2 ошибок.

Доказательство. Предположим, что d=3 (рис. 7.5). Шар

радиуса r с центром в точке и состоит из всех векторов v таких, что dist (u,v) ≤ r. Если вокруг каждого кодового слова описать шар радиуса 1, то эти шары не пересекаются. Если передавалось кодовое слово u и произошла одна ошибка, то принятый

168

вектор а находится внутри шара, проведенного вокруг u, и поэтому а ближе к u, чем к любому другому кодовому слову v. Таким образом, декодирование в ближайшее кодовое слово исправит эту ошибку.

Подобным образом, если d=2t +1, то шары радиуса t, описанные около каждого кодового слова, не пересекаются и код может исправлять t ошибок.

Теперь предположим, что d четное (рис. 7.6, где d=4). Сферы радиуса (d—2)/2, проведенные вокруг кодовых

слов, не пересекаются, и поэтому код может исправлять (d—2)/2 ошибок. Но если произошло d/2 ошибок, то принятый вектор а может находиться посреди между двумя кодовыми словами (рис. 1.5). В этом случае декодер может только обнаружить, что произошло d/2 (или больше) ошибок.

Обычно декодирование осуществляется таким образом, что любая принятая запрещенная кодовая комбинация отождествляется с разрешенной комбинацией, находящейся от неё на минимальном кодовом расстоянии. Если минимальное кодовое расстояние данного кода d = 1, т.е. все комбинации кода являются разрешенными, то обнаружить ошибку не удастся. Если d = 2, то удастся обнаружить единичную ошибку и т.д. В общем случае при необходимости обнаружения ошибки кратности до r включительно, минимальное кодовое расстояние должно удовлетворять условию

169

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

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

обнаружения всех ошибок кратности r (r > s) минимальное кодовое (Хэммингово) расстояние должно удовлетворять неравенству

≥ + +1 . (7.13)

Дадим геометрическую трактовку приведенным выше соотношениям.

Любая n -разрядная двоичная кодовая комбинация может быть интерпретирована как вершина n -мерного гиперкуба с длиной ребра равной 1. Например, при n = 2 это квадрат, при n = 3 - единичный куб. В общем случае n - мерный гиперкуб содержит 2n вершин, что совпадает с возможным числом n - разрядных двоичных кодовых комбинаций.

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