Основные теории информации кратко

Обновлено: 05.07.2024

Так вот у Хэмминга (да, да, самоконтролирующиеся и самокорректирующиеся коды Хэмминга) есть целая книга, написанная по мотивам его лекций. Мы ее переводим, ведь мужик дело говорит.

За перевод спасибо Андрею Пахомову.

Остановимся на этом подробнее. Шеннон полагал, что количественная мера информации должна быть непрерывной функцией от вероятности события p, а для независимых событий она должна быть аддитивной – количество информации, полученное в результате осуществления двух независимых событий, должно равняться количеству информации, полученному в результате осуществления совместного события. Например, результат броска игральных костей и монеты обычно рассматриваются как независимые события. Переведем вышесказанное на язык математики. Если I (p) – это количество информации, которое содержится в событии с вероятностью p, то, для совместного события, состоящего из двух независимых событий x с вероятностью p₁ и y с вероятностью p₂ получаем

(x и y независимые события)

Это функциональное уравнение Коши, истинное для всех p₁ и p2. Для решения этого функционального уравнения предположим, что

Если p₁ = p 2 и p₂ = p, тогда

и т.д. Расширяя этот процесс, используя стандартный метод для экспонент, для всех рациональных чисел m / n, верно следующее

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

В теории информации принято принимать основание логарифма равное 2, поэтому бинарный выбор содержит ровно 1 бит информации. Следовательно, информация измеряется по формуле

Давайте приостановимся и разберемся, что же произошло выше. Прежде всего, мы так и не дали определение понятию “информация”, мы просто определили формулу ее количественной меры.

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

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

Рассмотрим систему, алфавит которой состоит из символов q с вероятностями pi. В этом случае среднее количество информации в системе (её ожидаемое значение) равно:

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

Доказательство опирается на очевидный график, рис. 13.I, который показывает, что

а равенство достигается только при x = 1. Применим неравенство к каждому слагаемому суммы из левой части:

Если алфавит системы связи состоит из q символов, то принимая вероятность передачи каждого символа qi = 1/q и подставляя q, получаем из неравенства Гиббса

Рисунок 13.I

Это говорит о том, что если вероятность передачи всех q символов одинакова и равна — 1 / q, то максимальная энтропия равна ln q, в противном случае выполняется неравенство.

В случае однозначно декодируемого кода, мы имеем неравенство Крафта

Теперь если мы определим псевдовероятности

где конечно = 1, что следует из неравенства Гиббса,

и применим немного алгебры (помните, что K ≤ 1, поэтому мы можем опустить логарифмический член, и возможно, усилить неравенство позже), то получим

где L — это средняя длина кода.

Таким образом, энтропия является минимальной границей для любого посимвольного кода со средней длиной кодового слова L. Это теорема Шеннона для канала без помех.

(отправитель)
График 13.II

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

где, как и раньше, P — вероятность отсутствия ошибки в любом отправленном бите. При отправке n независимых битов емкость канала определяется как

Как может возникнуть ошибка? Ошибка может произойти в случаях, описанных в таблице ниже:

Рисунок 13.III

Мы можем выбросить первый множитель во втором слагаемом, приняв его за 1. Таким образом получим неравенство

повторно применяем к последнему члену справа

Приняв n достаточно большим, первый член может быть принят сколь угодно малым, скажем, меньше некоторого числа d. Поэтому мы имеем

кодовых словарей, имеющие одинаковую вероятность ½nM. Конечно, случайный процесс создания кодового словаря означает, что есть вероятность появления дубликатов, а также кодовых точек, которые будут близки друг к другу и, следовательно, будут источником вероятных ошибок. Нужно доказать, что если это не происходит с вероятностью выше, чем любой небольшой выбранный уровень ошибки, то заданное n достаточно велико.
Решающим момент заключается в том, что Шеннон усреднил все возможные кодовые книги, чтобы найти среднюю ошибку! Мы будем использовать символ Av [.], чтобы обозначить среднее значение по множеству всех возможных случайных кодовых словарей. Усреднение по константе d, конечно, дает константу, так как для усреднения каждый член совпадает с любым другим членом в сумме,

который может быть увеличен (M–1 переходит в M )

Теория информации (математическая теория связи) — раздел прикладной математики, аксиоматически определяющий понятие информации [1] , её свойства и устанавливающий предельные соотношения для систем передачи данных. Как и любая математическая теория, оперирует с математическими моделями, а не с реальными физическими объектами (источниками и каналами связи). Использует, главным образом, математический аппарат теории вероятностей и математической статистики.

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

Содержание

История

Применение

Достижения и методы теории информации широко используются в

См. также

Примечания

Библиография

Ссылки

Связь
Кибернетика
Теория информации

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое "Теория информации" в других словарях:

ТЕОРИЯ ИНФОРМАЦИИ — наука о статистич. процессах передачи информации в техн., природных и социальных системах. Осн. понятия Т … Физическая энциклопедия

ТЕОРИЯ ИНФОРМАЦИИ — ТЕОРИЯ ИНФОРМАЦИИ, математическая дисциплина, изучающая законы, которые управляют каналами коммуникации. Главным образом она имеет дело с измерением количества информации, методами ее кодирования, передачи, хранения и обработки. Некоторые понятия … Научно-технический энциклопедический словарь

ТЕОРИЯ ИНФОРМАЦИИ — теория, изучающая законы и способы измерения, преобразования, передачи, использования и хранения информации. В Т. и. и ее технич. приложениях центральными являются понятия количества информации и его меры. Эти понятия в известной степени… … Философская энциклопедия

ТЕОРИЯ ИНФОРМАЦИИ — 4.11. ТЕОРИЯ ИНФОРМАЦИИ Отрасль науки, занимающаяся изучением мер информации и их свойств СТ ИСО 2382/16 Источник: РМ 4 239 91: Системы автоматизации. Словарь справочник по терминам. Пособие к СНиП 3.05.07 85 … Словарь-справочник терминов нормативно-технической документации

теория информации — informacijos teorija statusas T sritis automatika atitikmenys: angl. information theory vok. Informationstheorie, f rus. теория информации, f pranc. théorie de l information … Automatikos terminų žodynas

теория информации — informacijos teorija statusas T sritis fizika atitikmenys: angl. information theory vok. Informationstheorie, f rus. теория информации, f pranc. théorie de l’information, f … Fizikos terminų žodynas

Это не столько о самой информации, сколько о передаче информации. То есть о коммуникации.

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

1. Единая структура коммуникации

Следует отметить, что информация в теории Шеннона НЕ равнозначна смыслу. Безнадежный бред, например, это тоже информация, потому что человек, слышащий ее, не знал этого раньше. То же самое с честным броском монеты.

2. Как передавать больше информации и быстрее

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

Как же бороться с шумом и снизить риск сбоя связи? Добавляя избыточность обратно !

ИНФОРМАЦИИ ТЕОРИЯ – раздел математики, исследующий процессы хранения, преобразования и передачи информации. В основе его лежит определенный способ измерения количества информации. Возникшая из задач теории связи, теория информации иногда рассматривается как математическая теория систем передачи информации. Опираясь на основополагающую работу К.Шеннона (1948), теория информации устанавливает основные границы возможностей систем передачи информации, задает исходные принципы их разработки и практического воплощения. В настоящей статье рассматривается ядро теории информации – свойства информационных мер и их приложения к анализу систем передачи информации.

Кодирование.

Источник информации можно представить в виде случайной величины X, принимающей одно из конечного числа возможных значений m> с вероятностью p_i (p_i – вероятность того, что X = i). Энтропия случайной величины X по определению равна

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

Рассмотрим случайную величину X, принимающую значения a, b, c> с вероятностями ( 1 /₂, 1 /₄, 1 /₄). Код для этой случайной величины мог бы иметь вид (0, 10, 11). Увидев строку 01001110, получатель мог бы однозначно разбить ее на 0, 10, 0, 11, 10, что декодируется в строку a, b, a, c, b>, причем необходимости в специальном символе для обозначения конца кодированного слова не возникает. Заметим, что средняя длина такого кода составляет ( 1 /₂ ×1) + ( 1 /₄ ×2) + ( 1 /₄ ×2) = 1,5 бита, т.е. совпадает с энтропией источника.

Один из основных результатов теории информации связан с теоремой, согласно которой выборочную случайную величину можно представить без ошибки с помощью H + 1 бита и невозможно представить источник без ошибки с помощью менее, чем H битов. Отсюда следует, что энтропия является фундаментальным ограничением для представления источника информации, и мы можем найти представления со средней длиной в пределах одного бита энтропии. Оптимальное представление случайной величины (в терминах средней длины) может быть найдено с помощью алгоритма Хаффмана. Этот алгоритм позволяет строить коды для источников с энтропией, не превышающей одного бита.

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

Для простоты предположим, что английский алфавит состоит из 26 букв и одного пробела. В простейшей модели все знаки равновероятны. Можно показать, что энтропия такой модели равна log 27 = 4,76 бита на букву. Но в реальном английском языке буквы не равновероятны (например, буква E встречается с большей вероятностью, чем Q). Используя относительные частоты различных букв для вычисления энтропии, мы получили бы оценку около 4,03 бита на букву. Таков был бы коэффициент энтропии, если бы буквы английского алфавита встречались независимо друг от друга.

Но это не так. Например, за буквой Q почти всегда следует U, и т.д. Воспользовавшись условными распределениями, мы могли бы построить более точную оценку коэффициента энтропии английского языка. Например, если воспользоваться моделью, в которой каждая буква зависит только от предыдущей, то получится оценка примерно в 3,3 бита на букву. Рассматривая распределение букв, которое зависит от трех предыдущих букв, мы получаем оценку примерно в 2,8 бита на букву.

Однако всю сложность зависимостей, существующих в реальном английском языке, ни одна из этих моделей полностью не передает. Зато играя в игру, аналогичную игре в 20 вопросов, и состоящую в угадывании следующей буквы, можно получить гораздо более точные оценки коэффициента энтропии английского языка. Эксперименты с образцами английских текстов показывают, что коэффициент энтропии немного больше, чем 1 бит на букву. Это означает, что в английском языке существует значительная избыточность, которую можно устранить с помощью подходящего кодирования. Например, не составляет никакого труда декодировать следующее английское предложение:

TH. . R. . S . NLY . N. W. Y

T. F. LL . N TH. V. W. LS

IS ONLY ONE WAY

FILL IN THE VOWELS

Сложность по Колмогорову.

Каналы связи.

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

Вместо того, чтобы заниматься конкретными деталями той или иной системы связи, мы можем построить ее общую модель. Это делается заданием списков возможных входных и выходных символов, а также функции распределения вероятностей, указывающей вероятность различных возможных выходных символов для каждого возможного входного символа. В простейшем случае выходной сигнал канала равен входному сигналу, и любая поступающая на вход информация без ошибок передается на выход. Например, если бы у нас был канал, который мог бы передавать два символа, и оба они принимались на выходе без ошибки (рис. 2), то с каждым символом мы могли бы передавать один бит информации. Такие каналы получили название каналов без шума. Их пропускная способность равна максимальному количеству информации, которое может поступить на вход. Если канал имеет N возможных входных символов, то его пропускная способность равна log N битов за передачу. Если такой канал может передавать 1 символ в секунду, то его пропускная способность равна log N битов в секунду.

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

Поскольку теорема Шеннона о пропускной способности канала связи в чем-то противоречит нашей интуиции, попытаемся понять, почему эта теорема верна. Рассмотрим канал, изображенный на рис. 4. В этом канале существует 10 возможных входных символов, обозначенных цифрами 0, 1, 2, ј , 9, и десять возможных выходных символов. Каждый входной символ с равной вероятностью порождает выходной символ, обозначенный либо той же цифрой, либо на единицу больше. Например, цифра 3 на входе с равной вероятностью порождает на выходе 3 или 4, а цифра 9, соответственно, – 9 или 0. Поэтому, обнаруживая на выходе канала цифру 5, мы не можем однозначно утверждать, была ли передана цифра 5 или 4.

Если мы ограничим множество входных символов четными числами, т.е. 0, 2, 4, 6 и 8, то при любом выходном символе без всякой неопределенности или ошибки сможем указать соответствующий входной символ. Таким образом, используя лишь некоторое подмножество возможных входных символов, мы можем передавать информацию без ошибок. Скорость, с которой мы можем передавать информацию по этому каналу, равна log 5 битов на передачу. Можно показать, что эта скорость оптимальна и совпадает с пропускной способностью канала, изображенного на рис. 4.

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

Такой непрерывный канал служит полезной моделью многих широко используемых на практике каналов радио- и телефонной связи.

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

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

Шеннон К. Работы по теории информации и кибернетике. М., 1963
Колмогоров А.Н. Проблемы передачи информации. М., 1965
Яглом А.М., Яглом И.М. Вероятность и информация. М., 1973
Галлагер Р. Теория информации и надежная связь. М., 1974
Чисар И., Кернер Я. Теория информации: теоремы кодирования для дискретных систем без памяти. М., 1985

Как звали математика, который в 19 лет решил задачу, не поддававшуюся усилиям лучших геометров со времен Евклида?

Читайте также: