У. Питерсон - Коды, исправляющие ошибки (1267328), страница 13
Текст из файла (страница 13)
Если У есть (п,й)-код. то à — это (п,п — й)- код. Если код является пространством строк некоторой матрицы, то двойственный к нему код — нулевое пространство этой матрицы и наоборот. Теорема 3.1. Пусть т' †линейн код, который совпадает с нулевым пространством матрицы Н. Тогда каждому кодовому слову веса Хэмминга и соответствует соотношение линейной зависимости, связывающее гв столбцов матрицы Н, и, наоборот, каждому соотношению линейной зависимости, включающему гв столбцов матрицы Н, соответствует кодовое слово веса и. Доказательство. Вектор т = (аь ам..., а„) является кодовым словом тогда и только тогда, когда чНт = О, илн, если обозначить 1-й вектор-столбец матрицы через пь тогда и только тогда, когда ~„а,(т, =О.
! Это соотношение линейной зависимости связывает столбцы матрицы Н, причем число столбцов матрицы, которые входят с ненулевыми коэффициентами, равно числу ненулевых компонент а; вектора тс Это число в точности равно весу вектора ч. Аналогично коэффициенты любого соотношения линейной зависимости, связывающего столбцы матрицы Н, являются компонентами вектора, который должен принадлежать нулевому пространству матрицы Н. Ч. т.
д. Следствие 3.1. Блоковый код, являющийся нулевым пространством матрицы Н, имеет минимальный вес (и„следовательно, минимальное расстояние), равный самое меньшее гь, тогда и только тогда, когда любая совокупность ш — 1 или меньшего числа столбцов П является линейно независимой. Отметим различие между этим условием и определением ранга матрицы. Если ранг по столбцам матрицы больше или равен г, то должна существовать по крайней мере одна совокупность из г столбцов, которые линейно независимы. При изучении свойств кодов, исправляющих ошибки, надо иметь в виду, что для любого канала с независимымн ошибками два кода, отличающиеся только расположением символов, имеют одну и ту же вероятность ошибки.
Вообще между двумя такими кодами имеется очень тесная связь, и поэтому они называются эквивалентными. Более точно, если у — пространство строк мат- ицы С, то код Г эквивалентен кодУ т' тогда и только тогда, когда пространство строк матрицы С; полученной из матрицы С перестановкой столбцов. Таким образом, перестановка столбцов порождающей матрицы кода приводит к порождающей матрице ля эквивалентного кода.
В результате любой элементарной опеации над строками матрицы получается матрица с тем же самым 1пространством строк, и поэтому измененная матрица является поождающей матрицей для того же самого кода. Если одна матрица может быть получена из другой путем комбинации элементарных операций над строками и перестановок столбцов, то эти две матрицы называются комбинаторно-эквивалентныии.
дюбая порождающая матрица С комбинаторно-эквивалентна некоторой матрипе С", имеющей ступенчатую каноническую форму. Матрица С' может быть получена из матрицы С следующим образом: начиная с первой строки с каждой из й строк матрицы С произведем следующие операции: 1. В 1-й строке найдется по меньшей мере один ненулевой элемент, поскольку строки линейно независимы. Предположим, что первый отличный от нуля элемент находится в 1-м столбце.
Разделим каждый элемент (-й строки на ам. В результате новый элемент матрицы а,'. станет равен единице. 2. К каждой 1-й строке (1чь!) прибавим 1-ю строку, умноженную на ( — аи). В результате в 1чм столбце 1-я строка будет содержать единицу, а все остальные строки — нули. Заметим, что как только какой-нибудь столбец будет содержать единицу в одной из строк и нули в остальных строках, то ни первая, ни вторая операции над строками уже не смогут изменить этот столбец. Таким образом, после того как эти операции будут троделаны над каждой строкой матрицы, получится матрица С', :одержащая й столбцов, каждый из которых содержит единицу т й — 1 нулей, причем единица появится обязательно в каждой тр оке. Итак, поскольку С' может быть получена из С с помощью операций над строками, то они порождают один и тот же код.
Далее |ерестановков столбцов можно сгруппировать слева А столбцов, одержащих единицы в качестве первых ненулевых элементов таждой строки, так чтобы онн образовали единичную матрицу эазмерности й ХА, в результате чего получится комбинаторно-экэивалентная матрица С" вида 1й...О рп ... рь„,— () 1 ... О рм ... рт, Си = [1эР1 (3.4) Такая форма матрицы называется приведению-ступенчатой. (В этих вопросах не выработано единообразной терминологии.) Таким образом, для каждой порождающей матрицы б существует комбинаторно-эквивалентная ей матрица б', имеющая приведенно-ступенчатую форму, и каждый код эквивалентен пространству строк некоторой матрицы, имеющей приведенно-ступенчатую форму. Пусть теперь ч =(а!,а„...,а„) — произвольный набор длины й.
Рассмотрим вектор н, являющийся линейной комбинацией строк матрицы б" с элементом а, в качестве !-го коэффициента; и = чб" = (а„а„..., аы со с„..., с„„), (3.5) где А с! — — ~ а,рц, ! 1 (3.6) пНт= 0 = ( — ~, а,р, + с„..., ~, а!р; „х + с„л), (3.7) ! ! что в точности совпадает с соотношениями (3.6). Связь между б и Н особенно ясно видна из этого соотно!пения, если заметить, что в обоих случаях рп — элемент из !-й строки и (что столбца матрицы Р— является как раз коэффициентом при с-м информационном символе а; в сумме, которая задает (хй проверочный символ с,.
Таким образом, первые й компонент кодового вектора могут быть произвольно выбранными информационными символами, а каждая из последних п — й компонент является линейной комбинацией первых я компонент. Благодаря этому кодирование сильно упрощается. Код такого типа называется систематическим кодом; первь!е й компонент называются информационными символами, а последние и — й компонент называют избыточными или проверочными символами. Таким образом, верна следующая теорема: Теорема 3.2. цаждый линейный код эквивалентен систематическо.ну коду.
Существует простой способ нахождения проверочной матрицы кода, если задана порождающая матрица кода в прнведепно-ступенчатой форме. Теорема 3.3. Если )л — пространство строк матрицы б = (1яР], где 1л — единичная матрица размерности й;к', й, а Р— матрица разл!ерности я;х,(п — й), то Р является нулевыл! пространством матрицы Н = ( — Рт!„х], где 1 ь — единичная матрица размерности (и — й) Х (и — Й), Доказательство. Легко проверить, что бНт = О, и поскольку сумма рангов матриц б н Н равна и, то пространство строк матрицы б является нулевым пространством для Н. Ч.
т. д. Бели и =(а!,а„...,аыс!,см...,с х) — кодовый вектор, то !1 ример. Порождающая матрица 10011 С= О1О(О =(1зР) 0010! я кода, использованного в предыдущих примерах, задана в приведенно-ступенчатой форме. Если положить то СНт = НСг = О, и пространство строк каждой матрицы является нулевым пространством для другой матрицы. В этом случае первые три компоненты каждого кодового слова (аьаз,аз,аь а ) могут быть выбраны произвольно.
Два оставшихся проверочных символа удовлетворяют уравнениям аз=а, + а,, а,=а, +а„ что видно по любой из двух матриц. В матрице С четвертый столбец содержит единицы в первой и второй строках, и поэтому первый и второй информационные символы входят в проверочной уравнение, используемое для вычисления четвертого символа, Что касается матрицы Н, то, поскольку каждая сгрока матрицы принадлежит нулевому пространству кода, каждое кодовое слово ортогонально каждой строке матрицы Н. В частности, для первой строки ! а, + 1а, + Оаз + 1а, + Оар = 0; это уравнение может быть рещено относительно аь З.З.
Описание древовидных линейных кодов при помощи матриц Пусть через Рз обозначена матрица, йр строк которой являются линейно независимыми полубесконечными векторами над ОР(д), где СГ(у) — конечное поле, содержащее д элементов (см. гл. 8), В дальнейшем предполагается, что первые (! — 1)пр столбцов матрицы Г, являются нулевыми и что некоторые элементы в столбцах . "номерами от (! — !)пр+ 1 до !пр ненулевые. Тогда древовидный линейный код определяется как совокупность полубесконечных векторов-строк, образующих пространство строк матрицы Г, Ез гз (3.8) Матрица С называется порождающей натрицей кода и представ- ляет собой матрицу вида "а (3.9) где заштрихованное пространство заполнено нулями. Полубесконечная кодовая последовательность с древовидного линейного кода, порождаемого матрицей С, получается из полу- бесконечной информационной последовательности 1 в соответствии с равенством ~З. И)) Требуется, чтобы некоторые элементь| С были нулями, поскольку в древовидном коде 1-й информационный блок не может влиять на кодовые блоки, соответствующие 1, 2, ..., г — ! информационным блокам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
