КОДИРОВАНИЕ, операция отождествления символов или групп символов одного кода с символами или группами символов др. кода. Необходимость К. возникает прежде всего из потребности приспособить форму сообщения к данному каналу связи или к.-л. др. устройству, предназначенному для преобразования или хранения информации. Так, сообщения, представленные в виде последовательности букв, напр., русского языка, и цифр, с помощью телеграфных кодов преобразуются в определённые комбинации посылок тока. При вводе в вычислит, устройства обычно пользуются преобразованием числовых данных из десятичной системы счисления в двоичную и т. д. (см. Кодирующее устройство).

К. в информации теории применяют для достижения следующих целей: во-первых, для уменьшения т. н. избыточности сообщений и, во-вторых, для уменьшения влияния помех, искажающих сообщения при передаче по каналам связи (см. Шеннона теорема). Поэтому выбор нового кода стремятся наиболее удачным образом согласовать со статистич. структурой рассматриваемого источника сообщений. В какой-то степени это согласование имеется уже в коде телеграфном, в к-ром чаще встречающиеся буквы обозначаются более короткими комбинациями точек и тире.

Приёмы, применяемые в теории информации для достижения указанного согласования, можно пояснить на примере построения "экономных" двоичных кодов. Пусть канал может передавать только символы 0 и 1, затрачивая на каждый одно и то же время t. Для уменьшения времени передачи (или, что то же самое, увеличения её скорости) целесообразно до передачи кодировать сообщения таким образом, чтобы средняя длина L кодового обозначения была наименьшей. Пусть xi, x₂,..., Хп обозначают возможные сообщения нек-рого источника, a PI, .р₂, ..., р_п- соответствующие VIM вероятности. Тогда, как устанавливается в теории информации, при любом способе К.,

где

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

L =< Н + 1        (2)

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

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

xi	рi	Кодовое обозначение
X1	9/16	0
x2	3/16	1	0
Х3	3/16	1	1	0
X4	1/16	1	1	1

В данном случае L =1 x ⁹/₁₆ + 2 x ³/₁₆ + 3 x ³/₁₆ + 3 x ¹/₁₆ = ²⁷/₁₆ = 1.688, и можно показать, что никакой Др. код не даёт меньшего значения. В то же время Н = 1,623. Вгё сказанное применимо и к случаю, когда алфавиг нового кода содержит не 2, как предполагалось выше, а т>2 букв. При этом лишь величина Н в формулах (1) и (2) должна быть заменена величиной ^H/_log2m.

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

С этой целью пользуются К. "блоками": по данному е выбирают натуральное число 5 и делят каждое сообщение на равные части -"блоки", содержащие по 5 букв. Затем эти блоки кодируют методом Шеннона - Фэно в тот же алфавит. Тогда при достаточно больших N будет выполнено неравенство (3). Справедливость этого утверждения легче всего понять, рассматривая случай, когда источником является последовательность независимых символов 0 и 1, появляющихся с вероятностями соответственно р и q, p <> q. Энтропия на блок равна 5-кратной энтропии на одну букву, т. е. равна sH = = ^s(plog2l/_p + qlog₂l/q. Кодовое обозначение блока требует в среднем не более sH + 1двоичных знаков. Поэтому для сообщения длины N букв LN =< (1 + N/S) (sH + + 1) = N(H+1/s) (1 + s/N), что при достаточно больших s и N/s приводит к неравенству (3). При таком К. энтропия на букву приближается к своему макс, значению - единице, а избыточность - к нулю.

Пример 2. Пусть источником сообщений является последовательность независимых знаков 0 и 1, в к-рой вероятность появления нуля равна р =¾, а единицы q = ¼. Здесь энтропия Н на букву равна 0,811, а избыточность - 0,189. Наименьшие блоки (s = 2), т. е. 00, 01, 10, 11, имеют соответственно вероятности р² = ⁹/₁₆, pq = ³/₁₆, qp = = ³/₁₆, q² = Vie. Применение метода Шеннона - Фэно (см. пример 1) приводит к правилу К.: 00 ->0, 01->10, 10->110, 11-МИ. При этом, напр., сообщение 00111000... примет вид 01111100... На каждую букву сообщения в прежней форме приходится в среднем ²⁷/₃₂ = 0,844 буквы в новой форме (при нижней границе коэффициента сжатия, равной Н = = 0,811). Энтропия на букву в новой последовательности равна 0,811/0,844 = = 0,961, а избыточность равна 0,039.

К., уменьшающее помехи, превратилось в большой раздел теории информации, со своим собственным математич. аппаратом, в значит, мере чисто алгебраическим (см. Канал, Шеннона теорема и лит. при этих статьях).

Ю. В. Прохоров.