История теории информации

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

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

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

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

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

До 1948 года

Ранние

Некоторые из старейших методов телекоммуникаций неявно используют многие идеи, которые позже будут количественно оценены в теории информации. Современная телеграфия , начиная с 1830-х годов, использовала азбуку Морзе , в которой более распространенные буквы (например, «Е», которая выражается одной «точкой») передаются быстрее, чем менее распространенные буквы (например, «J», которая выражается одна «точка», за которой следуют три «тире»). Идея кодирования информации таким способом является краеугольным камнем сжатия данных без потерь . Сто лет спустя частотная модуляция показала, что полосу пропускания можно рассматривать просто как еще одну степень свободы. Вокодер , который сейчас рассматривается как диковинка аудиотехники, изначально был разработан в 1939 году для использования меньшей полосы пропускания, чем у исходного сообщения, во многом так же, как мобильные телефоны теперь сочетают качество голоса с полосой пропускания.

Количественные представления информации

Самыми прямыми предшественниками работы Шеннона были две статьи, опубликованные в 1920-х годах Гарри Найквистом и Ральфом Хартли , которые оба все еще были руководителями исследований в Bell Labs, когда Шеннон прибыл в нее в начале 1940-х годов.

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

$W=K\log m\,$

где W — скорость передачи разведданных, m — количество различных уровней напряжения, из которых можно выбирать на каждом временном шаге, а K — константа.

Статья Хартли 1928 года, названная просто «Передача информации», пошла дальше, использовав слово «информация» (в техническом смысле) и ясно указав, что информация в этом контексте является измеримой величиной, отражающей только способность получателя различать эту последовательность. Набор символов был задуман отправителем, а не кем-либо другим, совершенно независимо от какого-либо связанного с ним значения или другого психологического или семантического аспекта, который эти символы могли представлять. Этот объем информации он количественно оценил как

$H=\log S^{n}\,$

где S — количество возможных символов, а n — количество символов в передаче. Таким образом, естественной единицей информации была десятичная цифра, гораздо позже переименованная в хартли в его честь как единица, масштаб или мера информации. Информация Хартли , H ₀ , до сих пор используется как величина для логарифма общего числа возможностей.

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

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

Энтропия в статистической механике

Одной из областей, где неравные вероятности были действительно хорошо известны, была статистическая механика, где Людвиг Больцман в контексте своей H-теоремы 1872 года впервые ввел величину

$H=-\sum f_{i}\log f_{i}$

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

Определение Больцмана вскоре было переработано американским физиком-математиком Дж. Уиллардом Гиббсом в общую формулу статистико-механической энтропии, которая больше не требует идентичных и невзаимодействующих частиц, а вместо этого основана на распределении вероятностей p _i для полного i микросостояния общая система:

$S=-k_{\text{B}}\sum p_{i}\ln p_{i}\,$

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

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

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

Разработка с 1948 года

Публикация статьи Шеннона « Математическая теория связи » в 1948 году в техническом журнале Bell System положила начало теории информации, какой мы ее знаем сегодня. С тех пор произошло множество разработок и применений этой теории, что сделало возможным появление многих современных устройств для передачи и хранения данных, таких как компакт-диски и мобильные телефоны .

Известные более поздние события перечислены в хронологии теории информации , в том числе:

• В 1951 году было изобретено кодирование Хаффмана — метод поиска оптимальных префиксных кодов для без потерь сжатия данных .
• Ирвинг С. Рид и Дэвид Э. Мюллер предлагают коды Рида-Мюллера в 1954 году.
• Предложение 1960 года кодов Рида-Соломона .
• В 1966 году Фумитада Итакура ( Университет Нагои ) и Сюдзо Сайто ( Nippon Telegraph and Telephone ) разрабатывают линейное предсказательное кодирование (LPC) — форму кодирования речи .
• В 1968 году Элвин Берлекамп изобретает алгоритм Берлекэмпа – Мэсси ; на его применение для декодирования кодов BCH и Рида – Соломона указал Джеймс Л. Мэсси в следующем году.
• В 1972 году Насир Ахмед предложил дискретное косинусное преобразование (ДКП). Позже он становится наиболее широко используемым алгоритмом сжатия с потерями и основой для стандартов сжатия цифрового мультимедиа , начиная с 1988 года, включая H.26x (начиная с H.261 ) и MPEG стандарты кодирования видео . JPEG сжатие изображений , MP3 сжатие звука , и расширенное кодирование звука (AAC).
• В 1976 году Готфрид Унгербёк опубликовал первую статью о решетчатой ​​модуляции ; более подробное изложение в 1982 году привело к повышению скорости аналоговых модемов POTS с 9,6 кбит/с до 33,6 кбит/с.
• В 1977 году Авраам Лемпель и Джейкоб Зив разработали сжатие Лемпеля-Зива ( LZ77 ).
• В начале 1980-х годов Ренука П. Джиндал из Bell Labs улучшил шумовые характеристики устройств металл-оксид-полупроводник (МОП), решив проблемы, которые ограничивали чувствительность их приемников и скорость передачи данных . Это приводит к широкому внедрению МОП-технологии в лазерных световых системах и беспроводных терминалах, что обеспечивает соблюдение закона Эдгольма .
• В 1989 году Кац публикует Фил .zip формат, включая DEFLATE (LZ77 + кодирование Хаффмана); позже стал наиболее широко используемым архивным контейнером.
• В 1995 году Бенджамин Шумахер ввел термин «кубит» и доказал теорему квантового бесшумного кодирования.

См. также

• Хронология теории информации
• Клод Шеннон
• Ральф Хартли
• H-теорема