Лекция №4 По дисциплине Теория информации - shikardos.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Вопросы к экзамену по дисциплине «Информатика» 1 66.04kb.
Рефератов и курсовых работ по дисциплине «Экономическая теория» 1 29.96kb.
Рефератов и курсовых работ по дисциплине «Экономическая теория» 1 30.17kb.
Лекция Введение в макроэкономику Предмет макроэкономики 11 1362.8kb.
Маркова Ирина Васильевна 1-ая неделя 16: 40-18: 10 1306 Теория принятия... 1 41.79kb.
Рабочая программа по дисциплине дс. 02 1 «Риторика и теория речевых... 2 410.7kb.
Не допускается 1 288.5kb.
Учебно-методический комплекс по учебной дисциплине Теория государства... 14 6458.41kb.
Курсовая работа по учебной дисциплине «История и теория Социально-Культурной... 3 1031.35kb.
Учебно-методический комплекс по дисциплине правовая защита информации 4 933.09kb.
Программа вступительного экзамена в аспирантуру по дисциплине «онтология... 1 111.04kb.
Техническое задание на организацию и предоставление в пользование... 1 40.2kb.
- 4 1234.94kb.
Лекция №4 По дисциплине Теория информации - страница №1/1

КАФЕДРА

ПРИКЛАДНОЙ ИНФОРМАТИКИ



ЛЕКЦИЯ № 4



По дисциплине

Теория информации







Тема № 3

Информационные модели сигналов систем





полное наименование темы


Занятие № 7

Передача информации .




полное наименование занятия



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

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

2. Пропускная способность дискретного канала без помех

3. Пропускная способность дискретного канала с помехами

4. Пропускная способность непрерывного канала с помехами




1. Информационная модель канала
В этом разделе мы переходим к рассмотрению методов кодирования информации.

Вернемся к модели обобщенного канала передачи данных, рассмотренной в подразделе 1.4. Чтобы сосредоточиться на проблемах кодирования, упростим ее и представим в виде рис.4.1.




Рис. 1.1

В этой модели мы будем рассматривать передачу по некоторому абстрактному (виртуальному) каналу передачи кодовых последовательностей.



Источник И передает получателю П дискретные сообщения в алфавите Z (напомним, что в частном случае они могут нести информацию о непрерывном сообщении, предварительно приведенном источником к дискретному виду).

Скорость выработки символов источником Vz = 1/tz, где tz - среднее время, приходящееся на один символ Zi. Hz - энтропия набора символов Zi.



Кодер КД преобразует алфавит Z, объема n, в алфавит X, объема m, удобный для передачи по каналу (чаще всего X - двоичный алфавит, включающий символы "1" и "0"). Кодер нередко выполняет кодирование в несколько этапов, реализуя в различных сочетаниях сжатие данных, защиту от ошибок передачи и шифрование. В любом случае скорость выработки разрядов кода Vx = 1/tx, где tx- среднее время передачи одного разряда.

В канале передачи КП могут возникать ошибки с вероятностью ро. (На рисунке показан условный источник помех ИП, который порождает эти ошибки). В связи с этим разряды кода Yj на выходе канала могут отличаться от разрядов Xj на входе.

Таким образом, возникает неопределенность Hx/y - принятому Yj неоднозначно отвечает Xj, а количество переданной с каждым разрядом информации Ixy = Hx - Hx/y. Интересно, что канал можно рассматривать и в другой "проекции": энтропия разрядов на его выходе Hy, а неопределенность по отношению к принятым разрядам Hy/x, при этом количество переданной информации Ixy = Hy - Hy/x.



Наконец, декодер ДК преобразует принятые разряды кода в символы для получателя (из-за ошибок алфавит Z* может не совпадать с Z.

Очевидно, что для эффективного использования канала скорость источника Vz необходимо согласовать с пропускной способностью канала С.

Дальше мы рассмотрим, как определить эту пропускную способность для случаев канала с ошибками и без ошибок, при передаче дискретных и непрерывных сообщений. Результаты, о которых пойдет речь, получены Клодом Шенноном и относятся к классике теории кодирования.
2. Пропускная способность дискретного канала без помех
Определим пропускную способность канала как максимальное количество информации, которое можно передавать по нему в единицу времени:

C = max{Ixy}/ tx (бит/с) (4.1)

Для канала без помех справедливо условие Ixy = Hx, а потому его пропускная способность:



Cбп = max{Hx}/ tx = log2m / tx (4.2)

В частном случае передачи двоичных разрядов (m = 2) справедливо



Сбп = 1/tx (4.3).

Для нас важно, как соотносится величина Сбп с потоком информации источника H`z, который определяется по формуле



H`z = Hz/tz (бит/с) (4.4).

Пропускная способность канала используется полностью, когда H`z = C. Между тем, уменьшение энтропии Hz может привести к сокращению информационного потока. Чтобы его увеличить, требуется сократить время tz. Если учесть, что



tz = tx * lср, где lср - средняя длина кода символа, то становится ясно: чтобы полнее использовать пропускную способность канала для любого источника, нужно рационально кодировать сообщения, по возможности сокращая величину lср.

Если записать условие полного использования пропускной способности канала H`z = C в развернутом виде, то для канала без помех оно будет иметь вид:



Hz/tz = log2m/tx (4.5),

а с учетом tz = tx * lср и log2m = 1 (при m=2) мы получим условие:


lср = Hz (4.6)
По сути, доказательство этой так называемой теоремы Шеннона о кодировании для канала без помех сводится к нахождению процедуры, позволяющей получить требуемый код. Эта процедура, именуемая эффективным кодированием, была предложена самим Шенноном и в дальнейшем усовершенствована (с точки зрения удобства ее практического применения) Хаффменом.

В обоих случаях речь идет о посимвольном кодировании и величина Hz имеет значение безусловной энтропии. В принципе можно пойти дальше и рассматривать кодирование цепочек символов. В этом случае Hz будет иметь смысл условной энтропии порядка l, где l - максимальная длина цепочки. О "цепочечном" кодировании речь впереди, а пока мы рассмотрим классический подход к эффективному кодированию на уровне символов.


3. Пропускная способность дискретного канала с помехами
Рассмотрим теперь вариант, когда помехи в канале вызывают появление ошибок с вероятностью p0. В этом случае из соотношения 3.1 следует:

C = max {Hx - Hx/y}/ tx = (log2m - Hx/y) / tx (4.8)
Рассмотрим наиболее распространенный случай так называемого двоичного симметричного канала. При этом m = 2 (log2m = 1), а вероятности ошибки “переход "1" в "0” ” “переход "0" в "1" ” одинаковы.

Если теперь рассмотреть в качестве случайного события передачу разряда кода с ошибкой (вероятность p0), то, используя формулу (2.8) для определения энтропии, получим:



Hx/y = Hy/x = -p0 log2p0 - (1 - p0) log2(1 - p0) (4.9)
С учетом этого (4.8) преобразуется к виду:
C = [1 - p0log2p0 - (1 - p0)log2(1 - p0)]/tx (4.10)

Таким образом, пропускная способность симметричного двоичного канала с помехами определяется только скоростью передачи разрядов кода (Vx = 1/tx) и вероятностью ошибок.

На рис. 4.2 показана зависимость C(p0). Как видно, даже относительно небольшой процент ошибок приводит к значительному снижению пропускной способности канала (например, при p0 = 0.1, она падает более чем вдвое), а при p0 = 0.5 канал вообще не способен пропускать информацию.

Клод Шеннон показал, что за счет кодирования пропускную способность канала с помехами также можно использовать максимально полно (напомним, что сама она будет ниже, чем у канала без помех).

Способ кодирования, который позволяет этого добиться, основан на использовании избыточных кодов, когда каждый информационный блок защищается контрольными разрядами и чем больше длина блока, тем меньше удельный вес этих избыточных разрядов, позволяющих обнаружить и исправить ошибки. Вопросы применения корректирующих кодов мы рассмотрим в разделе 5.



4. Пропускная способность непрерывного канала с помехами
На рис. 4.1 была показана модель дискретного канала передачи данных. Напомним, что с помощью дискретизации и квантования к дискретному виду можно свести любое непрерывное сообщение. Однако, если шаг квантования dx и шаг дискретизации dt устремить к нулю, то из модели рис. 4.1 мы получим частный случай непрерывного канала (рис. 4.3).

Рис. 1.1
Источник И передает в канал непрерывное сообщение Z(t).



Формирователь сигналов Фс преобразует его в сигнал X (t), приспособленный для передачи по аналоговому каналу.

В линии связи ЛС на сигнал воздействуют случайные аддитивные помехи e(t) (для помех такого типа справедливо соотношение Y(t) = X(t) + e(t)).

Устройство распознавания сигнала восстанавливает сообщение Z(t) по полученному Y(t).

В этой схеме стадия кодирования вообще не рассматривается. Однако подход (кстати, предложенный опять-таки Клодом Шенноном) основан на тех же принципах, что и для дискретного канала, потому нам целесообразно рассмотреть этот вопрос именно здесь.

Вернемся к определению пропускной способности канала связи:

Cбп = max{Ixy} / tx = max{Hx } / tx (4.11)

Величина tx в нашем случае соответствует шагу дискретизации сигнала dt. Согласно теореме Котельникова, непрерывный сигнал можно полностью восстановить по его дискретным отсчетам, если шаг дискретизации dt вдвое меньше периода самой высокочастотной составляющей fm сигнала (dt = 1/2fm). Учитывая, что любой физический канал связи всегда имеет ограниченную полосу частот, которые он в состоянии пропустить, величину fm (а следовательно и dt) можно определить исходя из характеристик канала.

Если значение dx конечно, то непрерывный канал можно рассматривать как дискретный с объемом алфавита m = xm/dx + 1. Если к тому же в канале отсутствуют помехи (Hx/y = 0), то соотношение (4.11) можно преобразовать к виду:

C = max {Hx} / dt = 2fm * log2m = 2fm * log2 (xm/ dx + 1) (4.12)

Отсюда видно, что пропускная способность непрерывного канала без помех (dx -> 0) стремится к бесконечности. Однако, в реальном канале помехи присутствуют всегда, при этом сколько бит информации удается "нагрузить" на один дискретный отсчет, зависит от соотношения мощности полезного сигнала на входе приемника и помехи Pс/Pп.



Клод Шеннон показал, что в случае наиболее "неприятной" помехи типа "белый шум", чья мощность равномерно распределена во всей полосе частот канала, справедливо соотношение:

Cn = fm log2(Pс/Pп + 1) (4.13)
Доказательство этой теоремы Шеннона о пропускной способности непрерывного канала весьма громоздко и мы не станем его рассматривать. Остановимся на анализе самой формулы. Итак пропускная способность непрерывного канала с помехами:

- пропорциональна ширине полосы частот канала fm;

- возрастает с увеличением отношения полезный сигнал/помеха (в этом случае будет уверенно распознаваться на фоне помех);

- не равна нулю даже при Pc << Pп (то-есть, передачу информации принципиально можно вести сигналами более слабыми, чем помехи).

Мы вернемся к использованию соотношения Шеннона 4.13 при рассмотрении вопросов передачи сигналов.


Контрольные вопросы.
1. Поясните, как логически можно получить формулу (4.2).

2. Обоснуйте условие (4.6) полного использования пропускной способности канала без помех.

3. Сформулируйте теорему Шеннона для канала без помех.

4. Как отличается трактовка величины Hz для случаев "посимвольного" и "цепочечного" эффективного кодирования?

5. Поясните смысл формулы (4.8)

6. При каких допущениях и каким образом получена формула (4.10)

7. Почему при вероятности ошибки p0 =1 пропускная способность канала имеет ту же величину, что и при p0 = 0? Как практически можно использовать такой канал?

8. В чем суть теоремы Шеннона для канала с помехами?



9. Как практически можно избежать потери информации в канале с помехами?