КОДИРОВАНИЕ
операция отождествления
символов или групп символов одного кода с символами или группами
символов др. кода. Необходимость К. возникает прежде всего из потребности
приспособить форму сообщения к данному каналу связи или к.-л. др. устройству,
предназначенному для преобразования или хранения информации. Так, сообщения,
представленные в виде последовательности букв, напр, русского языка, и
цифр, с помощью телеграфных кодов преобразуются в определённые комбинации
посылок тока. При вводе в вычислит, устройства обычно пользуются преобразованием
числовых данных из десятичной системы счисления в двоичную и т. д. (см.
Кодирующее
устройство).
К. в информации теории применяют
для достижения следующих целей: во-первых, для уменьшения т. н. избыточности
сообщений
и, во-вторых, для уменьшения влияния помех, искажающих сообщения при передаче
по каналам связи (см. Шеннона теорема). Поэтому выбор нового кода
стремятся наиболее удачным образом согласовать со статистич. структурой
рассматриваемого источника сообщений. В какой-то степени это согласование
имеется уже в коде телеграфном, в к-ром чаще встречающиеся буквы
обозначаются более короткими комбинациями точек и тире.
Приёмы, применяемые в теории информации
энтропия источника. Граница
L =< Н + 1
Метод состоит и том, что сообщения
Пример 1. Пусть n = 4 и p Задача о "сжатии" записи сообщений
С этой целью пользуются К. "блоками":
Пример 2. Пусть источником сообщений
К., уменьшающее помехи, превратилось
А
Б
В
Г
Д
Е
Ё
Ж
З
И
Й
К
Л
М
Н
О
П
Р
С
Т
У
Ф
Х
Ц
Ч
Ш
Щ
Ъ
Ы
Ь
Э
Ю
Я
для достижения указанного согласования, можно пояснить на примере построения
"экономных" двоичных кодов. Пусть канал может передавать только символы
0 и 1, затрачивая на каждый одно и то же время t. Для уменьшения
времени передачи (или, что то же самое, увеличения её скорости) целесообразно
до передачи кодировать сообщения таким образом, чтобы средняя длина L кодового
обозначения была наименьшей. Пусть xi, x
возможные сообщения нек-рого источника, a PI, .р
устанавливается в теории информации, при любом способе К.,
где
для L в формуле (1) может не достигаться. Од-нако при любых
рi
существует метод К. (метод Шеннона - Фэно), для к-рого
(2)
располагаются в порядке убывания вероятностей и полученный ряд делится
на 2 части с вероятностями, по возможности близкими друг к другу. В качестве
1-го двоичного знака принимают 0 в 1-й части и 1 - во 2-й. Подобным же
образом делят пополам каждую из частей и выбирают 2-й двоичный знак и т.
д., пока не придут к частям, содержащим только по одному сообщению.
Применение метода иллюстрируется табл.:
xi
рi
Кодовое
обозначение
X1
9/16
0
x2
3/16
1
0
Х3
3/16
1
1
0
X4
1/16
1
1
1
В данном случае L =1x9/16 + 2x
3/16 +3x3/16+3x1/16=27/16=1.688, и можно показать, что никакой Др. код
не даёт меньшего значения. В то же время Н = 1,623. Вгё сказанное применимо
и к случаю, когда алфавиг нового кода содержит не 2, как предполагалось
выше, а т>2 букв. При этом лишь величина Н в формулах (1)
и
(2) должна быть заменена величиной H/log
в данном алфавите (т. е. задача об уменьшении избыточности) может
быть решена на основе метода Шеннона - Фэно. Действительно, с одной стороны,
если сообщения представлены последовательностями букв длины N из
те-буквенного алфавита, то их средняя длина L
К. всегда удовлетворяет неравенству L
угодно малом e>0 можно добиться выполнения при всех достаточно больших
N
неравенства
по данному е выбирают натуральное число 5 и делят каждое сообщение на равные
части -"блоки", содержащие по 5 букв. Затем эти блоки кодируют методом
Шеннона - Фэно в тот же алфавит. Тогда при достаточно больших N будет
выполнено неравенство (3). Справедливость этого утверждения легче
всего понять, рассматривая случай, когда источником является последовательность
независимых символов 0 и 1, появляющихся с вероятностями соответственно
р
и q, p<>q. Энтропия на блок равна 5-кратной энтропии на одну
букву, т. е. равна sH = = s(plog2l/p + qlog
обозначение блока требует в среднем не более sH+ 1двоичных знаков.
Поэтому для сообщения длины N букв LN=<(1 + N/S) (sH + +
1) = N(H+1/s) (1 + s/N), что при достаточно больших s и N/s
приводит к неравенству (3). При таком К. энтропия на букву приближается
к своему макс, значению - единице, а избыточность - к нулю.
является последовательность независимых знаков 0 и 1, в к-рой вероятность
появления нуля равна р = 3/4, а единицы q = 1/4
Здесь энтропия Н на букву равна 0,811, а избыточность - 0,189. Наименьшие
блоки (s = 2), т. е. 00, 01, 10, 11, имеют соответственно
вероятности р2 = 9/1б, pq = 3/i6,
qp
= = 3/i6, q2 = Vie. Применение метода
Шеннона - Фэно (см. пример 1) приводит к правилу К.: 00 ->0, 01->10,
10->110, 11-МИ. При этом, напр., сообщение 00111000... примет вид 01111100...
На каждую букву сообщения в прежней форме приходится в среднем 27/32 =
0,844 буквы в новой форме (при нижней границе коэффициента сжатия, равной
Н = = 0,811). Энтропия на букву в новой последовательности равна
0,811/0,844 = = 0,961, а избыточность равна 0,039.
в большой раздел теории информации, со своим собственным математич. аппаратом,
в
значит, мере чисто алгебраическим (см. Канал, Шеннона теорема
и
лит. при этих статьях). Ю. В. Прохоров.