Оценка по кодовому расстоянию

Способности кода

Вероятностная оценка корректирующей

Корректирующие способности кода

В качестве корректирующих кодов наиболее часто используют систематические коды. Систематический код -это код, который кроме информационных разрядов содержит и контрольные, в которые записывается некоторая информация об исходном числе. Систематический код обладает избыточностью. Избыточность указывает степень удлинения кодовой комбинации для достижения определённой корректирующей способности. При этом абсолютная избыточность будет выражаться количеством контрольных разрядов k, а относительная – отношением k/n, где n=m+k – общее количество разрядов в кодовой комбинации.

Информационные и контрольные разряды во всех кодовых комбинациях занимают всегда одни и те же позиции. Одни помехоустойчивые систематические коды могут только обнаруживать ошибки, другие не только обнаруживать, но и исправлять их. Существует 2 подхода к оценке корректирующих способностей кода – вероятностный и по минимальному кодовому расстоянию.

Импульсные помехи, приводящие к изменению кода носят случайный характер. Если искажение отдельных символов кодовой последовательности считать событиями независимыми и принять, что искажения нулевых и единичных символов одинаковы, то в качестве модели помехи используют помеху с биноминальным законом распределения. Количественно корректирующая способность кода определяется вероятностью обнаружения или исправления ошибки. Вероятность ошибки кратности i в кодовой комбинации (КК) из n символов применительно к помехе с биноминальным законом вычисляется следующим образом:

P_iⁿ = C_nⁱ P_эⁱ (1 ‑ P_э)^{n ‑ i}, (3.24)

где С_nⁱ – число КК, каждая из которых содержит i искаженных элементов (это число сочетаний из n по i):

;

Pэ – вероятность искажения одного символа в КК;

P_эⁱ (1‑P_э)^n‑i – вероятность того, что искажены i символов КК, а остальные (n‑i) не искажены (по теореме умножения вероятностей).

Тогда полная вероятность искажения в КК:

. (3.25)

Пример. Если принять n=6, Рэ=0,01 и вычислить P_iⁿ по формуле (3.24) для i=1,2,3 (P16 = 0.057, P26 =0.014, P36 = 0.000019), можно видеть, что с повышением кратности ошибки вероятность её резко убывает. Наибольший вес в сумме вероятностей (3.25) имеет вероятность искажения одного символа, и, следовательно, основное внимание необходимо обратить на обнаружение и исправление одиночной ошибки.

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

Пример 1. Найти d(A,B) для кодовых комбинаций А и В:

A = 011011100₂; B = 100111001₂.

Для этого сложим их по mod2 и найдём вес суммарной двоичной комбинации

S=6 которая и определяет кодовое расстояние заданных комбинаций d(A,B).

Минимальное кодовое расстояние dmin – это минимальное расстояние, взятое по всем парам разрешённых КК.

Систематический код способен обнаруживать ошибки только тогда, когда d_min ≥ 2t, где t – кратность обнаруживаемых ошибок (для одиночных ошибок t = 1).

При d_min ≥ 2t никакой вариант t-кратной ошибки не может перевести одну разрешенную кодовую комбинацию в другую разрешённую.

Если же, то найдётся такой вариант t-кратной ошибки, который трансформирует одну комбинацию в другую.

В случаях, когда необходимо не только обнаружить ошибку, но и исправить её, необходимо, чтобы минимальное кодовое расстояние было
d_min ≥ 2t+1.

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