Метод контрольных сумм

Метод контроля четности

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

Рассмотрим простые практические способы построения кодов, способных обнаруживать и исправлять ошибки.

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

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

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

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

Пример:

Будем из входной последовательности символов брать по четыре информационных символа а₁а₂а₃а₄, дополнять их тремя контрольными символами а₅а₆а₇ и получившееся семисимвольное слово посылать в канал. Контрольные символы будем подбирать так, чтобы были четными следующие суммы:

s₁= а₁ +а₂ +а₃ + a₅,

s₂= а₁ +а₂ +а₄ + a₆,

s₃= а₁ +а₃ +а₄ + a₇.

В каждую сумму входит по оному контрольному символу, поэтому данное требование всегда выполнимо.

Благодаря «маленьким хитростям», предусмотренным при формировании контрольных сумм, проверка их четности на выходе канала позволяет однозначно установить, была ли допущена при передаче однократная ошибка и какой из разрядов был при этом искажен (ошибками большей кратности пренебрегаем).Действительно, если один из семи символов был искажен, то по крайней мере одна из сумм обязательно окажется нечетной, т.е. четность всех контрольных сумм s₁, s₂, s₃ свидетельствует об отсутствии однократных ошибок. Далее, лишь одна сумма будет нечетной в том, (и только в том) случае, если искажен входящий в эту сумму один из трех контрольных символов (a₅, a₆ или a₇). Нечетность двух сумм означает, что искажен тот из информационных символов а₂, а₃ или а₄, который входи в обе эти суммы. Наконец, нечетность всех трех сумм означает, что неверно принят входящий во все суммы символ а₁.

Итак, в данном примере метод контрольных сумм, увеличивая длину кода в 7/4=1,75 раза за счет введения избыточности, позволяет исправить любую однократную ошибку (но не ошибку большей кратности). Основываясь на этой идее, в принципе, можно построить коды, исправляющие все ошибки большей (но всегда ограниченной) кратности.