Как уже говорилось, неравномерные кода удобнее использовать при кодировании сообщений, имеющих разную частоту появления. Частота появления какого-нибудь события E обычно оценивается вероятностью этого события, которое обозначается P(E). Иногда вероятность появления события мы так и будем называть частотой этого события.
Пусть передача некоторых сообщений состоит всего из четырех типов сообщений, но каждый тип сообщения имеет свою частоту появления. Пусть множеством этих типов сообщений будет множество S = {s1,s2,s3,s4} с вероятностями их появления: P(s1)=1/2, P(s2)=1/4, P(s3)=P(s4)=1/8 . Это означает, что из 1000 переданных сообщений около 500 раз появляется сообщение s1, около 250 – сообщение s2 , и примерно по 125 раз – каждое из сообщений s3 иs4 . Эти сообщения можно закодировать двоичными словами длины 2, как показано в таблице 1.
Таблица 1.
s1
s2
s3
s4
Но это равномерный код и он никак не учитывает вероятность появления событий.
Роберт Фано предложил следующий способ кодирования таких неравновероятных сообщений. Разобьем сообщения на две равновероятные группы: в одну группу попадает сообщение s1 , а в другую группу - сообщения s2, s3 и s4 . Сопоставим первой группе символ 0, а второй группе – 1 (см. таблицу 2, во втором столбце указаны вероятности событий).
Таблица 2.
s1
1/2
s2
1/4
s3
1/8
s4
1/8
Далее вторую группу разобьем на две равновероятные подгруппы: в одну подгруппу попадает сообщение s2 , а в другую подгруппу – сообщенияs3 и s4 . Аналогично, первой подгруппе сопоставим символ 0, а второй подгруппе – 1. И наконец, вторую подгруппу разобьем на две равновероятные части, состоящие из сообщений: s3 и s4 , и аналогично, сопоставим s3 символ 0, а s4 – 1. В итоге получается следующая кодовая таблица:
Таблица 3.
s1
s2
s3
s4
Как видим, этот код удовлетворяет условию Фано, то есть является префиксным.
Оценим, на сколько этот код экономнее равномерного кода (Таблица 1). Пусть нужно передать 1000 сообщений. При равномерном коде каждое сообщение передается двумя символами, следовательно, будет передано 2000символов. А теперь подсчитаем, сколько символов будет передано при кодировании кодом Фано (таблица 2). Сообщение s1 будет передано примерно 500 раз и на это уйдет 500 символов. Сообщение s2 встретится около 250 раз, но оно передается двумя символами, поэтому на него уйдет тоже 500 символов. А каждое из сообщений : s3 и s4встретится по 125 раз, но они передаются по три символа, поэтому на них уйдет (125+125) · 3 = 750 символов. Получается, что всего будет передано
500+250·2+125·3+125·3=500+500+750=1750 символов. Это меньше, чем для равномерного кода на 250 символов.
В итоге мы экономим одну восьмую часть времени, которое требуется при передаче сообщений. Но мы рассмотрели упрощенный пример. В реальных случаях применение кода Фано дает значительную экономию.
Обычно экономию неравномерного кода оценивают средней длиной кодового слова. Так в нашем примере средняя длина кодового слова L=1750/1000=1.75, то есть это отношение длины кодовой последовательности к числу кодовых слов в этой последовательности. Если известны вероятности появления кодовых слов, то вычислить среднюю длину кодового слова можно по формуле:
n
L=∑ Li·Pi , где Li- длина i-го кодового слова, а Pi- его вероятность, n– число
i=1
кодовых слов.
Более точно, пусть S = {s1,s2, …, sn} - некоторое множество возможных сообщений, а
A={A1, A2, … An} -код такой, чтоAi = F(si), где F- функция кодирования. Тогда в указанной формуле Pi=P(si)=P(Ai)– вероятности сообщений, а следовательно, и появлений кодовых слов, а Li- число символов в кодовом слове Ai.
Вычислим по этой формуле среднюю длину кодового слова для кода из последнего примера (таблицы 2 и 3): L=1·1/2+2·1/4+3·1/8+3·1/8=1/2+1/2+3/4=1.75 , то есть мы получили тот же результат, что и раньше.
Для заданного кода A средняя длина кодового слова Lназывается ценой (или стоимостью) кода A. Цена кода определяет его экономичность. Так цена кода из таблицы 1 равна 2, а цена кода из таблицы 3 равна 1.75.
Другая оценка экономичности кода определяется избыточностью, вычисляемой по формуле:
I
δ=1─ ─, гдеI- среднее количество информации сообщений (кода):
L
N 1
I=∑ Pi·log2──(формула Шеннона).
i=1 Pi
Для последнего примера (таблица 2): I=1/2·1+1/4·2+1/8·3+1/8·3=1.75и δ=0, то есть избыточность нулевая, что означает, что экономнее код быть не может. А если мы рассмотрим равномерный код (таблица 1), но с теми же вероятностями,
то δ=1-1.75/2=0.125, то есть избыточность ненулевая, что означает, что код имеет избыточность, то есть не является самым экономным.
Теперь рассмотрим общий метод построения кода методом Фано.
Располагаем сообщения в порядке убывания вероятностей их появления:
P(s1)≥ P(s2)≥ . . . ≥ P(sN). Далее разбиваем множество сообщений на две группы так, чтобы суммарные вероятности сообщений каждой из групп были как можно более близки друг к другу. Сообщениям одной группы в качестве первого символа кодового слова приписывается символ 0, а сообщениям из другой – символ 1. По тому же принципу каждая из полученных групп снова разбивается на две части, и это разбиение определяет значение второго символа кодового слова. Процедура продолжается до тех пор, пока все множество не будет разбито на отдельные сообщения. В результате каждому из сообщений будет сопоставлено кодовое слово из нулей и единиц.
Ясно, что чем более вероятно сообщение тем быстрее оно образует «самостоятельную» группу и тем более коротким словом оно будет закодировано. Это обстоятельство и обеспечивает высокую экономность кода Фано.
Описанный метод кодирования можно применить и в случае произвольного алфавита для кодовых слов из М символов с той лишь разницей, что на каждом шаге следует производить разбиение на М приблизительно равновероятных групп.
Рассмотрим построение кода Фано на примере алфавитного кодирования. Пусть нужно кодировать сообщения, в которых встречаются только буквы алфавита {a, b, c, d, e, f, g}с частотами (вероятностями появления), заданными следующей таблицей:
Буква
Частота
a
0.12
b
0.27
c
0.06
d
0.10
e
0.11
f
0.30
g
0.04
Сначала, нужно отсортировать таблицу по убыванию частот. Получаем:
Буква
Частота
f
0.30
b
0.27
a
0.12
e
0.11
d
0.10
c
0.06
g
0.04
На первом шаге, делим таблицу на две части, так чтобы суммы частот в обоих частях были как можно более одинаковыми. В данном случае делаем это так:f-b (суммарная частота 0.57), a-g (суммарная частота 0.43). Далее верхней части приписываем 0, нижней 1.
Получится:
Буква
Частота
Код
f
0.30
b
0.27
a
0.12
e
0.11
d
0.10
c
0.06
g
0.04
Далее, каждую из полученных половинок делим на две по такому же принципу. И аналогично распределяем нули и единицы.
Буква
Частота
Код
f
0.30
b
0.27
a
0.12
e
0.11
d
0.10
c
0.06
g
0.04
И далее поступаем аналогично. В результате получим
Буква
Частота
Код
f
0.30
b
0.27
a
0.12
e
0.11
d
0.10
c
0.06
g
0.04
В итоге получаем следующую функцию кодирования: {a→100, b→01, c→1110, d→110, e→101, f→00, g→1111 }
Задача 2. Вычислить цену полученного кода и его избыточность.
