Коды, исправляющие ошибки

Особое значение имеют помехозащитные коды, которые могут исправлять ошибки определенной кратности. Соотношение между максимальной кратностью исправляемой ошибки q и кодовым расстоянием d определяется по формуле:

               d ≥ 2q + 1.                                        

В основу исправления ошибок положена следующая идея: определяется множество кодовых комбинаций, включающее все разрешенные и те запрещенные, которые получены при искажении ошибкой кратности не более q. Это множество разбивается на m+1 подмножеств, где m – число исходных кодируемых символов. В каждое из m подмножество входят: разрешенная кодовая комбинация и ближайшие к ней запрещенные, которые отстоят от разрешенной на расстояние не больше q. Еще одно подмножество составляют те кодовые комбинации, которые отстоят от исходной на расстояние больше q.                       

              Тогда при декодировании определяется, в какое подмножество входит принятая кодовая комбинация. Если она является разрешенной, то сразу декодируется; если запрещенная, то исправляется на разрешенную, с которой находится в одном подмножеств, а затем декодируется. Если кодовая комбинация не распознается по одному из приведенных правил, она считается искаженной, по исправить ее нет возможности (корректирующая способность кода недостаточна для этого).

Пример 1. Построить помехозащитный код, исправляющий ошибку кратности 1, для передачи двух символов: a и b.

Построим первичный код. Поскольку для кодирования двух символов достаточно одного двоичного разряда, первичный код может иметь следующий вид:

       a        0,

       b        1.

В силу приведенной выше формулы для расчета кодового расстояния для исправления ошибки  и поскольку по заданию q = 1, имеем d = 3, таким образом, для исправления ошибки кратности 1 кодовое расстояние должно быть равно по меньшей мере 3.

Поскольку в первичном коде обеспечено расстояние между кодовыми комбинациями, равное 1, для выполнения условия d = 3 необходимо, чтобы проверочные разряды обеспечивали расстояние между кодовыми комбинациями, по меньшей мере, равным 2.

Очевидно, для этого число проверочных разрядов должно быть не меньше 2. Тогда разрешенные кодовые комбинации могут иметь вид:

Исходный символ	Информационный разряд	Проверочные разряды	Результирующий код
a	0	00	000
b	1	11	111

Из таблицы видно, что кодовое расстояние равно 3, а построенные кодовые комбинации являются разрешенными.

Определим общее число всевозможных комбинаций, если число разрядов кода равно 3:

разрешенные кодовые комбинации = {000, 111};

запрещенные кодовые комбинации = {001, 010, 011, 100, 101, 110}.

Определим подмножества кодовых комбинаций, которые отстояли бы от каждой разрешенной на минимальное расстояние, равное 1:

для 000                для 111

001                        011

010                        101                                                        

100                        110.

Пусть передается кодовая комбинация 000 (символ a) и на нее накладывается ошибка кратности 1. В таблице показаны полученные кодовые комбинации и их декодирование:

Передаваемая кодовая комбинация	Ошибка	Принимаемая кодовая комбинация	Результат исправления	Результат декодирования
000	100	100	000	a
000	010	010	000	a
000	001	001	000	a

Таким образом, построенный код позволяет исправлять ошибки кратности 1.

Пример 2. Построить помехозащитный код, исправляющий ошибку кратности 1, для передачи символов: a, b и c.

Вначале построим первичный код: a – 00;    b – 01; c – 10.

Для решения поставленной задачи необходимо обеспечить d = 3. Для этого воспользуемся схемой формирования кода Грея:

	00	01	11
000	a
011		b
101			c

Таким образом, построены коды:

a → 00000, b → 01101, c→ 10111.

Полученное кодовое расстояние d = min {d_ab, d_ac, d_bc} = min {3, 4, 3} = 3 обеспечивает исправление ошибки кратности q = 1.

Рассмотрим, как исправляются ошибки в данном случае. Все множество кодовых комбинаций пятиразрядного двоичного кода равно 2⁵ = 32. Из них три кодовые комбинации – разрешенные, остальные – запрещенные. Разобьем кодовые комбинации на три подмножества, в каждое из которых будут входить: одна разрешенная и те запрещенные, которые отстоят от разрешенной на расстояние в 1. Имеем:

для 00000        для 01101        для 10111

00001                01100                10110

00010                01111                10101

00100                01001                10011                                                

01000                00101                11111

10000                11101                00111

Очевидно, общее число кодовых комбинаций, включенных в построенные подмножества, равно 24. Оставшиеся 8 кодовых комбинаций являются следствием ошибки кратности больше 1 и в сформированные подмножества не включены.

Проверим, как выполняется исправление ошибки кратности 1. Пусть передается кодовая комбинация 01101 (символ b) и на нее накладывается ошибка кратности 1. В таблице показаны полученные кодовые комбинации и их декодирование:

Передаваемая кодовая комбинация	Ошибка	Принимаемая кодовая комбинация	Результат исправления	Результат декодирования
01101	10000	11101	01101	b
01101	01000	00101	01101	b
01101	00100	01001	01101	b
01101	00010	01111	01101	b
01101	00001	01100	01101	b

Пусть на ту же кодовую комбинацию накладывается ошибка кратности 2. Результирующие кодовые комбинации либо невозможно декодировать, либо декодирование неверно:

Передаваемая кодовая комбинация	Ошибка	Принимаемая кодовая комбинация	Результат декодирования
01101	10001	11100	Невозможно декодировать
01101	01001	00100	То же
01101	00101	01000	a
01101	00011	01110	Невозможно декодировать
01101	10010	11111	c
01101	01010	00111	Невозможно декодировать
01101	00110	01011	То же
01101	10100	11001	"-"
01101	01100	00001	a
01101	11000	10101	c

В заключение отметим, что для обнаружения ошибки кратности q₁ и исправления ошибки кратности q₂ (q₁ ≥ q₂) минимальное кодовое расстояние должно удовлетворять следующему соотношению: d ≥ q₁ + q₂ + 1.

Измерение информации

В информатике, как правило, измерению подвергается информация, представленная дискретным сигналом. При этом различают следующие подходы:

1. структурный. Измеряет количество информации простым подсчетом  информационных элементов, составляющих сообщение. Применяется для оценки возможностей запоминающих устройств, объемов передаваемых сообщений, инструментов кодирования без учета статистических характеристик их эксплуатации.

1. статистический. Учитывает вероятность появления сообщений: более информативным считается то сообщение, которое менее вероятно, т.е. менее всего ожидалось. Применяется при оценке значимости получаемой информации.

1. семантический. Учитывает целесообразность и полезность информации. Применяется при оценке эффективности получаемой информации и ее соответствия реальности.

Структурный подход к измерению информации

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

• геометрическая. Определяет максимально возможное количество информации в заданных объемах. Мера может быть использована для определения информационной емкости памяти компьютера;

• комбинаторная. Оценивает возможность представления информации при помощи различных комбинаций информационных элементов в заданном объеме. Комбинаторная мера может использоваться для оценки информационных возможностей некоторого системы кодирования;

• аддитивная, или мера Хартли.

Геометрическая мера

Определяет максимально возможное количество информации в заданных объемах. Единица измерения – информационный элемент. Мера может быть использована для определения информационной емкости памяти компьютера. В этом случае в качестве информационного элемента выступает минимальная единица хранения – бит. Список самых распространенных более крупных единиц и соотношение между ними приведено ниже:

8 бит = 1 байт (сокращенно б или Б),

1024 Б = 1 килобайт (сокращенно Кб или К),

1024 К = 1 мегабайт (сокращенно Мб или М),

1024 М = 1 гигабайт (сокращенно Гб или Г).

Тогда, например, объем винчестера – 3 гигабайта; объем основной памяти компьютера – 32 мегабайта и т.д.

Пример 1. Пусть сообщение  

5555 6666 888888

закодировано одним из специальных методов эффективного кодирования – кодирование повторений – и имеет вид:

5(4) 6(4) 8(6)        .        

Требуется измерить информацию в исходном и закодированном сообщениях геометрической мерой и оценить эффективность кодирования.

В качестве информационного элемента зададимся символом сообщения. Тогда:

I^(исх.) = l^(исх.) = 14 символов;

I^{(закод.)} = l^{(закод.)} = 12 символов,

где I^(исх.), I^{(закод.)} – количества информации, соответственно, в исходном и закодированном сообщениях;

l^(исх.), l^{(закод.)} – длины (объемы) тех же сообщений, соответственно.

Эффект кодирования определяется как разница между I^(исх.)  и I^{(закод.)} и составляет 2 символа.

Очевидно, геометрическая мера не учитывает, какими символами заполнено сообщение. Так, одинаковыми по количеству информации, измеренной геометрической мерой, являются, например, сообщения «компьютер» и «программа»; а также 346 и 10В.