Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Теорія інформації та кодування. Тема 2. Джерела повідомлень. Носов В.В.
Лекція 6. Дискретне джерело повідомлень
Навчальні питання
1. Дискретна послідовність символів 1
2. Послідовні наближення до англійської мови 4
3. Марковські процеси 6
4. Ергодичні і змішані джерела 8
Час – 2 год.
Література.
Вступ
Для исследования свойств информации источника сообщений необходимо создание удовлетворительной математической модели. Клод Шеннон предложил несколько решений, позволяющих математически описывать источник сообщений, и соответственно имитировать реальный поток текстовых сообщений. Рассмотрим его рассуждения на этот счет. В лекции в основном приводится прямой перевод [3], который был представлен в [1].
Как следует математически описывать источник сообщений и какое количество информации, измеряемое числом битов в секунду, создается данным источником?
Главная сторона этого вопроса заключается в использовании статистических сведений об источнике для уменьшения требуемой пропускной способности канала путем применения надлежащего метода кодирования информации. В телеграфии, например, сообщения, которые должны быть переданы, состоят из последовательностей букв. Эти последовательности, однако, не являются вполне случайными. Вообще говоря, они образуют фразы и имеют статистическую структуру, скажем, английского языка.
Буква встречается чаще, чем ; последовательность чаще, чем , и т. д. Наличие такой структуры позволяет получить некоторую экономию времени (или пропускной способности канала) с помощью подходящего кодирования последовательностей сообщений в последовательности сигналов.
В ограниченных пределах это уже делается в телеграфии путем использования наиболее короткого символа в канале —точки—для наиболее распространенной в английском языке буквы , в то время как редко встречающиеся буквы представляются более длинными последовательностями точек и тире. Этот принцип проводится еще дальше в некоторых кодах, где наиболее употребительные слова и фразы представляются четырех- или пятибуквенными кодовыми группами, что дает значительную экономию среднего времени. В стандартизированных и поздравительных телеграммах, используемых в настоящее время, этот принцип развивается еще дальше. Там проводится кодирование одного или двух предложений в относительно короткую последовательность цифр.
Можно считать, что дискретный источник создает сообщение символ за символом. Он будет выбирать последовательные символы в соответствии с некоторыми вероятностями, зависящими, вообще говоря, как от предыдущих выборов, так и от конкретного рассматриваемого символа. Физическая система или математическая модель системы, которая создает такую последовательность символов, определяемую некоторой заданной совокупностью вероятностей, называется вероятностным процессом. Поэтому можно считать, что дискретный источник представляется некоторым вероятностным процессом. Обратно, любой вероятностный процесс, который создает дискретную последовательность символов, выбираемых из некоторого конечного множества, может рассматриваться как дискретный источник. Это включает такие случаи, как:
Приведем следующие примеры источников последнего типа:
A) пусть имеются пять букв , каждая из которых выбирается с вероятностью 0,2 независимо от результатов предыдущих выборов. Это привело бы к последовательностям, типичным примером которых является следующая последовательность:
Этот пример был построен при помощи таблицы случайных чисел.
Б) Пусть при использовании тех же самых пяти букв их вероятности будут соответственно, причем буквы выбираются независимо. Типичным сообщением такого источника является тогда:
B) Более сложная структура получается, если последовательные символы выбираются не независимо, а так, что их вероятности зависят от предыдущих букв. В простейшем случае такого типа выбор зависит только от предшествующей буквы, но не от ранее стоящих букв. Тогда статистическая структура может быть описана с помощью множества условных вероятностей , т.е. вероятностей того, что за буквой следует буква . Индексы пробегают значения, соответствующие всем возможным символам.
Другой эквивалентный способ задания этой структуры заключается в том, чтобы задать вероятности «диграмм» (двухбуквенных сочетаний) , т.е. относительные частоты диграмм . Частоты букв (вероятности буквы ), условные вероятности и вероятности диаграмм связаны следующими соотношениями:
В качестве примера предположим, что имеются три буквы с таблицами вероятностей
Типичное сообщение от такого источника имеет вид
Следующее увеличение сложности заключалось бы во включении частот триграмм (трехбуквенных сочетаний), но не более длинных сочетаний. Выбор буквы зависел бы при этом только от двух предыдущих букв. При этом потребовалось бы задать множество частот триграмм или, что эквивалентно, множество условных вероятностей . Следуя далее таким путем, получим последовательно более сложные вероятностные процессы.
В общем случае -грамм (сочетаний из букв) для задания статистической структуры требуется множество n-граммных вероятностей или же множество условных вероятностей .
Г) Можно также определять вероятностные процессы, которые создают текст, состоящий из последовательности «слов». Предположим, что в языке имеются пять букв и 16 «слов» с вероятностями появления:
|
0,10 А |
0,16 ВЕВЕ |
0,11 CABED |
0,04 DEB |
|
0,04 ADEB |
0,04 BED |
0,05 CEED |
0,15 DEED |
|
0,05 ADEE |
0,02 BEED |
0,08 DAB |
0,01 EAB |
|
0,01 BADD |
0,05 СА |
0,04 DAD |
0,05 ЕЕ |
Предположим, что последовательные «слова» выбираются независимо и отделяются друг от друга некоторым промежутком. Типичное сообщение могло бы быть таким:
Если все слова конечной длины, то этот процесс эквивалентен процессу предыдущего типа, но описание может быть проще в терминах структуры слов и их вероятностей. Можно также обобщить и этот случай, вводя условные вероятности между словами и т. д.
Такие искусственные языки полезны при конструировании простых задач и примеров, имеющих иллюстративные цели. С помощью ряда простых искусственных языков можно также приблизиться к естественному языку.
Приближение нулевого порядка получится, если выбирать все буквы с одинаковой вероятностью и независимо.
Приближение первого порядка получится, если последовательные буквы выбираются независимо, но каждая буква при этом имеет ту же самую вероятность, что и в естественном языке.
Поэтому в приближении первого порядка к английскому языку буква выбирается с вероятностью 0,12 (ее частота в нормативном английском языке) и с вероятностью 0,02, но нет никакой зависимости между смежными буквами и никакой тенденции образовывать предпочтительные диграммы, такие, как и т. д.
Для приближения второго порядка вводится структура диграмм. После того как выбрана некоторая буква, следующая буква выбирается в соответствии с частотами, с которыми различные буквы следуют за первой буквой. Для этого требуется таблица частот диграмм .
Для приближения третьего порядка вводится структура триграмм. Каждая буква выбирается с вероятностями, которые зависят от двух предыдущих букв.
Следует заметить, что использование вероятностных характеристик букв, например, английского языка, может иметь некоторые ограничения. В 1939 году Эрнест Винсент Райт опубликовал роман. На 267 страницах этой книги ни разу не была использована буква . Один абзац из этой книги:
Upon this basis I am going to show you how a bunch of bright young folks did find a champion; a man with boys and girls of his own; a man of so dominating and happy individuality that Youth is drawn to him as is a fly to a sugar bowl. It is a story about a small town. It is not a gossipy yarn; nor is it a dry, monotonous account, full of such customary "fill-ins" as "romantic moonlight casting murky shadows down a long, winding country road". Nor will it say anything about tinklings lulling distant folds; robins carolling at twilight, nor any "warm glow of lamplight" from a cabin window. No. It is an account of up-and-doing activity; a vivid portrayal of Youth as it is today; and a practical discarding of that wornout notion that "a child don't know anything".
Чтобы дать наглядную картину того, как эти последовательные приближения аппроксимируют естественный язык, ниже приводятся типичные последовательности букв для таких приближений к английскому языку. Во всех случаях использовался 27-буквенный «алфавит»(26 букв и пробел между буквами).
1. Приближение нулевого порядка (символы независимы и равновероятны):
.
Здесь слишком много букв и и явно недостаточно буквы и пробелов. Лучшее приближение к английскому тексту можно получить, выбирая буквы независимо одна от другой, но выбирая букву намного чаще, чем буквы или . Это можно было бы сделать, положив в шляпу много карточек с буквой и мало карточек с буквами . Поскольку вероятность того, что вытащенной буквой окажется , должна быть равна 0,13, то из каждой сотни карточек, положенных в шляпу, на тринадцати должна стоять буква . Вероятность того, что вытащенной буквой окажется , должна быть равна 0,02, поэтому из каждой сотни карточек, положенных в шляпу, на двух должна стоять буква , и т. д.
Вот результат, полученный с помощью описанной процедуры, который дает то, что Шеннон называет приближением первого порядка к английскому тексту:
2. Приближение первого порядка (символы независимы, но с частотами, свойственными английскому тексту):
В английском языке нет ни одной пары букв, начинающейся с , кроме сочетания . Вероятность того, что встретится или , равна нулю. Хотя вероятность появления не равна нулю, она так мала, что ее нет в известных таблицах. С другой стороны, вероятность появления сочетания равна 0,037, вероятность появления — 0,010, а вероятность появления — 0,006. Эти вероятности имеют следующий смысл. Пусть в тексте содержится 10 001 буква. Тогда первая и вторая буквы, вторая и третья и т. д. дадут 10 000 последовательных буквенных пар. Определенное количество раз встретится сочетание . Предположим, что оно встретилось 370 раз. Если разделить это число на общее число пар, которое по предположению равно 10 000, то получим вероятность того, что при случайном выборе в тексте появится сочетание , т. е. эта вероятность равна 370/10 000, или 0,037.
Усердные шифровальщики составили таблицы вероятностей появления в английском тексте групп из двух букв, так называемых диграмм. Покажем, как можно было бы построить буквенную последовательность, используя те же вероятности появления диграмм, что и в английском тексте. Для этого возьмем 27 шляп: из них 26 для диграмм, начинающихся с каждой из букв алфавита, и одну для диграмм, начинающихся с пробела. Затем положим в шляпы карточки с написанными на них диграммами в соответствии с вероятностью их появления, т. е. каждая 1000 карточек должна содержать 37 диграмм , 6 диграмм и т. д.
Остановимся на мгновение, чтобы уяснить смысл шляп, наполненных диграммами, и через исходные значения частоты их появления перейдем к подсчету вероятностей появления диграмм.
Предположим, что мы хотим найти все буквы в тексте и для этого просматриваем его букву за буквой. Будем выписывать на карточки и класть в одну шляпу все диграммы, начинающиеся с буквы . При этом окажется, что таких диграмм ровно столько, сколько букв попалось в тексте. А доля, которую эти диграммы составляют от общего количества диграмм, есть вероятность появления буквы в тексте, т. е. 0,10. Обозначим эту вероятность ; тогда можно записать .
Отметим, что эта вероятность — не только доля диграмм, начинающихся с буквы Т, но и доля распределенных по разным шляпам диграмм, кончающихся буквой Т.
Далее, если общее число букв в тексте 1001 и, следовательно, количество последовательных диграмм 1000, то диграмма ТН встретится 37 раз, и поэтому вероятность ее появления мы обозначим р (Т, Н), и она равна р (Т, Н) = 0,037.
Теперь ясно, что 100 диграмм, или 0,10 часть всего их количества, будут начинаться с буквы Т и они попадут, следовательно, в шляпу Т, а 37 из них будут диграммы ТН. Таким образом, доля диграмм ТН от всего количества диграмм, начинающихся с буквы Т, будет равна 37/100, или 0,37. Соответственно мы говорим о вероятности Рт(Н) того, что диграмма, начинающаяся с буквы Т, будет ТН, т. е. Pт(Н) = 0,37; Pт(Н) — это условная вероятность появления буквы Н после буквы Т.
Вероятности появления диграмм можно использовать, чтобы построить текст, в котором и буквы, и диграммы появляются с той же частотой, что и в английском языке. Для этого вытащим наудачу карточку из любой шляпы и выпишем проставленные на ней буквы. Затем по второй букве первой диграммы определим шляпу, из которой нужно вытащить вторую карточку, и выпишем вторую букву второй диграммы. Затем по второй букве второй диграммы определим шляпу, из которой нужно вытащить третью, и т. д. Пробел можно считать буквой, так как имеется вполне определенная вероятность того, что после данной буквы будет пробел (окончание «слова»), а также имеется вполне определенная вероятность того, что после пробела будет стоять определенная буква (начало «слова»).
Подобным методом Шеннон построил то, что он называет приближением второго порядка к английскому языку.
3. Приближение второго порядка (структура диграмм такая же, как в английском языке):
Шифровальщики составили таблицы вероятностей появления групп из трех букв, так называемых триграмм. С помощью этих вероятностей можно получить то, что Шеннон называет приближением третьего порядка к английскому языку. Приведем пример из его работы:
4. Приближение третьего порядка (структура триграмм такая же, как в английском языке).
5. Приближение первого порядка на уровне слов. Вместо того чтобы продолжать процесс приближения с помощью структур тетраграмм n-грамм, легче и лучше сразу перейти к словарным единицам. Здесь слова выбираются независимо, но с соответствующими им частотами:
6. Приближение второго порядка на уровне слов. Переходные вероятности от слова к слову являются правильными, но никакая дальнейшая структура не учитывается:
НА САМОСТОЯТЕЛЬНУЮ РАБОТУ
С помощью доступных приложений написать программу, с помощью которой аппроксимировать естественный русский (украинский) язык для шести вариантов приближений.
С каждым из шагов, проделанных выше, сходство с обычным английским текстом возрастает довольно заметно. Отметим, что эти примеры имеют достаточно хорошую структуру в пределах расстояний, которые приблизительно в два раза превышают расстояния, учтенные при конструировании.
Например, в случае 3 статистический процесс обеспечивает формирование приемлемого текста для двухбуквенных последовательностей, но и четырехбуквенные последовательности из этой выборки обычно могут быть вставлены в осмысленные предложения.
В примере 6 последовательности из четырех или более слов могут быть довольно легко вставлены в предложения без необычных или натянутых конструкций. Последовательность из десяти слов «attack on an English writer that the character of this» не является совершенно неприемлемой. Таким образом, оказывается, что достаточно сложный вероятностный процесс дает удовлетворительное представление дискретного источника.
Первые два примера были построены с помощью таблиц случайных чисел, а также (для примера 2) таблицы частот различных букв.
Точно так же можно было бы построить и примеры 3, 4 и 5 , так как частоты диграмм, триграмм и отдельных слов известны, но мы использовали более простой эквивалентный метод. Например, чтобы построить пример 3, можно открыть книгу случайным образом и выбрать также случайно букву на странице. Эта буква записывается. Затем книга открывается на другой странице и читается до тех пор, пока не встречается записанная буква. Следующая за ней буква записывается. Затем на другой странице ищется эта последняя буква и записывается следующая за ней и так далее. Аналогичный процесс был использован для составления примеров 4, 5 и 6.
Вероятностные процессы описанного выше типа известны в математике как дискретные марковские процессы или цепь Маркова.
Нестрогое определение. Цепь Маркова — последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем свойством, что, говоря нестрого, при фиксированном настоящем будущее независимо от прошлого. Названа в честь А. А. Маркова (старшего).
Строгое определение. Цепь Маркова с дискретным временем
Последовательность дискретных случайных величин называется простой цепью Маркова (с дискретным временем), если
Таким образом, в простейшем случае условное распределение последующего состояния цепи Маркова зависит только от текущего состояния и не зависит от всех предыдущих состояний (в отличие от цепей Маркова высших порядков).
Область значений случайных величин называется пространством состояний цепи, а номер — номером шага.
Графическое представление марковского процесса
Общий случай может быть описан следующим образом: существует конечное число возможных «состояний» системы: S1, . . ., Sn. Кроме того, имеется совокупность условных вероятностей рi(j), т. е. вероятностей того, что система, находящаяся в состоянии Si, перейдет затем в состояние Sj,.
Чтобы использовать этот марковский процесс в качестве источника сообщений, нужно только предположить, что при каждом переходе из одного состояния в другое создается одна буква. Состояния будут соответствовать «остатку влияния» предшествовавших букв.
Это положение может быть графически проиллюстрировано, как показано на рис. 3, 4 и 5. «Состояниями» являются узловые точки схемы, а условные вероятности и создаваемые при этом буквы указаны около соответствующих линий.
Рис. 3. Граф, соответствующий источнику в примере Б
Рис. 3 соответствует примеру Б ( выбираются независимо с вероятностями ), где имеется только одно состояние, так как последовательные буквы независимы.
Рис. 4. Граф, соответствующий источнику в примере В
Рис. 4 соответствует примеру В (вероятности появления букв зависят от предыдущей буквы), где имеется столько же состояний, сколько букв. Если бы конструировался триграммный пример, то имелось бы самое большее n2 состояний, соответствующих возможным парам букв, предшествующих выбираемой букве.
|
0,10 А |
0,16 ВЕВЕ |
0,11 CABED |
0,04 DEB |
|
0,04 ADEB |
0,04 BED |
0,05 CEED |
0,15 DEED |
|
0,05 ADEE |
0,02 BEED |
0,08 DAB |
0,01 EAB |
|
0,01 BADD |
0,05 СА |
0,04 DAD |
0,05 ЕЕ |
Рис.5. Граф, соответствующий источнику из примера Г
Рис. 5 представляет схему для случая структуры слов в примере Г (в языке пять букв и 16 «слов» с соответствующими вероятностями появления). Здесь S соответствует символу «пробел между словами».
Как уже было отмечено, дискретный источник в описанных ранее задачах может рассматриваться как марковский процесс. Среди всех возможных марковских процессов можно выделить группу со свойствами, важными для теории связи. В этот класс входят так называемые эргодические процессы, и мы будем называть соответствующие источники эргодическими.
Для эргодического процесса все сгенерированные последовательности обладают одинаковыми статистическими свойствами. К примеру, частоты встречаемости букв, диграмм и так далее, оцененные по отдельным последовательностям, сходятся с ростом длины выборок к определенным пределам, не зависящим от последовательности.
Другое определение эргодичности. Стационарный случайный процесс называют эргодическим, если при нахождении его моментных функций усреднение по статистическому ансамблю можно заменить усреднением по времени. Операция усреднения выполняется над единственной реализацией x(t), длительность Т, которой теоретически может быть сколь угодно велика.
На самом деле это верно не для всякой последовательности, однако множество последовательностей, для которых это не выполняется, имеет меру ноль (то есть обладает нулевой вероятностью). Грубо свойство эргодичности означает статистическую однородность.
Все вышеприведенные примеры искусственных языков являются эргодическими. Это связано со структурой соответствующих графов. Шеннон определил, что если граф обладает двумя следующими свойствами, соответствующий процесс будет эргодическим:
В математической литературе принято называть эргодическими процессы, обладающие свойством 1) и, быть может, не обладающие свойством 2).
Если первое условие удовлетворено, а второе нарушено тем, что общий делитель d > 1, то последовательности имеют некоторого рода периодическую структуру.
Различные последовательности распадаются на d различных классов, которые в статистическом отношении одинаковы, за исключением сдвига начала (т. е. выбора того, какую букву последовательности назвать первой). С помощью смещения на величину от 0 до d1 каждая последовательность может быть сделана статистически эквивалентной любой другой.
При d — 2 простым примером является следующий: имеются три возможные буквы а, b, с. За буквой а следует либо b, либо с с вероятностями 1/3 и 2/3 соответственно. За b и с всегда следует буква а.
Тогда типичная последовательность имеет вид:
abacacacabacababacac
Процессы такого типа не учитываются в контексте модели источника сообщений.
Если нарушено первое условие, то граф может быть разделен на некоторое число подграфов, каждый из которых удовлетворяет первому условию. Будем предполагать, что второе условие также выполняется для каждого подграфа. В этом случае имеет место то, что может быть названо «смешанным» источником, составленным из некоторого числа чистых компонент классов состояний. Эти классы состояний соответствуют различным подграфам. Если L1, L2, L3...— источники, соответствующие этим классам, то можно записать
L = p1L1 + p2L2 + p3L3 + …
где pi— вероятность класса Li.
Физический смысл описанного состоит в следующем: имеется несколько различных источников L1, L2, L3..., каждый из которых имеет однородную статистическую структуру (т.е. является эргодическим). Априори неизвестно, какой источник будет использован, но если последовательность начинается с состояния, принадлежащего данному классу состояния Li, то она продолжается бесконечно в соответствии со статистической структурой этого класса.
В качестве примера можно взять два процесса из определенных выше и предположить, что p1= 0,2 и р2= 0,8. Последовательность из смешанного источника L = 0,2L1 + 0,8L2 могла бы быть получена следующим образом: сначала выбирается L1 или L2 с вероятностями 0,2 и 0,8, а затем выбранный источник создает последовательность. Если не оговорено противное, будем предполагать, что источник является эргодическим. Такое предположение позволяет отождествлять средние значения вдоль некоторой последовательности со средними значениями по ансамблю возможных последовательностей (причем вероятность расхождения равна нулю).
Например, относительная частота буквы в частной бесконечной последовательности будет с вероятностью единица равняться ее относительной частоте по ансамблю последовательностей.
Если pi — вероятность состояния i, a рi(j) — условная вероятность перехода в состояние j, то для того, чтобы процесс был стационарным, pi должны, очевидно, удовлетворять условиям равновесия:
Можно показать, что в эргодическом случае при любых начальных условиях вероятности пребывания в состоянии j после N шагов Pj(N) при N стремятся к величинам, удовлетворяющим условиям равновесия.
Висновки
Контрольні питання