Оценка корректирующей способности кода

з

Корректирующая способность кода зависит от минимального кодового расстояния.

Условие обнаружения ошибок кратности r: d  r + 1,

Условие исправления ошибки кратности s: d  2s + 1,

Условие одновременного обнаружения ошибок кратности r и исправления ошибок кратности s: d  r + s + 1 (r  s).

Оценка (Хемминга) необходимой избыточности:

2^n-k–1  C_n¹ + C_n² +…+ C_n^s.

(число кодовых комбинаций в контрольных разрядах должно быть больше числа исправляемых ошибок).

Перемешивание символов

Перемешивание символов (чередование, перемежение, interleaving), является эффективным способом исправления пакетов ошибок без введения избыточности.

Применяется блочное и сверточное перемешивание.

Пример блочного перемешивания

Исходная последовательность данных

a₁ a₂ a₃ a₄ a₅ ; b₁ b₂ b₃ b₄ b₅ ; c₁ c₂ c₃ c₄ c₅ ; d₁ d₂ d₃ d₄ d₅; e₁ e₂ e₃ e₄ e₅

записывается в таблицу по строкам,

a₁ a₂ a₃ a₄ a₅ ;

b₁ b₂ b₃ b₄ b₅:

c₁ c₂ c₃ c₄ c₅

d₁ d₂ d₃ d₄ d₅;

e₁ e₂ e₃ e₄ e₅

а выдается в канал по столбцам

В приемнике прежняя последовательность восстанавливается:

a₁ a₂ a₃ a₄ a₅ b₁ b₂ b₃ b₄ b₅ c₁ c₂ c₃ c₄ c₅ d₁ d₂ d₃ d₄ d₅ e₁ e₂ e₃ e₄ e₅.

При «пакетной» ошибке ошибочные символы распределятся по различным кодовым комбинациям.

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

Принцип построения кодов Хемминга (с исправлением одиночной ошибки)

Блоковый код (7, 4) удовлетворяет оценке Хемминга: 2^n–k – 1 = n.

Все возможные векторы ошибок:

Проверочные равенства:

а₁ + а₃ + а₅ + а₇ = 0,

а₂ + а₃ + а₆ + а₇ = 0,

а₄ + а₅ + а₆ + а₇ = 0.

Правила определения контрольных разрядов:

а₁ = а₃ + а₅ + а₇,

а₂ = а₃ + а₆ + а_{7 ,}

а₄ = а₅ + а₆ + а_7.

Пример:

а₇ а₆ а₅ а₄ а₃ а₂ а₁ – символы кодового слова,

0 1 1 - 0 - - – информационная часть кодового слова,

0 1 1 – опознаватель,

0 1 1 0 0 1 1 – кодовое слово полностью,

0 0 1 0 0 1 1 – кодовое слово с ошибочным символом а₆.

Проверочные равенства дают следующий результат:

Синдром 110 = 6 указывает номер ошибочного разряда слова.

Блоковый код, в котором контрольные символы являются суммами

некоторых разрядов исходного слова, называется линейным кодом.

Порождающая и проверочная матрицы

Блоковый (n,k) код можно представить матрицей, строки которой – «разрешенные» кодовые слова, или векторы, состоящие из знаков 0 и 1. Порождающая матрица G – это набор из любых k линейно независимых векторов (базисных). Любое разрешенное слово можно получить суммированием некоторых базисных слов.

Матричная операция В = А G (А – исходное безызбыточное слово) дает слово В помехоустойчивого кода:

Принятое слово проверяется на наличие ошибки умножением его на проверочную матрицу

Формирование слова Проверка принятого слова

помехоустойчивого кода на наличие ошибки

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