Обнаружение и исправление ошибок

Помехоустойчивое кодирование

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

Классификация помехоустойчивых кодов

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

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

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

Наличие в кодовых комбинациях заведомо большего числа единичных элементов n>m, чем это минимально необходимо для первичного кодирования, приводит к тому, что из общего числа N=2ⁿ кодовых комбинаций (n, m) только N_p=2^m разрешены, а остальные (N-N_p) являются запрещенными и для кодирования сообщений не используются. Избыточность помехоустойчивых кодов оценивается коэффициентом избыточности

.

По своим корректирующим свойствам избыточные коды делятся на коды, обнаруживающие ошибки, исправляющие ошибки и частично обнаруживающие и исправляющие ошибки. Очевидно, что чем больше избыточность кода, тем лучше его корректирующие свойства. Это объясняется тем, что чем больше r и значит n при заданном m, тем легче из общего числа кодовых комбинаций N выбрать N_p разрешенных кодовых комбинаций, заметно отличающихся друг от друга.

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

Например, кодовое расстояние d между комбинациями 100001 и 011000 будет равно d=4. Весом V кодовой комбинации является количество входящих в нее единиц. Вес комбинации 100001 равен V=2, а вес комбинации 011000 равен V=2.

С другой стороны сумма этих комбинаций по модулю 2 дает суммарную комбинацию 111001, вес которой V=4 и равен кодовому расстоянию между комбинациями-слагаемыми 100001 и 011000

Корректирующие свойства кода определяются минимальным кодовым расстоянием d₀ (расстояние Хэмминга) между любыми двумя кодовыми комбинациями. Так, например, для первичного кода МТК-2, все кодовые комбинации разрешены и расстояние Хэмминга d₀ = 1. Это означает, что искажение хотя бы одного единичного элемента любой кодовой комбинации кода МКТ-2, приводит к замене этой кодовой комбинации на другую, т.е. ошибки не могут быть обнаружены. Для обнаружения ошибок необходимо, чтобы d₀ ³ t₀ + 1, где t₀ – кратность обнаруживаемых кодом ошибок.

Для исправления ошибок необходимо, чтобы расстояние от принимаемой с ошибками запрещенной комбинации до переданной комбинации было меньше, чем до любой другой разрешенной комбинации. Другими словами необходимо, чтобы кратность ошибки не превышала половины кодового расстояния d₀ ³ 2t_u + 1, где t_u – кратность исправляемых ошибок. Определяемые из указанных выражений значения t₀ и t_u дают число гарантированно обнаруживаемых и исправляемых ошибок. Из этих выражений также следует, что коды, исправляющие ошибки, можно использовать для гарантированного обнаружения ошибок кратностью t₀=2t_u. Чтобы код обнаруживал ошибки кратностью t₀ и исправлял ошибки кратностью t_u кодовое расстояние должно быть d₀ ³ t₀ + t_u + 1.