Кодирование

Значение слова Кодирование по Ефремовой:
Кодирование - Процесс действия по знач. несов. глаг.: кодировать, кодироваться (1).

Кодирование в Энциклопедическом словаре:
Кодирование - операция отождествления символов или групп символов одногокода с символами или группами символов другого кода.

Значение слова Кодирование по словарю медицинских терминов:
Кодирование - процесс записи информации при помощи кода, напр., К. порядка расположения аминокислот в полипептидной цепи последовательностью азотистых оснований нуклеиновой кислоты.

Определение слова «Кодирование» по БСЭ:
Кодирование - операция отождествления символов или групп символов одного кода с символами или группами символов другого кода. Необходимость К. возникает прежде всего из потребности приспособить форму сообщения к данному каналу связи или какому-либо другому устройству, предназначенному для преобразования или хранению информации. Так, сообщения представленные в виде последовательности букв, например русского языка, и цифр, с помощью телеграфных кодов преобразуются в определённые комбинации посылок тока. При вводе в вычислительные устройства обычно пользуются преобразованием числовых данных из десятичной системы счисления в двоичную и т.д. (см. Кодирующее устройство).
К. в информации теории применяют для достижения следующих целей: во-первых, для уменьшения так называемой избыточности сообщений и, во-вторых, для уменьшения влияния помех, искажающих сообщения при передаче по каналам связи (см. Шеннона теорема). Поэтому выбор нового кода стремятся наиболее удачным образом согласовать со статистической структурой рассматриваемого источника сообщений. В какой-то степени это согласование имеется уже в коде телеграфном, в котором чаще встречающиеся буквы обозначаются более короткими комбинациями точек и тире.
Приёмы, применяемые в теории информации для достижения указанного согласования, можно пояснить на примере построения «экономных» двоичных кодов. Пусть канал может передавать только символы 0 и 1, затрачивая на каждый одно и то же время t. Для уменьшения времени передачи (или, что то же самое, увеличения её скорости) целесообразно до передачи кодировать сообщения таким образом, чтобы средняя длина L кодового обозначения была наименьшей. Пусть х₁, х₂,..., x_n обозначают возможные сообщения некоторого источника, a p₁, р₂,..., р₂ - соответствующие им вероятности. Тогда, как устанавливается в теории информации, при любом способе К.,
L ≥ Н , (1)
где H = Σ_i=1ⁿ p_i log₂ (1 ⁄ p_i)
- энтропия источника. Граница для 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. Применение метода иллюстрируется табл.:

х_i Pi Кодовое обозначение
х₁ 9/16 0
х₂ 3/16 1 0
х₃ 3/16 1 1 0
х₃ 1/16 1 1 1

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

L = 1· 1

16
+ 2· 3

16
+ 3· 3

16
+ 3· 1

16
= 27

16
= 1,688

и можно показать, что никакой др. код не даёт меньшего значения. В то же время H = 1,623. Всё сказанное применимо и к случаю, когда алфавит нового кода содержит не 2, как предполагалось выше, а m>2 букв. При этом лишь величина H в формулах (1) и (2) должна быть заменена величиной H/log₂m.
Задача о «сжатии» записи сообщений в данном алфавите (то есть задача об уменьшении избыточности) может быть решена на основе метода Шеннона-Фэно. Действительно, с одной стороны, если сообщения представлены последовательностями букв длины N из m-буквенного алфавита, то их средняя длина L_N после К. всегда удовлетворяет неравенству
L_N ≥ NH ⁄log₂m , где Н - энтропия источника на букву.
С другой стороны, при сколь угодно малом ε > 0 можно добиться выполнения при всех достаточно больших N неравенства
L_N < N (^H ⁄_log₂m + ε) . (3)
С этой целью пользуются К. «блоками»: по данному ε выбирают натуральное число s и делят каждое сообщение на равные части - «блоки», содержащие по s букв. Затем эти блоки кодируют методом Шеннона - Фэно в тот же алфавит. Тогда при достаточно больших N будет выполнено неравенство (3). Справедливость этого утверждения легче всего понять, рассматривая случай, когда источником является последовательность независимых символов 0 и 1, появляющихся с вероятностями соответственно p и 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).
При таком К. энтропия на букву приближается к своему максимальному значению - единице, а избыточность - к нулю.
Пример 2. Пусть источником сообщений является последовательность независимых знаков 0 и 1, в которой вероятность появления нуля равна p = ³/₄, а единицы q = ј. Здесь энтропия Н на букву равна 0,811, а избыточность - 0,189. Наименьшие блоки (s = 2), то есть 00, 01, 10, 11, имеют соответственно вероятности pІ = ⁹/₁₆, pq = ³/₁₆, qp = ³/₁₆, qІ =¹/₁₆. Применение метода Шеннона - Фэно (см. пример 1) приводит к правилу К.: 00
→0, 01→10, 10→110, 11→111. При этом, например, сообщение 00111000... примет вид 01111100... На каждую букву сообщения в прежней форме приходится в среднем ²⁷/₃₂ = 0,844 буквы в новой форме (при нижней границе коэффициента сжатия, равной Н = 0,811). Энтропия на букву в новой последовательности равна 0,811/0,844 = 0,961, а избыточность равна 0,039.
К., уменьшающее помехи, превратилось в большой раздел теории информации, со своим собственным математическим аппаратом, в значительной мере чисто алгебраическим (см. Канал, Шеннона теорема и литературу при этих статьях).
Ю. В. Прохоров.

Кодировальный Кодирование Кодирование Товара Штриховое