Понятие о корректирующих кодах

Пусть имеется источник сообщений с объемом алфавита К.

Поставим в соответствие каждому сообщению n - элементную двоичную последовательность. Всего последовательностей из n - элементов может быть .

Если , то все последовательности (или кодовые комбинации) будут использоваться для кодирования сообщений, т.е. будут разрешенными.

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

Для того, что бы код мог обнаруживать и исправлять ошибки необходимо выполнение условия , при этом неиспользуемые для передачи комбинации (N₀-K) называют запрещенными.

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

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

Перебрав все возможные пары разрешенных комбинаций рассматриваемого кода можно найти минимальное расстояние Хемминга d₀.

Минимальное расстояние d₀ - называется кодовым расстоянием

Кодовое расстояние определяет способность кода обнаруживать и исправлять ошибки.

У простого кода d₀=1 – он не обнаруживает и не исправляет ошибки. Так как любая ошибка переводит одну разрешенную комбинацию в другую.

В общем случае справедливы следующие соотношения

– для обнаруживающей способности

для четных

для нечетных

– для исправляющей способности

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

Двоичный блочный код является линейным если сумма по модулю 2 двух кодовых слов является также кодовым словом.

Линейные коды также называют групповыми.

Введем понятия группы.

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

1. Замкнутость g_i g _j= g_k G в результате операции с двумя элементами группы получается третий, так же принадлежащий этой группе.
2. Ассоциативность (сочетательность) (g_i g_j) g_k = g_i (g_j g_k)
3. Наличие нейтрального элемента g_j e = g_j
4. Наличие обратного элемента. g_i (g_i)^-1= e

Если выполняется условие g_i g_j = g_j g_i, то группа называется коммутативной.

Множество кодовых комбинаций n-элементного кода является замкнутой группой с заданной групповой операцией сложение по модулю 2.

Поэтому используя свойство замкнутости относительно операции 2, множество всех элементов можно задать не перечислением всех элементов, а производящей матрицей.

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

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