Читать «Большая Советская Энциклопедия (КО)» онлайн - страница 97

  Приёмы, применяемые в теории информации для достижения указанного согласования, можно пояснить на примере построения «экономных» двоичных кодов. Пусть канал может передавать только символы 0 и 1, затрачивая на каждый одно и то же время t. Для уменьшения времени передачи (или, что то же самое, увеличения её скорости) целесообразно до передачи кодировать сообщения таким образом, чтобы средняя длина L кодового обозначения была наименьшей. Пусть х₁ , х₂ ,..., x_n обозначают возможные сообщения некоторого источника, a p₁ , р₂ , ..., р₂   — соответствующие им вероятности. Тогда, как устанавливается в теории информации, при любом способе К.,

  где L ³ Н, (1)

   —

  энтропия источника. Граница для L в формуле (1) может не достигаться. Однако при любых p_i существует метод К. (метод Шеннона — Фэно), для которого

  L £ Н + 1. (2)

  Метод состоит в том, что сообщения располагаются в порядке убывания вероятностей и полученный ряд делится на 2 части с вероятностями, по возможности близкими друг к другу. В качестве 1-го двоичного знака принимают 0 в 1-й части и 1 — во 2-й. Подобным же образом делят пополам каждую из частей и выбирают 2-й двоичный знак и т.д., пока не придут к частям, содержащим только по одному сообщению.

  Пример 1. Пусть n = 4 и p₁ =9/16, р₂ = р₃ = 3/16, p₄ = 1/16. Применение метода иллюстрируется табл.:

х,

Pi

Кодовое обозначение

х₁

9/16

0

х₂

3/16

1

0

х₃

3/16

1

1

0

х₃

1/16

1

1

1

B данном случае L =  = 1,688 и можно показать, что никакой др. код не даёт меньшего значения. В то же время Н = 1,623. Всё сказанное применимо и к случаю, когда алфавит нового кода содержит не 2, как предполагалось выше, а m > 2 букв. При этом лишь величина Н в формулах (1) и (2) должна быть заменена величиной H/log₂ m.

  Задача о «сжатии» записи сообщений в данном алфавите (то есть задача об уменьшении избыточности) может быть решена на основе метода Шеннона — Фэно. Действительно, с одной стороны, если сообщения представлены последовательностями букв длины N из м -буквенного алфавита, то их средняя длина L_N после К. всегда удовлетворяет неравенству L_N ³NH/log₂ т, где Н — энтропия источника на букву. С другой стороны, при сколь угодно малом e>0 можно добиться выполнения при всех достаточно больших N неравенства

  . (3)

  С этой целью пользуются К. «блоками»: по данному e выбирают натуральное число s и делят каждое сообщение на равные части — «блоки», содержащие по s букв. Затем эти блоки кодируют методом Шеннона — Фэно в тот же алфавит. Тогда при достаточно больших N будет выполнено неравенство (3). Справедливость этого утверждения легче всего понять, рассматривая случай, когда источником является последовательность независимых символов 0 и 1, появляющихся с вероятностями соответственно р и q, p ¹q. Энтропия на блок равна s-кpaтной энтропии на одну букву, т. е. равна sH =s (plog₂ 1/p+qlog₂ 1/q ). Кодовое обозначение блока требует в среднем не более sH + 1 двоичных знаков. Поэтому для сообщения длины N букв L_N £(1+N/s ) (sH +1) = N (H +1/s ) (1+s/N ), что при достаточно больших s и N/s приводит к неравенству (3). При таком К. энтропия на букву приближается к своему максимальному значению — единице, а избыточность — к нулю.