Основы кодирования

Проблемы кодирования и сжатия данных

Проблемы хранения информации.

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

Кодирование — представление сообщения (информации) последовательностью элементарных символов.

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

Количество информации в сообщении (элементе сообщения) определяется по формуле

I = — log2 P,

где Р — вероятность появления сообщения (элемента сообщения).

При равновероятном появлении 1 и 0, один бит равен единице количества информации.

Информационная энтропия характеризует степень неопределенности передаваемой информации.

Информационная энтропия источника информации с N независимыми сообщениями есть среднее арифметическое количеств информации сообщений

H = —1* P_k log₂ P_k

где Pk — вероятность появления k-го сообщения. Другими словами, энтропия есть мера неопределенности ожидаемой информации.

Пример. Источник передает двоичный код с равновероятным появлением в нем a b c d, значит H = -(4*(0.25*-2) = 2.

Теоремы Шеннона

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

Для рассмотренного выше примера оптимально кодировать каждую букву 2битами.

Вторая теорема Шеннона относится к условиям надежной передачи информации по ненадежным каналам. И ее рассмотрение относится скорее к разделу передача данных.

Двоичные кодировки:

ASCII (American Standards Committee for Information Interchange) — семибитовый двоичный код.

Для кодировки русского текста нужно вводить дополнительные битовые комбинации. Семибитовая кодировка здесь уже недостаточна. Так возникли кодировка КОИ-8, затем Windows 1251. Множество используемых кодировок существенно усложняет проблему согласования почтовых программ в глобальных сетях.

Коэффициент избыточности сообщения А определяется по формуле

r = (Imax — I)/Imax,

где I — количество информации в сообщении А, Imax — максимально возможное количество информации в сообщении той же длины, что и А.

Наличие избыточности позволяет ставить вопрос о сжатии информации без ее потери в передаваемых сообщениях.

Эффект сжатия оценивают коэффициентом сжатия:

где n — число минимально необходимых символов для передачи сообщения; q — число символов в сообщении, сжатом данным алгоритмом.

Часто степень сжатия оценивают отношением длин кодов на входе и выходе алгоритма сжатия.

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

Устройства или программы, применяемые для компрессии и декомпрессии, называют кодеками(кодирование-декодирование).