Доля ошибок, обнаруживаемых корректирующим кодом

Найдем долю обнаруживаемых ошибок.

Доля обнаруживаемых ошибок равна

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

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

Тогда

Например, если N₀=100, N=20, то ошибка обнаруживается в 80% случаев.

Рассуждения поясняются рисунком:

Доля ошибок, исправляемых корректирующим кодом

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

Множество всех запрещенных комбинаций разобьем на N непересекающихся подмножеств (число подмножеств должно быть равно числу разрешенных комбинаций, а их N). Каждое полученное подмножество, состоящее из запрещенных комбинаций, приписывается одной из разрешенных кодовых комбинаций. Способ приема состоит в том, что если при­нята запрещенная комбинация, приписанная i-ой разрешенной комбинации, то считается, что и передана i-ая разрешенная комбинация.

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

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

Доля исправляемых ошибок равна

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

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

Тогда

Например, если N₀=100, N=20, то ошибка обнаруживается в 5% случаев.

Кодовое расстояние

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

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

Пример

Определить расстояние между кодовыми комбинациями 01011 и 10010.

Для решения найдем сумму этих комбинаций по модулю 2:

Число единиц в полученной сумме равно 3, следовательно, кодовое расстояние равно 3.

Обычно кодовое расстояние обозначают d (d=3).

Для анализа корректирующих свойств кода используется минималь­ное кодовое расстояние или расстояние Хэмминга, которое обозна­чают через d₀.

Чтобы определить d₀, составляются все возможные разрешенные кодовые комбинации и определяются кодовые расстояния между возможными парами комбинаций. Минимальное из найденных значений и будет d₀.

Любой простой код (например, МТК-2) имеет d₀=1. Каждая кодовая комбинация такого кода является разрешенной, поэтому он не может обнаруживать и исправлять ошибки. Следовательно, помехоустойчивые коды долж­ны иметь минимальное кодовое расстояние d₀ 2. Нужное кодовое расстояние устанавливается введением определенного количества дополни­тельных разрядов в кодовую комбинацию.