Основные определения

Повышение требований к скорости и достоверности передачи информации, увеличение протяженности линий связи приводит к необходимости принятия специальных мер, направленных на уменьшение вероятности возникновения ошибок в процессе передачи. Одним из возможных решений указанной задачи служит помехоустойчивое кодирование. Под помехоустойчивыми понимаются коды, позволяющие обнаруживать и исправлять ошибки, возникающие при передаче из-за воздействия помех. Суть данной процедуры состоит во введении в информационный поток специальным образом дополнительных символов, в результате чего каждому блоку из k информационных бит сопоставляется n символьная последовательность – число возможных сообщений. Поскольку , то не все последовательности длины n используются при кодировании M сообщений. Комбинации символов, используемые для отображения информационных блоков или сообщений, называют разрешенными комбинациями или кодовыми последовательностями (словами), тогда как остальные – запрещенными. Вся совокупность кодовых слов образует код, для обозначения которого обычно говорят «код объема длины ». Множество символов, из которых составляются кодовые слова, называется алфавитом кода, а число различных символов в алфавите – основанием кода, или объемом (мощностью) алфавита.

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

Пример 5.1.1. Предположим, что по двоичному симметричному каналу (ДСК) передается сообщений. В простейшем варианте для передачи этого количества сообщений достаточно двух бит, т.е. сопоставить сообщениям двоичные кодовые слова вида 00, 10, 01 и 11 соответственно. Хотя подобное сопоставление может рассматриваться как примитивное кодирование (каждое сообщение отображается в двоичный вектор размерности ), оно не предполагает никаких мер для борьбы с канальными искажениями. Данный вариант отображения может быть назван безызбыточным кодированием. Достаточно исказиться одному символу – мерного вектора (например, входная последовательность 10 трансформируется в 11), как на приемной стороне будет принято неправильное решение о переданном сообщении (вместо будет принято решение в пользу ). Если же осуществить специальное кодирование, предусматривающее введение избыточных символов, появляется возможность защитить передаваемую информацию от искажения в канале. Например, сопоставим упомянутым выше 4-м сообщениям – мерные двоичные вектора, состоящие из 5–ти символов: 00000, 10110, 01101 и 11011. В этом случае искажение одного символа последовательности не приведет к неправильному решению о переданном сообщении, если принятие решения основывается на «близости» (минимальном отличии в числе символов) принятой последовательности от кодового слова. Так, при векторе на выходе канала вида 10111, отличающемся от кодовых слов в 4-х, 1-й, 3-х и 2-х позициях соответственно, принимается решение о передаче сообщения . Не трудно убедиться, что данный вариант кодирования позволяет исправлять любую однократную ошибку в передаваемой последовательности. Появление указанной способности объясняется введение добавочных (проверочных) символов в кодовом слове, т.е. за счет введения избыточности.

Важной характеристикой кода является скорость кода, определяемая соотношением

. (5.1)

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

. (5.2)

Параметр (5.2) показывает, какое количество бит информации передается за единицу времени, и измеряется в бит/сек.

Скорость кода является важнейшей характеристикой, так как входит в условия прямой и обратной теорем помехоустойчивого кодирования. Она определяет ту избыточность, которая вводится в кодовые слова для противодействия помехам в канале связи. Для двоичных кодов, в словах которых символы могут принимать только 2 значения, скорость лежит в диапазоне от 0 до 1. При в коде отсутствует избыточность и, следовательно, он не способен ни обнаруживать, ни исправлять ошибки. Избыточность кода уменьшает скорость, но, как показывает пример 5.1.1, позволяет понизить вероятность ошибочного приема.

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

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

Классификация кодов может быть осуществлена и по возможности выделения информационных символов в кодовом слове. Коды, в которых, как правило, первые позиций занимают информационные символы, называются систематическими кодами. В противном случае – несистематическимими. В рассмотренном ранее примере 5.1.1 представлен систематический блоковый код, поскольку первые два символа кодовых слов являются информационными.

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

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