Связь между корректирующей способностью кода и кодовым расстоянием

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

Лекция №9. Методы и устройства помехоустойчивого кодирования

Цель лекции: изучение принципов помехоустойчивого кодирования

Содержание:

1. Основные принципы обнаружения и исправления ошибки.

2. Кодовое расстояние и корректирующая способность кода.

3. Границы для кодового расстояния.

4. Границы Варшамова - Гильберта, Плоткина.

5. Классификация корректирующих кодов.

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

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

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

Проиллюстрируем этот подход для (3,2)- кода: количество информационных разрядов k = 2, следовательно, число разрешенных кодовых комбинаций S_р = 2² = 4; общее число кодов S=2³ =8. Число проверочных бит r = n – k = 1 и устанавливать их значение условимся таким образом, чтобы количество «единиц» во всех кодовых комбинациях было бы четным (по этой причине такой проверочный бит называется битом четности).

Ui	a1	a2	b	∑
U1
U2
U3
U4

Будем обозначать разрешенные кодовые комбинации U_i. Их информационная часть может принимать значения 00, 01,10 и 11 (обозначим эти биты a₁ и a ₂); проверочный бит b принимает значения, приведенные в таблице. Последняя колонка содержит суммы (количество) бит со значением " 1 " в каждой кодовой комбинации. Любую из 8 существующих для n = 3 кодовых комбинаций можно считать вектором в пространстве, построенном на единичных векторах a₁, a₂, b – это иллюстрируется рисунком 9.1. Отметим разрешенные комбинации ноликами; остальные, очевидно, будут запрещенными - их отметим крестиками. Видно, что минимальное кодовое расстояние между разрешенными комбинациями равно 2 (расстояние между разрешенными вершинами по ребрам куба). На рисунке однократной ошибке соответствует переход из вершины куба в соседнюю вершину. Любая однократная ошибка переводит разрешенную комбинацию в запрещенную, следовательно, может быть обнаружена. Однако исправить такую ошибку нельзя, поскольку в любую из запрещенных вершин за один шаг можно попасть, по крайней мере, из двух разрешенных.

Рис. 9.1. К вопросу о связи кодового расстояния и корректирующей способности кода.

Обобщим рассуждения. Пусть необходимо построить код, обнаруживающий все ошибки кратности τ и меньше. Построить такой код – это значит из множества S возможных комбинаций выбрать S_p разрешенных комбинаций так, чтобы любая сумма по модулю 2 с любым вектором ошибок с весом ω ≤ τ не дала бы в результате никакой другой разрешенной комбинации. Для этого необходимо, чтобы наименьшее кодовое расстояние удовлетворяло условию

Рассмотрим код со значностью n=3. Все возможные комбинации этого кода приведены в таблице:

А1	А2	А3	А4	А5	А6	А7	А8

Составим матрицу кодовых расстояний:

	А1	А2	А3	А4	А5	А6	А7	А8
А1
А2
А3
А4
А5
А6
А7
А8

Для того, чтобы код обеспечивал обнаружение однократных ошибок, необходимо из 8 возможных комбинаций выбрать в качестве разрешенных такие, расстояние между которыми было бы не менее d=2. Например, определим разрешенными комбинациями такие: А₂ = 001, А₃ = 010, А₅ = 100, А₈ = 111. Любая однократная ошибка переводит разрешенную комбинацию в запрещенную.

Для обнаружения двукратных ошибок наименьшее кодовое расстояние должно быть d_min=3. В качестве примера разрешенных комбинаций в этом случае можно выбрать А₃=010 и А₆=101.

Пусть теперь необходимо построить код, обеспечивающий исправление однократных ошибок. Выберем в качестве первой разрешенной комбинации А₂=001. При однократной ошибке комбинация А₂ перейдет в одну из трех комбинаций: А₁=000, А₄=011 или А₆=101 (рис. 9.1). Эти комбинации объявляются запрещенными комбинациями для А₂. Это означает, что при появлении одной из этих комбинаций на выходе канала связи будет принято решение, что передана комбинация А₂.

А2

А3

А7

А1

А4

А6

А7

А3

А5

А8

d=3

d=2

Рис. 9.2. Варианты перехода между кодовыми комбинациями при однократной ошибке.

Допустим, в качестве второй разрешенной комбинации выбрана А₃=010, отстоящая на расстоянии d=2. Ей соответствует подмножество запрещенных комбинаций А₄=011, А₁=000 и А₇=110. Однако получилось пересечение подмножеств запрещенных комбинаций. При приеме запрещенных комбинаций А₄ и А₁ нельзя однозначно установить, какая комбинация была послана – А₂ или А₃. Если же в качестве второй разрешенной комбинации принять А₇=110, которой соответствуют запрещенные комбинации А₈=111, А₅=100 и А₃=010, то в этом случае подмножества запрещенных комбинаций не пересекаются и имеется однозначное соответствие принятой и переданной комбинации.

Следовательно, при d_min=3 обеспечивается исправление всех однократных ошибок.

В общем случае, для исправления ошибок кратности t минимальное кодовое расстояние должно удовлетворять условию

d_min ≥ 2t + 1

Аналогично рассуждая, можно установить, что для исправления всех ошибок кратности не более t и одновременного обнаружения всех ошибок кратности не более τ (при τ ≥ t) кодовое расстояние должно удовлетворять условию

d_min ≥ t + τ + 1

Дата добавления: 2014-10-22