Кодовое расстояние d - число позиций, в которых две кодовые комбинации отличаются друг от друга. Кодовое расстояние можно найти в результате сложения по модулю 2 одноименных разрядов кодовой комбинации.
Например. A=01101
B=10111
11010 → d=3
Кодовое расстояние часто называют кодом Хемминга. Кодовое расстояние между различными комбинациями конкретного кода может быть различным.
Минимальное кодовое расстояние - это минимальное расстояние между разрешенными кодовыми комбинациями данного кода. является основной характеристикой корректирующей способности кода.
Декодирование после приема может производиться таким образом, что принятая комбинация отождествляется с той разрешенной, которая находится от нее на наименьшем кодовом расстоянии. Такое декодирование называется декодированием по методу максимального правдоподобия.
Например, при d=1 все кодовые комбинации называют разрешенными. Пусть n=3 , кодовые комбинации: 000, 001, 010, 100, 110, 111, 101. Любая одиночная ошибка в таком коде переводит заданную разрешенную комбинацию в другую разрешенную комбинацию. Это случай без избыточного кода, не обладающего корректирующей способностью.
Если предположить, что d=2, и для n=3 сформируем набор разрешенных комбинаций:
000, 011, 101, 110 - разрешенные комбинации;
001, 010, 100, 111 - запрещенные комбинации.
При этом однократная ошибка переведет кодовую комбинацию из категории разрешенных в категорию запрещенных. Этот факт позволяет обнаружить наличие ошибки. Эти ошибки будут обнаружены, если кратность их нечетная. При d=2 и более в кодах появляется корректирующее свойство.
В общем случае при необходимости обнаружения ошибки с кратностью s очевидно, что (граница обнаружения ошибки кратностью s).
Для исправления одиночной ошибки в разрешенной кодовой комбинации необходимо составить подмножества кодовых комбинаций, зная, в каком подмножестве запрещенных кодовых комбинаций окажется принятая, можно точно восстановить переданную комбинацию, т.е. исправить ошибки.
Рассмотрим случай, когда d=3 и n=3.
001
010
100
Разрешенные кодовые комбинации
0
Запрещенные кодовые комбинации
00
111
110
101
011
Тогда по принятой комбинации 011 и факту её попадания в запрещенную кодовую комбинацию ошибка будет обнаружена, а зная, что подмножество запрещенных комбинаций соответствует разрешенной комбинации 111, мы можем исправить принятую комбинацию на разрешенную. Код при этих условиях обладает свойствами исправления ошибок. В общем случае для обеспечения возможности исправления всех ошибок кратности до t включительно при декодировании при методе максимального правдоподобия, каждая из ошибок декодирования должна приводить к запрещенной комбинации, относящейся к подмножеству исходных разрешенных кодовых комбинаций:
- граница исправления ошибок кратностью t.
Общая граница обнаружения и исправления ошибок с соответствующей кратностью:
.
Таким образом, задача построения помехоустойчивой корректирующей способностью сводится к обеспечению необходимого минимального кодового расстояния. Увеличение минимального кодового расстояния приводит к росту избыточности кода, при этом желательно, чтобы число проверочных символов было минимальным. Это противоречие разрешается через определение верхней и нижней границ числа проверочных символов.
В настоящее время известен ряд границ, которые устанавливают взаимосвязь между кодовым расстоянием и числом проверочных символов. Кроме того, эти границы позволяют определить вероятность ошибки декодирования.
Граница Хемминга находится из соотношения известного для числа разрешенных комбинаций:
, где n=k+r – число символов; t = - кратность исправляемых ошибок; - число сочетаний из n по i.
Применение границы Хемминга дает результаты близкие к оптимальным для высокоскоростных кодов > 0,3.
Для низкоскоростных кодов, т.е. R = ≤ 0,3, границу числа проверочных символов называют границей Плоткина:
Достарыңызбен бөлісу: |