Групповые коды

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

Определения

TemplateDifinitionIcon.svg Определение «Определение - Группа »

Группа - это некоторое непустое множество с заданной на нем бинарной операцией *, для которого справедливы следующие аксиомы:

1. ассоциативность:
2. наличие нейтрального элемента:
3. наличие обратного элемента
TemplateDifinitionIcon.svg Определение «Определение - Групповой код»
Групповой код длины над полем - это произвольная подгруппа абелевой группы линейного пространства .
TemplateDifinitionIcon.svg Определение «Определение - Линейный код»
Линейный код - это линейное подпространство в .

В линейном коде помимо операции сложения (+) элементов определено еще и умножение на элементы из

Когда групповой код будет линейным?[1]


TemplateExampleIcon.svg Пример Пример

Рассмотрим , т.е.

Линейный групповой код

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


Порождающая матрица

TemplateDifinitionIcon.svg Определение «Определение - Порождающая матрица»
Порождающая матрица линейного кода - это матрица, строки которой образуют базис в .
TemplateExampleIcon.svg Пример Пример


  • Строки порождающей матрицы выражают базис, следовательно через нее можно выразить все строки кода.
  • Порождающая матрица для кода определена не однозначно.


TemplateExampleIcon.svg Пример Пример


Поле ; — длина кода; — размерность. Векторы линейно независимы, линейная оболочка — пространство размерности 2 кодовых слов.

Составим все линейные комбинации, упорядочив их в виде:

Порождающая матрица


Теорема о кодовом расстоянии

TemplateTheoremIcon.svg Теорема Теорема о кодовом расстоянии для линейных кодов
Для линейных кодов:
Доказательство


Проверочная матрица

TemplateDifinitionIcon.svg Определение «Проверочная матрица»

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

TemplateExampleIcon.svg Пример Пример
Порождающая и проверочная матрицы


TemplateExampleIcon.svg Пример Пример

Найдём по известной .

Составим систему уравнений:

Фундаментальная система решений:

Пример проверочной матрицы

.

состоит из элементов .

Для справедливо: для (т.е. любой строки в ).


Размерность кода

TemplateDifinitionIcon.svg Определение «Размерность кода»
Так как линейный код - это линейное кодовое пространство, то размерность кода - количество векторов в базисе соответствующего линейного пространства.
TemplateTheoremIcon.svg Теорема Теорема
Доказательство
Без доказательства. См. Линейная алгебра


Литература

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

Примечания

  1. Построить групповой код, не являющийся линейным.