Теория информации

Введение в теорию информации.

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

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

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

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

Общие сведения.

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

Отображение множества состояний источника в множество состояний носителя называется способом кодирования, а образ состояния при выбранном способе кодирования - кодом этого состояния.

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

2.Обмен информацией предполагает использование некоторой системы знаков, например, естественного или искусственного (формального) языка. Учитывая определенную взаимосвязь проблем передачи информации с уровнями изучения знаковых систем, их разделяют на проблемы синтаксического, семантического и прагматического уровней.

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

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

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

3.Различают следующие аспекты теории информации.

- информационная метрология,

- сигналы и отсчеты информация,

- кодирование и декодирование,

- модуляция и демодуляция.

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

4.Основные свойства информации.

1).Информация существует только в случайных объектах.

2).Количество информации зависит от неожиданности изменения процесса или сигнала.

3).Количество информации измеряется положительным числом.

4).Информация об объекте А относительно объекта В равна информации в объекте В относительно объекта А.

5).Информация в объекте А относительно объекта В не зависит от объекта С, если объекты В и С не влияют друг на друга.

5. Теория информации как самостоятельная научная дисциплина, связанная с восприятием. передачей и переработкой, хранением и использованием информации, была основана американским ученым К.Шенноном в конце 40-х гг. 20-го века. Предложенная Шенноном теория (в 1948 г. выпущена в свет монография "Математическая теория связи") основывалась на фундаментальном понятии количественной меры неопределенности - энтропии - и связанного с нею понятия - количества информации. Другим фактором в становлении теории информации стало осознание того, что носитель информации сигнал - имеет случайную природу. При вероятностном подходе информация рассматривается как сообщение об исходе случайных событий, реализации случайных величин и функций, а количество информации ставится в зависимость от априорных вероятностей этих событий, величин, функций. Чтобы измерить количество информации, исходя из понятия неопределенности человек ставит себя на место приемника действительной или возможной информации.

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

6. На основе понятий энтропии и количества информации в теории информации введены важные характеристики сигналов и информационных систем. Вот основные из них:

- скорость создания информации - энтропия источника(H),отнесенная к единице времени;

- скорость передачи информации R - количество информации, передаваемое по каналу связи в единицу времени (например, для речи в обычном темпе - около 20 бит/с).

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

- пропускная способность канала связи C – максимальная скорость передачи информации: C = max R, где максимум отыскивается среди всех мыслимых приемно-передающих систем, связанных данным каналом. К.Шеннон рассматривал разные способы кодирования при фиксированных мощностях сигналов и шумов. Экспериментально установлено, что пропускная способность зрения и слуха человека около 5 бит/с.

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

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

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

Во всех остальных случаях полностью избавиться от действия помех невозможно. В частности, при передаче сигналов ДА-НЕТ (0 или 1) вероятность ошибки, то есть отношение искаженных посылок к их общему числу, определяется только отношением энергии сигнала к энергии помех при данном способе их передачи.

Какой же способ передачи этих широко применяемых сигналов дает самую лучшую защиту от помех? На этот вопрос дает ответ алгоритм работы "идеального приемника". Если ДА передается сигналом A(t), а НЕТ - сигналом B(t), то энергии этих сигналов должны быть равны, а по своей форме они должны быть противоположны, то есть A(t) + B(t) = 0. Это разнополярные сигналы, сигналы фазовой манипуляции со сдвигом на 180 градусов.

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

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

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

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

8. Для определения максимальной скорости передачи в идеальной системе связи со сколь угодно малой вероятностью ошибки К.Шеннон и получил достаточно простую формулу.

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

C = /\f * log(1 + P /P ) .

Величину С называют емкостью или пропускной способностью системы связи. Если скорость передачи идеальными сигналами J меньше или равна С, то есть J < C , то в идеальной системе связи можно осуществить передачу без ошибок.

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

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

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

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

10. А.Н.Колмогоров отмечал, что "строгое математическое обоснование своих идей в сколько-нибудь трудных случаях К.Шеннон представил своим продолжателям". Были нужны работы математического уровня, закладывающие математический фундамент теории информации. Эта задача была выполнена трудами следующих ученых: А.Я.Хинчина, И.М.Гельфанда, А.Н.Колмогорова, А.М.Яглома. Первые пионерские работы А.Я.Хинчина были посвящены доказательствам основных теорем теории информации для дискретного случая. В последующих работах И.М.Гельфанда, А.Н.Колмогорова, А.М.Яглома был рассмотрен более общий случай непрерывных систем, лишь слегка затронутый в первоначальных работах Шеннона. Впервые установленые в них общие свойства количества информации, явные формулы для информационных характеристик в гауссовском случае, формулировки теорем кодирования для воспроизведения сообщений с заданной точностью остались незыблемыми до настоящего дня.

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

При алгоритмическом подходе учитываются не только все вероятностные закономерности, но и другие (если они есть); если других закономерностей нет, то алгоритмический подход приводит к тем же результатам, что и вероятностный. Алгоритмический подход основан на применении теории алгоритмов для определения понятия энтропии, или сложности, конечного объекта и понятия информации в одном ко нечном объекте о другом. С помощью теории алгоритмов можно определить сложность описания различных объектов. Так, по А.Н.Колмогорову "относительной сложностью" объекта y при заданном x считается минимальная длина l(p) "программы" p получения y из x. Сформулированное так определение зависит от "метода программирования". Метод программирования есть не что иное, как функция ф(р,x) = y ставящая в соответствие программе p и объекту x объект y.

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