Лекция №5 По дисциплине Теория информации



Скачать 75.93 Kb.
Дата23.07.2013
Размер75.93 Kb.
ТипЛекция
КАФЕДРА

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

ЛЕКЦИЯ № 5



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

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









Тема № 3

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





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


Занятие № 7

Согласование пропускной способности канала передачи информации с потоком информации от источника




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



Цель занятия: дать систематизированные основы научных знаний по согласованию пропускной способности канала передачи информации с потоком информации от источника
Изучаемые вопросы:
1 Шенноновская модель дискретного канала и его пропускная способность.

2 Пропускная способность непрерывного канала.

3 Согласование потока информации от источника и пропускной способности канала
1 Шенноновская модель дискретного канала и его пропускная способность.
Здесь И – источник сообщений, основанных на алфавите Z из n символов {z1…zn}. Средняя информативность источника характеризуется безусловной энтропией Hz (бит/символ), а среднее время выработки источником символа – tz (с/символ).

Кд – кодер, преобразует алфавит источника Z в алфавит канала X, состоящий из m символов {x1…xm}. Средняя информативность символов канала характеризуется энтропией Hx (бит/символ), а время передачи одного символа – tx (с/символ).

Декодер (Дк) раскодирует символ канала для приемника (П).

Поскольку в канале с вероятностью p0 в канале Кн могут возникать ошибки, на его выходе символам xi соответствуют символы yi (в общем случае ). Мы будем рассматривать наиболее распространенный случай двойного симметричного канала (m = 2, p0 = p1/0 = p0/1).
В таком варианте очевидно Hy = Hx, поскольку ошибки не меняют соотношение вероятностей «1» и «0».

Среднее количество информации Ixy, переносимое одним символом канала можно определить по формуле (4.1)

где Hx/y – условная энтропия, характеризующая неопределенность переданного символа xi, если принят yi. Очевидно, что используя разные варианты формулы 4.1, мы как бы рассматриваем канал в разных ракурсах (со стороны источника или приемника), при этом неопределенность, вносимая каналом остается одинаковой (Hx/y = Hy/x).

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

Для двоичного симметричного канала, где max{Hx} = 1, а Hy/x определяется только вероятностью ошибки p0, справедливо


Выясним теперь зависимость между Hx/y и p0*. Пользуясь формулой условной энтропии для случая, когда m = 2 и p1/0 = p0/1 = p0, запишем


Учитывая, что p”0” + p”1” = 1, можно теперь записать (4.3) в виде



Наглядно зависимость C(p0) иллюстрирует рисунок 4.2.

Как видно, максимальное значение пропускной способности канала достигается при p0 = 0 «канал без помех» и при p0 = 1 (очевидно, что если канал передает все символы с ошибками, то последние легко устраняются инвертированием). Минимальное значение C = 0 имеет место при p0 = 0.5.
2 Пропускная способность непрерывного канала.
Непрерывный канал используется для передачи аналоговых сигналов (примером здесь может служить хорошо знакомый нам телефонный канал). Определяя пропускную способность такого канала, будем рассматривать непрерывный сигнал как предел дискретного при уменьшении кванта и дискреты по времени .

Каналы характеризуются конечной шириной полосы пропускания сигналов.

Как мы уже знаем, согласно теореме Найквиста-Котельникова, для представления непрерывного сигнала с шириной спектра (а именно такая ширина будет максимальной в нашем случае) достаточна величина шага.

С учетом сказанного величину пропускной способности непрерывного канала можно записать в виде

Учитывая, что, видно, что при и в отсутствии помех эта величина, а с ней и пропускная способность канала стремится к бесконечности. При наличии помех уменьшением сопровождается не только ростом , но и увеличением (поскольку растет вероятность ошибки распознавания сигнала). В этих условиях пропускная способность канала определяется соотношением мощности полезного сигнала (Px) и помехи (Pe). Здесь мы не станем приводить громоздкий вывод соответствующей формулы. Отметим лишь, что она получена в предположении, что помеха имеет спектр, равномерно распределенный во всей полосе частот канала (т.н. «белый шум»), а сигнал имеет нормальное распределение мощности. В этом случае


Из формулы (5.7) следуют, в частности, несколько примечательных выводов.

Во-первых, увеличение отношения «сигнал/помеха» очевидно позволяет повысить пропускную способность канала. Реально этому может соответствовать увеличение объема алфавита m, когда один сигнал («отсчет») несет несколько бит информации (похоже дело обстоит например, в современных моделях).

Во-вторых, полученную информацию можно передавать по каналу даже в случае, когда (полезный сигнал слабее помехи). Отложим рассмотрение конкретных способов такой передачи, отметив лишь, что подобный подход позволяет эффективно скрывать сам факт передачи сигналов на фоне помех.
3 Согласование потока информации от источника и пропускной способности канала
Поток информации определяется как среднее количество информации, которое источник вырабатывает в единицу времени (бит/с). Зная среднюю длительность выработки одного символа tz и его среднюю информативность Hz, величину потока можно рассчитать как


Очевидно, что величину потока следует согласовывать с пропускной способностью канала C таким образом, чтобы с одной стороны, вся вырабатываемая источником информация успевала передаваться, а с другой – возможности канала использовались бы как можно полнее. Поскольку величина определяется особенностями источника и в этом смысле является заданной, единственным «инструментом» согласования остается величина tz, а значит – кодирование символов источника, которое определяет среднюю длину кода, и вслед за ней величину .

Клод Шеннон доказал следующую важную теорему.

Существует способ кодирования, который обеспечивает выполнение условия



где е – сколь угодно малая величина. При этом не существует способа кодирования, который бы обеспечил .
Шеннон указал способ такого кодирования (получившего название «эффективного» суть которого сводится к следующему: часто встречающиеся символы кодируются более короткими кодовыми цепочками, в то время, как редко встречающиеся более длинными. В результате средняя длина кода сокращается в пределе , что эквивалентно выполнению условия (5.9)
Пример 1 кодирования по Шеннону

Пусть имеется 4 типа символов, составляющих алфавит Z и известны их вероятности (таблица 1). При кодировании символы выстраивают по убыванию вероятностей и делят на группы так, чтобы суммарные вероятности каждой из них были максимально близки. Группам присваивают противоположные значения разрядов кода. Затем процедуру повторяют до тех пор, пока каждая группа не сведется к одному символу.

Таблица1

Zi

Pi

Ki

Группы

Z1

P1=0,5

1

1

Z2

P2=0,25

01

2 1

Z3

P3=0,125

001

2 2 1

Z4

P4=0,125

001

2 2 2


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

Пример 2.

Исходный алфавит включает символы Z1 и Z2 с вероятностями 0,8 и 0,2 (рис.4.4). Согласно процедуре Шеннона, чтобы повысить эффективность кодирования следует ввести новый алфавит, символы которого обозначают сочетанием исходных символов Zi.



На первом шаге новые символы ai соответствуют парам zizj, на втором символы bm отвечает тройкам zizjzl и т.д. Очевидно, что с каждым шагом расширения алфавита мы все больше «дробим» вероятности так, что суммарная вероятность в группах может приближаться к отрицательным степеням двойки (здесь шаг за шагом мы движемся к выполнению условия ). С другой стороны расширение алфавита существенно усложняет код (поэтому на практике такой прием распространения не получил).

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

Похожие:

Лекция №5 По дисциплине Теория информации iconЛекция №1 По дисциплине Теория информации
Цель занятия: дать систематизированные основы научных знаний по структуре дисциплины, предмету, методам, задачам; основным понятиям...
Лекция №5 По дисциплине Теория информации iconТеория информации. Мера количества информации лобач Г. С., Саттаров И. Д
Теория информации – комплексная, в основном математическая теория, включающая в себя описание и оценки методов извлечения, передачи,...
Лекция №5 По дисциплине Теория информации iconЛекция №8 По дисциплине Теория информации Тема №4 Помехоустойчивость и эффективность информационных систем полное наименование темы Занятие №12
Цель занятия: дать систематизированные основы научных знаний по различным методам кодированию данных с помощью кодов с памятью и...
Лекция №5 По дисциплине Теория информации iconЗанятие №3 По дисциплине Теория информации
Цель занятия: Закрепить теоретические знания по определению энтропии объединения информации при различных вероятностях событий
Лекция №5 По дисциплине Теория информации iconЗанятие №2 По дисциплине Теория информации
Цель занятия: Закрепить теоретические знания по определению условной энтропии информации при различных вероятностях событий
Лекция №5 По дисциплине Теория информации iconРабочая программа по дисциплине "Теория информации" для студентов специальности 090106
Учебный план набора 2006 года и последующих лет, квалификация специалист по защите информации
Лекция №5 По дисциплине Теория информации iconЗанятие №1. По дисциплине Теория информации
Цель занятия: Закрепить теоретические знания по определению количества информации при равновероятных событиях, а также при различных...
Лекция №5 По дисциплине Теория информации iconЛекция 07. Теория информации 1 Ключевые слова настоящей лекции понятия информации, материальный и идеалистичный аспекты, информация с физической, синтаксической, семантической и прагматической точек зрения, код, алфавит, формулы Хартли и Шеннона
Хартли и Шеннона, бит, вероятность и неопределенность в структуре сигнала, понятия энтропии и информации в кодировании
Лекция №5 По дисциплине Теория информации iconЛекция №15 (Теорема 21), [6] Метод покоординатного спуска. Лекция №16 (Теорема 24), [2, 3]
Теория двойственности нелинейного программирования. Лекция №4 (Теорема 10, леммы 5, 6, следствия 1 и 2), Лекция №5 (следствие 3),...
Лекция №5 По дисциплине Теория информации iconУчебная программа Дисциплины б5 «Теория информации и кодирования»
Дисциплины «Теория информации и кодирования» направлено на ознакомление студентов с основными количественными характеристиками источников...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org