vopros-otvet (519806), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Различают две составляющие избыточности:

• избыточность, обусловленная статистической взаимосвязью букв между собой:

,

где H(X) – энтропия для букв, когда они неравновероятны и взаимосвязаны;

H₁(X) – энтропия для букв, когда они статистически не взаимосвязаны и неравновероятны.

• избыточность, обусловленная распределением вероятностей между буквами алфавита:

.

Между R; R_р и R_с существует зависимость: R = R_р + R_с + R_р · R_с.

Если R_р и R_с – невелики, то R ≈ R_р + R_с.

Укрупнение алфавита с M₁ элементов алфавита до M₂ ≥ M₁(M₂ = M₁ⁿ) не изменяет избыточности: R₁ = R₂.

Но статистические связи между элементами укрупненного алфавита падают R_с ≈ 0; следовательно возрастает неравномерность употребления отдельных букв алфавита M₂, то есть R_р2 >> R_р1; R_р2 ≈ R₁ ≈ R₂.

Доказательство, что R₁ ≈ R₂ сводится к следующему:

1. Подсчитаем H₂(X):

Из свойства аддитивности информации следует, что в одном элементе второго алфавита содержится столько же информации, сколько ее содержится в n элементах первичного алфавита. Среднее количество информации на один элемент первого алфавита – H₁; математическое ожидание на n элементов первого алфавита – n · H₁ равно информации на один элемент второго алфавита H₂(X) = n · H₁.

2. Избыточность второго алфавита

.

Избыточность языка подсчитывается по формуле:

,

где H_max = log M, а M – число букв в алфавите.

Избыточность языка можно подсчитывать для H₀; H₁; H₂;...H_N, где

H_∞(X) = 0.87÷1.37^бит⁄_буква,

а 0; 1; 2… – количество букв между которыми учитываются взаимосвязи.

Примеры.

1. Во сколько раз больше содержится информации на странице текста для иностранца, начавшего изучать новый для себя язык (например, русский) и для носителя языка?

Ответ. Для носителя языка среднее количество информации на одну букву определяется как H_языка ≈ H₃₀ = 1.35^бит⁄_буква, а для иностранца, плохо знающего словарь и не учитывающему взаимосвязь букв между собой H = H₀ или H₁, что соответствует

,

а

^бит⁄_буква.

То есть на странице текста для носителя языка содержится информации в

раза меньше информации, чем для иностранца. Частичное знание словаря и закономерностей языка уменьшает эту разницу.

2. Во сколько раз удлиняется текст в деловых бумагах, если их избыточность составляет 90÷95%?

Ответ. При такой избыточности энтропия на одну букву составляет:

;

;

H_¶(X) = 0.25÷0.5^бит⁄_буква.

В то время как в письменной речи: H_∞(X) = 0.87÷1.37^бит⁄_буква.

Текст удлиняется в раз.

9. Взаимосвязь между энтропией и числом сообщений.

При работе линии связи большое значение имеют статистические закономерности больших последовательностей букв.

Пусть имеет место алфавит из M букв, а источником выдается последовательность из N букв.

Возможное число различных последовательностей – M ^N. Вероятности появления каждой из них при неравной вероятности букв, из которых они состоят, различны.

Оказывается, что для таких последовательностей можно доказать теорему:

«Как бы ни были малы два числа ε > 0 и δ > 0 при достаточно большом N все последовательности могут быть разбиты на две группы.

Первая группа включает подавляющее число (большинство) таких последовательностей, каждая из которых будет иметь настолько ничтожную вероятность, что даже суммарная вероятность всех таких последовательностей очень мала и при достаточно большом N будет меньше сколь угодно малого числа ε > 0. Эти последовательности называются нетипичными.

Вторая группа (типичные последовательности) при достаточно большом N отличается тем, что вероятности этих последовательностей почти не отличаются друг от друга. Вероятность ( p) появления каждой из них удовлетворяет неравенству:

где – энтропия на целую последовательность;

– энтропия на букву;

H – энтропия источника с учетом статистических связей и неравновероятности букв.

Другими словами, почти достоверно, что весьма близко к H, когда N – велико – это свойство ассимптотической равновероятности достаточно длинных последовательностей (N > 1000).

Для достаточно длинных последовательностей с весьма малой погрешностью можно ожидать, что

или , откуда ,

а число типичных последовательностей

(точнее это можно записать так:

,

где δ – сколь угодно мало).

Доказательство сложно. Для простейшего случая отсутствия статистических связей теорема является следствием закона больших чисел, который можно изменить так: с вероятностью близкой к 1 в длинной последовательности из N элементов будет N·p₁ – элементов первого алфавита, N·p₂ – второго и т.д. (частота встречаемости стремится к вероятности при числе испытаний стремящихся к бесконечности). Следовательно, для типичной последовательности вероятность её появления будет равна:

,

откуда

и

.

Типичные последовательности составляют лишь незначительную часть всех возможных последовательностей. Число всех возможных последовательностей длиной в N-букв равно:

.

Число типичных последовательностей:

.

Следовательно,

,

так как .

Доля нетипичных последовательностей велика.

Решим такую задачу.

Какова вероятность того, что обезьяна путём случайных нажатий на клавиатуре пишушей машинки, имеющей всего 32 клавиши (буквы и пропуск), наберет типичное сообщение длиною N = 20 букв?

Решение

Обезьяна путем случайных нажатий может создать одно из Q_е сообщений:

.

Из них имеют смысл только те, что соответствуют языку, т.е. типичным сообщениям.

.

Вероятность того, что случайно набранное сообщение будет типичным равна:

.

Эта вероятность бесконечно мала.

10. Пропускная способность двоичного канала.

Нарисуем схему передачи информации.

Рис. 2.9

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

Рис. 2.10

Введены следующие обозначения:

• вероятность безошибочной передачи "0" – , т.е. вероятность получения "0" на приёмной стороне, если передавался "0";

• – вероятность получения единицы на приёмной стороне, если передавался "0";

• аналогично введем и ;

• P_y(0) и P_y(1) – вероятности встречаемости нуля и единицы на передающей стороне;

• P_z(0) и P_z(1) – вероятности встречаемости нуля и единицы на приёмной стороне.

Конечно, выполняются условия:

Подсчет пропускной способности линии связи будем вести по формуле:

где V_{лс max} – максимальная скорость передачи импульсов по данной линии связи;

– максимальное количество информации, приходящееся в среднем на один символ.

V_{лс max} считается по формуле

, (2.2)

где Δt_min – минимально допустимый интервал времени для передачи по данной линии связи.

Он определяется физическими свойствами линии связи (тонкий или толстый коаксиал; витая пара; оптический канал). Δt_min определяется по формуле Котельникова В.А. (будет рассмотрена в главе 8) по формуле:

, (2.3)

где F_max – максимальная частота, пропускаемая этим каналом. Она определяется экспериментально путём подачи на вход канала сигнала постоянной амплитды и переменной частоты. Если амплитуда на выходе канала упадет до , то эта частота и принимается за максимальную (см. рис. 2.11).

Рис. 2.11

зависит от помех и от вероятностей встречаемости нулей и единиц на передающей стороне.

. (2.4)

. (2.5)

H_апост(Z) – это остаточная неопределенность на приёмной стороне, если известно какой символ со стороны Y передавался.

P_z(0) и P_z(1) – определяют априорную неопределенность на стороне "Z". При этом

; (2.7)

. (2.8)

Все необходимые для расчета пропускной способности линии связи формулы приведены.

Рассмотрим три частных случая.

1. Отсутствие ошибок, т.е. .

Тогда P_z(0) = P_y(0) и P_z(1) = P_y(1); ;

То есть в этом случае максимальная пропускная способность линии связи равна максимальной скорости передачи нулей и единиц по этой линии связи при условии, что вероятность передачи нулей и единиц на передающей стороне одинакова, т.е. P_y(0) = P_y(1) = 1/2.

2. Имеет место , т.е. доля ошибок при передаче нулей и единиц одинакова. Это двоичный симметричный канал.

Подставив p_ош в формулу 2.6, имеем:

а формула 2.1 может быть видоизменена

3. При придётся воспользоваться всем набором формул от 2.1 до 2.8. Лучше решать задачу не в общем виде, а подставлять числовые значения и .

Вероятность P_y(0), дающую , искать через приравнивание I '_{на 1 символ}(Z; Y) нулю. Решение уравнения I '(Z; Y) = 0 получить графически, задавая различные значения P_y(0).

11. Согласование характеристик сигнала и канала.

Рассмотрим три основных параметра сигнала, существенных для передачи по каналу.

1. Время передачи по каналу – T_y.

2. Мощность передаваемого сигнала – P_y с определенным уровнем помех – P_ξ, т.е. отношение сигнал/помеха

.

Или логарифм отношения мощностей сигнала к помехе, называемым превышением сигнала над помехой,

Характеристики

Список файлов ответов (шпаргалок)