Лекции по теории информации МГУ (PDF.ZIP)
Лекции по теории алгоритмам на графах (PDF.ZIP)
Эффективная организация обмена информации приобретает все
большее значение как условие пешной практической деятельности людей. Объем
информации необходимый для нормального функционирования современного общества
растет примерно пропорционально квадрату развития промышленного потенциала. Доля
рабочей силы занятой вопросами обеспечения информацией начинает превышать долю
рабочей силы занятой непосредственно в производстве. Поэтому науки изучающие
структуру и закономерности протекания информационных процессов, к числу которых
относится и теория информации (ТИ) в такой ситуации становиться исключительно
актуальной. 1) информация приносит сведения, об окружающем мире которых
в рассматриваемой точке не было до ее получения;
Информация наряду с материей и энергией является первичным
понятием нашего мира и поэтому в строгом смысле не может быть определена. Можно
лишь перечислить ее основные свойства, например такие как:
2) информация не
материальна, но она проявляется в форме материальных носителей дискретных знаков
или первичных сигналах;
3) знаки и первичные сигналы несут информацию
только для получателя способного распознать.
Вместе с тем слово информация является одним из тех терминов,
которые достаточно часто встречаются не только в научных трудах специального
характера, нон и во множестве обиходных ситуаций и являются интуитивно понятными
каждому человеку. При этом в узком практическом смысле под информацией обычно
понимают совокупность сведений об
окружающем мире являющихся объектом хранения, передачи и
преобразования. 1) Непрерывный или аналоговый сигналы
Знаки или первичные сигналы, организованные в
последовательности несут информацию не потому, что они повторяют объекты
реального времени, а по общественной договоренности об однозначной связи знаков
и объектов, например: предметы и слова для их обозначения. Кроме того, первичные
сигналы могут быть порождены естественными законами реального мира, например:
напряжение на выходе термопары под действием температуры. Информация, основанная
на однозначной связи знаков или сигналов с объектами реального мира, называется
семантической или смысловой. Информация, заключенная в характере (порядке и
взаимосвязи) следования знаков сообщающей называется синтаксической. Также в
общей науке о знаках (семиотики) кроме перечисленных выделяют сигматический и
прагматический аспекты информации. В первом случае изучается вопрос о выборе
знаков для обозначения объектов реального мира, во втором случае о ценности
информации для достижения поставленных целей.
Очевидно, что наибольший
практический интерес представляют смысловой и семантический и прагматический
аспекты. Однако до сих пор не определены объективные количественные критерии
меры ценности и полезности информации. В курсе теории информации изучаются
проблемы синтаксического уровня касающихся создания теоретических основ
построения систем связи основные показатели функционирования, которых были бы
близки к предельно возможным.
Иначе говоря, рассмотрению подлежат вопросы
доставки получателю информации как совокупность из знаков. При этом
последовательностью игнорируются смысловое и прагматическое ее содержание.
Синтаксическая мера информации имеет практическую ценность потому, что
интересующая в конечном итоге получателя семантическая информация заключена в
заданной последовательности знаков или первичных сигналов. Чем больше знаков
передаются в определенный интервал времени, тем в среднем больше передается и
смысловой информации.
Теория информации представляет собой ветвь
статистической теории связи. Для того чтобы более конкретно обозначить предмет
этой науки введем некоторые понятия и определения.
Информация передается, и
храниться в виде сообщений.
Под сообщением понимают совокупность знаков или первичных сигналов содержащих
информацию. Иначе говоря, сообщение - это информация представленная в какой-либо
форме. Пример сообщений: текст телеграммы, данные на выходе ЭВМ, речь, музыка и
т.д.
Для того чтобы сообщение можно было передать получателю, необходимо
воспользоваться некоторым физическим процессом, способным с той или иной
скоростью распространяться от источника к получателю сообщения. Изменяющийся во
времени физический процесс, отражающий передаваемое сообщение называется сигналом
.
Сообщения могут быть функциями
времени (когда информация представлена в виде первичных сигналов: речь, музыка)
и не является ими (когда информация представлена в виде совокупности
знаков).
Сигнал всегда является функцией времени. В зависимости от того,
какие значения могут принимать аргумент (время t) и уровни сигналов их делят на
4 типа.
случайными процессами). Они определены для
всех моментов времени и могут принимать все значения из заданного диапазона.Чаще
всего физические процессы, порождающие сигналы являются непрерывными. Этим и
объясняется второе название сигналов данного типа аналоговый т.е. аналогичные
порождающим процессам.
2) Дискретизированный или дискретно непрерывные
сигналы
Совокупность технических средств
используемых для передачи сообщений от источника к потребителю информации называется системой
связи. Общая схема системы связи представлена на рисунке
0.5.
1) Источник сообщений создающий сообщения или
последовательность сообщений, которые должны быть переданы. Сообщения могут быть
разных типов: последовательность букв или цифр как в системах телеграфа и
передачи данных. Одна или более функций времени как в системах передачи звука в
моно и стерео звучаниях и т.д.
2) Передатчик, который перерабатывает
некоторым образом сообщения в сигналы соответственного типа определенного
характеристиками используемого канала.
3) Канал
Тогда круг проблем составляющих основное содержание ТИ можно
охарактеризовать как исследование методов кодирования для экономического
представления сообщений различных источников сообщений и для надежной передачи
сообщений по каналам связи с шумом.
В основе ТИ лежит статистическое описание
источников сообщений и каналов связи, а так же базирующееся на этом описании
измерении количества информации между сообщениями определенного только
вероятностными свойствами сообщений и не от каких других их свойств
независящих.
На основе ТИ можно ответить на вопросы о предельных возможностях
(т.е. о максимально достижимых характеристиках) различных систем, определить в
какой мере проектируемая система уступает теоретически возможной. В некоторых
случаях логика рассуждений, используемая в ТИ, подсказывает путь, на котором
может быть найдено конструктивное решение для реальной системы.
Датой
рождения ТИ 1948г. Год появления основополагающей статьи Клода Шеннона
"Математическая теория связи". Начиная с этого времени, ТИ интенсивно
развивалась в немалой степени благодаря работам и наших соотечественников
Холмогорова, Добрушина, Хоркевича, Ханчина и других.
Предположим, что источник сообщений может в каждый момент времени случайным образом принять одно из конечного множества возможных состояний. Такой источник называют дискретным источником сообщений. При этом принято говорить, что различные состояния реализуются вследствие выбора их источника. Каждому состоянию источника U ставиться в соответствие условное обозначение в виде знака. Совокупность знаков u1, u2,:,ui,:,uN соответствующих всем N возможным состояниям источника называют его алфавитом
, а количество состояний N объемом алфавита. Формирование таким источником сообщений сводиться к выбору им некоторого состояния ui и выдачи соответствующего знака. Таким образом, под элементарным дискретным сообщением будем понимать символ ui выдаваемое источником, при этом в течение некоторого времени Т источник может выдать дискретное сообщение в виде последовательности элементарных дискретных сообщений, представляющей сбой набор символов ui (например, u5, u1, u3) каждый из которых имеет длительность ti секунд. В общем случае необязательно одинаковую для различных i. Такая модель источника сообщений соответствует реальной ситуации имеющей место в телеграфии (ti№const) и передаче данных (ti=const). Отдельные состояния источника могут выбираться им чаще, другие реже. Поэтому в общем случае он храниться дискретным ансамблем U т.е. полной совокупностью состояний с вероятностями их появления, составляющими в сумме 1.Располагая такими сведениями об источнике можно вычислить
вероятность любого отрезка сообщения длиной меньше n. Если функция не меняется во
времени, если она
при любых t, то источник называется
стационарным. Если при определении вероятностных характеристик стационарного
источника усреднение по ансамблю можно заменить усреднением по времени, то такой
источник называется эргодическим. Вероятностные свойства эргодического источника
можно оценить, рассматривая лишь одну его достаточно длинную реализацию. В
каждом элементарном сообщении содержится для
его получателя определенная информация совокупность сведений о состоянии
дискретного источника сообщения. Определяя количественную меру этой информации, мы совершенно
не будем учитывать ее смыслового содержания, так же ее значения для конкретного
получателя. Очевидно, что при отсутствии сведений о состоянии источника имеется
неопределенность относительно того, какое сообщение ui из числа
возможных им выбрано, а при наличии этих сведений данная неопределенность
полностью исчезает. Естественно количество информации содержащейся в дискретном
сообщении измерять величиной исчезнувшей неопределенности. Введем меру этой
неопределенности, которую можно рассматривать и как меру количественной
информации. Мера должна удовлетворять ряды естественных условий, одним из них
является необходимость ее монотонного возрастания с увеличением возможности
выбора, т.е. объема алфавита источника N. Кроме того, желательно, чтобы вводимая
мера обладала свойством
адетивности заключающееся в следующем: если 2 независимых
источника с объемами алфавита N и M рассматривать как один источник,
одновременно реализующий пары состояний ni и mi то в
соответствии с принципом адетивности полагают, что неопределенность
объединенного источника равна сумме неопределенностей исходных источников.
Поскольку объемы алфавита объединенного источника =N ЧM то искомая функция при равной вероятности состояний источников
должна удовлетворять условию f(NЧ M)=f(N)+f(M).
Можно математически строго показать, что единственной функцией, при перемножении
аргументов которой значение функций складываются, является логарифмическая
функция. Поэтому перечисленные требования выполняются, если в качестве меры
неопределенности источника с равновероятными состояниями и характеризующего его
ансамбля U принять логарифм объема алфавита источника
1) с ростом N величина H(U) монотонно возрастает.
2)
в случае если объем алфавита источника N равен 1, т.е. когда неопределенность
отсутствует,
Впервые данная мера была предложена Хартли в 1928г. Основание
логарифма в (1.1) не
имеет принципиального значения и определяет только масштаб или единицу
количества информации. Чаще всего в качестве основания используют число 2, при
этом единица количества информации называется двоичной единицей или битом, и
представляет собой информацию, содержащуюся в одном дискретном сообщении
источника равновероятных сообщений с объемом алфавита равным двум. При выборе в
(1.1) основания логарифма равным 10 получаем десятичную единицу называемую
дитом. Иногда используют натуральную единицу количества информации называемую
натом, при этом основание логарифма в (1.1) равно
е=2,7.
Рассматриваемая мера количества информации может иметь лишь
ограниченное применение, поскольку предполагает равную вероятность выбора
источником любого из возможных его состояний. В более общем случае, когда
вероятности различных состояний источника не одинаковы степень неопределенности
конкретного состояния зависит не только от объема алфавита источника, но и от
вероятности этого состояния. В такой ситуации количество информации,
содержащееся в одном дискретном сообщении uk целесообразно определить
как функцию вероятности появления этого сообщения P(uk) и
характеризовать величиной (1.2). Основание логарифма
в (1.2) выбирается из тех же соображений что и в (1.1). Знак минус в первом
равенстве (1.2) необходим для того, чтобы количество информации
было
неотрицательным числом т.к. всегда
. Очевидно что, так же как и мера H(U)
определяемая (1.1)
величина
обладает свойством
адетивности. И в случае достоверного сообщения, когда
,
. Однако, теперь количество информации
содержащееся в дискретном сообщении зависит от степени неожиданности этого
сообщения характеризуемой вероятностью его появления. Количество информации в
сообщении тем больше, чем оно более неожиданно. Если источник выдает
последовательность зависимых между собой элементарных сообщений, то
наличие предшествующих сообщений может изменить вероятность последующего а,
следовательно, и количество информации в нем. Оно должно определяться по
условной вероятности
выдачи сообщений
при известных предшествующих сообщений
, тогда
количество информации
![]() |
(1.3). |
Чем больше энтропия источника, тем больше степень неожиданности
выдаваемых им сообщений в среднем, т.е. тем более неопределенным является
ожидание сообщений. Впервые мера (1.4) была преложена Клодом Шенноном в его
фундаментальной работе "Математические основы теории связи" опубликованной в
1948г в которой были заложены основы современной ТИ. Предполагающая мера была
названа энтропией не случайно. Дело в том, что вид формулы (1.4) совпадает с
полученным ранее результатом Вольцманом выражением для энтропии
термодинамической системы. Рассмотрим взаимосвязь меры Шеннона с мерой Хартли
если в источнике может быть реализовано h равновероятных состояний, то
вероятность каждого из них , с учетом этого меру неопределенности
источника Хартли
можно трактовать, как количество информации приходящей на одно
дискретное сообщение (поскольку все сообщения источника равновероятные
количества информации в каждом из них равны) в тоже время энтропия по Шеннону
это среднее количество информации содержащееся в одном из не равновероятных
состояний. Она позволяет учесть статистические свойства источника информации.
Наряду с рассмотренными мерами Хартли и Шеннона существуют и другие подходы к
определению количества информации. Наиболее интересной, наиболее новой явилась
информационная концепция Холмогорова, ее основным тезисом является то, что на
основании определения энтропии (1.4) количество информации связывается с
вероятностью наступления Pi, т.к. понятие вероятности имеет смысл
лишь в связи с массовыми явлениями количества единиц информации в единичном акте
и представляющих интерес в связи с данным исходом, оказывается выраженным через
вероятности массовых явлений. Эта внутренняя противоречивость содержания
информации опирающейся на концепцию выбора продолжатся на базе общей теории
алгоритма. Согласно алгоритмическому подходу энтропия H(u,z) есть мнимая длина
записанная в виде последовательности 0 и 1 программы, которая позволяет
построить объект u имея в своем распоряжении объект z. Тогда основные понятия
теории информации могут быть обоснованы без обращения к теории вероятности,
причем так, что понятие энтропия и количество информации оказываются строго
приемлемыми к индивидуальным объектам. Однако Шенноновская мера интересна не
сама по себе, а как основание встроенной теории позволяющей изменить и расширить
существующие предположения о возможностях в технике связи, которая и подлежит в
рассмотрении ТИ.
1) Энтропия любого
дискретного ансамбля не отрицательна (1.5). Равенство нулю возможно лишь в том
случае, когда источник генерирует одно единственное сообщение с вероятностью Р=1
в этом случае вероятности других сообщений равны нулю. Не отрицательность
следует из того, что количество информации в каждом из возможных сообщений
источника определенных в соответствии с (1.2) не
отрицательно.
2) Пусть N - объем алфавита дискретного
источника, тогда (1.6). Причем равенство имеет место, когда все сообщения источника
равновероятные. Для доказательства (1.6) рассмотрим разность,
если все
сообщения источника uk k=1:N выдаются им с вероятностями
P(uk), тогда можно записать
(1.7).
Для дальнейшего
доказательства воспользуемся неравенством
что и требовалось доказать.
Ю
,
При этом в
соответствии с (1.7) в том случае, когда
(из этого равенства следует, что при этом
). Итак,
максимально возможное значение энтропии дискретного источника с объемом алфавита
N равно logN и достигается в том случае, когда все его сообщения равновероятны.
3) Энтропия объединения нескольких независимых статистических источников
сообщений равна сумме энтропии исходных источников - свойство адетивности
энтропии. Не теряя общности, ограничимся рассмотрением объединения u и z с
объемами алфавита соответственно N и M. Под объединением двух источников u и z
понимают обобщенный источник сообщений (uЧz)
характеризующейся совместными P(uizj) всех возможных
комбинаций, состояния ui - источника u, zi - источника z.
В соответствии с определением (1.4) энтропия обобщенного
источника будет равна: (1.8а). В случае статистической
независимости u и z;
, тогда
(1.8).
Определенная равенством (1.4) энтропия характеризует информационные свойства одного дискретного источника или ансамбля. Однако в технике связи очень часто представляет интерес выявление количества информации содержащегося в одном ансамбле сообщений u с объемом алфавита N относительно другого в общем случае зависящего от него ансамбля Z, с объемом алфавита M. В качестве U и Z можно рассматривать, например ансамбль сообщений U и сигналов Z, с помощью которых передают сообщения Z. Для определения такой информационной характеристики введем понятие условной энтропииm
, которое будем обозначать H(U/Z) определяющей среднее количество информации даваемое сообщением ансамбля u при условии, что сообщение ансамбля Z уже известно. Если оба ансамбля имеют независимые элементы, то мера неопределенности H(U/Z) находится усреднением по всем значениям Zj средней неопределенности элементов ансамбля H(U/Zj) при данном Zj. Последнее находится аналогично энтропии H(u) заменой безусловных вероятностей P(Uk) (появление сообщения Uk) на условные вероятности появления Uk при условии Zj P(Uk/Zj).По теореме умножения вероятности имеем:(1.10), где
- вероятность совместного
появления сообщений uk и zj.
С учетом выражения (1.10),
выражение (1.9) можно переписать в виде(1.11).
Возможно также другое
представление (1.10) и (1.11) (1.11а), где М{} - символ математического
ожидания.
Усовная энтропия удовлетворяет неравенству (1.12), причем
, когда по
реализации ансамбля Z можно точно установить реализацию ансамбля U (канал без
помех).
, когда ансамбли U и Z независимы и знание реализации Z ничего не
говорит о реализации U. В общем случае
и знание реализации Z снижает
первоначальную неопределенность U. На основании этого можно ввести
информационную характеристику двух ансамблей U и Z называемую взаимной информацией
между U и Z или количеством
информации, содержащимся в Z относительно U, которая определяется,
как
![]() |
(1.13). |
1) (1.15), причем равенство имеет место
только в том случае, когда u и z независимы между собой. Это
следует из определения (1.13) и неравенства (1.12).
2) (1.16), т.е z
содержит столько же информации относительно u, сколько u содержит относительно
z, это свойство вытекает из симметрии (1.14). Поэтому можно так же записать
(1.17).
3) Причем равенство имеет место, когда по
реализации z можно точно восстановить реализацию u или наоборот. Это
следует из (1.12) и (1.13). (1.19) вытекает из
(1.16) и (1.18).
4) Полагая в (1.13) и учитывая, что
, получаем
Это
позволяет интерпретировать энтропию источника как его собственную информацию
ансамбля U о самом себе.
Пусть U ансамбль дискретных сообщений, а Z
ансамбль дискретных сигналов, в которые преобразуется сообщение U, тогда только в том
случае когда преобразование U в Z обратимо, т.е. однозначно. При необратимом
преобразовании
и разность
называют потерей информации или ненадежностью преобразования U в Z.
Таким образом, информация не теряется только при обратимых преобразованиях,
величина
называется энтропией шума преобразования или ложной информацией, создаваемой при
образовании.
Из определения энтропии H(U) дискретного источника характеризуемого ансамблем U следует, что величина H(U) зависит от распределения вероятности ансамбля, причем как показано в параграфе 1.2 свойство 2 энтропии. Энтропия максимальна только в том случае, когда все сообщения источника равновероятны. При генерировании источником последовательности сообщений существует еще один фактор, оказывающий влияние на величину энтропии, а именно наличия или отсутствия у источника памяти. Источник дискретных сообщений называется источником с памятью
, если вероятность выдачи им очередного элементарного сообщения uk зависит от того, какое (или какие) элементарные сообщения были выданы ранее. Иначе говоря, сообщения источника с памятью являются зависимыми. Стационарный источник независимых сообщений называется источником без памяти.1) все сообщения источника независимы (источник без
памяти).
2) все сообщения источника равновероятны.
Невыполнение любого из этих требований уменьшает энтропию источника и является причиной избыточности. Избыточностью
источника дискретных сообщений с энтропией Hu и объемом алфавита N называется величинаОбычно источники передают сообщения, с некоторой скоростью, затрачивая в среднем время Т на передачу одного сообщения. Производительность источника
![]() |
(1.21). |
В любой системе связи по каналу передается информация, скорость
ее передачи определяется выражением (1.23) как видно из него
это скорость зависит от свойств самого канала, но и от подаваемого на его вход
сигнала, и поэтому не может характеризовать канал как средство передачи
информации. Попытаемся найти объективную характеристику способности канала
передавать информацию. Рассмотрим дискретный канал, через который в единицу
времени передается символов источника с объемом алфавита M. При
передаче каждого символа в среднем по каналу проходит количество информации
, где U и Z
ансамбли сообщений на входе и выходе канала. Из четырех фигурирующих здесь энтропий лишь H(U) -
собственная информация
источника передаваемых символов, определяется источником входного сигнала и не зависит от
свойств канала.
Остальные три энтропии в общем случае зависят как от свойств источника, так и от
канала. Представим себе, что на вход канала можно подавать символы от различных
источников характеризуемых различными распределениями вероятностей P(U) при
одних и тех же значениях
и M. Для каждого такого источника
количество информации переданной по каналу принимает свое значение. Очевидно,
существует какой-то источник входного сигнала с некоторым распределением P(U)
для которого величина I(U,Z) максимальна. Максимальное количество переданной
информации, взятое по всевозможным источникам входного сигнала, характеризует
сам канал, и называется пропускной способностью канала в расчете на один символ.
![]() |
(1.24а), |
![]() |
(1.24б), |
![]() |
(1.26), |
Создатели электронного учебника |
Информация о дисциплине |
Программа дисциплины |