3. Линейные и циклические коды

3.1. Линейные коды

Линейные коды составляют лишь небольшой подкласс блоковых кодов, однако, поскольку они образуют такую хорошо известную структуру, как линейное пространство, то сразу же после их построения Киясу [1] и Слепяном [2] они стали основным объектом исследования в теории кодирования. Предположим, что число символов на входе канала является некоторой степенью простого числа Входные символы канала представляют собой обозначения для реальных сигналов в канале; для удобства обращения с ними возьмем в качестве входного алфавита канала конечное поле из элементов. Введенное выше предположение о том, что является степенью простого числа, обусловлено тем, что, как указывалось в разд. 2.5, число элементов в любом конечном поле есть степень простого числа и, наоборот, для любого являющегося степенью простого числа, существует поле из элементов.

Пусть векторное пространство размерности над полем Подпространства размерности пространства называются -ичными линейными кодами длины информационными символами [или -кодами]. Если С — линейный код, то подпространства линейного пространства С будем называть (линейными) подкодами кода С.

Коды из примеров 1.3 и 1.4 являются линейными. В случае линейных кодов кодовые слова называют также кодовыми векторами. При линейные коды называют групповыми.

Как было замечено выше, линейные коды представляют собой лишь подкласс класса блоковых кодов; известны примеры нелинейных кодов, число кодовых слов в которых больше числа кодовых слов в любом линейном коде с теми же параметрами Однако линейные коды обладают более простой структурой, что позволяет выявить более тонкие их свойства и делает их перспективными при построении простых процедур кодирования и декодирования. Кроме того, следует заметить, что коды Препараты [4], являющиеся типичными представителями нелинейных кодов, тесно связаны с циклическими кодами (см. разд. 3.5), являющимися в свою очередь подклассом класса линейных кодов.

Назовем весом Хэмминга вектора (или просто весом вектора из число ненулевых компонент этого вектора; вес

вектора будем обозначать через Расстояние Хэмминга между векторами определим как вес их разности, а именно положим . Пусть минимальное расстояние линейного кода С. Тогда для любого ненулевого вектора

так как нулевой вектор также принадлежит коду С (нулевой вектор обозначен здесь символом 0).

С другой стороны, из определения следует существование векторов таких, что Но тогда, поскольку минимальный вес кода С (который определяется как минимальный из весов ненулевых векторов, входящих в С) в точности равен минимальному расстоянию кода С.

Для задания линейного кода удобно пользоваться определяемой ниже матрицей Пусть некоторый базис -кода С, и пусть матрица из строк и столбцов, 1-й строкой которой является базисный вектор Матрица называется порождающей матрицей кода С. Из свойств базиса непосредственно следует, что любой кодовый вектор может быть представлен в виде линейной комбинации строк матрицы наоборот, что любая линейная комбинация строк матрицы представляет собой кодовый вектор и, более того, различные линейные комбинации задают различные кодовые векторы.

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

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

где индекс означает транспонирование. Как известно, является подпространством размерности пространства Это подпространство называется кодом, двойственным коду С. Порождающую матрицу двойственного кода назовем

проверочной матрицей (или просто матрицей ) исходного кода С. Матрица имеет размер По определению

В частности, если взять в качестве векторов базисные векторы кода С, то получим

где 0 — нулевая матрица. С помощью матрицы , например, задавался код в примере 1.4. Поскольку по определению ранг матрицы равен то содержит невырожденную подматрицу размера Путем перестановки столбцов и соответствующего изменения нумерации компонент кодовых векторов всегда можно добиться того, чтобы матрица была образована последними столбцами . Как хорошо известно, с помощью элементарных операций над строками [умножения строк на ненулевые элементы поля и сложения одной строки с другой] матрица всегда может быть приведена к следующему виду:

где некоторая матрица размера единичная матрица размера

Поскольку получена посредством элементарных операций над строками, то

т. е. также является проверочной матрицей кода С. Обозначим через элемент подматрицы матрицы стоящий в 1-й строке и столбце. Очевидно, что необходимым и достаточным условием принадлежности вектора коду С является выполнение следующей системы равенств:

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

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

Краткое доказательство. Ранг равен Поскольку то каждая строка является кодовым вектором кода С.

Вернемся к примеру 1.4. Изменяя нумерацию компонент кодовых векторов, можно привести проверочную матрицу рассматриваемого кода к виду (3.2). В данном случае

Но тогда, как следует из утверждения 3.1, проверочная матрица кода, двойственного -коду Хэмминга из примера 1.4, имеет следующий вид:

Пример 3.1. Пусть С — линейный -ичный -код. Линейный -ичный -код

называется расширением кода С. Исходный код С при этом называют укорочением расширенного кода Множество является подкодом кода С и называется четным подкодом кода С. Если содержит вектор ( то двойственный код кода является расширением двойственного кода четного подкода кода С.

Доказательство. Пусть Поскольку то

Следовательно, — расширение кода Число информационных символов

кода совпадает с числом информационных символов кода и равно Если то

Так как то а это значит, что Далее, поскольку число информационных символов кода равно и совпадает с числом информационных символов кода то

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

Обозначим через столбец проверочной матрицы линейного кода С. Пусть кодовый вектор веса ненулевые компоненты которого имеют номера Из формулы (3.1) имеем

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

Пусть вектор, у которого компоненты с номерами равны а другие равны 0. Тогда в силу равенства (3.5)

т. е. у — кодовый вектор веса

Таким образом, мы доказали следующую теорему.

Теорема 3.1. Минимальный вес линейного -кода С равен тогда и только тогда, когда любые столбцов проверочной матрицы этого кода линейно независимы, но некоторые столбцов проверочной матрицы линейно зависимы.

Прямым следствием этой теоремы является следующее.

Следствие 3.1.

Линейный код, для которого последнее соотношение выполняется со знаком равенства, называется разделимым кодом с достижимым максимальным расстоянием. Примерами таких кодов являются описанные ниже коды Рида — Соломона, а также БЧХ-коды из примера 4.5.

Доказанная простая теорема указывает способ прямого построения проверочных матриц И кода с заданными параметрами Она оказывается полезной при построении и исследовании не только БЧХ-кодов и кодов Гоппы, но и кодов Сриваставы [9] и других кодов. Кроме того, на основании этой теоремы выводится граница Варшамова — Гилберта. До сих пор считалось конечным полем, однако в действительности можно рассмотреть более общий случай, когда является конечным кольцом. Однако, поскольку в этом более общем случае не удается получить какие-либо полезные результаты, далее мы будем по-прежнему считать, что конечное поле.

Утверждение 3.2. Пусть степень простого числа и и пусть а — примитивный элемент поля Представим каждый элемент поля в виде

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

Доказательство. Пусть вектор из такой, что все его компоненты, за исключением и равны нулю. Если предположить, что то

Но тогда, если один из элементов или равен нулю, то и другой элемент также должен быть равен нулю. Если же то из определения имеем

где Возводя обе части последнего равенства в степень получаем

Это приводит к противоречию, поскольку Следовательно, минимальное расстояние рассматриваемого кода не меньше 3. Более того, поскольку этот код лежит на границе Хэмминга при он является совершенным. Этот код называется -ичным (обобщенным) кодом Хэмминга.