ЛИНЕЙНЫЕ БЛОКОВЫЕ КОДЫ

Теория кодирования. Линейные блоковые коды.

1. Цель работы

Разработать программный модуль, который по заданным параметрам
(n, k, d) строит двоичный линейный блоковый код.

Требования к программе:

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

2. Ход исследования

2.1. Краткие теоретические сведения

Пусть кодируемая информация делится на фрагменты длиной k бит, которые преобразуются в кодовые слова длиной n бит. Блоковый код, соответствующий данным параметра, обычно обозначают (n, k). Также вводится определение числа R = n / k, называемое скоростью кода.

Число d называется минимальным расстоянием кода, определяющееся, как минимум расстояния Хэмминга по всем возможным парам различных кодовых слов.

Обозначение (n, k, d) используется для параметров блокового кода длины n, который используется для кодирования сообщений длины k, и имеет минимальное Хэммингово расстояние d. Число кодовых слов данного кода С равно |C|=2^k.

Корректирующей способностью (error correcting capability) t кода C называют максимальное количество ошибок, которое можно обнаружить с данными параметрами: t = (d-1)/2, округленное вниз.

Задать блоковый код можно по-разному, в том числе таблицей, где каждой совокупности из k информационных бит сопоставляется n бит кодового слова. Однако, хороший код должен удовлетворять, как минимум, следующим критериям:

• простота кодирования и декодирования;
• способность исправлять как можно больше ошибок;
• избыточность минимальна.

Таким образом, требуется обеспечить: d0 ↑, N ↑, n ↓.

Очевидно, что приведённые требования противоречат друг другу. Именно поэтому кодов существует достаточно много.

Верхняя граница N_В определяется утверждением: не существует кода, число слов в котором N>N_В.

Нижняя граница N_Н определяется утверждением: существует код, число слов в котором N>=N_Н.

2.2. Алгоритм

Произвольная порождающая матрица G линейного блокового (n,k,d) кода может быть преобразована к систематическому (каноническому) виду с помощью элементарных операций и перестановок столбцов матрицы.

Матрица G_sys состоит из двух подматриц: единичной матрицы I_k размерами k*k и k*(n-k) проверочной подматрицы P (матрица дополнений). Таким образом, G_sys=(I_k|P).

Для построения линейного блокового кода достаточно найти матрицу дополнений P. Матрица P состоит из k векторов длины r=n-k.

Рассмотрим множество (А) двоичных векторов длины r, мощность такого множества равна 2^r.

Исходя из того, что все векторы в матрице P различны, и того, что перестановка векторов будет давать эквивалентную порождающую матрицу, будем строить матрицу дополнений следующим образом:

• пронумеруем векторы, принадлежащие множеству А, будем отбирать только те, чей вес больше d-1. Выберем первый – а1;
• выберем (из следующих за первым) второй (а2) таким образом, чтобы вес w(a1+a2)>=d-2 («+» − сложение по модулю 2);
• на шаге i сумма любой пары векторов должна иметь вес не меньше d-2, сумма любой тройки не меньше d-3, аналогично до комбинаций из d-1 векторов, вес которых должен быть ненулевым.

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

Если k векторов найти не удалось, увеличим n на единицу, создадим заново множество А. Тем самым будем рассматривать векторы, отобранные ранее, в новом пространстве с увеличенным числом измерений, считая у них нулевой координату нового измерения.

Увеличивая n, мы либо построим на каком-то шаге матрицу дополнений, либо n достигнет нижней границы Варшамова–Гильберта, код с таким n удовлетворяет требуемым параметрам, следовательно, матрица будет построена.