3. Коды, исправляющие ошибки

3.1. Блоковые и сверточные коды

В соответствии с тем, как вводится избыточность в сообщение, коды, исправляющие ошибки, могут быть разделены на два класса: блоковые и сверточные (convolutionalcode)коды. Обе схемы кодирования нашли практическое применение. Исто­рически сверточные коды имели преимущество главным обра­зом потому, что для них известен алгоритм декодирования Ви­терби с мягким решением и в течение многих лет существова­ла убежденность в том, что блоковые коды невозможно декодировать с мягким решением. Однако последние достиже­ния в теории и конструировании алгоритмов декодирования с мягким решением для линейных блоковых кодов помогли рассеять это убеждение. Более того, наилучшие ЕСС, извест­ные сегодня (в начале двадцать первого века), являются блоко­выми кодами (нерегулярными кодами с низкой плотностью про­верок — irregularlow-densityparity-checkcodes).

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

Следует заметить, что на самом деле блоковые коды обла­дают памятью, если рассматривать кодирование как побито­вый процесс в пределах кодового слова. Сегодня это различие между блоковыми и сверточными кодами кажется все менее и менее ясным, особенно после недавних достижений в пони­мании решетчатой (trellis) структуры блоковых кодов и кольце­вой (tail-biting) структуры некоторых сверточных кодов.

Дополнение переводчика. Название кольцевые сверточные ко­ды еще не окончательно утвердилось в отечественной литерату­ре, иногда tail-bitingconvolutionalcodesназывают циклически за­мкнутыми.

Специалисты по сверточным кодам иногда рассматривают блоковые коды как «коды с меняющейся во времени структу­рой решетки» (time-varyingtrellisstructure).Аналогично, специ­алисты в области блоковых кодов могут рассматривать свер­точные коды как «коды с регулярной структурой решетки».

3.2. Хеммингово расстояние, Хемминговы сферы и корректирующая способность

Рассмотрим двоичный код С, исправляющий ошибки. Еслиневсе из 2ⁿ возможных двоичных векторов длины n будут переда­ваться по каналу связи, то этот код может обладать свойством помехоустойчивости. В действительности, код С является под­множеством n-мерного двоичного векторного пространства таким, что элементы этого подмножества макси­мально удалены друг от друга.

В двоичном пространствеV₂расстояние определяется как число позиций, на которых два вектора не совпадают. Пусть и два вектора в V₂. Тогда Хеммингово расстояние между векторами х, и х₂, обозна­чаемое какd_H(x₁,х₂), равно

(3.1)

где через обозначено число элементов в множестве А.

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

(3.2)

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

Пример. Простейшим примером является код-повторе­ние длины 3. Каждый информационный бит повторяется три раза. Таким образом, сообщение «О» кодируется вектором (ООО), а сообщение «1», вектором (111). Так как два вектора различаются в трех позициях, Хеммингово расстояние между ними равно 3. На рисунке 3.1 показано графическое представле­ние этого кода. Трехмерное двоичное векторное пространство соответствует 2³=8 вершинам трехмерного единичного куба. Хеммингово расстояние между кодовыми словами (ООО) и (111) равно числу вершин, через которые проходит соединя­ющий их путь. Это эквивалентно числу координат, которые необходимо изменить, чтобы преобразовать (ООО) в (111) и на­оборот. Таким образом, . Так как в этом коде только два кодовых слова, тоd_min= 3.

Двоичное векторное пространствоV₂обычно называют Хемминговым пространством. Пустьvкодовое слово кода С. Хемминговой сферой S_t(v) радиусаtс центром в точкеvявляется множество векторов (точек) вV₂на расстоянии меньше или рав­номtот центраv,

(3.3)

Рис. 3.1. (3,1,3) код-повторение в трехмерном векторном пространстве

Рис. 3.2. Хемминговы сферы радиусаt= 1, окружающие кодовые слова (3,1,3) двоичного кода-повторения

Заметим, что число слов (число векторов) в S_t(v) равно

(3.4)

Пример. На рис. 3.2 показаны Хемминговы сферы ра­диусаt= 1, окружающие кодовые слова (3,1,3) двоичного кода-повторения.

Заметим, что Хемминговы сферы для этого кода не пересе­каются, т.е. в пространстве V₂ нет векторов (или вершин в еди­ничном трехмерном кубе), принадлежащих одновременно и (000), и (111). В результате, если изменить любую одну позицию кодового слова то получится вектор, который, тем не менее, останется внутри Хемминговой сферы с центром в v. Эта идея является принципиальной для понимания и опреде­ления корректирующей способности кода С.

Корректирующей способностью (errorcorrectingcapability) t кода С называют наибольший радиус Хемминговой сферы S_t(y) для всех кодовых слов v С такой, что для любых различных пар V соответствующие им Хемминговы сферы не пере­секаются, т.е.

(3.5)

Это соответствует более распространенному определению

(3.6)

где [x]обозначена целая часть х, т.е. целое число меньше или равное х.

Заметим, что для определения минимального кодового расстояния произвольного блокового кода С в соответствии с (1.4), необходимо вычислить все2^k{2^k— 1) расстояний между различными парами кодовых слов. Это практически невоз­можно даже для сравнительно коротких кодов, например, с к = 50. Одним из важных преимуществ линейных блоковых кодов является то, что для вычисления d_mm достаточно знать только Хемминговы веса 2^к - 1 ненулевых кодовых слов.