История теории информации - History of information theory

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «История теории информации»  – Новости  · газеты  · книги  · ученый  · JSTOR (Август 2017 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

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

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

До 1948 г.

Ранние телекоммуникации

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

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

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

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

${displaystyle W = Klog m,}$

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

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

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

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

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

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

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

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

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

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

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

${displaystyle S = -k_ {ext {B}} sum p_ {i} ln p_ {i},}$

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

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

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

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

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

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

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

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

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

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