Главная arrow Двоичный код arrow Эффективность кодирования
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Эффективность кодирования Печать

Повысить эффективность кодирования можно, строя код не для символа, а для блоков из n символов, причем частота блока рассчитывается как произведение частот символов, входящих в блок. Рассмотрим этот тезис на примере.

Пример 1. Даны символы a и b с частотами, соответственно, 0,9 и 0,1. Построить эффективный код методом Шеннона-Фано для блоков из двух символов (n = 2).

Сформируем список возможных блоков и их частот. При этом частоту блока будем рассчитывать как произведение частот символов, входящих в блок. Тогда имеем:

Блоки исходных        Частоты блоков                

символов

aa                                0,81

ab                                0,09

ba                                0,09

bb                                0,01

Построение кода сведем в таблицу:

Блоки исходных символов

Частоты блоков

Этапы построения кода

первый

второй

третий

aa

0,81

1

код построен

ab

0,09

0

1

код построен

ba

0,09

0

0

1

bb

0,01

0

0

0

Таким образом, получены коды:

aa                -        1;                

ab                -        01;                

ba                -        001;                        

bb                -        000.

Определим эффективность построенного кода. Для этого рассчитаем сначала показатель эффективности для блока символов:

lср блока = 0,81*1 + 0,09*2 + 0,09*3 + 0,01*3 = 1,28.

Поскольку в блоке 2 символа (n=2), для одного символа lср = lср блока/2 = 1,28/2 = 0,64.

При посимвольном кодировании для эффективного кода потребуется по одному двоичному разряду. В самом деле, применение метода Шеннона-Фано дает результат, представленный в таблице:

Исходные символы

Частоты символов

Построение кода

a

0,9

1

b

0,1

0

Таким образом, при блочном кодировании выигрыш составил 1 - 0,64 = 0,36 двоичных разрядов на один кодируемый символ в среднем.

Эффективность блочного кодирования тем выше, чем больше символов включается в блок.