2.6. Основные принципы помехоустойчивого кодирования
При дальнейшем рассмотрении помехоустойчивых кодов будем полагать их блочными и равномерными.
Для иллюстрации идеи помехоустойчивого кодирования рассмотрим двоичный код, нашедший на практике наиболее широкое применение. Напомним, что двоичный код – это код с основанием В = 2; количество разрядов m в кодовой комбинации принято называть длиной или значностью кода; символы каждого разряда могут принимать значения 0 и 1; количество единиц в кодовой комбинации называют весом кодовой комбинации и обозначают w.
Например, кодовая комбинация 100101100 характеризуется значностью
m = 9 и весом w = 4.
Степень отличия любых двух кодовых комбинаций данного кода характеризуется так называемым расстоянием между кодами d. Оно выражается числом позиций или разрядов, в которых комбинации отличаются одна от другой, и определяется как вес суммы по модулю два этих кодовых комбинаций. Например, для определения расстояния между комбинациями 100101100 и 110110101 необходимо просуммировать их по модулю два:
Полученная в результате суммирования новая кодовая комбинация характеризуется весом w = 4. Следовательно, расстояние между исходными кодовыми комбинациями d = 4.
Ошибки вследствие воздействия помех проявляются в том, что в одном или нескольких разрядах кодовой комбинации нули переходят в единицы и, наоборот, единицы переходят в нули. В результате создается новая – ложная – кодовая комбинация.
Если ошибки происходят только в одном разряде кодовой комбинации, то их называют однократными. При наличии ошибок в двух, трех и т. д. разрядах ошибки называют двукратными, трехкратными и т. д.
Для указания мест в кодовой комбинации, где имеются искажения символов, используется вектор ошибки V. Вектор ошибки m-разрядного кода – это m-разрядная комбинация, единицы в которой указывают положение искаженных символов кодовой комбинации. Например, если для пятиразрядного кода вектор ошибки имеет вид V = 01100, то это значит, что имеют место ошибки в третьем и четвертом разрядах кодовой комбинации.
Вес вектора ошибки Wv характеризует кратность ошибки. Сумма по модулю два для искаженной кодовой комбинации и вектора ошибки дает исходную неискаженную комбинацию.
Как уже отмечалось, помехоустойчивость кодирования обеспечивается за счет введения избыточности в кодовые комбинации. Это значит, что из m символов кодовой комбинации для передачи информации используется k < m символов. Следовательно, из общего числа N0 = 2m возможных кодовых комбинаций для передачи информации используется только N = 2k комбинаций. В соответствии с этим все множество возможных кодовых комбинаций
(N0 = 2m) делится на две группы. В первую группу входит множество N = 2k разрешенных комбинаций, вторая группа включает в себя множество
(N0 – N) = 2m – 2k запрещенных комбинаций. Если на приемной стороне установлено, что принятая комбинация относится к группе разрешенных, то считается, что сигнал пришел без искажений. В противном случае делается вывод, что принятая комбинация искажена. Это справедливо для таких помех, которые своим воздействием переводят разрешенные кодовые комбинации в запрещенные, т.е. когда исключена возможность перехода одних разрешенных комбинаций в другие.
В общем случае каждая из N разрешенных комбинаций может трансформироваться в любую из N0 возможных комбинаций, т. е. всего имеется
(N · No) возможных вариантов приема, из них N вариантов безошибочного приема, N(N – 1) вариантов перехода в другие разрешенные комбинации и
N (N0 – N) вариантов перехода в запрещенные комбинации.
Таким образом, не все искажения могут быть обнаружены. Доля обнаруживаемых ошибочных комбинаций составляет N(N0 – N)/(N · No) = 1 – N/N0 .
Для использования данного кода в качестве исправляющего множество запрещенных кодовых комбинаций разбивается на N непересекающихся подмножеств Мk. Каждое из подмножеств Мk ставится в соответствие одной из разрешенных комбинаций.
Если принятая запрещенная комбинация принадлежит подмножеству Мi, то считается, что передана комбинация Ai. Ошибка будет исправлена в тех случаях, когда полученная комбинация действительно образовалась из комбинации Ai. Таким образом, ошибка исправляется в (N0 – N) случаях, равных количеству запрещенных комбинаций. Доля исправляемых ошибочных комбинаций от общего числа обнаруживаемых ошибочных комбинаций составляет (N0 – N)/N(N0 – N) = 1/N.
Способ разбиения на подмножества зависит от того, какие ошибки должны исправляться данным кодом.
2.7. Связь корректирующей способности кода с кодовым расстоянием
Для оценки степени различия между двумя произвольными комбинациями данного кода используется характеристика, получившая название расстояния между кодовыми комбинациями d. Наименьшее расстояние между разрешенными кодовыми комбинациями dмин является характеристикой кода и характеризует его корректирующие способности. Рассмотрим это на конкретных примерах.
Пусть необходимо построить код, обнаруживающий все ошибки кратностью S и ниже. Построить такой код – это значит из множества N0 возможных выбрать N разрешенных комбинаций так, чтобы любая из них в сумме по модулю два с любым вектором ошибок с весом Wl £ S не дала бы в результате никакой другой разрешенной комбинации. Для этого необходимо, чтобы наименьшее кодовое расстояние удовлетворяло условию
dмин = S + 1. (2.3)
В качестве примера рассмотрим код со значностью m = 3. Все возможные комбинации такого кода представлены в табл. 2.9. Значения расстояний между кодовыми комбинациями приведены в табл. 2.10.
Таблица 2.9
|
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
|
0 0 0 |
0 0 1 |
0 1 0 |
0 1 1 |
1 0 0 |
1 0 1 |
1 1 0 |
1 1 1 |
Таблица 2.10
|
A0 |
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
|
|
A0 |
0 |
1 |
1 |
2 |
1 |
2 |
2 |
3 |
|
A1 |
1 |
0 |
2 |
1 |
2 |
1 |
3 |
2 |
|
A2 |
1 |
2 |
0 |
1 |
2 |
3 |
1 |
2 |
|
A3 |
2 |
1 |
1 |
0 |
3 |
2 |
2 |
1 |
|
A4 |
1 |
2 |
2 |
3 |
0 |
1 |
1 |
2 |
|
A5 |
2 |
1 |
3 |
2 |
1 |
0 |
2 |
1 |
|
A6 |
2 |
3 |
1 |
2 |
1 |
2 |
0 |
1 |
|
A7 |
3 |
2 |
2 |
1 |
2 |
1 |
1 |
0 |
Для того чтобы код обеспечивал обнаружение однократных ошибок, необходимо из всего множества N0 = 8 возможных комбинаций выбрать в качестве разрешенных такие, расстояние между которыми было бы не менее d = = 2. Как видно из таблицы расстояний, в качестве разрешенных комбинаций в этом случае можно выбрать следующие:
A0 = 000; А3 = 011; А5 = 101; А6 = 110
или
A1 = 001; А2 = 010; А4 = 100; А7 = 111.
Для обнаружения двукратных ошибок наименьшее расстояние должно быть равно dмин = 3. При этом в качестве примера разрешенных комбинаций можно выбрать A0 = 000; A7 = 111.
Пусть требуется построить код, обеспечивающий устранение однократных ошибок. Выбираем в качестве первой разрешенной комбинации A0 = 000. При наличии однократных ошибок комбинация A0 может перейти в одну из следующих запрещенных комбинаций: А1 = 001, А2 = 010 и A4 = 100. Комбинации A1, A2 и A4 можно принять в качестве подмножества запрещенных комбинаций для A0. Последнее означает, что в случае приема одной из комбинаций этого подмножества выносится решение, что передана комбинация A0.
Пусть в качестве второй разрешенной комбинации выбирается комбинация, отстоящая от первой на расстоянии d = 2, например А3 = 011. Ей должно соответствовать подмножество запрещенных комбинаций А2 = 010; A1 = 001 и A7 = 111. Однако получилось пересечение подмножеств. При приеме запрещенных сигналов А1 или A2 нельзя однозначно установить, какой был передан сигнал – A0 или А3.
Если же в качестве второй разрешенной комбинации выбрать комбинацию, отстоящую от A0 на d = 3, т. е. комбинацию A7 = 111, которой соответствует подмножество запрещенных комбинаций А3 = 011, А5 = 101 и a6 = 110, то в этом случае подмножества запрещенных комбинаций не пересекаются. Следовательно, при d = 3 обеспечивается устранение всех однократных ошибок.
В общем случае для устранения ошибок кратности Z кодовое расстояние должно удовлетворять условию
dмин = 2Z + 1. (2.4)
Аналогично рассуждая, можно установить, что для исправления всех ошибок кратности не более Z и одновременно обнаружения всех ошибок кратности не более S (при S ³ Z ) кодовое расстояние должно удовлетворять условию
dмин = S + Z + 1. (2.5 )