Коды Хемминга

Исторически первыми были коды Хемминга. Их параметры: проверочная матрицагдепримитивный элемент поля Галуа

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

есть матрица линейного -кода.

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

Расстояние Хэмминга обладает всеми свойствами расстояния:

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

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

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

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

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

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

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

Определение Кодом Хемминга называется линейный код с проверочной матрицей .Здесь – двоичный вектор-столбец над полемв базиседля примитивного элементаполя.

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

Теорема У кода Хэмминга минимальное расстояние Код Хэмминга исправляет одиночные ошибки.

Коды бчх

Наиболее распространёнными кодами являются БЧХ-коды, которые задаются матрицами гдепримитивный элемент поля Галуа

Определение Линейный код длинойс проверочной матрицей

Н=(2.1)

над полем называется кодом Боуза-Чоудхури-Хоквингема (БЧХ-кодом) с конструктивным расстоянием. При n = БЧХ-код называют примитивным, и не примитивным, если n<.

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

Теорема Для всякого целого числа не делящегося на над полемсуществует БЧХ-код длиной Для всякого нечетного существует двоичный БЧХ-код длиной

Ранг проверочной матрицы БЧХ-кодачаще всего совпадает с числом ее строк

Теорема Пусть для некоторого целого не делящегося напроверочная матрицаБЧХ-кода содержит, с точностью до перестановки строк, подматрицу Тогда

Замечание. Теорема остается справедливой, если в подматрице степень заменить надля целых

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

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

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

Классический примитивный БЧХ-код С с проверочной матрицей имеет кодовое расстояние равное 5. Следовательно, этот код корректирует одиночные и двойные ошибки.