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

 

Идея помехоустойчивого кодирования состоит в том, что в пере­даваемую кодовую комбинацию по определенным правилам вносится избыточность (признаки разрешенной комбинации). Правила вне­сения избыточности, т. е. признаки, должны быть известны как на передающей, так и на приемной стороне. Если на приемной стороне эти признаки в кодовой комбинации не обнаруживаются, то счита­ется, что произошла ошибка (или ошибки). В противном случае (при наличии признаков) считается, что кодовая комбинация принята правильно (является разрешенной). Внесение избыточности при использовании помехоустойчивых (корректирующих кодов) обяза­тельно связано с увеличением числа разрядов (длины) кодовой ком­бинации п. При этом все множество N₀=2ⁿ комбинаций можно раз­бить на два подмножества: подмножество разрешенных комбинаций, т. е. обладающих определенными признаками, и подмножество за­прещенных комбинаций, этими признаками не обладающих. Коррек­тирующий код отличается от обычного тем, что в канал передаются не все кодовые комбинации (N₀), которые можно сформировать из имеющегося числа разрядов п, а только их часть N, которая состав­ляет подмножество разрешенных комбинаций: N< N₀.

Если в результате искажений переданная кодовая комбинация переходит в подмножество запрещенных кодовых комбинаций, то ошибка будет обнаружена. Однако если совокупность ошибок в дан­ной кодовой комбинации превращает ее в какую-либо другую раз­решенную, то в этом случае ошибки не могут быть обнаружены.

Поскольку любая из N разрешенных комбинаций может превра­титься в любую из N₀ возможных, то общее число таких случаев рав­но NN₀. Очевидно, что число случаев, в которых ошибки обнару­живаются, равно N(N₀ - N), где N₀ - N – число запрещенных комбинаций. Тогда доля обнаруживаемых ошибочных комбинаций составит:

Например, если N₀= 100, N = 20, то ошибка обнаруживается в 80% случаев.

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

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

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

Степень отличия любых двух кодовых комбинаций характери­зуется кодовым расстоянием (расстоянием Хемминга). Оно выра­жается числом символов, в которых комбинации отличаются одна от другой, и обозначается через d.

Чтобы получить кодовое расстояние между двумя комбинация­ми двоичного кода, достаточно подсчитать число единиц в сумме этих комбинаций по модулю 2.

Например:

1100001010

0101110111, d = 7.

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

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

Очевидно, что при минимальном кодовом расстоянии d = 1 все кодовые комбинации являются разрешенными.

Например, при п = 3 разрешенные комбинации образуют следу­ющее множество: 000, 001, 010, 011, 100, 101, 110, 111.

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

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

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

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

Данный код обнаруживает одиночные ошибки, а также другие ошибки нечетной кратности (при n = 3 тройные). В общем случае при необходимости обнаруживать ошибки кратности до r₀ включи­тельно должно выполняться условие:

Действительно, одновременная ошибка в r₀ разрядах кода создает новую кодовую комбинацию, отстоящую от первой на расстоянии r₀. Чтобы она не совпала с какой-либо другой разрешенной кодовой комбинацией, минимальное расстояние между двумя разрешен­ными кодовыми комбинациями должно быть хотя бы на единицу больше, чем r₀.

Для исправления r_и -кратной ошибки необходимо, чтобы новая кодовая комбинация, полученная в результате такой ошибки, не толь­ко не совпадала с какой-либо разрешенной комбинацией, но и оста­валась ближе к правильной комбинации, чем к любой другой разре­шенной. Иными словами, должно выполняться соотношение:

Учитывая, что r_u и d целые числа, получаем:

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

 

 

Таким образом, при n = 3 имеем N₀ = 2³ = 8 кодовых комбинаций, из которых только две N=2 разрешенных. С использованием дан­ного трехразрядного кода можно передать только два различных сообщения. Для передачи двух сообщений обычным непомехоус­тойчивым способом достаточно было бы одноразрядных комбинаций «0» и «1», т. е. обеспечение возможности исправления одиноч­ной ошибки в нашем случае связано с увеличением длины кода на k = 2 разряда.

Величину ω, равную отношению числа дополнительных прове­рочных разрядов кода (k) к разрядности кода (n), называют избы­точностью корректирующего кода:

ω =k/n=(n-m)/n=1-m/n,

где m - число информационных символов корректирующего кода.

Величина m/n = 1-ω показывает, какую часть общего числа символов кодовой комбинации составляют информационные сим­волы. Она характеризует относительную скорость передачи. Так, если производительность источника информации равна R симво­лов в секунду, то скорость передачи после кодирования этой ин­формации:

поскольку в закодированной последовательности из каждых n сим­волов только m символов являются информационными.

При построении корректирующих кодов возникает задача на­хождения наибольшего числа N кодовых комбинаций n -значного двоичного кода, расстояние между которыми не менее d. Общее решение этой задачи неизвестно. Некоторые частные результаты приведены в таблице.

d	N
	2n
	2n-1