6. Каналы связи (Лекции 9, 10 )

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

Модель канала

Согласно эталонной модели, каналом передачи данных (ПД) является совокупность средств двух уровней:

• физического;

• канального.

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

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

По типу все процессы в системе связи делятся на дискретные и непрерывные (См. раздел 1).

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

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

Очевидно, объем алфавита совпадает с числом уровней квантования :

.

Максимальная ошибка при такой замене непрерывных значений отсчетов дискретными равна

.

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

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

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

В узком смысле кодирование – это преобразование дискретного сообщения в последовательность кодовых символов по определенному правилу. Кодирование в широком смысле – это любое преобразование сообщения в сигнал путем установления взаимного соответствия. Множество всех кодовых последовательностей (кодовых комбинаций), возможных при данном правиле кодировки, образует код. Совокупность символов, из которых состоят кодовые последовательности, называют кодовым алфавитом. Количество символов в кодовой комбинации может быть одинаковым или разным. Соответственно различают равномерные и неравномерные коды. Число символов в кодовой комбинации равномерного кода называется длиной кода. Благодаря простоте реализации наибольшее распространение приобрел двоичный код с двумя символами 0 и 1. Последовательности кодовых символов на выходе кодера называются кодовыми комбинациями или кодовыми словами.

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

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

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

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

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

Каналы передачи информации классифицируют по разным признакам: по назначению, по характеру линий связи, по диапазону частот, по характеру сигналов на входе и выходе каналов и тому подобное. В теории передачи сигналов каналы классифицируют по характеру сигналов на входе и выходе. Различают непрерывные, дискретные и дискретно-непрерывные каналы. В непрерывных каналах сигналы на входе и выходе непрерывны по уровням; в дискретных каналах – они соответственно дискретные; а в дискретно-непрерывных – сигналы на входе дискретны, а на выходе непрерывные, и наоборот.

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

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

Рассмотрим коротко особенности использования радиоволн разных диапазонов в каналах с открытым распространением. В диапазонах инфранизких (ИНЧ), очень низких (ОНЧ) и низких (НЧ) частот на небольших расстояниях поле в месте приема образуется за счет дифракционного огибания волнами выпуклой поверхности Земли. На больших расстояниях радиоволны распространяются в своеобразном сферическом волноводе, внутренняя стенка которого образуется поверхностью Земли, а внешняя – ионосферой. Такой механизм распространения позволяет принимать сигналы в любой точке Земли, причем параметры принятых сигналов отличаются достаточно высокой стабильностью. Особенностью этих диапазонов является также способность волн проникать в толщу Земли и воды на глубину в десятки метров. Принципиальным недостатком таких каналов является: ограниченная полоса частот и очень большие линейные размеры антенных устройств, соизмеримых с длиной волны, достигающих километров. Сверхдлинные волны применяются для навигации и передачи информации на подводные объекты.

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

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

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

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

Рассмотрим особенности передачи сигналов по непрерывному каналу. В разделе 1 мы кратко отметили достоинства и недостатки аналоговых систем связи. Здесь рассмотрим особенности передачи сигналов по непрерывному каналу подробнее.

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

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

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

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

,

где – принятый с искажениями полезный сигнал с параметрами .

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

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

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

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

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

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

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

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

Характеристики канала

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

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

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

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

Характеристики ошибок в дискретном канале

Как показывает анализ экспериментальных данных, можно сделать следующие выводы о характере ошибок в реальных каналах.

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

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

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

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

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

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

Основные модели источника ошибок

Моделей источников ошибок (ИО) существует много. Мы коротко остановимся на одной из них.

Описание источника ошибок на основе цепи Маркова [1, 3]

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

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

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

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

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

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

Перечислим лишь некоторые задачи анализа и синтеза систем, которые можно решать на базе теории марковских процессов.

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

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

3. Наиболее полные и продуктивные результаты в области синтеза оптимальных систем при наличии случайных воздействий с известными или неизвестными характеристиками удается получить для марковских процессов.

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

Широкое использование марковской модели в радиотехнике и в связи объясняется такими причинами:

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

▪ гауссовы случайные процессы со спектральной плотностью средней мощности в виде дробно-рациональной функции частоты всегда с заданной точностью можно аппроксимировать марковскими процессами;

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

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

Дискретные цепи Маркова (марковские цепи)

В теории вероятностей и во многих ее приложениях используется так называемая схема независимых испытаний. Значение термина "независимые испытания" заключается в том, что результат испытания в некоторый момент времени не влияет на результат любого другого испытания в любой следующий момент времени. Общая постановка задачи при этом такая: при заданных вероятностях каждой из возможных событий необходимо определить вероятность того, что за серию испытаний некоторое испытание состоится заданное количество раз. Такую задачу можно решать и для более сложного случая зависимых испытаний. В этом случае вероятность осуществления некоторого события в i-том испытании зависит от результатов предыдущих испытаний. При этом, очевидно, предыдущие испытания по-разному влияют на результат испытания, которое осуществляется. Интуитивно можно считать, что при увеличении значения степень этого влияния уменьшается. Обычно величину ограничивают некоторым значением так, что при результаты испытаний уже не влияют на результат i-го испытания.

Последовательность таких зависимых испытаний называют цепью

Маркова.

Выбор значения величины m играет принципиальную роль, и определяет связность цепи.

Цепь Маркова называется m-связной, если на результат каждого испытания влияют только m предыдущих испытаний.

Односвязную цепь (m=1) называют простой цепью Маркова.

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

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

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

Таким образом, цепи Маркова являются дискретными как по состоянию, так и по времени.

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

, (6.1)

где – начальное состояние системы (перед первым шагом); – состояние системы непосредственно после первого шага и т. д.

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

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

Пример 6.1

Пусть имеется марковская цепь с N состояниями . Рассмотрим, что собой представляет марковский процесс во временной области.

Решение:

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

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



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

Вероятности перехода цепи Маркова

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

Вероятности являются основными характеристиками марковских цепей и называются вероятностями перехода из состояния в состояние .

Поскольку система может находиться в одном из N состояний, в каждый момент времени необходимо задать вероятностей перехода . Эти вероятности удобно записывать в виде такой матрицы:

. (6.2)

Матрицу (6.2) называют матрицей перехода. В каждой строке этой матрицы записаны вероятности всех возможных переходов из выбранного состояния. Эти переходы представляют полную группу событий. Таким образом:

Матрица перехода – это всегда квадратная матрица с неотрицательными элементами, сумма которых в каждой строке равняется единице.

Матрицы, которые удовлетворяют этим требованиям, называются стохастическими матрицами.

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

В случае однородной цепи Маркова матрица перехода (6.2) записывается в виде

. (6.3)

Определив вероятности переходов конкретной цепи, можно сделать классификацию этой цепи и ее состояний.

Классификация состояний и цепей Маркова

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

● Два состояния и , для которых и , то такие состояния называются соединеняющимися.

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

● Если множество соединяющихся состояний состоит из одного состояния, это состояние называется поглощающим состоянием. В это состояние процесс может войти, но выйти из него не может. Это значит, что для поглощающего состояния вероятности перехода равняются: , а .

● Если среди всех состояний цепи Маркова есть хотя бы одно поглощающее состояние, цепь называют поглощающей цепью Маркова.

● Цепь Маркова, которая не содержит поглощающих состояний и состоит из одного класса соединеняющихся состояний, называют эргодической марковской цепью.

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

Вероятности начальных состояний цепи Маркова

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

Вероятности начальных состояний являются безусловными вероятностями и образуют вектор-строку

, (6.4)

сумма элементов которого по условию нормировки должна равняться единице.

Если начальное состояние системы известно точно, например, это состояние , тогда для всех и .

Следовательно, если известны матрица перехода (6.2) и вектор-строка вероятности начальных состояний (6.4), цепь Маркова полностью определена. Теперь можно начать анализ процессов, которые происходят в марковских цепях. Рассмотрим сначала такую задачу.

Пусть некоторая система в данный момент времени находится в состоянии . Нужно найти вероятность того, что система перейдет в состояние за 2, 3, …, n шагов. Иначе говоря, нужно найти матрицу перехода для заданного количества шагов, если известна матрица перехода за 1 шаг.

Уравнение Колмогорова - Чепмена

Для однородной цепи Маркова вероятность перехода из i-го в j-ое состояние за 2 шага, то есть , определяется таким очевидным соотношением:

, (6.5)

где и – элементы заданной матрицы перехода за 1 шаг.

Переходя к матричной записи выражения (6.5), получаем, что матрица перехода за 2 шага равняется произведению двух одинаковых матриц (6.3), то есть

. (6.6)

Вероятность перехода из из i-го в j-ое состояние за 3 шага можно вычислить по формуле

или

.

В общем случае получаем

. (6.7)

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

(6.8)

или

. (6.9)

Матрица перехода за n шагов равняется произведению матрицы перехода зa q шагов и матрицы перехода за шагов.

Соотношение (16.9) устанавливает связь между вероятностями перехода для любых трех последовательных моментов времени и носит название уравнения Колмогорова-Чепмена.

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

Кроме условных вероятностей (матриц перехода) часто возникает необходимость найти безусловные вероятности состояний системы в 1, 2,…, n-й моменты времени. Для их определения используют вектор-строку вероятностей начальных состояний .

Безусловная (абсолютная) вероятность того, что после первого шага цепь Маркова перейдет в состояние j определяется очевидным соотношением

. (6.10)

Совокупность безусловных вероятностей состояний образует вектор-строку .

Из (6.10) следует, что вектор-строка вероятностей состояния цепи после первого шага равняется произведению вектора-строки вероятностей начальных состояний на матрицу перехода, то есть

.

Очевидно, что вектор-строка вероятностей состояний после n -го шага определяется выражением

. (6.11)

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

Теорема Маркова о предельных (финальных) вероятностях

Пусть есть некоторая эргодическая марковская цепь. Тогда для нее справедлива такая теорема Маркова.

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

для всех i, j. (6.12)

В матричной форме это записывается так:

. (6.13)

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

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

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

Режим работы эргодической марковской цепи (системы) при достаточно большом значении n называют стационарным режимом марковской цепи.

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

1) Воспользоваться теоремой Маркова, согласно которой возведение матрицы перехода в достаточно высокую степень n должно дать вектор-строку искомых вероятностей. Ясно, что этот алгоритм является чрезвычайно трудоемким.

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

.

При больших значениях n безусловные вероятности равняются финальным вероятностям, поэтому

. (6.14)

Получили систему N алгебраических уравнений с N неизвестными. Чтобы решить эту систему, из (6.14) надо взять N–1 уравнение и дополнить систему условием нормировки .

Рассмотрим два примера примера.

Первый пример.

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

.

Нужно найти вероятности ссостояний ЭВМ после трех проверок.

Решение: