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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Введение[править | править вики-текст]

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

Блок-схема системы связи

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

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


История[править | править вики-текст]

Рождение теории информации зачастую связывают с размещением в июле-октябре 1948 года Шенноном Клодом работы в журнале американской телефонной компании "Bell System" под названием "Математическая теория связи". Но стоит упомянуть, что также был внесён в формулировку и построение теории информации вклад и многими другими, выдающимися учёными. Сам Шеннон в начале своей статьи написал «Некоторые основные положения этой теории имеются в важных работах Найквиста и Хартли. В настоящее теория расширена тем, что включено некоторое число новых факторов, в частности, влияние шума в канале».

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

Базовые законы теории информации[править | править вики-текст]

Закон 1: на получение информации любая кибернетическая система тратит не меньше определённого минимального количества энергии.
Закон 2: количество информации, которую получает кибернетическая система в процессе распознавания после приёма определённого сигнала, равняется логарифму при основе m от количества вариантов выбора, которые могли быть распознаны.
Закон 3: любая информация, полученная кибернетической системой, влияет на эту систему.

Свойства информации[править | править вики-текст]

  1. Релевантность — способность информации соответствовать нуждам (запросам) потребителя (неспособность информации быть полезной называют нерелевантностью).
  2. Полнота — свойство информации исчерпывающе (для данного потребителя) характеризовать отображаемый объект и/или процесс.
  3. Своевременность — способность информации соответствовать нуждам потребителя в нужный момент времени.
  4. Достоверность — свойство информации не иметь скрытых ошибок.
  5. Доступность — свойство информации, характеризующее воз­можность ее получения данным потребителем.
  6. Защищенность — свойство, характеризующее невозможность несанкционированного использования или изменения.
  7. Эргономичность — свойство, характеризующее удобство формы или объема информации с точки зрения данного потребителя.
  8. Адекватность — свойство информации однозначно соответствовать отображаемому объекту или явлению. Адекватность оказывается для потребителя внутренним свойством информации, проявляющем себя через релевантность и достоверность.

Также свойства информации можно определить по её потреблению: политическую, химическую, биологическую, техническую, экономическую и т. д. Информация ещё имеет внутренние свойства - внутренняя организация (структура) информации и её объём (количество). Структура информации выделяет отдельные её элементы, которые могут быть и простыми и сложными. Простые элементы не поддаются дальнейшему расчленению; сложные образуются как сочетание различных элементов и представляются информационными совокупностями. Структура информации достаточно сложна и может включать различные комбинации информационных совокупностей, обладающих определённым содержанием. А количество же информации является мерой уменьшения неопределенности знания при получении информационных сообщений. За единицу количества информации принимается бит. Это количество информации, при котором неопределенность - количество вариантов выбора, уменьшается вдвое (это ответ на вопрос, требующий односложный ответ – да или нет). Количество информации равновероятных событий определяется формулой Хартли, в ней процесс получения информации рассматривается как выбор одного сообщения из наперёд заданного множества равновероятных сообщений:

I=log_2N

Где  I - количество информации, а  N - возможное множество сообщений. Логарифм по основанию 2 ввиду того, что подсчёт информации требуется в основном в компьютерной технике, где информация хранится в двоичной системе счисления. Формула определения количества информации, учитывая возможную неодинаковую вероятность событий, названа в честь её открывателя - Шеннона:

I = -\sum_{n} p_n log_2 p_n

Где p_n - вероятность того, что именно n-е сообщение верно. Условно методы обнаружения количества информации можно разделить на пять видов:

  • энтропийный;
  • алгоритмический;
  • комбинаторный;
  • семантический;
  • прагматический.

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

Кодирование информации[править | править вики-текст]

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

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

2.Кодирование информации при её передаче по каналу с шумом. Этот метод учитывает и защищает информацию от помех в канале связи. Код является однозначно декодируемым, если любая последовательность символов из алфавита кода (а, в основном, это 0 и 1) кода разбивается на отдельные слова. Если ни одно кодовое слово не является началом другого, код называется префиксным и он является однозначно декодируемым. Следовательно, префиксность - достаточное, но не необходимое условие однозначной декодируемости. Требование префиксности ограничивает множество длин кодовых слов и не даёт возможности выбирать кодовые слова слишком короткими. Необходимым и достаточным условием существования префиксного кода объёма M с длинами кодовых слов l_1,...,l_M является выполнение неравенства Крафта:

\sum_{i=1}^{M} {2}^{-l_i}\leqslant{1}

Также требуется рассмотреть код Шеннона-Фано - алгоритм префиксного неоднородного кодирования. Этот метод кодирования использует избыточность сообщения, заключённую в неоднородном распределении частот символов его алфавита, то есть заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов — более длинными двоичными последовательностями. Рассмотрим источник, выбирающий буквы из множества  X=M с вероятностями p_M. Считаем, что буквы упорядочены по убыванию вероятностей ({p_1}\geqslant {p_2}\geqslant {p_M}). Кодовым словом кода Шеннона для сообщения с номером  M является двоичная последовательность, представляющая собой первые  l=-\log {p_m} разрядов после запятой в двоичной записи числа q_M:

 {q_M}=\sum_{i=1}^{M-1} p_i

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

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

5.Секретная связь, системы защиты информации от несанкционированного доступа. Этот тип активно используются и является актуальным. Затрагивает теорию информации, теории вычислительной мощности алгоритмов, исследования операций, теории чисел.

Информационная энтропия[править | править вики-текст]

Информационная энтропия( H ) - мера хаотичности информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения. Энтропия является количеством, определённым в контексте вероятностной модели для источника данных. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для её зашифровки без потери информации, при оптимальном кодировании. Энтропия ограничивает максимально возможное сжатие без потерь, которое может быть реализовано при использовании теоретически - типичного набора или, на практике кодирование Хаффмана, кодирования Лемпеля-Зива-Велча или арифметического кодирования. Свойства энтропии:
1.Энтропия не может быть отрицательной  H(X)\geqslant 0 ;
2.Энтропия ограничена  H(X)\leqslant \log_2 |X| (если все элементы X равновероятны;
3.Если  X,Y независимы, то  H(XY)=H(X)+H(Y) ;
4.Если  X,Y имеют одинаковое распределение вероятностей элементов, то  H(X)=H(Y) ;
5.Некоторые биты данных могут не нести информации;
6.Количество энтропии не всегда выражается целым числом бит.

Определение с помощью собственной информации[править | править вики-текст]

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

 {H(X)}={E(I(X))}=-\sum_{i=1}^{n} {p(i)} {\log {p(i)}}

Средняя энтропия сообщения[править | править вики-текст]

Информационная энтропия для независимых случайных событий  X с  n возможными состояниями (от  1 до  n ) рассчитывается по формуле:

 {H(X)}=-\sum_{i=1}^{n} {p(i)} \log_2 {p(i)}

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

Частичная энтропия[править | править вики-текст]

Величина  \log_2 {\frac{1}{p(i)}} называется частичной энтропией, характеризующей только i-е значение.

Формула Шеннона[править | править вики-текст]

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

 -K\sum_{i=1}^{n} {p(i)} \log_2 {p(i)}

где  K - константа, которая нужна для выбора единиц измерения.

Альтернативное определение[править | править вики-текст]

Другим способом определения энтропии  H является доказательство, что  H однозначно определена, если  H удовлетворяет условиям:
1.  H(p_1,...,p_n) определена и непрерывна для всех  p_1,...,p_n , где  {p_i}\in {[{0},{1}]} для всех  i=1,...,n и  p_1+...+p_n=1 .
2.Для целых положительных  n , должно выполнятся неравенство:

 H=\left(\frac{1}{n},...,\frac{1}{n}\right)<\left(\frac{1}{n+1},...,\frac{1}{n+1}\right)

3.Для целых положительных  b_i где  b_1+...+b_k=n , должно выполняться неравенство:

 H=\left(\frac{1}{n},...,\frac{1}{n}\right)=H\left(\frac{b_1}{n},...,\frac{b_k}{n}\right)+\sum_{i=1}^{k} {\frac{b_i}{n}}H\left({\frac{1}{b_i}},...,{\frac{1}{b_i}}\right)

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]