[Создатели электронного учебника] [Информация о дисциплине] [Программа дисциплины]

Лекции по теории информации МГУ (PDF.ZIP)
Лекции по теории алгоритмам на графах (PDF.ZIP)

ВВЕДЕНИЕ


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

1) информация приносит сведения, об окружающем мире которых в рассматриваемой точке не было до ее получения;

2) информация не материальна, но она проявляется в форме материальных носителей дискретных знаков или первичных сигналах;

3) знаки и первичные сигналы несут информацию только для получателя способного распознать.

Вместе с тем слово информация является одним из тех терминов, которые достаточно часто встречаются не только в научных трудах специального характера, нон и во множестве обиходных ситуаций и являются интуитивно понятными каждому человеку. При этом в узком практическом смысле под информацией обычно понимают совокупность сведений об окружающем мире являющихся объектом хранения, передачи и преобразования.
Знаки или первичные сигналы, организованные в последовательности несут информацию не потому, что они повторяют объекты реального времени, а по общественной договоренности об однозначной связи знаков и объектов, например: предметы и слова для их обозначения. Кроме того, первичные сигналы могут быть порождены естественными законами реального мира, например: напряжение на выходе термопары под действием температуры. Информация, основанная на однозначной связи знаков или сигналов с объектами реального мира, называется семантической или смысловой. Информация, заключенная в характере (порядке и взаимосвязи) следования знаков сообщающей называется синтаксической. Также в общей науке о знаках (семиотики) кроме перечисленных выделяют сигматический и прагматический аспекты информации. В первом случае изучается вопрос о выборе знаков для обозначения объектов реального мира, во втором случае о ценности информации для достижения поставленных целей.
Очевидно, что наибольший практический интерес представляют смысловой и семантический и прагматический аспекты. Однако до сих пор не определены объективные количественные критерии меры ценности и полезности информации. В курсе теории информации изучаются проблемы синтаксического уровня касающихся создания теоретических основ построения систем связи основные показатели функционирования, которых были бы близки к предельно возможным.
Иначе говоря, рассмотрению подлежат вопросы доставки получателю информации как совокупность из знаков. При этом последовательностью игнорируются смысловое и прагматическое ее содержание. Синтаксическая мера информации имеет практическую ценность потому, что интересующая в конечном итоге получателя семантическая информация заключена в заданной последовательности знаков или первичных сигналов. Чем больше знаков передаются в определенный интервал времени, тем в среднем больше передается и смысловой информации.
Теория информации представляет собой ветвь статистической теории связи. Для того чтобы более конкретно обозначить предмет этой науки введем некоторые понятия и определения.
Информация передается, и храниться в виде сообщений.
Под сообщением понимают совокупность знаков или первичных сигналов содержащих информацию. Иначе говоря, сообщение - это информация представленная в какой-либо форме. Пример сообщений: текст телеграммы, данные на выходе ЭВМ, речь, музыка и т.д.
Для того чтобы сообщение можно было передать получателю, необходимо воспользоваться некоторым физическим процессом, способным с той или иной скоростью распространяться от источника к получателю сообщения. Изменяющийся во времени физический процесс, отражающий передаваемое сообщение
называется сигналом .
Сообщения могут быть функциями времени (когда информация представлена в виде первичных сигналов: речь, музыка) и не является ими (когда информация представлена в виде совокупности знаков).
Сигнал всегда является функцией времени. В зависимости от того, какие значения могут принимать аргумент (время t) и уровни сигналов их делят на 4 типа.

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





2) Дискретизированный или дискретно непрерывные сигналы (случайные сигналы этого типа называют процессами с дискретным временем или непрерывными случайными последовательностями). Они определены лишь в отдельные моменты времени и могут принимать любые значения уровня. Временной интервал Dt между соседними отсчетами называется шагом дискретизации. Часто такие сигналы называют дискретными по времени.





3) Дискретные по уровню или квантованные сигналы (случайные сигналы этого типа называют дискретными случайными процессами). Они определены для всех моментов времени и принимают лишь разрешенные значения уровней отделенные от друг друга на величину шага квантования Dx=xk+1+xk







4) Дискретные по уровню и по времени сигналы (случайные сигналы этого типа называют дискретными случайными последовательностями). Они определены лишь в отдельные разрешенные моменты времени и могут принимать лишь разрешенные значения уровней.








Совокупность технических средств используемых для передачи сообщений от источника к потребителю информации называется системой связи. Общая схема системы связи представлена на рисунке 0.5.

Она состоит из 5 частей:

1) Источник сообщений создающий сообщения или последовательность сообщений, которые должны быть переданы. Сообщения могут быть разных типов: последовательность букв или цифр как в системах телеграфа и передачи данных. Одна или более функций времени как в системах передачи звука в моно и стерео звучаниях и т.д.

2) Передатчик, который перерабатывает некоторым образом сообщения в сигналы соответственного типа определенного характеристиками используемого канала.

3) Канал - это комплекс технических средств, обеспечивающий передачу сигналов от передатчика к приемнику. В состав канала входит каналообразующая аппаратура, осуществляющая сопряжение выходного и входного сигналов соответственно передатчика и приемника с линией связи, и самой линии связи.
Линией связи называется среда, используемая для передачи сигнала от передатчика к приемнику. Это может быть, например: пара поводов, коаксиальный кабель, область распространения радиоволн, световод и т.д. Обычно входными и выходными сигналами линии связи является сигналы типа один, т.е. непрерывный. Вместе с тем на входе и выходе канала могут присутствовать сигналы и других типов. Канал называется дискретным, если на его входе и выходе присутствуют сигналы дискретные по уровню (сигналы типа 3,4). Если сигналы на входе и выходе канала непрерывны по времени (типа 1 или 2) то он называется непрерывным. В общем случае в процессе передачи в канале сигнал искажается шумом, что соответствует наличию рисунок 0.5 источника шума.

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

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

Тогда круг проблем составляющих основное содержание ТИ можно охарактеризовать как исследование методов кодирования для экономического представления сообщений различных источников сообщений и для надежной передачи сообщений по каналам связи с шумом.
В основе ТИ лежит статистическое описание источников сообщений и каналов связи, а так же базирующееся на этом описании измерении количества информации между сообщениями определенного только вероятностными свойствами сообщений и не от каких других их свойств независящих.
На основе ТИ можно ответить на вопросы о предельных возможностях (т.е. о максимально достижимых характеристиках) различных систем, определить в какой мере проектируемая система уступает теоретически возможной. В некоторых случаях логика рассуждений, используемая в ТИ, подсказывает путь, на котором может быть найдено конструктивное решение для реальной системы.
Датой рождения ТИ 1948г. Год появления основополагающей статьи Клода Шеннона "Математическая теория связи". Начиная с этого времени, ТИ интенсивно развивалась в немалой степени благодаря работам и наших соотечественников Холмогорова, Добрушина, Хоркевича, Ханчина и других.



1. КОЛИЧЕСТВЕННЫЕ ИНФОРМАЦИОННЫЕ ХАРАКТЕРИСТИКИ ДИСКРЕТНЫХ ИСТОЧНИКОВ СООБЩЕНИЙ И КАНАЛОВ



1.1. Количество информации в дискретном сообщении. Энтропия

Предположим, что источник сообщений может в каждый момент времени случайным образом принять одно из конечного множества возможных состояний. Такой источник называют дискретным источником сообщений. При этом принято говорить, что различные состояния реализуются вследствие выбора их источника. Каждому состоянию источника U ставиться в соответствие условное обозначение в виде знака. Совокупность знаков u1, u2,:,ui,:,uN соответствующих всем N возможным состояниям источника называют его алфавитом, а количество состояний N объемом алфавита. Формирование таким источником сообщений сводиться к выбору им некоторого состояния ui и выдачи соответствующего знака. Таким образом, под элементарным дискретным сообщением будем понимать символ ui выдаваемое источником, при этом в течение некоторого времени Т источник может выдать дискретное сообщение в виде последовательности элементарных дискретных сообщений, представляющей сбой набор символов ui (например, u5, u1, u3) каждый из которых имеет длительность ti секунд. В общем случае необязательно одинаковую для различных i. Такая модель источника сообщений соответствует реальной ситуации имеющей место в телеграфии (ticonst) и передаче данных (ti=const). Отдельные состояния источника могут выбираться им чаще, другие реже. Поэтому в общем случае он храниться дискретным ансамблем U т.е. полной совокупностью состояний с вероятностями их появления, составляющими в сумме 1.
, (1.0), где P(ui) это вероятность выбора источником состояния ui. При выдаче источником сообщений в виде последовательности элементарных дискретных сообщений, полным вероятностным описанием является вероятность совместного появления набора различных символов ui в момент t1, t2,...,tn, где n - длина последовательности

.

Располагая такими сведениями об источнике можно вычислить вероятность любого отрезка сообщения длиной меньше n. Если функция не меняется во времени, если она при любых t, то источник называется стационарным. Если при определении вероятностных характеристик стационарного источника усреднение по ансамблю можно заменить усреднением по времени, то такой источник называется эргодическим. Вероятностные свойства эргодического источника можно оценить, рассматривая лишь одну его достаточно длинную реализацию. В каждом элементарном сообщении содержится для его получателя определенная информация совокупность сведений о состоянии дискретного источника сообщения. Определяя количественную меру этой информации, мы совершенно не будем учитывать ее смыслового содержания, так же ее значения для конкретного получателя. Очевидно, что при отсутствии сведений о состоянии источника имеется неопределенность относительно того, какое сообщение ui из числа возможных им выбрано, а при наличии этих сведений данная неопределенность полностью исчезает. Естественно количество информации содержащейся в дискретном сообщении измерять величиной исчезнувшей неопределенности. Введем меру этой неопределенности, которую можно рассматривать и как меру количественной информации. Мера должна удовлетворять ряды естественных условий, одним из них является необходимость ее монотонного возрастания с увеличением возможности выбора, т.е. объема алфавита источника N. Кроме того, желательно, чтобы вводимая мера обладала свойством адетивности заключающееся в следующем: если 2 независимых источника с объемами алфавита N и M рассматривать как один источник, одновременно реализующий пары состояний ni и mi то в соответствии с принципом адетивности полагают, что неопределенность объединенного источника равна сумме неопределенностей исходных источников. Поскольку объемы алфавита объединенного источника =N ЧM то искомая функция при равной вероятности состояний источников должна удовлетворять условию f(NЧ M)=f(N)+f(M). Можно математически строго показать, что единственной функцией, при перемножении аргументов которой значение функций складываются, является логарифмическая функция. Поэтому перечисленные требования выполняются, если в качестве меры неопределенности источника с равновероятными состояниями и характеризующего его ансамбля U принять логарифм объема алфавита источника

(1.1).
Легко видеть, что:

1) с ростом N величина H(U) монотонно возрастает.

2) в случае если объем алфавита источника N равен 1, т.е. когда неопределенность отсутствует,

.

3) величина H(U) обладает свойством адетивности, поскольку
.

Впервые данная мера была предложена Хартли в 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.2) и (1.3) количества информации являются случайной величиной, поскольку сами сообщения являются случайными. Его распределение вероятностей определяется распределением вероятностей сообщений в данном ансамбле для цифровой характеристики всего ансамбля или источника сообщения используется математическое ожидание количества информации в отдельных сообщениях называемых энтропией.

(1.4)

Чем больше энтропия источника, тем больше степень неожиданности выдаваемых им сообщений в среднем, т.е. тем более неопределенным является ожидание сообщений. Впервые мера (1.4) была преложена Клодом Шенноном в его фундаментальной работе "Математические основы теории связи" опубликованной в 1948г в которой были заложены основы современной ТИ. Предполагающая мера была названа энтропией не случайно. Дело в том, что вид формулы (1.4) совпадает с полученным ранее результатом Вольцманом выражением для энтропии термодинамической системы. Рассмотрим взаимосвязь меры Шеннона с мерой Хартли если в источнике может быть реализовано h равновероятных состояний, то вероятность каждого из них , с учетом этого меру неопределенности источника Хартли можно трактовать, как количество информации приходящей на одно дискретное сообщение (поскольку все сообщения источника равновероятные количества информации в каждом из них равны) в тоже время энтропия по Шеннону это среднее количество информации содержащееся в одном из не равновероятных состояний. Она позволяет учесть статистические свойства источника информации. Наряду с рассмотренными мерами Хартли и Шеннона существуют и другие подходы к определению количества информации. Наиболее интересной, наиболее новой явилась информационная концепция Холмогорова, ее основным тезисом является то, что на основании определения энтропии (1.4) количество информации связывается с вероятностью наступления Pi, т.к. понятие вероятности имеет смысл лишь в связи с массовыми явлениями количества единиц информации в единичном акте и представляющих интерес в связи с данным исходом, оказывается выраженным через вероятности массовых явлений. Эта внутренняя противоречивость содержания информации опирающейся на концепцию выбора продолжатся на базе общей теории алгоритма. Согласно алгоритмическому подходу энтропия H(u,z) есть мнимая длина записанная в виде последовательности 0 и 1 программы, которая позволяет построить объект u имея в своем распоряжении объект z. Тогда основные понятия теории информации могут быть обоснованы без обращения к теории вероятности, причем так, что понятие энтропия и количество информации оказываются строго приемлемыми к индивидуальным объектам. Однако Шенноновская мера интересна не сама по себе, а как основание встроенной теории позволяющей изменить и расширить существующие предположения о возможностях в технике связи, которая и подлежит в рассмотрении ТИ.

1.2. Свойства энтропии

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.3. Условная энтропия и взаимная информация

Определенная равенством (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.9)

По теореме умножения вероятности имеем:
(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).
Взаимная информация измеряется в тех же единицах что и энтропия, например в битах. Величина показывает, сколько в среднем бит информации о реализации ансамбля u дает наблюдение о реализации ансамбля z. Подставляя (1.4) и (1.11) в (1.13) имеем:
. Учитывая, что последнее выражение можно записать в виде (1.14).
Взаимная информация обладает следующими свойствами:

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.
Таким образом, информация не теряется только при обратимых преобразованиях, величина называется энтропией шума преобразования или ложной информацией, создаваемой при образовании.

1.4. Дискретные источники сообщений с памятью. Избыточность дискретного источника сообщений

Из определения энтропии H(U) дискретного источника характеризуемого ансамблем U следует, что величина H(U) зависит от распределения вероятности ансамбля, причем как показано в параграфе 1.2 свойство 2 энтропии. Энтропия максимальна только в том случае, когда все сообщения источника равновероятны. При генерировании источником последовательности сообщений существует еще один фактор, оказывающий влияние на величину энтропии, а именно наличия или отсутствия у источника памяти. Источник дискретных сообщений называется источником с памятью, если вероятность выдачи им очередного элементарного сообщения uk зависит от того, какое (или какие) элементарные сообщения были выданы ранее. Иначе говоря, сообщения источника с памятью являются зависимыми. Стационарный источник независимых сообщений называется источником без памяти.
В качестве примера источника дискретных сообщений с памятью можно привести источник связанного русского текста, в качестве элементарных сообщений которого рассматриваются отдельные буквы русского алфавита. Наряду с тем, что различными являются вероятности появления разных букв в тексте (а чаще чем ъ) имеет место зависимость вероятности появления каждой буквы, от того какая буква ей предшествовала. Так сочетание букв "ар" может встретиться чаще чем "аъ". В тоже время если передачи подлежат расчеты ЭВМ и в качестве элементарных сообщений выступают отдельные цифры, то есть основания в общем случае такой источник информации считать источником без памяти.
Как видно из параграфа 1.3 количество информации, содержащееся в одном элементарном сообщении источника с памятью, определяется с помощью условных вероятностей. Следовательно, и энтропия такого источника, определяемая на основе (1.4) так же будет равна условной энтропии H(u/z). Сообщения ансамбля U при условии, что ему предшествовало сообщение (или несколько сообщений) ансамбля Z. В соответствии со свойством условной энтропии (1.12) для случая зависимых ансамблей U и Z всегда, т.е. энтропия источника с памятью всегда меньше энтропии источника независимых сообщений. Таким образом, энтропия дискретного источника максимальна в том случае, когда выполняются 2 условия:

1) все сообщения источника независимы (источник без памяти).

2) все сообщения источника равновероятны.

Невыполнение любого из этих требований уменьшает энтропию источника и является причиной избыточности. Избыточностью источника дискретных сообщений с энтропией Hu и объемом алфавита N называется величина (1.20), где - максимально возможное значение энтропии при данном объеме алфавита, оно достигается при выполнении условий 1) и 2) и в соответствии с (1.6)
.
Избыточность показывает, какая доля максимально возможной при заданном объеме алфавита неопределенности (энтропии) не используется источником. В частности избыточность современного английского текста составляет 50%, избыточность русского текста 70%.

1.5. Производительность источника дискретных сообщений. Скорость передачи информации

Обычно источники передают сообщения, с некоторой скоростью, затрачивая в среднем время Т на передачу одного сообщения. Производительность источника назовем суммарную энтропию сообщений переданных за единицу времени
(1.21).
Производительность измеряется в битах на секунду. Если сообщение может быть представлено в виде последовательности элементарных дискретных сообщений источника с энтропией следующих со скоростью элементов в секунду, то (1.22). Аналогичным образом, т.е. разделив формулы (1.11)-(1.19) на Т и обозначая , получим соответственные равенства для условных энтропии и количества информации, рассчитанных на одно сообщение в единицу времени. Величина называется скоростью передачи информации от U к Z или наоборот. Если, например U ансамбль сигналов на входе дискретного канала, а Z ансамбль сигналов на его выходе то скорость передачи информации по каналу (1.23). Это соотношение наглядно иллюстрируется на рисунке 1.1.
Здесь H'(U) производительность источника передаваемого сигнала U, а "производительность" канала, т.е. полная собственная информация в принятом сигнале за единицу времени. Величина представляет собой потерю информации или ненадежность канала в единицу времени, а скорость создания ложной, посторонней информации в канале не имеющей отношение к U и обусловленная присутствующими в канале помехами. По определению Шеннона ненадежность канала является энтропией входа, когда выход известен, т.е. ее можно считать мерой средней неопределенности принятого сигнала. Величина же есть энтропия выхода, когда вход известен и служит мерой средней неопределенности передаваемого сигнала.
Соотношение между и зависит от свойств канала. Так, например, при передаче звукового сигнала по каналу с узкой полосой пропускания недостаточный для качественного воспроизведения сигнала и с низким уровнем помех. Теряется часть полезной информации, но почти не получается бесполезной, в этом случае . Если же сигнал воспроизводится качественно, но при этом прослушиваются наводки от сосе5днего радиоканала, то это означает, что почти не теряя полезной информации мы получили много лишней мешающей информации и
.

1.6. Пропускная способность дискретного канала

В любой системе связи по каналу передается информация, скорость ее передачи определяется выражением (1.23) как видно из него это скорость зависит от свойств самого канала, но и от подаваемого на его вход сигнала, и поэтому не может характеризовать канал как средство передачи информации. Попытаемся найти объективную характеристику способности канала передавать информацию. Рассмотрим дискретный канал, через который в единицу времени передается символов источника с объемом алфавита M. При передаче каждого символа в среднем по каналу проходит количество информации , где U и Z ансамбли сообщений на входе и выходе канала. Из четырех фигурирующих здесь энтропий лишь H(U) - собственная информация источника передаваемых символов, определяется источником входного сигнала и не зависит от свойств канала. Остальные три энтропии в общем случае зависят как от свойств источника, так и от канала. Представим себе, что на вход канала можно подавать символы от различных источников характеризуемых различными распределениями вероятностей P(U) при одних и тех же значениях и M. Для каждого такого источника количество информации переданной по каналу принимает свое значение. Очевидно, существует какой-то источник входного сигнала с некоторым распределением P(U) для которого величина I(U,Z) максимальна. Максимальное количество переданной информации, взятое по всевозможным источникам входного сигнала, характеризует сам канал, и называется пропускной способностью канала в расчете на один символ.
(1.24а),
где максимизация производится по всем возможным многомерным (т.е. учитывающим и статистическую взаимозависимость последовательно выдаваемых элементарных сообщений) распределением вероятностей P(U)). Обычно определяют пропускную способность в расчете на единицу времени.
(1.24б),
которую и называют просто пропускной способностью канала. Пропускная способность канала удовлетворяет системе неравенств (1.25), причем С=0 при независимых входе и выходе канала, т.е. H(U/Z)=H(U) (обрыв канала или сильные помехи). Ограниченное значение (1.25а) наблюдается в том случае, когда помех в канале нет H(U/Z)=H(Z/U)=0 при этом H(U)=H(Z)=I(U,Z) если учесть что при заданном M (см. свойство 2 энтропии). Таким образом, пропускная способность дискретного канала без шума определяется равенством (1.25а) при наличии шума (1.25б). В качестве примера вычислим пропускную способность дискретного симметричного канала без памяти. В таком канале каждый переданный кодовый символ может быть принят ошибочно с фиксированной вероятностью P и правильно с вероятностью 1-P, при чем в случае ошибки вместо переданного символа может быть с равной вероятностью принят любой другой символ. Таким образом, вероятность того, что принят символ Zj при условии, что передавался символ Uk равна
(1.26),
где N - объем алфавита источника.
Термин без памяти означает, что вероятность ошибки в канале не зависит от того, какие символы передавались ранее и как они были приняты. В соответствии с (1.24а) . В соответствии с (1.19) и (1.26) имеем
(1.26а),
итак . В правой части от P(U) зависит только H(Z) следует минимизировать только ее. В соответствии со вторым свойством энтропии максимальное значение и реализуется оно тогда когда все принятые сигналы Zj равновероятные и независимые. Легко убедиться, что это условие выполняется, когда , . В соответствии с (1.26) при каждом значении j для одного из слагаемых этой суммы соответствующего , при j=k, а для всех остальных . При этом и (1.27). Отсюда пропускная способность канала (1.27а). Для двоичного симметричного канала N=2 и (1.27а) принимает вид (1.28). Зависимость, построенная в соответствии с (1.28) показана на рисунке 1.2. При пропускная способность двоичного канала C=0 т.к. при такой вероятности ошибки последовательность выходящих двоичных символов можно получить, совсем не передавая сигнала по каналу, а выбирая их наугад, т.е. при последовательности на входе и выходе независимы (обрыв канала). То, что пропускная способность при P=1 в двоичном канале такая же, что и при P=0 (канал без шумов) объясняется тем, что при P=1 достаточно все выходные символы инвертировать, чтобы правильно восстановить исходный сигнал.



Создатели электронного учебника
Информация о дисциплине
Программа дисциплины