Общая характеристика блочных кодов

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

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

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

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

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

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

Для коррекции наиболее вероятных ошибок, т.е. ошибок малой кратности, следует принимать решение, что была передана та разрешенная комбинация, которая отличается от принятой наименьшим числом символов. Различие между комбинациями принято характеризовать расстоянием Хэмминга d, равным числу разрядов, в которых две комбинации имеют различные, т.е. не совпадающие символы. Например, комбинация 0100 отличается от комбинации 1000 в двух разрядах, следовательно, дистанция (расстояние) Хэмминга между этими комбинациями равна двум. Чем больше минимальное расстояние между разрешенными комбинациями кода (кодовое расстояние d₀), тем больше корректирующие возможности кода. Так, при кодовом расстоянии d₀ = 2 код дает возможность обнаруживать только одиночные ошибки, при d₀ = 3 - исправляет все одиночные ошибки или обнаруживает все одиночные и двойные ошибки. В общем случае для исправления ошибок кратности до S включительно кодовое расстояние должно удовлетворять условию d₀≥ 2S+1.

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

Из рис. 3.1 ясно, что при необходимости исправления всех одиночных ошибок в качестве разрешенных следует выбирать две комбинации, соответствующие противоположным вершинам куба (например, 101 и 010 или 000 и 111). Если необходимо только обнаруживать одиночные ошибки, в качестве разрешенных можно брать комбинации, различающиеся в двух разрядах (например, 001, 010 и 111).

Рассмотрим кратко свойства наиболее широко применяемых кодов.