3.2 ЛИНЕЙНЫЕ БЛОЧНЫЕ КОДЫ

Рассмотрим наиболее интересный для практики класс блочных кодов — линейные.

Определение 3.5. Линейный код есть подпространство в поле Галуа Линейный непрерывный код называют сверточным кодом. Любой линейный код содержит нулевое слово как начало координат векторного пространства.

Определение 3.6. Вес Хэмминга кодового слова а равен числу его ненулевых компонент. Минимальный вес кода есть минимальный вес ненулевого кодового слова.

Утверждение 3.1. Для линейного кода минимальное расстояние находится из равенства

Определение 3.7. Порождающей матрицей называется такая матрица, которая порождает подпространство, являющееся -линейным кодом.

Любое взаимно однозначное соответствие векторов и а может быть использовано для кодирования, в том числе и

Поскольку линейный код А является подпространством, то он имеет ортогональное дополнение которое называется дуальным кодом. Код имеет размерность

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

Утверждение 3.2. Линейный код А имеет минимальное расстояние не менее тогда и только тогда, когда каждое из столбцов линейно независимо.

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

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

Утверждение 3.4. Минимальное расстояние (минимальный вес) любого линейного кода удовлетворяет неравенству

Определение 3.9. Любой код с минимальным расстоянием, удовлетворяющий равенству называется кодом с максимальным расстоянием.

Определение 3.10. Для любого принятого вектора а синдромом называется вектор

Все векторы, имеющие одинаковый синдром, принадлежат одному смежному классу кода. Для кодовых слов синдром равен нулю.

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

циклического кода любой циклический сдвиг кодового слова будет также кодовым словом. Теория циклических кодов описана во многих монографиях [24—37]. Многие рассматриваемые в дальнейшем линейные коды имеют циклическую структуру. Здесь отметим лишь, что операции над кодовыми словами можно осуществлять в алгебре многочленов. Тогда циклический код состоит из всех произведений порождающего многочлена на многочлены степени не выше

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

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

Коды БЧХ (Боуза-Чоудхури - Хоквингема). Коды представляют собой обобщение кодов Хэмминга для исправления кратных ошибок.

Определение 3.11. Примитивный код БЧХ, исправляющий ошибок, — это блоковый код длины над полем для которого элементы (для произвольного являются корнями порождающего многочлена Здесь примитивный элемент поля

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

Коды РС (Рида — Соломона). Коды представляют собой важный подкласс кодов БЧХ при Для этих кодов длина блока коды задаются над полем а порождающий многочлен задается формулой

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

Коды РМ (Рида — Маллера). Коды являются двоичными линейными кодами, эквивалентными циклическим кодам с добавлением общей проверки на четность.

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

покомпонентные произведения или меньшего числа векторов Код порядка имеет параметры и дуален коду порядка.

Пример 3.4. Код РМ первого порядка имеет Код содержит одно слово веса 0, одно слово веса слов веса Этот код называется биортогональным, так как эквивалентен ансамблю биортогоиальных сигналов в евклидовом пространстве

Пример 3.5 Код РМ порядка имеет Код эквивалентен коду Хэмминга с добавлением общей проверки на четность

Мажоритарные коды на основе проектной плоскости Важными являются коды, имеющие достаточно простую схему декодирования—мажоритарную Эти коды имеют много модификаций и в основном строятся при помощи евклидовых и проектных конечных геометрий [37, 38] Здесь опишем лишь простейший вариант мажоритарных кодов, имеющих разделенные проверки и основанные на проективной плоскости порядка Эта плоскость содержит точек, которые могут быть заданы тройками элементов Эти точек определенным образом нумеруются

Тогда код над образуемый векторами инцидентности прямых в Код циклический имеет длину и число информационных символов [39]

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

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

Пример 3.7. Пусть простое Тогда получаем -ичные коды с параметрами При получим соответственно коды и (31, 15, 7) 5 Как показано в [40], действительное минимальное расстояние этих кодов существенно выше

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