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

Научное исследование цифровой информации

Теория информации – это математическое исследование количественного определения , хранения и передачи информации . ^[1] Первоначально эта область была основана работами Гарри Найквиста и Ральфа Хартли в 1920-х годах и Клода Шеннона в 1940-х годах. ^{[2] : vii} Область прикладной математики находится на стыке теории вероятностей , статистики , информатики , статистической механики , информационной инженерии и электротехники .

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

Приложения фундаментальных тем теории информации включают исходное кодирование/ сжатие данных (например, для ZIP-файлов ) и канальное кодирование/ обнаружение и исправление ошибок (например, для DSL ). Его влияние имело решающее значение для успеха миссий «Вояджера» в глубокий космос, изобретения компакт-дисков , возможности мобильных телефонов и развития Интернета. Теория также нашла применение в других областях, включая статистический вывод , ^[3] криптографию , нейробиологию , ^[4] восприятие , ^[5] лингвистику, эволюцию ^[6] и функции ^[7] молекулярных кодов ( биоинформатика ), теплофизику. , ^[8] молекулярная динамика , ^[9] квантовые вычисления , черные дыры , поиск информации , сбор разведданных , обнаружение плагиата , ^[10] распознавание образов , обнаружение аномалий ^[11] и даже создание произведений искусства.

Обзор

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

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

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

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

Знаковым событием, заложившим дисциплину теории информации и привлекшим к ней немедленное внимание всего мира, стала публикация классической статьи Клода Э. Шеннона «Математическая теория связи» в техническом журнале Bell System в июле и октябре 1948 года. Он стал известен как «отец теории информации». ^{[12] [13] [14]}

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle H=-\sum _{i}p_{i}\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 ₁ , ..., x _n } , которыми может быть X , и p ( x ) - вероятность некоторого сообщения , то энтропия H X определяется: ^[15] ${\displaystyle \mathbb {X} }$ ${\displaystyle x\in \mathbb {X} }$

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

(Здесь I ( x ) — это самоинформация , которая представляет собой энтропийный вклад отдельного сообщения и является ожидаемым значением .) Свойством энтропии является то, что она максимизируется, когда все сообщения в пространстве сообщений равновероятны . ( Икс ) знак равно 1/ п ; т. е. наиболее непредсказуемо, и в этом случае H ( X ) = log n . ${\displaystyle \mathbb {E} _{X}}$

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

${\displaystyle H_{\mathrm {b} }(p)=-p\log _{2}p-(1-p)\log _{2}(1-p).}$

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

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

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

${\displaystyle H(X,Y)=\mathbb {E} _{X,Y}[-\log p(x,y)]=-\sum _{x,y}p(x,y)\log p(x,y)\,}$

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

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

Условная энтропия или условная неопределенность X с учетом случайной величины Y (также называемая двусмысленностью X относительно Y ) — это средняя условная энтропия по Y : ^[16]

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

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

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

Взаимная информация (трансинформация)

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

${\displaystyle I(X;Y)=\mathbb {E} _{X,Y}[SI(x,y)]=\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(x)\,p(y)}}}$

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

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

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

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

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

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

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

${\displaystyle I(X;Y)=\mathbb {E} _{p(y)}[D_{\mathrm {KL} }(p(X|Y=y)\|p(X))].}$

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

${\displaystyle I(X;Y)=D_{\mathrm {KL} }(p(X,Y)\|p(X)p(Y)).}$

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

Расхождение Кульбака – Лейблера (прирост информации)

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

${\displaystyle D_{\mathrm {KL} }(p(X)\|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 {\frac {p(x)}{q(x)}}.}$

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

Другая интерпретация расхождения КЛ — это «ненужный сюрприз», внесенный априорным отличием от истины: предположим, что число X собирается быть случайным образом выбрано из дискретного набора с распределением вероятностей . Если Алиса знает истинное распределение , а Боб считает (имеет априорное значение ), что распределение равно , то Боб в среднем будет более удивлен , чем Алиса, увидев значение X. Дивергенция KL — это (объективное) ожидаемое значение (субъективного) сюрприза Боба минус сюрприз Алисы, измеренное в битах, если журнал находится в базе 2. Таким образом, степень, в которой априорное значение Боба «неправильно», можно выразить количественно в терминах о том, как «ненужно удивлюсь» его это ожидает. ${\displaystyle p(x)}$ ${\displaystyle p(x)}$ ${\displaystyle q(x)}$

Направленная информация

Направленная информация -это мера теории информации, которая количественно определяет поток информации от случайного процессак случайному процессу. Термин «направленная информация» был придуман Джеймсом Мэсси и определяется как ${\displaystyle I(X^{n}\to Y^{n})}$ ${\displaystyle X^{n}=\{X_{1},X_{2},\dots ,X_{n}\}}$ ${\displaystyle Y^{n}=\{Y_{1},Y_{2},\dots ,Y_{n}\}}$

${\displaystyle I(X^{n}\to Y^{n})\triangleq \sum _{i=1}^{n}I(X^{i};Y_{i}|Y^{i-1})}$,

где условная взаимная информация . ${\displaystyle I(X^{i};Y_{i}|Y^{i-1})}$ ${\displaystyle I(X_{1},X_{2},...,X_{i};Y_{i}|Y_{1},Y_{2},...,Y_{i-1})}$

В отличие от взаимной информации, направленная информация не симметрична. Измеряет биты информации, которые передаются причинно ^{[определение причинной передачи?]} от до . Направленная информация имеет множество применений в задачах, где причинность играет важную роль, таких как пропускная способность канала с обратной связью, ^{[17] [18]} пропускная способность дискретных сетей без памяти с обратной связью, ^[19] игра с причинно-следственной информацией, ^[20] сжатие с причинно-следственная информация, ^[21] и в настройках управления связью в реальном времени , ^{[22] [23]} статистическая физика. ^[24] ${\displaystyle I(X^{n}\to Y^{n})}$ ${\displaystyle X^{n}}$ ${\displaystyle Y^{n}}$

Другие количества

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

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

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

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

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

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

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

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

Ставка

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

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

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

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

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

Скорость информации определяется как

${\displaystyle r=\lim _{n\to \infty }{\frac {1}{n}}I(X_{1},X_{2},\dots X_{n};Y_{1},Y_{2},\dots Y_{n});}$

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

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

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

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

${\displaystyle {\xrightarrow[{\text{Message}}]{W}}{\begin{array}{|c| }\hline {\text{Encoder}}\\f_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Encoded \atop sequence} }]{X^{n}}}{\begin{array}{|c| }\hline {\text{Channel}}\\p(y|x)\\\hline \end{array}}{\xrightarrow[{\mathrm {Received \atop sequence} }]{Y^{n}}}{\begin{array}{|c| }\hline {\text{Decoder}}\\g_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Estimated \atop message} }]{\hat {W}}}}$

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

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

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

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

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

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

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

Каналы с памятью и направленной информацией

На практике многие каналы имеют память. А именно, во времени канал задается условной вероятностью . Часто удобнее использовать обозначение, и канал становится . В таком случае пропускная способность определяется скоростью взаимной информации при отсутствии обратной связи и скоростью направленной информации в случае, если обратная связь есть или нет ^{[26] [27]} (при отсутствии обратной связи направленная информация равна взаимная информация). ${\displaystyle i}$ ${\displaystyle P(y_{i}|x_{i},x_{i-1},x_{i-2},...,x_{1},y_{i-1},y_{i-2},...,y_{1}).}$ ${\displaystyle x^{i}=(x_{i},x_{i-1},x_{i-2},...,x_{1})}$ ${\displaystyle P(y_{i}|x^{i},y^{i-1}).}$

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

Использование разведки и секретные приложения

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

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

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

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

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

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

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

Семиотика

Семиотики Доде Наута и Винфрид Нёт считали, что Чарльз Сандерс Пирс создал теорию информации в своих работах по семиотике. ^{[29] : 171  [30] : 137} Наута определил семиотическую теорию информации как исследование «внутренних процессов кодирования, фильтрации и обработки информации». ^{[29] : 91}

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

Интегрированная организация процессов нейронной информации

Количественные методы теории информации применялись в когнитивной науке для анализа интегрированной организации процессов нейронной информации в контексте проблемы связывания в когнитивной нейробиологии . ^[32] В этом контексте либо теоретико-информационная мера, такая как функциональные кластеры ( модель функциональной кластеризации Джеральда Эдельмана и Джулио Тонони и гипотеза динамического ядра (DCH) ^[33] ), либо эффективная информация ( теория интегрированной информации Тонони (IIT) ) сознания ^{[34] [35] [36]} ), определяется (на основе реентерабельной организации процесса, т.е. синхронизации нейрофизиологической активности между группами популяций нейронов), или мера минимизации свободной энергии на основе статистических методов ( принцип свободной энергии Карла Дж. Фристона (FEP), теоретическая мера информации, которая утверждает, что каждое адаптивное изменение в самоорганизующейся системе приводит к минимизации свободной энергии, и байесовская гипотеза мозга ^{[37] ] [38] [39] [40] [41]} ).

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

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

Смотрите также

• Математический портал

• Алгоритмическая вероятность
• Байесовский вывод
• Теория коммуникации
• Теория конструктора - обобщение теории информации, включающее квантовую информацию.
• Формальная наука
• Индуктивная вероятность
• Инфо-метрика
• Минимальная длина сообщения
• Минимальная длина описания
• Философия информации

Приложения

• Активное нетворкинг
• Криптоанализ
• Криптография
• Кибернетика
• Энтропия в термодинамике и теории информации
• Играть в азартные игры
• Разведка (сбор информации)
• Сейсморазведка

История

• Хартли, РВЛ
• История теории информации
• Шеннон, CE
• Хронология теории информации
• Йоки, HP

Теория

• Теория кодирования
• Теория обнаружения
• Теория оценки
• Информация о Фишере
• Информационная алгебра
• Информационная асимметрия
• Теория информационного поля
• Информационная геометрия
• Теория информации и теория меры
• Колмогоровская сложность
• Список нерешенных проблем теории информации
• Логика информации
• Сетевое кодирование
• Философия информации
• Квантовая информатика
• Исходное кодирование

Концепции

• Бан (единица)
• Пропускная способность канала
• Канал связи
• Источник связи
• Условная энтропия
• Скрытый канал
• Сжатие данных
• Декодер
• Дифференциальная энтропия
• Взаимозаменяемая информация
• Сложность колебания информации
• Информационная энтропия
• Совместная энтропия
• Расхождение Кульбака – Лейблера
• Взаимная информация
• Поточечная взаимная информация (PMI)
• Приемник (теория информации)
• Резервирование
• Энтропия Реньи
• Самоинформация
• Расстояние уникальности
• Разнообразие
• Расстояние Хэмминга
• Растерянность

Рекомендации

1. «Клод Шеннон, пионер теории цифровой информации». ФиерсТелеком . Проверено 30 апреля 2021 г.
2. Шеннон, Клод Элвуд (1998). Математическая теория связи. Уоррен Уивер. Урбана: Издательство Университета Иллинойса. ISBN 0-252-72546-8. ОСЛК  40716662.
3. Бернхэм, К.П. и Андерсон Д.Р. (2002) Выбор модели и многомодельный вывод: практический информационно-теоретический подход, второе издание (Springer Science, Нью-Йорк) ISBN 978-0-387-95364-9 . 
4. Ф. Рике; Д. Варланд; Р Рюйтер ван Стивенинк; В Бялек (1997). Спайкс: исследование нейронного кода . Пресса МТИ. ISBN 978-0262681087.
5. Дельгадо-Бональ, Альфонсо; Мартин-Торрес, Хавьер (3 ноября 2016 г.). «Человеческое зрение определяется на основе теории информации». Научные отчеты . 6 (1): 36038. Бибкод : 2016NatSR...636038D. дои : 10.1038/srep36038. ISSN  2045-2322. ПМК 5093619 . ПМИД  27808236. 
6. см.; Хюльзенбек, JP; Ронквист, Ф.; Нильсен, Р.; Болбак, JP (2001). «Байесовский вывод филогении и его влияние на эволюционную биологию». Наука . 294 (5550): 2310–2314. Бибкод : 2001Sci...294.2310H. дои : 10.1126/science.1065889. PMID  11743192. S2CID  2138288.
7. Алликметс, Рандо; Вассерман, Уайет В.; Хатчинсон, Эми; Смоллвуд, Филип; Натанс, Джереми; Роган, Питер К. (1998). «Томас Д. Шнайдер], Майкл Дин (1998) Организация гена ABCR: анализ последовательностей промотора и сплайсингового соединения». Джин . 215 (1): 111–122. дои : 10.1016/s0378-1119(98)00269-8 . ПМИД  9666097.
8. Джейнс, ET (1957). «Теория информации и статистическая механика». Физ. Преподобный . 106 (4): 620. Бибкод : 1957PhRv..106..620J. doi : 10.1103/physrev.106.620. S2CID  17870175.
9. Талаат, Халед; Коуэн, Бенджамин; Андероглу, Осман (05.10.2020). «Метод информационной энтропии для оценки сходимости молекулярно-динамического моделирования». Журнал прикладной физики . 128 (13): 135102. Бибкод : 2020JAP...128m5102T. дои : 10.1063/5.0019078 . ОСТИ  1691442. S2CID  225010720.
10. Беннетт, Чарльз Х.; Ли, Мин; Ма, Бин (2003). «Письма счастья и эволюционные истории». Научный американец . 288 (6): 76–81. Бибкод : 2003SciAm.288f..76B. doi : 10.1038/scientificamerican0603-76. PMID  12764940. Архивировано из оригинала 7 октября 2007 г. Проверено 11 марта 2008 г.
11. Дэвид Р. Андерсон (1 ноября 2003 г.). «Некоторые сведения о том, почему люди, занимающиеся эмпирическими науками, могут захотеть лучше понять методы теории информации» (PDF) . Архивировано из оригинала (PDF) 23 июля 2011 года . Проверено 23 июня 2010 г.
12. Хорган, Джон (27 апреля 2016 г.). «Клод Шеннон: тинкерер, шутник и отец теории информации». Spectrum.ieee.org . Проверено 30 сентября 2023 г.
13. Робертс, Шивон (30 апреля 2016 г.). «Забытый отец информационного века». Житель Нью-Йорка . ISSN  0028-792X . Проверено 30 сентября 2023 г.
14. Це, Дэвид (22 декабря 2020 г.). «Как Клод Шеннон изобрел будущее». Журнал Кванта . Проверено 30 сентября 2023 г.
15. Фазлолла М. Реза (1994) [1961]. Введение в теорию информации. Dover Publications, Inc., Нью-Йорк. ISBN 0-486-68210-2.
16. Роберт Б. Эш (1990) [1965]. Теория информации. ISBN Dover Publications, Inc. 0-486-66521-6.
17. Мэсси, Джеймс (1990), Причинно-следственная связь, обратная связь и направленная информация , CiteSeerX 10.1.1.36.5688 
18. Пермутер, Хаим Генри; Вайсман, Цахи; Голдсмит, Андреа Дж. (февраль 2009 г.). «Каналы конечных состояний с инвариантной во времени детерминированной обратной связью». Транзакции IEEE по теории информации . 55 (2): 644–662. arXiv : cs/0608070 . дои : 10.1109/TIT.2008.2009849. S2CID  13178.
19. Крамер, Г. (январь 2003 г.). «Результаты емкости дискретной сети без памяти». Транзакции IEEE по теории информации . 49 (1): 4–21. дои : 10.1109/TIT.2002.806135.
20. Пермутер, Хаим Х.; Ким, Ён-Хан; Вайсман, Цахи (июнь 2011 г.). «Интерпретации направленной информации в теории портфеля, сжатии данных и проверке гипотез». Транзакции IEEE по теории информации . 57 (6): 3248–3259. arXiv : 0912.4872 . дои : 10.1109/TIT.2011.2136270. S2CID  11722596.
21. Симеоне, Освальдо; Пермутер, Хаим Анри (июнь 2013 г.). «Исходное кодирование, когда дополнительная информация может быть задержана». Транзакции IEEE по теории информации . 59 (6): 3607–3618. arXiv : 1109.1293 . дои :10.1109/TIT.2013.2248192. S2CID  3211485.
22. Хараламбус, Хараламбос Д.; Ставру, Фотий А. (август 2016 г.). «Направленная информация об абстрактных пространствах: свойства и вариационные равенства». Транзакции IEEE по теории информации . 62 (11): 6019–6052. arXiv : 1302.3971 . дои : 10.1109/TIT.2016.2604846. S2CID  8107565.
23. Танака, Такаши; Исфахани, Пейман Мохаджерин; Миттер, Санджой К. (январь 2018 г.). «Управление LQG с минимальной направленной информацией: подход полуопределенного программирования». Транзакции IEEE при автоматическом управлении . 63 (1): 37–52. arXiv : 1510.04214 . дои : 10.1109/TAC.2017.2709618. S2CID  1401958.
24. Винклер, Дрор А; Пермутер, Хаим Х; Мерхав, Нери (20 апреля 2016 г.). «Аналогия между азартными играми и извлечением работы, основанной на измерениях». Журнал статистической механики: теория и эксперимент . 2016 (4): 043403. arXiv : 1404.6788 . Бибкод : 2016JSMTE..04.3403V. дои : 10.1088/1742-5468/2016/04/043403. S2CID  124719237.
25. Джерри Д. Гибсон (1998). Цифровое сжатие мультимедиа: принципы и стандарты. Морган Кауфманн. ISBN 1-55860-369-7.
26. Мэсси, Джеймс Л. (1990). «Причинность, обратная связь и направленная информация». CiteSeerX 10.1.1.36.5688 .  {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
27. Пермутер, Хаим Генри; Вайсман, Цахи; Голдсмит, Андреа Дж. (февраль 2009 г.). «Каналы конечных состояний с инвариантной во времени детерминированной обратной связью». Транзакции IEEE по теории информации . 55 (2): 644–662. arXiv : cs/0608070 . дои : 10.1109/TIT.2008.2009849. S2CID  13178.
28. Хаггерти, Патрик Э. (1981). «Корпорация и инновации». Журнал стратегического менеджмента . 2 (2): 97–118. дои : 10.1002/smj.4250020202.
29. Наута, Доде (1972). Значение информации . Гаага: Мутон. ISBN 9789027919960.
30. Нёт, Винфрид (январь 2012 г.). «Теория информации Чарльза С. Пирса: теория роста символов и знаний». Кибернетика и человеческое познание . 19 (1–2): 137–161.
31. Нёт, Винфрид (1981). «Семиотика идеологии». Семиотика , Выпуск 148.
32. Маурер, Х. (2021). Когнитивная наука: механизмы интегративной синхронизации в когнитивных нейроархитектурах современного коннекционизма. CRC Press, Бока-Ратон/Флорида, гл. 10, ISBN 978-1-351-04352-6. https://doi.org/10.1201/9781351043526
33. Эдельман, GM и Дж. Тонони (2000). Вселенная сознания: как материя становится воображением. Основные книги, Нью-Йорк.
34. Тонони, Г. и О. Спорнс (2003). Измерение интеграции информации. BMC Нейронаука 4: 1-20.
35. Тонони, Г. (2004a). Теория информационной интеграции сознания. BMC Нейронаука 5: 1-22.
36. Тонони, Г. (2004b). Сознание и мозг: теоретические аспекты. В: Г. Адельман и Б. Смит [ред.]: Энциклопедия неврологии. 3-е изд. Эльзевир, Амстердам, Оксфорд.
37. Фристон, К. и К.Е. Стефан (2007). Свободная энергия и мозг. Синтез 159: 417-458.
38. Фристон, К. (2010). Принцип свободной энергии: единая теория мозга. Обзоры природы по неврологии 11: 127–138.
39. Фристон, К., М. Брейкстир и Г. Деко (2012). Восприятие и самоорганизованная нестабильность. Границы вычислительной нейронауки 6: 1-19.
40. Фристон, К. (2013). Жизнь такая какая она есть. Журнал интерфейса Королевского общества 10: 20130475.
41. Кирхгоф, М., Т. Парр, Э. Паласиос, К. Фристон и Дж. Киверштейн. (2018). Марковские одеяла жизни: автономия, активный вывод и принцип свободной энергии. Журнал интерфейса Королевского общества 15: 20170792.

дальнейшее чтение

Классическая работа

• Шеннон, CE (1948), « Математическая теория связи », Технический журнал Bell System , 27, стр. 379–423 и 623–656, июль и октябрь 1948 г. PDF.
  Заметки и другие форматы.
• Р.В.Л. Хартли, «Передача информации», Технический журнал Bell System , июль 1928 г.
• Андрей Колмогоров (1968), «Три подхода к количественному определению информации» в Международном журнале компьютерной математики , 2, стр. 157–168.

Другие журнальные статьи

• Дж. Л. Келли-младший, Принстон, «Новая интерпретация скорости передачи информации», Технический журнал Bell System , Vol. 35 июля 1956 г., стр. 917–26.
• Р. Ландауэр, IEEE.org, «Информация физична», Proc. Семинар по физике и вычислениям PhysComp'92 (IEEE Comp. Sci.Press, Los Alamitos, 1993), стр. 1–4.
• Ландауэр, Р. (1961). «Необратимость и выделение тепла в вычислительном процессе» (PDF) . IBM J. Res. Дев . 5 (3): 183–191. дои : 10.1147/рд.53.0183.
• Тимме, Николас; Алфорд, Уэсли; Флекер, Бенджамин; Беггс, Джон М. (2012). «Многомерные информационные меры: взгляд экспериментатора». arXiv : 1111.6857 [cs.IT].

Учебники по теории информации

• Аладжаджи Ф. и Чен П.Н. Введение в теорию однопользовательской информации. Сингапур: Springer, 2018. ISBN 978-981-10-8000-5 . 
• Арндт, К. Информационные меры, информация и ее описание в науке и технике (Серия Springer: Сигналы и коммуникационные технологии), 2004, ISBN 978-3-540-40855-0 
• Эш, РБ. Теория информации . Нью-Йорк: Interscience, 1965. ISBN 0-470-03445-9 . Нью-Йорк: Дувр, 1990. ISBN 0-486-66521-6.  
• Галлагер Р. Теория информации и надежная связь. Нью-Йорк: Джон Уайли и сыновья, 1968. ISBN 0-471-29048-3 . 
• Гольдман, С. Теория информации . Нью-Йорк: Прентис-Холл, 1953. Нью-Йорк: ISBN Дувра, 1968 г. 0-486-62209-6 , ISBN 2005 г. 0-486-44271-3 .  
• Кавер, Томас ; Томас, Джой А. (2006). Элементы теории информации (2-е изд.). Нью-Йорк: Wiley-Interscience . ISBN 0-471-24195-4.
• Чисар И., Корнер Дж. Теория информации: теоремы кодирования для дискретных систем без памяти Akademiai Kiado: 2-е издание, 1997. ISBN 963-05-7440-3 
• Маккей, Дэвид Дж. К. Теория информации, вывод и алгоритмы обучения Кембридж: Издательство Кембриджского университета, 2003. ISBN 0-521-64298-1 
• Мансурипур, М. Введение в теорию информации . Нью-Йорк: Прентис Холл, 1987. ISBN 0-13-484668-0. 
• МакЭлис, Р. Теория информации и кодирования . Кембридж, 2002. ISBN 978-0521831857. 
• Пирс, младший . «Введение в теорию информации: символы, сигналы и шум». Дувр (2-е издание). 1961 г. (перепечатано Dover 1980 г.).
• Реза, Ф. Введение в теорию информации . Нью-Йорк: McGraw-Hill 1961. Нью-Йорк: Дувр 1994. ISBN 0-486-68210-2 . 
• Шеннон, Клод ; Уивер, Уоррен (1949). Математическая теория связи (PDF) . Урбана, Иллинойс : Издательство Университета Иллинойса . ISBN 0-252-72548-4. LCCN  49-11922.
• Стоун, СП. Глава 1 книги «Теория информации: введение в учебное пособие», Университет Шеффилда, Англия, 2014 г. ISBN 978-0956372857 . 
• Юнг, Р.В. Первый курс теории информации Kluwer Academic/Plenum Publishers, 2002. ISBN 0-306-46791-7 . 
• Юнг, Р.В. Теория информации и сетевое кодирование Springer 2008, 2002. ISBN 978-0-387-79233-0 

Другие книги

• Леон Бриллюэн, Наука и теория информации , Минеола, Нью-Йорк: Дувр, [1956, 1962] 2004. ISBN 0-486-43918-6 
• Джеймс Глейк , Информация: история, теория, потоп , Нью-Йорк: Пантеон, 2011. ISBN 978-0-375-42372-7 
• А. И. Хинчин, Математические основы теории информации , Нью-Йорк: Дувр, 1957. ISBN 0-486-60434-9. 
• Х. С. Лефф и А. Ф. Рекс, редакторы журнала «Демон Максвелла: энтропия, информация, вычисления» , Princeton University Press, Принстон, Нью-Джерси (1990). ISBN 0-691-08727-X 
• Роберт К. Логан . Что такое информация? - Распространяющая организация в биосфере, символосфере, техносфере и эконосфере , Торонто: DEMO Publishing.
• Том Зигфрид, Бит и маятник , Уайли, 2000. ISBN 0-471-32174-5 
• Чарльз Сейф , Расшифровка Вселенной , Викинг, 2006. ISBN 0-670-03441-X 
• Джереми Кэмпбелл, грамматик , Touchstone/Simon & Schuster, 1982, ISBN 0-671-44062-4 
• Анри Тейль, Экономика и теория информации , Rand McNally & Company – Чикаго, 1967.
• Эсколано, Суау, Бонев, Теория информации в компьютерном зрении и распознавании образов , Springer, 2009. ISBN 978-1-84882-296-2 . 
• Влатко Ведрал, Декодирование реальности: Вселенная как квантовая информация , Oxford University Press, 2010. ISBN 0-19-923769-7 

Внешние ссылки

• «Информация», Математическая энциклопедия , EMS Press , 2001 [1994]
• Ламберт Флорида (1999), «Перетасованные карты, грязные столы и беспорядок в комнатах общежития - примеры увеличения энтропии? Чепуха!», Журнал химического образования
• Монографии, исследования и обзоры Общества теории информации IEEE и ITSOC, заархивировано 12 июня 2018 г. в Wayback Machine.