Параметры (характеристики) помехоустойчивых кодов и их границы. Корректирующие свойства кодов.

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

- длина кода n;

- основание кода m;

- общее число кодовых комбинаций N;

- число разрешенных кодовых комбинаций N_р;

- избыточность кода ;

- минимальное кодовое расстояние.

 

Длина (разрядность) кода n - это число символов в кодовой комбинации. Если кодовые комбинации содержат одинаковое число символов, то код называется равномерным.

 

Основание кода m - это число различных символов в коде. Для двоичных кодов символами являются 1 и 0, поэтому m=2.

Число кодовых комбинаций для равномерного кода равно . (Например, для равномерного двоичного кода число кодовых комбинаций при n=6, N=2⁶=64).

 

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

Для помехоустойчивых кодов .

() – запрещенные комбинации. Если , то код является безызбыточным. Для двоичных разделимых кодов 2^k .

 

Избыточность кода в общем случае определяется выражением:

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

Для разделимых кодов

- относительная скорость кода

Кодовое расстояние d(A,B) - это число позиций, в которых две кодовые комбинации A и B отличаются друг от друга. Например, A=01101, B=10111, => d(A,B)=3.

Кодовое расстояние можно найти в результате сложения по модулю 2 одноименных разрядов комбинаций.

 

где – значения i-х разрядов кодовых комбинаций A,B

- сложение по модулю 2

 

Например. A=01101

B=10111

d(A,B)=1+1+0+1+0=3

 

Кодовое расстояние называют кодом Хемминга.

Кодовое расстояние между различными комбинациями конкретного кода может быть различным.

 

Минимальное кодовое расстояние - это минимальное расстояние между разрешенными кодовыми комбинациями данного кода.

Минимальное кодовое расстояние является основной характеристикой корректирующей способности кода.

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

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

Так, при кодовом расстоянии d=1 все кодовые комбинации являются разрешенными. Например, при n=3, разрешенные комбинации образуют следующее множество:

000, 001, 010, 100, 110, 111, 101.

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

Если d=2, то ни одна из разрешенных кодовых комбинаций при одиночной ошибке не переходит в другую разрешенную комбинацию. Например, подмножество разрешенных кодовых комбинаций может быть образовано по принципу четности в нем числа единиц. Для n=3:

000, 011, 101, 110 - разрешенные комбинации;

001, 010, 100, 111 - запрещенные комбинации.

Код обнаруживает одиночные ошибки, а также другие ошибки нечетной кратности (при n=3 - тройные).

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

граница обнаружения ошибки кратностью s.

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

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

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

Поясним на примере если n=3, то и разрешенные кодовые комбинации можно выбрать 000 и 111. Тогда разрешенной комбинации 000 необходимо приписать подмножество запрещенных кодовых комбинаций 001, 010, 100, образующихся в результате одиночной ошибки (в одном разряде комбинации) в комбинации 000. Аналогично разрешенной комбинации необходимо приписать подмножество запрещенных кодовых комбинаций 110, 011, 101, образующихся в результате возникновения единичной ошибки в комбинации 111.

 

 

 

Если будет принята комбинация 010, то определив, что она относится к подмножеству запрещенных комбинаций, ошибка будет обнаружена, а так как это подмножество приписано (прибавлено в соответствие) разрешенной комбинации 000, то ошибка может быть исправлена. Окончательным решением о принятой комбинации будет разрешенная = 000.

 

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

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

- граница исправления ошибок кратности t.

 

Например, для обнаружения однократных ошибок (s=1) требуется код с , а для того, чтобы исправить такие ошибки, требуется код с

Для обнаружения s ошибок и исправления t из них код должен обладать , причем t≤s.

Таким образом, задача построения помехоустойчивой корректирующей способностью сводится к обеспечению необходимого минимального кодового расстояния. Увеличение приводит к росту избыточности кода. При этом желательно, чтобы число проверочных символов r было минимальным. Это противоречие разрешается через определение верхней и нижней границ числа проверочных символов (верхняя граница Хемминга и Плоткина, нижняя граница Варшамова-Гильберта).