3.2.2. Перестановочное декодирование с помощью матрицы Н
Существует другой подход к перестановочному декодированию, который позволяет сосредоточить внимание на возникновении ошибок. При основной схеме декодирования предполагается, что информационное множество не содержит ошибок, производится повторное декодирование, получается кодовое слово, которое затем сравнивается с принятой последовательностью. Если производить сравнение сложением принятой последовательности с кодовым словом, то в результате получается гипотетическая комбинация ошибок. Эта комбинация, очевидно, содержит нулевые символы в позициях информационного множества; ненулевые символы могут содержаться лишь в позициях проверочного множества. Более того, часть комбинации ошибок, содержащаяся в проверочном множестве, совпадает с синдромом. Таким образом, она является результатом повторного вычисления проверочных символов и добавления этих новых проверочных символов к принятым. Это замечание, конечно, вытекает непосредственно из рассмотрения матрицы Н. Подходящей формой матрицы Н, соответствующей данному информационному множеству, является форма, содержащая единичную матрицу в столбцах проверочного множества. Если комбинация ошибок является ненулевой только в этих позициях, то сразу получаем, что синдром будет совпадать с комбинацией ошибок. Например, матрица Н для рассмотренного в подразд. 3.2.1 кода Хемминга имеет вид
Эта матрица соответствует информационному множеству {1, 2, 3, 4}. Если принятая последовательность содержит ошибки лишь в позициях 5, 6 или 7, то синдром в точности совпадает с этой комбинацией ошибок.
Столбцы матрицы Н, образующие единичную подматрицу, можно рассматривать как окно, через которое можно посмотреть на принятую последовательность и увидеть комбинацию ошибок. Польза такой точки зрения состоит в том, что она позволяет определить потенциально корректируемые комбинации ошибок по некоторым параметрам кода. Например, в ситуации, когда
появляются случайные ошибки, можно проверить, находится ли вес гипотетической комбинации ошибок в пределах корректирующей способности кода. При возникновении пакетов ошибок можно проверить, совместима ли длина пакета (число символов между первым и последним ошибочными символами) со способностью кода исправлять пакеты ошибок. Это соображение используется для упрощения декодера Меггитта, изображенного на рис. 3.1.
Важное замечание, которое нужно сделать при рассмотрении перестановочного декодирования исходя из вычисления синдромов, состоит в том, что комбинация ошибок будет определена, если удастся найти проверочное множество, целиком содержащее эту комбинацию. Такое проверочное множество называется покрывающим комбинацию ошибок, и набор проверочных множеств, покрывающих все наборы ошибок данного типа, называется покрытием. Задача декодера состоит в том, чтобы найти проверочное множество, которое покрывает данную неизвестную комбинацию ошибок.
При поиске такого множества можно использовать два метода. Один из них состоит в предварительном выборе некоторого набора покрывающих множеств, приводящего к исправлению определенного множества ошибок Затем такой набор просматривается в соответствии с некоторым детерминированным правилом определения комбинации ошибок, имеющей наименьший вес. Достоинство этого метода состоит в том, что вычисления, необходимые для поиска проверочной матрицы, соответствующей данному информационному множеству, можно выполнить заранее и поместить результат в память декодера. При втором методе следующее исследуемое информационное множество выбирается на основе предыдущих вычислений или с использованием имеющейся дополнительной информации. Хотя при этом каждая итерация может потребовать большего объема вычислений, общее число итераций может иногда уменьшиться. Каждый из этих методов будет подробно рассматриваться далее.
