БСЭ энциклопедия
Кодирование, операция отождествления символов или групп

Кодирование

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

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

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

  где L & sup3;Н, (1)

 

Большая Советская 
 Энциклопедия (КО)
 

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

  L ? Н + 1. (2)

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

  Пример 1. Пусть n = 4 и p1 =9/16, р2 = р3 = 3/16, p4 = 1/16. Применение метода иллюстрируется табл.:



х, Pi Кодовое обозначение
х1 9/16 0
х2 3/16 1 0
х3 3/16 1 1 0
х3 1/16 1 1 1


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

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

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

 

Большая Советская 
 Энциклопедия (КО)
. (3)

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

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

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

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

источник: Большая Советская Энциклопедия

  • Другие статьи:
Искать информацию по запросу: Кодирование на eBay аукцион * в Большой Российской Энциклопедии * в магазине Озоне
Search Москва All Amazon* UK* DE* FR* JP* CA* CN* IT* ES* IN* BR* MX
Search Moscow All Ebay* AU* AT* BE* CA* FR* DE* IN* IE* IT* MY* NL* PL* SG* ES* CH* UK*


$13.99
End Date: Sunday Jun-16-2019 11:58:41 PDT
Buy It Now for only: $13.99
|
Russia Р РѕСЃСЃРёСЏ Moscow Putin Communist Soviet Red Alert USSR Funny T-shirt


$13.99
End Date: Sunday Jun-16-2019 11:58:41 PDT
Buy It Now for only: $13.99
|
Russia Р РѕСЃСЃРёСЏ Moscow Putin Communist Soviet Red Alert USSR Funny T-shirt


$13.99
End Date: Sunday Jun-16-2019 11:58:41 PDT
Buy It Now for only: $13.99
|
Russia Р РѕСЃСЃРёСЏ Moscow Putin Communist Soviet Red Alert USSR Funny T-shirt


$13.99
End Date: Sunday Jun-16-2019 11:58:41 PDT
Buy It Now for only: $13.99
|
Russia Р РѕСЃСЃРёСЏ Moscow Putin Communist Soviet Red Alert USSR Funny T-shirt


$13.99
End Date: Sunday Jun-16-2019 11:58:41 PDT
Buy It Now for only: $13.99
|
Russia Р РѕСЃСЃРёСЏ Moscow Putin Communist Soviet Red Alert USSR Funny T-shirt


$13.99
End Date: Sunday Jun-16-2019 12:02:14 PDT
Buy It Now for only: $13.99
|
Russia Retro Ringer Р РѕСЃСЃРёСЏ Moscow Putin Communist Soviet Football T-shirt (Red)


$13.99
End Date: Thursday Jun-6-2019 14:51:06 PDT
Buy It Now for only: $13.99
|
CCCP Star Soviet Communist Russia Moscow Putin Funny Politics T-shirt


$13.99
End Date: Thursday Jun-6-2019 14:51:06 PDT
Buy It Now for only: $13.99
|
Search Results from «Ваш Магазин» Печать книг на заказ. Новинки.
 Москва в судьбах казачества РоссииМосква в судьбах казачества России, 2018 г.
Шишов А.В.

История казачества России, уникального воинского сословия, на протяжении многих веков неразрывными узами связана с первопрестольной Москвой-столицей. Возникнув на южной степной окраине Русской земли, вольное православное казачество само пришло на службу Отечеству как порубежная стража,...
Цена: 679 руб.
 Москва. История. Архитектура. Искусство (на французском языке)Москва. История. Архитектура. Искусство (на французском языке), 2011 г.

Альбом - сувенир рассказывает о Кремле, Красной площади, Москве, Московском метро и Троице-Сергиевой Лавре.
Цена: 853 руб.
 Сухарева башня. Исторический памятник и проблема его воссозданияСухарева башня. Исторический памятник и проблема его воссоздания, 1997 г.
Щербо Г.М.

Учитывая неполноту, неточность и искаженность представлений о создании Сухаревой башни и последующей истории вплоть до трагедии ее уничтожения, автор дает ряд новых научных сведений и оценок. Проанализированы градостроительные условия существования уникального сооружения. Показаны...
Цена: 757 руб.
 Прияузье. По древним московским землямПрияузье. По древним московским землям, 2017 г.
Шеватов Борис Алексеевич

Как Москва-река от верховья до устья была местом притяжения сел и древних монастырей, дворянских усадеб, так и Яуза, опоясавшая обширные территории предместья, все больше привлекала к себе русских служилых людей. И возникали деревни, и села, и приходские храмы по берегам этой речки....
Цена: 707 руб.
 Исторический путеводитель по московским переулкам. Часть 1. Лаврушинский. Писательский переулокИсторический путеводитель по московским переулкам. Часть 1. Лаврушинский. Писательский переулок, 2019 г.
Васькин А.А.

«Красна изба пирогами, а Москва – дворцами». Да, богата наша столица палатами каменными да особняками барскими. На какую улицу ни брось взгляд – то здесь, то там высится старинный памятник архитектуры с длинной историей, составившей ему славу и популярность. Толпами ходят вокруг...
Цена: 101 руб.
2008 Copyright © MoscowMSK.ru Мобильная Версия v.2015 | PeterLife и компания Москвоведение. Энциклопедия. Компании и фирмы. Новости Москвы. России и Мира сегодня. Прогноз погоды. Политика, бизнес, экономика. Объявления: Работа и вакансии. Знакомства. Полезная информация для туристов: отдых и путешествия. Экскурсии и туры по Москве. Популярные магазины. Продажа товаров и услуги онлайн. | Пользовательское соглашение использование материалов сайта разрешено с активной ссылкой на сайт. | SkimLinks международная реклама магазинов. | Скрипты Nevius. | Раскрутка сайтов 1ПС. | Хостинг Valuehost.
Рейтинг@Mail.ru Яндекс.Метрика Яндекс цитирования