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

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

кафедра РЭС

реферат на тему:

«Основные параметры помехоустойчивого кодирования. Основные параметры помехоустойчивых кодов»

МИНСК, 2009

ОСНОВНЫЕ ПРИНЦИПЫ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ

Кодирование с исправлением ошибок, по существу, представляет собой метод обработки сигналов, предназначенный для увеличения надежности передачи по цифровым каналам. Хотя различные схемы кодирования очень непохожи друг на друга и основаны на различных математических теориях, всем им присущи два общих свойства. Одно из них - использование избыточности. Закодированные цифровые сообщения всегда содержат дополнительные, или избыточные, символы. Эти символы используют для того, чтобы подчеркнуть индивидуальность каждого сообщения. Их всегда выбирают так, чтобы сделать маловероятной потерю сообщением его индивидуальности из-за искажения при воздействии помех достаточно большого числа символов. Второе свойство состоит в усреднении шума. Эффект усреднения достигается за счет того, что избыточные символы зависят от нескольких информационных символов. Для понимания процесса кодирования полезно рассмотреть каждое из этих свойств отдельно.

Рассмотрим вначале двоичный канал связи с помехами, приводящими к тому, что ошибки появляются независимо в каждом символе и средняя вероятность ошибки равна Р=0,01. Если требуется рассмотреть произвольный блок из 10 символов на выходе канала, то весьма трудно выявить символы, которые являются ошибочными. Вместе с тем если считать, что такой блок содержит не более трех ошибок, то мы будем неправы лишь два раза на миллион блоков. Кроме того, вероятность, что мы окажемся правы, возрастает с увеличением длины блока. При увеличении длины блока доля ошибочных символов в блоке стремится к средней частоте ошибок в канале, а также, что очень важно, доля блоков, число ошибок в которых существенно отличается от этого среднего значения, становится очень малой. Простые вычисления помогают понять, насколько верным является это утверждение. Рассмотрев, например, тот же канал, вычислим вероятность того, что доля ошибочных символов превышает значение p, и построим график этой функции для нескольких значений длины блока.

Рис. 1. Вероятность того, что доля ошибочных символов e/N в блоке длиной N превышает р при вероятности Р _e =0,01

Кривые на рис.1 показывают, что при обработке символов блоками, а не одного за другим можно уменьшить общую частоту ошибок. При этом потребуется, чтобы существовала схема кодирования, нечувствительная к ошибкам в некоторой доле символов блока и не приводящая при этом к потере сообщением своей индивидуальности, т. е. не приводящая к ошибочному блоку. Из графиков для различных длин блоков видно, какую именно долю ошибок нужно исправлять, чтобы получить заданную вероятность ошибки блока. Он показывает также, что при фиксированной вероятности ошибки блока доля ошибок, которые нужно исправлять, уменьшается при возрастании длины блока. Сказанное свидетельствует о резервах улучшения характеристик при усреднении шума и о том, что эти резервы возрастают при увеличении длины блока. Таким образом, длинные блоковые коды эффективнее коротких. После того как установлена целесообразность исправления ошибок в символах, возникает следующий логичный вопрос: как это сделать? Ключ лежит в избыточности. После некоторых размышлений читатель поймет, что при исправлении ошибок в сообщении, представляемом последовательностью из n двоичных символов, очень важно учесть, чтобы не все 2ⁿ возможных последовательностей представляли сообщения. В самом деле, когда каждая из возможных принятых последовательностей n символов представляет некоторое сообщение, нет никаких оснований считать, что одна последовательность является более правильной, чем любая другая. Продолжая рассуждать таким же способом, можно ясно увидеть, что для исправления всех наборов из t или менее ошибок необходимо и достаточно, чтобы каждая последовательность, представляющая сообщение, отличалась от последовательности, представляющей любое другое сообщение, не менее чем в 2t+1 местах. Например, для исправления всех одиночных или всех двойных ошибок в символах нужно, чтобы каждые две последовательности, представляющие разные сообщения, отличались не менее чем в пяти символах. Каждая принятая последовательность, содержащая два ошибочных символа и, следовательно, отличающаяся от посланной последовательности ровно в двух местах, будет всегда отличаться от всех других последовательностей, представляющих сообщения, не менее чем в трех местах. Число позиций, в которых две последовательности отличаются друг от друга, будем называть расстоянием Хемминга d между этими двумя последовательностями. Наименьшее значение d для всех пар кодовых последовательностей называется кодовым расстоянием и обозначается d_min . Поскольку d_min всегда должно быть на единицу больше удвоенного числа исправляемых ошибок, можно написать t=[(d_min -l)/2], где [ ] обозначает целую часть. Параметр t указывает, что все комбинации из t или менее ошибок в любой принятой последовательности могут быть исправлены.Имеются модели каналов, в которых значение t может быть больше указанного.

Пример. Рассмотрим код, состоящий из четырех кодовых слов 00000, 00111,11100 и 11011. Каждое кодовое слово используется для представления одного из четырех воз