Modeling Markov chains in Galois fields

The automaton implementation of a determinate function is a probabilistic automaton $A_1=(S,Y,P_s,\lambda(s))$, where $S$ is the Markov chain state set, $P_s$ is an $m_1\times m_1$ stochastic matrix, $Y$ is the output alphabet of cardinality $m_2\le m_1$. The automaton implementation of a probabilistic function is a probabilistic automaton $A_2=(S,Y,P_s,P_y)$, where $S$, $Y$, $P_s$ are of the same sense as in $A_1$, while $P_y$ is a stochastic $m_1\times m_2$ matrix.
In this paper, we solve the problem of synthesis of generators of finite homogeneous Markov chains on the base of the analytical apparatus of polynomial functions over a Galois field. We suggest a method to calculate the coefficients of a polynomial in several variables which implements any mapping of the Galois field into itself. We study the case of implementing a finite automaton by a homogeneous computing structure defined over a Galois field; automaton mappings are implemented as polynomial functions over the Galois field.
As the base polynomials, we use polynomial functions over the Galois field
$$ f_1(x, s)=\sum_{i,j=0}^ra_{ij}x^js^i, \qquad f_2(s)=\sum_{i=0}^rb_is^i, $$
where $r=2^n-1$, $x,s,b_i,a_{ij}\in\mathit{GF}(2^n)$.
We give expressions of an automaton $A_1$ in the framework of a polynomial model over the field $\mathit{GF}(2^n)$ of the form $M_1=(\hat\mu_1, f_1(x,s),f_2(s))$, where $\hat\mu_1$ is the discrete random variable which takes values $\mu\in\mathit{GF}(2^n)$ determined by some probability vector $\bar P=(p_1,\ldots,p_{k_1})$ such that
$$ P_s=\sum_{i=1}^{k_1}p_iB_i, $$
where $B_i$ are stochastic Boolean matrices and $k_1\ge m_1^2-m_1+1$, and of an automaton\linebreak $M_2=(\hat\mu_1, f_1(x,s),f_2(s),\hat\mu',f_3(x',s))$, where $\hat\mu_1'$ is a discrete random variable which takes values $\mu' \in\mathit{GF}(2^n)$ determined by some probability vector $\hat P=(p_1,\ldots,p_{k_2})$ such that
$$ P_y=\sum_{i=1}^{k_2}p_iB_i, $$
where $B_i$ are stochastic Boolean matrices and $k_2\ge m_1^2-m_1+1$. The problem of representation of a discrete random variable over the field $\mathit{GF}(2^n)$ has been solved earlier.
This research was supported by the Russian Foundation for Basic Research, grant 99–01–00163.