Теория вероятности. Вентцель Е.С (4-е издание) (1082431), страница 87
Текст из файла (страница 87)
Поэтому данный принцип кодирования может быть рекомендован только в случае. когда ошибки при кодировании и передаче сообщения практически исключены. Возникает естественный вопрос: а является лн составлеиный нами код при отсутствии ошибок действительно оптимальным? Для того чтобы ответить на этот вопрос, найдем среднюю информацию, приходящуюся на один элементарный символ (О нли 1), н сравним ее с манснмально возможной информацией, которая равна одной двоичной единице.
Для этого найдем сначала среднюю информацию, содержащуюся в одной букве передаваемого текста, т. е. энтропию на одну букву: зт зт Н (б) = — ~~'„~ р, 1од р, = ~~'., т) (р ), 1=1 !=! где р! — вероятность того, что буква примет определенное состояние (« — », о, е, а, ..., ф). Из табл. 18.8.1 имеем Н(б)=т)(0,145)+т1(0,095)+ ... +«1(0,003)+т)(0,002) ж 4,42 (дв.
единиц на букву текста). По таблице 18.8.2 определяем среднее число элементарных символов на букву п«р — — 3 ° О,! 45+ 3 ° 0,095+ 4 ° 0,074.+ ... +.9 ° 0,003+9 ° 0.002 =4,45. Деля энтропию Н(б) на л,р, получаем информацию на один эле!уентарный символ /!' 445 = 0,994 (дз. ед.). 4,42 Таким образом, информация на один символ весьма близка к своеэгу верхнему пределу 1, а выбранный нами код весьма близок к оптимальному. Оставаясь в пределах задачи кодирования по буквам, мы ничего лучшего получить не сможем. Заметим, что в случае кодировзния просто двоичных номеров букв мы имели бы изображение каждой буквы пятью двоичными знаками и информация на один символ была бы 5Ю вЂ” 0,884 (дв. ед.), 4,42 т. е. заметно меньше.
чем при оптимальном буквенном кодировании, Однако надо заметить, что' кодирование «по буквам» вообще не является экономичным. Дело в том, что между соседними буквами бб8 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИНФОРМАЦИИ >гл. >з любого осмысленного текста всегда имеется завис и масть. Например, после гласной буквы в русском языке ле может стоять «ъ» илн «ь»; после шипящих не могут стоять «я» или «ю»; после нескольких согласных подряд увеличивается вероятность глзсной и т. д. Мы знаем, что при объединении зависимых систем суммарная энтропия меньше суммы энтропий отдельных систем; следовательно, информация, передаваемая отрезком связного текста, всегда меньше.
чем информация нз один символ, умноженная на число символов. С учетом этого обстоятельствз более экономный код можно построить. если кодировать не каждую букву з отдельности, а целые «блоки» из букв. Например, в русском тексте имеет смысл кодировать целиком некоторые часто встречающиеся комбинации букв, как «тся», «ает», «нне» и т. л. Коднруемые блоки располагаются в порядке убывания частот, как буквы в табл. 18.8.1, а двоичное кодирование осуществляется по тому же принципу.
В ряде случаев оказывается разумным кодировать лзже не блоки из букв, а целые осмысленные куски текста. Например, для разгруаки телеграфа в предпраздничные дни целесообразно кодировать условными номерами целые стандартные тексты, вроде: «поздравляю новым годом желаю здоровья успехов работе». Не останавливаясь специально на методах кодирования блокзми, ограничимся тем, что сформулируем относящуюся сюда теорему Шеннона. Пусть имеется источник информации Х и приемник У, связанные каналом связи Х (рис.
18.8.1). Известна производительность источника информации Н>(Х), т. е. среднее количество двоичных единиц информации, поступающее от источника з единицу времени (численно А б у оно равно средней энтропии сообщения, производимого источником в единицу времени). Пусть, кроме того, известна праРнс. 18.8.1. пускная способность канала С>, т. е. максимальное количество йнформации 1например, двоичных знаков 0 илн 1), которое способен передать канал а ту же единицу времени.
Возникает вопрос: какова должна быть прооуш нзя но«обнос;>, капала. ПОГИ оо «справлялся» со своей задачей, т. е. чтобы информация от источника Х к приемнику У поступала без задержки? Ответ на этот вопрос дает первая теорема Шеннона. Сформулируем ее здесь без доказательства. 1-я теорема Шеннона Если пропускная способность канала связи С, больше энтропии исп>оьника инФормации з единицу зремени пеРедАчА инно»млцин с искажениями 509 Ы,91 то всегда можно закодировать достаточно длинное сообиге- кие так, чтобы ояо передавалось каналом связи без задержки. Если же, напротив, .
С, ()т',1Х), то передача информации без задержек невозможна. 18.9. Передача информации с искажениями. Пропускная способность канала с помехвмн В предыдущем и' мы рассмотрели вопросы, связанные с кодированием и передачей информации по каналу связи в идеальном случае, когда процесс передачи информации осуществляется без ошибок. В действительности этот процесс неизбежно сопровождается ошибками (искажениями). Канал передачи, в котором возможны искажения, называется каналом с помехами (или шумами). В частном случае ошибки возникают в процессе самого кодирования, и тогда кодирующее устройство может рассматриваться как канал с помехами.
Совершенно очевидно, что наличие помех приводит к потере информации, Чтобы в условиях наличия помех получить на приемнике требуемый обьем информации, необходимо принимать специальные меры. Одной из таких мер является введение так называемой «нзбыточности» в передаваемые сообщения; при этом источник информации выдает заведомо больше символов, чем это было бы нужно при отсутствии помех. Одна из форм введения избыточности — простое повторение сообщения. Таким приемом пользуются, например, при плохой слышимости по телефону, повторяя каждое сообщение дважды.
Другой общеизвестный способ повышения надежности передачи состоит в передаче слова «по буквам» вЂ” когда вместо каждой буквы передается хорошо знакомое слово(имя), начинающееся с этой буквы. Заметим, что все живые языки естественно обладают некоторой избыточностью. Эта избыточность часто помогает восстановить правильный текст «по смыслу» сообщения.
Вот почему встречающиеся вообще нередко искажения отдельных букв телеграмм довольно редко прьводяг ь дгзс1з|г1 ел»ной гютерс информации: обьщно удается исправить искаженное слово, пользуясь одними только свойствами языка. Этого не было бы при отсутствии избыточности. Мерой избыточности языка служит величина 1) 1 ~~с 1ояп ' 118.9.1) где Нм — средняя фактическая энтропия, приходящаяся на олин передаваемый символ 1букву), рассчитанная для достаточно длинных отрывков текста, с учетом зависимости между символами, и — шсло 510 основныв понятия теогнн инэовмлцни 1гл. ~а применяемых символов (букв), !ояп — максимально возможная в данных условиях энтропия иа один передаваемый символ, которая была бы, если бы все символы были равновероятны и независимы.
Расчеты, проведенные на материале наиболее распространенных европейских языков, показывают, что их избыточность достигает 5088 и более (т. е., грубо говоря. 50та передаваемых символов являются лишними и могли бы не передаваться, если бы не опасность искажений). Однако для безошибочной передачи сведений естественная избыточность явыка может оказаться как чрезмерной, так и недостаточной: все зависит от того, как велика оласность искажениИ («уровень помех») в канале связи. С помощью методов теории информа- ции можно для каждого уровня помех Ряс. !8«д1.
найти нужную степень избыточности источ- ника информации, Те же методы помогают разрабатывать специальные помехоустойчивые коды (в частности. так называемые «самокорректирующиеся» коды). Для решения этих задач нужно уметь учитывать потерю информации в канале, связанную с наличием помех.
Рассмотрим сложную систему, состоящую из источника информации Х, канала связи К и приемника У (рис, 18.9.1). Источник информации представляет собой физическую систему Х, которая имеет и возможных состояний х1 хм» " хл с вероятностями Р1 Рн ''' Рж Будем рассматривать эти состояния как элементарные символы, которые может передавать источннк Х через канал К к приемнику У, Количество информации на один символ, которое даат источник, будет равно энтропии на один символ: ч Н(Х) = — ~ р;1оу ри Если бы передача сообщений не сопровождалась ошибками, то коли чество информации, содержащееся в системе У относительно Х, было бы равно самой энтропии системы Х, При наличии ошибок оно будет меньше: ге+-+х = Н(Х) — Н(Х | У), Естественно рассматривать условную энтропию Н(Х ) У) как погяерв информвйии на один элементарный символ, связанную с наличием помех.
чзл! пвяидлча ииэогмлции с нсклжвниями 511 Умея определять потерю информации в.канале, приходящуюся на один элементарный символ, переданный источником информации, можно определить п рону с к ную способность канала с помехами, т. е. максимальное количество информации, которое способен передать канал в единицу времени. Предположим, что канал может передавать в единицу времени Ф элементарных символов. В отсутствие помех пропускная способность канала была бы равна С=я!ояи, (18.9.2) так как максимальное количество информации, которое может содержать один символ, равно !оял, а максимальное количество информации, которое могут содержать Ф символов, равно й!спи, и оио достигается, когла символы появляются независимо друг от друга.
Теперь рассмотрим канал с помехами. Его пропускная способность определится как С = й так 1'у'. л, (18.9.3) где шахах+к — максимальная информация на один символ, которую лп может передать канал при наличии помех. Определение этой максимальной информации в общем случае— дело довольно сложное, так как она зависит оттого, как и с какими вероятностями искзжаются символы; происходит ли их перепутывание, или же простое выпадение некоторых символов; происходят ли искажения символов независимо друг от друга н т. д.
Однако для простейших случаев пропускную способность канала удается сравнительно легко рассчитать. Рассмотрим, например, такую задачу. Канал связи К передает от источника информации Х к приемнику )' элементарные символы 0 и 1 в количестве л символов в единицу времени. В процессе передачи каждый символ, независимо от других, с вероятностью р может быть искажен (т, е. заменен противоположным).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
