Главная > Помехоустойчивое кодирование > Коды, исправляющие ошибки
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.6. Эквивалентность линейных кодов

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

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

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

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

где -некоторая матрица перестановки. Эта матрица называется А-перестановкой, соответствующей 5. (Заметим, что матрица зависит также от выбора матрицы

Для каждого I среди строк матрицы имеется какая-либо, скажем, строка, в которой находится вектор, содержащий нули во всех позициях, кроме позиции. Поэтому строка матрицы 5 появляется как строка матрицы следовательно, различные матрицы 5 приводят к различным перестановкам Далее, если невырожденные матрицы размерности к X к, то

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

Рассмотрим теперь результат применения Л-перестановки к строкам матрицы Пусть Тогда

Так как матрица перестановки является ортогональной матрицей, то и

Поэтому применение А-перестановки к строкам эквивалентно применению другой, но связанной с ней А-перестановки, к столбцам матрицы С.

Выбор нового базиса и порождающей матрицы для группового кода соответствует умножению слева порождающей матрицы на некоторую невырожденную матрицу Ненулевые кодовые векторы для порождающей матрицы являются строками матрицы

т. е. являются строками матрицы переставленными с помощью Таким образом, выбор нового базиса эквивалентен применению

Л-перестановки к кодовым словам. Очевидно, что эти рассуждения могут быть проведены и в обратную сторону.

Аналогично столбец типа матрицы , в которой перечислены все кодовые слова, совладает с столбцом матрицы С. Поэтому в матрице этот столбец совпадает с столбцом матрицы Но где и поэтому столбец матрицы С, который соответствует столбцу матрицы является тем самым столбцом, который матрица перестановки переводит в столбец. Следовательно,

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

<< Предыдущий параграф Следующий параграф >>
Оглавление