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

 

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

в которой сумма всех элементов, образующих строку, равна единице.

 

В качестве примера вычислим пропускную способность симметричного канала, который описывается матрицей

где m =m_X=m_у.

 

В этом случае

Рис. 3. Зависимость пропускной способности ДСК от вероятности ошибки p_e

Вероятность 1- р_е равна вероятности правильного приема символа. Вероятность ошибки р_е равна вероятности приема y_j, j i при условии, что было передано х_i. Тогда .

Широкое распространение получил двоичный симметричный канал (ДСК) (m = 2 ), для которого пропускная способность (рис. 3) .

Максимальная скорость передачи информации, равная единице, получается при р_е =0и при р_е =1. В этом случае множества X и У находятся во взаимно однозначном соответствии, и по принятому у_j (j =1, 2) всегда можно определить с вероятностью, равной единице, переданную букву. К сожалению, это возможно только тогда, когда априори (до приема) известно значение вероятности р_е (нуль или единица).

Билет 2.
а) Понятие сообщения и сигнала. Модели сигналов
б) Определение канала со стиранием и вычисление его пропускной способности

а) Понятие сообщения и сигнала. Модели сигналов

Сообщение — это то, что можно сообщить, а сообщить можно только состояние системы. Следовательно, сообщение — это сообщаемое (передаваемое) состояние системы, которое сообщается в той или иной форме.

Сигнал — это материальный переносчик информации в пространстве и во времени.

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

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

б) Определение канала со стиранием и вычисление его пропускной способности

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

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

 

 

Указанный канал описывается матрицей:

.

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

Для симметричного по входу канала условная энтропия не зависит от вида распределения источника сообщений и полностью определяется параметрами канала и . Согласно (6.2.1)

(5.3.1)

Поэтому пропускная способность канала

(5.3.2)

Вычислим , энтропия определяется через вероятности:

где обозначения и введены для сокращения записи. Из последнего равенства следует, что безусловная вероятность равна условной вероятности .

Принимая во внимание, что , имеем: Отсюда следует, что зависит от (от распределения источника) только через .

Значение , при котором достигает своего максимального значения, определяется из уравнения ,

которое для данного случая имеет вид: .

 

Последнее уравнение распадается на два уравнения:

Если параметры канала и удовлетворяют первому уравнению, то есть =0.5 (1- ), то пропускная способность канала = 0. При этом независимо от значения вероятности .

Билет 3.
а) Комбинаторные определения кол-ва информации. Единицы измерения
б) Теоремы Шеннона о помехоустойчивом кодировании

Билет 4.
а) Определение типичных последовательностей и вычисление их кол-ва
б) Принципы построения корректирующих кодов. Связь корректирующей способности кода с кодовым расстоянием

Билет 5.
а) Связь между ценностью информации и энтропией
б) Принципы построения линейных кодов. Декодирование по синдрому

 

а) Связь между ценностью информации и энтропией:

 

Ценность информации

 

- Ценной информацией считается та информация, которая способ­ствует достижению поставленной цели.

 

Один из способов измерения ценности информации, сформулированный в рамках статистической теории информации, был предложен А.А.Харкевичем. Ценность информации может быть выражена через приращение вероятности достижения цели. Если значение априорной вероятности достижения цели обозначить через р₁, а апостериорной — через p₂, то ценность полученной информации можно определить как

log .

В системах передачи информации цель сводится к правильной передаче сообщений независимо от их конкретного содержания и формулируется относительно каждого символа множества X. Пусть целью является принятие решения в пользу x_i. Тогда относительно этой цели ценность сведений,содержащихся в принятом y_j равна log , где P(x_i) — априорная вероятность передачи х_i; p(x_i|y_j) — вероятность того, что было передано x_i после принятия y_j. При такой формулировке цели ценность информации совпадает с обычным количеством информации, которое определено выше.

Таким образом, количество информации, которое у_i несет об x_i, равно

.

Умножая числитель и знаменатель под логарифмом на р{у_j) и учитывая равенства

p(x_i|y_j)p(y_j)= p(x_i, y_j)= p(y_j |x_i)р(х_i),

получим

(3)

 

Отсюда следует, что y_j несет об такое же количество информации, какое х_i несет об y_j (свойство симметрии). Поэтому I(х_i, y_j) называется взаимным количеством информации между i-м символом множества X и j-м символом множества У. Взаимное количество информации I(х_i, y_j), может быть положительным , отрицательным и равным нулю . Отрицательная информация называется дезинформацией.