Теория информации и кодирование как научное направление (стр. 2 )

В качестве примера равномерного кода можно назвать ASCII-таблицу, где каждому из 256 символов сопоставлено двоичное значение от 00000000 до 11111111. Независимо от вероятности появления символа на его представление отводится 1 байт, или 8 бит. Как известно, национальные языки обладают большой избыточностью, то есть разницей между энтропией источника и максимально возможной энтропией, обусловленной равной вероятностью появления любого символа из алфавита. Например, избыточность русского языка составляет 70%, а английского – 50%. Это в частности означает, что некоторые буквы появляются в тексте гораздо чаще других и поэтому использовать равномерное кодирование нерационально.

При неравномерном кодировании часто встречающимся символам сопоставляются более короткие кодовые последовательности, редко встречающимся – более длинные. За счет этого удается значительно сократить объем файла без потерь информации. Существует несколько методов неравномерного кодирования, важнейших из которых является метод Шеннона-Фано.

9. Количество и объем информации  при передаче информации в равномерном коде

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

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

Здесь предполагается, что текст — это последовательная цепочка пронумерованных символов. В формуле (1) i1 обозначает информационный вес первого символа текста, i2 — информационный вес второго символа текста и т. д.; K — размер текста, т. е. полное число символов в тексте.

Все множество различных символов, используемых для записи текстов, называетсяалфавитом. Размер алфавита — целое число, которое называется мощностью алфавита. Следует иметь в виду, что в алфавит входят не только буквы определенного языка, но все другие символы, которые могут использоваться в тексте: цифры, знаки препинания, различные скобки, пробел и пр.

10. Простые коды и методы их построения. Избыточность кодов.

11. Равномерные коды. Понятие разрядности кода и ее расчет.

Равномерные простые коды

Как следует из определения, простые равномерные коды сос­тоят из комбинаций одинаковой длины. Естественно, возникает вопрос:

Хорошо это или плохо?" Для ответа на этот вопрос рас­смотрим следующий пример.

Пусть имеется некоторое сообщение, состоящее из М эле­ментов, представляющее собой некоторую последовательность m(m<<M) знаков (например, книга имеет M =100000 элемен­тов, представляющая собой некоторую последовательность из 32 букв, 10 цифр и 11 знаков препинания, т. е. из m = 53 знаков). Как известно, это сообщение несет некоторое количество инфор­мации I, равное:

I=log2N

где N - число возможных вариантов последовательностей из M элементов.

Поскольку последовательность из M элементов составлена знаками, каждый из которых ( xi) появляется в последо­вательности с различными вероятностями рi, то, используя формулу Стерлинга, можно показать, что количество информации в этой последовательности будет:

На один элемент сообщения будет приходиться в среднем количество информации:

Если каждый знак сообщения кодируется n - элементной кодовой комбинацией, состояний из двоичных символов, то каждый из них будет содержать Нэ количества информации

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

Из теории информации известно, что один двоичный элемент может содержать максимальное количество информации равное 1-му биту, т. е. всегда Нэ <= I.

Следовательно, величина

может служить мерой, информационной недогрузки каждого двоич­ного элемента.

Если число знаков, из которых состоит сообщение, m=2n и все знаки равновероятны pi=1/m, то величина R = 0 Действительно.

Таким образом, максимальная скорость передачи равномерно­го простого кода будет тогда и только тогда, когда выполняются условия

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

Кроме того, за счет простых способов определения на при­емной стороне начала и конца каждой кодовой комбинации, что является необходимым условием однозначного декодирования, по­мехоустойчивость равномерных кодов достаточно высокая. Важным фактором является также то, что простые равномерные коды лег­ко преобразуются в корректирующие коды для повышения достовер­ности информации. Все это привело к тому, что равномерные ко­ды получили широкое применение на практике.

Для расширения возможностей равномерных кодов используют следующие меры. Например, число русских букв, цифр и знаков препинания составляет 53, что требует применения 6-элементных кодовых комбинаций (). Поэтому все множество знаков разбивается на два множества (регистра): буквенный и цифровой, что позволяет использовать 5-элементные кодовые комбинации. Для правильного декодирования вводятся специальные комбинации, указывающие о переходе с одного регистра на другой.

Современные отечественные телеграфные аппараты имеют три регистра: русский, латинский и цифровой.

Увеличение алфавита может быть достигнуто за счет того, что кодируются не только отдельные буквы (цифры), а и целые слова и даже отдельные фразы. Естественно - это вызывает не­обходимость увеличения числа регистров при использовании того же 5-элементного равномерного кода.

12. Неравномерное кодирование дискретных источников.

Неравномерные коды

Как отмечалось выше, неравномерными кодами называют такие коды, которые содержат разное число элементов.

Эти коды, как и равномерные коды, с точки зрения скорости передачи информации могут оцениваться величиной информационной недогрузки каждого двоичного символа:

где - средняя длина кодовой комбинации;

- длина комбинации, соответствующей i-му сим­волу сообщения;

- вероятность появления i-го символа в сообщении.

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

Такие коды называют оптимальными. Если символы сообщения резко неравновероятны, то, целая код оптимальным, иногда мож­но увеличить скорость по сравнению с равномерным кодом.

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

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

11, 10, 011, 001, 000, 00001, 000001

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

Например, последовательность

- 1011100000110000101111101000111 -
однозначно разбивается на комбинации

10, 11, 10, 00001, 10, 0001, 011, 11, 10, 10, 001, 11

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

13. Основные характеристики неравномерного кода. Условие Фано.

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