Необходимые теоретические сведения

Пусть линейный код над полем .

Определение 2.1. Матрица порядка называется проверочной матрицей кода , если

Отметим некоторые свойства проверочных матриц.

Свойство 1. Проверочная матрица у каждого линейного кода всегда существует.

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

Если известна порождающая матрица кода , то с помощью строк этой матрицы, а фактически базиса , кода , можно составить систему линейных однородных уравнений:

(2.1)

Множество решений системы (2.1) составляет ядро матрицы подпространство пространства размерностью . Пусть базис пространства решений системы (2.1). Тогда матрица

(2.2)

есть искомая проверочная матрица кода . Действительно, в силу соотношений (2.1) должны выполняться равенства . Они означают, что . С другой стороны, . Это означает, что . действительно является проверочнай матрицей кода .

Свойство 2. Координаты базиса ядра матрицы составляют проверочную матрицу кода только для векторов и только для них.

Свойство 3. ; .

Пример 2.1. Код с проверкой на чётность из примера 1.2 состоит из векторов-решений единственного уравнения над полем Следовательно, проверочная матрица кода есть матрица и имеет вид:

Пример 2.2. В силу сказанного выше, матрица коэффициентов системы линейных уравнений (1.3)

есть проверочная матрица – кода Хемминга, определенного в примере 1.3. Так как базисный минор матрицы расположен в последних трех столбцах, то являются свободными переменными системы линейных уравнений (1). Отсюда легко получаем порождающую матрицу кода Хемминга:

.

Проверочная матрица кода определена не однозначно.

Свойство 4. Пусть матрица порядка и ранга проверочная матрица линейного кода , где Тогда для всякой невырожденной квадратной матрицы порядка матрица также является проверочной для кода .

Данное свойство дополняет свойство, указанное ниже.

Свойство 5. Пусть и две проверочные матрицы линейного кода . Тогда существует квадратная – матрица для такая, что

Каждая из матриц или однозначно определяет код

Из свойств 3 и 4 следует критерий для определения, когда две матрицы являются проверочными матрицами одного и того же линейного кода.

Теорема 2.1. Пусть проверочная матрица линейного кода . Матрица порядка является проверочной матрицей этого же кода тогда и только тогда, когда найдется такая невырожденная – матрица что

Свойство 6. Количество различных проверочных матриц линейного кода над конечным полем совпадает с количеством различных невырожденных квадратных матриц порядка в поле , то есть с порядком группы невырожденных квадратных матриц порядка над полем .

Свойство 6 позволяет определить количество проверочных матриц у данного линейного кода над конечным полем . Так, над полем из двух элементов, по теореме 4.11 [11], группа матриц имеет порядок В частности, при этот порядок равен При искомый порядок равен Это означает, что у кода Хемминга над полем имеется 168 различных проверочных матриц.

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

1) тогда и только тогда, когда (аксиома тождества);

2) (аксиома треугольника);

3) (аксиома симметрии).

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

Определение 2.3. Расстоянием Хемминга между векторами называется количество несовпадающих координат этих векторов.

Весом вектора называется количество ненулевых координат этого вектора.

Несложно видеть, что расстояние Хэмминга между векторами равно весу вектора Очевидно,

Лемма 2.1. Расстояние Хэмминга обладает всеми свойствами обычного расстояния

1) свойство симметричности;

2) тогда и только тогда, когда ;

3) неравенство треугольника.

Определение 2.4. окрестностью вектора назовём совокупность всех векторов для которых

окрестности обладают обычным свойством отделимости.

Лемма 2.2. Если то окрестности векторов не пересекаются.

Определение 2.5. Минимальным или кодовым расстоянием кода называется наименьшее из расстояний между попарно различными векторами кода .

Из равенства следует, что минимальное расстояние линейного кода равно наименьшему из весов ненулевых векторов этого кода.

Значение кодового расстояния определяет следующая фундаментальная в помехоустойчивом кодировании теорема.

Теорема 2.2. Если минимальное расстояние кода равно или , то код может обнаружить до ошибок и исправить до ошибок в каждом принятом векторе-слове длиной .

Следующая теорема служит критерием для определения минимального расстояния кода.

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

Доказательство теоремы обеспечивает

Лемма 2.3. Пусть это i –ый столбец проверочной матрицы линейного кода над полем Вектор весом с ненулевыми координатами на позициях принадлежит коду тогда и только тогда, когда система столбцов линейно зависима.

Одним из важнейших понятий теории помехоустойчивых кодов является синдром ошибок. В процессе передачи информации на кодовое слово может наложиться «шум» вектор-ошибок В результате приемное устройство получает искажённое сообщение

Определение 2.6. Синдромом ошибок принятого слова в коде С с проверочной матрицей называется вектор .

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

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

Предложение 2.1. Если пробегает все векторы пространства E_n, то пробегает все векторы пространства E _n-k.

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

Пусть минимальное расстояние кода Пусть , если нечетно, и , если четно. Пусть множество всех векторов весом в пространстве

Предложение 2.2. Если для , но , то . Следовательно, для произвольных , их синдромы попарно различны: .

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

1) согласно предложению 2.2 синдромы однозначно соответствуют ошибкам декодируемого многообразия;

2) синдромы имеют существенно меньшие размеры по сравнению с кодовыми словами и векторами ошибок (что особенно наглядно для высокоскоростных кодов, например для кодов Хемминга);

3) для нахождения синдромов не требуется специальных вычислений, кроме обусловленных необходимостью индикации наличия или отсутствия ошибок в принятом блоке-сообщении;

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

Дата добавления: 2017-02-01