$Математика$	Основы радиоэлектроники и связи
7. Основы теории информации и кодирования : 7.2. Кодирование сообщений

7.2.4 Корректирующие коды

Коды, позволяющие обнаружить и по возможности исправить ошибки при приеме, называются корректирующими.

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

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

сообщение A B C D

код 00 01 10 11.

Если передается сообщение В, то одиночная ошибка в первом знаке приведет к приему сообщения D, а ошибка во втором знаке – к А, двойные ошибки - к С. Эти ошибки не различимы из-за того, что все сообщения различаются только в одном или в двух знаках.

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

сообщение A B C D

код 000 011 101 110.

Здесь каждая комбинация отличается от другой двумя знаками. Для этого пришлось взять трехзначный код ( N=8 ).

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

сообщение A B C D

код 00000 01101 10110 11011.

Здесь пришлось применить пятизначный код. Пусть принята комбинация 01001. Такой комбинации в кодовой таблице нет. Следовательно, произошла ошибка. Принятая комбинация отличается от А и D в двух знаках, от В – в одном, от С – в пяти, следовательно передавалось сообщение В.

Чем больше исправляющая способность кода, тем выше кратность исправляемых ошибок, тем больше требуется знаков.

Само исправление происходит путем сравнения принятого кода с разрешенными, и если обнаружена ошибка, то истинной считается та комбинация, от которой принятая наименее отличается. Это достаточно сложная задача, приводящая к громоздким техническим решениям. Поэтому разрабатываются специальные коды, строение которых позволяет осуществить декодирование более простыми способами. Одним из таких кодов являются систематические коды – коды, у которых общее число знаков состоит из информационных знаков и контрольных знаков так что n = k + r.

Число информационных знаков определяется числом N различных сообщений, которые нужно передать, т.е. N=.

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

а) указать, есть ли ошибка или нет;

б) если ошибка есть, то указать в какой из n позиций она находится.

Исправление сводится к замене в указаном месте нуля единицей или наоборот. Таким образом, нужна одна кодовая комбинация для ответа “да” или “нет” на вопрос о наличии ошибки и n кодовых комбинаций для указания номера ошибочной позиции. Отсюда должно выполняться неравенство

или

В ранее расмотренном примере приема кодовых комбинаций N =4=, k =2, n =5, r =3. Первые два знака – информационные, а последние 3 – контрольные.

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