Как вы понимаете что такое теория информации
Теория информации
Основные разделы теории информации — кодирование источника (сжимающее кодирование) и канальное (помехоустойчивое) кодирование. Теория информации тесно связана с криптографией и другими смежными дисциплинами.
Содержание
История
Клода Шеннона (1916—2001) называют [2] «отцом теории информации». Разработанная им теория дала инженерам-разработчикам систем передачи данных возможность определения ёмкости коммуникационного канала. Часть теории, изучающей передачу информации, не занимается значением (семантикой) передаваемого сообщения, однако дополняющая часть теории информации обращает внимание на содержимое через сжатие с потерями субъекта сообщения, используя критерий точности.
Применение
Достижения и методы теории информации широко используются в
См. также
Примечания
Библиография
Ссылки
Полезное
Смотреть что такое «Теория информации» в других словарях:
ТЕОРИЯ ИНФОРМАЦИИ — наука о статистич. процессах передачи информации в техн., природных и социальных системах. Осн. понятия Т … Физическая энциклопедия
теория информации — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] теория информации Или математическая теория связи — раздел кибернетики, исследующий процессы хранения, преобразования и передачи информации; это основная часть… … Справочник технического переводчика
Теория информации — [information theory], или математическая теория связи раздел кибернетики, исследующий процессы хранения, преобразования и передачи информации; это основная часть кибернетики, поэтому последнюю тоже иногда называют «теорией информации» … Экономико-математический словарь
ТЕОРИЯ ИНФОРМАЦИИ — ТЕОРИЯ ИНФОРМАЦИИ, математическая дисциплина, изучающая законы, которые управляют каналами коммуникации. Главным образом она имеет дело с измерением количества информации, методами ее кодирования, передачи, хранения и обработки. Некоторые понятия … Научно-технический энциклопедический словарь
ТЕОРИЯ ИНФОРМАЦИИ — теория, изучающая законы и способы измерения, преобразования, передачи, использования и хранения информации. В Т. и. и ее технич. приложениях центральными являются понятия количества информации и его меры. Эти понятия в известной степени… … Философская энциклопедия
ТЕОРИЯ ИНФОРМАЦИИ — 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
ТЕОРИЯ ИНФОРМАЦИИ — в узком смысле математич. теория передачи сообщений в системах связи (телефон, телеграф и т. п.), возникшая на базе основополагающих трудов К. Шеннона (США). Основана на следующих представлениях: сообщения (точнее, их коды) поступают из источника … Российская социологическая энциклопедия
ТЕОРИЯ ИНФОРМАЦИИ — наука, изучающая свойства, количественные характеристики и методы кодирования информации. В основе Т. и. лежит определенный способ измерения количества информации, содержащейся в какихлибо данных (сообщениях). Наиболее развита статистическая Т. и … Энциклопедический словарь по психологии и педагогике
Ричард Хэмминг: Глава 13. Теория информации
«Цель этого курса — подготовить вас к вашему техническому будущему.»
Привет, Хабр. Помните офигенную статью «Вы и ваша работа» (+219, 2588 в закладки, 429k прочтений)?
Так вот у Хэмминга (да, да, самоконтролирующиеся и самокорректирующиеся коды Хэмминга) есть целая книга, написанная по мотивам его лекций. Мы ее переводим, ведь мужик дело говорит.
Это книга не просто про ИТ, это книга про стиль мышления невероятно крутых людей. «Это не просто заряд положительного мышления; в ней описаны условия, которые увеличивают шансы сделать великую работу.»
За перевод спасибо Андрею Пахомову.
Теория Информации была разработана К. Э. Шенноном в конце 1940х годов. Руководство Лабораторий Белла настаивало, чтобы он назвал ее «Теория Связи», т.к. это намного более точное название. По очевидным причинам, название «Теория Информации» обладает значительно большим воздействием на публику, поэтому Шеннон выбрал именно его, и именно оно известно нам по сей день. Само название предполагает, что теория имеет дело с информацией, это и делает ее важной, поскольку мы все глубже проникаем в информационную эпоху. В этой главе я затрону несколько основных выводов из этой теории, приведу не строгие, а скорее интуитивно понятные доказательства некоторых отдельных положений этой теории, чтобы вы поняли, чем на самом деле является «Теория Информации», где вы можете ее применять, а где нет.
Прежде всего, что такое “информация”? Шеннон отождествляет информацию с неопределенностью. Он выбрал отрицательный логарифм вероятности события в качестве количественной меры информации, которую вы получаете при наступлении события с вероятностью p. Например, если я скажу вам, что в Лос-Анжелесе туманная погода, тогда р близок к 1, что по большому счету, не дает нам много информации. Но если я скажу, что в июне в Монтерей идет дождь, то в этом сообщении будет присутствовать неопределенность, и оно будет содержать в себе больше информации. Достоверное событие не содержит в себе никакой информации, поскольку log 1 = 0.
Остановимся на этом подробнее. Шеннон полагал, что количественная мера информации должна быть непрерывной функцией от вероятности события p, а для независимых событий она должна быть аддитивной – количество информации, полученное в результате осуществления двух независимых событий, должно равняться количеству информации, полученному в результате осуществления совместного события. Например, результат броска игральных костей и монеты обычно рассматриваются как независимые события. Переведем вышесказанное на язык математики. Если I (p) – это количество информации, которое содержится в событии с вероятностью p, то, для совместного события, состоящего из двух независимых событий x с вероятностью p1 и y с вероятностью p2 получаем
(x и y независимые события)
Это функциональное уравнение Коши, истинное для всех p1 и p2. Для решения этого функционального уравнения предположим, что
Если p1 = p 2 и p2 = p, тогда
и т.д. Расширяя этот процесс, используя стандартный метод для экспонент, для всех рациональных чисел m / n, верно следующее
Из предполагаемой непрерывности информационной меры, следует, что логарифмическая функция является единственным непрерывным решением функционального уравнения Коши.
В теории информации принято принимать основание логарифма равное 2, поэтому бинарный выбор содержит ровно 1 бит информации. Следовательно, информация измеряется по формуле
Давайте приостановимся и разберемся, что же произошло выше. Прежде всего, мы так и не дали определение понятию “информация”, мы просто определили формулу ее количественной меры.
Во-вторых, эта мера зависит от неопределенности, и, хотя она в достаточной степени подходит для машин — например, телефонных системы, радио, телевидения, компьютеров и т. д. — она не отражает нормального человеческого отношения к информации.
В-третьих, это относительная мера, она зависит от текущего состояния вашего знания. Если вы смотрите на поток “случайных чисел” из генератора случайных чисел, вы предполагаете, что каждое следующее число неопределенно, но, если вы знаете формулу для вычисления «случайных чисел», следующее число будет известно, и, соответственно, не будет содержать в себе информации.
Таким образом, определение, данное Шенноном для информации, во многих случаях подходит для машин, но, похоже, не соответствует человеческому пониманию этого слова. Именно по этой причине «Теорию информации» следовало назвать «Теорией связи». Тем не менее, уже слишком поздно чтобы менять определения (благодаря которым теория приобрела свою первоначальную популярность, и которые все еще заставляют людей думать, что эта теория имеет дело с «информацией»), поэтому мы вынуждены с ними смириться, но при этом вы должны чётко понимать, насколько определение информации, данное Шенноном, далеко от своего общеупотребительного смысла. Информация Шеннона имеет дело с чем-то совершенно другим, а именно с неопределенностью.
Вот о чем нужно подумать, когда вы предлагаете какую-либо терминологию. Насколько предложенное определение, например, определение информации данное Шенноном, согласуется с вашей первоначальной идеей и насколько оно отличается? Почти нет термина, который бы в точности отражал ваше ранее видение концепции, но в конечном итоге, именно используемая терминология отражает смысл концепции, поэтому формализация чего-то посредством чётких определений всегда вносит некоторый шум.
Рассмотрим систему, алфавит которой состоит из символов q с вероятностями pi. В этом случае среднее количество информации в системе (её ожидаемое значение) равно:
Это называется энтропией системы с распределением вероятности
Энтропия распределения вероятности играет главную роль в теории кодирования. Неравенство Гиббса для двух разных распределений вероятности pi и qi является одним из важных следствий этой теории. Итак, мы должны доказать, что
Доказательство опирается на очевидный график, рис. 13.I, который показывает, что
а равенство достигается только при x = 1. Применим неравенство к каждому слагаемому суммы из левой части:
Если алфавит системы связи состоит из q символов, то принимая вероятность передачи каждого символа qi = 1/q и подставляя q, получаем из неравенства Гиббса
Это говорит о том, что если вероятность передачи всех q символов одинакова и равна — 1 / q, то максимальная энтропия равна ln q, в противном случае выполняется неравенство.
В случае однозначно декодируемого кода, мы имеем неравенство Крафта
Теперь если мы определим псевдовероятности
где конечно 
= 1, что следует из неравенства Гиббса,
и применим немного алгебры (помните, что K ≤ 1, поэтому мы можем опустить логарифмический член, и возможно, усилить неравенство позже), то получим
где L — это средняя длина кода.
Таким образом, энтропия является минимальной границей для любого посимвольного кода со средней длиной кодового слова L. Это теорема Шеннона для канала без помех.
Теперь рассмотрим главную теорему об ограничениях систем связи, в которых информация передаётся в виде потока независимых бит и присутствует шум. Подразумевается, что вероятность корректной передачи одного бита P > 1 / 2, а вероятность того, что значение бита будет инвертировано при передачи (произойдет ошибка) равняется Q = 1 — P. Для удобства предположим, что ошибки независимы и вероятность ошибки одинакова для каждого отправленного бита — то есть в канале связи присутствует «белый шум».
Путь мы имеем длинный поток из n бит, закодированные в одно сообщение — n — мерное расширение однобитового кода. Значение n мы определим позже. Рассмотрим сообщение, состоящее из n-битов как точку в n-мерном пространстве. Поскольку у нас есть n-мерное пространство — и для простоты будем предполагать, что каждое сообщение имеет одинаковую вероятность возникновения — существует M возможных сообщений (M также будет определено позже), следовательно, вероятность любого оправленного сообщения равняется
(отправитель)
График 13.II
Далее рассмотрим идею о пропускной способности канала. Не вдаваясь в подробности, пропускная способность канала определяется как максимальный объем информации, который может быть надежно передан по каналу связи, с учётом использования максимально эффективного кодирования. Нет доводов в пользу того, что через канал связи может быть передано больше информации, чем его емкость. Это можно доказать для бинарного симметричного канала (который мы используем в нашем случае). Емкость канала, при побитовой отправки, задается как
где, как и раньше, P — вероятность отсутствия ошибки в любом отправленном бите. При отправке n независимых битов емкость канала определяется как
когда мы отправляем какое-либо из М равновероятных сообщений ai, мы имеем
При отправке n бит мы ожидаем возникновение nQ ошибок. На практике, для сообщения состоящего из n-бит, мы будем иметь приблизительно nQ ошибок в полученном сообщении. При больших n, относительная вариация ( вариация = ширина распределения, )
распределения числа ошибок будет все более узкой с ростом n.
Итак, со стороны передатчика, я беру сообщение ai для отправки и рисую сферу вокруг него радиусом
который немного больше на величину равную e2, чем ожидаемое число ошибок Q, (рисунок 13.II). Если n достаточно велико, то существует сколь угодно малая вероятность появления точки сообщения bj на стороне приемника, которая выходит за пределы этой сферы. Зарисуем ситуацию, как вижу ее я с точки зрения передатчика: мы имеем любые радиусы от переданного сообщения ai к полученному сообщению bj с вероятностью ошибки равной (или почти равной) нормальному распределению, достигающего максимума в nQ. Для любого заданного e2 существует n настолько большое, что вероятность того, что полученная точка bj, выходящая за пределы моей сферы, будет настолько малой, насколько вам будет угодно.
Теперь рассмотрим эту же ситуацию с вашей стороны (рис. 13.III). На стороне приемника есть сфера S( r) того же радиуса r вокруг принятой точки bj в n-мерном пространстве, такая, что если принятое сообщение bj находится внутри моей сферы, тогда отправленное мной сообщение ai находится внутри вашей сферы.
Как может возникнуть ошибка? Ошибка может произойти в случаях, описанных в таблице ниже:
Здесь мы видим, что, если в сфере построенной вокруг принятой точки существует еще хотя бы еще одна точка, соответствующая возможному отправленному не закодированному сообщению, то при передачи произошла ошибка, так как вы не можете определить какое именно из этих сообщений было передано. Отправленное сообщение не содержит ошибки, только если точка, соответствующая ему, находится в сфере, и не существует других точек, возможных в данном коде, которые находятся в той же сфере.
Мы имеет математическое уравнение для вероятности ошибки Ре, если было отправлено сообщение ai
Мы можем выбросить первый множитель во втором слагаемом, приняв его за 1. Таким образом получим неравенство
повторно применяем к последнему члену справа
Приняв n достаточно большим, первый член может быть принят сколь угодно малым, скажем, меньше некоторого числа d. Поэтому мы имеем
Теперь рассмотрим, как можно построить код простой замены для кодирования M сообщений, состоящих из n бит. Не имея представления о том, как именно строить код (коды с коррекцией ошибки еще не были изобретены), Шеннон выбрал случайное кодирование. Подбросьте монетку для каждого из n битов в сообщении и повторите процесс для М сообщений. Всего нужно сделать nM бросков монеты, поэтому возможны
кодовых словарей, имеющие одинаковую вероятность ½nM. Конечно, случайный процесс создания кодового словаря означает, что есть вероятность появления дубликатов, а также кодовых точек, которые будут близки друг к другу и, следовательно, будут источником вероятных ошибок. Нужно доказать, что если это не происходит с вероятностью выше, чем любой небольшой выбранный уровень ошибки, то заданное n достаточно велико.
Решающим момент заключается в том, что Шеннон усреднил все возможные кодовые книги, чтобы найти среднюю ошибку! Мы будем использовать символ Av [.], чтобы обозначить среднее значение по множеству всех возможных случайных кодовых словарей. Усреднение по константе d, конечно, дает константу, так как для усреднения каждый член совпадает с любым другим членом в сумме,
который может быть увеличен (M–1 переходит в M )
Для любого конкретного сообщения, при усреднении всех кодовых книг, кодирование пробегает все возможные значения, поэтому средняя вероятность того, что точка находится в сфере, — это отношение объема сферы к общему объему пространства. Объем сферы при этом
где s=Q+e2 Содержание книги и переведенные главы
ИНФОРМАЦИИ ТЕОРИЯ
ИНФОРМАЦИИ ТЕОРИЯ – раздел математики, исследующий процессы хранения, преобразования и передачи информации. В основе его лежит определенный способ измерения количества информации. Возникшая из задач теории связи, теория информации иногда рассматривается как математическая теория систем передачи информации. Опираясь на основополагающую работу К.Шеннона (1948), теория информации устанавливает основные границы возможностей систем передачи информации, задает исходные принципы их разработки и практического воплощения. В настоящей статье рассматривается ядро теории информации – свойства информационных мер и их приложения к анализу систем передачи информации.
Основные свойства информации можно описать с помощью математической модели, отражающей многие характерные особенности информационной меры, как она обычно понимается на интуитивном уровне. Источник информации и канал связи, по которому передается информация, можно моделировать, используя вероятностные представления. Энтропия источника информации равна логарифму (эффективного) числа сообщений, которые он порождает. Это – мера сложности описания источника (или, как иногда говорят, мера неопределенности сообщения). Такое понимание энтропии тесно связано с понятием энтропии, используемым в термодинамике (см. также ТЕРМОДИНАМИКА).
Физически передачу информации можно представить как индуцирование в приемном устройстве требуемого физического состояния. Отправитель намерен передать сообщение получателю. Суть передачи заключается в воспроизведении на выходе канала связи переданного сообщения. В момент передачи отправитель выбирает нужное сообщение из списка всех возможных сообщений. Получатель заранее не знает, какое из них будет выбрано. (Если бы он был об этом заранее информирован, то никакой необходимости посылать сообщение не было бы.) Канал связи вносит в процесс передачи информации случайный шум, который искажает сообщение и тем самым затрудняет его прочтение. В начале процесса связи получатель находится в полной неопределенности относительно того, какое сообщение выбрано из списка возможных. К концу связи получателю становится это известно, т.е. становится известно точное описание выбранного сообщения.
Способность канала связи передавать информацию характеризуется некоторым числом – пропускной способностью (емкостью), равной логарифму эффективного числа сообщений, различимых на его выходе. Процесс передачи информации можно считать надежным, если скорость передачи сообщений меньше пропускной способности канала. В противном случае надежная передача информации оказывается невозможной. Основной результат теории информации состоит в утверждении: если энтропия источника меньше пропускной способности канала, то на его выходе исходное сообщение может быть воспроизведено со сколь угодно малой ошибкой; если же энтропия источника превышает его пропускную способность, то ошибку сделать малой невозможно.
Трудность передачи сообщения не зависит от его содержания; передавать бессмысленные сообщения не менее трудно, чем осмысленные. Например, число 23 в одном контексте может быть ценой одного барреля нефти, а в другом – номером победителя заезда на скачках. Смысл сообщения зависит от контекста и семантики, а трудность его передачи определяется только перечнем возможных сообщений (и их вероятностей).
Любую систему передачи информации можно считать состоящей из трех частей: источника сообщений, канала связи и приемного устройства (рис. 1). Например, при разговоре по телефону источником является говорящий, сообщением – его речь. Каналом связи служат провода, передающие электрический сигнал от говорящего к слушателю – получателю сообщения.
Между отправителем сообщения и каналом связи могут находиться устройства (обозначенные на рис. 1 как кодирующие), преобразующие сообщение в форму, удобную для передачи по каналу связи. Декодирующее устройство, установленное на другом конце канала, восстанавливает принятое сообщение.
Изучение систем передачи информации мы начнем с источника сообщений. По каналу связи может передаваться самая различная информация: текст, живая речь, музыка или изображения. Для каждого источника можно указать перечень сообщений, которые он может генерировать. Например, источник телеграфных или телексных сообщений передает только буквы и не содержит, скажем, нотных знаков. Если по каналу связи передается живая речь, то сигнал лишается полезного содержания при частоте выше 20 000 Гц, верхнего предела, воспринимаемого человеческим слухом. Этими фактами можно воспользоваться при проектировании входа канала связи.
Кодирование.
Моделью источника информации может служить генератор последовательности случайных величин. Следовательно, генерируемые сообщения можно рассматривать как исходы некоторого случайного испытания, вроде бросания игральной кости. Первоначально мы будем предполагать, что список возможных сообщений и их вероятности известны.
Простейший список возможных сообщений состоит из двух сообщений. Чтобы передать одно из них, необходим символ, принимающий два значения. Количество информации, которую может передать источник, содержащий два равновероятных сообщения, называется битом и служит основной единицей измерения информации. Символ, представляющий такое количество информации, обычно является двоичной цифрой, 0 или 1. Один бит позволяет различать две равновероятные возможности (0, 1), два бита позволяют различать четыре возможности (00, 01, 10, 11), и т.д. Если число равновероятных возможностей равно N, то количество информации, необходимое для представления одной из них, равно log2N битов. Например, чтобы передать одно из 32 возможных сообщений, отправитель мог бы послать получателю последовательность из log232 = 5 битов. Эта последовательность из 5 двоичных знаков сообщит получателю, какое из 32 возможных сообщений было передано.
Другой подход к той же проблеме можно пояснить на примере игры в 20 вопросов. Один из участников игры задумывает нечто, а другой пытается это отгадать с помощью 20 вопросов, допускающих ответы только типа «да – нет». Предположим, например, что первый из участников игры задумывает «Чарлз Диккенс». Второй участник игры может задать вопрос: «Это реальное лицо?», а затем спросить: «Этот человек жив?» и т.д. С каждым вопросом число вариантов отгадки уменьшается до тех пор, пока задуманное не будет идентифицировано. На языке теории информации можно сказать, что второй участник игры (отгадывающий задуманное) с каждым вопросом может получать самое большее один бит информации. С помощью 20 вопросов он может различить самое большее 2 20 (т.е. приблизительно миллион) различных объектов.
Если заранее известно, что первый участник игры более чем в половине случаев задумывает «Уильяма Шекспира», то имеет смысл, задавая первый вопрос, спросить: «Это Уильям Шекспир?» Более чем в половине случаев отгадка будет найдена с помощью одного вопроса, и поэтому в среднем число вопросов окажется меньше, чем в описанной выше процедуре. Таким образом, если возможные ответы не равновероятны, то для идентификации наиболее вероятных кандидатов разумнее использовать более короткие последовательности вопросов (и, соответственно, более длинные для идентификации менее вероятных кандидатов).
Точно также и не всегда равновероятны сообщения, порождаемые источниками информации. Если одно сообщение имеет намного более высокую вероятность, чем другие, то для его идентификации мы можем использовать более короткое представление и более длинные – для других, менее вероятных. Предположим, например, что источник генерирует одно из четырех сообщений A, B, C и D с вероятностями 1 /2, 1 /4, 1 /8 и 1 /8. Каждое сообщение из этого списка можно было бы представить кодовым словом в два бита (например, представить A кодовым словом 00, B – кодовым словом 01, C – кодовым словом 10 и D – кодовым словом 11). Средняя длина такого представления составляет два бита. Мы могли бы также представить сообщение A кодовым словом 0, B – кодовым словом 10, C – кодовым словом 110 и D – кодовым словом 111. Приняв на выходе некоторую последовательность битов, получатель может решить, какое из четырех сообщений было передано. Средняя длина такого представления равна ( 1 /2 ×1) + ( 1 /4 ×2) + ( 1 /8×3) + ( 1 /8×3) = 1,75 бита. Таким образом, представление с переменной длиной кодовых слов в среднем оказывается короче, и при его достаточно продолжительном использовании мы сэкономили бы биты (1,75 по сравнению с 2). В какой-то степени это согласование имеется уже в коде Морзе, где чаще встречающиеся буквы обозначаются более короткими комбинациями точек и тире. Минимальная средняя длина представления ограничена некоторой фундаментальной величиной, называемой энтропией источника.
где логарифмы берутся по основанию 2 и энтропия измеряется в битах. Такое определение энтропии связано с определением энтропии в термодинамике. Энтропия устанавливает нижнюю границу средней длины любого двоичного представления случайной величины.
Рассмотрим случайную величину X, принимающую значения <a, b, c> с вероятностями ( 1 /2, 1 /4, 1 /4). Код для этой случайной величины мог бы иметь вид (0, 10, 11). Увидев строку 01001110, получатель мог бы однозначно разбить ее на 0, 10, 0, 11, 10, что декодируется в строку <a, b, a, c, b>, причем необходимости в специальном символе для обозначения конца кодированного слова не возникает. Заметим, что средняя длина такого кода составляет ( 1 /2 ×1) + ( 1 /4 ×2) + ( 1 /4 ×2) = 1,5 бита, т.е. совпадает с энтропией источника.
Так же, как мы определили энтропию одной случайной величины, можно определить энтропию последовательности, или множества, случайных величин. Коэффициент энтропии такой последовательности равен пределу отношения энтропии последовательности к числу элементов этой последовательности и называется энтропией сообщения на символ. Если случайные величины коррелированы, то энтропия последовательности меньше суммы энтропий ее элементов.
Один из основных результатов теории информации связан с теоремой, согласно которой выборочную случайную величину можно представить без ошибки с помощью H + 1 бита и невозможно представить источник без ошибки с помощью менее, чем H битов. Отсюда следует, что энтропия является фундаментальным ограничением для представления источника информации, и мы можем найти представления со средней длиной в пределах одного бита энтропии. Оптимальное представление случайной величины (в терминах средней длины) может быть найдено с помощью алгоритма Хаффмана. Этот алгоритм позволяет строить коды для источников с энтропией, не превышающей одного бита.
Теоретически можно вычислить коэффициент энтропии случайного процесса, моделирующего источник информации, а затем найти представления, не превышающие один бит энтропии. Однако многие встречающиеся на практике источники информации обладают структурой, которую очень трудно представить в рамках простой модели. Примером источника, который исследовали многие авторы, служит английский текст. Попытаемся оценить коэффициент энтропии английского языка с помощью различных моделей.
Для простоты предположим, что английский алфавит состоит из 26 букв и одного пробела. В простейшей модели все знаки равновероятны. Можно показать, что энтропия такой модели равна log 27 = 4,76 бита на букву. Но в реальном английском языке буквы не равновероятны (например, буква E встречается с большей вероятностью, чем Q). Используя относительные частоты различных букв для вычисления энтропии, мы получили бы оценку около 4,03 бита на букву. Таков был бы коэффициент энтропии, если бы буквы английского алфавита встречались независимо друг от друга.
Но это не так. Например, за буквой Q почти всегда следует U, и т.д. Воспользовавшись условными распределениями, мы могли бы построить более точную оценку коэффициента энтропии английского языка. Например, если воспользоваться моделью, в которой каждая буква зависит только от предыдущей, то получится оценка примерно в 3,3 бита на букву. Рассматривая распределение букв, которое зависит от трех предыдущих букв, мы получаем оценку примерно в 2,8 бита на букву.
Однако всю сложность зависимостей, существующих в реальном английском языке, ни одна из этих моделей полностью не передает. Зато играя в игру, аналогичную игре в 20 вопросов, и состоящую в угадывании следующей буквы, можно получить гораздо более точные оценки коэффициента энтропии английского языка. Эксперименты с образцами английских текстов показывают, что коэффициент энтропии немного больше, чем 1 бит на букву. Это означает, что в английском языке существует значительная избыточность, которую можно устранить с помощью подходящего кодирования. Например, не составляет никакого труда декодировать следующее английское предложение:
FILL IN THE VOWELS
хотя почти половина букв отсутствует. Как показывают оценки коэффициента энтропии, английский язык, вообще говоря, допускает примерно четырехкратное сжатие, если воспользоваться для этого идеальным сжимающим алгоритмом. Например, 300-страничное издание Повести о двух городах Чарлза Диккенса можно было бы сократить до объема в 75 страниц такой же печати. Разумеется, в сжатом варианте буквы алфавита от A до Z использовались бы примерно одинаковое число раз, поэтому сжатый текст мог бы выглядеть, как «ZQRRLEW ј ». Тем не менее механизм «растяжения» позволил бы восстановить первоначальный текст Повести о двух городах слово в слово.
Непосредственное применение алгоритма Хаффмана для нахождения оптимального кода требует знания характерного для данного источника информации распределения вероятностей. Однако во многих случаях, как и в примере с английским языком, распределение вероятностей либо неизвестно, либо слишком сложно для того, чтобы его можно было использовать для кодирования. Но и в этих случаях можно придумать такие алгоритмы, которые восстанавливают распределение вероятностей по эмпирическим данным, а затем используют полученную информацию для сжатия данных. Такие алгоритмы называются универсальными. Широко известным примером может служить алгоритм Лемпеля – Зива, который не требует знания статистики источника информации и тем не менее асимптотически оптимален (см. ниже). Основная идея заключается в составлении словаря или таблицы, часто встречающихся фраз и в представлении новых фраз по их префиксам в таблице. Последовательность букв прежде всего необходимо разбить на последовательности, не встречавшиеся ранее. Например, двоичную строку 11010011011100 мы разбиваем на последовательности 1, 10, 100, 11, 0, 111, 00. Затем вместо того, чтобы передавать биты каждой фразы, мы передаем указатель фразы и значение ее последнего бита. Например, если мы используем для указателя три бита, то нашу исходную строку представляем последовательностью (000, 1), (001, 0), (010, 0), (001, 1), (000, 0), (100, 1), (101, 0) и т.д. Самое удивительное заключается в том, что, как показали А.Лемпель и Я.Зив, для всех «хороших» источников информации их алгоритм асимптотически оптимален в смысле сходимости коэффициента сжатия к энтропии. Таким образом, для всех достаточно длинных массивов алгоритм Лемпеля – Зива (не требующий никаких допущений относительно распределения вероятностей источника) позволяет достичь таких же результатов, как если бы мы заранее знали вероятностное распределение и построили для него оптимальный код.
Описанный алгоритм – лишь один из широкого класса аналогичных адаптивных алгоритмов, действующих на основе словаря и называемых алгоритмами Лемпеля – Зива. Они просты, обладают высоким быстродействием и реализуются как с помощью программного обеспечения, так и аппаратно. Их используют, чтобы «удвоить» емкость памяти для хранения данных или эффективную скорость передачи модема, поскольку в большинстве случаев они позволяют вдвое сжать английские тексты.
Сложность по Колмогорову.
Исходя из такого рода соображений, А.Н.Колмогоров определил сложность двоичной строки как длину кратчайшей программы для универсального компьютера, способной генерировать эту строку. (Такое представление о сложности независимо и почти одновременно предложили Г.Чайтин и Р.Соломонофф.) Универсальный компьютер можно рассматривать как машину Тьюринга, которая может моделировать любой другой универсальный компьютер. На первый взгляд кажется, что предложенное А.Н.Колмогоровым определение сложности бесполезно, поскольку зависит от возможностей конкретного компьютера. Но это не так, поскольку любой универсальный компьютер может моделировать любой другой универсальный компьютер, то любая программа, написанная для одного компьютера, может быть конвертирована в программу для другого компьютера путем добавления в качестве префикса «программы имитации», имеющей постоянную длину. Опираясь на эту идею, можно показать, что величина сложности по существу не зависит от компьютера. Внутренняя сложность описания любого объекта не зависит от компьютера или лица, описывающего данный объект. При некоторых предположениях можно доказать, что сложность по Колмогорову есть не что иное, как шенноновская энтропия. Иначе говоря, в среднем длина кратчайшей компьютерной программы, способной воспроизвести случайный объект, равна энтропии вероятностного распределения, из которого этот объект был извлечен. Сложность по Колмогорову предлагает единый подход к проблемам сжатия данных. Кроме того, она служит основой теории статистических выводов (бритва Оккама: «Простейшее объяснение – лучшее») и тесно связана с теорией вычислимости.
Каналы связи.
До сих пор мы рассматривали сложность описания источника информации и показали, что естественной мерой этой сложности служит коэффициент энтропии случайного процесса, моделирующего источник. Рассмотрим теперь проблему передачи этого описания по каналу связи. Примерами каналов связи могут служить телеграфные и телефонные провода, передающие информацию посредством электрических сигналов. В сотовых телефонах информация передается с помощью электромагнитного излучения.
Вместо того, чтобы заниматься конкретными деталями той или иной системы связи, мы можем построить ее общую модель. Это делается заданием списков возможных входных и выходных символов, а также функции распределения вероятностей, указывающей вероятность различных возможных выходных символов для каждого возможного входного символа. В простейшем случае выходной сигнал канала равен входному сигналу, и любая поступающая на вход информация без ошибок передается на выход. Например, если бы у нас был канал, который мог бы передавать два символа, и оба они принимались на выходе без ошибки (рис. 2), то с каждым символом мы могли бы передавать один бит информации. Такие каналы получили название каналов без шума. Их пропускная способность равна максимальному количеству информации, которое может поступить на вход. Если канал имеет N возможных входных символов, то его пропускная способность равна log N битов за передачу. Если такой канал может передавать 1 символ в секунду, то его пропускная способность равна log N битов в секунду.
Однако в общем случае сигналы на входе и выходе канала связи не совпадают. Рассмотрим, например, изображенный на рис. 3 канал связи с двумя входами и двумя выходами. Входами для этого канала служат символы «0» или «1». Если передается «0», то на выходе получатель видит в 90% случаев «0», а в 10% символ «1», что составляет ошибку в 10%. Следовательно, передав по каналу длинную последовательность битов, мы получим на выходе последовательность, в которой 10% двоичных цифр будут ошибочными. Если бы получатель знал, какие знаки неверны, их можно было бы исправить, заменив 0 на 1 и наоборот. Однако, поскольку такой информации у него нет, он может знать значение первого переданного по каналу бита не более, чем с 90%-й уверенностью.
Степень уверенности получателя можно повысить, повторяя сообщение. Например, мы можем трижды повторить передачу первого бита. Взглянув на трижды полученные биты, тот, кому они предназначены, «по большинству голосов» решает, какой именно двоичный знак был ему передан. Ошибиться он может только в том случае, если неверными были два или более битов. Вычисляя вероятность такого события, мы приходим к заключению, что получатель на этот раз будет ошибаться в 2,8% случаев. Увеличивая число повторений, мы можем и далее снижать вероятность ошибки.
Однако для этого нам понадобится все больше и больше сообщений. В результате скорость передачи информации снизится: например, если мы использовали 9 сообщений для передачи 1 бита, то она составит 1 /9 бита на передачу. До Шеннона инженеры-связисты полагали, что повторная передача сигнала – лучшее средство повышения ее надежности, т.е. для того, чтобы снизить вероятность ошибки, надо снизить скорость передачи информации. Но Шеннон в своей основополагающей статье показал, что снижать скорость передачи информации для этого совсем не обязательно. С каждым каналом связи связана некоторая критическая скорость передачи информации, называемая пропускной способностью, или емкостью, канала. Информацию можно передавать со сколь угодно малой вероятностью ошибки и с любой скоростью, если она меньше критической. Для скоростей, превышающих пропускную способность канала, вероятность ошибки не может быть малой, более того, с ростом длины используемого кода она приближается к 1.
В приведенном выше примере двоичного канала его пропускная способность составляет 0,53 бита на передачу. Таким образом, с помощью 100-кратного повторения мы можем передать по этому каналу 53 бита информации с пренебрежимо малой вероятностью ошибки.
Если мы ограничим множество входных символов четными числами, т.е. 0, 2, 4, 6 и 8, то при любом выходном символе без всякой неопределенности или ошибки сможем указать соответствующий входной символ. Таким образом, используя лишь некоторое подмножество возможных входных символов, мы можем передавать информацию без ошибок. Скорость, с которой мы можем передавать информацию по этому каналу, равна log 5 битов на передачу. Можно показать, что эта скорость оптимальна и совпадает с пропускной способностью канала, изображенного на рис. 4.
Таким образом, если считать, что при передаче длинной последовательности символов все каналы подобны каналу, изображенному на рис. 4, то теорема Шеннона может выглядеть интуитивно более оправданной. Длинная последовательность входных символов может порождать любую выходную последовательность, но по законам теории вероятностей скорее всего породит одну из небольшого множества условно «типичных» выходных последовательностей. Например, в двоичном симметричном канале входная последовательность длины n вероятнее всего породит одну из 2 nH (p) условно типичных последовательностей (где H (p) = –p log p – (1 – p) log (1 – p) и p – вероятность того, что «0» будет принят как «1» или наоборот). Так как всего существует 2 n возможных выходных последовательностей длины n, нетрудно показать, что можно выбрать ок. 2 n /2 nH (p) = 2 n (1 – H (p)) различных входных последовательностей (называемых кодовыми словами), таких, что их выходные варианты будут существенно неперекрывающимися (как на рис. 4), и, следовательно, получатель сможет различить эти последовательности с очень малой ошибкой. Таким образом, пропускная способность такого канала (скорость, с которой информация может быть передана по нему с пренебрежимо малой ошибкой) по существу равна 1 – H (p) битов на одну передачу.
В общем случае пропускная способность канала определяется разностью между безусловной энтропией выхода канала и условной энтропией канала с заданным входным сигналом. Эта величина называется взаимной информацией между входом и выходом канала; максимум взаимной информации по всем распределениям вероятностей входа является пропускной способностью канала. Если распределение вероятностей, которому подчиняется канал, известно, то эта величина может быть вычислена.
До сих пор мы рассматривали дискретные каналы связи. Это каналы, сигналы на входе и выходе которых представлены дискретными последовательностями символов. Однако во многих практически используемых устройствах передачи информации сигналы имеют вид непрерывно меняющихся функций времени. Важным примером здесь является гауссовский канал с заданной полосой пропускания, где параметры входного сигнала ограничены средней мощностью P ватт и спектром частот в некотором их диапазоне шириной W гц, а на выходе получается входной сигнал, искаженный шумом с плоским спектром частот, средней плотностью рассеиваемой мощности N ватт/гц и с гауссовым распределением вероятностей. В этом случае мы можем воспользоваться «теоремой отсчетов» и показать, что входной сигнал можно представить, взяв 2W его выборочных значений в секунду. Можно показать также, что пропускная способность такого канала определяется по формуле
Такой непрерывный канал служит полезной моделью многих широко используемых на практике каналов радио- и телефонной связи.
Коэффициент энтропии источника и пропускная способность канала связаны основной теоремой теории информации, которая гласит: кодирующие и декодирующие устройства, позволяющие безошибочно воссоздавать входной сигнал на выходе, могут быть построены в том и только в том случае, если коэффициент энтропии источника меньше пропускной способности канала. Теория информации ничего не говорит нам о том, как именно такие кодирующие и декодирующие устройства можно сконструировать, она лишь говорит о возможности их существования в принципе, если предположить, что их сложность может быть сколь угодно велика. Создание таких устройств составляет предмет теории кодирования, ставшей самостоятельной наукой со своими методами и важными результатами. Для создания практических кодирующих и декодирующих устройств были разработаны различные тонкие алгебраические методы. Широкому распространению таких кодов способствовали и успехи в развитии технологии интегральных схем. Например, в плейерах для проигрывания компакт-дисков используется один из видов кодов, исправляющих ошибки, который называется кодом Рида – Соломона и способен исправлять до 4000 следующих подряд ошибок.
Последние достижения в области теории информации несколько расширили понятия пропускной способности и сжатия данных на случай сетей каналов связи. Прогресс в теории кодирования позволил создавать модемы для телефонных каналов, вплотную приблизившие скорость передачи информации к их пропускной способности. Универсальные алгоритмы сжатия данных типа алгоритма Лемпеля – Зива ныне широко используются для сжатия компьютерных файлов. Теория информации остается активно развивающейся областью исследований, поставляющей в наш информационный век новые идеи и подходы в сферу проектирования и анализа систем передачи данных и компьютерных систем.
Шеннон К. Работы по теории информации и кибернетике. М., 1963
Колмогоров А.Н. Проблемы передачи информации. М., 1965
Яглом А.М., Яглом И.М. Вероятность и информация. М., 1973
Галлагер Р. Теория информации и надежная связь. М., 1974
Чисар И., Кернер Я. Теория информации: теоремы кодирования для дискретных систем без памяти. М., 1985