Стандартное расположение. Синдромное декодирование линейных кодов

 

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

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

, (6.10)

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

.

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

.

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

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

Таблица 6.6.

 

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

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

Пример 6.9.1. Обратимся к (5,2) линейному коду, рассмотренному в примере 6.7.2. Данный код состоит из четырех слов: {00000, 10110, 01101 и 11011} и способен исправить любую однократную ошибку. Таблица 6.7 содержит все различные слова пространства размерности 5 в соответствии со стандартным расположением. Вектора, отличающиеся от кодовых более чем в позиции, отделены горизонтальной чертой.

 

Таблица 6.7.

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

 

 

Пример 6.9.2. Для декодирования с помощью стандартного расположения (32,26) кода Хэмминга, используемого в СРНС GPS NAVSTAR, требуется 17 Гбайт памяти. При использовании быстродействующего микропроцессора со временем обращения к памяти, равным 100 нСек, процедура декодирования может занять до 429 сек, тогда как обновление информации осуществляется со скоростью 1 слово/сек.

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

, (6.11)

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

Учитывая (6.10), расстояние между вектором наблюдения и кодовым словом определятся соотношением

.

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

Поскольку размерность вектора синдрома , а вектора ошибки – , то одному и тому же значению могут отвечать различные конфигурации .

Лемма 6.9.1. Любые два различных вектора ошибок и отвечают одному и тому же значению синдрома, если их разность дает кодовое слово, т.е. .

Доказательство. Пусть и . Тогда из равенства синдромов получаем, что с учетом (6.10) и (6.6) . Последнее возможно только в том случае, если – кодовый вектор.

Из леммы 6.9.1 непосредственно следует, что одному и тому же значению синдрома соответствуют ровно векторов ошибок.

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

Очевидно, что число смежных классов и различных значений синдрома совпадает и равно .

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

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

Следовательно, вычисление синдрома позволяет определить вектор ошибки с точностью до смежного класса, а значит сократить число конкурирующих гипотез в раз. Выбор же в качестве оценочного значения вектора лидера этого класса завершает процедуру нахождения минимального веса. Таким образом, для декодирования вектора наблюдения достаточно иметь заранее вычисленную таблицу соответствия между значениями синдрома и лидерами смежных классов, содержащую записей. Ясно, что объем памяти, необходимой для содержания указанной таблицы, значительно меньше, чем в случае запоминания таблицы стандартного расположения (требует хранения слов) либо множества кодовых слов ( записей), которые необходимы для прямой реализации декодирования по минимуму расстояния. В частности, объем памяти, потребной для выполнения синдромного декодирования в условиях примера 6.9.2, составляет всего байта. Более того, для двоичного кода Хэмминга таблица декодирования вообще не нужна, поскольку, учитывая метод построения его проверочной матрицы, вычисленное значение синдрома непосредственно дает номер позиции искаженного символа в двоичном представлении.

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

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

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

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

Проиллюстрируем действие этого алгоритма для кода, рассмотренного в примере 6.7.2.

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

.

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

Таблица 6.8.

 

 

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

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

.

2. По вычисленному значению синдрома из табл. 6.8. находится лидер смежного класса – .

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

,

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

В заключение следует отметить, что работа устройства, реализующего алгоритм синдромного декодирования, не лишена возможных ошибок. Последнее обусловлено тем, что одному и тому же значению синдрома отвечают ошибки разной конфигурации. Декодер же «настроен» на исправление наиболее вероятной ошибки, т.е. ошибки с малым весом (или малой кратности). Если же произойдет ошибка большей кратности, чем та, на которую рассчитан код, декодер вынесет неправильное решение. Так, в условиях примера 6.9.3 значению синдрома отвечает не только вектор ошибки вида , но и . Если фактически происшедшая ошибка соответствует вектору , то на приемной стороне будет принят вектор . На основании вычисленного синдрома декодер примет решение, что произошла ошибка вида , и значит, было передано слово , что не соответствует действительности. Как видно, декодер не только не исправил ошибок, но и внес еще одну дополнительно.