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

Теория, имеющая дело с информацией

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

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

. фундаментальные темы теории информации включают сжатие данных без потерь (например, ZIP-файлы ), сжатие данных с потерями (например, MP3 и JPEG ) и канальное кодирование (например, для DSL ). Теория информации используется в поиске информации, сборе разведданных, азартных играх и даже в музыкальной композиции.

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

Содержание

• 1 Обзор
• 2 Историческая справка
• 3 Количество информации
  • 3.1 Энтропия источника информации
  • 3.2 Совместная энтропия
  • 3.3 Условная энтропия (двусмысленность)
  • 3.4 Взаимная информация (трансинформация)
  • 3.5 Расхождение Кульбака – Лейблера (информация усиление)
  • 3.6 Другие величины
• 4 Теория кодирования
  • 4.1 Теория источников
    • 4.1.1 Скорость
  • 4.2 Пропускная способность канала
    • 4.2.1 Пропускная способность конкретных моделей каналов
• 5 Приложения для другие области
  • 5.1 Использование разведки и секретные приложения
  • 5.2 Генерация псевдослучайных чисел
  • 5.3 Сейсморазведка
  • 5.4 Семиотика
  • 5.5 Разные приложения
• 6 См. также
  • 6.1 Приложения
  • 6.2 История
  • 6.3 Теория
  • 6.4 Концепции
• 7 Ссылки
  • 7.1 Классический труд
  • 7.2 Другие журнальные статьи
  • 7.3 Учебники по информации теория
  • 7.4 Другие книги
  • 7.5 MOOC по теории информации
• 8 Внешние ссылки

Обзор

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

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

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

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

Историческая справка

Знаменательным событием, которое установило дисциплину теории информации и сразу привлекло к ней внимание всего мира, была публикация классической статьи Клода Э. Шеннона «Математическая теория коммуникации» в Bell System Technical Journal в июле и октябре 1948 года.

До этой статьи в Bell Labs были разработаны ограниченные теоретико-информационные идеи, все неявно предполагавшие события равная вероятность. Статья Гарри Найквиста 1924 года «Определенные факторы, влияющие на скорость телеграфа» содержит теоретический раздел, в котором количественно оцениваются «интеллект» и «скорость линии», с которой он может передаваться системой связи, что дает соотношение W = K log m (вспоминая постоянную Больцмана ), где W - скорость передачи информации, m - количество различных уровней напряжения, которые можно выбрать на каждом временном шаге, а K - постоянная величина. В статье Ральфа Хартли 1928 года «Передача информации» словесная информация используется как измеримая величина, отражающая способность получателя отличить одну последовательность символов от любой другой, таким образом количественно оценивая информацию как H = log S = n log S, где S - количество возможных символов, а n - количество символов в передаче. Таким образом, единицей информации была десятичная цифра, которую с тех пор иногда называли Хартли в его честь как единицей, шкалой или мерой информации. Алан Тьюринг в 1940 году использовал аналогичные идеи в рамках статистического анализа взлома немецких шифров Enigma Второй мировой войны.

Большая часть математики, лежащей в основе теории информации с событиями разной вероятности, была разработана для области термодинамики Людвигом Больцманном и Дж. Уиллард Гиббс. Связь между теоретико-информационной энтропией и термодинамической энтропией, включая важный вклад Рольфа Ландауэра в 1960-х годах, исследуется в Энтропия в термодинамике и теории информации.

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

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

Вместе с ней пришли идеи

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

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

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

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

В дальнейшем выражение вида p log p считается по соглашению равным нулю всякий раз, когда p = 0. Это оправдано, поскольку $lim\; p\; \to \; 0\; +\; p\; log\; \; p\; =\; 0\; \{\backslash \; displaystyle\; \backslash \; lim\; \_\; \{p\; \backslash \; rightarrow\; 0+\}\; p\; \backslash \; log\; p\; =\; 0\}$для любого логарифмического основания.

Энтропия источника информации

На основе функции массы каждого символа источника, подлежащего передаче, энтропия Шеннона H, в единицах бит (на символ), задается выражением

$H\; =\; -\; \sum \; ipi\; log\; 2\; \; (pi)\; \{\backslash \; displaystyle\; H\; =\; -\; \backslash \; sum\; \_\; \{i\}\; p\_\; \{i\}\; \backslash \; log\; \_\; \{2\}\; (p\_\; \{i\; \})\}$

где p i - вероятность появления i-го возможного значения исходного символа. Это уравнение дает энтропию в единицах «биты» (на символ), потому что в нем используется логарифм по основанию 2, и эта мера энтропии по основанию 2 иногда называлась шенноном в его честь. Энтропия также обычно вычисляется с использованием натурального логарифма (основание e, где e - число Эйлера), который дает измерение энтропии в натсах на символ и иногда упрощает анализ, избегая необходимости включать дополнительные константы в формулы. Возможны и другие основания, но они используются реже. Например, логарифм по основанию 2 = 256 даст результат измерения в байтах на символ, а логарифм с основанием 10 даст измерение в десятичных цифрах (или хартлей ) на символ..

Интуитивно энтропия H X дискретной случайной величины X является мерой степени неопределенности, связанной со значением X, когда известно только его распределение.

Энтропия источника, который испускает последовательность из N символов, которые независимы и одинаково распределены (iid), составляет N ⋅ H бит (на сообщение из N символов). Если символы исходных данных одинаково распределены, но не независимы, энтропия сообщения длины N будет меньше N ⋅ H.

Энтропия испытания Бернулли как функция вероятности успеха, часто называется двоичной функцией энтропии, H b (p). Энтропия максимизируется на уровне 1 бита на испытание, когда два возможных результата равновероятны, как при несмещенном подбрасывании монеты.

Если передается 1000 бит (0 и 1), и значение каждого из этих битов известно приемник (имеет определенное значение с уверенностью) перед передачей, ясно, что информация не передается. Однако, если каждый бит независимо равновероятен равным 0 или 1, то было передано 1000 шаннонов информации (чаще называемых битами). Между этими двумя крайностями информацию можно количественно определить следующим образом. Если 𝕏 - это набор всех сообщений {x 1,..., x n }, которые может быть X, а p (x) - вероятность некоторого $x\; \in \; X\; \{\backslash \; displaystyle\; x\; \backslash \; in\; \backslash \; mathbb\; \{X\}\}$, тогда определяется энтропия H, X:

$H\; (X)\; =\; EX\; [I\; (x)]\; =\; -\; \sum \; x\; \in \; X\; p\; (x)\; log\; \; p\; (x).\; \{\backslash \; Displaystyle\; H\; (X)\; =\; \backslash \; mathbb\; \{E\}\; \_\; \{X\}\; [I\; (x)]\; =\; -\; \backslash \; sum\; \_\; \{x\; \backslash \; in\; \backslash \; mathbb\; \{X\}\}\; p\; (x)\; \backslash \; log\; p\; (x).\}$

(Здесь I (x) - это самоинформация, которая представляет собой энтропийный вклад отдельного сообщения, а 𝔼 X - ожидаемое значение.) Свойство энтропии состоит в том, что она максимизируется, когда все сообщения в пространстве сообщений равновероятны p (x) = 1 / n; то есть наиболее непредсказуемо, и в этом случае H (X) = log n.

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

$H\; b\; (p)\; =\; -\; p\; журнал\; 2\; \; p\; -\; (1\; -\; p)\; журнал\; 2\; \; (1\; -\; p).\; \{\backslash \; displaystyle\; H\; \_\; \{\backslash \; mathrm\; \{b\}\}\; (p)\; =\; -\; p\; \backslash \; log\; \_\; \{2\}\; p-\; (1-p)\; \backslash \; log\; \_\; \{2\}\; (1-p).\}$

Совместная энтропия

совместная энтропия двух дискретных случайных величин X и Y - это просто энтропия их спаривания: (X, Y). Это означает, что если X и Y независимы, то их совместная энтропия является суммой их индивидуальных энтропий.

Например, если (X, Y) представляет положение шахматной фигуры - X строка и Y столбец, то совместная энтропия строки и столбца фигуры будет энтропия положения фигуры.

$ЧАС\; (X,\; Y)\; =\; EX,\; Y\; [-\; журнал\; \; p\; (x,\; y)]\; =\; -\; \sum \; x,\; yp\; (x,\; y)\; журнал\; \; p\; (x,\; y)\; \{\backslash \; displaystyle\; H\; (X,\; Y)\; =\; \backslash \; mathbb\; \{E\}\; \_\; \{X,\; Y\}\; [-\; \backslash \; log\; p\; (x,\; y)]\; =\; -\; \backslash \; sum\; \_\; \{x,\; y\}\; p\; (x,\; y)\; \backslash \; log\; p\; (x,\; y)\; \backslash ,\}$

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

Условная энтропия (двусмысленность)

условная энтропия или условная неопределенность X, заданная случайная величина Y (также называемая двусмысленностью X относительно Y) - это средняя условная энтропия по Y:

$H\; (X\; |\; Y)\; =\; EY\; [H\; (X\; |\; y)]\; =\; -\; \sum \; y\; \in \; Y\; p\; (y)\; \sum \; x\; \in \; X\; p\; (x\; |\; y)\; log\; \; p\; (x\; |\; y)\; =\; -\; \sum \; x,\; yp\; (x,\; y)\; log\; \; p\; (x\; |\; y).\; \{\backslash \; Displaystyle\; H\; (X\; |\; Y)\; =\; \backslash \; mathbb\; \{E\}\; \_\; \{Y\}\; [H\; (X\; |\; y)]\; =\; -\; \backslash \; sum\; \_\; \{y\; \backslash \; in\; Y\}\; p\; (y)\; \backslash \; sum\; \_\; \{x\; \backslash \; in\; X\; \}\; p\; (x\; |\; y)\; \backslash \; log\; p\; (x\; |\; y)\; =\; -\; \backslash \; sum\; \_\; \{x,\; y\}\; p\; (x,\; y)\; \backslash \; log\; p\; (x\; |\; y).\}$

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

$H\; (X\; |\; Y)\; =\; H\; (X,\; Y)\; -\; H\; (Y).\; \{\backslash \; displaystyle\; H\; (X\; |\; Y)\; =\; H\; (X,\; Y)\; -H\; (Y).\; \backslash ,\}$

Взаимная информация (преобразование)

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

$I\; (X;\; Y)\; =\; EX,\; Y\; [SI\; (x,\; y)]\; =\; \sum \; x,\; yp\; (x,\; y)\; log\; \; p\; (x,\; y))\; п\; (Икс)\; п\; (Y)\; \{\backslash \; Displaystyle\; I\; (X;\; Y)\; =\; \backslash \; mathbb\; \{E\}\; \_\; \{X,\; Y\}\; [SI\; (x,\; y)]\; =\; \backslash \; sum\; \_\; \{x,\; y\}\; p\; (x,\; y)\; \backslash \; log\; \{\backslash \; frac\; \{p\; (x,\; y)\}\; \{p\; (x)\; \backslash ,\; p\; (y)\}\}\}$

где SI (конкретная взаимная информация) - точечная взаимная информация.

Основным свойством взаимной информации является то, что

$I\; (X;\; Y)\; =\; H\; (X)\; -\; H\; (X\; |\; Y).\; \{\backslash \; displaystyle\; I\; (X;\; Y)\; =\; H\; (X)\; -H\; (X\; |\; Y).\; \backslash ,\}$

То есть, зная Y, мы можем сохранить в среднем I (X; Y) бит при кодировании X по сравнению с незнанием Y.

Взаимная информация симметрична :

$I\; (X;\; Y)\; =\; I\; (Y;\; X)\; =\; H\; (X)\; +\; H\; (Y)\; -\; H\; (X,\; Y).\; \{\backslash \; displaystyle\; I\; (X;\; Y)\; =\; I\; (Y;\; X)\; =\; H\; (X)\; +\; H\; (Y)\; -H\; (X,\; Y).\; \backslash ,\}$

Взаимная информация может быть выражена как среднее значение Kullback– Дивергенция Лейблера (получение информации) между апостериорным распределением вероятностей X при значении Y и априорным распределением на X:

$I\; (X;\; Y)\; =\; E\; p\; (\; y)\; [DKL\; (p\; (X\; |\; Y\; =\; y)\; \Vert \; p\; (X))].\; \{\backslash \; Displaystyle\; I\; (X;\; Y)\; =\; \backslash \; mathbb\; \{E\}\; \_\; \{p\; (y)\}\; [D\; \_\; \{\backslash \; mathrm\; \{KL\}\}\; (p\; (X\; |\; Y\; =\; y)\; \backslash \; |\; p\; (X))].\}$

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

$I\; (X;\; Y)\; =\; DKL\; (p\; (X,\; Y)\; \Vert \; p\; (X)\; p\; (Y)).\; \{\backslash \; displaystyle\; I\; (X;\; Y)\; =\; D\; \_\; \{\backslash \; mathrm\; \{KL\}\}\; (p\; (X,\; Y)\; \backslash \; |\; p\; (X)\; p\; (Y)).\}$

Взаимная информация тесно связана с тест отношения логарифмического правдоподобия в контексте таблиц сопряженности и полиномиального распределения и критерия χ Пирсона : взаимная информация может рассматриваться как статистика для оценки независимости пары переменных и имеет строго заданное асимптотическое распределение.

Дивергенция Кульбака – Лейблера (получение информации)

Дивергенция Кульбака – Лейблера (или расхождение информации, получение информации или относительная энтропия) - это способ сравнения двух распределений : «истинное» распределение вероятностей p (X) и произвольное распределение вероятностей q (X). Если мы сжимаем данные таким образом, который предполагает, что q (X) является распределением, лежащим в основе некоторых данных, когда на самом деле p (X) является правильным распределением, расхождение Кульбака-Лейблера - это количество средних дополнительных битов на данные, необходимые для сжатие. Таким образом, он определен

$DKL\; (p\; (X)\; \Vert \; q\; (X))\; =\; \sum \; x\; \in \; X\; -\; p\; (x)\; log\; \; q\; (x)\; -\; \sum \; x\; \in \; X\; -\; p\; (x)\; log\; \; p\; (x)\; =\; \sum \; x\; \in \; X\; p\; (x)\; log\; \; p\; (x)\; q\; (x).\; \{\backslash \; Displaystyle\; D\; \_\; \{\backslash \; mathrm\; \{KL\}\}\; (p\; (X)\; \backslash \; |\; q\; (X))\; =\; \backslash \; sum\; \_\; \{x\; \backslash \; in\; X\}\; -p\; (x)\; \backslash \; log\; \{q\; (x)\}\; \backslash ,\; -\; \backslash ,\; \backslash \; sum\; \_\; \{x\; \backslash \; in\; X\}\; -p\; (x)\; \backslash \; log\; \{p\; (x)\}\; =\; \backslash \; sum\; \_\; \{x\; \backslash \; in\; X\}\; p\; (x)\; \backslash \; log\; \{\backslash \; frac\; \{p\; (x)\}\; \{q\; (x)\}\}.\}$

Хотя это иногда используется как «метрика расстояния», расхождение KL не является истинной метрикой, поскольку она не симметрична и не удовлетворяет неравенству треугольника (что делает его полуквазиметрическим).

Другая интерпретация расхождения KL - это «ненужный сюрприз», внесенный априорном из истины: предположим, что число X собирается случайным образом вытянуть из дискретного набора с распределением вероятностей p (x). Если Алиса знает истинное распределение p (x), в то время как Боб полагает (имеет предшествующее ), что распределение равно q (x), то Боб будет более удивлен, чем Алиса, на среднее значение, увидев значение X. Дивергенция KL - это (объективное) ожидаемое значение (субъективной) неожиданности Боба за вычетом неожиданности Алисы, измеренное в битах, если журнал ведется по основанию 2. Таким образом, степень, в которой предварительная оценка Боба "неправильно" можно количественно оценить с точки зрения того, насколько "излишне удивлен", как ожидается, он его сделает.

Другие величины

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

теория кодирования

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

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

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

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

Теория источников

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

Скорость

Информация скорость - это средняя энтропия на символ. Для источников без памяти это просто энтропия каждого символа, тогда как в случае стационарного случайного процесса это

$r\; =\; lim\; n\; \to \; \infty \; H\; (X\; n\; |\; X\; n\; -\; 1,\; X\; n\; -\; 2,\; X\; n\; -\; 3,\dots );\; \{\backslash \; displaystyle\; r\; =\; \backslash \; lim\; \_\; \{n\; \backslash \; to\; \backslash \; infty\}\; H\; (X\_\; \{n\}\; |\; X\_\; \{n-1\},\; X\_\; \{n-2\},\; X\_\; \{n-3\},\; \backslash \; ldots);\}$

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

$r\; =\; lim\; n\; \to \; \infty \; 1\; n\; H\; (X\; 1,\; X\; 2,\dots \; X\; n);\; \{\backslash \; displaystyle\; r\; =\; \backslash \; lim\; \_\; \{n\; \backslash \; to\; \backslash \; infty\}\; \{\backslash \; frac\; \{1\}\; \{n\}\}\; H\; (X\_\; \{1\},\; X\_\; \{2\},\; \backslash \; dots\; X\_\; \{n\});\}$

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

В теории информации принято говорить о «скорости» или «энтропии» языка. Это уместно, например, когда источником информации является английская проза. Скорость источника информации зависит от его избыточности и того, насколько хорошо он может быть сжат, что является предметом кодирования источника.

Пропускная способность канала

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

Рассмотрим процесс связи по дискретному каналу. Простая модель процесса показана ниже:

Здесь X представляет собой пространство переданных сообщений, а Y пространство сообщений, полученных за единицу времени по нашему каналу. Пусть p (y | x) будет функцией распределения условной вероятности Y для данного X. Мы будем рассматривать p (y | x) как неотъемлемое фиксированное свойство нашего канала связи (представляющее природу шум нашего канала). Тогда совместное распределение X и Y полностью определяется нашим каналом и нашим выбором f (x), предельным распределением сообщений, которые мы выбираем для отправки по каналу. При этих ограничениях мы хотели бы максимизировать скорость передачи информации или сигнала , с которым мы можем общаться по каналу. Подходящей мерой для этого является взаимная информация, и эта максимальная взаимная информация называется пропускной способностью канала и определяется выражением:

$C\; =\; max\; f\; I\; (X;\; Y).\; \{\backslash \; displaystyle\; C\; =\; \backslash \; max\; \_\; \{f\}\; I\; (X;\; Y).\; \backslash !\}$

Эта емкость имеет следующее свойство, связанное с передачей информации со скоростью R (где R обычно бит на символ). Для любой скорости передачи информации R < C and coding error ε>0, для достаточно большого N существует код длины N и скорости ≥ R и алгоритм декодирования, так что максимальная вероятность ошибки блока составляет ≤ ε; то есть всегда возможна передача с произвольно малой блочной ошибкой. Кроме того, при любой скорости R>C передача с произвольно малой ошибкой блока невозможна.

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

Пропускная способность конкретных моделей каналов

• Аналоговый канал связи с непрерывным временем, подверженный гауссовскому шуму - см. теорема Шеннона – Хартли.
• A двоичный симметричный канал ( BSC) с вероятностью кроссовера p представляет собой двоичный входной канал двоичного вывода, который переворачивает входной бит с вероятностью p. BSC имеет пропускную способность 1 - H b (p) бит на использование канала, где H b - это функция двоичной энтропии с логарифмом с основанием 2:

• A двоичное стирание канал (BEC) с вероятностью стирания p является двоичным входом, троичный выходной канал. Возможные выходы канала: 0, 1 и третий символ «e», называемый стиранием. Стирание представляет собой полную потерю информации о входном бите. Пропускная способность BEC составляет 1 - p бит на использование канала.

Приложения для других областей

Приложения для разведки и секретности

Концепции теории информации применимы к криптографии и криптоанализу. Информационная единица Тьюринга, запрет, использовалась в проекте Ultra, взломав немецкий код Enigma machine и ускорив окончание Второй мировой войны в Европа. Сам Шеннон определил важную концепцию, которая теперь называется расстоянием единственности. Основываясь на избыточности открытого текста, он пытается предоставить минимальный объем зашифрованного текста, необходимый для обеспечения уникальной дешифрируемости.

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

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

Генерация псевдослучайных чисел

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

Сейсморазведка

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

Семиотика

Семиотики Doede Nauta и Винфрид Нёт оба считали Чарльза Сандерса Пирса создателем теории информации в своих работах по семиотике. Наута определил семиотическую теорию информации как исследование «внутренних процессов кодирования, фильтрации и обработки информации».

Такие концепции теории информации, как избыточность и управление кодом, использовались семиотиками, такими как Умберто Эко и Ферруччо Росси-Ланди для объяснения идеологии как формы передачи сообщений, при которой доминирующий социальный класс излучает свое сообщение, используя знаки, которые демонстрируют высокую степень избыточности, так что только одно сообщение декодируется среди выбор конкурирующих.

Разные приложения

Теория информации также имеет приложения в азартных играх и теории информации, черных дырах и биоинформатика.

См. также

• Портал математики

• Алгоритмическая вероятность
• Байесовский вывод
• Теория коммуникации
• Теория конструкторов - обобщение теории информации, которое включает квантовую информацию
• Индуктивная вероятность
• Инфо-метрики
• Минимальная длина сообщения
• Minimum description length
• List of important publications
• Philosophy of information

Applications

• Active networking
• Cryptanalysis
• Cryptography
• Cybernetics
• Entropy in thermodynamics and information theory
• Gambling
• Intelligence (information gathering)
• Seismic exploration

History

• Hartley, R.V.L.
• History of information theory
• Shannon, C.E.
• Timeline of information theory
• Yockey, H.P.

Theory

• Coding theory
• Detection theory
• Estimation theory
• Fisher information
• Information algebra
• Information asymmetry
• Information field theory
• Information geometry
• Information theory and measure theory
• Kolmogorov complexity
• List of unsolved problems in information theory
• Logic of information
• Network coding
• Philosophy of information
• Quantum information science
• Source coding

Concepts

• Ban (unit)
• Channel capacity
• Communication channel
• Communication source
• Conditional entropy
• Covert channel
• Data compression
• Decoder
• Differential entropy
• Fungible information
• Information fluctuation complexity
• Information entropy
• Joint entropy
• Kullback–Leibler divergence
• Mutual information
• Pointwise mutual information (PMI)
• Receiver (information theory)
• Redundancy
• Rényi entropy
• Self-information
• Unicity distance
• Variety
• Hamming distance

References

The classic work

Other journal articles

Textbooks on information theory

Other books

MOOC on information theory

• Raymond W. Yeung, "Information Theory " (The Chinese University of Hong Kong )

External links

Wikiquote has quotations related to: Information theory

• , Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Lambert F. L. (1999), "Shuffled Cards, Messy Desks, and Disorderly Dorm Rooms - Examples of Entropy Increase? Nonsense! ", Journal of Chemical Education
• IEEE Information Theory Society and ITSOC Monographs, Surveys, and Reviews