Помехоустойчивое кодирование. Помехоустойчивость кода. Корректирующие коды.

Помехоустойчивость кода.

Минимальное кодовое расстояние некоторого кода определяется как минимальное расстояние Хэмминга между любыми разрешенными кодовыми словами этого кода. У безызбыточного кода минимальное кодовое расстояние d_min=1. Чем больше минимальное кодовое расстояние, тем больше избыточность кода. Максимальное кодовое расстояние кода, очевидно, равно его размеру, т.е. числу двоичных разрядов в кодовом слове.

Непосредственные вычисления кодовых расстояний у рассмотренного выше кода, построенного методом контрольных сумм, дают следующие значения показателей: d_min=3 и d_max=7.

Очевидно, что -кратная ошибка приводит к тому, что искаженная кодовая комбинация отодвигается от исходной на расстояние. В то же время ошибка не может быть обнаружена, если она переводит одну разрешенную кодовую комбинацию в другую, тоже разрешенную. Следовательно, способность кода обнаруживать все ошибки некоторой кратности зависит от минимального расстояния между разрешенными кодовыми словами: чем больше минимальное кодовое расстояние, тем большей кратности требуется ошибка для перевода любой разрешенной кодовой комбинации в другую разрешенную. Таким образом, можно утверждать, что код с минимальным кодовым расстоянием d_min способен обнаруживать любые ошибки кратностью

У рассмотренного выше кода d_min=3, следовательно, он может обнаруживать любые однократные и двукратные ошибки.

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

У рассмотренного выше кода, построенного методом контрольных сумм, d_min=3, следовательно, он может исправлять только любые однократные ошибки.

Рассмотрим n-разрядный код, основанный на n- кратном повторении каждого передаваемого символа. У него d_min= n. Следовательно, максимальная кратность обнаруживаемых ошибок равна , что соответствует случаю искажения всех символов, кроме одного. Максимальная кратность исправляемых ошибок равна (n-1) /2, что соответствует искажению «почти» половины всех символов. Это соответствует фиксации ошибки при обнаружении хотя бы одного неодинакового символа и исправлению ошибки на основе определения, каких значений больше.

Рассмотрим n-разрядный код, основанный на введении одного разряда контроля четности. У него d_min= 2, и, следовательно, максимальеная кратность обнаруживаемых ошибок равна 1, а исправляемых – 0 (код не способен исправлять ошибки).

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

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

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