Моделирование цепей Маркова в полях Галуа
Ш. Р. Нурутдинов
Аннотация:
Автоматной моделью детерминированной функции является вероятностный автомат
$A_1=(S,Y,P_s,\lambda(s))$, где
$S$ — множество состояний цепи Маркова,
$P_s$ — стохастическая матрица размера
$m_1\times m_1$,
$Y$ — выходной алфавит мощности
${m_2\le m_1}$. Автоматной моделью вероятностной функции является вероятностный автомат
${A_2=(S,Y,P_s,P_y)}$, где элементы
$S$,
$Y$,
$P_s$ те же, что в
$A_1$, а
$P_y$ — стохастическая
$m_1\times m_2$ матрица. В настоящей работе решается задача синтеза генераторов конечных однородных цепей Маркова на основе аналитического аппарата полиномиальных функций над полем Галуа. Предложен способ вычисления коэффициентов полинома от нескольких переменных, моделирующего любое отображение поля Галуа в себя. Исследован случай моделирования любого конечного автомата однородной вычислительной структурой, определенной в поле Галуа, причем автоматные отображения реализуются как полиномиальные функции в поле Галуа. В качестве базовых полиномов используются полиномиальные функции над полем Галуа
$$
f_1(x, s)=\sum_{i,j=0}^{r}a_{ij}x^js^i,\qquad
f_2(s)=\sum_{i=0}^{r}b_{i}s^i,
$$
где
$r=2^n-1$,
$x,s,b_i, a_{ij}\in\mathit{GF}(2^n)$. Приведены представления автомата
$A_1$ полиномиальной моделью над полем
$\mathit{GF}(2^n)$ вида
$M_1=(\hat\mu_1, f_1(x,s),f_2(s))$, где
$\hat\mu_1$ — случайная дискретная величина с множеством значений
$\mu\in\mathit{GF}(2^n)$, задаваемая вектором вероятностей
$\bar P=(p_1,\ldots, p_{k_1})$ таким, что
$$
P_s=\sum_{i=1}^{k_1}p_iB_i,
$$
где
$B_i$ — стохастические булевы матрицы и
$k_1\ge m_1^2-m_1+1$, и автомата $M_2=(\hat\mu_1, f_1(x,s),f_2(s),\hat\mu',f_3(x',s))$, где
$\hat\mu_1'$ — случайная дискретная величина с множеством значений
$\mu'\in\mathit{GF}(2^n)$, и вектором вероятностей
$\hat P=(p_1,\ldots,p_{k_2})$ таким, что
$$
P_y=\sum_{i=1}^{k_2}p_i B_i,
$$
где
$B_i$ — стохастические булевы матрицы и
$k_2\ge{m_1}^2-m_1+1$. Задача представления случайной дискретной величины над полем
$\mathit{GF}(2^n)$ была решена ранее.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 99–01–00163.
УДК:
519.7 Статья поступила: 10.04.2002
DOI:
10.4213/dm159