Теория вероятности. Вентцель Е.С (4-е издание) (1082431), страница 88
Текст из файла (страница 88)
Требуется найти пропускную способность канала. Определим сначала максимальную информацию на один символ. которую может передавать канал. Пусть источник производит символы 0 и 1 с всроито -нт р и 1 — р. Тогда энтропия источника будет Н (Х) = — р 1оп р — (1 — р) 1оп (1 — р). Определим информацию ю~г.+х на один элементарный символ! Л) 6' х=н(У) — Н(У~ Х). Чтобы найти полную условную энтропию Н(!')Х), найдем сначала частные условные энтропии: Н(г'1х,) (энтропию системы У при условии, что система Х приняла состояние х,) и Н('г~!х ) 5!2 основные понятия теогнн ннеоямлцнн !гл, ~а (энтропию системы У при условии, что система Х приняла состояние х,).
Вычислим Н(У(х,); для этого предположим, что передан элементарный символ О. Найдем условные вероятности того, что при этом система У находится в состоянии у,=О и в состоянии у,=1. Первая из них равна вероятности того, что сигнал не перепутан: Р(у,)х,)= 1 — р; вторая — вероятности того, что сигнал перепутан: ! (уз! х~) =р Условная энтропия Н(У)х,) будет: Н(У~ х,) = — ~~'„, Р(у, !х,)!опР(у,~ х,) = 1=1 = — (1 — р) !ои(1 — р) — р !пир.
Найдем теперь условную энтропию системы У при условии, что Х х, (передан сигнал единица): Р(у, ~ ха) = р.; Р(уа) ха) = 1 — р, откуда И (УЧ ха) р !Ок р (1 р) 1ок (1 р) Таким образом, Н(У ~ х,) = Н(У~х,) = — р!оду, — (1 — р) !о8(1 — р). (18,9.4) Полная условная энтропия Н(У! Х) получится, если осреднить условные энтропии Н(У~х,) и Н(У!хт) с учетом вероятностей р и 1 — р значений хн хм Так как частные условные энтропии равны, то Н (У ! Л) — — р !оя р — (1 — р) !ои (! — р).
Мы получили следующий вывод: условная энтропия Н(У~Х) гопгпв пе эпгпгпт от того. с ппппмп впрпяпппо.тл.ип р, 1 — р всглрвчаются символы О; 1 в передаваемом сооби(епии, а эависигп только от вероятности ошибки р. Вычислим полную информацию, передаваемую одним символом: Ф х=-Н(У) — Н(У~Х)= = ( — г !пег — (1 — г) !оп(1 — г)]— — ( — р !оп р — (1 — р) !оп(! — р)) =— = (4(г)+4(! — г)! — ! !(р)+4(1 — р)), пвопдлчл инеоомлцнн с нсклжининми 813 |з.в1 где г — вероятность того, что на ныходе появится символ О.
Оче- видно, при заданных свойствах канала информация на один символ 1г. х 111 достигает максимума, когда т)(г)+т)(1 — г) максимально. Мы знаем, что такая функция достигает максимума при г= 1/2, т. е. когда на приемнике оба сигнала равновероьтны. Легко убедиться, что это достигается, когда источник передает оба символа с одинаковой вероятностью р =!/2. При том же значении р = 1/2 достигает максимума и информации на один символ. Максимальное значение равно !ггц х=)У(У) — [0(р)+)(1 — р)[=! — [0(р)+ц(! — Р)[ Следовательно, в нашем случае та х 7 г~ ь — — 1 — [ ц (р) + л (1 — р)!, и пропускная способность канала связи будет равна С=а [! — [л(р)+)(1 — р)Ц.
(18.9.5) Заметим, что ц(р) + ц (1 — р) есть не что иное, как энтропия системы, имеющей два возможных состоннин с вероятностями р н 1 — р. Она характеризует потерю информации на один с и и в о л, связанную с наличием помех в канале. П р и м е р. 1. Определить пропускную способность канала связи, способ- ного вередавать 100 символов 0 илн 1 в единицу времени, причем каждый нз символов искажается (заменяетсв противоположным) с вероятностью р = 0,01. Решение.
По таблице 7 приложения находим х (р) = 0,08бб, ч П вЂ” и) =0,0Ьи, Ч(,)+,(1 Р) =0,0808. На один символ теряетсн информация 0,0808 (дв. ел). Пропускная способ- ность канала равна С = 100 (1 — 0,0808) = 91,92 ж 92 двоичные единицы в единицу времени. С помощью аналогичных расчетов может быть определена пропускиаа способность канала и в более сложных случаях: когда число элементарных символов более двух и когда пскв>кенпп отдельных символов зависимы. Зная пропускную способность канала, можно определить верхний предел скорости передачи информации по каналу с помехами. Сформулируем (без доказательства) относяшуюсв к этому случаю вторую теорему Шеннона.
2-н теорема Шеннона Пусть имеется источник информации Х, энтропия которого в единицу времени равна Й(Х), и канал с пропускной способностью С. Тогда если Й(Х) ) С, 33 е. с. вьнтчель 514 основныи понятия тнорнн ннеооыдцнн (гп. га то при любом кодировании лередача сообщений без задержек и искажений. невозможна, Если же Й(Х) <С, то всегда можно достаточно длинное сообщение закодировать так, чтобы оно было передано без задержек и искажений с вероятностью, сколь угодно близкой к единице, Пример 2. Имеются источник информации с энтропией в единицу времени тт'(Х) =100 (дв. ед.) и два канала связи; кажлый из иих может передавать в единицу времени 70 двоичных знаков (О или 1); каждый двоич- ный знак заменяется противоположным с вероятностью и=0,1. Требуется выяснить: достаточна ли пропускная способность этик каналов для передачи информации, поставляемой источником? Р е ш е н и е.
Определяем потерю информации на один символ; и(р)+ч(1 — р) =0,332+0,137 0,469 (де. ед.). Максимальное количество информации, передаваемое по одному каналу в единицу времени; С = 70 (1 — 0,469) = 37,2. Максимальное количество информации, которое может быть передано по двум каналам в единицу времени: 37,2. 2 74,4 (да, ед.), чего недостаточно для обеспечения передачи информации от источника.
ГЛАВА 19 ЭЛЕМЕНТЫ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ 1ВЛ. Предмет теории массового обслуживания За последние десятилетия в самых разных областях практики возникла необходимость в решении своеобразных вероятностных задач. свяаанных с работой так называемых сисшем массового обслуживания.
Примерами таких систем могут служить: телефонные станции, ремонтные мастерские, билетные кассы, справочные бюро, парикмахерские и т. п, Каждая такая система состоит из какого-то числа обслуживающих единиц, которые мы будем называть «каналами» обслуживания. В качестве каналов могут фигурировать. "линии связи; лица, выполняющие те ли иные операции; различные приборы и т. п. Системы массового обслуживания могут быть как одно-,так и многоканальными.
Работа любой системы массового обслуживания состоит в выполнении поступающего на нее потока требований или заявок. Заявки поступают одна за другой в некоторые, вообще говоря, случайные, моменты времени. Обслуживание поступившей заявки продолжается какое-то время, после чего канал освобождается и снова готов для приема следующей заявки. Каждая система массового обслуживания, в аависимости от числа каналов и их производительности, обладает какой-то пропускной способностью, позволяющей ей более или менее успешно справляться с потоком заявок.
Предмет теории массового обслуживания †установлен зависимости между характером потока заявок. производительностью отдельного канала, числом каналов и успешностью (эффективностью) обслуживания. В качестве характеристик эффективности обслуживания — в зависимости от условиИ задачи к целей исследования — могут применяться различные величины и функции, например: средний процент заявок, получающих откаа и покидающих систему необслуженнымн; среднее время «простоя» отдельных каналов и системы в целом; среднее время ожидания в очереди; вероятность того, что поступившая заявка немедленно будет принята к обслуживанию; закон распределения длины очереди и т. д. Каждая из этих характеристик описывает, с той или другой стороны, степень приспособленности системы к выполнению потока заявок, иными словами — ее пропускную способность.
616 эляминты теояии млссового овслгживлния [гл ~а Под «пропускной способностью» в узком смысле слова обычно понимают среднее число заявок, которое система может обслужить в единицу времени. Наряду с нею часто рассматривают относительную пропускную способность †средн отношение числа обслуженных заявок к числу поданных. Пропускная способность (как абсолютная, так и относительная) в общем случае зависит не только от параметров системы, но и от характера потока заявок, Если бы заявки поступали регулярно, через точно определенные промежутки времени, и обслуживание каждой заявки тоже имело строго определенную длительность, расчет пропускной способности системы не представлял бы никакой трудности. На практике обычно моменты поступления заявок случайны; по большей части случайна и длительность обслуживания заявки.
В связи с этим процесс работы системы протекает нерегулярнш в потоке заявок образуются местные сгущения и разрежения. Сгущения могут привести либо к отказам в обслуживании. либо к образованию очередей. Разрежения могут привести к непроизводительным простоям отдельных каналов или системы в целом. На этн случайности, связанные с неоднородностью потока заявок, накладываются еще случайности, связанные с задержками обслуживания отдельных заявок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
