Лекции. лекции оти. Лекция 1. Теория информации. Понятие видов информации
 Скачать 1.19 Mb.
|
|
Пример. Если A и B рассматривать как сообщение, порожденные различными источниками (например, публикации в различных газетах ), тогда для получения взаимно большей совместной ( суммарной) информации взаимная, т.е. одинаковая в данном случае информация, должна быть минимальной. Если A и B сообщения соответственно на входе и выходе канала связи с помехами, то для получения взаимно большей информации её получателем необходимо, чтобы взаимная информация была наибольшей. В то же время для описания воздействия помех в канале связи на полученное сообщение используется понятие условной информации и условной энтропии. Для определения условной информации и условной энтропии в заданной объединенной вероятностной схеме вернемся к соотношению:  = =  .При этом совместная информация пары событий складывается из собственной информации каждого из этих событий и некоторой информации, добавленной вторым событием при условии, что произошло первое событие. Поэтому  I называют условной информацией пары случайных событий. Если аналогично тому, как мы это делали ранее, составить вероятностную схему для условной вероятности пары событий как для случайной величины: ,тогда математическое ожидание этой случайной величины и будет являться условной энтропией объединенной вероятностной схемы:  Найдем соотношение между условной энтропией и ее взаимной информаций:  Рассмотрим взаимную информацию опять как случайную величину и, усредняя её, т.е. определяя математическое ожидание по объединенной вероятностной схеме, получим: I(А;B) = E  H(A) - H(A/B) = H(B) - H(B/A).2.4 Понятие совместной энтропии. Для двух источников, образующих объединенную вероятностную схему, используя понятие совместной вероятности пары событий, можно определить среднюю информацию всех пар событий: H(AB) = E  .Не сложно показать, что совместная энтропия складывается из: H(AB)=H(A)+H(A/B)=H(B)+H(B/A). Если источники не совместны, то: H(A/B)=H(A), H(B/A)=H(B). Если источники считаются связанными, тогда: H(A/B)  H(A);H(B/A) H(B).Поэтому в общем случае совместная энтропия определяется следующим образом: H(AB) H(A)+H(B).ЛЕКЦИЯ №3 .ИСТОЧНИКИ ИНФОРМАЦИИ И ИХ ЭНТРОПИЯ. Дискретные источники без памяти и с памятью. До сих пор мы рассматривали простейшие источники информации, так называемые источники без памяти. Напомним, что дискретный источник без памяти X в каждый фиксированный момент времени выдает некоторый символ  из конечного алфавита X= с соответствующими вероятностями  , причем выборка символов производится независимо друг от друга. Вот именно для такого источника мы получили информационные меры, в том числе по Шеннону, которые определяется заданной вероятностной схемой сообщения такого источника.Энтропией дискретного источника без памяти является усредненное на алфавите источника количество информации, приходящееся на один символ, т.е. на одно событие:  , i= .Кроме того, нами были получены выражения для совместной условной энтропии пары дискретных источников без памяти, а также выражения для взаимной информации источников. Кроме рассмотренного, на практике широко применяется понятие стационарного дискретного источника с памятью. Например, если считать, что выходом источника является дискретизированный аналоговый сигнал (например, речевой), то соседние отсчеты такой дискретизированной последовательности будут как бы взаимосвязаны по времени, т.е. обладают некоторой памятью. X(t)                        t  Дискретный источник с памятью Х можно представить как дискретизированный во времени случайный процесс, реализацией которого является последовательность событий xn, принадлежащих алфавиту источника. И если совместные вероятности этих последовательностей событий xn не зависят от выбора начальной точки отсчета времени, то дискретный источник с памятью является стационарным. Следовательно, стационарный дискретный источник с памятью математически полностью считается описанным, если известны совместные вероятности  для любой выборки  , где  .Определение энтропии стационарного дискретного источника с памятью следует из двух подходов, приводящих к одинаковому решению. При первом подходе используют понятие совместной энтропии, при втором - условной энтропии. И это понятно, если учесть, что в энтропии должно быть учтено свойство памяти источника, которое распространяется на некоторую последовательность событий. А это означает, что отдельное событие несет дополнительную информацию, если блок предшествующих событий уже известен. Можно доказать, что энтропия стационарного дискретного источника с памятью можно найти следующим образом:  где  - энтропия стационарного дискретного источника с памятью; – совместная энтропия L последовательных выборок, которые можно рассматривать как самостоятельных L источников, причем последовательных; - условная энтропия источника  при условии, что события предыдущих источников, т.е. до  , известны.Для стационарных дискретных источников с памятью используют теорему Шеннона. Если совместная энтропия стационарных дискретных источников  то имеют место следующие выражения:  не возрастают с ростом длины блока L.Эргодические источники. Все дискретные источники без памяти однозначно относятся к классу эргодических источников. Свойство эргодичности - это постоянство поведения случайного процесса во времени. Примером такого процесса является бросание монеты или игрального кубика. Свойство эргодичности процесса позволяет применять операцию усреднения для определения энтропии как среднего количества информации источника. Другими словами, источник будет называться эргодическим, если его вероятностные параметры можно определить по одной достаточно длинной реализации, которую он вырабатывает. В этом случае реализации, по которым можно оценить закон распределения, являются как бы типичными, поэтому эргодические источники можно назвать источниками, которые вырабатывают типичные последовательности. Кроме источника без памяти, свойством эргодичности могут обладать и источники с памятью. Например, эргодические источники являются наиболее близкими с вероятностной точки зрения моделям осмысленных сообщений, например, источников текстов. Для эргодических источников справедливы все понятия энтропии, рассмотренной для дискретных источников без памяти. Кроме того, понятия энтропии стационарных дискретных источников, а также совместной и условной его энтропий и их свойств, определенных теоремой Шеннона, имеют место, если стационарный дискретный источник с памятью является эргодическим. Марковские цепи В классе дискретных источников с памятью особое место занимают марковские источники. Их описания базируются на математическом аппарате марковских цепей, с помощью которых можно составить математическую модель многих процессов, наиболее близких к практике. Значение марковских цепей в теории информации заключается в том, что реальные источники информации вырабатывают сообщения при наличии статистической зависимости между отдельными событиями, символами. В реальных источниках вероятность выбора какого-либо очередного символа зависит от предшествующих символов. Марковским процессом называется случайный процесс, у которого будущее состояние определяется только настоящим и не зависит от прошлого. Дискретный по времени и состояниям марковский процесс называется марковской цепью. Реализацией марковского источника является последовательность состояний  Для описания марковских цепей используют понятия: Множество состояний; Начальное условие (это распределение вероятностей событий в начальный момент времени);  3.Стохастический вектор распределения вероятностей состояний в момент времени n.  , где n=1,2,3,…- дискретные моменты времени.4.Смена состояний марковских цепей описывается вероятностями перехода  .5.Переходные вероятности на совокупности состояний в разные моменты времени образуют соответствующие матрицы вероятности перехода.  Заметим, что эта стохастическая матрица , в которой сумма вероятностей строк равна 1.Вычисление матрицы вероятности переходов производится с использованием известной рекуррентной формулой, которая является частным случаем уравнения Колмогорова- Чепмена  .Применение марковских цепей достаточно сильно упрощается, когда эти цепи гомогенны, стационарны и регулярны. Марковская цепь называется гомогенной (однородной), если вероятности переходов между состояниями не зависят от выбора временной точки отсчета, т.е. вероятности переходов зависят от разности временных отсчетов, тогда можно записать:  , где  =0,1,2,... ;  Если  ;  , то  .Это выражение может быть представлено в виде суммы компонентных произведений векторов- строк на векторы- столбцы. Записав переходные вероятности виде матриц, получаем матричную запись этого выражения:   Таким образом, можно получить матрицы переходных вероятностей на любом шаге  многократно применяя указанные выше матричные преобразования к исходному распределению состояний. Тогда можно получить распределение вероятностей на любом шаге, т.е. в любой момент времени   Итак, гомогенная марковская цепь полностью описывается матрицей переходных вероятностей и векторами исходных вероятностей состояний. Кроме аналитического представления, широко используется и графическое представление марковских цепей.      π(j/i)   π(i/j) Гомогенная марковская цепь является стационарной, если распределение состояний постоянно во времени. В этом случае начальное распределение вероятностей состояний является собственным вектором матрицы переходных вероятностей. Гомогенная цепь Маркова является регулярной, если: Предельная матрица вероятностей перехода существует.  Причем все строк предельной матрицы представляют собой предельное распределение вероятностей состояний матрицы. 2. Предельное распределение вероятностей состояний  является единственным стационарным распределением вероятностей состояний любой регулярной цепи Маркова.  3.Цепь Маркова везде будет регулярной, если существует некоторое натуральное значение шага n, при котором все компоненты некоторого столбца матрицы вероятностей перехода на этом шаге n, будет отлично от нуля. Другими словами, цепь Маркова является регулярной если, на некотором шаге n существует по меньшей мере одно состояние, которое может быть достигнуто из любого начального состояния. Если в марковской цепи вероятность очередного символа оказывает влияние на r предыдущих символов, то говорят, что память такого источника охватывает r последовательных символов, а сам источник называют конечным дискретным марковским источником с памятью r. Заметим, что такой источник обладает свойством эргодичности. Тогда конечный дискретный эргодический марковский источник с памятью r полностью считается заданным (или определенным ) следующими условиями: 1.Задано непустое множество состояний  , причем каждое состояние  содержит вектор длиной r .2. Каждое состояние соответствует дискретному источнику без памяти с алфавитом  и вероятностями j- тых символов алфавита  .3. Задано начальное распределение вероятностей состояний  .4. Состояние  образованное из r -1 последовательных символов, после добавления очередного символа  переходит в состояние S[n+1].Энтропия стационарного эргодического марковского источника вычисляется исходя из того, что некоторое состояние источника является как бы подысточником без памяти, обладающим в свою очередь соответствующей энтропией. Тогда энтропия первоначального источника равна математическому ожиданию энтропии подысточников. Таким образом, стационарный эргодический марковский источник с алфавитом из М символов, имеющий n состояний, т.е. N подысточников без памяти энтропия каждого из которых равна  , где  - вероятность символа  при условии состояния, обладает энтропией, равной математическому оживанию энтропии подысточника. , где  - предельное распределение вероятностей состояний.Строго говоря, это энтропия обладает теми же свойствами, что и дискретный стационарный источник с памятью общего вида. В теории информации, особенно для связанных источников и источников с памятью, используют понятие информационной дивергенции. Это функция, определяемая для двух распределений вероятностей и характеризующая степень их близости. ЛЕКЦИЯ №4 ОПТИМАЛЬНОЕ И ЭФФЕКТИВНОЕ КОДИРОВАНИЕ Понятие кодирования. Кодовое дерево. В процессе кодирования каждая буква исходного алфавита представляется различными последовательностями, состоящими из кодовых букв или цифр. Если исходный алфавит содержит m букв, то для построения равномерного кода с использованием D кодовых букв необходимо обеспечить выполнение следующего условия:  , где n- количество элементов кодовой последовательности. Для построения равномерного кода достаточно пронумеровать буквы исходного алфавита и записать их в коды как n-разрядное число в D-ичной системе счисления. Заметим, что поиск равномерного кода означает, что каждая буква исходного алфавита m кодируется кодовой последовательностью длинной n. Очевидно, что при различной вероятности появления букв исходного алфавита равномерный код является избыточным, так как энтропия, характеризующая информационную емкость сообщения максимальна при равновероятных буквах исходного текста:  .При этом  - энтропия кода одной буквы в n - разрядном D- ичном числе. Таким образом, информационные возможности кода используются не полностью. Пример. Для двоичного 5-рарядного кода букв русского алфавита информационная емкость составляет  5 бит,  =4,35 бит.Устранение избыточности достигается применением неравномерных кодов, в которых буквы, имеющие наибольшие вероятности, кодируются короткими кодовыми последовательностями, а более длинные комбинации присваиваются редким, имеющим меньшую вероятность буквам. Если i-ая буква, вероятность которой pi, получает кодовую комбинацию длины ni, то средняя длинна кода или средняя длина кодового слова равна:  Введем понятие кодового дерева, которым часто пользуются при рассмотрении Известно, что любую букву или событие, содержащиеся в алфавите источника или в сообщении, можно разложить на последовательности двоичных решений с исходами «ДА»=1 и «НЕТ»=0, причем без потери информации. Таким образом, каждой букве исходного алфавита может быть поставлена в соответствие или, как говорят, приписана некоторая последовательность двоичных символов - 0 или 1.А такую последовательность называют кодовым деревом. При этом потери информации не происходит, так как каждое событие может быть восстановлено по соответствующему кодовому слову.   Корень  0 1    0 1      1 2 0                    2 4 3 8 4 16 1 1 0 С1 1 0 1 0 10 0   С2 С3 1 0 1 0 1 0 1 0  С11 С10 С9 С8 С7 С6 С5 С4 C1,C2,…,C11-кодовые слова. Уровень кодового дерева определяет длину кодового слова. Теорема кодирования источников, неравенство Крафта. Префиксный код. Теорема Шеннона о кодировании источников устанавливает связь между средней длинной кодового слова и энтропией источника. Для любого дискретного источника без памяти X с конечным алфавитом и энтропией H(X) существует D- ичный префиксный код, в котором средняя длинна кодового слова  , удовлетворяет неравенству:  В префиксном коде никакое кодовое дерево не является префиксом другого кодового дерева. Это значит, что поток кодовых слов может использоваться без специального разделения этих слов. Например, если код 101 является кодом какой-то буквы, то в качестве кодов других букв нельзя использовать следующие комбинации: 1,10,10101, …и т.д. Из теоремы Шеннона следует, что тем ближе длина кодового слова к энтропии источника, тем более эффективно кодирование. В идеальном случае, когда  , код называют эффективным. Эффективность кода оценивается величиной: .Если средняя длина  кодового слова является минимально возможной, то код еще и оптимальный. Теорема кодирования источников доказывается с использованием неравенства Крафта и формулируется следующим образом.Для существования однозначно декодируемого D- ичного кода, содержащего k кодовых слов с длинами n1,n2,…,nk, необходимо и достаточно, чтобы выполнялось неравенство Крафта:  Методы оптимального кодирования. Сжатие данных. Процедуру оптимального кодирования часто называют сжатием данных. Тогда задача сжатия данных есть минимизация технических затрат на хранение или передачу информации путем оптимального кодирования. На практике используют два вида сжатия данных: 1.Сжатие без потерь - устранение избыточности информации, не связанное с ее изменением, принципиально существенным для пользователя. 2. Сжатие с потерями – устранение избыточности информации, которое приводит к безвозвратной потере некоторой доли информации, хотя это не принципиально для ее восстановления в интересах пользователя. Сжатие без потерь наиболее применимо к числовым и текстовым данным. Применительно к вычислительной технике сжатие позволяет уменьшить количество бит информации, необходимого для хранения и передачи заданного объема этой информации, что дает возможность передавать сообщения более быстро или хранить более экономно. Такие программные средства, реализующие сжатие, называют архиваторами. Существует достаточно большое их разнообразие. Методы сжатия данных были разработаны как математическая теория, которая до первой половины 80-х годов 20 века мало использовалась в компьютерной технике. Методы или алгоритмы сжатия данных без потерь можно разделить на: 1.Статистические методы или алгоритмы. Например, методы Шеннона - Фано, Хаффмана и др. Они базируются на априорной статистике (вероятностях появления букв алфавита). Это главный недостаток таких кодов, так как априорная статистика кодов заранее не известна, а, следовательно, эффективному кодированию должен предстоять так называемый частотный анализ, т.е. анализ частоты появления символов в кодовой комбинации. 2.Адаптивные методы или алгоритмы. Например, модифицированные коды Хаффмана, арифметическое кодирование и др. Здесь распределение вероятностей символов сначала считается равномерным на заданном интервале, а потом оно меняется по мере накопления статистики. 3.Динамические методы или алгоритмы. Они являются универсальными и не нуждаются в априорной статистике. Например, метод Лемпела- Зива. Метод кодирования Шеннона - Фано. Буквы исходного алфавита записываются в порядке убывания их вероятностей. Это множество разбивается так, чтобы вероятности двух подмножеств были примерно равны. Все буквы верхнего подмножества в качестве первого символа кода получают 1, а буквы нижнего подмножества-0. Затем последнее подмножество снова разбивается на два подмножества с соблюдением того же условия и проводят то же самое присвоение кодовым элементам второго символа. Процесс продолжается до тех пор, пока во всех подмножествах не останется по одной букве кодового алфавита. Пример.
= = (0,25*2+0,25*2+0,15*3+0,15*3+0,05*4+0,05*4+0,05*4+0,15*4)=2,7 бит = - (2*0,25*log2 0,25 + 2*0,15*log2 0,15 + 4*0,05*log20,05) = 2,7 бит =  1Метод Шеннона - Фано не всегда приводит к однозначному построению кода, так как при разбиении на подмножества можно сделать большей по вероятности как верхнюю, так и нижнюю часть, следовательно, такое кодирование хотя и является эффективным, но не всегда будет оптимальным. Метод кодирования Хаффмана. Этот метод всегда дает оптимальное кодирование в отличие от предыдущего, так как получаемая средняя длина кодового слова является минимальной. Буквы алфавита сообщения располагают в порядке убывания вероятностей. Две последние буквы объединяют в один составной символ, которому приписывают суммарную вероятность. Далее заново переупорядочивают символы и снова объединяют пару с наименьшими вероятностями. Продолжают эту процедуру до тех пор, пока все значения не будут объединены. Это называется редукцией. Затем строится кодовое дерево из точки, соответствующей вероятности 1 (это корень дерева), причем ребрам с большей вероятностью присваивают 1,а с меньшей-0. Двигаясь по кодовому дереву от корня к оконечному узлу, можно записать кодовое слово для каждой буквы исходного алфавита. Пример.
0,4 0,2 0,15 0,05 0,15 0,35 0,05 1 0,1      0,6 1 0,25                  0 1 1 0 0 1 0 0 1 = = (4*0,05 +3*0,15+4*0,05+0,4+3*0,2+3*0,15)= 2,3 бит = - (0,4log2 0,4+0,2 log2 0,2+2* 0,15 log20,15 +2*0,05 log20,05)= - (0,52 + 0,46+ 2*0,4+2*0,2)= 2,18 =  1,05Из рассмотренного примера видно, что чем больше разница между вероятностями букв исходного алфавита, тем больше выигрыш кода Хаффмана по сравнению с простым блоковым кодированием. Декодирование блока Хаффмана легко представить, используя кодовое дерево. Принятая кодовая комбинация анализируется посимвольно, в результате чего, начиная с корня дерева, мы попадаем в оконечный узел, соответствующий принятой букве исходного алфавита. Недостатки кода: 1.Различные длины кодовых слов приводят к неравномерным задержкам кодирования. 2.Сжатие снижает избыточность, что соответственно повышает предрасположенность к распространению ошибок, т.е. один ошибочно принятый бит может привести к тому, что все последующие символы будут декодироваться неверно. 3.Предполагаются априорные знания вероятности букв, которые на практике не известны, а их оценки часто бывают затруднительны. 4.3.3. Арифметическое кодирование. Алгоритм Хаффмана не может передавать на каждый символ сообщения , если не использовать блоковое кодирование, менее одного бита информации, хотя энтропия источника может быть меньше 1, особенно при существовании различных вероятностей символов.  Поэтому хотелось бы иметь такой алгоритм кодирования, который позволял бы кодировать символы менее чем 1 бит. Одним из таких алгоритмов является арифметическое кодирование, представленное в 70-х годах 20 века. При рассмотрении этого алгоритма будем исходить из того факта, что сумма вероятностей символов (и соответствующим им относительным частотам появления этих символов), всегда равна 1.Отсительные частоты появления могут определяться путем текущих статистических измерений исходного сообщения (это первый « проход» процедуры кодирования). Особенностью арифметического кодирования является то, что для отображения последовательности символов на интервале [0,1] используются относительные частоты их появления. Пример определения частоты появления символов в сообщении BANANANBAB.    Результатом такого отображения является сжатие символов или посимвольное сжатие в соответствии с их вероятностями, т.е. результатом арифметического сжатия будет некоторая дробь из интервала [0,1], который представляется двоичной записью (это второй «проход» процедуры кодирования). Заметим, что такой двухпроходный алгоритм может быть реализован в ранее рассмотренных кодах Шеннона – Фано и Хаффмана. Принципиальное отличие арифметического кодирования от предыдущих методов заключается в том, что кодированию подвергается сообщения целиком (весь набор символов или файл), а не символы по отдельности или их блоки. Эффективность арифметического кодирования растет с увеличением длины сжимаемого сообщения. Заметим, что в кодах Шеннона – Фано и Хаффмана такого не происходит. Арифметическое кодирование заключается в построении отрезка , однозначно определяющего заданную последовательность символов в соответствии с их вероятностями. Объединение всех отрезков, пересекающихся только в граничных точках, для вероятностей каждого символа должно образовывать формальный интервал [0,1]. Для последнего полученного интервала, соответствующего последнему принятому символу сообщения, находит число, принадлежащее его внутренней части. Это число в двоичном представлении и будет кодом для рассматриваемой последовательности. Пример. Пусть задан алфавит X={a ,b}, p(a) =  , p(b) =  . Необходимо закодировать сообщение {aba}.
 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1]
]