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

Разрешенными кодовыми комбинациями называются те, которые соответствуют символам исходного алфавита. Их количество равно числу исходных символов (m). Запрещенные кодовые комбинации – это те, которые отсутствуют в исходной кодовой таблице. Их количество определяется по формуле: 2^r – m, где r – общее число двоичных разрядов (информационные плюс проверочные) в коде.

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

d  2q + 1.

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

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

В заключение отметим, что для обнаружения ошибки кратности q₁ и исправления ошибки кратности q₂ при q₁q₂ минимальное кодовое расстояние должно удовлетворять следующему соотношению:

d  q₁ + q₂ + 1.

13. Измерение дискретного сигнала

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

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

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

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

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

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

1. геометрическая;

2. комбинаторная;

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

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

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

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

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

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

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

Геометрическая мера не учитывает, какими символами заполнено сообщение.