NUMERICAL SIMULATION OF BINARY MULTILINK MARKOV CHAIN

Abstract

The paper presents an extended version of the algorithm of numerical simulation of multi-link Markov chain with stationary transition probabilities. The results of the algorithm using for assessing the adequacy of speech signals parameterization with Markov chains of higher orders are obtained and analyzed.

Full Text

Введение Марковские модели нашли широкое применение при описании случайных процессов в радиотехнических [1-6], связных и телекоммуникационных системах [7-9]. Простые и сложные (многосвязные) цепи Маркова используются при решении задач: фильтрации и сегментации изображений и видеопоследовательностей [10-12], поиска и кодовой синхронизации сигналов широкополосных систем связи [13-15], оценки трафика [16], параметризации и распознавания речевых сигналов [17-19] и т.д. Однако полноценное аналитическое исследование поведения сложных нелинейных систем с протекающими в них случайными процессами зачастую затруднительно. В качестве альтернативы в таких случаях используются методы имитационного и статистического компьютерного моделирования, для которых важно наличие простых в реализации алгоритмов формирования случайных процессов с заданными характеристиками. В данной работе предлагается расширенный вариант алгоритма формирования цепи Маркова [20-21] для случая многосвязной однородной бинарной цепи. Постановка задачи Многосвязная (связности т) однородная бинарная цепь Маркова задается вектором начальных вероятностей Р = [/?1?/>2] состояний sx, s2 (st= 0,1) и условными вероятностями | ...s(k~m)s(k~m~l)...) = = p(s™ (1) которые можно отобразить матрицей переходных вероятностей в следующем виде * -'l ..5, Пп...п ПП..Л2 П = SjSj. ..S2 ^11...21 Щ1...22 S2S2- ••^2 _Л22..21 П22...22 4.s*=P(S ,(*) I и (2) где я ^9 j9 7*9 ^ * Матрица (2) должна удовлетворять условию нормировки (3) 1=1 Требуется разработать алгоритм численного моделирования однородной цепи Маркова с заданными вектором начальных вероятностей Р и матрицей переходных вероятностей (2). Преобразование многосвязной цепи Маркова в простую цепь Пусть многосвязная (связности т) цепь Маркова задана двумя состояниями: sl, s2 (st = 0,1) и условными вероятностями вида (1). Перейдем от нее к простой цепи Маркова, формируя вектор s(k) = длины т [22]: (4) где ij,k,n = 1,2. При m = 2 условные вероятности (1) принимают вид /Ч*) ^-i) Pis | s Sj I bj ), (5) где ij,k,n = 1,2. Число состояний полученной таким образом простой цепи Маркова равно M = 2т. При заданных условных вероятностях (1) можно определить вероятности перехода (4) Мк) r(*-i)\ ш \s = «Инфокоммуникационные технологии» Том 12, № 2, 2014 Прозоров Д.Е., Плетнев К.В. 9 p(s?s\k-l) \ П 1 (к-т+1) (к-1) (к-т+1) (к-т) \ ' j ’i ' j г ) р p[s ^(*-1) s(k-m+l)s(k-m) j (*)„(*-!) Jk-m+l)(k-m n лг ") р\ ' s{k~^ ...s{k~m+V) s{k~m)'' 1 (6) =Г& (*) I Jk-m+\) (k-m) At ...Aj йг )• где i,j,...,r,n = 1,2. В дальнейшем будем рассматривать только однородные цепи Маркова, где условные вероятности (4) не зависят от номера шага к. При т = 2, например, получим четыре комбинации состояний: , .s'j.s'j , s2sl, s2s2 и матрицу переходных вероятностей размером 4x4: (7) ад S1S2 S2Sl S2S2 J,Jl Л112 0 0 П = sxs2 0 0 Л121 Ы to S2S1 Л211 7t2i2 0 0 S2S2 0 0 Л221 ^222. p( Sn Sj 1 Sj -•ун1 , Uj и = 1,2 Нулевые элементы матрицы переходных вероятностей П' (7) соответствуют вероятностям невозможных событий. Аналогичным образом можно получить матрицы переходных вероятностей для общего случая т>2. Для элементов квадратных матриц вида (7) должны соблюдаться модифицированные условия нормировки и=1 и согласованности 2 _ *=1 (8) (9) где pjn = P^s^sf^). В [22] показано, что для введенной таким образом простой цепи с квадратной матрицей вида (7) соблюдаются разностные уравнения ,(*) = р(*-1)1Г = р(0) [irf, (10) где - вектор безусловных вероятностей всех возможных комбинаций состояний на к-ом шаге. Например, для т = 2 М. = [p(j«^)], i,j = 1,2. (11) Алгоритм численного моделирования многосвязной бинарной цепи Маркова Полученные соотношения позволяют сформировать алгоритм численного моделирования многосвязной однородной бинарной цепи Маркова, заданной вектором начальных вероятностей Р = \рх,р2\ состояний ^, s2 (st = 0,1) и матрицей переходных вероятностей П (2). Алгоритм моделирования состоит из следующих шагов. 1. На основании заданной матрицы переходных вероятностей П (2) и соотношения (6) формируется квадратная матрица П вида (7). 2. Генерируются m значений случайной величины Е , равномерно распределенной на интервале [0,1). 3. Формируются m первых состояний sl,...,sm сложной бинарной цепи Маркова в соответствии с правилом s.- = \siAi^pr, {s2£i> Pi- 4. Генерируется k-ое значение %k случайной величины Е, равномерно распределенной на интервале [0,1). Если sk_^ , i = 1,2, то h = 5 ^>k - %Л1 > IS2 > ^>k > • Здесь n'y nr - элемент сформированной ранее матрицы переходных вероятностей П'. Результаты эксперимента Предложенный алгоритм численного моделирования многосвязных бинарных цепей Маркова использован для оценки адекватности параметризации речевых сигналов цепями Маркова высших порядков. Для эксперимента выбраны фрагменты речевых сигналов с частотой дискретизации 8 кГц. В работах [17-18] показано, что компромисс между эффективностью распознавания речевых команд и вычислительной сложностью алгоритма параметризации достигается при использовании (для оценки параметров аппроксимирующей цепи Маркова) от одного до четырех старших бит равномерно квантованного речевого сигнала. Наименьшей вычислительной сложностью обладают методы параметризации по одному старшему значащему биту фрагмента речевого сигнала. «Инфокоммуникационные технологии» Том 12, № 2, 2014 10 Прозоров Д.Е., Плетнев К.В. Эксперимент заключался в выполнении следующих действий: - расчет параметров простой (или многосвязной) цепи Маркова, аппроксимирующей бинарную последовательность, образованную старшим битом фрагмента речевого сигнала; - синтез искусственной цепи Маркова с параметрами, полученными в результате выполнения п.1, по предложенному в данной статье методу численного моделирования, и - оценка близости корреляционной функции сформированной цепи Маркова к корреляционной функции бинарной последовательности, образованной старшим битом параметризируе-мого фрагмента речевого сигнала. Результаты расчетов представлены на графиках рис. 1-3, где 1 - АКФ старшего бита па-раметризируемого фрагмента речевого сигнала; 2 - АКФ бинарной последовательности, синтезированной по модели простой цепи Маркова; 3 - АКФ бинарной последовательности, синтезированной по модели многосвязной цепи Маркова второго порядка. Очевидно, что для исследованных случаев (см. рис. 1-3) модель многосвязной цепи Маркова второго порядка является более адекватной по сравнению с моделью простой цепи. Выводы Разработанный алгоритм позволяет моделировать многосвязные бинарные цепи Маркова и обладает низкой вычислительной сложностью. Полученные в эксперименте результаты свидетельствуют о необходимости применения моделей многосвязных цепей Маркова в задачах марковской параметризации речевых сигналов. Указанный вывод согласуется с работой [18], где показано, что применение модели многосвязной цепи Маркова позволило повысить вероятность автоматического «дикторозависимого» распознавания речевых команд.