Главная › Тарифы › Теоремы шеннона. Основная теорема шеннона о кодировании для канала без помех

Теоремы шеннона. Основная теорема шеннона о кодировании для канала без помех

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

Утверждение теоремы

Рассматривая все возможные многоуровневые и многофазные методы кодирования, теорема Шеннона - Хартли утверждает, что пропускная способность канала C {\displaystyle C} , означающая теоретическую верхнюю границу скорости передачи данных, которые можно передать с данной средней мощностью сигнала S {\displaystyle S} через аналоговый канал связи, подверженный аддитивному белому гауссовскому шуму мощности N {\displaystyle N} равна:

C = B log 2 ⁡ (1 + S N) , {\displaystyle C=B\log _{2}\left(1+{\frac {S}{N}}\right),} C {\displaystyle C} - пропускная способность канала, бит /с; B {\displaystyle B} - полоса пропускания канала, Гц ; S {\displaystyle S} - полная мощность сигнала над полосой пропускания, Вт или ²; N {\displaystyle N} - полная шумовая мощность над полосой пропускания, Вт или ²; S / N {\displaystyle S/N} - отношение мощности сигнала к шуму (SNR) .

История развития

В течение конца 1920-х гг. Гарри Найквист и Ральф Хартли разработали фундаментальные идеи, связанные с передачей информации, с помощью телеграфа как системы коммуникаций. В то время, это был прорыв, но науки как таковой не существовало. В 1940-х гг., Клод Шеннон ввёл понятие пропускной способности канала , которое базировалось на идеях Найквиста и Хартли, а затем сформулировал полную теорию передачи информации.

Критерий Найквиста

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

f p ⩽ 2 B , {\displaystyle f_{p}\leqslant 2B,}

где f p {\displaystyle f_{p}} - частота импульса (имп/с), и B {\displaystyle B} - полоса пропускания (Гц).

Формула Хартли

Теоремы Шеннона для канала с шумами

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

Если скорость передачи сообщений меньше пропускной способности канала связи

R < C , {\displaystyle R

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

R > C , {\displaystyle R>C,}

то кода, на основе которого можно добиться сколько угодной малой вероятности возникновения ошибки, не существует.

Теорема Шеннона - Хартли

В данной теореме определено, что достичь максимальной скорости (бит/с) можно путём увеличения полосы пропускания и мощности сигнала и, в то же время, уменьшения шума.

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

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

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

Это дополнение создает неуверенность относительно ценности оригинального сигнала. Если приёмник обладает информацией о вероятности ненужного сигнала, который создает шум, то можно восстановить информацию в оригинальном виде, рассматривая все возможные влияния шумового процесса. В случае теоремы Шеннона - Хартли шум, как таковой, произведен гауссовским процессом с некоторыми отклонениями в канале передачи. Такой канал называют совокупным белым гауссовским шумовым каналом , так как гауссовский шум является частью полезного сигнала. «Белый» подразумевает равное количество шума во всех частотах в пределах полосы пропускания канала. Такой шум может возникнуть при воздействии случайных источников энергии, а также быть связан с ошибками, возникшими при кодировании. Знание о вероятности возникновения гауссовского шума значительно упрощает определение полезного сигнала.

Значение теоремы

Пропускная способность канала и формула Хартли

Сравнивая пропускную способность канала и формулу Хартли, мы можем найти эффективное число M {\displaystyle M} различимых уровней:

2 B log 2 ⁡ M = B log 2 ⁡ (1 + S N) , {\displaystyle 2B\log _{2}M=B\log _{2}\left(1+{\frac {S}{N}}\right),} M = 1 + S N . {\displaystyle M={\sqrt {1+{\frac {S}{N}}}}.}

Взятие квадратного корня по сути возвращает отношение мощностей к отношению напряжений, таким образом число уровней приблизительно равно отношению среднеквадратичной амплитуды сигнала к шумовому стандартному отклонению. Это подобие в форме между пропускной способностью по Шеннону и формулой Хартли не стоит понимать буквально, что для безошибочной передачи достаточно M {\displaystyle M} уровней сигнала. Избыточное кодирование для устранения ошибок потребует большего числа уровней, но предельная скорость передачи данных, к которой можно приблизиться с кодированием, эквивалентна использованию того самого M {\displaystyle M} из формулы Хартли.

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

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

Пусть 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 байтов не имеет связи с предыдущим.

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

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

Передача информации

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

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

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

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

Используя понятие избыточности кода, можно дать более короткую формулировку теоремы:

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

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

Далее в основном ограничим себя ситуацией, когда M = 2 , т.е. для представления кодов в линии связи используется лишь два типа сигналов – с практической точки зрения это наиболее просто реализуемый вариант (например, существование напряжения в проводе (будем называть это импульсом) или его отсутствие (пауза); наличие или отсутствие отверстия на перфокарте или намагниченной области на дискете); подобное кодирование называется двоичным. Знаки двоичного алфавита принято обозначать "0" и "1", но нужно воспринимать их как буквы, а не цифры. Удобство двоичных кодов и в том, что при равных длительностях и вероятностях каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации (log 2 M = 1) ; тогда из (1), теоремы Шеннона:

I 1 (A) K (2)

и первая теорема Шеннона получает следующую интерпретацию:

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

Применение формулы (2) для двоичного кодирования дает:

Определение количества переданной информации при двоичном кодировании сводится к простому подсчету числа импульсов (единиц) и пауз (нулей). При этом возникает проблема выделения из потока сигналов (последовательности импульсов и пауз) отдельных кодов. Приемное устройство фиксирует интенсивность и длительность сигналов. Элементарные сигналы (0 и 1) могут иметь одинаковые или разные длительности. Их количество в коде (длина кодовой цепочки), который ставится в соответствие знаку первичного алфавита, также может быть одинаковым (в этом случае код называется равномерным) или разным (неравномерный код). Наконец, коды могут строиться для каждого знака исходного алфавита (алфавитное кодирование) или для их комбинаций (кодирование блоков, слов). В результате при кодировании (алфавитном и словесном) возможны следующие варианты сочетаний:

В случае использования неравномерного кодирования или сигналов разной длительности (ситуации (2), (3)) для отделения кода одного знака от другого между ними необходимо передавать специальный сигнал – временной разделитель (признак конца знака) или применять такие коды, которые оказываются уникальными, т.е. несовпадающими с частями других кодов. При равномерном кодировании одинаковыми по длительности сигналами (ситуация (1)) передачи специального разделителя не требуется, поскольку отделение одного кода от другого производится по общей длительности, которая для всех кодов оказывается одинаковой (или одинаковому числу бит при хранении).

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

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 (Х), т.е. среднее количество двоичных единиц информации, поступающее от источника в единицу времени (численно оно равно средней энтропии сообщения, производимого источником в единицу времени). Известна пропускная способность канала С 1 , т.е. максимальное количество информации, которое способен передать канал в ту же единицу времени. Возникает вопрос: какой должна быть пропускная способность канала, чтобы он справлялся со своей задачей, т.е. чтобы информация от источника к приёмнику поступала без задержки?

Несмотря на то, что ответ и так очевиден, он даётся в первой теореме Шеннона.

1-я теорема Шеннона:

Если пропускная способность канала связи С 1 больше энтропии источника информации в единицу времени

С 1 > Н 1 (Х),

то всегда можно закодировать достаточно длинное сообщение так, чтобы оно передавалось каналом связи без задержки.

Если же, напротив,

С 1 < Н 1 (Х),

то передача информации без задержек невозможна.

Передача информации с искажениями.

Пропускная способность канала с помехами.

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

Совершенно очевидно, что наличие помех приводит к потере информации. Чтобы в условиях наличия помех получить на приёмнике требуемый объём информации, необходимо принимать специальные меры. Одной из таких мер является введение так называемой «избыточности». Известно, что все живые языки обладают некоторой избыточностью, доходящей до 50% (т.е.50% букв мы могли бы вообще не произносить или перепутывать их местами:-)).

Вот пример: По рзелульаттам илссеовадний одонго анлигйсокго унвиертисета, не иеемт занчнеия, в кокам пряокде рсапожолены бкувы в солве. Галвоне, чотбы преавя и пслоендяя бквуы блыи на мсете. Осатьлыне бквуы мгоут селдовтаь в плоонм бсепордяке, всё-рвано ткест чтаитсея без побрелм.

Надеюсь, вы поняли, что здесь написано))))

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

Рассмотрим, например, такую задачу. Канал связи К передаёт от источника информации Х к приёмнику У элементарные символы 0 и 1 в количестве k символов в единицу времени. В процессе передачи каждый символ, независимо от других, с вероятностью μ может быть искажён (т.е. заменён противоположным). Требуется найти пропускную способность канала.

Определим сначала максимальную информацию на один символ, которую может передавать канал. Пусть источник производит символы 0 и 1 с вероятностями p и 1-p.

Тогда энтропия источника будет

Н(Х)=-p log p - (1-p) log (1-p).

Если бы передача сообщений не сопровождалась ошибками, то количество информации на один символ было бы равно самой энтропии системы Х. При наличии ошибок оно будет меньше:

I = H(Y) - H(Y/X).

Чтобы найти полную условную энтропию Н(У/Х), найдём сначала частные условные энтропии: Н(У/х 1) и Н(У/х 2).

Вычислим Н(У/х 1); для этого предположим, что передан символ 0. Найдём условные вероятности того, что при этом система У находится в состоянии у 1 =0 и в состоянии у 2 =1. Первая из них равна вероятности того, что сигнал не перепутан:

Р(у 1 /х 1)=1-µ;

вторая - вероятности того, что сигнал перепутан:

Р(у 2 /х 1)=µ.

Условная энтропия Н(У/х 1) будет:

Н(У/х 1)=-Σ Р(у i /x 1) log P(y i /x 1) = -(1-µ) log (1-µ) - µ log µ.

Найдём теперь условную энтропию системы У при условии, что передан сигнал 1:

Р(у 1 /х 2)=µ; Р(у 2 /х 2)=1-µ,

Н(У/х 2)= - µ log µ - (1-µ) log (1-µ).

Таким образом

Н(У/х 1)= Н(У/х 2).

Полная условная энтропия Н(У/Х) получится, если осреднить условные энтропии с учётом вероятностей р и 1-р. Так как частные условные энтропии равны, то

Н(У/Х)= - µ log µ - (1-µ) log (1-µ).

Вывод: условная энтропия Н(У/Х) совсем не зависит от того, с какими вероятностями встречаются символы 0 и 1 в передаваемом сообщении, а зависит только от вероятности ошибки µ.

Теперь вычислить информацию, передаваемую одним символом:

I = H(Y) - H(Y/X) = - r log r - (1-r) log (1-r) - - µ log µ - (1-µ) log (1-µ) =

= [η(r) + η(1-r)] - [η(µ) + η(1-µ)],

Где r - вероятность того, что на выходе появится символ 0.

Мы знаем, что энтропия и количество информации максимально при равновероятных сигналах, т.е. (в нашем случае) при р=1/2. Следовательно, максимальное количество информации, передаваемое одним символом

I max = 1 - [η(µ) + η(1-µ)],

А пропускная способность канала связи будет равна

С= k(1 - [η(µ) + η(1-µ)]).

Заметьте, что η(µ) + η(1-µ) - это энтропия системы, имеющей 2 возможных состояния с вероятностями µ и 1-µ. Она характеризует потерю информации на один символ, связанную с наличием помех.

Пример 1. Определить пропускную способность канала связи, способного передавать 100 символов 0 или 1 в единицу времени, причем каждый из символов искажается (заменяется противоположным) с вероятностью µ=0,001.

η(µ) = η(0,001) = 0,0664

η(1-µ) = 0,0144

η(µ) + η(1-µ) = 0,0808

На один символ теряется информация 0,0808 бит. Пропускная способность канала равна

С = 100(1-0808) = 91,92 ≈ 92 бит в единицу времени.

Зная пропускную способность канала, можно определить верхний предел скорости передачи информации по каналу с помехами. К этому случаю относится вторая теорема Шеннона.

2-я теорема Шеннона:

Пусть имеется источник информации Х, энтропия которого в единицу времени равна Н 2 (Х), и канал с пропускной способностью С 2 . Тогда, если

Н 2 (Х) >С 2 ,

То при любом кодировании передача сообщений без задержек и искажений невозможна. Если же

Н 2 (Х) < С 2 ,

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

Пример 2. Имеются источник информации с энтропией в единицу времени Н(Х) = 100 бит и 2 канала связи; каждый из них может передавать в единицу времени 70 двоичных знаков (0 или 1); каждый двоичный знак заменяется противоположным с вероятностью µ=0,1. Требуется выяснить: достаточна ли пропускная способность этих каналов для передачи информации, поставляемой источником?

Решение: Определяем потерю информации на один символ:

η(µ) + η(1-µ) = 0,332+0,137=0,469 бит

Максимальное количество информации, передаваемое по одному каналу в единицу времени:

С = 70(1-0,469) = 37,2 бит.

Максимальное количество информации, которое может быть передано по двум каналам в единицу времени:

37,2*2 = 74,7 бит,

чего недостаточно для обеспечения передачи информации от источника.

| 2 |