Связь корректирующей способности с кодовым расстоянием

Основные понятия помехоустойчивого кодирования

Количество разрядов n кодовой конструкции называется длиной кода. Вес - это количество единиц, содержащихся в кодовой конструкции. Степень отличия любых двух кодовых конструкций характеризуется кодовым расстоянием d, оно выражается числом позиций в которых одна кодовая конструкция (к.к.) отлична от другой. d определяется как сумма по модулю два этих к.к.

_+mod21101101

0010100

1111001 (w =5[В.В1]) Þ d = 5

Ошибки появляющиеся в канале из-за помех проявляются в замене 0 на 1 и 1 на 0. Ошибка в одном разряде называется однократной. Экспериментальные исследования показали, что ошибки как правило группируются в пачке различной длины. Пачка ошибок - это участок последовательности, начинающийся и кончающийся неправильно принятыми символами. Внутри пачки могут быть и правильные символы. Для указания места ошибки используют вектор ошибки (e). Вектор ошибки n - разрядного кода представляет собой n - разрядную последовательность единицы в которой указывают положение искаженных символов. Вес вектора ошибки w_e определяет кратность ошибки. Сложение по модулю два искаженной к.к и вектора ошибки дают исходную неискаженную комбинацию. Помехоустойчивое кодирование обеспечивается за счет введения избыточности, т.е. из n символов к.к используется только k разрешенных.

Для оценки различия между двумя произвольными к.к данного кода используется d(min) - минимальное кодовое расстояние. Пусть задан код длина которого n = 3, тогда N = 2³ = 8

А1	А2	А3	А4	А5	А6	А7	А8

Необходимо построить код, обнаруживающий t кратные ошибки. Для того, чтобы построить код необходимо из множества возможных комбинаций N = 8 выбрать Nо разрешенных комбинаций, таких чтобы любая комбинация в сумме по модулю два с вектором ошибок весом меньшим либо равным t не давала бы в результате никакой разрешенной комбинации. Для этого необходимо чтобы d(min) ³ t+1

Пусть t = 1 откуда следует что d(min) ³ 1+1 = 2

А1 А4 А6 А7 - разрешенные к.к.

Пусть необходимо построить корректирующий код, позволяющий исправлять однократную ошибку. В качестве исходной возьмем комбинацию А1 = 000, в результате воздействия ошибок данная к.к может преобразоваться в комбинации: 001 010 100.

Возьмем в качестве второй разрешенной к.к А4 = 011 (111, 001, 010), т.е запрещенные к.к пересекаются, т.е. нельзя однозначно определить исходный переданный сигнал. Поэтому второй разрешенной к.к возьмем А8 = 111 (011, 101, 110).

Для однократных ошибок d(min) = 3. Для кодов с d(min) = 3 d(min) =2g+1

g - кратность ошибки. Обнаруживает t -кратные ошибки исправляет g кратные

d(min) = t+g+1

r = n - k (правило)

log₂ (C^g_n+ C^g-1_n+...+1) £ r £ log₂ (C^2g-1_n-1+ C^2g-2_n-1+...+1)

граница Хэминга граница Варшамова

[В.В1]

Дата добавления: 2014-01-13