Шпоргалки по теории информации. Вопросы к зачету по курсу Теория информации
 Скачать 0.84 Mb.
|
|
Вопросы к зачету по курсу «Теория информации» 1. Теория информации как наука. Информация, сообщения, сигналы (понятия). 2. Передача информации в информационной системе. 3. Случайные модели в задачах теории информации. Случайная величина. 4. Случайные модели в задачах теории информации. Случайное событие. 5. Измерение информации (меры информации) 6. Информационная мера Шеннона. Энтропия. Условная энтропия. 7. Свойства энтропии дискретного и непрерывного источников информации 8. Избыточность информации. Взаимная информация. 9. Обобщенные характеристики сигналов и каналов 10. Характеристика канала связи без помех. Теорема Шеннона для канала без помех. 11. Характеристика канала связи с помехами. Теорема Шеннона для канала с помехами. 12. Значение результатов Шеннона. 13. Сжатие данных 14. Экономное кодирование 15. Процедуры Шеннона-Фано и Хаффмена 16. Помехоустойчивое кодирование. Основные принципы помехоустойчивого кодирования. 17. Помехоустойчивое кодирование. Помехоустойчивость кода. Корректирующие коды. 18. Помехоустойчивое кодирование. Методы помехоустойчивого кодирования. 19. Дискретизация информации. Теорема Котельникова. 20. Квантование по уровню. Дискретизация по времени. 1. Теория информации как наука. Информация, сообщения, сигналы (понятия). Информация – лат. Information – разъяснение, изложение, осведомленность; –одно из общих понятий науки, обозначающее некоторые сведения, совокупность каких-либо данных, знаний. В широком смысле – отражение реального мира; В узком смысле – любые сведения, являющиеся объектом хранения, передачи, и преобразования информации. Теория информации – это наука о получении, преобразовании, накоплении, отображении и передаче информации. Структурная теория информации рассматривает структуру построения отдельных информационных сообщений. Единица количества информации – элементарная структурная единица квант. Статистическая теория оценивает информацию с точки зрения меры неопределенности. Основное внимание уделяется распределению вероятностей, либо появлению сигналов, либо изменению характеристик этих сигналов и построению на его основе некоторых обобщенных характеристик, позволяющих оценить количество информации. Семантическая теориязанимается изучением именно смысловых характеристик информации: ценности, содержательности, полезности. Помогает связать количество и ценность информации с такими обобщенными характеристиками системы, как эффективность, информационная пропускная способность, информационная помехоустойчивость. С технической точки зрения, информация – это сведения, являющиеся объектом хранения, передачи и преобразования. Информация – это, прежде всего, сведения, которые должны быть использованы. Под сообщением понимают информацию, выраженную в определенной форме и подлежащую передаче. Сообщение – это форма представления информации. Примерами сообщений являются: текст телеграммы, речь оратора, показания измерительного датчика, команды управления и т.д. Непрерывные по времени сообщения отображаются непрерывной функцией времени. Дискретные по времени сообщения характеризуются тем, что поступают в определенные моменты времени и описываются дискретной функцией t. Непрерывные множеству сообщения характеризуются тем, что функция, их описывающая, может принимать непрерывное множество значений. Дискретные по множеству сообщения – это сообщения, которые могут быть описаны с помощью конечного набора чисел или дискретных значений некоторой функции. Сообщение для передачи его в соответствующий адрес должно быть предварительно преобразовано в сигнал. Под сигналом понимается изменяющаяся физическая величина, отображающее сообщение. Сигнал – материальный переносчик сообщения, т.е. изменяющаяся физическая величина, обеспечивающая передачу информации по линии связи. Квантование по уровнюсостоит в преобразовании непрерывного множества значений сигнала x(ti) в дискретное множество значений xk, k=0, …., m-1,  (III вид сигнала).Операцию, переводящую непрерывный сигнал во II вид называют квантованием по времени или дискретизацией. 2. Передача информации в информационной системе.  Система состоит из отправителя информации, линии связи и получателя информации. Сообщение для передачи его в соответствующий адрес должно быть предварительно преобразовано в сигнал. Под сигналом понимается изменяющаяся физическая величина, отображающее сообщение. Сигнал – материальный переносчик сообщения, т.е. изменяющаяся физическая величина, обеспечивающая передачу информации по линии связи. Физическая среда, по которой происходит передача сигналов от передатчика к приемнику, называется линией связи. В современной технике нашли применение электрические, электромагнитные, световые, механические, звуковые, ультразвуковые сигналы. Для передачи сообщений необходимо принять тот переносчик, который способен эффективно распределяться по используемой в системе линии связи (FE: по радиолинии эффективно распределяется только электромагнитные колебания высоких частот – от сотен кГц до дес. тысяч МГц). Преобразование сообщений в сигналы, удобные для прохождения по линии связи, осуществляется передатчиком. В процессе преобразования дискретных сообщений в сигнал происходит кодирование сообщения. В широком смысле кодированием называется преобразование сообщений в сигнал. В узком смысле кодирование – это отображение дискретных сообщений сигналами в виде определенных сочетаний символов. Устройство, осуществляющее кодирование называется кодером. При передаче сигналы подвергаются воздействию помех. Под помехами подразумеваются любые мешающие внешние возмущения или воздействия (атмосферные помехи, влияние посторонних источников сигналов), а также искажения сигналов в самой аппаратуре (аппаратурные помехи), вызывающие случайное отклонение принятого сообщения (сигнала) от передаваемого. На приемной стороне осуществляется обратная операция декодирования, т.е. восстановление по принятому сигналу переданного сообщения. Решающее устройство, помещенное после приемника, осуществляет обработку принятого сигнала с целью наиболее полного извлечения из него информации. Декодирующее устройство, (декодер) преобразует принятый сигнал к виду удобному для восприятия получателем. Совокупность средств, предназначенных для передачи сигнала, называется каналом связи. Одна и та же линия связи может использоваться для передачи сигналов между многими источниками и приемниками, т.е. линия связи может обслуживать несколько каналов. При синтезе систем передачи информации приходится решать две основные проблемы, связанные с передачей сообщений: - обеспечение помехоустойчивости передачи сообщений - обеспечение высокой эффективности передачи сообщений Под помехоустойчивостью понимается способность информации противостоять вредному воздействию помех. При данных условиях, т.е. при заданной помехе, помехоустойчивость определяет верность передачи информации. Под верностью понимается мера соответствия принятого сообщения (сигнала) переданному сообщению (сигналу). Под эффективностью системы передачи информации понимается способность системы обеспечивать передачу заданного количества информации наиболее экономичным способом. Эффективность характеризует способность системы обеспечить передачу данного количества информации с наименьшими затратами мощности сигнала, времени и полосы частот. Теория информации устанавливает критерии оценки помехоустойчивости и эффективности информационных систем, а также указывает общие пути повышения помехоустойчивости и эффективности. Повышение помехоустойчивости практически всегда сопровождается ухудшением эффективности и наоборот. 3. Случайные модели в задачах теории информации. Случайная величина. Случайной величиной называется такая переменная величина, которая в результате опыта может принимать то или иное заранее неизвестное значение  , из известного множества значений Х. Различают два основных типа случайных величин: дискретные и непрерывные.Дискретная случайная величина может принимать конечное или бесконечное множество значений {x1}, которые можно пронумеровать i=1,2,,,,n. Полной статистической характеристикой случайной величины является закон распределения вероятностей. В случае дискретной величины под ним понимается соотношение, устанавливающее зависимость между возможными значениями дискретной случайной величины и их вероятностями  при этом Закон распределения дискретной случайной величины можно задать в различных формах: табличной, графической, аналитической. Универсальной характеристикой, одинаково пригодной для дискретных и для непрерывных одномерных случайных величин, является функция распределения вероятностей  (интегральная функция распределения), определяющая вероятность  того, что случайная величина  примет значение меньше некоторого числа  : Функция распределения обладает следующими свойствами: 1.  2.  3.  неубывающая функция, т.е.  при  4.  .Функция распределения дискретной случайной величины представляет собой ступенчатую функцию со скачками в точках x1,x2,.... Во многих ситуациях невозможно определить закон распределения случайной величины, часто в этом нет необходимости. В таких ситуациях рассматривают отдельные параметры (числовые характеристики) этого закона. Наиболее важными числовыми характеристиками случайной величины с множеством значений  и законом распределения вероятностей  являются:  - математическое ожидание; - средний квадрат; - дисперсия.Возможные значения непрерывных случайных величин не могут быть заранее перечислены и непрерывно заполняют некоторый промежуток или даже всю ось. Функция распределения непрерывной случайной величины представляет собой непрерывную функцию. Часто предполагают, что функции распределения непрерывных случайных величин дифференцируемы во всей области возможных значений случайных величин. При таком предположении непрерывная случайная величина чаще своего описывается плотностью распределения вероятности  , которая иногда называется дифференциальным законом распределения или дифференциальной функцией распределения. Плотность вероятности определяется как производная функции распределения:  Плотность вероятности обладает следующими основными свойствами: 1. Плотность вероятности неотрицательна, т.е.  2. Вероятность попадания непрерывной случайной величины в интервал  равна интегралу от плотности вероятности в этих пределах: 3. Интеграл в бесконечных пределах от функции равен единице (условие нормировки): Для непрерывной случайной величины формулы для математического ожидания и дисперсии имеют вид:  4. Случайные модели в задачах теории информации. Случайное событие. Событие - всякий факт, который в результате опыта может произойти или не произойти. Вероятность события - это число, которое является мерой возможности реализации события. Вероятность P(A) случайного события A заключена в пределах  Достоверное событие U такое, что  Невозможное событие V такое, что  Суммой или объединением событий называется событие A, которое происходит тогда и только тогда, когда происходит, по крайней мере, одно из этих событий. Сумма обозначается   Произведением или пересечением событий  называется такое событие A, которое происходит тогда и только тогда, когда происходят события вместе. Произведение обозначается  События образуют полную группу событий, если в результате опыта появляется хотя бы одно из них: События A и B называются несовместными, если их совместное появление невозможно:  Два события называются противоположными, если они несовместны и образуют полную группу. Событие, противоположное событию A, обозначается  . Когда рассматриваемый опыт имеет N равновозможных исходов, которые несовместны и составляют полную группу, вероятность события А можно рассчитать по формуле:  где m - число исходов, которые приводят к наступлению события A. Частотой или статистической вероятностью P*(A) события A в данной серии испытаний называется отношение числа опытов n, в которых появилось событие, к общему числу N произведенных опытов:  По теореме Бернулли при большом числе опытов частота сходится по вероятности к вероятности события. Расчеты вероятности сложного события A через вероятности более простых событий базируются на использовании основных теорем теории вероятностей.Теорема сложения вероятностей. Вероятность суммы двух событий равна сумме вероятностей этих событий минус вероятность их произведения:  Теорема умножения вероятностей. Вероятность совместного появления двух событий равна произведению вероятности одного из них на условную вероятность другого при условии, что первое имело место:  где  - условная вероятность события B, т.е. вероятность события B, вычисленная в предположении, что имело место событие A.Во многих ситуациях событие A может появиться лишь как случайное следствие одного из несовместных событий  образующих полную группу. В этих случаях безусловная вероятность P(A) события A при известных вероятностях  и  определяется по формуле полной вероятности: При этих же данных можно найти значения вероятностей событий  если предположить, что событие A уже произошло. Задачи такого типа решаются с помощью формулы Байеса:  5. Измерение информации (меры информации)
 Единицы измерения информации и примеры Синтаксическая мера информации Объем данных Vд. в сообщение измеряется количеством символов (разрядов) в этом сообщение. В различных системах счисления один разряд имеет различный вес и соответственно меняется единица измерения данных: в двоичной системе счисления единица измерения - бит (bit-binary digit-двоичный разряд); в десятичной системе счисления единица измерения – дит (десятичный разряд). Количество информации I на синтаксическом уровне невозможно определить без рассмотрения понятия неопределенности состояния системы (энтропии системы). Получение информации о какой–либо системе всегда связано с изменением степени неосведомленности получателя о состоянии этой системы. (теория Шеннона). Семантическая мера информации. Тезаурус- это совокупность сведений, которыми располагает пользователь или система. В зависимости от соотношений между смысловым содержанием информации S и тезаурусом пользователя Sp. изменяется количество семантической информации Ic, воспринимаемой пользователем и включаемой им в дальнейшем в свой тезаурус.  при Sp≈0 пользователь не воспринимает, не понимает поступающую информацию; при Sp→ ∞ пользователь все знает, и информация ему не нужна.Максимальное количество информации Ic потребитель приобретает при согласовании ее смыслового содержания S со своим тезаурусом Sp ( Sp = Sp opt) ,когда поступающая информация понятна пользователю и несет ему ранее не известные (отсутствующие в его тезаурусе) сведения. Относительной мерой количества семантической информации может служить коэффициент содержательности C, который определяется как отношение количества семантической информации к ее объему:С= Ic / Vд. Прагматическая мера информации.Эта мера определяет полезность информации (ценность) для достижения пользователем поставленной цели. Эта мера также величина относительная, обусловленная особенностями использования этой информации в той или иной системе. Ценность информации целесообразно измерять в тех же единицах (или близких к ним), в которых измеряется целевая функция. Алгоритмическая мера информации.Каждый согласится , что слово 0101….01 сложнее слова 00….0, а слово, где 0 и 1 выбираются из эксперимента – бросания монеты (где 0-герб,1 –решка),сложнее обоих предыдущих . Любому сообщению можно приписать количественную характеристику, отражающую сложность (размер) программы, которая позволяет ее произвести. Так как имеется много разных вычислительных машин и разных языков программирования (разных способов задания алгоритма), то для определенности задаются некоторой конкретной вычислительной машиной, например машиной Тьюринга. Сложность слова (сообщения) определяется как минимальное число внутренних состояний машины Тьюринга, требующиеся для его воспроизведения. Структурные меры информации: структурная, геометрическая и др. меры информации. Геометрическая (метрическая): Единица измерения – метрон (мера точности измеряемого параметра); Метронная мощность (плотность)физической системы – количество метронов в расчете на единичный объем координатного пространства; Применяется и для оценки максимально возможного количества информации в заданных структурных габаритах - информационной емкости устройств. Комбинаторная (структурная) возможное количество комбинаций информационных элементов Перестановки – группы элементов, содержащие все имеющиеся в наличии элементы Определение количества информации в комбинаторной мере -определение количества возможных или существующих комбинаций, т.е. оценка структурного разнообразия информационного устройства. Аддитивная мера – мера Хартли – логарифм числа возможных размещений из h элементов по l  Позволяет производить суммирование количеств информации отдельных элементов информационного комплекса. Всегда положительна. Логарифм с основанием 2 - единица количества информации говорит о том, что произошло одно из двух равновероятных событий (двоичная единица информации или бит). Логарифм с основанием 10 - количество информации в дитах, натуральный логарифм с основанием е=2,71828 – в нитах.
6. Информационная мера Шеннона. Энтропия. Условная энтропия. Когда мы решаем задачи кодирования и поиска информации мы, главным образом, имеем дело с сообщениями. При этом мы имеем дело не с какими-то автономными сообщениями, а с сообщениями, входящими в некоторое множество. Одним из критериев, определяющих сложность алгоритмов для решения этих задач, является неопределенность сообщений. Действительно, чем больше элементов во множестве сообщений, тем больше неопределенность того, какой из них выбран в качестве аргумента поиска, тем больше сравнений требуется произвести для нахождения элемента. Чем больше неопределенность сообщения, тем длиннее требуется последовательность знаков, чтобы указать на выбранное сообщение, т. е. закодировать сообщение. Следовательно, неопределенность сообщений можно количественно измерить упомянутой предельной сложностью алгоритмов поиска и кодирования. Кроме того, любое сообщение несет некоторую информацию. И здесь важнейшим моментом является понятие количество информации. До получения конкретного сообщения оно характеризуется для получателя некоторой неопределенностью. После получения сообщения неопределенность исчезает, а мы обогащаемся некоторыми сведениями. Это можно трактовать как переход неопределенности в информацию. Следовательно, количество информации можно задать как уменьшение неопределенности. Вообще различают типичную и нетипичную последовательность сообщений. Пусть имеется последовательность из n сообщений s1, s2, .., sn, каждое из которых принадлежит множеству из N возможных значений {х1,.., хN}. Сообщения независимы и принимают возможные значения с определенными вероятностями р1,…pN. Рассмотрим свойства таких последовательностей при п ->∞. Вообще говоря, последовательность может принимать Nn возможных значений. Однако при больших n вступают в действие вероятностные законы, в частности, закон больших чисел, и количество действительно выпадающих значений сокращается. По закону больших чисел при больших n в последовательности должно быть приблизительно np1 значений х1, приблизительно nр2 значений х2, …, приблизительно npN значений xN, причем точность такой оценки увеличивается с ростом n. Конкретная последовательность называется типичной, если в ней выполняются вышеприведенные соотношения, и нетипичной в противном случае. Вероятность того, что значение x1 встретится n1 раз, значение x2 – n2 раз,… равна q=p1n1p2n2…pNnN Поэтому вероятность типичной последовательности для больших n близка к величине q=p1np1p2np2…pNnpN Это выражение одинаково для всех типичных последовательностей, следовательно, все типичные последовательности становятся равновероятными. При стремлении п к бесконечности суммарная вероятность нетипичных последовательностей стремится к нулю, а типичные последовательности становятся относительноравновероятными.(теорема асимптотической равновероятности типичных последовательностей) Из этой теоремы следует, что с увеличением n из общего числа nN возможных последовательностей остается  (1)(типичных) последовательностей. CN=log2N – 1 + ε (2) – формула для среднего числа сравнений при чистом дихотомическом поиске, где ε = ограниченная положительная величина. Объединим (1) и (2) и получим:  (3)А для одного сообщения  (4)При n->∞ эта величина стремится к пределу:  (5)(5) – формула Шеннона для энтропии сообщений. Это энтропия, которая по Шеннону является мерой информации. Энтропия Н — это количественная мера неопределенности сообщений. В соответствии с приведенными рассуждениями энтропия имеет ясный физический смысл. Она выражает предельно достижимое среднее число сравнений, необходимых при чистом дихотомическом поиске в условиях отсутствия помех, или предельно достижимое среднее число двоичных знаков, необходимых при двоичном кодировании сообщений. В качестве единицы измерения энтропии (и количества информации), таким образом, выступает энтропия множества двух равновероятных сообщений. Эта единица измерения называется битом. К сожалению, такое же название в вычислительной технике имеет совершенно иной объект — двоичный символ (двоичный разряд).Поэтому следует отличать бит как единицу количества информации от бита как двоичного символа. Условная энтропия Пусть  случайные величины с множествами возможных значений:X=  Количество информации  при наблюдении случайной величины  с распределением вероятностей  задается формулой Шеннона: Условной энтропией величины  при наблюдении величины называется  Справедливы соотношения:   7. Свойства энтропии дискретного и непрерывного источников информации Свойства энтропии дискретного источника информации. Дискретные системы связи - системы, в которых как реализации сообщения, так и реализации сигнала представляют собой последовательности символов алфавита, содержащего конечное число элементарных символов. Пусть и - случайные величины с множествами возможных значений   Количество информации  при наблюдении случайной величины  с распределением вероятностей  задается формулой Шеннона:  Единицей измерения количества информации является бит, который представляет собой количество информации, получаемое при наблюдении случайной величины, имеющей два равновероятных значения. Рассмотрим свойства энтропии, вытекающие из формулы Шеннона. 1) Энтропия — неотрицательное вещественное число. Это свойство — прямое следствие того, что 0 <= pi <= 1, i=1,..., N и свойств функции у = log2 х. 2) Энтропия равна нулю тогда и только тогда, когда ε — детерминированная величина, т. е. когда для некоторого j = 1 вероятность pj=1. Пусть ε — детерминированная величина, тогда  (неопределенности раскрываются по правилу Лопиталя). Пусть теперь Н{£) = 0. Так как слагаемые в формуле энтропии неотрицательны, то для этого должны выполняться следующие условия:  Эти условия выполняются только тогда, когда рi= 0 или Pi== 1. С учетом условия нормировки ∑iPi=1 возможно только, если для некоторого к, 1 <= к <= N выполняется условие Pk = 1, Pi≠jt =0, т.е. если ε — детерминированная величина.Таким образом, только детерминированная система имеет нулевую энтропию. 3) Энтропия максимальна при равновероятных значенияхε, т. е. когда p1=р2 =… рN = 1/N.- Это свойство легко доказать, найдя максимум многомерной функции H(ε), например, методом множителей Лагранжа. При равновероятных значениях ε получаем  , т. е. максимум равен H=log2N. (**)Это выражение называется формулой Хартли. Таким образом, неопределенность системы максимальна, когда все ее состояния равновероятны. Это и понятно: если какое-то из состояний более вероятно, то это уже есть какая-то степень определенности. Становится также понятно стремление при кодировании и поиске разбивать исходные множества на подмножества с примерно равными суммарными вероятностями. При этом получается максимальная энтропия возможных исходов сравнения и, следовательно, сравнение дает максимальное количество информации.’ 4) Энтропия аддитивна Можно привести следующие доказательства аддитивности энтропии. Сначала приведем доказательство аддитивности меры Хартли (формула **). Рассмотрим два источника информации:  |
