Пропускная способность бинарного, симметричного канала. Двоичный канал

Двоичный симметричный канал (сокращенно ДСК) определяется диаграммой вероятностей перехода, изображенной на рис. 1. На вход канала поступают двоичные сигналы, например 0 и 1. Для каждого из этих входных сигналов имеется вероятность того, что этот сигнал получен правильно, и вероятность того, что он получен неправильно.

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

Злой шутник, который вводит ошибки в передачу, очень простодушен: у него нет памяти и он "перевирает" символы случайно и независимо друг от друга. Его действия разрушительны, но в нем нет сознательной зловредности и деятельность его устойчива, по крайней мере, в статистическом смысле.

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

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

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

Рис. 2. Передача информации по двоичному симметричному каналу.

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

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

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

Существует, по крайней мере, одно простое и очевидное решение этой задачи: каждый символ последовательности х повторить раз. Например, информационной последовательности

при будет соответствовать передаваемая последовательность

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

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

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

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

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

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

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

В век повсеместного Интернета, жителям крупных городов, его отсутствие кажется недоразумением, но какие варианты имеются у жителей частных домов и в удаленных от больших населенных пунктов местах? Большинству провайдеров выгоден охват домовыми сетями лишь многоквартирных домов. Организовать интернет-канал жителям «частного сектора» гораздо сложнее, не говоря уже о удаленных районах, куда провайдеры вряд ли придут в ближайшем будущем. Конечно, есть возможность выхода в Сеть через мобильного оператора, но при современном объеме трафика это очень дорого.

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

Охват спутникового интернета

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

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

Асимметричный - спутниковый интернет на 50%

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

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

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

• спутниковый ресивер для приема
• услуги наземного провайдера (например, мобильного оператора) для отправки запросов и данных.

Варианты организации обратного канала

Способов организовать обратный канал существует множество. Конечно, выбор технологии в первую очередь должен определяться возможностями, доступными в конкретной географической точке. Это может быть не только стационарная или мобильная телефонная линия, но и какой-то из вариантов радиодоступа. Не исключается и локальный провайдер с «домашней сетью» (по каким-то причинам не устраивающей вас в качестве единственного подключения к Глобальной паутине).

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

Особенности асимметричного канала

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

Спутниковый ресивер дешифрует поступающий со спутника сигнал в запрошенные интернет-данные

Выделением нужных данных из этой массы занимается ресивер по MAC-адресу спутникового терминала. Конечно, провайдеры спутникового Интернета прибегают к различным ухищрениям, чтобы пользователи не могли прочитать информацию, предназначенную не для них, - например, каналы шифруются по различным алгоритмам. Но сам факт того, что конфиденциальные данные могут быть доступны, привлекает массу мошенников и просто любопытствующих. Развлечение, состоящее в чтении чужих данных, получило название «рыбалка со спутника».

Оборудование для спутникового интернета

Наиболее популярными для организации спутникового Интернета на сегодняшний день являются стандарты DVB-S и DVB-S2 (второй - это усовершенствованный вариант первого). Для подключения к Сети посредством спутника по распространенной асимметричной схеме вам потребуется:

• спутниковая «тарелка» рекомендованного диаметра
• конвертер сигнала
• ресивер (терминал спутникового Интернета)
• необходимые кабели
• контракт со спутниковым оператором.

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

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

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

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

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

Внимание! Не стоит сначала покупать оборудование, а затем подыскивать провайдера услуг спутникового Интернета. Если «тарелки» более или менее универсальны, то терминалы для доступа, предлагаемые различными операторами, очень часто оказываются несовместимыми. Поставщик интернет-услуг, как правило, может снабдить вас и оборудованием, и программным обеспечением, в котором уже заданы его собственные настройки (кодирование, прокси-серверы и т. п.).

Двусторонний канал спутниковой связи

Симметричный канал

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

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

Дорог ли спутниковый интернет?

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

С несимметричным доступом ситуация обстоит лучше: стоимость приемного оборудования - около 5000-7000 рублей. Ежемесячные расходы на трафик или абонентская плата в среднем составляют от 500 рублей за соединения без нижнего порога гарантированной скорости (CIR) и от 2000 рублей - с таким порогом.

Нужен ли Вам спутниковый интернет?

Спутниковый Интернет может быть единственным шансом подключиться к Интернету там, где нет стабильной сотовой или кабельной телефонной связи. И если цена вопроса вас не останавливает, имеет смысл обратить внимание именно на симметричный способ доступа. Но стоит принимать в расчет и недостатки типов связи спутникового интернета. К сожалению, такой доступ в Интернет, как это ни странно, не так уж надежен. Учитывая, что сигнал до спутника проходит тысячи километров, помехой может стать любое заметное облако. Бороться с этим позволяет использование большей по площади спутниковой антенны, которая обойдется дороже. Еще одним недостатком такого подключения является необходимость помощи специалистов при установке и настройке оборудования, что тоже требует денежных затрат.

7.5. Пропускная способность канала

Величина I (X ; Y ) играет особую роль в теории информации и опи-сывает передачу информации по каналу связи. Из определения (7.9) следует, что I (X ; Y ) зависит как от переходных вероятностей кана-ла, так и от распределения вероятностей символов на входе канала. Для дальнейших рассуждений рассмотрим дискретный канал без памяти с фиксированными переходными вероятностями и зададим-ся вопросом: Какое максимальное количество информации можно передать по данному каналу?

Пропускная способность канала с заданными переходными вероят-ностями равна максимуму передаваемой информации по всем вход-ным распределениям символов источника X

Замечание. Размерность пропускной способности - бит/символ. Если, например, по каналу передается один символ в сек, то можно также говорить о размерности бит/сек.

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

С математической точки зрения, поиск пропускной способности дискретного канала без памяти сводится к поиску распределения ве-роятностей входных символов источника, обеспечивающего максимум информации I (X ; Y ). При этом, на вероятности входных сим-волов накладываются ограничения

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

Теорема 7.5.1. В симметричных дискретных каналах без памяти пропускная способность достигается при равномерном распределе-нии вероятностей входных символов источника Х.

Замечание. В приводится также метод, позволяющий опре-делить, является ли канал симметричным или нет.

7.5.1. Пропускная способность

Двоичный дискретный симметричный канал без памяти (ДСК) определяется с помощью матрицы переходных вероятностей канала (7.2). Единственным параметром, характеризующим ДСК, являет-ся вероятность ошибки ε. Из равномерного распределения входных символов и симметрии переходов канала следует равномерное рас-пределение выходных символов, т.е

Используя (7.9), получаем

Подставляя числовые значения, имеем

Энтропия ДСК определяется через (2.32)

Окончательно получаем пропускную способность ДСК в компактной форме

Интересными являются два граничных случая:

1. Передача информации по бесшумному каналу:

и

2. Канал полностью зашумлен:

И

Важным частным случаем ДСК является двоичный симметричный канал со стираниями (ДСКС) или двоичный канал со стирания-ми (Binary Erasure Channel, ВЕС - англ.). Как и ДСК, двоичный канал со стираниями может служить упрощенной моделью переда-чи информации по каналу с аддитивным белым гауссовским шумом (АБГШ). Правило принятия решения в ДСКС приведено на рис. 7.11. Из рисунка видно, что наряду с решениями о переданном символе «0» или «1», здесь иногда принимается решение о стирании приня-того символа «е»(Erasure-англ.). Стирание происходит в случае, ес-ли продетектированный аналоговый сигнал V попадает в зону, для которой значения условных функций плотности распределения ве-роятностей f (V/0) и f (V /1) оказываются близкими к нулю.

Рис. 7.11. Условные функции плотности распределения ве-роятностей продетектированного сигнала и об-ласти принятия решений.

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

Рис. 7.12.

Обозначим вероятность стирания через q , а вероятность ошибки нестертого символа через р.

Диаграмма переходов для капала с двумя входными и тремя вы-ходными символами приведена на рис. 7.12. Соответствующая мат-рица канала, содержащая переходные вероятности, имеет вид

Найдем пропускную способность канала со стираниями. Так как ка-нал симметричен, пропускная способность достигается при равно-мерном распределении входных символов

Отсюда следует, что вероятности выходных символов равны

Теперь все необходимые вероятности известны. Воспользовавшись (7.9), имеем

Используя свойство симметрии канала, получаем

Как мы видим, пропускная способность канала со стираниями зави-сит только от вероятностей р и q . График С = f (p , q ) представляет собой пространственную трехмерную поверхность, расположенную над плоскостью (p , q ). Здесь мы ограничимся только рассмотрением двух важных частных случаев.

1. При q = 0, мы имеем двоичный симметричный канал, уже рас-смотренный ранее. Подставляя q = 0 в (7.59) мы, как и ожидалось, получаем (7.49).

2. В канале присутствуют только стирания, т.е. при р = 0 ошиб-ки или не присутствуют, или мы ими пренебрегаем. В этом случае

На рис. 7.13 показаны пропускные способности ДСК (7.49) и дво-ичного канала со стираниями (р = 0). Нужно отметить, что при ма-лых вероятностях ошибки, выбором оптимальных областей стираний в ДСКС можно достичь существенно больших пропускных способ-ностей, чем в обычных двоичных каналах.

Замечание. Здесь возникает вопрос о возможности увеличения пропускной способности при приеме со стираниями на практике. В этом месте обнаруживается слабость теории информации. Тео-рия информации зачастую не может предложить конструкцию, реализующую теоретически достижимые границы. Тем не менее, небольшой пример, подробно рассмотренный во второй части этой книги, показывает, что введение стираний может иногда снижать вероятность ошибки. Рассмотрим этот пример на интуитивном уровне. Разобьем поток передаваемой информации на блоки, содер-жащие 7 двоичных символов (7 бит). К каждому блоку добавим один бит («О» или «1») проверки на четность. Закодированные та-ким образом блоки из восьми двоичных символов всегда будут со-держать четное число единиц. Пусть вероятность ошибки в ДСК достаточно мала. Введем зону стирания (рис. 7.11) таким образом, чтобы ошибки, в основном, перешли в стирания. При этом, вероят-ность «нестертой» ошибки будет пренебрежимо мала, а вероят-ность стирания будет оставаться достаточно малой. Мы получим стирающий капал (ДСКС), в котором блоки из восьми двоичных символов в подавляющем большинстве случаев или будут приняты правильно или будут содержать только один стертый двоичный символ. Качество приема существенно улучшится, так как одно стирание в блоке с четным числом единиц всегда может быть ис-правлено.

Рис. 7.13. Пропускная способность двоичного симметрич-ного канала С ДСК с вероятностью ошибки ε и двоичного канала со стираниями С ДСКС с ве-роятностью стирания q и вероятностью ошибки р = 0.

Пример: Двоичный симметричный канал со стираниями.

Рис. 7.14. Двоичный канала со стираниями.

На рис. 7.14 задана переходная диаграмма симметричного канала со стираниями. Определите:

1. Матрицу канала

2. Распределение вероятностей символов источника У, если из-вестно, что символы источника X равномерно распределены, т.е. pa = pi = 1/2;

3. Пропускную способность канала;

4. Диаграмму информационных потоков со всеми энтропиями;

5. Модель канала с матрицей Ру/у.

Решение.

1. С учетом того, что сумма вероятностей в каждой строке мат-рицы равна 1, получим

2. Исходя из равномерного распределения вероятностей символов на входе, согласно (7.52), имеем

3. Так как рассматриваемый канал симметричен, пропускная спо-собность достигается при равномерном распределении входных сим-волов. Из (7.54) с учетом (7.56) имеем

4. Энтропия дискретного двоичного источника, без памяти X с равномерным распределением вероятностей символов равна

Энтропия источника Y р авна

Так как в симметричном канале с равномерным распределени-ем входных символов I (X ; Y ) совпадает с пропускной способностью С из (7,58), совместную энтропию и две условные энтропии мож-но подсчитать, используя таблицу 7.3. Диаграмма информационных потоков изображена на рис. 7.15.

Рис. 7.15. Диаграмма информационных потоков двоичного симметричного канала со стираниями.

5. Пересчет матрицы переходных вероятностей канала в

матрицупредоставляем сделать читателю в качестве самостоятельного упражнения. Диаграмма канала с входным источником Y и выходным X приведена на рис. 7.16 для контроля.

Рис. 7.16. Двоичный симметричный канал со стираниями.

7.6. Теорема кодирования для дискретных каналов без памяти

Рассмотрим дискретный канал без памяти с пропускной способно-стью С[бит/символ], в котором каждый символ передается в течении Т s сек. Для этого канала

Пусть энтропия некоторого источника X , измеренная в течении сек, составляет Н(Х) бит. Тогда имеет место следующая теорема.

Теорема 7.6.1. Теорема кодирования для канала (теорема Шенно-на).

Для источника X со скоростью R = H (X )/ T S [бит/сек] и R < С существует некоторый код. с помощью которого информация источ-ника X может быть передана но каналу связи с пропускной способ-ностью С 1 [бит/сек] со сколь угодно малой вероятностью ошибки.*

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

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

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

Теорема кодирования определяет также верхнюю границу для скорости передачи R .*

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

* Здесь необходимо сделать разъяснение. Существует обратная теорема кодиро-вания, которая говорит о том. что при R > С не существует никакого метода кодирования, позволяющего передавать информацию с как угодно малой веро-ятностью ошибки. Прим. перев.

Глава 8. Непрерывные источники и каналы

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

Рис. 8.1. Сигнал непрерывного источника.

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

8.1. Дифференциальная энтропия

На рисунке 8.2 показаны два непрерывных источника X и Y , свя-занные каналом (аналогично рис. 7.4). Здесь, вместо вероятностей, стоят функции плотностей распределения вероятностей стохастических переменных.

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

Рис. 8.2. Два непрерывных источника без памяти, связан-ных каналом.

Преобразуем непрерывный источник X в дискретный. Для это-го проквантуем значения аналогового выхода источника с шагом Δ (рис. 8.3).

Рис. 8.3. Оцифровка непрерывного источника с интерва-лом квантования Δ в моменты наблюдения t 0 , t 1 и т.д.

Кроме этого, как это обычно делается в теории информации, про-изведем дискретизацию источника но времени. В результате, полу-чим последовательность стохастических переменных Следуя таблице 7.2, определим взаимную информацию символов x i , и y j , где x i - значение выходного символа в момент времени t m , a x j - в момент времени t n

Взаимную информацию можно трактовать как «снятую» (утра-ченную) неопределенность попадания переменной Х п в интервале , когда известно, что переменная Х т принадлежит интер-валу или наоборот. Будем считать функцию плотности распределения вероятности непрерывной функцией. Тогда, устрем-ляя ширину интервала квантования к нулю, получим

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

Замечание. Здесь, для приведения в соответствие обозначений этой главы с результатами таблицы 7.2, вместо Х т используется X , а вместо Y n - Y .

Информация источника определяется исходя из аналогичных рас-суждений

В отличие от выражения (8.3) для взаимной информации, в (8.4) появляется слагаемое, зависящее от интервала квантования Δ.

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

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

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

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

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

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

Замечание. В информационной технике за исходный параметр принимают σ 2 - дисперсию, которая определяет среднюю мощ-ность стохастического процесса [ 10]. Ясно, что с увеличением мощности передатчика, количество передаваемой информации уве-личивается и, наоборот, с увеличением мощности шумов, возрас-тает неопределенность, т.е. в единицу времени передается меньше информации.

Из теории информации следует, что дифференциальная энтропия достигает своего максимума при гауссовском распределении вероят-ности.

Теорема 8.1.1. При заданной дисперсии σ 2 , максимальной диффе-ренциальной энтропией обладает источник с гауссовским распреде-лением вероятности, причем.

Пример: Дифференциальная энтропия гауссовского источника.

Из (8.5) следует, что дифференциальная энтропия гауссовского источника равна

Выражение в квадратных скобках может быть разложено на два интеграла. Таким образом, окончательно имеем

Численные примеры для трех, наиболее употребительных распреде-лений, приведены в таблице 8.1.

Таблица 8.1. Пример дифференциальной энтропии.

Пример: Телефония.

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

Исходя из равномерного распределения вероятностей в интервале [-1,1], опытным путем получим σ 2 = 1/3. Таким образом, дифферен-циальная энтропия на один отсчет составляет

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

- (ДСК) это простейший канал связи, на вход которого подаются двоичные символы с предположением, что данные всегда будут передаваться корректно. Этот канал часто используется в теории кодирования, как один из самых простейших для анализа… … Википедия

двоичный симметричный канал - Канал передачи данных, в котором вероятности появления ошибок в символах “0” и “1” в среднем одинаковы и отсутствует влияние предыдущих символов на последующие. Достоверность передачи информации не зависит от того, какой… …

- (англ. channel, data line) система технических средств и среда распространения сигналов для передачи сообщений (не только данных) от источника к получателю (и наоборот). Канал связи, понимаемый в узком смысле (тракт связи),… … Википедия

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

Канал связи, переходная функция к рого обладает тем или иным свойством симметрии. Однородный канал без памяти с дискретным временем и конечными пространствами состояний У и компонент сигналов на входе и выходе, задаваемый матрицей переходных… … Математическая энциклопедия

I Канал (от лат. canalis труба, жёлоб) в гидротехнике, искусственное русло (водовод) правильной формы с безнапорным движением воды, устроенное в грунте. К. сооружают в открытой выемке или в насыпи (при пересечении балок, оврагов и др.),… … Большая советская энциклопедия

Цифровой канал передачи - 3.8 Цифровой канал передачи комплекс технических средств и среды передачи, обеспечивающий передачу цифрового сигнала электросвязи со скоростью передачи, характерной для данного канала передачи. Источник …

цифровой канал передачи данных - цифровой канал ПД Канал передачи данных, по которому может передаваться только цифровой сигнал данных. Примечание Цифровому каналу передачи данных присваивается название в зависимости от вида передаваемого сигнала, например, двоичный цифровой… … Справочник технического переводчика

Цифровой канал передачи данных - 164. Цифровой канал передачи данных Цифровой канал ПД Е. Digital data channel Канал передачи данных, по которому может передаваться только цифровой сигнал данных. Примечание. Цифровому каналу передачи данных присваивается название в зависимости… … Словарь-справочник терминов нормативно-технической документации

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

ГОСТ Р 51385-99: Элементы процедур передачи и форматы служебных пакетов (сообщений) в широкополосной цифровой сети интегрального обслуживания с быстрой коммутацией пакетов. Требования к процедурам и форматам - Терминология ГОСТ Р 51385 99: Элементы процедур передачи и форматы служебных пакетов (сообщений) в широкополосной цифровой сети интегрального обслуживания с быстрой коммутацией пакетов. Требования к процедурам и форматам оригинал документа: 2.2… … Словарь-справочник терминов нормативно-технической документации

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

	Передатчик	Канал	Приемник
Разговор людей	Голосовой аппарат человека	Воздушная среда. Акустические колебания	Слуховой аппарат человека
Телефонный разговор	Микрофон	Проводник. Переменный электрический ток	Динамик
Передача данных в сети Интернет	Модулятор	Проводник. Оптоволоконный кабель . Переменный электрический ток. Оптический сигнал	Демодулятор
Радиотелефон, рация	Радиопередатчик	Эфир. Электромагнитные волны	Радиоприемник

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

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

Рис. 7.1.

Для изучения механизма воздействия помех на процесс передачи данных и способов защиты от них необходима некоторая модель. Процесс возникновения ошибок описывает модель под названием двоичный симметричный канал (ДСК) , , схема которой показана на рис.7.2 .

Рис. 7.2.

При передаче сообщения по ДСК в каждом бите сообщения с вероятностью может произойти ошибка, независимо от наличия ошибок в других битах. Ошибка заключается в замене знака 0 на 1 или 1 на 0.

Некоторые типы ошибок:

Чаще других встречается замена знака. Этот тип ошибок исследован наиболее полно.

Способы повышения надежности передачи сообщений

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

Сообщения	Кодовое слово
	00
	01
	10
	110
	111

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

На практике необходим компромисс между экономностью кода и защитой от ошибок.

Сначала удаляется "бесполезная" избыточность (в основном статистическая), а затем добавляется "полезная" избыточность , которая помогает обнаруживать и исправлять ошибки.

Рассмотрим некоторые методы повышения надежности передачи данных. Широко известными методами борьбы с помехами являются следующие :

1. передача в контексте;
2. дублирование сообщений;
3. передача с переспросом.

Рассмотрим подробней каждый из этих способов.

1. Передача в контексте. С этим хорошо известным и общепринятым способом сталкивался каждый, кто, пытаясь передать по телефону с плохой слышимостью чью-либо фамилию, называл вместо букв, ее составляющих, какие-нибудь имена, первые буквы которых составляют данную фамилию. В данном случае правильному восстановлению искаженного сообщения помогает знание его смыслового содержания.
2. Дублирование сообщений . Этот способ тоже широко применяется в житейской практике, когда для того, чтобы быть правильно понятым, нужное сообщение повторяют несколько раз.
3. Передача с переспросом . В случае, когда получатель имеет связь с источником сообщений , для надежной расшифровки сообщений пользуются переспросом, т. е. просят повторить все переданное сообщение или часть его.

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

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

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

Принципы обнаружения и исправления ошибок с использованием кодов

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

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

Рассмотрим схему передачи данных, показанную на рис.7.3 .

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

Рис. 7.3.

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

Рис. 7.4.

В геометрической интерпретации эти блоки можно рассматривать как точки n-мерного пространства , где . Точки этого пространства представляют собой последовательности чисел 0 и 1 длины . Пространства для можно представить в виде угловых точек единичного интервала (), вершин квадрата со стороной, равной 1 (), и вершин куба с ребрами длины 1 (). Эти пространства условно изображены на рис.7.5 .

Код, используемый для обнаружения и исправления ошибок, представляет собой некоторое