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

Не путать с информатикой .

Теория информации это математическое исследование количественного определения , хранения и передачи информации – . Эта область была основана и поставлена ​​на прочную основу Клодом Шенноном в 1940-х годах. хотя ранний вклад был сделан в 1920-х годах благодаря работам Гарри Найквиста и Ральфа Хартли . Он находится на стыке электронной инженерии , математики , статистики , информатики , нейробиологии , физики и электротехники .

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

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

Обзор

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

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

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

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

Основная статья: История теории информации

Знаковым событием, заложившим дисциплину теории информации и привлекшим к ней немедленное внимание всего мира, стала публикация классической статьи Клода Э. Шеннона «Математическая теория связи» в техническом журнале Bell System в июле и октябре 1948 года. Он стал известен как «отец теории информации». Шеннон изложил некоторые из своих первоначальных идей теории информации еще в 1939 году в письме Ванневару Бушу .

До этой статьи в 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 . Это оправдано, поскольку $\lim _{p\rightarrow 0+}p\log p=0$ для любого логарифмического основания.

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

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

$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 элементов информации (чаще называемых битами). Между этими двумя крайностями информацию можно количественно оценить следующим образом. Если $\mathbb {X}$ — это набор всех сообщений { x ₁ , ..., x _n }, которыми X может быть , а p ( x ) — это вероятность некоторого $x\in \mathbb {X}$, то энтропия H X : определяется

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

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

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

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

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

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

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

$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 ) — это средняя условная энтропия по двусмысленностью :

$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).$

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

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

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

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

$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 ( специфическая взаимная информация) — это поточечная взаимная информация .

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

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

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

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

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

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

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

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

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

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

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

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

$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 иногда используется как «метрика расстояния», она не является истинной метрикой , поскольку она не симметрична и не удовлетворяет неравенству треугольника (что делает ее полуквазиметрикой).

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

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

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

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

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

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

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

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

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

Основная статья: Теория кодирования

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

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

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

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

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

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

Ставка

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

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

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

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

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

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

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

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

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

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

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

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

${\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 ) — предельного распределения сообщений, которые мы выбираем для отправки по каналу. При этих ограничениях мы хотели бы максимизировать скорость передачи информации или сигнала , которую мы можем передавать по каналу. Подходящей мерой для этого является взаимная информация, и эта максимальная взаимная информация называется пропускной способностью канала и определяется как:

$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 бит на использование канала.

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

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

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

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

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

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

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

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

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

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

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

Семиотика

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

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

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

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

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

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

См. также

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

Приложения

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

История

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

Теория

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

Концепции

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

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

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

• Шеннон, 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 ].

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

• Аладжаджи Ф. и Чен П.Н. Введение в теорию однопользовательской информации. Сингапур: Спрингер, 2018. ISBN   978-981-10-8000-5
• Арндт, К. Информационные меры, информация и ее описание в науке и технике (Серия Springer: Сигналы и коммуникационные технологии), 2004 г., ISBN   978-3-540-40855-0
• Эш, РБ. Теория информации . Нью-Йорк: Интерсайенс, 1965. ISBN   0-470-03445-9 . Нью-Йорк: Дувр, 1990. ISBN   0-486-66521-6
• Галлагер, Р. Теория информации и надежная связь. Нью-Йорк: Джон Уайли и сыновья, 1968. ISBN   0-471-29048-3
• Гольдман, С. Теория информации . Нью-Йорк: Прентис-Холл, 1953. Нью-Йорк: Дувр, 1968. ISBN   0-486-62209-6 , 2005 г. ISBN   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 г.).
• Реза, Ф . Введение в теорию информации . Нью-Йорк: МакГроу-Хилл, 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.