Синдром вектора

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:59, 14 мая 2016.

Определение

TemplateDifinitionIcon.svg Определение «Определение - Cиндром вектора»
Пусть - проверочная матрица:
для
Пусть - произвольный вектор.
- синдром (не зависит от исходного кодового слова).

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

, где:
- ошибка,
- кодовое слово с ошибкой.

Смежные классы, синдром смежного класса. Лидеры смежного класса

абелева группа, где - подгруппа.

Введем смежный класс по аддитивной подгруппе .

Заметим:

- синдромы совпадают для всех векторов из одного и того же класса смежности.

TemplateTheoremIcon.svg Теорема Теорема о синдроме смежного класса
Два вектора и принадлежат одному и тому же смежному классу тогда и только тогда, когда их синдромы равны.
Доказательство

Два элемента группы и принадлежат одному и тому же смежному классу тогда и только тогда, когда есть элемент подгруппы, которой в данном случае является кодовое векторное пространство. Если кодовое пространство — это нулевое пространство матрицы , то вектор принадлежит кодовому пространству тогда и только тогда, когда:

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

Т.о. вектор является кодовым вектором тогда и только тогда, когда синдромы векторов и равны. ч.т.д.


Синдромов столько же, сколько существует смежных классов:

Декодирование по синдрому. Стандартное расположение линейного кода

Пусть — линейный -код, — нулевой вектор и — остальные кодовые векторы. Тогда таблицу декодирования можно составить следующим образом. Кодовые векторы располагаются в виде строки с нулевым вектором слева. Затем один из оставшихся наборов длины , например , помещается под нулевым вектором. (Обычно это бывает один из наборов, которые наиболее вероятно получить на выходе, если по каналу передавался нулевой вектор.) Далее строка заполняется так, чтобы под каждым кодовым вектором - помещался вектор . Аналогично в первый столбец второй строки помещается вектор и строка заполняется таким же способом. Процесс продолжается до тех пор, пока каждый возможный набор длины не появится где-нибудь в таблице. Это стандартное расположение, конечно, в точности совпадает с таблицей смежных классов. Строки являются смежными классами, а векторы в первом столбце — образующими смежных классов.

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

Процесс декодирования может быть значительно упрощен за счет использования таблицы декодирования:


Таблица строится так, что в ней приводятся образующие смежных классов и синдромы для каждого из смежных классов. После того как получен вектор, вычисляется его синдром. Затем по таблице отыскивается образующий смежного класса, являющийся предполагаемым набором ошибок; вычитание его из полученного вектора дает предположительно посланный кодовый вектор. Хотя в большинстве случаев такая процедура во много раз уменьшает требования к объему памяти при осуществлении декодирования, этот объем все-таки может быть очень большим. Например, для двоичного (100,80)-кода требуется таблица декодирования с входами, что конечно, далеко выходит за пределы разумного. Число смежных классов равно — величине, много меньшей, но тем не менее все еще совсем нереальной.

TemplateTheoremIcon.svg Теорема Утверждение
Пусть — линейный двоичный -код (т. е. групповой код), используемый для передачи по двоичному симметричному каналу. Предположим, что все кодовые векторы имеют одну и ту же вероятность быть переданными. Тогда средняя вероятность правильного декодирования совпадает с наибольшей возможной для этого кода, если в качестве таблицы декодирования используется стандартное расположение, в котором каждый образующий смежного класса имеет минимальный вес в своем классе.
Доказательство
Обозначим через вектор, стоящий в -й строке и -м столбце таблицы декодирования. Кодовое слово в верхней строке столбца обозначим через ,-. Обозначим через расстояние Хэмминга между полученным вектором и кодовым словом , в которое он преобразуется при декодировании. Тогда вероятность правильного декодирования, если было передано слово , равна

где — вероятность ошибки в канале, a . Поскольку имеется кодовых слов, которые предполагаются равновероятными, то при осреднении вероятности правильного декодирования используется весовой множитель :

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

Предположим теперь, что некоторый вектор расположен в таблице декодирования под кодовым вектором , так что расстояние Хэмминга между ними равно . Допустим, что ближайший кодовый вектор находится на расстоянии . Пусть — образующий смежного класса, содержащего вектор . Тогда вес вектора равен . Элемент имеет вес и лежит в том же самом смежном классе. Поскольку предполагалось, что имеет минимальный вес в своем смежном классе, то , и поэтому лежит по крайней мере так же близко к , как и к . Число образующих смежных классов веса обозначим через . Вероятность правильного декодирования может быть записана тогда следующим образом:


Литература

Мак-Вильямс Ф. Дж, Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М. : Связь, 1979. — С. 744, ил.