3.Сжатие на базе экономного кода.

Двоичного кодирования достаточно для кодирования любой информации и двоичное представление в памяти не вызывает удивления, хотя хранит любую мыслимую информацию и в разных структурах. При этом единица кодированной информации имеет, как правило, фиксированную длину, что не всегда оправдано и выгодно. Для кодирования букв русского языка было бы достаточно 5 разрядов (объединив е и ё). Но мы используем 8 разрядов

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

К1 – команда вперед

К2 – команда влево

К3 – команда вправо

К4 – команда назад.

Для кодирования 4 команд требуется 2 разряда и может показаться, что это вполне оптимально.

Закодируем каждую из них, на что потребуется два двоичных кода:

К1	К2	К3	К4
00	01	10	11
50%	25%	12,5%	12,5%
500	250	125	125

Таблица 3.1

В процессе передачи выяснилось, что половина команд, т.е. 50 - это команды вперед, следующая по частоте команда назад, а остальные команда налево и направо примерно поровну составляют оставшуюся часть, около 25%. Тогда была поставлена задача, перепрограммировать робот и подавать команды управления в экономном режиме.

Рассуждение ведется следующим образом: Разобьем все сообщения на две группы с учетом частоты передаваемых команд, так чтобы число сообщений передаваемых по командам на 1000 было примерно поровну, то есть: 1 - (К1) - 500 и 2 - (К2, К3, К4) - 500, первой присвоим 0, второй – 1.(таблица 3.2). Точно также рассуждаем для второй итерации: 1 - (К2) 250 и 2 - (К3, К4) 250, первой присвоим 0, второй -1. И наконец, для третьей итерации: 1 - (К3) - 125 и 2 - (К4) - 125, первой присвоим 0, второй -1. Результаты такого разбиения хорошо видны в таблице 3.2

К1	50%	0
К2	25%	1	0
К3	12,5%		1		0
К4	12,5%				1

Таблица 3.2

В результате получим неравномерный код команд и вместо таблицы 3.1, таблицу 3.3, где в строке 2 указаны соответствующие коды..

К1	К2	К3	К4
0	10	110	111
50%	25%	12,5%	12,5%
500	250	125	125

Таблица 3.3

Теперь очевидно, что для передачи в первом варианте при наличии 2 разрядов для каждой команды потребуется 2000 бит. А для второго варианта потребуется 500*1= 500 бит для первой команды, 250*2= 500 бит для второй команды и (125+125)*3= 750 бит для 3 и 4 команд. Таким образом, это составит 1750 вместо 2000 бит информации.

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

Если £ _сред – средняя длина кодового сообщения ( набора команд ),

а l_i - длина кода единичного сообщения (команды), P(k_i) – вероятность появления сообщения (команды) длины l_i , а N – общее число сообщений(команд), то формула, определяющая среднюю длину одного сообщения( команды), будет выглядеть следующим образом:

_N

£ _сред = ∑ l_i P(k_i).

^{i =1}

Наиболее экономным будет код, средняя длина которого будет минимальной. Для данного примера

£ _сред = 1*0,5 + 2*0,25+3*2*0,125 = 1,75

Очевидно, что для равномерного кода £ _сред = 2,00.

Рассмотренный выше способ формирования кода был предложен американским математиком Фано.

Общий алгоритм получения кода Фано будет состоять в следующем.

Расположим вероятности появления сообщений в порядке их убывания. Далее разбиваем их на две группы по приблизительному равенству суммы вероятностей, не меняя их последовательности. В первой группе, как правило, будет оказываться меньшее число, по отношению ко второй группе. Первой группе относительно данного разбиения присваиваем – 0, а второй группе присваиваем – 1. Группы первую и вторую разбиваем на две части до тех пор, пока в группе не останется только одна вероятность. Для нее процесс получения кода закончен. Далее такие действия предпринимаем для оставшихся групп, пока дальнейшее разбиение будет невозможным. Лучше всего такое разбиение оформлять в виде таблицы подобной таблице 3.2. Тогда код для соответствующего сообщения (команды) будет складываться из значений находящихся в колонках слева направо, до завершения их появления.

Общий алгоритм для k- значного кода ……