Кодирование

Коди́рование, операция отождествления символов или групп символов одного кода с символами или группами символов другого кода. Необходимость кодирования возникает прежде всего из потребности приспособить форму сообщения к данному каналу связи или какому-либо другому устройству, предназначенному для преобразования или хранения информации. Так, с помощью телеграфных кодов сообщения, представленные в виде последовательности букв и цифр, преобразуются в определённые комбинации точек и тире. Другой целью кодирования является защита сообщений от несанкционированного доступа.

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

Приёмы, применяемые в теории информации для достижения указанного согласования, можно пояснить на примере построения экономных двоичных кодов. Пусть канал связи может передавать только символы ${\displaystyle 0}$ и ${\displaystyle 1}$, затрачивая на каждый одно и то же время ${\displaystyle t}$. Для уменьшения времени передачи (или для увеличения её скорости) целесообразно до передачи кодировать сообщения таким образом, чтобы средняя длина ${\displaystyle L}$ кодового обозначения была наименьшей. Пусть ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ обозначают возможные сообщения некоторого источника, а ${\displaystyle p_{1},p_{2},\ldots ,p_{n}}$ – соответствующие им вероятности. Тогда, как устанавливается в теории информации, при любом способе кодирования

${\displaystyle L\geq H}$ (1),

где ${\displaystyle H=\sum _{i=1}^{n}p_{i}\log _{2}(1/p_{i})}$ – энтропия источника. Равенство в формуле ${\displaystyle (1)}$ может не достигаться. Однако при любых ${\displaystyle p_{1},p_{2},\ldots ,p_{n}}$ существует метод кодирования (метод Шеннона – Фано), для которого

${\displaystyle L\leq H+1}$ (2).

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

Пример 1. Пусть ${\displaystyle n=4}$ и ${\displaystyle p_{1}=9/16}$, ${\displaystyle p_{2}=p_{3}=3/16}$, ${\displaystyle p_{4}=1/16}$. Применение метода иллюстрируется таблицей:

${\displaystyle x_{i}}$	${\displaystyle p_{i}}$	Кодовое обозначение
${\displaystyle x_{1}}$	${\displaystyle 9/16}$	${\displaystyle 0}$
${\displaystyle x_{2}}$	${\displaystyle 3/16}$	${\displaystyle 10}$
${\displaystyle x_{3}}$	${\displaystyle 3/16}$	${\displaystyle 110}$
${\displaystyle x_{4}}$	${\displaystyle 1/16}$	${\displaystyle 111}$

В данном случае

${\displaystyle L=1\cdot {\frac {9}{16}}+2\cdot {\frac {3}{16}}+3\cdot {\frac {3}{16}}+3\cdot {\frac {1}{16}}={\frac {27}{16}}=1,688}$,

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

Задача о сжатии записи сообщений в данном алфавите (т. е. задача об уменьшении избыточности) может быть решена на основе метода Шеннона – Фано. Если сообщения представлены последовательностями длины ${\displaystyle N}$ букв из ${\displaystyle m}$-буквенного алфавита, то их средняя длина ${\displaystyle L_{N}}$ после кодирования всегда удовлетворяет неравенству

${\displaystyle L_{N}\geq NH/\log _{2}m}$,

где ${\displaystyle H}$ – энтропия источника на букву. Кроме того, при сколь угодно малом ${\displaystyle \epsilon >0}$ можно добиться выполнения при всех достаточно больших ${\displaystyle N}$ неравенства

${\displaystyle L_{N}<N(H/\log _{2}m+\varepsilon )}$ (3).

С этой целью используют кодирование блоками: по данному ${\displaystyle \epsilon }$ выбирают достаточно большое натуральное число ${\displaystyle s}$ и делят каждое сообщение на равные части – блоки, содержащие по ${\displaystyle s}$ букв. Затем эти блоки кодируют методом Шеннона – Фано в тот же алфавит. Тогда при достаточно больших ${\displaystyle N}$ будет выполнено неравенство ${\displaystyle (3)}$. Справедливость этого утверждения легче всего понять, рассматривая случай, когда источником является последовательность независимых символов ${\displaystyle 0}$ и ${\displaystyle 1}$, появляющихся соответственно с вероятностями ${\displaystyle p}$ и ${\displaystyle q}$, ${\displaystyle 0<p<1}$. Энтропия на блок равна ${\displaystyle s}$-кратной энтропии на одну букву, т. е. равна ${\displaystyle sH=s(p\log _{2}1/p+q\log _{2}1/q)}$. Кодовое обозначение блока требует в среднем не более ${\displaystyle sH+1}$ двоичных знаков. Поэтому для сообщения, состоящего из ${\displaystyle N}$ букв,

${\displaystyle L_{N}\leq (1+N/s)(sH+1)=N(H+1/s)(1+s/H)}$,

что при достаточно больших ${\displaystyle s}$ и ${\displaystyle N/s}$ приводит к неравенству ${\displaystyle (3)}$. При таком кодировании энтропия на букву приближается к своему максимальному значению – единице, а избыточность – к нулю.

Пример 2. Пусть источником сообщений является последовательность независимых знаков ${\displaystyle 0}$ и ${\displaystyle 1}$, в которой вероятность появления нуля равна ${\displaystyle p=3/4}$, а единицы – ${\displaystyle q=1/4}$. Здесь энтропия ${\displaystyle H}$ на букву равна ${\displaystyle 0,811}$, а избыточность – ${\displaystyle 0,189}$. Наименьшие блоки (${\displaystyle s=2}$), т. е. ${\displaystyle 00}$, ${\displaystyle 01}$, ${\displaystyle 10}$, ${\displaystyle 11}$, имеют соответственно вероятности ${\displaystyle p^{2}=9/16}$, ${\displaystyle pq=3/16}$, ${\displaystyle qp=3/16}$, ${\displaystyle q^{2}=1/16}$. Применение метода Шеннона – Фано приводит к следующему правилу кодирования: ${\displaystyle 00\to 0}$, ${\displaystyle 01\to 10}$, ${\displaystyle 10\to 110}$, ${\displaystyle 11\to 111}$. При этом, например, сообщение ${\displaystyle 00111000\ldots }$ примет вид ${\displaystyle 01111100\ldots }$ На каждую букву сообщения в прежней форме приходится в среднем ${\displaystyle 27/32=0,844}$ буквы в новой форме (при нижней границе коэффициента сжатия, равной ${\displaystyle H=0,811}$. Энтропия на букву в новой последовательности равна ${\displaystyle 0,811/0,844=0,961}$, а избыточность равна ${\displaystyle 0,039}$.

См. также Криптография, теорема Шеннона.