2.1.6. Синдром

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

Как отмечалось в гл. 1, таблица декодирования (или стандартное расположение) лежит в основе работы декодера. Один из методов построения декодера состоит в том, чтобы записать эту таблицу в постоянную память. Принятое слово является адресом, а кодовое слово — информацией, хранящейся по этому адресу. Сложность такой схемы можно заметно уменьшить, если удастся найти простое правило, определяющее класс смежности, в котором лежит принятая последовательность длины Тогда будет нужна существенно меньшая таблица, в которой будем искать требуемый лидер класса смежности или комбинацию ошибок. Затем эта комбинация ошибок будет складываться по модулю 2 с принятой последовательностью. Покажем, что такой подход действительно оказывается возможным.

Предположим, что принятое слово содержит комбинацию ошибок Тогда можно записать в виде

Умножив принятое слово на матрицу Н, получим вектор (называемый синдромом):

Таким образом, проверочная матрица позволяет определить вектор, зависящий только от комбинации ошибок. Заметим

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

Таблица 2.1. (см. скан) Стандартное расположение для -кода, исправляющего одиночные ошибки

Рассмотрим в качестве примера стандартное расположение, показанное в табл. 2.1. Это расположение соответствует -коду, задаваемому матрицей Н из (2.1). Заметим, что синдром, соответствующий второй строке стандартного расположения (одна ошибка в первом символе), совпадает с первым столбцом матрицы Н, синдром, соответствующий третьей строке, — со вторым столбцом . Синдром, соответствующий последней строке стандартного расположения, равен сумме первого и третьего столбцов матрицы Н. Читатель может заметить, что все синдромы различны и все возможные тройки исчерпаны.

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

последнее свойство иногда легче использовать.