Теория информации (стр. 12 из 29)
При построении неравномерных кодов необходимо обеспечить возможность их однозначной расшифровки. В равномерных кодах такая проблема не возникает, т.к. при расшифровке достаточно кодовую последовательность разделить на группы, каждая из которых состоит из q элементов. В неравномерных кодах можно использовать разделительный символ между буквами алфавита (так поступают, например, при передаче сообщений с помощью азбуки Морзе).
Если же отказаться от разделительных символов, то следует запретить такие кодовые комбинации, начальные части которых уже использованы в качестве самостоятельной комбинации. Например, если 101 означает код какой-то буквы, то нельзя использовать комбинации 1, 10 или 10101.
Практические методы оптимального кодирования просты и основаны на очевидных соображениях ( метод Шеннона – Фано ).
Прежде всего, буквы (или любые сообщения, подлежащие кодированию) исходного алфавита записывают в порядке убывающей вероятности. Упорядоченное таким образом множество букв разбивают так, чтобы суммарные вероятности этих подмножеств были примерно равны. Всем знакам (буквам) верхней половины в качестве первого символа присваивают кодовый элемент 1, а всем нижним 0. Затем каждое подмножество снова разбивается на два подмножества с соблюдением того же условия равенства вероятностей и с тем же условием присваивания кодовых элементов в качестве второго символа. Такое разбиение продолжается до тех пор, пока в подмножестве не окажется только по одной букве кодируемого алфавита. При каждом разбиении буквам верхнего подмножества присваивается кодовый элемент 1, а буквам нижнего подмножества - 0.
Пример16: Провести эффективное кодирование ансамбля из восьми знаков:
Таблица 3.1.
| Буква (знак) xi | Вероят-ность Рi | Кодовые последовательности | Длина qi | рi qi | -рilog рi | ||||
| Номер разбиения | |||||||||
| 1 | 2 | 3 | 4 | ||||||
| x1 | 0,25 | 1 | 1 | 2 | 0,5 | 0,50 | |||
| x2 | 0,25 | 1 | 0 | 2 | 0,5 | 0,50 | |||
| x3 | 0,15 | 0 | 1 | 1 | 3 | 0,45 | 0,41 | ||
| x4 | 0,15 | 0 | 1 | 0 | 3 | 0,45 | 0,41 | ||
| x5 | 0,05 | 0 | 0 | 1 | 1 | 4 | 0,2 | 0,22 | |
| x6 | 0,05 | 0 | 0 | 1 | 0 | 4 | 0,2 | 0,22 | |
| x7 | 0,05 | 0 | 0 | 0 | 1 | 4 | 0,2 | 0,22 | |
| x8 | 0,05 | 0 | 0 | 0 | 0 | 4 | 0,2 | 0,22 | |
= 2,7 
Как видно, qср = H, следовательно, полученный код является оптимальным.
Пример17: Построить код Шеннона - Фано, если известны вероятности: Р(x1) = 0,5; P(x2)= 0,25; P(x3) = 0,125; P(x4) = 0,125
Пример18: Провести эффективное кодирование ансамбля из восьми знаков (m=8), используя метод Шеннона - Фано.
Решение: При обычном (не учитывающем статистических характеристик) двоичном кодировании с использованием k=2 знаков при построении равномерного кода количество элементов в кодовой последовательности будет q ³ logk m = log2 8 = 3, т.е. для представления каждого знака использованного алфавита потребуется три двоичных символа.
Метод Шеннона - Фано позволяет построить кодовые комбинации, в которых знаки исходного ансамбля, имеющие наибольшую вероятность, кодируются наиболее короткими кодовыми последовательностями. Таким образом, устраняется избыточность обычного двоичного кодирования, информационные возможности которого используются не полностью.
Таблица 3.2.
| Знаки (буквы) xi | Вероятность Pi | Кодовые комбинации | |||||||
| номер разбиения | |||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |||
| x1 | 1/2 | 1 | |||||||
| x2 | 1/4 | 0 | 1 | ||||||
| x3 | 1/8 | 0 | 0 | 1 | |||||
| x4 | 1/16 | 0 | 0 | 0 | 1 | ||||
| x5 | 1/32 | 0 | 0 | 0 | 0 | 1 | |||
| x6 | 1/64 | 0 | 0 | 0 | 0 | 0 | 1 | ||
| x7 | 1/128 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |
| x8 | 1/128 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
Так как вероятности знаков представляют собой отрицательные целочисленные степени двойки, то избыточность при кодировании устранена полностью.
Среднее число символов на знак в этом случае точно равно энтропии. В общем случае для алфавита из восьми знаков среднее число символов на знак будет меньше трех, но больше энтропии алфавита. Вычислим энтропию алфавита:
Вычислим среднее число символов на знак:
где q(xi) - число символов в кодовой комбинации, соответствующей знаку xi.
Пример19: Определить среднюю длину кодовой комбинации при эффективном кодировании по методу Шеннона - Фано ансамбля - из восьми знаков и энтропию алфавита.
Таблица 3.3.
| Знаки(буквы) xi | ВероятностьPi | Кодовые комбинации | ||||
| номер разбиения | ||||||
| 1 | 2 | 3 | 4 | 5 | ||
| x1 | 0,22 | 1 | 1 | |||
| x2 | 0,20 | 1 | 0 | 1 | ||
| x3 | 0,16 | 1 | 0 | 0 | ||
| x4 | 0,16 | 0 | 1 | |||
| x5 | 0,10 | 0 | 0 | 1 | ||
| x6 | 0,10 | 0 | 0 | 0 | 1 | |
| x7 | 0,04 | 0 | 0 | 0 | 0 | 1 |
| x8 | 0,02 | 0 | 0 | 0 | 0 | 0 |
Решение: 1. Средняя длина кодовых комбинаций
2. Энтропия алфавита
При кодировании по методу Шеннона - Фано некоторая избыточность в последовательностях символов, как правило, остается (qср > H).
Эту избыточность можно устранить, если перейти к кодированию достаточно большими блоками.
Пример20: Рассмотрим процедуру эффективного кодирования по методике Шеннона - Фано сообщений, образованных с помощью алфавита, состоящего всего из двух знаков x1 и x2 с вероятностями появления соответственно Р(х1) = 0,9; P(x2) = 0,1.
Так как вероятности не равны, то последовательность из таких букв будет обладать избыточностью. Однако, при побуквенном кодировании мы никакого эффекта не получим. Действительно, на передачу каждой буквы требуется символ либо 1, либо 0, в то время как энтропия равна
,т.е. оказывается 
При кодировании блоков, содержащих по две буквы, получим коды:
Таблица 3.4.
| Блоки | Вероятности | Кодовые комбинации | ||
| номер разбиения | ||||
| 1 | 2 | 3 | ||
| x1x1 | 0,81 | 1 | ||
| x1x2 | 0,09 | 0 | 1 | |
| x2x1 | 0,09 | 0 | 0 | 1 |
| x2x2 | 0,01 | 0 | 0 | 0 |
Так как знаки статистически не связаны, вероятности блоков определяют как произведение вероятностей составляющих знаков.
Среднее число символов на блок
а на букву 1,29/2 = 0,645, т.е. приблизилось к Н = 0,47 и таким образом удалось повысить эффективность кодирования.
Кодирование блоков, содержащих по три знака, дает еще больший эффект:
Таблица 3.5.
| Блоки | ВероятностьPi | кодовые комбинации | ||||
| номер разбиения | ||||||
| 1 | 2 | 3 | 4 | 5 | ||
| x1x1x1 | 0,729 | 1 | ||||
| x2x1x1 | 0,081 | 0 | 1 | 1 | ||
| x1x2x1 | 0,081 | 0 | 1 | 0 | ||
| x1x1x2 | 0,081 | 0 | 0 | 1 | ||
| x2x2x1 | 0,009 | 0 | 0 | 1 | 1 | |
| x2x1x2 | 0,009 | 0 | 0 | 0 | 1 | 0 |
| x1x2x2 | 0,009 | 0 | 0 | 0 | 0 | 1 |
| x2x2x2 | 0,001 | 0 | 0 | 0 | 0 | 0 |
Среднее число символов на блок равно 1,59, а на знак - 0,53, что всего на 12% больше энтропии.
Следует подчеркнуть, что увеличение эффективности кодирования при укрупнении блоков не связано с учетом все более далеких статистических связей, т.к. нами рассматривались алфавиты с независимыми знаками.
Повышение эффективности определяется лишь тем, что набор вероятностей получившихся при укрупнении блоков можно делить на более близкие по суммарным вероятностям подгруппы.
Рассмотренная методика Шеннона - Фано не всегда приводит к однозначному построению кода, т.к. при разбиении на подгруппы можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппы:
Таблица 3.6.
| Знаки (буквы)xi | ВероятностьPi | 1-е кодовые комбинации | 2-е кодовые комбинации | ||||||||
| номер разбиения | номер разбиения | ||||||||||
| 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5 | ||
| x1 | 0,22 | 1 | 1 | 1 | 1 | ||||||
| x2 | 0,20 | 1 | 0 | 1 | 1 | 0 | |||||
| x3 | 0,16 | 1 | 0 | 0 | 0 | 1 | 1 | ||||
| x4 | 0,16 | 0 | 1 | 0 | 1 | 0 | |||||
| x5 | 0,10 | 0 | 0 | 1 | 0 | 0 | 1 | ||||
| x6 | 0,10 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | ||
| x7 | 0,04 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| x8 | 0,02 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
От указанного недостатка свободен метод Хаффмона.