Вопрос 1. Систематические коды

Обратное преобразование линейного кода

, (1.1)

где

получают передаваемое сообщение I ₁_x _k.

Можно облегчить процесс декодирования и сделать С более наглядным.

При изучении свойств кодов, исправляющих ошибки, надо иметь в виду, что для любого канала с независимыми ошибками два кода, отличающиеся только расположением символов, имеют одну и ту же вероятность ошибки. Вообще между двумя такими кодами имеется очень тесная связь, и поэтому они называются эквивалентными. В результате любой элементарной операции ^{^[1]} над строками матрицы получается матрица с тем же самым пространством строк, и поэтому измененная матрица является порождающей матрицей для того же самого кода.

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

Любая порождающая матрица G комбинаторно-эквивалентна некоторой матрице G’, имеющей ступенчатую каноническую форму:

1. Первый ненулевой элемент каждой строки равен «1»;

2. Каждый столбец, содержащий первый ненулевой элемент некоторой строки, в качестве всех остальных элементов содержит нули;

3. первый ненулевой элемент каждой строки стоит правее первого ненулевого столбца каждой предыдущей строки.

4. Все нулевые строки расположены ниже всех ненулевых строк.

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

Перестановкой столбцов можно образовать приведено-ступенчатую матрицу: сгруппировать слева k столбцов, содержащих единицы в качестве первых ненулевых элементов каждой строки, так чтобы они образовали единичную матрицу размерности k x k, в результате чего получится комбинаторно-эквивалентная матрица G" вида

Таким образом, для каждой порождающей матрицы G существует комбинаторно-эквивалентная ей матрица G", имеющая приведенно-ступенчатую форму, и каждый код эквивалентен пространству строк некоторой матрицы, имеющей приведенно-ступенчатую форму.

Следует обратить внимание, что матрица G” порождает другой код, но эквивалентный исходному по помехоустойчивости.

Тогда пусть I₁_x _k = (I₁,I₂,..., I_k) – произвольный набор длины k. Рассмотрим вектор С:

где

Таким образом, первые k компонент кодового вектора могут быть произвольно выбранными информационными символами, а каждая из последних n — k компонент является линейной комбинацией первых k компонент.

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

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

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

Существует теорема: Каждый линейный код эквивалентен систематическому коду.

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

Теорема. (О проверочной матрице). Если V’— пространство строк матрицы G” = [E_kP], где E_k— единичная матрица размерности k x k, a Р— матрица размерности k x (n — k), то V’ является нулевым пространством матрицы Н” = [ – Р^ТE_n_-_k], где E_n_-_k — единичная матрица размерности (n - k) x (n - k).

Здесь уместно отметить, что «– P» это матрица, такая, что P + (–P) = 0. Для двоичного исчисления «–P» = P.

Пример. Порождающая матрица задана в приведенно-ступенчатой форме.