Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Математические модели дискретных каналов с памятью - файл 1.doc


Математические модели дискретных каналов с памятью
скачать (6894.5 kb.)

Доступные файлы (1):

1.doc6895kb.20.11.2011 16:41скачать

содержание

1.doc

  1   2   3   4
ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

БАШКИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ФИЗИЧЕСКИЙ ФАКУЛЬТЕТ
Кафедра статической радиофизики и связи
Курсовая работа по теории электрической связи


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


Выполнила студентка 3 курса

группы 3 ФТОС-2

Осокина Анна Борисовна

Проверил доктор физ.-мат. наук,

проф. Гоц С.С.

Уфа-2009
Оглавление

Введение……………………………………………………………………………….……….3

  1. Дискретные каналы с памятью…………………………………………………….……...4




    1. Математические основы каналов с памятью. Теорема кодирования………….……...5

    2. Примеры каналов, обладающих памятью………………………………………….…...11




  1. Основные математические модели дискретных каналов с памятью………………….14


2.1. Математическая модель канала с памятью коррелированными замираниями…...…14

2.2. Математическая модель дискретных «двумерных» каналов с памятью……..………16

2.3. Вероятности ошибки для некоторых каналов с памятью………………………..……17

2.3.1 Расчет верхней границы Род для квазибиномиальной модели……………….…19

2.3.2 Расчет верхней границы Род для произвольных РЗК……………………….…...23


  1. Практическая реализация каналов с памятью, на примере Марковских моделей массового обслуживания……………………………………………………………………..27




    1. Задача о функционировании одноканальной системы обслуживания с отказами…...28

    2. Задача о пропускной способности одноканальной системы обслуживания………...31


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

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

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

Во второй главе рассмотрены основные математические модели дискретных каналов с памятью:

  • Математическая модель канала с памятью коррелированными замираниями.

  • Математическая модель дискретных «двумерных» каналов с памятью.

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

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

  1. Дискретные каналы с памятью.


В канале, без памяти, основным событием является передача и прием простого элемента, т. е. канал полностью определяется заданием вероятностей возможных выходов всевозможных простых передач. С другой стороны, рассмотрим канал, в котором передача простого посылаемого символа вызывает определенного вида „шум", интерферирующий с выходом последующего символа. Для полного определения системы в этом случае необходимо множество условных вероятностей р (у|х, х'), где х' означает посылаемый символ, переданный непосредственно перед х. Если передача простого символа сопровождается „шумом", интерферирующим с выходом двух последующих символов, канал будет определяться набором условных вероятностей р (у | х, х', х"), где х" предшествует х'.

Другим типом канала с памятью будет канал, в котором последовательные „шумовые выборки" не зависят от всех переданных раньше символов, хотя и не являются статистически независимыми. Другими словами, равенство p1, у2, | х1, х2) = p1 | х1) p2 | х2) в общем случае неверно. В данном разделе курсовой работе мы определим класс каналов, обладающих памятью, который фактически включает оба типа, рассматриваемые здесь.

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

Лемма 1. Для любых ε, δ >0 найдется натуральное n (ε, δ), такое, что для любого nn (ε, δ) множество u-элементов, для которых неравенство
| H (x)+ log p (u) | < ε (1.1)
не выполняется, обладает p (u) вероятностью, меньшей δ. Аналогично, хотя уже с другим n (ε, δ), множество пар (u, υ), для которых не выполняется неравенство

| H (X | Y)+ log p (u, υ) | < ε (1.2)
обладает вероятностью p (u, υ), меньшей δ.

Доказательство. Утверждения данной леммы попросту сводятся к слабому закону больших чисел. На самом деле нам понадобится только одна часть каждого из этих двух неравенств, а именно
p (u) < 2-n [H (X) - ε] и p (u, υ)> 2-n [H (X | Y) + ε] (1.3)
Вероятности невыполнения данных неравенств будут обозначаться соответственно через δ - и δ +.

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

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


    1. Математические основы каналов с памятью. Теорема кодирования.


Перейдем теперь к определению класса каналов, обладающих памятью. Обозначим через (X, х) конечное абстрактное множество. Пусть XI означает множество всех бесконечных в обе стороны последовательностей (..., x-1, х0, х1, . . .), где хi X, i = 0, ±1, ±2,...; т. е, XI = Xi , где Xi =X. Если n – положительное целое число, а0, ..., an-1 — элементы X, t — заданное целое число, то множество всех последовательностей из XI , удовлетворяющих соотношению xt+k = ak, k = 0,…, n — 1, мы назовем цилиндрическим множеством; цилиндрическое множество определяется заданием n, t и а0, ..., an-1. Борелевское поле элементов XI, порожденное всеми цилиндрическими множествами, обозначим через X.

Обозначим через ^ Т преобразование переноса, определяемое на XI соотношением

T (…, x-1 , x0 , x1 ,…) = (…, x'-1 , x'0 , x'1 ,…) (1.4)
где x'i= xi+1. Тогда существует Т-1 и справедливы следующие утверждения:

1. T XI = XI и Т-1 XI = XI

2. Как Т, так и Т-1 переводят цилиндрические множества в цилиндрические же множества.
3. Как Т, так и Т-1 переводят измеримые множества в измеримые; ни одно из них не переводит неизмеримые множества в измеримые.

Утверждения 1 и 2 очевидны, а первая часть утверждения 3 просто следует из рассуждений о борелевских полях, полученных путем отображения. Что касается второй части утверждения 3, то в случае, когда Т-1S измеримо, Т(Т1S)=S также будет измеримым.

Пусть µ - вероятностная мера на X . Говорят, что мера µ стационарна, если µ (TS) = µ (S) для каждого S X. Если, кроме того, µ (S) = 0 или µ (S) =1 для инвариантных S, т. е. для S, удовлетворяющих условию TS = S, то µ называется эргодической мерой. В дальнейшем µ будет всегда считаться стационарной. Однако поскольку некоторые из наших результатов справедливы для вероятностных мер, являющихся стационарными, но не обязательно эргодическими, мы не будем предполагать эргодичности меры, если она особо не оговорена.

Определим теперь источник информации, образованный пространством XI, борелевским полем X и вероятностной мерой µ. Нашим первым результатом будет определение скорости создания сообщений источником информации.

Предположим, что XI содержит N элементов. Тогда для заданных t и n можно определить в точности Nn цилиндрических множеств. Вместе с вероятностной мерой µ это семейство цилиндрических множеств определяет конечное пространство элементарных событий Хn,t. Поскольку µ стационарна, количество информации, содержащейся в Хn,t , не зависит от t. Обозначим это количество информации через Н(n). Величину Н(Х)= назовем скоростью создания, сообщений (на одну букву) источника XI, X, µ.

Чтобы показать, что действительно существует, заметим, что по лемме Н (m+n) Н(m) + H (n) для любых m и n. Пусть a = inf , тогда для любого ε > 0 существует такое целое q, что a + ε. Для любого целого n ≥ q мы определим целое kn соотношением (kn —1) qn<knq. Тогда H(n) H (knq) knH(q) и, следовательно,. Далее, при n имеем kn, а значит,. Отсюда следует, что lim sup для всех ε > 0, что и означает lim sup а. Поскольку, с другой стороны , то = a = H (X)

Если µ — произведение мер, тогда, очевидно, Н(n) = nН(1); следовательно, Н(Х) = Н(1), что вполне согласуется с нашим предыдущим пониманием символа H (X).

Для определения дискретного канала с памятью введем конечное множество принимаемых сигналов ^ Y. Как и выше, определим Y' и Y. Наконец, для любого х XI обозначим через ν( |х) вероятностную меру на Y, обладающую следующими свойствами:

1. Для любого цилиндрического множества S YI функция ν(S) измерима на XI.

2. ν( |х) стационарна, т. е. для любого S Y,
ν(TS |Tх) = ν(S), (1.5)
где Т — преобразование переноса на XI и YI одновременно.

3. ν( |х) есть мера без предвосхищения, т. е. она обладает следующим свойством: если S Y таково, что из того, что (…, y-1, ν0, y1, …) S для некоторого фиксированного t, следует (…, y-1, ν0, y1, …) S при y'к, для которых y'i=yi, it, то ν(S) = ν(S |х') при любых х и х', для которых х'ii, it.

Условие 1 является техническим, и важность его очевидна. Условие стационарности 2 не нуждается в пояснениях; следует, однако, подчеркнуть, что в, общем случае мера ν( |х) не стационарна при фиксированном х. Условие 3 указывает на то, что для нумерации компонент х существенна их зависимость от времени.

Множество объектов X, XI, x, Y, YI, Y и мера ν( |х) определяют канал с памятью. Поскольку XI, x, YI, и Y однозначно определяются по X и Y, мы будем обозначать канал просто X, Y и ν( |х).

Пусть XIYI обозначает, как обычно, множество всех пар ( х, y), и пусть x,y — определенное борелевское поле на XIYI.

Заданная вероятностная мера µ на x, позволяет естественным образом определить вероятностную меру на x,y. Действительно, пусть S], обозначает сечение множества S x,y вдоль х. Тогда при любом х имеем S] y и ν(S] |х) — измеримая функция х. Отсюда просто получаем, что

ω (S) = (1.6)
определяет вероятностную меру на x,y к- Стационарность ω ( ) непосредственно вытекает из стационарности ν( |х) и µ. Далее, мы можем определить стационарную меру на Y, полагая η (S) = ω([XIS]) для любого S y; заметим, что µ = ω([])

Пусть, как и выше, означает семейство цилиндрических множеств на XI с заданными n, t; определяем аналогично. Для краткости мы будем писать и вместо и соответственно. Тогда ω можно рассматривать как вероятностную меру на XnYn; µ = ω([]) — как вероятностную меру на Xn и η = ω([Xn]) —как вероятностную меру на Yn. Таким образом, Н (), H () и Н () полностью определены, поскольку из существования Н(Х)= следует, что Н(Y)= и Н(Х,Y)=также существуют.

По лемме Н () H () + H (), а отсюда R=H(X)+H(Y)—Н(Х, Y) 0. Назовем R скоростью передачи информации (на одну букву) канала X,Y,ν(|х) относительно р. в. на входе i ( ). Наименьшую верхнюю границу R по всем р. в. на входе µ мы называем стационарной пропускной способностью Сs канала X, Y, ν(|х) (на одну букву). Наименьшую верхнюю границу R по всем эргодическим входам, для которых ω также эргодична, будем называть эргодической пропускной способностью Се канала X,Y,ν(|х). Назовем эргодическую меру на входе µ допустимой, если соответствующая мера ω также эргодична.

Уже сейчас очевидно, что каналы с памятью требуют более тонких исследований, чем для каналов без памяти. В частности, уже определены две пропускные способности Cs и Се. Но мы еще не можем утверждать, что Cs или Се достигается на некотором р. в. на входе или на некотором допустимом р. в. на входе соответственно. Мы можем пока только утверждать, что справедливо очевидное соотношение Cs Се. Как мы сейчас увидим, именно с помощью понятия эргодической пропускной способности формулируются известные нам результаты для дискретных каналов с памятью. Основную лемму мы можем обобщить на случай дискретных каналов с памятью только при предположении об эргодичности мер µ и ω. Прежде чем переходить к установлению этого результата, отметим известный факт: стационарное произведение мер в бесконечномерном произведении пространств — таких, как XI, YI, и XIYI, эргодично.

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

Лемма может быть обобщена следующим образом.

Пусть µ эргодична. Тогда для любых ε, δ > 0 существует такое целое положительное n (ε, δ), что если Sn — семейство цилиндрических множеств u из Xn, для которых неравенство
| | ε (1.7)
не выполняется, то (Sn) δ при nn (ε, δ)

Как показано, XIYI можно считать эквивалентным (XY)I . Таким образом, этот результат можно применять к XnYn и Н(Х, Y) всегда, когда ω эргодична, и к Yn и H(Y) в случае, когда η эргодична.

Отметим, что из эргодичности ω следует, что меры =ω([]) и η=([XI]) эргодичны. Действительно, если S X, то S X,Y; если TS = S, то Т (S) = S.

Значит, если ω эргодична, то ω (S= 1 или ω(S=0, т. е. (S)=l или (S)= 0, а это означает, что мера эргодична. Аналогично доказывается эргодичность меры η. Следовательно, допустимая мера является эргодической.
Пусть X, Y, ν( |х) — заданный дискретный канал с памятью, имеющий эргодическую пропускную способность Се > 0. Для любого Н < Се мы, следовательно, можем найти допустимое р. в. на входе , такое, что H(X)+H(Y) — Н(Х, Y) > Н. Будем обозначать элементы Хn и Yn буквами u и υ соответственно. Зададимся произвольными ε, δ1 > 0 и обозначим через Z'n множество тех (u, υ), для которых | | , а через S'n — множество тех , для которых | | . Из САР следует, что для достаточно больших n имеем
ω (Z'n) > 1- и ω (Xn S'n)= > 1- . (1.8)
Тогда, полагая Zn = Z'n, получаем ω (Z'n) > 1- Положим = (что уже определено для всех S'n); тогда для любых ()Zn имеем
| | (1.9)
Оставшиеся действия тривиальны. В отличие от случая канала без памяти, где задается заранее, здесь мы должны определить в соответствии с формулой= имеющей смысл всюду, исключая подмножество Xn -меры нуль, что не вызывает затруднений. Теперь мы можем сформулировать, следующий результат.

Теорема. Пусть X, Y, ν( |х) — дискретный канал с памятью, обладающий эргодической пропускной способностью Се > 0. Тогда для любых Н и е, удовлетворяющих неравенствам 0 <H < Се, е > 0, существует такое целое положительное n(е,Н), что для любого n > n(е, Н) найдутся в Xn элементы u1,…, uN, N 2nH, а в Yn — непересекающиеся множества А1,…, АN, такие, что р (Ai | ui) 1 — е, i = 1, …, N.

Как подразумевается в формулировке теоремы, элементы ui таковы, что р(|ui) определено, т. е. (ui) > 0, где р. в. на входе канала, которое используется для доказательства теоремы. Отметим, что в случае отсутствия памяти утверждение теоремы кодирования не содержало ссылок на р. в. на входе, используемое в доказательстве теоремы. Это расхождение объясняется тем, что интерпретация соотношения р (Ai | ui) 1 — е здесь совершенно отлична от интерпретации. Нельзя интерпретировать это неравенство как утверждение, что „вероятность получения последовательности у0, .... уn-1, такой, что 0, .... уn-1]Ai, когда последовательность xi0, .... xin-1, определяющая ui, передана, будет не меньше 1 — еu. Действительно, слова „u передано" описывают не элементарное событие, каким является передача фиксированного x, а скорее класс (т. е. цилиндрическое множество) событий ui.

Вероятностная мера р( | ui), определенная на Y, является вероятностным распределением на при условии, что передаются только последовательности xui; условные вероятности передачи задаются вероятностной мерой = определенной на борелевском поле всех измеримых подмножеств цилиндрического множества ui. Для того чтобы иметь возможность интерпретировать неравенство р (Ai | ui) 1—е так же, как и в случае отсутствия памяти, нам нужны условия независимости в каком-то смысле. Следующие условия, наложенные на ν( |х), оказываются достаточными.

П.1. Существует фиксированное положительное m, такое, что для любого цилиндрического множества t, .... уt+n-1 ] из YI справедливо соотношение

ν([уt, .... уt+n-1 ] |х) = ν([уt, .... уt+n-1 ] |х') при любых x'i = x i, i = tm, …, t+n—1.

П.2 Для любых двух цилиндрических множеств i, .... уj ] и [у'k, .... у'n ], таких, что j+m<k, где m—фиксированное положительное число, справедливо соотношение
ν([уt, .... уt+n-1 ] |х) = ν([уt, .... уt+n-1 ] |х') = ν([уi, .... уj ] 'k, .... у'n ] |х), (1.10)
для всех х.

Наименьшее m, для которого данный канал удовлетворяет этим двум условиям, называется памятью канала. Если такого m не существует, мы будем говорить, что канал обладает бесконечной памятью. Заметим, что при таком определении канал с нулевой памятью вполне характеризуется заданием значений ν([у0] |х) для всех возможных у0 и всех возможных последовательностей х, отличающихся компонентой х0. Таким образом, канал с нулевой памятью суть просто канал без памяти.

Заметим также, что П. 1 вместе с общим требованием отсутствия предвосхищения ν( |х) гарантирует измеримость функции ν(S) по хдля всех цилиндрических множеств S.

Для канала, обладающего конечной памятью m, условия р (Ai | ui) 1 — е, i = 1, . . ., N, легко сводятся к условиям для ν( |х). Пусть ui = [xi1, .... xin], a z обозначает произвольную последовательность x-m+1, .... x0; обозначим цилиндр [ x-m+1, .... x0, xi1, .... xin ] через [z, ui ]. Тогда

р (Ai | ui) = = ([z, ui]) ν(Ai |[z, ui]) 1 – e (1.11)
Поскольку ([z, ui]) = = 1, отсюда следует, что по крайней мере для одного z, например для zi, должно иметь место неравенство ν(Ai|[zi,ui])1—е. Интерпретация этого неравенства получается сразу же. В комбинации с П. 2 оно позволяет нам „передавать" последовательность (zi,ui) в любом желаемом порядке и при этом принимать каждую последовательность правильно в соответствии с законом больших чисел по крайней мере в 1—е случаях из всех случаев, когда она передавалась, если число случаев стремится к бесконечности.

Невыясненным остается только один пункт. По-прежнему имеется N2nH последовательностей, но длины их теперь равны n+m. Однако, поскольку m фиксировано, а n выбирается произвольно большим, выход из этого положения очевиден. Мы доказываем теорему для некоторого Н', удовлетворяющего неравенству Н < Н'^ С, и выбираем> n настолько большим, чтобы Н' H. Количество последовательностей тогда определится числом N 2nH' 2(n+m)H


    1.   1   2   3   4



      Скачать файл (6894.5 kb.)

      Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации