Оценка корректирующей способности кода
з
Корректирующая способность кода зависит от минимального кодового расстояния.
Условие обнаружения ошибок кратности r: d r + 1,
Условие исправления ошибки кратности s: d 2s + 1,
Условие одновременного обнаружения ошибок кратности r и исправления ошибок кратности s: d r + s + 1 (r s).
Оценка (Хемминга) необходимой избыточности:
2n-k–1 Cn1 + Cn2 +…+ Cns.
(число кодовых комбинаций в контрольных разрядах должно быть больше числа исправляемых ошибок).
Перемешивание символов
Перемешивание символов (чередование, перемежение, interleaving), является эффективным способом исправления пакетов ошибок без введения избыточности.
Применяется блочное и сверточное перемешивание.
Пример блочного перемешивания
Исходная последовательность данных
a1 a2 a3 a4 a5 ; b1 b2 b3 b4 b5 ; c1 c2 c3 c4 c5 ; d1 d2 d3 d4 d5; e1 e2 e3 e4 e5
записывается в таблицу по строкам,
a1 a2 a3 a4 a5 ;
b1 b2 b3 b4 b5:
c1 c2 c3 c4 c5
d1 d2 d3 d4 d5;
e1 e2 e3 e4 e5
а выдается в канал по столбцам
В приемнике прежняя последовательность восстанавливается:
a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 d1 d2 d3 d4 d5 e1 e2 e3 e4 e5.
При «пакетной» ошибке ошибочные символы распределятся по различным кодовым комбинациям.
Число строк в матрице называют глубиной перемежения. Это число определяет размер пакета ошибок, исправляемого благодаря применению перемешивания.
Принцип формирования линейного блокового кода Порождающая и проверочная матрицы
Блоковый (n,k) код можно представить матрицей, строки которой – «разрешенные» кодовые слова, или векторы, состоящие из знаков 0 и 1. Порождающая матрица G – это набор из любых k линейно независимых векторов (базисных). Любое разрешенное слово можно получить суммированием некоторых базисных слов.
Матричная операция В = А G (А – исходное безызбыточное слово) дает слово В помехоустойчивого кода:
Принятое слово проверяется на наличие ошибки умножением его на проверочную матрицу
Формирование слова Проверка принятого слова
помехоустойчивого кода на наличие ошибки
В рассмотренном примере кода с исправлением одиночной ошибки результат умножения принятого слова на проверочную матрицу указывает номер искаженного разряда в принятом слове
Принцип формирования циклического кода Представление двоичного слова многочленом
(х– формальная переменная)
Сдвиг числа влево – умножение многочлена на х:
Циклический сдвиг с приведением по модулю xn + 1:
Циклический сдвиг описывается умножением соответствующего числу многочлена a(x) на переменную х с записью единицы в младший разряд, если при сдвиге числа происходит переполнение разрядной сетки. Последнее действие над многочленом xa(x), называемое «приведением по модулю xn + 1», эквивалентно делению на многочлен (xn + 1), прибавлению или вычитанию многочлена xn + 1.