50_000337

Последствия от наличия избыточности неоднозначны. С одной стороны, избыточные сообщения требуют дополнительных затрат при передаче - например, увеличения времени передачи или расширения полосы частот. С другой стороны, при адекватном учете избыточности (или введении искусственной избыточности) становится возможно применять алгоритмы обнаружения и исправления ошибок, что обеспечивает повышение помехоустойчивости передачи. Так, высокая избыточность большинства естественных языков обеспечивает достаточно надежное общение людей даже при наличии дефектов речи и неидеальной слышимости.

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

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

Решение. Максимальная энтропия текста на русском языке (с учетом пренебрежения при передаче различий в буквах е и ё, ъ и ь) равна 5 бит (см. Дмитриев, пример 3.3.). Там же определена энтропия с учетом неравномерного распределения вероятностей появления отдельных букв (4.42 бит). Имея сведения о переходных вероятностях и упрощенно представляя текст в виде простой цепи Маркова, можно определить, что энтропия уменьшается до 3.52 бит. Учет всех ограничений в языке, включая связи между словами, позволяет по различным экспертным оценкам ограничить минимальное значение энтропии значением 1.5 бит. Таким образом, избыточность русского языка составляет:

Таким образом, полное устранение избыточности при передаче текстов на русском языке позволит повысить эффективность использования каналов связи более чем в три раза.

13Рассматриваются в теме 3 приведенного курса лекций.

14Рассматривается в теме 4 приведенного курса лекций.

71

5.2.3Производительность источника сообщений

Рассмотрим последнюю интересующую нас в рамках данной лекции характеристику источников сообщений. Итак:

Производительностью источника сообщений называется ко-

личество информации, вырабатываемое источником в единицу времени15.

Поскольку возможное воздействие помех на источник сообщений принято учитывать эквивалентным изменением характеристик модели канала связи, то производительность источника сообщений равна энтропии источника, приходящейся на единицу времени и измеряется в бит-с.

Длительность выдачи знаков источником в каждом из состояний в общем случае может быть различной. Обозначим длительность выдачи знака zl, формируемого источником в состоянии Sq через qzl. В этом случае средняя длительность выдачи источником одного знака равна:

RL

Производительность источника I(Z) таким образом возможно выразить формулой:

Как следует из 5.12, повышение производительности источника возможно не только за счет увеличения энтропии, но и за счет снижения средней длительности формирования знака. Длительность знаков желательно выбирать обратно пропорциональными вероятностям их появления.

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

15Данную характеристику называют также скоростью сообщений или интенсивностью потока входной информации.

72

Лекция 6

Дискретные каналы связи

6.1Дискретные каналы связи

6.1.1Модели дискретных каналов связи

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

Вкаждом своем состоянии канал характеризуется матрицей услов-

ных вероятностей P (UijZj) того, что переданный символ Ui будет воспринят на выходе кака символ Zj. Таким образом, нестационарный канал связи имеет зависимость матрицы P от времени, но при этом может быть представлен рядом стационарных каналов, соответствующим различным временным интервалам.

Информационная модель канала без помех является частным случаем с определением однозначных соответствий между множествами символов на входе и выходе канала (матрица условных вероятностей заполняется единицами). В общем случае M-ичным каналом (с помехами, либо без помех) называется такой канал связи, в котором размеры ансамблей U и Z совпадают.

Важной частной моделью, широко использующейся при анализе и построении систем и сетей телекоммуникаций является стационарный дискретный двоичный канал без памяти. Данная модель однозначно определяется четырьмя условными вероятностями: p(0j0); p(1j0); p(0j1); p(1j1).

73

Рис. 6.1: Дискретный двоичный канал без памяти

На указанном рис. 6.1 p(0j0) и p(1j1) - вероятности неискаженной передачи символов, а p(0j1) и p(1j0) - вероятности искажения (трансформации) символов 0 и 1 соответственно.

Если вероятности искажения символов приблизительно равны:

p(0j1) p(1j0) = q;

то такой канал называют двоичным симметричным каналом, иначе -

несимметричным.

Достаточно интересной также является мат. модель т.н. двоичного дискретного канала со стиранием. На выходе такого канала возможен символ неопределенности состояния (когда символ с равным основанием может быть отнесен к нулю, либо единице) - символ стирания, обозначающийся S:

Рис. 6.2: Дискретный двоичный канал со стиранием

При декодировании символы стирания существенно проще исправить, чем ошибочно определенные.

6.2 Теоремы Шеннона для дискретных каналов связи

6.2.1Теорема Шеннона для дискретного канала без помех

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

74

Пропускной способностью канала связи называется величина

C, характеризующая максимально возможную скорость передачи информации по каналу с данными техническими характеристиками.

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

Для случая канала без помех имеет место взаимно-однозначного соответствия между множествами символов U и Z на входе и выходе канала, соответственно. Таким образом, для канала без помех:

I(U; Z) = I(Z; U) = H(U):

При этом максимум возможного количества информации на символ равен log M, где M - объем алфавита символов; таким образом, пропускная способность дискретного канала без помех определяется следующим образом:

Исходя из свойства асимптотической сходимости становится возможно доказать теорему Шеннона для дискретного канала без помех:

Теорема 1 (Теорема Шеннона для дискретного канала без помех). Если пропускная способность дискретного канала без помех превышает производительность источника сообщений, т.е. удовлетворяется условие:

то существует способ кодирования и декодирования сообщений источника с энтропией H(A), обеспечивающий сколь угодно высокую однозначного и верного декодирования. В противном случае такого способа не существует.

Доказательство.Для доказательства теоремы пронумеруем все типичные последовательности достаточно большой временной длины T = N

vsource

цифровыми комбинациями B с основанием M, равным объему алфавиту канала. Таким образом, число различных кодовых комбинаций равно:

75

Число типичных последовательностей длительностью N в соответствии с (5.9)

Ntyp(U) = 2T vsource H(U)

. Условие теоремы Шеннона 6.3 возможно записать в виде vchannel log M = vsourceH(A) + , где - сколь угодно малая величина и, следовательно:

или

N(B) > Ntyp(U) + 1:

Таким образом, при выполнении базового условия теоремы Шеннона число различных комбинаций по крайней мере на единицу больше числа типичных последовательностей источника. Эту избыточную кодовую комбинацию поставим в соответствие всем нетипичным последовательностям, предопределив их недостоверную передачу. Поскольку при T ! 1 и N ! 1, то вероятность появления нетипичной последовательности стремится к нулю, а величина бесконечно мала, то первую часть теоремы возможно считать доказанной.

Докажем теперь вторую часть теоремы - в случае нарушения условия

6.3, когда vchannel log M > vsourceH(U), используя аналогичный подход при доказательстве, получаем неравенство

Ntyp(U) > N(B) + 1:

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

76

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

Кодирование данным способом связано с задержкой передачи сообщения (латентностью передачи) на время:

где время 2T определяется тем, что кодирование может начаться, лишь когда известна уже вся последовательность символов источника длительностью T , а декодирование - когда уже принята кодовая комбинация той же длительности; T0 - время, затрачиваемое на технические операции кодирования, декодирования и на прохождение сигнала по каналу1.

6.2.2Теорема Шеннона для дискретного канала с помехами

При наличии помех соответствие между множествами символов на входе и выходе канала связи перестает быть однозначным. Среднее количество информации I(U; Z), передаваемое по каналу одним символом, определяется в этом случае соотношением:

Если статистические связи между символами отсутствуют, энтропия на выходе канала связи равна:

M

X

При наличии статистической связи энтропию определяют с использованием цепей Маркова. Для простоты рассуждений ограничимся здесь случаем отсутствия корреляции между отдельными символами.

1Необходимо отметить, что в канале без помех источником ненадежности отождествления передаваемых сообщений может быть только операция кодирования, т.к. нарушение соответствия при передаче сообщений по каналу исключено.

77

Итак, если объем алфавита входных символов U равен M, а выходных символов Z - L, то апостериорная энтропия2 входного сообщения U после приема конкретного символа может быть вычислена по следующей формуле:

ML

X X

HZ(U) = p(um; zl) log p(umjzl): (6.10)

m=1 l=1

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

где vsymbol - символьная скорость передачи по каналу связи. Согласно своему определению, пропускная способность канала с помехами является

пределом функции I(U; Z):

C = max vsymbolI(U; Z):

p(U)

Для двоичного симметричного канала с помехами пропускная способность определяется по формуле

где - вероятность ошибочного приема; F = 1= - символьная частота передачи данных ( - длительность канального символа).

C учетом вышеизложенного, реальная степень загрузки канала характеризуется коэффициентом использования канала:

где I(U) - производительность источника сообщений, а C - пропускная способность канала связи.

6.2.3Теорема Шеннона для дискретного канала с помехами

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

2В случае канала без помех значение апостериорной энтропии равно нулю.

78

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

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

Доказательство данной теоремы приводится, например, [Липкин] и может быть детально рассмотрено читателем. Отметим лишь основные следствия данной теоремы:

1 Теорема Шеннона для дискретного канала с помехами под оптимальным понимает кодирование, связанное с увеличием задержки передачи сообщения3 на время latency = 2T + T0.

2 Теорема Шеннона для канала с шумами не указыает конкретного способа кодирования, обеспечивающего достоверную передачу информации, а лишь доказывает принципиальное существование такого кода.

3Чем выше длительность кодированной последовательности (и, соответственно, латентность) и чем меньше коэффициент использования канала, тем больше помехоустойчивость сообщений.

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

3Латентности сообщения.

79

Практика 5 – каналы связи

6.3Каналы связи

6.3.1Взаимная информация, производительность канала связи

1Энтропия дискретного источника сообщений всегда положительна. Дифференциальная энтропия, в свою очередь, может быть отрицательной. Может ли быть отрицательной полная взаимная информация двух непрерывных систем?

2 Лектор произносит в среднем около сорока шестибуквенных слов в минуту. Рассматривая его как источник дискретных сообщений, определить его производительность. Для простоты принять, что все буквы алфавита равновероятны и статистически независимы.

3Двоичный источник с равновероятными элементами имеет производительность 1000 бит-с. При передаче по каналу в среднем один из переданных 100 символов искажается. Определить скорость передачи информации по данному каналу.

4По двоичному симметричному канала связи с помехами передаются

сигналы (x1; x2) c априорными вероятностями p(x1) = 3=4; p(x2) = 1=4. Из-за наличия помех вероятность правильного приема каждого из сигналов (x1; x2) уменьшается до = 7=8. Найти:

1.Среднее количество информации I(x; y);

2.Пропускную способность канала связи C = max I(x; y).

p(x)

5 Имеется источник информации с энтропией в единицу времени H = 100 бит и два канала связи: каждый из них может передавать в единицу времени 70 бит информации, при этом в результате

80