Теория информации - Information theory

Теория информации
Энтропия Дифференциальная энтропия Условная энтропия Совместная энтропия Взаимная информация Условная взаимная информация Относительная энтропия Скорость энтропии Предельная плотность дискретных точек Теория информации с конечной длиной блока
Свойство асимптотического равнораспределения Теория скорости-искажения
Теорема кодирования источника Шеннона Емкость канала Теорема кодирования с шумом канала Теорема Шеннона – Хартли.
v т е

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

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

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

Обзор

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

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

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

Историческое прошлое

Знаковым событием, установившим дисциплину теории информации и привлекшим к ней немедленное внимание всего мира, стала публикация классической статьи Клода Э. Шеннона «Математическая теория коммуникации» в журнале 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 года, Шеннон впервые представил качественную и количественную модель коммуникации как статистический процесс, лежащий в основе теории информации, начиная с утверждения:

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

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

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

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

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

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

В дальнейшем выражение вида 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 : ${\ Displaystyle \ mathbb {X}}$${\ Displaystyle х \ в \ mathbb {X}}$

${\ Displaystyle H (X) = \ mathbb {E} _ {X} [I (x)] = - \ sum _ {x \ in \ mathbb {X}} p (x) \ log p (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 р (х, у) \,}$

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

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

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

${\ 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 ( S pecific взаимной I нформация) является точечно взаимной информации .

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

${\ 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 (Икс)}}.}$

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

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

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

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

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

Картинка, показывающая царапины на читаемой поверхности 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});}$

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

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

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

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

Емкость канала

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

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

${\ displaystyle {\ xrightarrow [{\ text {Message}}] {W}} {\ begin {array} {| c | } \ hline {\ text {Encoder}} \\ f_ {n} \\\ hline \ end {array}} {\ xrightarrow [{\ mathrm {Закодированная \ наверху последовательность}}] {X ^ {n}}} { \ begin {array} {| c | } \ hline {\ text {Channel}} \\ p (y | x) \\\ hline \ end {array}} {\ xrightarrow [{\ mathrm {Получено \ наверху последовательности}}] {Y ^ {n}} } {\ begin {array} {| c | } \ hline {\ text {Decoder}} \\ g_ {n} \\\ hline \ end {array}} {\ xrightarrow [{\ mathrm {Оценка \ наверху сообщения}}] {\ hat {W}}}}$

Здесь X представляет собой пространство переданных сообщений, а Y пространство сообщений, полученных за единицу времени по нашему каналу. Пусть р ( у | х ) является условной вероятностью функция распределения 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 имеет пропускную способность 1 - H _b ( p ) бит на использование канала, где H _b - двоичная функция энтропии до логарифма с основанием 2:

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

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

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

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

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

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

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

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

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

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

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

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

Семиотика

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

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

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

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

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

Приложения

История

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

Теория

Концепции

использованная литература

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

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

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

Другие книги

МООК по теории информации

• Раймонд В. Юнг, " Теория информации " ( Китайский университет Гонконга )

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

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