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

ТЕМА 6. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ.

ОБЩИЕ ПРИНЦИПЫ ИСПОЛЬЗОВАНИЯ ИЗБЫТОЧНОСТИ ДЛЯ ОБЕСПЕЧЕНИЯ ПОМЕХОУСТОЙЧИВОСТИ КОДОВ.

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

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

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

Начнем эту серьезную тему со старого анекдота. Беседуют два пенсионера:

-Вы не могли бы сказать номер вашего телефона? – говорит один.

-Вы знаете, признается другой, - я, к сожалению, точно его не помню.

-Какая жалость, сокрушается первый, - ну скажите хотя бы приблизительно…

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

Рассмотрим например телефонный номер 34-33-44. Соответственно запись «трицть четре трцать три сорк чтре», в которой имеется не один, а несколько пропущенных символов, по-прежнему легко читается. Это связано с тем, наш язык имеет определенную избыточность, которая с одной стороны, увеличивает длину записи, а с другой – повышает надежность ее передачи. Это же свойство обеспечивает надежное общение людей даже при наличии у них дефектов речи. Объясняется это тем, что вероятность появления каждого последующего символа в цифровой записи телефона одинакова, в то время как в тексте, записанном словами русского языка, это не так. Очевидно, например, что твёрдый знак в русском языке появляется значительно реже, чем, например, буква «а». (Наиболее вероятно появление в русском языке буквы «о» p=0,096, наименее вероятно – буква «ф» p=0,002) Более того, некоторые сочетания букв более вероятны, чем другие, а такие, как два твердых знака подряд, невозможны в принципе, и т.д. Зная, какова вероятность появления какой-либо буквы в тексте, и сравнив её с максимальной, можно установить, насколько экономичен или избыточен данный способ кодирования (в нашем случае русский язык).

Мы уже знаем, что количество информации в сообщении тем больше, чем больше его неопределенность (энтропия). Для любой системы кодирования можно оценить её максимально возможную энтропию (информационную ёмкость) H_max , которая соответствует случаю равновероятности появления символов в коде и равна, как вы уже знаете, , где N – объём алфавита символов кода. Для русского языка H_max = 5 (если буквы е и ё неразличимы). Также можно определить действительную энтропию H. Для русского языка H » 1,5 бит. Случай H < H_max означает, что каждый символ (в русском языке буква) несет меньше информации, чем максимально возможно. Это явление называют избыточностью R (или редунданцией - redundancy) и вычисляют как отношение:

Измерение избыточности естественных языков дает потрясающие результаты: она составляет ~80%, а это свидетельствует о том, что практически 80% передаваемой с помощью языка информации является избыточной, т.е. лишней. Любопытен и тот факт, что показатели избыточности разных языков очень близки. Данная цифра примерно определяет теоретический предел сжатия текстовых файлов.

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

Все помехоустойчивые коды можно разделить на два типа:

· обнаруживающие (проверочные EDC – Error Detection Code);

· корректирующие (ECC – Error Correction Code).

У подавляющего большинства существующих в настоящее время помехоустойчивых кодов избыточность является следствием их алгебраической структуры. В связи с этим их называют алгебраическими кодами. Алгебраические коды можно подразделить на два больших класса: блоковые и непрерывные.

В случае блоковых кодов процедура кодирования заключается в сопоставлении каждой букве сообщения (или, что чаще, последовательности из k двоичных символов, соответствующих этой букве) блока из n двоичных символов. Блоковый код называют равномерным, если n остается постоянным для всех букв сообщения. Отношение k/n определяют как относительную скорость кода.

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

При кодировании неразделимыми кодами разделить символы выходной последовательности на информационные и проверочные невозможно.

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

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

Всего может быть 2^k различных входных и 2ⁿ различных выходных последовательностей. Из общего числа 2ⁿ выходных последовательностей только 2^k последовательностей соответствуют входным. Назовем их разрешенными кодовыми комбинациями. Остальные 2ⁿ-2^k возможные выходные последовательности для передачи не используются. Они могут возникнуть лишь в результате ошибки передачи. Назовем их запрещенными комбинациями.

Каждая из 2^k разрешенных комбинаций в результате действия помех может трансформироваться в любую другую, всего имеется 2^k2ⁿ возможных случаев передачи. В это число входят (рис. 6.1.):

· 2^k случаев безошибочной передачи ( );

· 2^k(2^k-1) случаев перехода в другие разрешенные комбинации, что соответствует необнаруживаемым ошибкам ( );

· 2^k(2ⁿ-2^k) случаев перехода в неразрешенные комбинации, которые могут быть обнаружены ( ).

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

Рис. 6.1. Трансформация передаваемых кодовых комбинаций.

Рассмотрим теперь случай исправления ошибок.

Любой метод помехоустойчивого кодирования можно рассматривать как правило разбиения всего множества запрещенных кодовых комбинаций на 2^k непересекающихся подмножеств M_i, каждое из которых ставится в соответствие одной из разрешенных комбинаций. При получении запрещенной комбинации, принадлежащей подмножеству M_i, принимается решение, что передавалась разрешенная комбинация A_i. Ошибка будет исправлена в тех случаях, когда полученная комбинация действительно образовалась из A_i, т.е. в (2ⁿ-2^k) случаях. Т.е. отношение числа исправляемых кодом ошибочных кодовых комбинаций к числу обнаруживаемых ошибочных комбинаций равно:

Способ разбиения на подмножества зависит от того, какие ошибки должны исправляться данным конкретным кодом.

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

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

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

При взаимно-независимых ошибках вероятность искажения любых r символов в n-разрядной кодовой комбинации

где количество способов, которыми можно выбрать из n элементов r (число сочетаний из n по r)