Избыточные коды

Вступление.

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

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

Существуют избыточные коды с обнаружением (они только обнаруживают ошибку) и коды с исправлением (эти коды обнаруживают место ошибки и исправляют ее).

Для различных помех в канале существуют различные по своей структуре и избыточности коды. Обычно избыточность кодов находится в пределах 10…60% или чуть больше. Избыточность 1/4 (25%) применяется при записи информации на лазерные диски и в системах цифрового спутникового ТВ.

Классификация кодов.

Известно большое число помехоустойчивых кодов, которые классифицируются по различным признакам. По­мехоустойчивые коды можно разделить на два больших класса: блочные и непрерывные. При блочном кодировании последова­тельность элементарных сообщений источника разбивается на от­резки и каждому отрезку ставится в соответствие определенная последовательность (блок) кодовых символов, называемая обыч­но кодовой комбинацией. Множество всех кодовых комбинаций, возможных при данном способе блочного кодирования, и есть блочный код.

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

Блочные коды бывают разделимыми и неразделимыми. К разделимым относятся коды, в которых символы по их назначению могут быть разделены на информационные символы, несущие ин­формацию о сообщениях и проверочные. Такие коды обознача­ются как (n, k), где n- длина кода, k- число информационных символов. Число комбинаций в коде не превышает 2^k. К нераздели­мым относятся коды, символы которых нельзя разделить по их назначению на информационные и проверочные.

Коды с постоянным весом характеризуются тем, что их кодо­вые комбинации содержат одинаковое число единиц: Примером такого кода является код “3 из 7”, в котором каждая кодовая комбинация содержит три единицы и четыре нуля (стандартных телеграфный код № 3).

Коды с постоянным весом позволяют обнаружить все ошибки кратности q=1, .,n за исключением случаев, когда число еди­ниц, перешедших в нули, равно числу нулей, перешедших в еди­ницы. В полностью асимметричных каналах, в ко­торых имеет место только один вид ошибок (преобразование ну­лей в единицы или единиц в нули), такой код дозволяет обнару­жить все ошибки. В симметричных каналах вероятность необна­руженной ошибки можно определить как вероятность одновременного искажения одной единицы и одного нуля:

где Pош вероятность искажения символа.

Среди разделимых кодов различают линейные и нелинейные. К линейным относятся коды, в которых поразрядная сумма по модулю 2 любых двух кодовых слов также является кодовым словом. Линейный код называется систематическим, если первые k символов его любой кодовой комбинации являются информаци­онными, остальные (n- k) символов — проверочными.

Среди линейных систематических кодов наиболее простой код (n, n-k), содержащий один проверочный символ, ко­торый равен сумме по модулю 2 всех информационных символов. Этот код, называемый кодом с проверкой на четность, позволяет обнаружить все сочетания ошибок нечетной кратности. Вероятность необнаруженной ошибки в первом приближении можно определить как вероятность искажения двух символов:

Подклассом линейных кодов являются циклические коды. Они характеризуются тем, что все наборы, образованные циклической перестановкой любой кодовой комбинации, являются также кодо­выми комбинациями. Это свойство позволяет в значительной сте­пени упростить кодирующее и декодирующее устройства, особен­но при обнаружении ошибок и исправлении одиночной ошибки. Примерами циклических кодов являются коды Хэмминга, коды Боуза - Чоудхури - Хоквингема (БЧХ — коды) и др.

Перейти на страницу номер:
 1  2  3  4  5  6