4.5.3. Частичное синдромное декодирование

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

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

где матрица, состоящая из строк и к столбцов; -компонентный вектор; -компонентный вектор. Вектор называется частичным синдромом. Согласно (4.23) выполняются следующие соотношения:

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

В качестве примера рассмотрим код с восемью информационными символами и предположим, что удовлетворительным является значение Предположим, что матрица может быть разбита в соответствии с (4.23), причем

и что частичный синдром имеет вид

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

Таблица 4.2. (см. скан) Расположение пар ошибок

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

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