Рассмотрим идеализированный случай, когда источник дискретных сообщений с мощностью алфавита К и избыточностью х подключен к каналу без помех. При этом естественно возникает вопрос, связанный с поиском такого способа кодирования состояний источника, при котором в целях передачи по каналу максимально возможного количества информации в единицу времени избыточность источника была бы сокращена.
Поскольку избыточность источника является следствием неравновероятности состояний и их взаимной зависимости, для наиболее эффективного использования канала необходимо стремиться к тому, чтобы в последовательности кодовых слов на выходе кодирующего устройства по возможности отсутствовала бы их взаимная зависимость и неравновероятность. Процесс сокращения избыточности источника получил название эффективного кодирования сообщений, а коды, обеспечивающие решение этой задачи, называют статистическими кодами. Универсальным способом уменьшения избыточности источника, обусловленной взаимной зависимостью состояний источника, является укрупнение, смысл которого заключается в кодировании не каждого состояния, а последовательности состояний определенной длительности. Длительность кодируемых блоков определяется степенью их взаимной зависимости. Как правило, зависимость блоков с увеличением их длительности уменьшается.
Так, например, при кодировании текста, где элементарными сообщениями являются буквы, в целях сокращения избыточности текста, порожденной взаимной зависимостью букв, можно кодировать не отдельные буквы, а целые слова. Можно показать, что при таком кодировании текстов русской художественной прозы удается достигнуть сокращения избыточности до значения 2 двоичных символов на букву.
|
Далее сформулируем предельные возможности статистических кодов.
Рассмотрим вначале последовательность Вп = (b(1),...,b(n)) следующих друг за другом п элементов дискретного источника {В,р(b)}. Каждый элемент выбирается из алфавита {bi,...,bк}, и, таким образом, имеются Кп последовательностей различной длины п, которые могут появляться на выходе источника. Поставим задачу кодирования этих последовательностей в слова кода с фиксированной длиной. Если кодовый алфавит состоит из m символов и если длина каждого кодового слова равна l, то существуют ml различных кодовых слов. Следовательно, если нужно сопоставить различные кодовые слова разным последовательностям источника (если необходимо взаимно однозначное отображение), то получаем . Таким образом, для кодов с фиксированной длиной при декодировании необходимо иметь по меньшей мере log К/ log M кодовых символов на одну букву источника.
Если мы хотим в целях эффективного кодирования использовать меньше, чем log К/ log M символов на одну букву источника, то, очевидно, нужно ослабить требование того, чтобы всегда была возможность полного однозначного соответствия.
В подтверждение сказанному рассмотрим пример [1]. Предположим, что на телеграфе введена автоматическая обработка телеграмм,
записанных в алфавите объемом 64 буквы (количество букв, содержащееся в двух регистрах телетайпа). Пусть эффективность обработки информации определяется количеством телеграмм, которые можно ввести в запоминающее устройство (ЗУ). Объем ЗУ равен N двоичным ячейкам. Необходимо закодировать телеграммы двоичным кодом.
|
Рассмотрим вначале побуквенное кодирование. В этом случае используется код, содержащий 26 = 64 кодовых слова, и каждой букве телеграммы сопоставляется некоторое кодовое слово. Пусть используется равномерный код со словами в 6 двоичных символов. При этом в ЗУ можно поместить N/6 букв. Если считать, что средняя длина телеграммы — 20 слов, а средняя длина слова 8 букв, то в ЗУ можно поместить примерно N/960 телеграмм.
Второй способ кодирования состоит в том, что выделяется специальный словарь, например, из 213 = 8192 слов (достаточно практически для любой телеграммы). Каждое слово может быть закодировано с помощью двоичной последовательности длиной 13 символов. В этом случае в ЗУ можно записать N /260 телеграмм, т.е. в 3-4 раза больше, чем в первом случае. (При кодировании и декодировании можно считать слово, отсутствующее в словаре, «ошибкой».)
Таким образом, второй способ является значительно более эффективным с точки зрения сложности ЗУ. Эта эффективность является следствием устранения избыточности, хотя при кодировании по второму способу возможны ошибки, поскольку существует опасность появления слова, не входящего в кодовый словарь. При побуквенном кодировании обеспечивается безошибочное декодирование.
Из этого примера видно, что для сокращения избыточности мы должны приписывать кодовые слова только некоторому подмножеству последовательностей источника длины п.
Постановка задачи равномерного кодирования источника. Пусть А = { а1,..., ат } — алфавит кода источника — некоторое множество, состоящее из m элементов; аi — кодовые символы. Последовательность кодовых символов задает кодовое слово, любое семейство кодовых слов — это код над алфавитом А. (Примеры: множество букв русского алфавита, множество цифр и т.д.) Код называется равномерным, если все его слова имеют одинаковую длину l, называемую длиной (значностью) кода. В противном случае код называется неравномерным. Количество различных слов равномерного кода длины l не превосходит т1 —числа различных m -ичных последовательностей длины l.
|
Определение. Кодированием сообщений ансамбля В посредством кода А называется отображение множества сообщений Вп в множество кодовых слов.
Предлагается следующий способ равномерного кодирования [1]: множество всех последовательностей сообщений источника длиной п делится на два подмножества, одно из которых создается всеми последовательностями — блоками длины п, однозначно отображаемыми кодовыми словами. Это подмножество называется множеством однозначно кодируемых и декодируемых блоков. Остальные блоки образуют второе подмножество, которому соответствует одно единственное кодовое слово. Длина l всех кодовых слов одинакова; она определяется числом М кодовых слов: l — наименьшее целое, удовлетворяющее неравенству ml ≥ М. Процесс кодирования и декодирования заключается в разбиении последовательности сообщений на выходе источника на блоки длиной п и сопоставлении каждому блоку соответствующего кодового слова длины l. Ошибкой процедуры декодирования при этом является событие, состоящее в появлении неоднозначно кодируемого блока. Количество m -ичных кодовых символов, приходящихся на одно сообщение, определяется соотношением l/n ≥ log M/ log m. Число log M/n = R для заданных значений М и п называется скоростью равномерного кодирования источника. Скорость R измеряется в двоичных символах на сообщение. Таким образом, существо равномерного кодирования заключается в выборе множества однозначно кодируемых n -последовательностей сообщений.
Основная задача при кодировании равномерными кодами заключается в определении наименьшей возможной скорости кодирования, при которой вероятность ошибочного декодирования может быть сделана сколь угодно малой. Наименьшая достижимая скорость R является характеристикой кодируемого источника. Она носит название скорости создания информации.
Величина H может рассматриваться как скорость.создания информации, если может быть доказано следующее важное утверждение:
Для любого R > Н и произвольного положительного δ найдется значение п и код со скоростью R, для которого вероятность ошибки не превосходит δ. (Прямая теорема кодирования источника.)