1.2. Линейные блоковые коды

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

Линейный код (т.е. множество кодовых слов) является векторным подпространством в пространстве V₂. Это означает, что операция кодирования может быть представлена умножением на матрицу. В терминах цифровой электроники простое кодирующее устройство может быть построено на элементах «исключающее ИЛИ», «И» и триггерах типа D. В этой части операциями сложения и умножения в двоичном векторном пространстве являются «исключающее ИЛИ» (сложение по модулю 2) и «И», соответственно. Таблицы сложения и умножения двоичных элементов имеют следующий вид:

а	b	a+b	ab
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

1.2.1. Порождающая и проверочная матрицы

Пусть С двоичный линейный (п, к, d_min) код. Так как С есть k-мерное подпространство, то оно имеет базис, например, (v₀, v₁,…, v_k-1) такой, что любое кодовое слово v С может быть записано как линейная комбинация элементов этого базиса:

(1.9)

где u_i {0, 1}, 0 ≤ i < k. Уравнение (1.9) может быть записано в матричной форме через порождающую матрицу G и вектор-сообщение и = (и₀, u₁, …, u_k-1):

v=uG (1.10)

где

(1-11)

Так как С является k- мерным векторным пространством в V₂, то существует (n-k)-мерное дуальное пространство (dual space) С┴, которое порождается строками матрицы Н, называемой проверочной матрицей (parity-check matrix), такой, что GH^T=0, где через Н^T обозначена транспонированная матрица Н. Заметим, в частности, что любое кодовое слово v С удовлетворяет условию

vH^T=0 (1.12)

Как будет показано в разделе 1.3.2 уравнение (1.12) является фундаментальным для декодирования линейных кодов.

Линейный код С┴, который генерируется матрицей Н, является двоичным линейным (п, п - k, d┴_min) кодом, который называют обычно дуальным коду С.

1.2.2. Вес как расстояние

Как упоминалось в разделе 1.1.2, линейные коды отличаются тем, что для определения минимального расстояния кода достаточно знать минимум Хеммингова веса ненулевых кодовых слов. Ниже этот факт будет доказан. Определим вес Хемминга wt_H (x) вектора х V₂, как число ненулевых элементов в х. Из определения Хеммингова расстояния ясно, что wt_H(x) = d_H(x, 0). Для двоичного линейного кода С получаем

(1-13)

Наконец, из свойства линейности кода имеем v₁+v₂ C. Отсюда следует, что минимальное расстояние кода С равно и может быть вычислено как минимальный вес по всем 2^к — 1 ненулевым кодовым словам. Эта задача существенно проще, чем полный перебор по всем парам кодовых слов, хотя и остается очень сложной даже для кодов среднего размера (или размерности к).