10.3. Понятие о помехоустойчивом кодировании

Код – это совокупность символов в представлении информации. Каждому знаку соответствует определённая комбинация нулей и единиц (бинарное кодирование).

Простой код – если все его символы используются для представления информации.

Равномерный код – если все его слова имеют одинаковое количество разрядов.

Существуют коды обнаруживающие ошибки и коды, обнаруживающие и исправляющие ошибки.

Как правило, при передаче информации используется избыточность – не все разряды используются для передачи информации, не все 2ⁿ (где n количество разрядов) комбинаций используются для её представления.

Разделяют разрешённые и запрещённые комбинации. Появление запрещённых комбинаций – ошибка передачи информации.

В теории кодирования используется понятие кодового расстояния (расстояние Хэмминга).

d – кодовое расстояние – это число разрядов, по которым отличаются две кодовые комбинации.

В этих двух четырехразрядных кодовых комбинациях d=2.

Рассмотрим двухразрядную информацию.

При различных ошибках (типа инверсии разряда) можно получить различные комбинации, причём они входят в исходное множество комбинаций. Поэтому по виду комбинации нельзя обнаружить ошибку. Необходимо, чтобы при возникновении ошибки полученные коды не входили в число используемых.

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

d_min  t +1,

где t – кратность ошибок, а d_min – минимальное кодовое расстояние.

Здесь уже можно обнаружить ошибку, но нельзя её исправить. Исправить ошибку, значит, по виду принятой комбинации установить, какая истинная комбинация передавалась.

Для исправления необходимо: d_min2t+1 (рис. 83).

Рис. 83. Принцип исправления ошибок

От каждой из четырех комбинаций, указанных на рис. 83, ошибочная комбинация с t-кратной ошибкой отличается в t разрядах, поэтому необходимо, чтобы сами ошибочные комбинации отличались друг от друга хотя бы в одном разряде, иначе восстановить передаваемую информацию невозможно. Например, рис. 84 иллюстрирует возможные ошибки при передаче трехразрядной информации.

Рис. 84. Возможные ошибки при передаче трехразрядной информации

и некоторые кодовые расстояния

Примеры кодов.

1. Код с проверкой четности.

x2	x2	k
0	0	1
0	1	0
1	0	0
1	1	1

где k – контрольный разряд, чтобы сумма единиц была четной, либо нечетной. Это – контроль по четности (нечетности). В настоящее время широко применяется в стандартных микропроцессорах (ранее – только в особо ответственных вычислительных системах, например, военных).

В приемнике формируется контрольный разряд с помощью элемента сложения по модулю 2 (рис. 85).

Рис. 85. Передатчик и приемник информации с контролем по нечетности на основе элементов сложения по модулю 2 с инверсией

2. Коды с простым повторением – это коды, в которых повторяется кодовая комбинация.

3. Корреляционные коды.

В таких кодах используются дополнительные символы для представления информации:

001

110

4. Равновесные коды.

Характеризуются тем, что каждая комбинация содержит одинаковое количество нулей и единиц. Например, 2 из 5:

011000

110001

101002

100103

010104

001105

100016

010017

001018

000119

Существуют также систематические коды, где контрольные разряды отделены от информационных. К ним относятся коды Хэмминга.