Теорема Шеннона и передача информации. Понятие о теоремах шеннона

Теорема Под свободным мировым рынком понимается ситуация, когда товары и капиталы могут свободно перемещаться по всему миру, валюты свободно конвертируются, пошлины на границах невелики, или вообще ни пошлин, ни границ нет, и предприятия, независимо от формы

Рассмотрим две фундаментальные теоремы идеального кодирования, носящие имя Шеннона. Первая из них рассматривает случай отсутствия помех в канале, вторая учитывает наличие помех, приводящих к ошибкам.

Рассмотрим проблему согласования источника сообщений и канала при передаче последовательности сообщений. Пусть источник сообщений выдает сообщения с некоторой скоростью (сообщений/ед. времени), называемой технической производительностью источника. Пусть по каналу можно передавать без искажений сообщения со скоростью, не превышающей некоторую величину(сообщений/ед. времени), называемую технической пропускной способностью канала. Очевидно, что если выполняется условие<, то канал успевает передать все сообщения, поступающие на его вход от источника, и передача будет вестись без искажений. Что произойдет, если>? Можно ли в этом случае обеспечить передачу без искажений? Если исходить только из технических характеристик, то, очевидно, нельзя. А если учесть информационные характеристики? Ведь нам известно, что если последовательность обладает информационной избыточностью, то её можно сжать, применив методы экономного кодирования. Рассмотрим подробнее такую возможность.

Пусть V u - (информационная) производительность источника, т.е. количество информации, производимое источником в единицу времени; C k – (информационная) пропускная способность канала, т.е. максимальное количество информации, которое способен передать канал без искажений за единицу времени. Первая теорема Шеннона утверждает, что безошибочная передача сообщений определяется соотношением V u и C k .

Первая теорема Шеннона: если пропускная способность канала без помех превышает производительность источника сообщений, т.е. удовлетворяется условие C k > V u ,

то существует способ кодирования и декодирования сообщений источника, обеспечивающий сколь угодно высокую надежность передачи сообщений. В противном случае, т.е. если C k < V u

Такого способа нет.

Таким образом, идеальное кодирование по Шеннону по существу представляет собой экономное кодирование последовательности сообщений при безграничном укрупнении сообщений. Такой способ кодирования характеризуется задержкой сообщений

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

Теорема Шеннона для канала с помехами

При отсутствии помех ошибки при передаче могут возникать только за счет неоднозначного кодирования сообщений. Рассмотрим теперь ситуацию, когда в канале действуют помехи, вызывающие искажения передаваемых символов. Возникающие при этом ошибки носят случайный характер, они действуют при любой скорости передачи сообщений через канал, в том числе, когда V u < V k .

Возникает вопрос, возможен ли такой способ кодирования, при котором сообщения передаются через канал без ошибок с некоторой ненулевой скоростью V k. 0 (действие ошибок полностью устраняется при кодировании)? В первой главе рассматривались методы помехоустойчивости кодирования, основанные на введении избыточности. Однако для полного устранения ошибок их применение потребовало бы введения бесконечной избыточности, что привело бы к снижению скорости передачи сообщений до нуля.

Тем не менее вторая теорема Шеннона утверждает, что такой способ возможен. Тогда возникает следующий вопрос: чем определяется максимальная скорость передачи сообщений по каналу с помехами? Оказывается, что, как и для канала без помех, она определяется соотношением информационных характеристик источника и канала.

Вторая теорема Шеннона: для канала с помехами существует такой способ кодирования, при котором обеспечивается безошибочная передача всех сообщений источника, если только пропускная способность канала превышает производительность источника, т.е. C k > V u .

Возникающая ситуация поясняется на рис. 19. На вход канала поступают типичные последовательности источника А Т . Они кодируются последовательностями канала , причем для этой цели используется только часть возможных последовательностей каналаА к . Под действием помех входные последовательности изменяются и переходят в выходные последовательности канала В к , вообще говоря, не совпадающие с переданными.

Получив одну из последовательностей В к на выходе канала, мы должны принять решение относительно переданной последовательности. Как это сделать? Разобьем множество В к на непересекающиеся подмножества S k так, чтобы каждой переданной последовательности соответствовало своё подмножество S k .. При этом выберем подмножества так, чтобы для каждой вход-

ной последовательности вероятность попадания в своё подмножество была больше, чем в остальные. Принимая последовательность на выходе, смотрим, к какому подмножеству она относится, и в соответствии с этим принимаем решение о переданной типичной последовательности.

Очевидно, что при этом велика вероятность правильно определить переданную последовательность, однако, возможны и ошибки. Ошибка возникает, если входная последовательность перейдет в несоответствующее ей множество S k (на рис. 19 показан этот случай). Передача будет всегда безошибочной, если удастся так выбрать входные последовательности канала

Рис. 19. Преобразование типичных последовательностей при передаче через канал с помехами.

Канал

и разбиение S k , что переходы в несоответствующие подмножества будут невозможны или, по крайней мере, будут иметь сколь угодно малую вероятность для большихТ . Возможна ли такая ситуация? Оказывается возможна.

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

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

Значение результатов Шеннона для задач передачи, хранения и поиска информации.

Теорема Шеннона и передача информации.

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

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

Для наглядного пояснения роли теоремы Шеннона прибегнем к следующему сравнению. Пусть имеется трубопровод для доставки от источника некоторого жидкого продукта. Технические возможности трубопровода определяются количеством жидкости, которое можно передать по нему в единицу времени. Производительность источника определим количеством чистого продукта, поступающего от него в единицу времени, а пропускную способность трубопровода – как максимально возможную скорость передачи чистого продукта, соответствующую условию, что от источника поступает чистый продукт без примесей. Аналогом канала с помехами может служить трубопровод с утечкой. Пропускная его способность будет меньше. Чем в трубопроводе без утечки, на величину утечки продукта за единицу времени. Можно теперь представить, какой эффект вызвало бы утверждение, что существует такой способ введения примеси («избыточности») в продукт, при котором, введя количество примеси, равное утечке в трубопроводе, можно по нему доставлять продукт без потерь со скоростью, отвечающей пропускной способности трубопровода с утечкой. Именно такой смысл имеет теорема Шеннона применительно к задаче передачи информации. Продолжая аналогию этого примера, можно сказать, что такой способ введения примеси требует наличия некоего «отстойника», в котором примесь будет отстаиваться в течении определенного времени перед подачей в трубопровод (в идеале – бесконечное время). После такого «отстоя» при движении жидкости по трубопроводув утечку будет уходить только примесь.

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

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

Возникает вопрос, при каких условиях возможно достоверное хранение информации, т.е. получение из ЗУ данных в том виде, в каком они были туда помещены.

Для ответа на этот вопрос в соответствии с шенноновским подходом необходимо перейти от технических характеристик к информационным:

Для запоминаемых данных определить среднюю энтропию записи;

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

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

Если рассмотреть применение идеального кодирования к задаче хранения информации, то станет ясно, что для этого потребуется ЗУ с потенциально бесконечным числом ячеек, чтобы разместить в нем типичные последовательности записей сколь угодно большой длины. В этом проявляется техническая нереализуемость идеального кодирования применительно к задаче хранения информации.

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

Практическая реализация помехоустойчивого хранения информации основана на методах помехоустойчивого кодирования. Перед помещением записей в ЗУ искусственно увеличивается их избыточность за счет введения дополнительных контрольных символов. После считывания записей из ЗУ производится обнаружение и коррекция ошибок.

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

Возникает вопрос, при каких условиях возможен достоверный поиск информации, т.е. получение на каждый запрос именно тех записей которые требуются.

В соответствии с шенноновским подходом перейдем к информационным характеристикам:

Для последовательностей аргументов поиска определим среднюю энтропию аргументов. Если на аргументы действуют ошибки, то необходимо учесть увеличение средней энтропии вследствие ошибок;

Для множества записей файла определим информационную емкость ключа – максимальное количество информации, которое может содержаться в ключе файла. Если ключи файла могут содержать случайные ошибки, то необходимо учесть уменьшение информационной емкости ключа вследствие ошибок.

Тогда для информационных показателей будет справедлива следующая формулировка теоремы Шеннона для задачи поиска информации:

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

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

Как упоминалось во второй главе, разработка технически реализуемых способов помехоустойчивого поиска в настоящее время находится в зачаточном состоянии своего развития. Имеющиеся здесь результаты существенно скромнее, чем, например, в помехоустойчивом кодировании, где создана обширная и глубокая математическая теория кодирования. В чем здесь дело? Почему бы не воспользоваться результатами теории кодирования для решения родственной задачи поиска.

Основная идея помехоустойчивого кодирования состоит в искусственном введении избыточности в сообщения по подачи их в канал с помехами. В большинстве задач поиска мы имеем дело с естественной избыточностью сообщений, на которую мы не можем активно воздействовать. Мы получаем уже искаженный аргумент поиска, например, невнятно произнесенную по телефону фамилию клиента, и можем рассчитывать только на естественную избыточность языка (естественная избыточность русского языка, как и большинства европейских языков, оставляет примерно 60 %).

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

Сжатие данных.

Закодированные сообщения передаются по каналам связи, хранятся в запоминающих устройствах, обрабатываются процессором. Объемы данных, циркулирующих в АСУ, велики, и поэтому в о многих случаях важно обеспечить такое кодирование данных, которое характеризуется минимальной длиной получающихся сообщений. Эта проблема сжатия данных. Решение её обеспечивает увеличение скорости передачи информации и уменьшение требуемой памяти запоминающих устройств. В конечном итоге это ведет к повышению эффективности системы обработки данных.

Существует два подхода (или два этапа) сжатия данных:

сжатие, основанное на анализе конкретной структуры и смыслового содержания данных;

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

4.1. Сжатие на основе смыслового содержания данных

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

Переход от естественных обозначений к более компактным. Значения многих конкретных данных кодируются в виде, удобном для чтения человеком. При этом они содержат обычно больше символов, чем это необходимо. Например, дата записывается в виде «26 января 1982 г.» или в самой краткой форме: «26.01.82». при этом многие кодовые комбинации, например «33.18.53» или «95.00.11», никогда не используются. Для сжатия таких данных день можно закодировать пятью разрядами, месяц – четырьмя, год – семью, т.е. вся дата займет не более двух байтов. Другой способ записи даты, предложенный еще в средние века состоит в том, чтобы записывать общее число дней, прошедших к настоящему времени с некоторой точки отсчета. При этом часто ограничиваются четырьмя последними цифрами этого представления. Например, 24 мая 1967 года записывается в виде 0000 и отсчет дней от этой даты требует, очевидно, два байта в упакованном десятичном формате.

Аналогичным образом могут быть сжаты номера изделий, уличные адреса и т.п.

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

Означает, что символ, кодируемый следующим байтом, нужно повторить

Эффективность такого метода определяется числом и размерами участков повторяющихся символов.

Кодирование часто используемых элементов. Некоторые данные, такие ка имена и фамилии, принадлежат множеству возможных значений очень большого размера. Однако в большинстве случаев используется лишь малая часть возможных значений (действует правило «90/10»-в девяноста процентах случаев используется 10 процентов возможных значений). Поэтому для сжатия данных можно определить множество наиболее часто используемых значений, экономно закодировать его элементы и использовать эти коды вместо обычного представления. В частности, имена людей можно кодировать одним байтом, что дает 256 возможных кодовых комбинаций. Если при этом использовать первый разряд как признак пола, то получится 128 женских и 128 мужских имен. Как обеспечить возможность записи имен, не входящих в закодированные? Для этого можно, например, условиться, что некоторая специальная кодовая комбинация длиной в один байт означает, что последующие байты содержат полное написание имени в обычном коде ДКОИ-8.

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

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

элемент данных совпадает с предыдущим;

элемент данных имеет следующее по порядку значение;

элемент совпадает с предыдущим кроме последнего символа;

элемент совпадает с предыдущим кроме двух (трех, четырех и т.д.) последних символов;

элемент длиной l байтов не имеет связи с предыдущим.

При использовании подобных контекстных символов закодированные данные содержат только отличия текущих элементов от предыдущих.

Реализация сжатия данных требует специальных или (и) программных затрат, а также затрат памяти на предварительное кодирование с целью сжатия данных и последующее декодирование для восстановления первоначальной формы данных. Это означает, что сжатие данных – не всегда целесообразное мероприятие. Например, в базах данных обычно сжимаются архивные файлы с невысокой частотой использования. Сжатие применяется также для сокращения размеров индексных таблиц, используемых для организации поиска информации в индексно-последовательных файлах.

1. При любой производительности источника сообщений, меньшей пропускной способности канала, существует способ кодирования, позволяющий передавать по каналу все сообщения, вырабатываемые источником.

2. Не существует способа кодирования, обеспечивающего передачу сообщений без их неограниченного накопления, если производительность источника сообщений больше пропускной способности канала.

Кодирование, о котором идет речь в этой формулировке, называется эффективным (безызбыточным) кодированием.

Пример эффективного кода

Множество сообщений – X = {x 1 , ... , x 8 }.

Энтропия множества сообщений – H (X ) = 2,76 бит.

Максимальная энтропия источника – H max = 3,00 бит.

Избыточность источника – R = (3,00– 2,76)/3 = 0,08 .

Среднее число символов на сообщение–l i p i = 2,84 .

Избыточность (остаточная) кода – R к = (3,00– 2,84)/3 =0,05 .

Основная теорема Шеннона о кодировании для канала с помехами

1. При любой производительности источника сообщений, меньшей, чем пропускная способность канала, существует такой способ кодирования, который позволяет обеспечить передачу всей информации, создаваемой источником, со сколь угодно малой вероятностью ошибки.

2. Не существует способа кодирования, позволяющего вести передачу информации со сколь угодно малой вероятностью ошибки, если производительность источника сообщений больше пропускной способности канала.

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

Пример помехоустойчивого кода

Основным практическим следствием теорем Шеннона является построение системы передачи данных с использованием двух ступеней кодирования‑декодирования: для устранения избыточности источника и для повышения помехоустойчивости, как это показано на Error: Reference source not found.

9.Эксперимент по нахождению модели объекта.

До сих пор рассматривалась теория кодирования; теперь приступим к рассмотрению теории информации. Теория кодирования отвечает на следующие вопросы: 1) как построить коды для белого шума (основной вопрос)? 2) как сжать сообщение, когда известна его вероятностная структура?

Займемся общим методом описания структуры источника. Для этого понадобится понятие энтропии. Хотя энтропия давно использовалась во многих физических задачах, и ее понятие в теории информации сильно напоминает классическое определение, тем не менее в теории информации энтропия изучается сама по себе без обращения к многочисленным аналогиям. Для нас энтропия будет просто функцией распределения вероятностей Некоторые аналогии приведены в .

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

Результат, который является целью изучения, - это основная теорема Шеннона из гл. 10, связывающая пропускную способность канала С (более точно будет определена далее) и максимально возможную скорость передачи сигналов. Доказывается замечательная теорема, утверждающая, что можно сколь угодно близко подойти к максимальной скорости передачи сигналов, достигая при этом сколь угодно низкого уровня ошибок. К сожалению, доказательство не является конструктивным, так что теория информации дает границы того, что можно достичь, и не говорит, как. этого достичь. Тем не менее, как уже упоминалось в разд. 1.2, эта теория весьма полезна.

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