Код Хаффмана. Для двоичного кода методика сводится к следующему

Для двоичного кода методика сводится к следующему. Буквы алфавита сообщений вписываются в основной столбец в порядке убывания вероятностей. Две последние буквы объединяют в одну вспомогательную букву, которой приписывают суммарную вероятность. Вероятности букв не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительный столбец, а две последние объединяются. Процесс продолжается до тех пор, пока не получим единственную вспомогательную букву с вероятностью, равной единице.

 

Пример: Используя методику Хаффмана, осуществим эффективное кодирование ансамбля знаков, приведенного на рис. 3.2.

 

 

Рис. 3.2. Эффективное кодирование ансамбля знаков по методике Хаффмана

 

Для наглядности строим кодовое дерево. Из точки, соответствующей вероятно-

ятности 1, направляем две ветви, причем ветви с большей вероятностью присваиваем символ 1, а с меньшей 0. Такое последовательное ветвление продолжаем

-4-

до тех пор, пока не дойдем до вероятности каждой буквы. Кодовое дерево для алфавита букв, рассматриваемого в табл. 3.2, приведено на рис. 3.3.

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

 

Таблица 3.2

 

Z1 Z2 Z3 Z4 Z5 Z6 Z7 Z8

 

 

Рис. 3.3. Кодовое дерево Хаффмана

 

Контрольные вопросы

 

1. Классификация кодов.

2. Код Хаффмана Шеннона-Фано. Принцип построения.

3. Условие префиксности. Удовлетворяют ли коды Хаффмана и Шеннона-Фано требованию префиксности.

4. Особенности эффективного кодирования.

5. Энтропия ансамбля и её расчёт.

6. Декодирование кода Хаффмана и Шеннона-Фано.

 

ПРИЛОЖЕНИЕ

 

Варианты заданий

 

0.085 0.060 0.064 0.043 0.091 0.107 0.107 0.113 0.081 0.105 0.045 0.099
  0.065 0.064 0.058 0.105 0.102 0.094 0.075 0.083 0.086 0.060 0.085 0.123
  0.093 0.065 0.076 0.110 0.070 0.085 0.072 0.117 0.073 0.061 0.087 0.091
0.062 0.083 0.114 0.063 0.054 0.094 0.090 0.117 0.054 0.071 0.102 0.096
  0.075 0.057 0.122 0.067 0.119 0.055 0.073 0.092 0.098 0.053 0.111 0.078
  0.053 0.105 0.070 0.052 0.101 0.092 0.061 0.057 0.117 0.122 0.083 0.087
0.100 0.043 0.043 0.078 0.093 0.080 0.080 0.080 0.112 0.110 0.083 0.098
  0.067 0.053 0.053 0.107 0.083 0.082 0.071 0.093 0.100 0.091 0.074 0.126
  0.092 0.058 0.095 0.110 0.107 0.064 0.050 0.089 0.065 0.117 0.057 0.096
0.088 0.061 0.055 0.091 0.057 0.096 0.120 0.067 0.096 0.090 0.083 0.096
  0.061 0.047 0.078 0.117 0.111 0.067 0.061 0.119 0.102 0.082 0.099 0.056
  0.070 0.095 0.113 0.042 0.107 0.070 0.104 0.073 0.055 0.085 0.072 0.114
0.096 0.072 0.058 0.084 0.075 0.099 0.051 0.109 0.050 0.105 0.095 0.106
  0.060 0.048 0.097 0.089 0.092 0.069 0.059 0.086 0.093 0.084 0.108 0.115
  0.089 0.085 0.054 0.061 0.086 0.111 0.079 0.082 0.118 0.082 0.097 0.056
0.059 0.122 0.089 0.065 0.067 0.058 0.122 0.085 0.077 0.030 0.098 0.068
  0.057 0.086 0.055 0.106 0.067 0.117 0.116 0.065 0.103 0.047 0.104 0.077
  0.085 0.075 0.050 0.119 0.096 0.063 0.111 0.117 0.085 0.081 0.055 0.063
0.042 0.047 0.091 0.115 0.107 0.081 0.086 0.106 0.080 0.086 0.046 0.113
  0.097 0.105 0.075 0.092 0.080 0.102 0.053 0.048 0.103 0.052 0.091 0.102
  0.070 0.067 0.065 0.080 0.098 0.079 0.085 0.103 0.081 0.093 0.070 0.109
0.078 0.057 0.111 0.083 0.115 0.084 0.083 0.049 0.104 0.072 0.088 0.076
  0.078 0.112 0.099 0.032 0.076 0.044 0.090 0.079 0.098 0.051 0.083 0.098
  0.101 0.065 0.090 0.080 0.088 0.103 0.095 0.081 0.059 0.105 0.057 0.076
0.10B 0.055 0.069 10.110 0.046 0.072 0.086 0.071 0.105 0.102 0.094 0.082
  0.049 0.076 0.122 0.092 0.112 0 067 0.070 0.057 0.079 0.082 0.079 0.115
  0.050 0.099 0 085 0.073 0.083 0.114 0.089 0.078 0.069 0.086 0.099 0.075
0.058 0.110 0.105 0 041 0.092 0.077 0.057 0.082 0.110 0.059 0.109 0.100
  0.065 0.089 0.116 0.075 0.071 0.105 0.116 0.035 0 074 0.080 0 045 0,069
  0.067 0.06B 0.081 0.080 0.102 0.081 0.099 0.0G6 0.112 0.090 0.069 0.085
0.082 0 070 0.114 0.109 0.062 0.065 0.055 0.111 0.103 0.053 0.077 0.099
  0.069 0.059 0.071 0.110 0.056 0.094 0.101 0.083 0.072 0.085 0.124 0.076
  0.101 0.098 0.083 0.075 0 091 0.122 0.065 0.084 0.090 0.057 0.053 0.081
0.098 0.123 0.054 0.085 0.049 0 067 0.057 0.062 0.106 0.089 0.103
  0.105 0.103 0 098 0 069 0 059 0.055 0.079 0.082 0.115 0 072 0.093 0 070
  0.095 0.093 0.100 0.106 0.110 0 088 0 057 0,072 0.070 0.063 0.052 0.094

 

Продолжение приложения

 

0.062 0.092 0.097 0.120 0.051 0.105 0.101 0.075 0.084 0.054 0.074 0.085
  0.080 0.092 0 057 0.110 0.076 0.050 0.092 0.053 0.074 0.113 0.098
  0.068 0.052 0.061 0.088 0.116 0.085 0.113 0.063 0.057 0.110 0.080
0.051 0.094 0.049 0.114 0.092 0.087 0.088 0.071 0.097 0.090 0.0G9 0.098
  0.105 0.056 0.097 0 062 0.060 0.112 0.088 0.078 0.060 0.113 0.0G3
  0.113 0 078 0.123 0.079 0.065 0.056 0.081 0.114 0.062 0.086 0.067 0.076
0.058 0.093 0.074 0.098 0.078 0.070 0.078 0.052 0.6О 0.100 0.111 0.120
  0.071 0.097 0.079 0.105 0.093 0.083 0.087 0.058 0.105 0.045 0.052
  0.118 0.056 0 058 0.067 0.077 0.111 0.062 0.103 0.104 0.123 0.057 0.064
0.105 0.103 0.118 0.057 0.102 0.072 0.104 0.081 0.099 0 056 0.053 0.050
  0.101 0.078 0.066 0.051 0 076 0.125 0.063 0.086 0.121 0.055 0.073
  0.093 0.090 0 084 0.096 0.074 0.086 0.098 0.070 0.074 0.102 0.039 0.094
0.096 0.096 0.082 0.051 0.099 0.085 0.111 0.110 0.069 0.040 0.090 0.071
  0.064 0.098 0.074 0.069 0.113 0.071 0.115 0.075 0.065 0.096 0.094 0.066
  0.066 0.080 0.101 0.092 0.107 0.004 0.117 0.053 0.073 0.054 0.111 0.062
0.118 0.007 0.096 0.096 0.071 0.109 0.095 0.060 0.067 0.050 0.055
  0.002 0.104 0.092 0 097 0.080 0.007 0.093 0.071 0.040 0.047 0.100 0.037
  0.103 0.064 0.110 0.04 5 0.059 0.101 0.086 0.095 0.064 0.098 0.112 0.063
0.070 0.053 0.106 0.090 0.095 0.089 0.099 0.055 0.109 0.109 0.044 0.081
  0.047 0.109 0.0S1 0.099 0.085 0.055 0.116 0 071 0.059 0.090 0.048 0.130
  0.045 0.097 0.084 0.086 0.051 0.084 0.053 0.103 0.056 0.116 0.106 0.119
0.008 0.082 0.099 0.062 0.101 0.057 0.082 0.113 0.093 0.063 0.087 0.073
  0.058 0.083 0.122 0.110 0.076 0.115 0.060 0.073 0 061 0.104 0.066 0 072
  0.057 0.053 0.076 0.097 0.070 0.110 0.122 0.094 0.073 0 096 0.080 0.072
0.105 0 080 0.058 0.114 0.078 0.057 0 061 0.069 0.089 0.082 0.114 0.093
  0 063 0.061 0 084 0.097 0.099 0.111 0.068 0 086 0.111 0.068 0.055 0.097
  0.058 0,117 0.068 0.072 0.066 0.095 0,097 0 092 0,058 0.097 0.094 0.086
0.045 0.083 0.107 0.116 0,105 0,063 0.046 0.087 0.065 0 071 0.107
  0,054 0.060 0,096 0.086 0.097 0.102 0.110 0 058 0.053 0.078 0.103
  0 071 0.097 0 089 0.055 0.101 0 098 0 078 0,102 0.069 0.061
0.109 0,079 0,070 0,102 0,072 0 055 0,065 0,066 0,103 0.090 0.103 0.086
  0,108 0,051 0,038 0.094 0.076 0,115 0 076 0,081 0,065 0.060 0.109 0.069
  0.095 0.099 0 0S3 0,077 0.113 0.093 0 064 0.091 0,111 0.074 0.063 0.057
0.103 0,093 0,093 0.063 0.096 0,061 0,081 0,054 0,110 0.052 0.103 0.111
  0.072 0.118 0 064 0,111 0.049 0.110 0,049 0,089 0,047 0.074 0.115 0.104
  0.063 0.077 0.080 0.066 0.058 0.101 0,107 0,097 0 069 0.116 0.093 0.073
0.100 0.052 0.108 0.036 0.073 0.070 0.055 0.077 0.111 0.044 0.097
  0.086 0.085 0.063 0.073 0 089 0.065 0.073 0.086 0.063 0.088 0.103
  0.088 0.104 0.083 0.096 0 074 0.052 0.070 0.053 0.080 0.109 0.083
0.088 0.110 0.047 0.056 0,083 0.104 0.088 0.075 0.059 0.071 0.108
  0.092 0.085 0.102 0 055 0.094 0.086 0.084 0.101 0 056 0.054 0.063 0.128
  0.036 0.009 0.068 0.058 0.094 0 047 0.111 0 071 0.091 0.066