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

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

Таким образом, код #1, минимальное расстояние которого равно 3, является кодом, исправляющим одну ошибку.

С другой стороны, если произошло больше чем d/2 ошибок, то принятый вектор может быть (или не быть) ближе к некоторому другому кодовому слову, а не к правильному. Если это произойдёт, то декодер ошибется и выдаст неправильное кодовое слово. Это называется ошибкой декодирования. Конечно, с хорошим кодом это случается редко.

Пока что мы предположили, что декодер всегда будет пытаться найти ближайшее кодовое слово. Эта схема декодирования, называемая полным декодированием, хороша для сообщений, которые не могут быть переданы еще раз, таких как фотография с Марса или старая магнитная лента. В таком случае мы хотим извлечь из принятого вектора как можно больше.

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

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

171

7.6. Математическое введение к линейным кодам

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

Если основная операция коммутативна, группа называется коммутативной или абелевой. Число элементов в конечной группе называют порядком группы. Для построения двоичных кодов используется коммутативная операция сложения по модулю 2, при выполнении которой число разрядов кода не увеличивается. Поэтому множество n - разрядных комбинаций двоичного кода является конечной абелевой группой.

Подмножество группы, само являющееся группой относительно операции, заданной в группе, называют подгруппой.

ные классы, можно разложить всю группу на смежные классы по подгруппе .

Таким образом, если является (п, k) линейным кодом над полем из q элементов. Для любого вектора а множество

+= { + }

называется смежным классом (или сдвигом) кода . Лю-

бой вектор b находится в некотором смежном классе (например, в b + ). Два вектора а и b лежат в одном и том же смежном классе, тогда и только тогда, когда (а - b) . Каждый смежный класс содержит qk векторов.

Определение. Два смежных класса либо не пересекаются, 172

где t = qn-k - 1.

Предположим теперь, что декодер принимает вектор у. Этот вектор должен принадлежать некоторому смежному классу в разложении (7.15), скажем, у = аi + х (х ). Что собой представляют "возможные векторы ошибок е, которые могли произойти? Если было передано кодовое слово х', то вектор ошибок - это вектор

е = у - х' = ai + x - x' = ai + x'' = ai + .

Отсюда мы заключаем, что возможными векторами ошибок являются в точности все векторы из смежного класса, содержащего у.

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

Таким образом, при данном у стратегия декодера заключается в выборе из смежного класса, содержащего у, вектора е с наименьшим весом и в декодировании у как х = у - е. Вектор из смежного класса, имеющий минимальный вес, называется лидером смежного класса. (Если же имеется более одного вектора с минимальным весом, то выберем случайным образом любой из таких векторов и назовем его лидером смежного класса).

173

7.7. Стандартное расположение

Будем считать, что в расположении (7.15) векторы аi являются лидерами смежных классов.

Полезным способом описания работы декодера является таблица, названная стандартным расположением для кода.

Первая строка ее состоит из самого кода с нулевым кодовым словом с левой стороны. Другими строками являются другие смежные классы ai + , расположенные в том же самом порядке и с лидерами этих классов с левой стороны:

последовательность символов может быть представлена в виде:

Y Xi E,

где E – вектор ошибки, содержащий единицы на позициях, отвечающих искаженным символам кодового слова, и нули – неискаженным. Реализация прямого метода декодирования по минимуму расстояния предполагает предварительное создание

таблицы, содержащей все (2n) возможные варианты вектора наблюдений Y, т.е. определенным образом распределение всех векторов пространства размерности n. Заполнение таблицы осуществляется следующим образом (см. таблицу 7.1). Пер-

вая строка содержат все кодовые вектора Xi ,i 1, M . Из

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

Y Xi E1,i 1, M .

174

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

Y Xi E2,i 1, M .

Аналогичным образом осуществляется заполнение и остальных строк, причем в качестве образующего вектора берется такой, который является ближайшим к нулевому и отсутствует в предыдущих строках таблицы. Пусть, например, на j– шаге

таковым служит E j , тогда в j–й строке будут содержаться вектора

Y Xi E j,i 1, M

Процедура заполнения завершится тогда, когда после l - го шага не останется ни одного вектора, не вошедшего в таблицу. Таблица слов, составленная подобным образом, получила наименование стандартного расположения.

Горизонтальная черта, проведенная в таблице 7.1, учитывает кодовое расстояние d , присущее коду. Если исправляющая способность кода велика, то вполне вероятно, что заполнение таблицы будет завершено до превышения кодового рассто-

175

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

Пример. Код #4 (продолжение). (4,2)-код с порождающей матрицей

(пока не обращайте внимания на последний столбец в таблице

7.2).

Заметим, что таблица 7.2 содержит все 16 векторов длины 4, которые разбиты на четыре смежных класса, образующих строки таблицы, и лидеры этих классов расположены в левом столбце.

Теперь о том, как декодер использует стандартное расположение. Когда принят у (например, 1111), определяется его положение в таблице. Затем декодер принимает решение, что вектор ошибок е - это лидер смежного класса, расположенный в первом столбце в той же строке, что и у, т. е. элемент (0100),

176

и у декодируется в кодовое слово х = у - е = 1011, которое находится в начале столбца, содержащего у (соответствующее сообщение равно 10).

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

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

Существуют два основных класса декодеров, использующих стандартное расположение: полные и неполные декодеры. Полный декодер всегда сопоставляет наблюдаемой последовательности ближайшее кодовое слово, что достигается определением столбца стандартного расположения, в котором находится вектор наблюдения, а затем выбирается кодовое слово в его верхней позиции. Неполный декодер, аналогично полному, может сопоставить принятой последовательности кодовое слово, но только тогда, когда принятая комбинация лежит выше горизонтальной линии. В противном случае принимается решение об отказе от декодирования, поскольку в принятой комбинации содержится более t ошибок.

7.8. Синдром

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

S = H·yT,

который называется синдромом у.

Свойства синдрома.

1)S представляет собой вектор-столбец, длины n—k.

2)Синдром вектора у, S = Н·ут, равен нулю, если и только если у — кодовое слово (по определению кода). Поэтому, если никаких ошибок не произошло, синдром вектора у равен нулю (но не обратное). В общем случае, если у = х + е, где

х , то

3)Если для двоичного кода имеются ошибки на позициях

сномерами а, b, с,..., так что е = 0 ... 010 ... 1 ... 1 ... 0, то из

a b c

(7.16) получаем, что

где Нi - i-й столбец H.

Теорема 1. Для двоичного кода синдром равен сумме тех столбцов Н, где произошли ошибки. (Таким образом, S называется синдромом, так как он выделяет совокупность ошибок).

Два вектора находятся в одном и том же смежном классе кода , если и только если они имеют один и тот же синдром. Действительно, u и v находятся в одном смежном классе, если и только если (u - v) , что эквивалентно Н·(u—v)T = 0 или Н·uT = H·vT. Следовательно, справедливо утверждение, приведенное ниже.

Теорема 2. Имеется взаимно однозначное соответствие между синдромами и смежными классами.

Например, смежные классы в таблице 7.2 занумерованы их синдромами.

Окончательно, метод синдромного декодирования предполагает последовательное осуществление следующих операций:

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

S YHT ;

–для вычисленного значений синдрома в таблице лидеров смежных классов находится оценка вектора ошибки Eˆ ;

–вычитание из Y вектора Eˆ позволяет получить оценку кодового вектора в виде Xˆ Y Eˆ .

Пример. Каноническая проверочная матрица линейного (5,2) кода имеет вид

178

1 1 1 0 0

H 1 0 0 1 0 .

0 1 0 0 1

Тогда с учетом (7.16) можно определить значения лидеров смежных классов и соответствующих им синдромов, которые сведены в таблицу 7.3.

Таблица 7.3.

Пусть передавалось кодовое слово X (11011). В результате действия помех на приемной стороне наблюдателю стал доступен вектор Y (01011). Декодер осуществляет следующую последовательность операций:

1. Вычисление синдрома:

1 1 01 0 1

S YHT [01011] 1 0 0 [110].0 1 0

0 0 1

2.По вычисленному значению синдрома из таблицы 7.3 находится лидер смежного класса – Eˆ (10000).

3.Осуществляется процедура декодирования вектора наблюдения Y

Xˆ Y Eˆ [01011] [10000] [11011],

где учтено, что поэлементное вычитание осуществляется по mod 2.

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

179

конфигурации. Декодер же «настроен» на исправление наиболее вероятной ошибки, т.е. ошибки с малым весом (или малой кратности). Если же произойдет ошибка большей кратности, чем та, которую рассчитан код, декодер вынесет неправильное решение. Так, в условиях примера значению синдрома S [110] отвечает не только вектор ошибки вида E (10000), но и E (00110). Если фактически происшедшая ошибка соответствует вектору E (00110), то на приемной стороне будет принят вектор Y X E (11011) (00110) (11101). На осно-

вании вычисленного синдрома декодер примет решение, что произошла ошибка вида Eˆ (10000), и значит, было передано

ствует действительности. Как видно, декодер не только не исправил ошибок, но и внес еще одну дополнительно.

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

7.9. Вероятность ошибки

Когда декодирование использует стандартное раcположение, выбранный декодером вектор ошибок всегда представляет собой один из лидеров смежных классов. Декодирование является правильным, если и только если истинный вектор ошибок в действительности является лидером смежного класса. Если это не так, то декодер совершает ошибку и выдает неправильное кодовое слово (хотя при этом некоторые из ин-

180