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

f (, ,…, ,

где =

= , (2.23)

На рис. 2 пунктиром показаны рассчитанные на ЭВМ зависимости E_r(R) от v при тех же параметрах R, n_f и h², что и для составного РЗК, но для «худшей» функции кратности (2.23). Видно, что они отличаются от составного РЗК незначительно и даже в этом случае E_r(R) существенно возрастает при увеличении v, что говорит о целесообразности q-ичного кодирования при медленных замираниях с произвольным законом распределения.

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

Подставляя границу (2.10) в (2.9), а (2.9) в (2.12), получим верхнюю границу для P_од, где, однако,

= , (2.24)

рассчитывается по (2.10), a P(v, 0) -- по (2.11).

На рис. 5 показана рассчитанная на ЭВМ зависимость E_r(R) как функция v для =25 и различных параметров r. Видно, что при r0,7 функция E_r(R) оказывается лучше, чем для составного канала (см. рис. 2) при тех же значениях параметров , R и v, а при r0,9 она идет ниже соответствующей кривой для составного канала, что, по-видимому, объясняется грубостью границ (2.10), (2.11). Представляет интерес определить худшее распределение конфигураций ошибок (2.9), не ограничиваясь классом квазибиномиальных каналов или РЗК, но полагая заданной вероятность P(v,0) безошибочного приема блока длины v, тем более что эта функция определяется экспериментально достаточно просто.

Рис.6 Зависимость E_r(R) для различных параметров h², c экстремумом

Рис.7 Зависимость пропускной способности на один бит для канала с распределением

Данная задача соответствует нахождению экстремума функции

(e) (2.25)

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

= 1-P (v,0) ,(2.26)

где {0} означает конфигурацию ошибки из v нулей.

Решение методом неопределенных множителей Лагранжа дает следующий результат:

P(e=0) = P(v, 0)(2.27)

P(e0) = ( l - P ( v , 0))/(2^v - l ).

Распределение вероятностей конфигураций ошибок (2.27) весьма близко (при больших v) к распределению, когда с вероятностью P₀=P(v, 0) каждая из строк матрицы рис. 1 заполняется нулями и с вероятностью 1-- Р₀ в каждой из строк независимо и равновероятно формируются нули и единицы для каждого из ее элементов. Физически такая ситуация соответствует независимому появлению с вероятностью 1-- Р₀ на каждой из n_f частот модема мощной сосредоточенной помехи, которая приводит к обрыву канала на этой частоте и пренебрежимо малому уровню шума на частотах, не пораженных сосредоточенными помехами.

Пропускная способность такого канала равна С=Р₀ и она реализуется при использовании каскадного кода с обнаружением ошибок внутренним кодом, символы которого расположены в различных столбцах, и исправлением стираний внешним PC-кодом, символы которого расположены в различных строках матрицы рис. 1. Однако для достижения P_одпри RC необходимо увеличивать как параметр v, так и параметр п_f для конечных же значений n_f и v верхнюю границу P_од для такого канала можно рассчитать по (2.12), где

=, (2.28)

Очевидно, что для такого канала при фиксированной величине v оптимальным алгоритмом декодирования q-ичного кода будет принятие решения о передаче такого кодового слова, которое отличается от принятого слова в наименьшем числе q-ичных символов.

Для расчета верхней границы P_од с использованием (2.28) необходимо задать зависимость P (v, 0) как функцию от v. Например, для зависимости P(v, 0), определенной соотношением (2.11), на рис. 6 показана E_r(R) как функция v для различных параметров h². Видно, что в отличие от рис. 2 она имеет экстремум, что объясняется, с одной стороны, увеличением c ростом v возможностей исправления ошибок при переходе к более мощному коду, а с другой стороны -- монотонным ухудшением качества двоичного канала при увеличении v из-за монотонного уменьшения Р (v, 0). На том же рисунке пунктирной линией показана аналогичная зависимость для функции P(v, 0), которая характерна для биномиального канала (P(v, 0) = (1-- p)^v, где p=1/(2+h²)). Видно, что для этого случая экстремум оказывается еще более острым, a E_r(R) становится меньше для всех v, что, естественно, объясняется более резким убыванием P(v, 0) как функции v, чем в случае составного канала. Уменьшение функции E_r(R) для распределения (2.27) по сравнению с составным РЗК, объясняется невозможностью использования распределения переходных вероятностей в q-ичном канале при декодировании, поскольку оно вырождается в (2.27).

С другой стороны, если не выполнять оптимальное декодирование, а только исправление ошибок не выше кратности d/2, то Р_од существенно увеличивается. Так, например, для составного РЗК q=2^v- ичного кода (24,6) при v=10, h²=25 (что дает P (v, 0)=0,84) получаем при расчете по (2.28) Р_од=3,2610^-7 и только 5,6 10^-4 при расчете по (2.20). На рис. 7 показана зависимость пропускной способности на один бит для канала с распределением (2.27), как функция v для P(v, 0), определяемой (2.11). Видно, что С максимизируется при некотором значении v. Кажущийся парадокс ухудшения канала с ростом v объясняется тем, что для модели (2.27) q-ичный канал с большим v не является расширением канала с меньшим v в том смысле, что вероятности конфигураций ошибок с меньшим v не являются вероятностями цилиндрических множеств в канале с большим v.

Как видно из результатов, представленных в предыдущих разделах, q-ичное кодирование в каналах, образованных многочастотными модемами, позволяет, несмотря на наличие сильной памяти по временной координате, значительно повышать надежность связи и при больших значениях q такой метод имеет преимущества перед двоичным кодированием или простыми вариантами каскадного кодирования. Существенным обстоятельством является декодирование по максимальному правдоподобию, которое при больших значениях q в настоящее время практически нереализуемо. Решение экстремальных задач позволяет сделать вывод, что при любых распределениях ошибок в строках матрицы рис. 1 (любых законах медленных замираний), кодирование q-ичными кодами оказывается эффективным при фиксированных «средних» характеристиках канала (вероятность ошибки символа р или безошибочного приема P(v, 0)).

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

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

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

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

Пусть S_t -- возможное состояние рассматриваемой системы обслуживания, характеризуемое тем, что в ней занято ровно i каналов обслуживания, i = 0, m, а возможное состояние системы S_m+r характеризуется тем, что все m каналов обслуживания заняты и очередь состоит из r заявок, где r 1. Если на длину очереди не накладывают ограничений, то r может быть сколь угодно большим и система может иметь счетное множество состояний. Системы обслуживания с отказами и с ограничениями на длину очереди могут иметь лишь конечные множества возможных состояний.

За бесконечно малый промежуток времени t система обслуживания с простейшим входным потоком заявок и экспоненциальным законом распределения времени обслуживания либо остается в прежнем состоянии (S_t), либо переходит в соседнее (S_t+1 или S_t-1 при i I, S₁ при i = 0).

Таким образом, в любой момент времени t система обслуживания с m идентичными параллельными каналами обслуживания находится в одном из своих возможных состояний { S_t=0, n N или n = . При этом:

если i = то занято i каналов и очереди нет;

если i то заняты все m каналов и в очереди находится (n-m) заявок;

если n = m, то рассматривают систему обслуживания с отказами;

если m < n < , то рассматривают систему обслуживания с ограниченной длиной очереди;

если n = , то рассматривают систему обслуживания с ожиданием без ограничений на длину очереди.

Пусть {S_t=0 -- множество возможных состояний рассматриваемой системы обслуживания. Для i = введем случайное событие а_t, заключающееся в том, что в момент времени t 0 система находится в состоянии S_t, и обозначим вероятность его реализации через p_t (t): р_t (t)Р[а_t]. В любой момент времени исходная система может находиться лишь в одном из возможных состояний, поэтому {а_t=1 -- полная группа событий и, как следствие,

(3.1)

Одна из задач теории массового обслуживания сводится к определению вероятностей p_t (t), i = как функций времени.

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

а) элемент размеченного графа состояний системы S, соответствующий возможному состоянию S_k, будем называть k-й вершиной графа; стрелки, указывающие возможные переходы системы S из состояния в состояние, с записанными переходными вероятностями, -- нагруженными дугами, а переходные вероятности -- весами;

б) при составлении системы уравнений Колмогорова можно использовать следующее правило: производная от вероятности пребывания системы в состоянии S_t в момент времени t равна сумме произведений весов дуг, инцидентных i-й вершине размеченного графа состояний, на вероятности состояний, к которым они направлены; при этом вес дуги берется со знаком

„плюс", если дуга направлена к i-й вершине, соответствующей состоянию S_t , и со знаком „минус" в противном случае;

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

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

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

Рис. 8 граф состояний канала

В данном случае система имеет лишь два возможных состояния: S₀ -- канал свободен; S₁ -- канал занят. Ее размеченный граф состояний изображен на рис. 8.

Если считать, что в начальный момент времени t = 0 система находилась в состоянии S₀, то математическая модель изучаемого процесса массового обслуживания имеет следующий вид:

При этом, учитывая, что, согласно (3.1),

математическую модель можно упростить:

Решив полученную задачу Коши, находим (рис. 9)

Рис. 9 График относительной пропускной способности системы

Важнейшими характеристиками системы обслуживания с отказами являются:

а) абсолютная пропускная способность -- среднее число заявок, которое может обслужить система в единицу времени;

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

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

При стационарном (установившемся) режиме функционирования имеем

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

= .

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

Одноканальная система обслуживания представляет собой телефонную линию. Заявка-вызов, поступившая в момент, когда линия занята, получает отказ. Интенсивность потока заявок 0,8 (вызовов в минуту). Средняя продолжительность разговора 1,5 минуты. Считая поток заявок простейшим, а время обслуживания распределенным по экспоненциальному закону, определим в стационарном режиме функционирования:

1) абсолютную пропускную способность канала связи Q;

2) относительную пропускную способность канала связи q;

3) вероятность отказа р_от.

Имеем

л= 0,8, µ= .

Таким образом,

Q = = 0,3636

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

q = = 0,4545

Есть вероятность того, что заявка будет обслужена, не получив отказа. Поэтому

Р_от = 1 - q = 0,5454.

Отметим, что номинальная пропускная способность рассматриваемого канала связи Q_ном, являясь величиной обратной по отношению к средней продолжительности времени разговора (Q_ном = µ = 2/3 0,66), почти вдвое больше его пропускной способности Q, определенной с учетом случайного характера потока заявок и времени обслуживания.

Заключение

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

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

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

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

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

Рассчитано и доказано, что пропускная способность канала с памятью не меньше пропускной способности канала без памяти.

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

Литература

Теория электрической связи / А.Г. Зюко, Д.Д. Кловский, В.И. Коржик, М.В. Назаров; Под ред. Д.Д. Кловского. - М.: Радио и связь, 1998, -432 с.

Теория информации и кодирование / Самсонов Б.Б., Плохов Е.М.,Филоненков А.И., Кречет Т.В. - Ростов на Дону, 2002, 288 с.

Вернер М. Основы кодирования. - М.: Техносфера, 2004. -288 с.

Зарубин B.C. Математическое моделирование в технике: Учеб. для вузов/Под ред. B.C. Зарубина, А.П. Крищенко. - 2-е изд., стереотип. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2003. -496 с.

Волков И.К., Зуев СМ., Цветкова Г.М. Случайные процессы: Учеб. для вузов / Под ред. B.C. Зарубина, А.П. Крищенко. - М.: Изд-во МГТУ им. Н.Э. Баумана, 1999. -448 с.

Финк ЛМ. Теория передачи дискретных сообщений. М.: Сов. радио, 1970.

7. Полтырев Г.Ш., Шехунова НА. Декодирование в дискретных каналах с памятью // Вопросы кибернетики. М.: Наука, 1977. Вып. 34. С. 130-158.

8. А. Файнстейн Основы теории информации, перевод с Английского И.Н, Коваленко и Э.Р. Ницкой под редакцией И.И. Гихмана М.: Издательство Иностранной литературы 1960.

9. Бернард Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд.2-е, испр.: Пер. с англ. - М.: Изд.дом «Вильямс», 2003.-1104 с. :ил. - Парал. тит. англ.

10. Wolfowitz J. Memory Increases Capacity, Inform, and Control, 1967, 11, 4, 423--428. Перевод JP. Л. Добрушин у М. С. Пинскер, Проблемы передачи информации. 1969г.

11. Gallager R. G. A. Simple Derivation of the Coding Theorem and Some Applications, IEEE Trans. Inform. Thory, 1965, 11, 1, 3--18. (Русск. пер.: Галлагер Р. Г. Кибернетический сб., 3. Новая серия. М., «Мир», 1966).

12. Вольфовиц Дж. Теоремы кодирования теории информации. М., «Мир», 1967.

13. Общероссийский математический портал Math-Net.Ru http://www.mathnet.ru/

Размещено на Allbest.ru