- •Д. В. Ломакин прикладная теория информации
- •Предисловие
- •Модели, используемые в статистической теории информации
- •Установление количественной меры информации комбинаторное определение количества информации
- •Определение количества информации по к. Шеннону
- •Прологарифмировав последнее равенство, получим
- •Свойства энтропии Энтропия
- •При равномерном распределении энтропия
- •Ценность информации
- •Собственная информация и энтропия
- •Взаимная информация
- •Условную энтропию можно представить в виде
- •3. Дискретные источники сообщений и их описание эргодические источники
- •Производительность дискретного источника сообщений
- •Марковские источники сообщений
- •4. Кодирование сообщений при передаче по каналу без помех возможность оптимального (эффективного) кодирования
- •Префиксные коды
- •Неравенство крафта
- •Предельные возможности оптимального кодирования
- •Пропускная способность дискретного канала связи
- •Вычисление пропускной способности симметричных каналов
- •Сумма не зависит от номера столбцаj и в общем
Пропускная способность дискретного канала связи
Для общего описания канала связи и построения теории информации используется одна и та же модель. Канал называется д и с к р е т н ы м (непрерывным), если множества Х и Y дискретны (непрерывны), и п о л у н е п р е р ы в н ы м , если одно из множеств дискретно, а другое непрерывно. Ниже рассматриваются только дискретные каналы.
Канал полностью описывается условными вероятностями того, что k-ì принятым символом будет
jk-й символ множества Y (jk=1,my).
Указанную вероятность можно рассматривать как функцию , вид которой отражает состояние канала, в частности, характер взаимодействия помехи и сигнала. Если
то соответствующий канал называется каналом без памяти. Если вероятность не зависит от k (от времени), то соответствующий канал называется стационарным. Ограничимся рассмотрением только стационарных каналов без памяти. Определим скорость передачи информации как предел:
где - средняя взаимная информация между переданным и принятым. В случае отсутствия помехH(X/Y)=0, следовательно, R =H(X). Этот предел в случае канала без памяти равен взаимной информации:
R=I(X,Y)=H(X) -H(X|Y)=H(Y) -H(Y|X) .
Скорость передачи информации R полностью определяется
вероятностями . Поэтому изменять величину R мы можем только за счет изменения вида распределения , поскольку — характеристика неуправляемого канала. Определим пропускную способность канала С как максимальную по скорость передачи информации:
.
В случае отсутствия помех
.
Вычисление пропускной способности симметричных каналов
Существует класс каналов, для которых пропускная способность С легко вычисляется. Канал полностью описывается так называемой стохастической матрицей
в которой сумма всех элементов, образующих строку, рвана единице.
Канал называется с и м м е т р и ч н ы м п о в х о д у , если строки матрицы различаются только порядком расстановки некоторого множества чисел
Для симметричных по входу каналов частная условная энтропия
Она не зависит от номера передаваемой буквы и может быть вычислена по любой строке матрицы. Поэтому условная энтропия
Канал называется с и м м е т р и ч н ы м п о в ы х о д у, если столбцы матрицы различаются только порядком расстановки некоторого множества чисел .
Если распределение источника равномерное
то распределение на выходе симметричного по выходу канала также будет равномерным. При этом энтропииН(Х) и H(Y) достигают своего максимального значения. В этом легко убедиться, если доказать, что вероятность не зависит отуj. Представим вероятность в виде
Поскольку
Сумма не зависит от номера столбцаj и в общем
случае не равна единице. Поэтому вероятность также
не зависит от j и равна . При этом
Канал называется симметричным, если он симметричен по входу и выходу. Для симметричного канала H(Y|X) не зависит от распределения источника сообщений, поэтому пропускная способность
В качестве примера вычислим пропускную способность симметричного канала, который описывается матрицей
где m=mX =mY . В этом случае
C 1
0,8
0,6
0,4
0,2
0 0,2 0,4 0,6 0,8 1 Pe
Рис. 3. Зависимость пропускной
способности ДСК от вероятности ошибки pe
Вероятность 1-pe равна вероятности правильного приема символа. Вероятность ошибки pe равна вероятности приема yj c при условии, что было передано xi . Тогда
.
Широкое распространение получил двоичный симметрич-ный канал (ДСК) (m=2) , для которого пропускная способность (Рис. 3)
Максимальная скорость передачи информации, равная единице, получается при ре=0 и при ре=1. В этом случае множества Х и Y находятся во взаимно однозначном соответствии, и по принятому уj (j=1, 2) всегда можно определить с вероятностью, равной единице, переданную букву. К сожалению, это возможно только тогда, когда априори (до приема) известно значение вероятности ре (нуль или единица).