Синдромное декодирование линейных кодов

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

Дело в том, что в попытках реализовать декодер напрямую (храня в памяти таблицу всех слов и сравнивая последние с вектором наблюдения yдля отыскания слова, ближайшего к нему), требования к объему памяти и/или быстродействию вычислений нередко противоречат реальности.

Пример 4.8.1 При прямом построении декодера (32,26) кода Хэмминга системы GPS понадобилось бы 256 Мбайт памяти. С процессором, выполняющим 10⁷ операций в секунду (обращение к памяти, вычисление расстояния, сравнение с предыдущими данными) декодирование одного слова заняло бы около шести секунд, в то время как каждую секунду передается более одного слова.

Введем новое понятие: (n–k)-элементный вектор

где H – проверочная матрица кода U, называется синдромом (или синдромным вектором). Всего для любого линейного двоичного кода возможны 2^n-k различных значений синдрома.

Представим вектор наблюдения y как сумму переданного кодового вектора u и вектора ошибки e:

.

В случае ДСК вектор ошибки содержит единицы на искаженных позициях u и нули на неискаженных.

Поскольку d(y,u)=W(y–u)=W(e), последнее представление yпозволяет следующим образом интерпретировать декодирование по минимуму расстояния: достаточно найти такой вектор ошибки ê минимального веса (W(e)=min), вычитание которого из y даст кодовый вектор. Последний и будет принят за оценку переданного кодового слова: y–ê=û.

Любые два вектора ошибки, разность которых равна какому-либо кодовому вектору, имеют один и тот же синдром. Поэтому одним и тем же синдромом обладают в точности M=2^k векторов ошибки. Множество всех таких векторов именуют смежным классом. Очевидно, количество смежных классов равно числу различных значений синдрома 2^n–k. Вычисление синдрома позволяет определить вектор ошибки с точностью до смежного класса, т.е. сократить число тестируемых векторов ошибки в 2^n–k раз. После того, как смежный класс найден, остается лишь отыскать в нем вектор ошибки минимального веса. Этот вектор называют лидером смежного класса. Конечно, все 2^n-k лидеров смежных классов данного кода можно вычислить заранее и иметь в памяти в виде таблицы. При этом потребуются 2^n–k позиций таблицы вместо 2^k в прямой схеме декодера.

Для высокоскоростных кодов выигрыш в аппаратной сложности и временных затратах может оказаться гигантским. Для данных примера 4.8.1 экономия измерялась бы цифрами порядка 2²¹ раз по обоим ресурсным показателям. В действительности же для декодирования кодов Хэмминга вообще не нужны никакие таблицы, так как вычисленный синдром является попросту двоичным номером искаженного символа (см. пример далее).

Резюмируя, синдромное декодирование сводится к следующим операциям:

1. Для вектора наблюдений y вычисляется синдром: s= yH^T;

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

3. Оценка вектора ошибки ê вычитается из наблюдения y,давая в результате оценку принятого кодового вектора û.

Пример 4.8.2 Проверочная матрица (15,11) кода Хэмминга

.

Допустим, принято наблюдение y=(101100110101100). Тогда синдром s^T есть вектор, равный сумме строк H^Т с номерами 1,3,4,7,8,10,12,13 (позициями ненулевых символов в y): s=(0100). Так как код Хэмминга исправляет любую однократную ошибку, не обнаруживая и не исправляя более никаких ошибок, вектор некоторой однократной ошибки должен иметь именно этот синдром. Понятно, что такой ошибкой является искажение второго символа кодового слова. Значит, декодированный кодовый вектор получается изменением второго символа в наблюдении y: û=(111100110101100).

Тема 5 Циклические коды