Принципы помехоустойчивого кодирования
Идея помехоустойчивого кодирования состоит в том, что в передаваемую кодовую комбинацию по определенным правилам вносится избыточность (признаки разрешенной комбинации). Правила внесения избыточности, т. е. признаки, должны быть известны как на передающей, так и на приемной стороне. Если на приемной стороне эти признаки в кодовой комбинации не обнаруживаются, то считается, что произошла ошибка (или ошибки). В противном случае (при наличии признаков) считается, что кодовая комбинация принята правильно (является разрешенной). Внесение избыточности при использовании помехоустойчивых (корректирующих кодов) обязательно связано с увеличением числа разрядов (длины) кодовой комбинации п. При этом все множество N0=2n комбинаций можно разбить на два подмножества: подмножество разрешенных комбинаций, т. е. обладающих определенными признаками, и подмножество запрещенных комбинаций, этими признаками не обладающих. Корректирующий код отличается от обычного тем, что в канал передаются не все кодовые комбинации (N0), которые можно сформировать из имеющегося числа разрядов п, а только их часть N, которая составляет подмножество разрешенных комбинаций: N< N0.
Если в результате искажений переданная кодовая комбинация переходит в подмножество запрещенных кодовых комбинаций, то ошибка будет обнаружена. Однако если совокупность ошибок в данной кодовой комбинации превращает ее в какую-либо другую разрешенную, то в этом случае ошибки не могут быть обнаружены.
Поскольку любая из N разрешенных комбинаций может превратиться в любую из N0 возможных, то общее число таких случаев равно NN0. Очевидно, что число случаев, в которых ошибки обнаруживаются, равно N(N0 - N), где N0 - N – число запрещенных комбинаций. Тогда доля обнаруживаемых ошибочных комбинаций составит:
Например, если N0= 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 тройные). В общем случае при необходимости обнаруживать ошибки кратности до r0 включительно должно выполняться условие:
Действительно, одновременная ошибка в r0 разрядах кода создает новую кодовую комбинацию, отстоящую от первой на расстоянии r0. Чтобы она не совпала с какой-либо другой разрешенной кодовой комбинацией, минимальное расстояние между двумя разрешенными кодовыми комбинациями должно быть хотя бы на единицу больше, чем r0.
Для исправления rи-кратной ошибки необходимо, чтобы новая кодовая комбинация, полученная в результате такой ошибки, не только не совпадала с какой-либо разрешенной комбинацией, но и оставалась ближе к правильной комбинации, чем к любой другой разрешенной. Иными словами, должно выполняться соотношение:
Учитывая, что ru и d целые числа, получаем:
Так, для исправления одиночной ошибки расстояние Хэмминга между разрешенными кодовыми комбинациями должно быть не менее трех. При n = 3 за разрешенные комбинации можно, например, принять 000 или 111. Тогда разрешенной комбинации 000 необходимо сопоставить подмножество запрещенных кодовых комбинаций 001, 010, 100, образующихся в результате возникновения единичной ошибки в комбинации 000. Подобным же образом разрешенной комбинации 111 необходимо сопоставить подмножество запрещенных кодовых комбинаций: 110, 011, 101, образующихся в результате возникновения единичной ошибки в комбинации 111:
Таким образом, при n = 3 имеем N0 = 23 = 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 | |