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

УДК 681.5:654.93 ББК 32.97

В. А. ПЕСОШИН, НА. ГАЛАНИНА, Н.Н. ИВАНОВА

ВЫЧИСЛЕНИЕ ПЕРЕХОДНЫХ ВЕРОЯТНОСТЕЙ ЦЕПЕЙ МАРКОВА ПРИ СИНТЕЗЕ УСТРОЙСТВ ОБРАБОТКИ СИГНАЛОВ В ЛИНЕЙНЫХ ФАЗОВЫХ СИСТЕМАХ

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

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

V. PESOSHIN, N. GALANINA, N. IVANOVA CALCULATING MARKOV CHAINS TRANSITION PROBABILITIES WHILE SYNTHESISING SIGNAL-PROCESSING HARDWARE IN LINEAR PHASE SYSTEMS Key words: Markov signals, transition probabilities, linear phase system. At the first stage of synthesis of various digital signal-processing hardware approximated by Markov chains it is necessary to determine a transition probability matrix. Its elements can be found by use of a signal phase distribution function. The paper presents analytical formulas for calculating a three-dimensional function of phase distribution in linear phase space. These formulas allow calculating transition probabilities and constructing a weight matrix for a special-purpose processor designed for optimal digital signal-processing.

Определение матрицы переходных вероятностей является одной из основных задач синтеза цифровых устройств обработки марковских сигналов [1-3, 6]. Элементы этой матрицы (pap...y) можно найти с помощью функции распределения фазы сигнала. В случае использования двухсвязной цепи Маркова при аппроксимации сигнала в линейной фазовой системе необходимо вычислить трехмерную функцию распределения фазы.

Если сигнал на входе АЦП считать гауссовым, то случайный процесс на выходе узкополосной линейной системы с резонансной частотой ю0 может быть представлен в виде

^(t) = A(t)cosro0t + C(t)sin&0t, где A(t) и C(t) - квадратурные компоненты комплексного гауссового процесса:

Е j = Aj + iCj, j = (...,-1,0,1,...),

где Aj(t) - реальная и Cj(t) - мнимая части, также являющиеся стационарными и стационарно связанными случайными функциями, совместное распределение которых нормально [5].

Случайный процесс E,(t) стационарен в широком смысле в случае, если он имеет ковариационную функцию, зависящую только от разности (j - k), а не от шагов j и k.

Обозначим Aj = X; Cj = Yj и определим для них моменты 1-го и 2-го порядков следующим образом:

M[Xj] = M[Yj] = 0; M[Xj] = M[j = a2; (j = ...,-1,0,1,...);

M [ X, X, ] = M [Yj ,Yk ] = K R

при j - k = x, при j - k = 2x;

при j Ф k ( j,k = ...,-1,0,1,...);

M [ X j ,Yk ] = -M [Yj, Xk ] =

с2 S1 при j - k = x; с2S2 при j - k = 2x;

0 при j = k.

Из последнего условия следует, что Xk и Yj независимы в совпадающие моменты времени [5].

Совместное распределение A(t) и C(t) в три момента времени t1, t2 и t3 представляет собой шестимерное нормальное распределение с нулевым математическим ожиданием и дисперсией с .

Тогда соответствующая корреляционная матрица будет равна:

A

A

M

( 1

0

Ri

Si R2

V S2

0 1

- Si Ri

- S2 R2

Ri

- Si i 0 Ri

Si

Ri 0 i

- Si

R2

- S2

Ri

- Si i 0

S2 л R2

Si

Ri 0 i

v2 Si Ri - y

Введем следующие обозначения: R1 = a ; Sx = b ; R2 = c ; S2 = d. Тогда

M(ti, t2) =

a

( i 0

0 i - b

a - b i

b a 0

c - d a

d c b

c

d л

a - d c

0 a b

1 - b a - b i 0

a 0 i

Детерминант матрицы M(ti, t2) равен

D* = detM(ti,t2) = [i - 2(a2 + b2) - (c2 + d2) + 4abd + 2(a2 -b2)c]2. Вычислим алгебраические дополнения Dik матрицы M(ti, t2): Dtl = i - 3a2 - 3b2 + 2a4 + 2b4 + 4a2b2 - 4a3bd + 4abd - 4ab3d + 2a2c -

- 2a4c + a2d2 + a 2c2 + b2d2 + b2c2 - d2 - c2 + 2b 4c - 2b 2c для i = i, 6;

Цг+i = Di+ii =0 для i = ï, 5;

Di3 = D31 = D46 = D64 = D24 = D42 = D35 = D53 =

= -a + 2a3 + 2ab2 - 6a2bd - 4a3c+ac - 2b3d+bd + 2a3c2 + +4ab2d2 -

- 2ab2c2 + 6a 2bcd - bd3 - bc2 d - 2b3cd+ac2 - acd2 - ac3 + ad2; D14 = D41 = D36 = D63 = -D23 = -D32 = -D45 = -D54 =

= -b + 2b3 + ad - bc + 2a2b - 2a3d - 6ab2d + 4b3c + 4a2bd2 - 2a2bc2 + + 2b3c2 + 2a 3cd + 6ab 2cd + bd2 - ad3 - ac 2d + bcd2 + bc2 + bc3;

Д5 = £>51 = D26 = D62 =

26

'62

= -2а4 + а2 - Ь2 + 2а2с - с + 2Ь2с + 2Ь4 - 4а2Ь2с + 4аЬ - 4аЬ^ + + Ь2 d2 + 3Ь2 с2 + 2Ь 4с - аV2 - 3а 2с2 + 2а 4с - 4аЬсё + с^2 + с3; Дб = Бб1 =-^25 =-^52 =

= -4аЬ3 - 4а2Ь + 2аЬ + 2Ь 2d - d + 2а^ - 4аЬ3с + Ьа2Ь2d - бaЬd2 -

- 2аЬс2 + 4а3Ьс - 2а^с + 2Ь2dc + с2d + d2. Выражения для алгебраических дополнений принимают компактный вид

после деления на л/Б*:

Djj = [1 - (a2 + b2)][1 - 2(a2 + b2) - (c2 + d2) + 4abd + 2(a2 -b2)c];

,2 , j.2

22

D31 = (ac + bd - a)[1 - 2(a2 + b2) - (c2 + d2) + 4abd + 2(a2 - b 2)c];

22

Б41 = ^ - Ьс - Ь)[1 - 2(а2 + Ь2) - (с2 + d2) + 4aЬd + 2(а2 - Ь2)с]; Б51 = (а2 -Ь2 - с)[1- 2(а2 + Ь2) - (с2 + d2) + 4aЬd + 2(а2 -Ь2)с]; Бб1 = (2аЬ - d )[1 - 2(а2 + Ь2) - (с2 + d2) + 4aЬd + 2(а2 - Ь 2)с]; Б23 = ^ - Ьс - Ь)[1 - 2(а2 + Ь2) - (с2 + d2) + 4aЬd + 2(а2 - Ь 2)с]. Тогда шестимерное распределение огибающей х = Л(0 и фазы у = С(0 в моменты времени I, ^ + х, ^ + 2х:

^б(xl,х2,xз,У1,У2,У3) =-Л Г— ехРМ;

(2лст 2)Ч D *

у =

у =

1

1

2a2 D*

ZZAkxixk

i=1 k=1

f M (хг) = 0 M (Xk) = 0

Л

2a2 VD*"{[1" (a2 + b 2)][X12 + X22 + X32 + y2 + y22 + Уз] + + 2(a - ac - bd)(x X2 + y У2 + X2 X3 + У2 Уз) + + 2(b + bc - ad)(X1 У2 - X2У1 + X2уз - X3У2) + + 2(a2 -b2 -c)(x1 X3 + y1 Уз) + 2(2ab-d)(x1 Уз -У1Х3)}. Произведем замену переменных

Xi = ricos 0i - ui;

У] = г3 81П 91 - ,

^ = Я? + ^ = Л0(Г);

^02 = ^2 + ^2 = R0(2T),

а = ^01СО8901; Ь = ^т 9ох;

с = ^02СО8902; d = ^02^ 902; Г\ ^ ~

901 = агс*8~71; 9 02 = ,

имеем для случая слабого сигнала (щ = 0; у = 0):

обозначив

учитывая, что

^б(гь г2, г3,0!, е2, е3, +х, г+2т) =

Г!Г2Г3 , 1

гехр{--

[(1 - ^21)(/12 + Г2 + Гз2) +

" (2л—2)3 л/О* 2-2л/й*

+ 2^01^02^008(02 -01 + 002 -001) + 2^)1^02^Г3 008(03 -02 + 002 -001) + (1) + 2^1^3 008(03 -01 + 2001) - 2Д01ПГ2 008(02 -01 +001) -

- 2^01Г2Г3 008(03 -02 +001) - 2^02^008(03 -01 +002)]}.

Трехмерное распределение фазы узкополосного гауссового случайного процесса находится тройным интегрированием (1) по г1, г2 и г3.

Учитывая, что энергетический спектр случайного процесса симметричен относительно средней частоты узкополосной системы, примем [5, 7] 51 = 52 = 0, а значит, 001 = 002 = 0, тогда Я01 = Яь Я02 = Я2 и, следовательно:

1 ададад 1

^3(01,0 2,03, г, т,2т) = -—= Ц|Г1Г2 Г3 ехр{- —^ [(1 - Л,?1)(Г12 + Г2 + Г2) + 8л3л/О 000 2-ЫО

+ 2(^01^02 -Я01МГ2 008(01 -02) + 2(^01^02 -Ял)^ 008(02 -03) +

+ 2(р2 - Я02)г1г3008(03 -01)]}^г1^г2^г3 .

Заменим переменные

_ = _ = Г2 - ^ = Г3 —

— —

и при вычислении значения интеграла воспользуемся формулой

ад

*со8Ф= £(-\)"1п(.

Тогда

Ж3(01,02,03, г, т,2т) =

1 ададад -

—тоТ 101 ^3е

8л Vи 000

£

х £ Iл

й=-ад

Обозначим

Я01 (Я02 - 1) ТО*

Г р2 - р Л01 02 „ ,

Л

\

(

1а

V

е' 2 3 .

< £ 1ь

Ь=-ад

Я01 (Я02 - 1) л/О*

¿Ь

ВаЬй =

X1Ь

1 ададад

8"Г7йТ0 0 0 ^

8л \и 000

Р01(Р02 -1) , •

(г? +г! +г32)(1-Д021) Г

Л Г я2 - Я

X 1 „

х I

а

Л

Я01(Я02 -1) ,

ТО*

л/О*

Отсюда

ададад

^3(01,02,03, г, т,2т) = £ £ £ В

аЬй

г[(а-й)01+(Ь-а)02 +($-Ь^] .

а=-ад Ь=-ад й=-ад

п=-ад

24 О

X

X

X

а=-ад

2V О

X

Иначе трехмерную плотность распределения вероятностей фазы гауссо-вого случайного процесса можно записать следующим образом:

ад ад ад

Ж3

а=-ад Ь=-ад й=-ад

Коэффициенты В^а находятся разложением функций Бесселя в степенной ряд вида:

( \ ад г+2п г+2п г+2п

I

<1212 2

= Ё

21 22

5 г + 2п , „мог+2п

Следовательно,

1

ВАй =

8л3

ЯТ0 рг+2п п!(п + г)!2

Т=Г Ш212223 Ё

V Б 0 0 0 п=0

ад / ¡а+2п а+2п а+2п ^ ад ^ *Ь+2к Ь+2к Ь+2к Л

. 21 22 п!(п + а)!

Ё

к=0

. 21 22 к!(к + Ь)!

/

^ ад + 21 й+21 0 +21 | (1-ЛщХ+ г| + 232) ' 21 22

к=0 1!(1 + Ь)!

й22 023,

где . = Ц»1^ ~1}; г = Б = 1 - 2< - Л + 2^.

Тогда, учитывая, что

' 1 | (2п -1)!

|х2пе 2 йх = (2п - 1)!^я и Г^п + ^ = ^^,

1 - Л 2

получим

Б

2 ад ад ад г г> / г> 1Мс+Ь+2п+ 2к

_ = Б! ^^ [Л01( Л02 - 1)]

ПМ ~ 0 3 ¿и ¿и ¿и

8л3 п=0к=01=0п!(п + а)!к!(к + Ь)!1!(1 + й)! + / 2

[< -Л02]й+21 Г^ + п +1 + 1|Г| + п + к + 1|Г| ^ + к +1 +1

аг>2 \а+Ь+й+2п+2к+21+3

Итак:

В = | Б* | Ё [Л01(Л02 - 1)]с+Ь+2п+2к[Л021 - Л02]й+21

ВсЬй —- / -

8л3 п,к1=0 п!(п + а)!к!(к + Ь)!1!(1 + й)!

г[ +п+1+^ С^+п+к + ^+к+1 +1

Х (1 - Л 2 ) с+Ь+й+2п+2к +21+3 '

Чтобы определить трехмерную плотность распределения вероятностей случайного процесса на выходе широкополосного ограничителя, из (2) надо получить статистические характеристики косинуса фазы функциональным преобразованием 2 = cos9г,  = 1, 2, 3. Каждой точке объема (212223) соответствует шесть точек плоскости 919293:

911 = arccos 21; 912 =-arccos 21; 922 = arccos 22; 921 =- arccos 22; 933 = arccos 23; 931 =- arccos 23.

х

X

Модули якобианов преобразования

5

&1&2&3

5

дz1дz2дz3

5

дг1дг2дг3

5

дг1дг2дг3

д

дz1дz2дz3

6

дг1дг2дг3 Из (2) имеем:

Wз(Zl, 22,23, Т,2т) =

дz1дz2дz3

1

дz1дz2дz3

1

ТО011,022,033, т,2т) + Wз(еll, 022,031, Т,2т) +

+»5(011,021,033, т,2т)+»5(011,021,031, т,2т)+»3(012,022,033, т,2т)+Wз(еl2,е22,031, т,2т) + + Wз (012,021,033, т, 2т) + Wз (012,021,031, т, 2т)].

Так как

^3 (011,022 , 033,т,2т) = 008а(011 - 022)008Ь(022 - 033 ) 008й(033 -011) = = [008(а аГ0008 21 )008(а аГ0008 22 ) + 8т(а аГ0008 21) 8т(а аГ0008 22)] X = [008(Ь аГ0008 22 )008(Ь аГ0008 23 ) + 8т(Ь аГ0008 22 ) 8т(Ь аГ0008 23 )] X = [008(й аГ0008 21 )008(й аГ0008 23) + 8ш(й аГ0008 23 ) 8ш(й аГ0008 21)], то выражение для трехмерной плотности распределения вероятностей на выходе ограничителя имеет вид:

16

^в(008 01,008 0 2, 008 03, т,2т) =

71 - 2^71 - 2171-1

X £ВЛй[Та (^ (22)Ть (22)Ть (23)Тй ЬТ (2з) + иа (21)и ^Ь № № (23)],

а,Ь,й=-ад

где Т^) - полиномы Чебышева первого рода; Щ^) - полиномы Чебышева второго рода.

Распределение вероятностей можно искать через числовые моменты распределения т^к на выходе АЦП 0 помощью интеграла:

+1+1+1

т

= 00 0'? V (21) 81 ( 22 ) 8 К ( 2з )Wз ( 21, 22,23, т, 2^^ 2 $23 ,

-1-1-1

вычисление которого сводится к нахождению интегралов вида: а) у 8"((Zl)dZl, 6) '/ 8"(^^(

-1 71 - 212 -1 Ф - 212

Интегрируя по частям ( яV (^1) = и ; йи =vg4,-1 (^)я), получим: а) йУ = Т^Щ!

у = 8т[(г - аг0008+ 81п[(г + аг°°°8= Уг^ + Уг+, при г ^ ^ .

2

2

2

У = 1аг0008+——8т[2гаг0008при г = х . 2 4г

х

б) йТ = УМЪ2 ^

Т s1n[(г - s)arccos s1n[(г + .^гс^ уг -„ ^ уг+, (^1) . V =---=---при г Ф 8 ;

2

2

2

V = !arccosЪ --4-зт[2г arccosпри г = 8 . Учитывая, что У (-1) = У (+1) = 0, имеем:

т

^к = 16 Ё ВаЪй

а,Ъ,й=-ад

V8^

1(N - 1)г

+ -

2

Л

х Ё18 ^ ) j ^-1 Г Уъ-й

Ё 8 "ЧЪ ) i v-lf Уа-Ъ

+Ё

Щ N - 1)v

2

Ё

1(N -1)"

+

Л

2

т

1 8 ^

'(N -1)к [ 2(а - й) 2(а + й) := 16 Ё В

при а ф Ь ; Ь ф й ; а ф й ;

^к

-ад (N - 1)^+к

N-1 Г 1 1 |

Ё 8 ^ (Ъ ) ^ [ - arccos Ъ + —У 2а (Ъ)1 х

N-1 Г 1 1 | N-1 Г 1 1 |

X Ё8М(ЪК-1| ^гсш^ +—У2с(Ъ) |х Ё8^) Н +—^а(Ъ)j +

N-1

+ Ё8)г^-1 f'~arccosЪ -"41сУ2с

N-1

х Ё8К_1(Ъ)^-1 Ъ -"41аУ2а(Ъ) | при а = Ь = 0;

или

ад 2 N-1

т,цк=16 Ё В

^к

= ЁЁ 8 "ЧЪ ) ^

аЪй

а,Ъ,й=-ад

Г Уа-Ъ (Ъ ) + (_1). Уа+Ъ (Ъ ) 1

í=1 г=1

2

2

Уъ-а

Ё

2

+НУ

2

«^(Ъ К-1 хЁ

Уа-й

2

+(-1У

2

к-^ \-к-1

8к-1

при а ф Ь; Ь ф й ; а ф й .

mvцк= 16 Ё В

^^ ^ аЬй ,д7- 1Л

а,Ь,й=-ад

N-1

г=1 г=1

2 N-1 Г 1

^+КЁЁ 8 V-1(Ъ' ) ^ ( ~arCCОSЪг + (-1)гУ2а (Ъг) 1х

/1

N-1

^Г1

х Ё^ (Ъ)^1^-arccoS;г + (-1)гУ2а(Ъ)Jх ЁЁЁ^"ЧЪ)^-1^-arccoS;г + (-1)гУ2а(Ъ)J;

при а = Ь = О.

х

х

х

1 =1

X

х

=1

=1

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

Литература

1. Иванова Н.Н. Устройства вычислительной техники для цифровой обработки сигналов, аппроксимированных цепями Маркова, в системе остаточных классов: дис. ... канд. техн. наук. Казань, 2011.

2. Иванова Н.Н. Непозиционные устройства обработки сигналов, аппроксимированных цепями Маркова // Информационные технологии в профессиональной деятельности и научной работе (Информационные технологии 2010): материалы Всерос. науч.-практ. конф. Йошкар-Ола, 2010. Ч. 2. С. 134-137.

3. Лебедев Е.К. Быстрые алгоритмы цифровой обработки сигналов. Красноярск: Изд-во Краснояр. ун-та, 1989. 192 с.

4. Лебедев Е.К., Галанина Н.А., Иванова Н.Н. Вычисление вероятностей переходов для цепей Маркова, аппроксимирующих сигналы в фазовых системах // Вестник Чувашского университета. 2001. № 3. С. 89-100.

5. Левин Б.Р. Теоретические основы статистической радиотехники. 3-е изд., перераб. и доп. М.: Радио и связь, 1989. 656 с.

6. Песошин В.А., Галанина Н.А., Иванова Н.Н. Марковская фильтрация цифровых сигналов в системе остаточных классов // Параллельная компьютерная алгебра и ее приложения в новых инфокоммуникационных системах: сб. науч. тр. 1-й междунар. конф. (20-24 октября 2014 г., Ставрополь, Северо-Кавказ. федер. университет). Ставрополь: Фабула, 2014. С. 331-337.

7. Тихонов В.И. Статистическая радиотехника. 2-е изд., доп. и перераб. М.: Радио и связь, 1982. 624 с.

References

1. Ivanova N.N. Ustroistva vychislitel'noi tekhniki dlya tsifrovoi obrabotki signalov, approksi-mirovannykh tsepyami Markova, v sisteme ostatochnykh klassov: dis. ... kand. tekhn. nauk [Computing device for digital signal processing, the approximate Markov chains, in the residue number system. Doct. Diss.]. Kazan, 2011.

2. Ivanova N.N. Nepozitsionnye ustroistva obrabotki signalov, approksimirovannykh tsepyami Markova [Nonpositional signal processing apparatus approximated by Markov chains]. Informatsionnye tekhnologii v professional'noi deyatel'nosti i nauchnoi rabote (Informatsionnye tekhnologii 2010): materialy Vseros. nauch.-prakt. konf. [Proc. of Rus. Conf. «Information technologies in professional and scientific work (IT 2010)»]. Ioshkar-Ola, 2010, part 2, pp. 134-137.

3. Lebedev E.K. Bystrye algoritmy tsifrovoi obrabotki signalov [Fast algorithms for digital signal processing]. Krasnoyarsk, Krasnoyarsk University Publ., 1989, 192 p.

4. Lebedev E.K., Galanina N.A., Ivanova N.N. Vychislenie veroyatnostei perekhodov dlya tse-pei Markova, approksimiruyushchikh signaly v fazovykh sistemakh [The calculation of the transition probabilities for Markov chains, approximating signals in phase systems]. Vestnik Chuvashskogo universiteta, 2001, no. 3, pp. 89-100.

5. Levin B.R. Teoreticheskie osnovy statisticheskoi radiotekhniki. 3-e izd., pererab. i dop. [Theoretical Foundations of Statistical Radio Engineering. 3rd ed.]. Moscow, Radio i svyaz' Publ., 1989, 656 p.

6. Pesoshin V.A., Galanina N.A., Ivanova N.N. Markovskaya fil'tratsiya tsifrovykh signalov v sisteme ostatochnykh klassov [Markov filtering digital signals in the remaining classes]. Parallel'naya komp'yuternaya algebra i eeprilozheniya v novykh infokommunikatsionnykh sistemakh: sb. nauch. tr. 1-i mezhdunar. konf. [Proc. of 1st Int. conf. «Parallel Computer Algebra and its Applications in new infocommunication systems»]. Stavropol, Fabula Publ., 2014, pp. 331-337.

7. Tikhonov V.I. Statisticheskaya radiotekhnika. 2-e izd., dop. i pererab. [Statistical radiotech-nology. 2nd ed.]. Moscow, Radio i svyaz' Publ., 1982, 624 p.

ПЕСОШИН ВАЛЕРИЙ АНДРЕЕВИЧ. См. с. 168.

ГАЛАНИНА НАТАЛИЯ АНДРЕЕВНА. См. с. 168.

ИВАНОВА НАДЕЖДА НИКОЛАЕВНА. См. с. 168._