Понятия

• информационная энтропия и избыточность источника – Теорема Шеннона о кодировании источника
• взаимная информация, пропускная способность зашумлённого канала – Теорема Шеннона для канала с шумами
• теорема Шеннона-Хартли о предельной пропускной способности зашумлённого канала с гауссовским шумом
• количественная мера информации

Предпосылки

• Методы связи неявно использовали идеи теории информации.
• Например, азбука Морзе
• более распространённые буквы имеют более короткие коды.
• Кодирование информации – основная идея, при сжатии данных без потерь.

• Найквист, 1924: “Определённые факторы, влияющие на скорость телеграфа”
• технические аспекты телеграфных сигналов
• дана количественная оценка “сведений” и “линейной скорости”, с которой они могут передаваться:
• \[W=K\log m,\] где \(W\) - скорость передачи данных, \(m\) - количество различных уровней напряжения на выбор на каждом шаге, а \(K\) - постоянная.

• Хартли, 1928: “Передача информации”
• использовано слово “информация” (в техническом смысле)
• чётко указано, что информация является измеримой величиной
• отражает только способность получателя отличать одну последовательность символов от любой другой
• определено количество информации как \(H=\log S^{n},\) где S - количество возможных символов, а n - количество символов в передаче. Естественной единицей информации, таким образом, была десятичная цифра.
• Аналогичные единицы вероятности – Тьюринг, 1940 в рамках криптоанализа Enigma.

• в основе – идея равной априорной вероятности
• на практике – вероятность различная
• неравномерность вероятностей изучается в статистической механике

• Больцманн, 1872: H-теорема
• \[ H=-\sum f_{i}\log f_{i}\] мера широты распространения состояний, доступных для одной частицы в газе таких же частиц, где f – относительное распределение частот каждого возможного состояния.
• эффект столкновений между частицами неизбежно приведёт к увеличению Н-функции от любой начальной конфигурации до достижения равновесия
• H – в основе микроскопического обоснования макроскопической термодинамической энтропии Клаузиуса.

• Гиббс: общая формула статистико-механической энтропии,
• не требует идентичных не взаимодействующих частиц
• основана на вероятностном распределении \(p_i\) для всего микросостояния \(i\) общей системы:
• \[S=-k_{\text{B}}\sum p_{i}\ln p_{i}\]
• Гиббсовская энтропия – в прямом соответствии с классическим термодинамическим определением Клаузиуса.

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

• Различные формальные подходы к определению информации
• С точки зрения информатики, нас интересуют два определения.

Информация по Шеннону

Информация – это снятая неопределённость.

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

Величина неопределённости

количество возможных равновероятных исходов события

• игральный кубик имеет неопределённость 6.
• содержательным подход
• интуитивен, но не отвечает на вопрос “сколько информации получено”.

Количество информации по Колмогорову

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

• любой алфавит может быть закодирован в двоичном
• следовательно определение достаточно универсально
• алфавитный подход

• Основная единица – бит – от binary digit.
• При алфавитном подходе один бит – это количество информации, которое можно закодировать одним двоичным знаком (0 или 1)
• С точки зрения содержательного подхода, один бит – это количество информации, уменьшающее неопределённость вдвое.

• В вопросе хранения информации, основным показателем является не количество информации, а информационный объем

Информационный объем сообщения

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

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

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

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