4.6. Декодирование на основе упорядоченной статистики

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

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

Алгоритм работы такого декодера (назовем его основным) рассмотрим на примере кода БЧХ (15;5;7). Порождающая матрица кода в систематической форме приведена в (4.5) и будет представлена здесь для удобства

.

Пусть от источника информации на вход кодера  поступает вектор вида 1 1 0 1 0 .

В результате умножения вектора на порождающую матрицу на выходе кодера формируется последовательность:

1 1 0 1 0 1 1 0 0 1 0 0 0 1 1.

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

.

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

В результате передачи кодового вектора по каналу связи и наложения на него вектора ошибок получаем последовательность вида

.

Эта последовательность фиксируется жестким декодером. В мягком декодере каждому жесткому решению приписывается степень его надежности. Пусть оценки надежности символов выражаются целыми числами от 0 до 7. Вектор  вместе с такими оценками представлен в табл. 4.11.

Табл. 4.11 Представление кодовой комбинации совместно с оценками надежности

Следуя по  в порядке возрастания номеров символов, декодер сортирует их по убыванию ИДС. Результат такой работы декодера представлен  в табл. 4.12.

Табл. 4.12 Результат работы декодера по упорядочению символов статистики

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

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

Выполняя ,  получим новую матрицу  размерности

.

 В этой матрице может быть утрачено свойство линейной независимости строк, которое обязательно для образования эквивалентного кода.

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

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

.

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

Вычисление детерминанта квадратной матрицы является достаточно емкой процедурой с точки зрения объема вычислений. Оценим максимальное число операций, необходимых для определения детерминанта квадратных матриц заданной размерности и полученные для различных значений  результаты сведем в табл. 4.13.

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

.

Современные процессоры тратят на операцию сложения до 2 нс, а на операцию умножения – до 180 нс.  в декодере осуществляется умножение единиц и нулей,  будем считать, с некоторой долей условности, что на операцию умножения операндов будет тратиться тоже 2 нс. Таким образом, на вычисление указанного определителя будет потрачено порядка 6 нс. Исходя из этих условий, в табл. 4.13 представлены данные оценки временных затрат при вычислении определителей других размерностей.

Табл. 4.13  Временные интервалы для оценки определителей

Из табл. 4.13 следует, что незначительное увеличение размерности квадратной матрицы приводит к существенному увеличению времени вычисления определителя.

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

.

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

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

.

После это шага декодер из табл. 4.12 извлекает часть «нового вектора»   1 1 0 0 0 (первые пять позиций) и кодирует ее с использованием  порождающей матрицы . Учитывая, что на месте информационных разрядов, после указанных преобразований, находятся наиболее надежные символы, декодер формирует вектора эквивалентного кода, который фиксируется как некоторая разрешенная последовательность, не содержащая ошибок.

Указанный вектор будет иметь вид

                                     1  1  0  0  0  1  1  1  0  0  1  1  0  0  1.                      (4.14)

Складывая  вектор (4.14) с «новым вектором» из табл. 4.13, получим предварительную версию вектора ошибок,  образец которой представлен в табл. 4.14.

Табл.4.14 Процедура формирования предварительной версии вектора ошибок

Результат работы декодера представлен в табл. 4.15.

Табл. 4.15  Результат работы декодера по обратному упорядочению символов

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

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

Пусть известна весовая структура кода (как правило, для коротких кодов весовой спектр кода известен). Код БЧХ (15,5,7) имеет кроме чисто нулевого и чисто единичного вектора по 15 векторов веса 7 и 8. Обозначим представители указанных значений,  как  и .

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

,

при = 7; 8.

Для кода БЧХ (15,5,7) = 385 при общем числе вариантов , что составляет 12,8 %. Следовательно, повторный поиск нелинейного соотношения строк порождающей матрицы не приводит к существенному снижению показателей эффективности разработанного алгоритма. С увеличением  это влияние уменьшается.