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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

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

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

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

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

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

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

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

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

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

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

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

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

Лемма 1. Для любых е, д >0 найдется натуральное n (е, д), такое, что для любого n ? n (е, д) множество 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.1 Математические основы каналов с памятью. Теорема кодирования

Перейдем теперь к определению класса каналов, обладающих памятью. Обозначим через (X, х) конечное абстрактное множество. Пусть X^I означает множество всех бесконечных в обе стороны последовательностей (..., x_-1, х₀, х₁, . . .), где х_i X, i = 0, ±1, ±2,...; т. е, X^I = X_i , где X_i =X. Если n - положительное целое число, а₀, ..., a_n-1 -- элементы X, t -- заданное целое число, то множество всех последовательностей из X^I , удовлетворяющих соотношению x_t+k = a_k, k = 0,…, n -- 1, мы назовем цилиндрическим множеством; цилиндрическое множество определяется заданием n, t и а₀, ..., a_n-1. Борелевское поле элементов X^I, порожденное всеми цилиндрическими множествами, обозначим через _X.

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

T (…, x_-1 , x₀ , x₁ ,…) = (…, x'_-1 , x'₀ , x'₁ ,…)(1.4)

где x'_i= x_i+1. Тогда существует Т^-1 и справедливы следующие утверждения:

1. T X^I = X^I и Т^-1 X^I = X^I

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

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

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

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

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

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

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

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

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

1. Для любого цилиндрического множества S Y^I функция н(S |х_?) измерима на X^I.

2. н( |х_?) стационарна, т. е. для любого S _Y,

н(TS |Tх_?) = н(S |х_?),(1.5)

где Т -- преобразование переноса на X^I и Y^I одновременно.

3. н( |х_?) есть мера без предвосхищения, т. е. она обладает следующим свойством: если S _Y таково, что из того, что (…, y_-1, н₀, y₁, …) S для некоторого фиксированного t, следует (…, y_-1, н₀, y₁, …) S при y'_к, для которых y'_i=y_i, it, то н(S |х_?) = н(S |х'_?) при любых х_? и х'_?, для которых х'_i=х_i, it.

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

Множество объектов X, X^I, _x, Y, Y^I, _Y и мера н( |х_?) определяют канал с памятью. Поскольку X^I, _x, Y^I, и _Y однозначно определяются по X и Y, мы будем обозначать канал просто X, Y и н( |х_?).

Пусть X^IY^I обозначает, как обычно, множество всех пар ( х_?, y_?), и пусть _x,y -- определенное борелевское поле на X^IY^I.

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

щ (S) = (1.6)

определяет вероятностную меру на _x,y к- Стационарность щ ( ) непосредственно вытекает из стационарности н( |х_?) и µ. Далее, мы можем определить стационарную меру на _Y, полагая з (S) = щ([X^IS]) для любого S _y; заметим, что µ = щ([])

Пусть, как и выше, означает семейство цилиндрических множеств на X^I с заданными n, t; определяем аналогично. Для краткости мы будем писать и вместо и соответственно. Тогда щ можно рассматривать как вероятностную меру на XⁿYⁿ; µ = щ([]) -- как вероятностную меру на Xⁿ и з = щ([Xⁿ]) --как вероятностную меру на Yⁿ. Таким образом, Н (), H () и Н () полностью определены, поскольку из существования Н(Х)= следует, что Н(Y)= и Н(Х,Y)=также существуют.

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

Уже сейчас очевидно, что каналы с памятью требуют более тонких исследований, чем для каналов без памяти. В частности, уже определены две пропускные способности C_s и С_е. Но мы еще не можем утверждать, что C_s или С_е достигается на некотором р. в. на входе или на некотором допустимом р. в. на входе соответственно. Мы можем пока только утверждать, что справедливо очевидное соотношение C_s С_е. Как мы сейчас увидим, именно с помощью понятия эргодической пропускной способности формулируются известные нам результаты для дискретных каналов с памятью. Основную лемму мы можем обобщить на случай дискретных каналов с памятью только при предположении об эргодичности мер µ и щ. Прежде чем переходить к установлению этого результата, отметим известный факт: стационарное произведение мер в бесконечномерном произведении пространств -- таких, как X^I, Y^I, и X^IY^I, эргодично.

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

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

Пусть µ эргодична. Тогда для любых е, д > 0 существует такое целое положительное n (е, д), что если Sⁿ -- семейство цилиндрических множеств u из Xⁿ, для которых неравенство

| | е(1.7)

не выполняется, то (Sⁿ) д при nn (е, д)

Как показано, X^IY^I можно считать эквивалентным (XY)^I . Таким образом, этот результат можно применять к XⁿYⁿ и Н(Х, Y) всегда, когда щ эргодична, и к Yⁿ и H(Y) в случае, когда з эргодична.

Отметим, что из эргодичности щ следует, что меры =щ([]) и з=([X^I]) эргодичны. Действительно, если 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) > Н. Будем обозначать элементы Хⁿ и Yⁿ буквами u и х соответственно. Зададимся произвольными е, д₁ > 0 и обозначим через Z'_n множество тех (u, х), для которых | | , а через S'_n -- множество тех , для которых | | . Из САР следует, что для достаточно больших n имеем

щ (Z'_n) > 1- и щ (X_n S'_n)= > 1- .(1.8)

Тогда, полагая Z_n = Z'_n, получаем щ (Z'_n) > 1- Положим = (что уже определено для всех S'_n); тогда для любых ()Z_n имеем

| | (1.9)

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

Теорема. Пусть X, Y, н( |х_?) -- дискретный канал с памятью, обладающий эргодической пропускной способностью С_е > 0. Тогда для любых Н и е, удовлетворяющих неравенствам 0 <H < С_е, е > 0, существует такое целое положительное n(е,Н), что для любого n > n(е, Н) найдутся в Xⁿ элементы u₁,…, u_N, N 2^nH, а в Yⁿ -- непересекающиеся множества А₁,…, А_N, такие, что р (A_i | u_i) 1 -- е, i = 1, …, N.

Как подразумевается в формулировке теоремы, элементы u_i таковы, что р(|u_i) определено, т. е. (u_i) > 0, где р. в. на входе канала, которое используется для доказательства теоремы. Отметим, что в случае отсутствия памяти утверждение теоремы кодирования не содержало ссылок на р. в. на входе, используемое в доказательстве теоремы. Это расхождение объясняется тем, что интерпретация соотношения р (A_i | u_i) 1 -- е здесь совершенно отлична от интерпретации. Нельзя интерпретировать это неравенство как утверждение, что „вероятность получения последовательности у₀, .... у_n-1, такой, что [у₀, .... у_n-1]A_i, когда последовательность xⁱ₀, .... xⁱ_n-1, определяющая u_i, передана, будет не меньше 1 -- е^u. Действительно, слова „u передано" описывают не элементарное событие, каким является передача фиксированного x_?, а скорее класс (т. е. цилиндрическое множество) событий u_i.

Вероятностная мера р( | u_i), определенная на _Y, является вероятностным распределением на при условии, что передаются только последовательности x_?u_i; условные вероятности передачи задаются вероятностной мерой = определенной на борелевском поле всех измеримых подмножеств цилиндрического множества u_i. Для того чтобы иметь возможность интерпретировать неравенство р (A_i | u_i) 1--е так же, как и в случае отсутствия памяти, нам нужны условия независимости в каком-то смысле. Следующие условия, наложенные на н( |х_?), оказываются достаточными.

П.1. Существует фиксированное положительное m, такое, что для любого цилиндрического множества [у_t, .... у_t+n-1 ] из Y^I справедливо соотношение н([у_t, .... у_t+n-1 ] |х_?) = н([у_t, .... у_t+n-1 ] |х'_?) при любых x'_i = x _i, i = t -- m, …, 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 не существует, мы будем говорить, что канал обладает бесконечной памятью. Заметим, что при таком определении канал с нулевой памятью вполне характеризуется заданием значений н([у₀] |х_?) для всех возможных у₀ и всех возможных последовательностей х_?, отличающихся компонентой х₀. Таким образом, канал с нулевой памятью суть просто канал без памяти.

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

Для канала, обладающего конечной памятью m, условия р (A_i | u_i) 1 -- е, i = 1, . . ., N, легко сводятся к условиям для н( |х_?). Пусть u_i = [xⁱ₁, .... xⁱ_n], a z обозначает произвольную последовательность x_-m+1, .... x₀; обозначим цилиндр [ x_-m+1, .... x₀, xⁱ₁, .... xⁱ_n ] через [z, u_i ]. Тогда

р (A_i | u_i) = = ([z, u_i]) н(A_i |[z, u_i]) 1 - e(1.11)

Поскольку ([z, u_i]) = = 1, отсюда следует, что по крайней мере для одного z, например для z_i, должно иметь место неравенство н(A_i|[z_i,u_i])1--е. Интерпретация этого неравенства получается сразу же. В комбинации с П. 2 оно позволяет нам „передавать" последовательность (z_i,u_i) в любом желаемом порядке и при этом принимать каждую последовательность правильно в соответствии с законом больших чисел по крайней мере в 1--е случаях из всех случаев, когда она передавалась, если число случаев стремится к бесконечности.

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

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

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

При рассмотрении каналов без памяти уже из самого их определения было ясно, как приступить к построению примера канала с ненулевой пропускной способностью. Наш главный результат относительно пропускной способности расширений заданного канала без памяти по существу означает, что пропускная способность таких каналов являлась бы неизменной и, кроме того, C_s = C_e. Существование максимизирующего р. в. на входе было очевидным. Из этих результатов также следовало, что теорема кодирования не выполняется, если Н > С. Естественно спросить, в какой мере эти результаты можно распространить, на дискретные каналы с памятью.

Сохранить равенство C_s = C_e без ограничения нельзя; немного погодя мы приведем пример, где C_s положительно, а C_e не определено, так как не существует никакой допустимой входной меры. Этот канал по необходимости имеет бесконечную память; для канала с конечной памятью предположение C_s = C_e не кажется неразумным.

По вопросу о том, достигаются ли в действительности C_s = C_e для каналов с конечной памятью, так же как по вопросу об отрицательном утверждении теоремы о кодировании при Н > С, трудно строить предположения, не имея нескольких хорошо изученных примеров таких каналов.

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

Обратимся теперь к построению разных примеров дискретных каналов, обладающих памятью. Наш первый пример будет относиться к тому случаю, когда C_s > 0, а C_e не определено. Пусть X, Y₁, p₁ (|х) и X, Y₂, p₂ (|х) -- два дискретных канала без памяти с ненулевыми пропускными способностями C₁ и С₂ соответственно, обладающие одним и тем же множеством передаваемых символов. Пусть Y = Y₁ Y₂. Тогда p₁ ( | х) и p₂ ( | х) могут рассматриваться как распределения вероятностей на Y. Для каждого х_? Х^I мы определяем вероятностную меру н ( | х_?) на Y^I, полагая

н ( | х_?) = […?p₁ ( | х_-1) ? p₁ ( | х₀) ? p₁ ( | х₁) ?… + (1.12)

+ …?p₂ ( | х_-1) ?p₂ ( | х₀) ?p₂ ( | х₁) ?…],

где х_? = (...,х_-1, х₀ , х₁, ...).

Легко убедиться в том, что X, Y, н ( | х_?) определяют канал с памятью. Ясно далее, что для любого входа µ() з (Y^I₁) = з (Y^I₂) = , а Y^I₁ и Y^I₂ измеримые и инвариантные множества на Y^I. Следовательно, з не является эргодической, а значит, и щ не может быть эргодической. С другой стороны, пусть С - пропускная способность канала без памяти X, Y, [p₁ ( | х) + p₂ (|х)], и пусть p р. в. на входе, при котором достигается С. Очевидно, что Сmax(C₁,С₂)>0, и легко видеть, что в X, Y, н ( | х_?) достигается эргодическая пропускная способность C_s = C для р. в., на входе имеющего вид произведения µ=……?p( )?p( )?… Отметим, между прочим, что этот канал удовлетворяет условию для m = 0. Простейшим случаем, для которого мы можем подсчитать скорость создания сообщений источника информации X^I, µ ( ), является случай, в котором р, ( ) определяется простой Марковской цепью. Простая (стационарная) Марковская цепь определяется заданием вероятностей „состояний" Р₁ ,. . ., P_N, удовлетворяющих условиям

= 1, и вероятностей „перехода" p_ij, i, j = 1, . . ., N, удовлетворяющих условиям , i=1, …N и , j=1, …, N.

Если X содержит N элементов x₁, .... , x_N, опpeделим вероятностную меру µ () на X^I, полагая

µ ([х_i]) = P_i; µ ([х_{i ,}х_j]) = P_i p _ij ; µ ([х_{i ,} х_j, х_k])= P_i p_ij p_jk и т. д.

Поскольку, очевидно,

µ ([х₀] | [x_-1,…, x_-n]) = µ ([х₀] | [x_-1] ,

получаем сразу же

H (K) = ([x_-1, х₀])| [x_-1]= _i p _ij (1.13)

Канал простого типа, обладающий конечной памятью, можно построить следующим образом. Выбрав два конечных абстрактных пространства X и Y, определим для каждой пары (х_{1 ,} х₂) X?Х на Y распределение вероятностей н₁ ( | х₁, х₂). Определим для любого х_? X^I на Y^I вероятностную меру, полагая н₁ ( | х_?) = …? н₁ ( | х₀, х_-1) ? н₁ ( | х₁, х₀) ? …, где x= (…,х_-1, х₀, х₁,…).

Легко убедиться, что X, У, н ( | х_?) действительно определяет канал, обладающий памятью m = 1. Если в качестве р. в. на входе этого канала взять µ ( ), определенную простой Марковской цепью, то легко увидеть, что тогда и ( ) и ( ) определяются простой Марковской цепью; таким образом, мы можем получить простое выражение для скорости передачи сообщений в канале относительно µ ( ).

Для того чтобы µ( ) была эргодической, достаточно, чтобы для определяющей ее Марковской цепи выполнялось условие p _ij >0 для всех i, j. Любое эргодическое р. в. на входе допустимо для канала, обладающего конечной памятью. Следовательно, нетрудно выбрать распределение н₁(|х₁,х₂) так, чтобы не обращалась в нуль скорость передачи информации канала относительно р. в. на входе приведенного выше типа. Мы, таким образом, имеем простой пример канала с памятью, для которого С_е > 0. Только что определенный канал имеет память m=1, однако удовлетворяет условию для m = 0. Нетрудно также построить каналы с конечной памятью, но удовлетворяющие условию для m = 0. Здесь мы приведем только основную идею построения. Исходим из того, что, грубо говоря, в сущности означает требование, чтобы „шумовые выборки", разделенные интервалом, большим m, были независимы, в то время как выборки, разделенные интервалом, не превосходящим m, были бы статистически зависимы. Шумовые выборки вообще описываются вероятностными процессами, т. е. последовательностью (вообще говоря, бесконечной) случайных величин. Нам нужен теперь стационарный процесс n_i, -- ? < i < ?, такой, что любые две группы величин n_i зависимы при любых индексах i одной группы и j другой группы, исключая случай, когда выполнено условие |i -- j| > m. Примеры таких процессов легко построить; если r_i, -- ? < i < ?, -- последовательность независимых одинаково распределенных случайных величин, то n_i= представляет процесс, удовлетворяющий; нужным требованиям.

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

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

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

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

Кодовые последовательности х = ( , {0,1}, j=1, 2,..., формируемые двоичным сверточным кодером, передаются с использованием сигналов двоичной частотной модуляции вида s_k(t) = cos 2рf_kt,0tT, k = 0,1, где E, T -- соответственно энергия и длительность сигнала, f_k = l_k/T, l_k-целые числа, l_k > 1. На выходе канала с замираниями наблюдается случайный процесс вида

у(t) = µ cos (2рf_kt +)+ n(t), 0 t T, (2.1)

где µ -- случайный коэффициент передачи канала, -- случайный фазовый сдвиг, n (t) -- белый гауссовский шум (АБГШ) со спектральной плотностью мощности N₀/2. При передаче последовательности x на выходе некогерентного демодулятора наблюдается последовательность у=(у⁽¹⁾,у⁽²⁾,…,у^{( j )} ,. . . ), которая обрабатывается декодером. Вектор у^{( j )}=(у₀^{( j )},у₁^{( j )}) , а его компоненты принимают значения

у₀^{( j )} = (µ_c^{( j )} + n _c0^{( j )})² + (µ_s^{( j )} + n _s0^{( j )})², (2.2)

у₁^(j) = (n _c1^{( j )}) ² + (n _s1^{( j )})²

при передаче символа х^{( j )} = 0, где µ_c^{( j )} µ^{( j )} cos, µ_s^{( j )} µ^{( j )}sin - квадратурные компоненты коэффициента передачи канала, соответствующие передаче j-го элемента последовательности сигналов, n _ck^{( j )}, n _sk^{( j )}, к = 0,1 -- случайные величины, определяемые влиянием АБГШ, - E/N₀ - отношение сигнал/шум. При передаче символа х ^{( j )}= 1 правые части равенств (2.2) меняются местами. Случайные величины µ_c^{( j )}, µ_s^{( j )}, n _ck^{( j )}, n _sk^{( j )}, k = 0,1 имеют гауссовское распределение с параметрами

= = = 0,

= = д_jl , (2.3)

= = = 0,

= = = = 0, i,j = 1,2,…

Из этого определения следует, что коэффициент передачи канала µ^{( j )}((µ_c^{( j )})²+(µ_s^{( j )})² имеет рэлеевское распределение. Память в канале с замираниями определяется видом зависимости элементов последовательности µ =( µ ⁽¹⁾, µ ⁽²⁾,…, µ ^{( j )}) , зависящей в свою очередь от характера зависимости элементов последовательностей

µ_c =( µ_c ⁽¹⁾, µ_c ⁽²⁾,…, µ_c ^{( j )} ) и µ_s =( µ_s ⁽¹⁾, µ_s ⁽²⁾,…, µ_s ^{( j )} ).

Положим, что

= = = , (2.4)

где 0 r 1.

Из определений (2.3) и (2.4) следует, что µ_c и µ_s -- независимые Марковские последовательности. Нетрудно показать, что последовательность µ в этом случае также оказывается Марковской, т.е. для любого N> 1 ее функция плотности вероятностей (ф.п.в.) w (µ) записывается в виде

w(µ) = w(µ⁽¹⁾) w(µ⁽²⁾ µ⁽¹⁾)...w(µ^(N) µ^(N-1)), (2.5)

w(µ) (2.6)

w(µ)

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

Для завершения формального описания модели канала нужно определить условную ф.п.в. w(y | х). Очевидно, что

w(y | x) = ( y | x, µ) w(µ)dµ, (2.7)

где ф.и.в. w(µ) определена равенством (2.5), а

w (y | x , µ) = (y^{( j )} | x^{( j )}, µ^{( j )}), (2.8)

где условные ф.п.в. w (y^{( j )} | x^{( j )}, µ^{( j )}), как следует из (2.2), представляют собой произведение ф.п.в. центрированного и не центрированного X² - распределения с двумя степенями свободы.

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

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

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

Представляет интерес оценить эффективность q-ичного кодирования линейным (п_j, k_j ) - кодом, у которого q=2^v-ичные символы образованы двоичными блоками длины v, расположенными в строках матрицы на рис. 1.

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

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

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

Как видно из рис. 1, б, набор P(j|k) (j, k=0,1, 2 , . . . , q--1) переходных вероятностей q=2^v-ичного однородного канала без памяти полностью определяется набором из 2^v вероятностей конфигураций образцов ошибок в строках матрицы рис. 1 (предполагается, что эти наборы одинаковы для всех строк).

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

P(j|k)=P(e(j,k)),j,k=0,1,...,q-1,(2.9)

где e(j,k)=v_j ? v_k, v_j и v_k -- двоичные представления чисел j и k соответственно, ? означает поэлементное суммирование по mod 2, P(e(j, к)) -- вероятность появления образца ошибки в виде двоичного вектора e(j,k) длины v. Исследуемый q-ичный канал не имеет памяти, а наборы переходных вероятностей для каждого из передаваемых элементов одинаковы и заданы (2.9).

Далее будем рассматривать две основные модели вероятностей конфигураций двоичных ошибок Р (е):

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

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

P(e)R_s^-1, s=|е|, s=1,2,…,v,

R_i=(2+h²) D_i-1-4r² D_i-2, D_i= D₁ D_i-1-4r² D_i-2, (2.10)

D₁=h²(1-r²)+2(1+r²), D₀=1.

Здесь h²=E/N₀ -- отношение средней энергии принимаемого элемента сигнала к спектральной плотности аддитивного белого шума в непрерывном

канале (этот параметр определяет среднюю вероятность ошибки символа p=1/(2+h²)); r -- коэффициент корреляции коэффициентов передачи канала на соседних элементах, который определяет «силу» памяти в канале (если r=0, то память отсутствует, если r=1, то канал квазибиномиальный и составной), Р(е:|е|=0)P (v, 0), где P(v, 0) --вероятность безошибочного приема блока в составном РЗК, рассчитывается по следующей рекуррентной формуле:

P (v, 0) = , P (1,0) = (2.11)

Рассмотрим верхние границы вероятностей ошибочного декодирования (P_од) в таких каналах, а также их пропускные способности, используя известные соотношения. Представляет интерес выяснить, будет ли P_од убывать при увеличении параметра v=log₂q в каналах с сильной памятью при фиксированной длине кодового блока n_f и как будет вести себя пропускная способность q-ичного канала без памяти при увеличении параметра v. Напомним, что при двоичном кодировании блоковым кодом длины v в каналах с сильной памятью P_од очень слабо зависит от v.

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

Оценка Галлагера для P_од в случае квазибиномиальной модели q-ичного симметричного канала без памяти принимает следующий вид:

P_од exp {- n_j E_r (R) }, (2.12)

E₀ (R) = ^1+p(2.13)

При скорости кода RR_kp = оптимальное значение =1, а при R>R_kp оно находится из уравнения

/ = R, (2.14)

где = .

Для биномиального канала (с независимыми ошибками), который является частным случаем квазибиномиального при P(v, i)=рⁱ (1--р)^v-i где р -- вероятность ошибки символа, выражения (2.12), (2.13), (2.14), сводятся к случаю обычного ДСК без памяти, а параметр v влияет на P_од как v - кратное увеличение длины кодового блока n_f.

Рассмотрим другой частный случай -- составной РЗК, который физически соответствует столь медленным замираниям, что коэффициент передачи канала практически не успевает изменяться на интервале Tv, где Т -- длительность двоичного сигнала. Для такого канала

P(v, i ) = ,(2.15)

P(i, i ) = ,(2.16)

где h² -- тот же параметр, что и в (2.10).

На рис. 2 представлена зависимость E_r(R) как функция v для различных значений параметра h², рассчитанная на ЭВМ.

На рис. 3 показаны зависимости верхних границ P_од от v при длине кодовых блоков n_f =24 и различных параметрах h² и аналогичная зависимость для биномиального канала при той же вероятности ошибки символа p=1/(2+h²), что и в составном РЗК для h²=25.

Рис.2 Зависимость E_r(R)

Рис.3 Зависимость верхних границ P_од

Из данных зависимостей видно, что, несмотря на сильную память по временной координате, переход от двоичного кодирования (v=l) к q=2^v-ичному при v>5--7 значительно увеличивает E_r(R), а следовательно, уменьшает границу P_од. (Так, при переходе от v = l к v=7 P_од при h²=25, R= и n_f =24 уменьшается примерно на 6 порядков.) Этот результат является несколько неожиданным, поскольку, как уже отмечалось ранее, чисто «временное» кодирование почти не приводит к уменьшению P_од.

На рис. 4 показаны зависимости пропускной способности на бит q=2^v -ичного симметричного канала без памяти с переходными вероятностями (2.9) квазибиномиального составного РЗК (2.14), которая рассчитывалась на ЭВМ по известной формуле C = |_с=0.

Рис.4 Зависимость пропускной способности

Здесь же показаны верхние границы С для пропускных способностей РЗК. (Заметим, что пропускная способность является асимптотической характеристикой, т. е. она реализуется в данном случае при n_f. Ранее было сделано предположение об ограниченности числа поднесущих n_f и поэтому понятие пропускной способности имеет смысл только как верхняя граница реализуемой скорости передачи при предельно малой величине P_од.)

Видно, что С при увеличении v монотонно возрастает, причем при v>50 наступает «насыщение». Значительное увеличение пропускной способности Рис. 4 (до 25%) можно получить, увеличивая v до величины 25--30, причем увеличение С происходит не за счет улучшения энергетики канала, расширения полосы частот сигналов и оптимизации формы непрерывных сигналов, а только за счет перехода от двоичного кодирования к q-ичному. Принципиально важным является выполнение процедуры декодирования в q-ичном канале по максимуму правдоподобия, а не исправление ошибок кратности менее t=[d/2]1 где d -- минимальное кодовое расстояние q-ичного (n_f, k_f)-кода. Действительно, если выполнено условие 2^v n_f -1, то q-ичный код можно выбрать максимальным, например Рида -- Соломона (PC). В этом случае, как известно d=n_f--k_f+1, и при исправлении только ошибок гарантированной кратности

P_од = (2.17)

Рассчитывая P_од по (2.17) для составного РЗК, например, для случая, когда R= , h²=25, n_f =24 и v=30, получим P_од =, в то время как расчет P_од по (2.11) для тех же параметров дает P_од5,910^-14. Переход к исправлению только стираний тем же PC-кодом уменьшает P_од до величины 7,910^-7, однако для формирования стираний в q-ичных символах необходимо вводить дополнительную избыточность в строках матрицы рис.1 для обнаружения ошибок и стирания тех q-ичных символов, где они обнаружены, что приводит к каскадному (n_t, k_t, п_f, k_f)-коду. Оптимизация в классе таких кодов при заданных параметрах n_f =24, R= k_tk_f / n_tп_f =1/4, n_t=30, h²=25 обеспечивает P_од 10^-4, что, как видно, значительно хуже, чем использование q-ичного кода с такой же скоростью передачи и при тех же параметрах канала.

Рассчитаем энергетический выигрыш от применения q-ичных кодов с оптимальным алгоритмом декодирования по сравнению с системой связи без кодирования, использующей тот же самый многочастотный модем при одинаковых информационных скоростях передачи и одинаковых вероятностях правильного приема равного числа информационных символов. В блоке q-ичного кода содержится k_fv двоичных символов и вероятность их правильной доставки не меньше, чем 1--P_од. Тогда вероятность безошибочного приема k_fv бит в системе без кодирования, использующей k_f частот, равна вероятности безошибочного приема k_f блоков длины v на каждой из частот, что для составного РЗК с независимыми столбцами в различных строках матрицы рис. 1 приводит к соотношению

P_од'= (v, 0). (2.18)

Задаваясь допустимой величиной P_од '= P_доп, находим, используя (2.15), (2.16), (2.18), необходимое для этого h₁². Далее полагая P_од = P_доп, где P_од рассчитывается по (2.12), находим требуемое для этого значение h² в системе с q-ичным кодированием. Энергетический выигрыш з (дБ) определим с учетом необходимости сокращения длительности элемента в 1/R раз в системе с кодированием для обеспечения равных информационных скоростей, что дает выражение

з (дБ) = 10 (2.19)

Для примера, выбирая P_доп =10^-3, n_f =24, R= , v=5, получаем, что энергетический выигрыш от применения q-ичного кодирования составит 28 дБ. Заметим, что данное значение энергетического выигрыша можно рассматривать как предельную величину при ограничении на время запаздывания и число частот модема. Открытым является вопрос о практическом приближении к такому выигрышу с помощью конструктивных методов кодирования и декодирования.

Оставаясь в классе квазибиномиальных каналов, для которых справедлива граница (2.12), представляет интерес найти «худшую» функцию кратности P(v, i), дающую минимальное значение E_r(R) при заданной величине вероятности ошибки символа р. Такая постановка задачи соответствует нахождению экстремума функции

f (, ,…, = (v,i)(2.20)

при дополнительных условиях

+ (v,i)=p,(2.21)

(v,i)=1,(2.22)

Рис.5 Зависимость E_r(R) как функция v

Решение данной задачи методом неопределенных множителей Лагранжа приводит к следующей границе для функции (2.20):

...