Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

3. Примеры линейных кодов

3.1. Границы минимального расстояния для линейных кодов.

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

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

Верхняя граница Плоткина устанавливает довольно грубую границу для расстояния d.

Теорема 3.1. Минимальный вес ненулевого кодового слова в двоичном (n, k)-коде равен самое большее 2k-1/(2k -1).

Доказательство. Построим матрицу, состоящую из всех кодовых слов двоичного (n,k)-кода. Так как код является подгруппой пространства всех булевых векторов длины n, то все столбцы матрицы содержат одинаковое число единиц и нулей. Следовательно, каждый столбец содержит 2k-1 единиц, а число единиц во всей матрице равно 2k-1. Утверждение теоремы вытекает из того, что общее число элементов с ненулевым весом равно 2k-1 и минимальный вес элемента не может превышать средний вес.

Таким образом, расстояние двоичного (n, k)-кода не может быть больше 2k-1/(2k -1). Например, расстояние двоичного (7, 4)-кода не превышает 7×23/(24-1) = 56/15 < 4. Таким образом, не существует двоичного (7, 4)-кода, который исправляет больше одной ошибки.

Верхняя граница Хэмминга для кодового расстояния d может быть получена следующим образом. Двоичный (n, k)-код содержит 2k кодовых векторов, т. е. стандартное расположение содержит 2n-k смежных классов. Если код исправляет все комбинации из t и меньшего числа ошибок, то все векторы веса t и менее должны быть образующими смежных классов. Таким образом, число векторов веса t или меньше не должно превосходить число смежных классов.

Теорема 3.2. Для любого двоичного (n, k)-кода с расстоянием не меньше 2t+1 число проверочных символов не меньше, чем log2[].

Доказательство. Рассмотрим стандартное расположение кода в виде таблицы декодировании. Чтобы исправить одиночные ошибки, все наборы веса 1 должны принадлежать различным смежным классам. Для исправления двух ошибок необходимо выполнение того же условия. Таким образом, чтобы исправить любые комбинации из t или менее ошибок, все вектора веса t и менее должны принадлежать различным смежным классам. Таким образом, число различных смежных классов больше или равно . Таким образом, число 2n-k смежных классов не меньше, чем , и следовательно

.

Продолжим рассмотрение двоичного линейного кода с длиной кодового слова 7. Согласно последней теореме, для того, чтобы код исправлял не менее двух ошибок, код должен иметь не менее 5 проверочных символов, т.к. log2() = log2(1+ C71 + C72) = log2(1 + 7 + 21) > 4. Однако, согласно теореме 3.1, расстояние двоичного (7,2)-кода не превышает 7×22/(23-1) = 4. Таким образом, единственный двоичный линейный код с длиной кодового слова 7, который исправляет не менее двух ошибок, есть (7, 1)-код, который содержит всего два кодовых слова.