yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->ТЕМА 2  ОСНОВЫ ЭКОНОМНОГО КОДИРОВАНИЯ ИНФОРМАЦИИ

Теория информации

ТЕМА 2  ОСНОВЫ ЭКОНОМНОГО КОДИРОВАНИЯ ИНФОРМАЦИИ

 

2.1  Способы задания кодов. Статистическое кодирование

 

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

         Цель сжатия – уменьшение количества битов, необходимых для хранения и передачи информации, что даёт возможность передавать сообщения более быстро и хранить более экономно и оперативно.

         Рассмотрим примеры кодов и способы их представления.

         Любое дискретное сообщение xі из алфавита объемом k можно закодировать последовательностью соответствующим образом выбранных кодовых символов. Например, любое число li можно записать в заданной позиционной системе счисления следующим образом:

 

                                    ,

 

где q – основание системы счисления;

 - коэффициенты при степенях q, .

Например: ,

,

или .

Таким образом, 323 и 111011 можно считать соответственно четверичным и двоичным кодами числа М=59.

         Самым простым способом представления кодов являются кодовые таблицы, ставящие в соответствие кодируемым значениям определенные кодовые комбинации (табл. 2.1).

Таблица 2.1

Буква

xi

Число

Код с основанием 10

Код с основанием 4

Код с основанием 2

А

Б

В

Г

Д

Е

Ж

З

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

00

01

02

03

10

11

12

13

000

001

010

011

100

101

110

111

 

         Нетрудно убедиться в том, что любое сообщение xi  из алфавита объемом k можно закодировать последовательностью кодовых символов из набора размером N=ql комбинаций, где N ³ k, lдлина кодовой комбинации. В общем случае .

         Например: k=32, q=2, тогда l=5, кодовые комбинации:  00000…11111; k=1000, q=10, тогда l=3 – 0…999.

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

         Другим наглядным и удобным способом описания кодов является их представление в виде кодового дерева (рис. 2.1).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 2.1

        

         Для этого, начиная с некоторой точки – «корня» кодового дерева, проводятся ветви, которые помечаются 0 или 1. На «вершинах» («листьях») кодового дерева находятся символы алфавита источника, причем каждому символу соответствует своя вершина и свой путь от корня к вершине.

         Код, полученный с использованием вышеприведенного кодового дерева (рис. 2.1), является примитивным равномерным трехразрядным кодом. Преимущество равномерных кодов, т. е. кодов, состоящих из одинакового для всех кодируемых букв количества символов (бит), заключается в простоте кодирования/декодирования и синхронизации системы (рис 2.2).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 2.2

 

Наряду с равномерными часто используются неравномерные коды. Примером такого кода может служить следующее кодовое дерево (рис 2.3).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 2.3

 

         Однако в этом случае некоторым буквам алфавита будут соответствовать не вершины дерева, а узлы, вследствие чего декодирование становится неоднозначным. Например, приняв 0, невозможно определить - это буква «Д» или начало букв «Е» или «Б». Это пример так называемых непрефиксных или приводимых кодов.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 2.4

 

         Задача приема и декодирования неравномерных кодов значительно более сложная, чем для равномерных кодов, поскольку поступление элементов сообщения (букв) становится непериодическим (рис. 2.5).

 

 

 

 

 

 

 

 

Рисунок 2.5

 

         Тогда возникает вопрос: зачем же используются неравномерные коды?

         Рассмотрим примеры кодирования сообщений xi  из алфавита объемом k=8 с помощью произвольного l-разрядного двоичного кода.

 

Пример 1  Пусть источник выдает одно из восьми сообщений АЗ, имеющих одинаковую вероятность pi=1/8.

        

         Кодирование этих сообщений равномерным трехразрядным двоичным кодом представлено в таблице 2.1.

        

         В этом случае:

-        энтропия источника (бит/сим);

-        избыточность источника ;

-        среднее число символов в коде  (бит/сим);

-        избыточность кода .

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

 

Пример 2 Предположим, что вероятность выпадения сообщений неодинакова (табл. 2.2).

Таблица 2.2

А

Б

В

Г

Д

Е

Ж

З

P=0,6

p=0,2

р=0,1

P=0,04

р=0,025

р=0,015

p=0,01

р=0,01

  

         Энтропия источника  при этом будет меньше: Н(Х)»1,781 (бит/сим).

        

         Среднее число символов на одно сообщение при использовании равномерного трехразрядного кода (бит/сим).

         Тогда избыточность кода , т.е. имеет достаточно большую величину (в среднем 3 символа из 10 не несут никакой информации).

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

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

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

 

 

 

7