Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Лекции ТЦС на 2014.docx
Скачиваний:
4
Добавлен:
01.07.2025
Размер:
2 Мб
Скачать
☆

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

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

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

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

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

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

Ui

a1

a2

b

∑

U1

0

0

0

0

U2

0

1

1

2

U3

1

0

1

2

U4

1

1

0

2

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

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

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

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

А1

А2

А3

А4

А5

А6

А7

А8

000

001

010

011

100

101

110

111

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

А1

А2

А3

А4

А5

А6

А7

А8

А1

0

1

1

2

1

2

2

3

А2

1

0

2

1

2

1

3

2

А3

1

2

0

1

2

3

1

2

А4

2

1

1

0

3

2

2

1

А5

1

2

2

3

0

1

1

2

А6

2

1

3

2

1

0

2

1

А7

2

3

1

2

1

2

0

1

А8

3

2

2

1

2

1

1

0

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

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

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

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

Допустим, в качестве второй разрешенной комбинации выбрана А3=010, отстоящая на расстоянии d=2. Ей соответствует подмножество запрещенных комбинаций А4=011, А1=000 и А7=110. Однако получилось пересечение подмножеств запрещенных комбинаций. При приеме запрещенных комбинаций А4 и А1 нельзя однозначно установить, какая комбинация была послана – А2 или А3. Если же в качестве второй разрешенной комбинации принять А7=110, которой соответствуют запрещенные комбинации А8=111, А5=100 и А3=010, то в этом случае подмножества запрещенных комбинаций не пересекаются и имеется однозначное соответствие принятой и переданной комбинации.

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

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

dmin ≥ 2t + 1

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

 dmin ≥ t + τ + 1

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]