3.2. Перестановочное декодирование

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

3.2.1. Общий алгоритм декодирования

Информационное множество группового -кода — это любое множество к символов кодового слова, которые можно

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

Прибавив первую строку к третьей и четвертой, можно преобразовать эту матрицу к виду

Тем самым мы поменяли местами первый и пятый столбцы и изменили шестой столбец. Мы видим, что символы образуют информационное множество.

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

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

1) выбрать несколько различных информационных множеств в соответствии с некоторым правилом;

2) построить кодовое слово для каждого из множеств, предположив, что символы информационного множества приняты без ошибки;

3) сравнить каждое гипотетическое кодовое слово с принятой последовательностью и выбрать ближайшее кодовое слово (находящееся на наименьшем расстоянии).

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

Рис. 3.3. Общий алгоритм перестановочного декодирования

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

В качестве примера применения этого метода декодирования рассмотрим -код Хемминга с информационными множествами Три порождающие матрицы, отвечающие этим трем информационным множествам, имеют вид

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

и при передаче произошла ошибка в четвертой позиции, так что

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

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

Использование трех информационных множеств, указанных в этом примере, позволяет исправито любую одиночную ошибку. Это утверждение становится очевидным, если заметить, чтоодиночная ошибка в символах 1, 2 или 3 будет исправлена множеством ошибка в символах 5, 6 или 7 — множеством а ошибка в символе 4 — множеством

Описанную процедуру можно слегка изменить с тем, чтобы она включала в себя мягкое решение. Используя квантование на восемь уровней с равномерной метрикой от 0 до 7, удобно представлять кодовое слово символами 0 и 7 (а не 0 и 1). В этом случае расстояние между кодовым словом и произвольной последовательностью равно сумме абсолютных значений разностей отдельных компонентов. Предположим, что передана последовательность

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

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

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

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

и декодер с жестким решением декодировал бы ее в кодовое слово

что, очевидно, неверно.

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

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

поскольку каждое из трех информационных множеств содержало бы ошибки. Эта трудность преодолевается, конечно, добавлением дополнительных информационных множеств. Можно показать, что в случае -кода Хемминга для исправления всех потенциально корректируемых комбинаций ошибок (при квантовании на восемь уровней) требуется восемь информационных множеств. Этот вопрос подробнее обсуждается в гл. 4.