Пропускная способность дискретного (цифрового) канала

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«РЯЗАНСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ

 

 

 

КОНТРОЛЬНАЯ РАБОТА ПО ДИСЦИПЛИНЕ:

«Прикладная теория информации»

 

 

 

 

 

 

Выполнила:

ст. гр. 2033 Правдина Т. Н.

Проверил:

проф. Нечаев Геннадий Иванович

 

 

 

 

 

Рязань 2015

Содержание

 

 

 

Введение

 

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

К теории информации, в ее узкой классической постановке, относят результаты решения ряда фундаментальных теоретических вопросов. Это в первую очередь: анализ вопросов оценки «количества информации»; анализ информационных характеристик источников сообщений и каналов связи и обоснование принципиальной возможности кодирования и декодирования сообщений, обеспечивающих предельно допустимую скорость передачи сообщений по каналу связи, как при отсутствии, так и при наличии помех.

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

 

1. Пропускная способность дискретного (цифрового) канала

 

Структурная схема цифрового информационного канала показана на рисунке 1.

 

      

 

 

 

 

 

 

 

 

Рисунок 1

 

На вход такого канала обычно поступают дискретные соотношения х, например, в виде текста. Последние с помощью кодирующего устройства преобразуются в кодированные сигналы у. Как известно, для кодирования используется некоторый алфавит элементарных сигналов (символов) – у1, у2,…, уm, а существо кодирования сводится к представлению отдельных сообщений xi или последовательностей сообщений некоторыми комбинациями символов используемого алфавита. Декодирующее устройство преобразует кодированные сигналы z в сообщения w в форме, наиболее приемлемой для получателя, которым может быть не только человек, но и различные технические устройства (принтер, монитор, ПЭВМ и др.). В современных информационно-вычислительных комплексах исходные сообщения х могут быть и в непрерывной форме, но с помощью кодирующих устройств последние преобразуют в кодированные сигналы.

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

 

 

 

2. Пропускная способность дискретных (цифровых) каналов при отсутствии шумов

 

При отсутствии шумов можно считать, что в информационном канале z = y, а w = x, следовательно, для сообщений zT = yT, wT = xT, передаваемых за время Т, количество информации, поступающей к получателю от источника, составит

 

где – энтропия источника сообщений.

По аналогии для канала связи, представляющего часть информационного канала, будем иметь

.

Если последовательность XТ состоит из m сообщений и средняя длительность сигнала, обеспечивающего передачу одного сообщения составляет tс, то можно определить скорость передачи информации как

 

где Н(X) – энтропия источника n сообщений:

 

В дальнейшем основание 2 логарифма для простоты будет опущено.

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

Пропускная способность информационного канала C определяется максимальным значением скорости передачи:

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

     (1.3)

Обычно Cс > C.

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

Дискретный канал, в котором передаваемые сообщения представлены двоичным кодом, называется двоичным каналом. Если код имеет m символов (разрядов), то очевидно, что всего можно закодировать n = 2m сообщений, а длительность одного сообщения составит T = mt, где t - длительность символа кода с учетом того, что все символы обычно имеют одинаковую длительность. Двоичные коды, состоящие из одинакового числа символов m, называются равномерными. Пропускная способность рассматриваемого канала с учетом формул (1.1), (1.2) и (1.3) составит

   (1.4)

Выражение (1.4) принимает максимальное значение, когда энтропия ансамбля событий (сообщений) H(YT) будет наибольшей. Из свойств энтропии следует, что H(YT) будет максимальна, если сообщения равновероятны, это максимальное значение может быть определено мерой Хартли и будет равно log n = log2m = m [2].

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

Рассмотрим простой пример.

Пример 1. Пусть источник сообщений вырабатывает четыре сообщения  X1, X2, X3, X4, (n = 4). Все сообщения имеют одинаковые вероятности: P(Xi) = 1/n = 0,25. Для их кодирования используется двоичный равномерный код, число символов в котором достаточно выбрать m = 2. Исходные сообщения х1, х2, х3, х4 в этом примере будут представлены следующими кодами: 00, 01, 10, 11.

Скорость передачи информации будет определяться по формуле (1.2), в которой энтропия источника равновероятных сообщений будет максимальной:

а длительность каждого из четырех сообщений будет определяться длительностями соответствующих кодовых комбинаций и составит tс = 2t. Для примера 1 по формуле (1.2) находим

3. Таким образом, в этом примере, как и следовало ожидать, скорость передачи информации оказалась равной пропускной способности канала:          = Cc = 1/t. 
   Расчётная часть

 

Источник сообщений вырабатывает четыре сообщения  X1, X2, X3, X4, (n = 4), со следующими вероятностями: P(X1) =0,125; P(X2) =0,49; P(X3) =0,25; P(X4)=0,135. Для их кодирования используется двоичный равномерный код. Длительность символа кода 0,5*10-3.

Решение:

Определим скорость передачи информации. Для этого сначала вычислим значение энтропии Н(X) (среднее количество информации):

Формула для вычисления: 

.

При длительности сообщений Скорость передачи информации составит:

 

Посчитаем пропускную способность двоичного канала:

 

Так как скорость передачи оказалась меньше, т.е. Cc > I (2000>1699) показывает, что канал не является эффективным и необходимо менять способ кодирования источника сообщений. Кодирование, при котором достигается наилучшее использование пропускной способности канала, называется эффективным. К эффективным относится, в частности, код Шеннона - Фано, пригодный для кодирования статистически независимых сообщений. Используем этот код для достижения максимальной скорости передачи информации.

Записывают сообщения в порядке убывания их вероятностей. Проводят первое деление всех сообщений на две подгруппы I и II так, чтобы сумма вероятностей сообщений в подгруппах I и II была бы по возможности одинаковой.

Таблица 1

Сообщение Xi	Вероятность P(Xi)	Номер деления на подгруппы			Символ кода			Длительность кодовой комбинации,  ti
					Позиции
		1	2	3	1	2	3
Х2	0,49				0			1t
Х3	0,25				1	0		2t
Х1	0,125				1	1	0	3t
Х4	0,135				1	1	1	3t

 

При первом делении получились подгруппы: I – 0,49; II – 0,25+0,125+0,125=0,51. Во втором делении: I – 0,25; II – 0,125+0,135=0,26. В заключительном делении получились подгруппы: I – 0,135; II – 0,125.

Номер подгруппы, в которую попадает данное сообщение при каждом делении, определяет символ на соответствующей позиции кода этого сообщения. В рассматриваемой таблице принадлежность к подгруппе I обозначается символом 0, а к подгруппе II – символом 1.

Анализируя неравномерный код Шеннона - Фано, можно убедиться в том, что наиболее вероятному сообщению соответствует самая короткая кодовая комбинация, наименее вероятному – длинная. Этим можно объяснить увеличение скорости передачи информации при использовании данного кода.

Для наглядности в таблице 2 для сообщений х1, х2, х3, х4 приведены неравномерный код Шеннона - Фано и равномерный, используемый ранее в примере 1.

 

 

 

Таблица 2

Сообщение xi	Код Шеннона - Фано	Равномерный код
X2	0	00
X3	10	01
X1	110	10
x4	111	11

 

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

Для вычисления скорости передачи информации при использовании кода Шеннона - Фано вычислим для начала длительность сообщения:

 с.

Находим скорость передачи информации:

 

 

 

Таким образом, код Шеннона - Фано позволил согласовать статистические характеристики источника сообщений с каналом связи, поскольку скорость передачи информации оказалась ближе к пропускной способности канала: (как минимум,  > , которые получились бы при длительности сообщений ). Это можно объяснить тем, что при использовании эффективного кода Шеннона - Фано сигнал каждого сообщения в среднем состоит из 1,77 символов, а при использовании равномерного кода – из 2-х.

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